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.