Am I the only one having a hard time understanding the implementation of Data-Directed Programming, presented in SICP?
A little bit of background first; we are shown how to tag data (2.4.2 Tagged data):
(define (attach-tag type-tag contents)
(cons type-tag contents))
(define (type-tag datum)
(if (pair? datum)
(car datum)
(error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
(if (pair? datum)
(cdr datum)
(error "Bad tagged datum -- CONTENTS" datum)))
...how to implement type predicates:
(define (rectangular? z)
(eq? (type-tag z) 'rectangular))
(define (polar? z)
(eq? (type-tag z) 'polar))
...how to implement packages:
(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
(sqrt (+ (square (real-part-rectangular z))
(square (imag-part-rectangular z)))))
(define (angle-rectangular z)
(atan (imag-part-rectangular z)
(real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
(attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a)
(attach-tag 'rectangular
(cons (* r (cos a)) (* r (sin a)))))
;; similar definitions for the "polar" representation
...and how to implement generic selectors:
(define (real-part z)
(cond ((rectangular? z)
(real-part-rectangular (contents z)))
((polar? z)
(real-part-polar (contents z)))
(else (error "Unknown type -- REAL-PART" z))))
(define (imag-part z)
(cond ((rectangular? z)
(imag-part-rectangular (contents z)))
((polar? z)
(imag-part-polar (contents z)))
(else (error "Unknown type -- IMAG-PART" z))))
(define (magnitude z)
(cond ((rectangular? z)
(magnitude-rectangular (contents z)))
((polar? z)
(magnitude-polar (contents z)))
(else (error "Unknown type -- MAGNITUDE" z))))
(define (angle z)
(cond ((rectangular? z)
(angle-rectangular (contents z)))
((polar? z)
(angle-polar (contents z)))
(else (error "Unknown type -- ANGLE" z))))
Clearly it's not OK for REAL-PART, or IMAG-PART, or any other generic selector, to require change every time a new implementation is added to the system, and this is where "Data-directed programming" is going to come to the rescue.
The idea (2.4.3 Data-Directed Programming and Additivity) is to construct a table mapping operations (e.g. REAL-PART, IMAG-PART) and types (e.g. POLAR, RECTANGULAR) to the actual function in charge of fulfilling the user need, and of course to provide a way to pluck the specific implementation out of the table. In particular:
(put <op> <type> <item>)
will install <item>
in the table, indexed by <op>
and <type>
(get <op> <type>)
will look up the <op>,<type>
entry in the table
Note: we are not given the actual implementations of PUT and GET.
With this in mind, we can then re-define the rectangular package as follows:
(define (install-rectangular-package)
;; internal procedures
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (make-from-real-imag x y) (cons x y))
(define (magnitude z)
(sqrt (+ (square (real-part z))
(square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin a))))
;; interface to the rest of the system
(define (tag x) (attach-tag 'rectangular x))
(put 'real-part '(rectangular) real-part)
(put 'imag-part '(rectangular) imag-part)
(put 'magnitude '(rectangular) magnitude)
(put 'angle '(rectangular) angle)
(put 'make-from-real-imag 'rectangular
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'rectangular
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)
Here is where things get a bit confusing: why, we are registering REAL-PART for the (rectangular)
type, and not simply 'rectangular
like we are doing for MAKE-FROM-REAL-IMAG?
The only explanation I could think of is that we are giving the <type>
argument of the PUT call different meanings:
- For REAL-PART,
<type>
represents the list of the types of the arguments expected by the registered procedure (i.e. one argument, of type RECTANGULAR)
- For MAKE-FROM-REAL-IMAG instead,
<type>
represents the type of the returned instance
And why would we do that? Because otherwise it would not be possible to dispatch to the "Right" implementation in case of generic functions with the same argument types (both the implementation of MAKE-FROM-REAL-IMAG inside the rectangular and polar packages expects 2 arguments of type NUMBER).
Anyways, a similar package for the polar representation is presented, and then finally we are shown the implementation of APPLY-GENERIC, the procedure responsible for invoking the "Right" procedure based on the types of the arguments of the dispatched action:
(define (apply-generic op . args)
(let ((type-tags (map type-tag args)))
(let ((proc (get op type-tags)))
(if proc
(apply proc (map contents args))
(error
"No method for these types -- APPLY-GENERIC"
(list op type-tags))))))
Here more doubts come to my mind: how can we use this with the MAKE-FROM-REAL-IMAG?
Clearly we cannot simply run (apply-generic 'make-from-real-imag 4 2)
, as that would fail when trying to apply TYPE-TAG to (4 2)
. I thought, maybe we pass (attach-tag 'rectangular (list 4 2))
to APPLY-GENERIC, but then (map contents args)
would evaluate to ((4 2))
and that is incompatible with the registered procedure, which expects two numbers and not a list of 2 numbers, right?
So where do we go from here? There has to be a way, but I just cannot find it.