SICP describes two ways by which we can call the functions associated with the given data: Dispatch by type, and Message passing.

These are just the ways (as is almost everything else in the book) of creating a new layer of abstraction on the top of what we already have. The use cases are different, but the end result is the same: call the methods associated with the data.

Dispatch by type is used in data-driven programming where the incoming data contains the necessary information of handling it. In this approach, we have a generic operation which needs to be applied to a given type. The type itself may be a generic type at a very high level of abstraction, but the data contains enough information to direct the operation to the necessary subtype. Therefore, this is a mapping from operation to type.

For example, given an operation like Add and a generic type like Number (which can be Real or Complex – the latter being an abstraction on two integral/real numbers), the flow of dispatching by type will go to Number, then to either Real or Complex, and if the number is Complex, then to it’s individual parts.

In the book, this is done by tagging the data based on type. The upper layers of abstraction are used for bookkeeping and redirection, and the lower levels do the real work of handling data. As data moves from top to bottom, the tags are checked removed and the data is directed based on the value of tags; which are added again when the data needs to move up.

The other concept is Message Passing wherein we follow a 90° approach. Here we already have the type which provides a set of operations, and we pick the one we need and apply it to the data. Essentially we are sending a message to the data to apply a given operation.

The following code implements a table by using lists and exposing the functions which can work with the table.

We are creating an object in the function create-table and pass back another function dispatch which receives the method name as a string, and returns the unexposed function from the object. This function uses the parameters and do whatever is asked of it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

(define (create-table)
  (define table '())
  (define (new-node k v)
    (cons k v))
  (define (get-key node)
    (car node))
  (define (get-value node)
    (cdr node))
  (define (insert k v)
    (set! table (cons (new-node k v) table)))
  (define (get k) (get-value-from-table k table))
  (define (get-value-from-table k table)
    (cond ((null? table) false)
          ((eq? (get-key (car table)) k)
           (get-value (car table)))
          (else (get-value-from-table k (cdr table)))))
  (define (update-table k v) (update k v table))
  (define (update k v table)
    (cond ((null? table) false)
          ((eq? (get-key (car table)) k)
           (set-car! table (new-node k v))
           true)
          (else (update k v (cdr table)))))
  (define (update-value v node)
    (set-cdr! node v))
  (define (dispatch operation)
    (cond ((eq? operation 'update)
           update-table)
          ((eq? operation 'insert)
           insert)
          ((eq? operation 'show)
           table)
          ((eq? operation 'get)
           get)))
  dispatch)

;; The following four create better abstactions for the table.
(define insert (lambda (table k v) ((table 'insert) k v)))
(define update (lambda (table k v) ((table 'update) k v)))
(define get (lambda (table k) ((table 'get) k)))
(define show  (lambda (table) (table 'show)))

Now using this code, we are going to implement both type-dispatch, and message passing. The following table helps in visualizing the connections between types (polar/rectangular) and functions (real-part, imag-part).

polar rectangular
real-part # #
imaginary-part # #

Type Dispatch

This means that we will have an operation which will be applied to the given type, e.g. We are given real-part which needs to be applied to polar. In some pseudo language (Haskellish), this will be the syntax of the operation:

1
2
3
4
5

real-part (Polar x y) = x * cos y
imag-part (Polar x y) = x * sin y

real-part (Rect x y) = x
imag-part (Rect x y) = y

Given the structure of the table above, we will have the data structured in the table like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

(define real-part (create-table))
;; In polar, representation: (2,4) = 2 + 4j
;; In rectangular, representation: (2,4) => 2 is the radius, 4 is the angle
(insert real-part 'polar (lambda (z) (car z)))
(insert real-part 'rectangular  (lambda (z) (* (car z) (cos (cdr z)))))

(define imag-part (create-table))
(insert imag-part 'polar (lambda (z) (cdr z)))
(insert imag-part 'rectangular  (lambda (z) (* (car z) (sin (cdr z)))))

(define op-table (create-table))
(insert op-table 'real-part real-part)
(insert op-table 'imag-part imag-part)

-- usage:
> ((get-op op-table 'real-part 'polar) (cons 3 5))
3
> ((get-op op-table 'real-part 'rectangular) (cons 3 5))
0.850986556389678

On the other hand, we have the message passing scheme, wherein we have the data first, and the operation. It is up to the data to correctly apply the operation and return the result. With respect to the table, we are moving from top to bottom: polar.real-part , polar.imag-part , rect.real-part, etc.

The implementation in scheme is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(define polar (create-table))
;; In polar representation: (2,4) = 2 + 4j
(insert polar 'real-part (lambda (z) (car z)))
(insert polar 'imag-part (lambda (z) (cdr z)))

(define rectangular (create-table))
;; In rectangular representation: (2,4) = (r, theta)
(insert rectangular 'magnitude (lambda (z) (car z)))
(insert rectangular 'angle (lambda (z) (cdr z)))

(define function-table (create-table))
(insert function-table 'polar polar)
(insert function-table 'rectangular rectangular)

Interestingly, the table itself implements the message-passing style since:

  • Each table is a different object having its own copies of these methods (which should be shared when the code is running)
  • We are passing each object the name of the operation to run.