Saturday, February 19, 2011

Another SICP Post

As I read The Structure and Interpretation of Computer Programs, I've been thinking about the stuff I used to do in my Lisp days, and how it compares with the style of a Haskell program.  Most of the differences, directly or indirectly, seem to boil down to static vs. dynamic typing (even more than strict vs. lazy). For example, Lisp has great metaprogramming facilities (macros, "runtime macros" consisting of eval plus manipulation of parse trees).  Haskell has no features that are really like that kind of macro*, and certainly has nothing like the inherently dynamic eval --- but that doesn't mean that it lacks for features that let you do many of things you would do with macros and eval.

But that doesn't mean that Haskell has a nice way to do absolutely everything that you might choose to do in Lisp.  

For instance, let's take a look at data-directed programming.  One of the sections in SICP discusses dynamically building a dispatch table for functions using the following calls:
(put <type> <op> <item>) installs <item> in the table entry indexed by <type> and <op>
(get <type> <op>) looks up the <type>, <op> entry in the table and returns the item found there.  If no item is found, get returns nil
By using these calls we can create polymorphic functions.  The first step is to define function real-part-rect and real-part-polar that will return the real part of a complex number (from rectangular form and polar form, respectively).  The put function defined above is then used to place these into the dispatch table. 
(defun real-part-rect ...
(defun real-part-polar ...
(put 'polar 'real-part real-part-polar)
(put 'rectangular 'real-part real-part-rect)
If we have an object that responds to (type obj) with one of polar or rectangular and responds to (contents obj) with a complex value in either polar or rectangular form, then
(define (operate op obj)
  (let ((proc (get (type obj) op)))
    (if (not (null? proc))
        (proc (contents obj))
        (error "Undefined operator for this type"))))

(define (real-part obj) (operate 'real-part obj))
creates an environment where real-part is a polymorphic function that gets the real part of the complex number.

I think it's pretty easy to see how this could be extended to dispatch on the type of more than one argument -- in other words, to create multi-methods.  In fact, with a trie structure this could be used to dispatch on a variable number of types.   That could be useful in handling default values for function arguments, or in creating a polymorphic lambda.  The latter example points out that the name of the function might well be viewed as just another argument with some syntactic sugar on top. 

This is an example of where Lisp dynamic typing shines, and Haskell's typing restrictions disallow some types of functionality...if there's a way to do this in Haskell, I am unaware of it. 

As an aside, one of the things that has always rubbed me the wrong way about many OO languages is the need to attach every procedure to one and only one data object.  If you want a method to multiply a complex matrix by a complex number, the method naturally belongs at the intersection of two different classes.  Making it belong to one class or the other seems like forcing a square peg into a round hole. 

*To the best of my knowledge.  I'm definitely still learning. 


  1. This is a nice, thought-provoking post that makes me want to try my hand at porting SICP to Haskell.

    After some reflection it seems like the data-directed programming you want is just typeclasses; the difference being Haskell has already implemented operate, so you don't get to, which is a pain in that part of the book. It's been a while since this was posted, so maybe you already know this, or maybe I'm missing the point.

    In any case, you might be interested in the vault package. I've think of it as a heterogeneous map in Haskell (which is just weird if you think about it). Based on that, I've thrown together a bit of Haskell that kinda implements operate anyway:

    1. Interesting implementation, Okuno.

      I think the typeclasses suffice for the 1-dimensional case of classic OO dispatch, but for multi-dispatch on an unknown number of arguments, I'm not seeing how to make that case work. My Haskell is a bit rusty, though, so I'll give it some more thought (and there are a number of newer packages like Vault that I'm not familiar with).

  2. In the example given, would a typeclass with a function for returning the real part of a type not be enough? Then instances could be provided for both polar and rectangular forms.

    1. Tuomas, certainly a typeclass will work for this case, where we are manipulating a function of one argument. Where we are dispatching on a multiple and varying number of arguments, I don't think a typeclass will suffice.

      Now that I've replied to Okuno above, though, maybe I do see a way to do that with Vaults, like he was saying. Need to think on it some more.