Data-directed programming in Haskell (SICP 2.4.3)
I have a copy of sicp, or as it is also known, The Wizard<br>Book.11 Structure and Interpretation of Computer Programs; Abelson and<br>Sussman; mit Press; 1996. This book is widely praised, but I can’t take the<br>time to work my way through all of it. Instead, I’m going to occasionally jump<br>into the parts of it that look interesting. Last week, we looked at tagged data<br>in Haskell. The authors of sicp weren’t convinced that’s the best approach, so<br>they move on to data-directed programming. We’ll do the same.
Complex numbers have four operations
Complex numbers can be stored in their rectangular form, with a real<br>and an imaginary part. They can also be stored in polar form, where there’s a<br>magnitude and an angle. Whichever way a complex number is stored, we would like<br>to be able to query it for all of these four quantities:
The real coordinate in the rectangular form of the complex number.
The imaginary coordinate in the rectangular form.
The magnitude in the polar form.
The angle in the polar form.
Last time we implemented these on top of a tagged value. To return one of the<br>four coordinates above, a function would introspect the tag to figure out how to<br>satisfy the caller for the representation involved. This works, but any time we<br>want to add a new representation, we have to change all four existing<br>operations.
To get around that problem, Abelson and Sussman suggest a data-directed approach<br>instead. We won’t start at the lowest level of Lisp like in the previous<br>article, but jump in around halfway, when we are using compiler-recognised<br>tuples and strings for tagging our types. That means we are starting from this code:
In[1]:<br>attach_tag tag contents = (tag, contents)<br>type_tag (tag, _) = tag<br>contents (_, value) = value
is_rectangular z = type_tag z == "rectangular"<br>is_polar z = type_tag z == "polar"
make_rectangular re im = (attach_tag "rectangular" (re, im))<br>make_polar r a = (attach_tag "polar" (r, a))
In the book, the authors use two magical functions get and put to store and<br>retrieve operations from an implicitly declared table of operations. Here’s what<br>those two functions look like in our Haskell code:
In[2]:<br>put op tag fn =<br>State.modify (Map.insert (op, tag) fn)
get op tag =<br>State.gets (Map.lookup (op, tag))
We will use them to install operations for the rectangular representation, just<br>like in the Lisp code in sicp.
In[3]:<br>install_rectangular =<br>let<br>real_part (re, _) = re<br>imag_part (_, im) = im<br>magnitude (re, im) = sqrt (re^2 + im^2)<br>angle (re, im) = atan2 im re<br>in do<br>put "real_part" "rectangular" real_part<br>put "imag_part" "rectangular" imag_part<br>put "magnitude" "rectangular" magnitude<br>put "angle" "rectangular" angle
We do the same for the polar representation.
In[4]:<br>install_polar =<br>let<br>real_part (r, a) = r * cos a<br>imag_part (r, a) = r * sin a<br>magnitude (r, _) = r<br>angle (_, a) = a<br>in do<br>put "real_part" "polar" real_part<br>put "imag_part" "polar" imag_part<br>put "magnitude" "polar" magnitude<br>put "angle" "polar" angle
We re-implement the apply_generic function from sicp to pick the right<br>operation from this table.
In[5]:<br>apply_generic op arg = do<br>value get op (type_tag arg)<br>pure $ case value of<br>Just fn -> fn (contents arg)<br>Nothing -> error "No method for these types."
This operation can be used to implement the generic coordinate extraction functions.
In[6]:<br>real_part z = apply_generic "real_part" z<br>imag_part z = apply_generic "imag_part" z<br>magnitude z = apply_generic "magnitude" z<br>angle z = apply_generic "angle" z
Then, because we are writing this in Haskell, the complex number arithmetic is<br>going to look a little clumsy. Don’t worry, we’ll fix that soon.
In[7]:<br>add_complex za zb = do<br>za_re real_part za<br>za_im imag_part za<br>zb_re real_part zb<br>zb_im imag_part zb<br>pure $ make_rectangular (za_re + zb_re) (za_im + zb_im)
mul_complex za zb = do<br>za_r magnitude za<br>za_a angle za<br>zb_r magnitude zb<br>zb_a angle zb<br>pure $ make_polar (za_r * zb_r) (za_a + zb_a)
To run a computation with this, we have to run it as a stateful computation,<br>where we first install the operations, and then perform the computations. It<br>might look like this.
In[8]:<br>main = flip State.evalStateT Map.empty $ do<br>install_rectangular<br>install_polar<br>zc add_complex (make_polar 4 0.3) (make_rectangular 3 2)<br>s show_complex zc<br>liftIO (putStrLn s)
Great! We can do what Lisp can do.
Moving to pure tables
Although it might seem like a step backwards, we will move away from the<br>implicit operation table, and instead specify it explicitly. Instead of having<br>installation functions that mutate a table of operations, each installation<br>function will return the part of the table they are responsible for.
In[9]:<br>rectangular =<br>let<br>real_part (re, _) = re<br>imag_part (_, im) = im<br>magnitude (re, im) = sqrt (re^2 + im^2)<br>angle (re, im) = atan2 im re<br>in<br>Map.fromList<br>[ (("real_part", "rectangular"), real_part)<br>, (("imag_part", "rectangular"),...