Data-Directed Programming

What is data-directed programming? Basically, it's a different way of organizing your code. Instead of using big cond expressions to handle all different behavior, you treat the code itself as data, and use that data to drive your program. Examples:

Our primary exposure to DDP in 61A is by using tagged data and generic operations to organize our code. When we want to perform an operation, we look up the implementation in a table (the "get/put table") to find the version of the operation appropriate for the type.

There are three parts to this system. First, we need an abstraction for "tagged data", with constructor attach-tag and selectors type-tag and contents. SICP chooses to implement these with cons, car, and cdr, respectively.

Next, we need a two-dimensional table (one where you can look things up by type and operation). We'll learn how these tables are constructed in Chapter 3, but for now we'll use one that comes with our CS61A library. Accessing this table is done through a pair of procedures called put and get.

> (put 'square 'perimeter (lambda (side) (* 4 side)))
okay
> (get 'square 'perimeter)
#[closure args=(side) 61a61a]
> ((get 'square 'perimeter) 5)
20
> (get 'triangle 'perimeter)  ; not in table
#f

We could just use this, but often we define a convenient procedure for using generic operators called operate. This isn't in the library, but it's pretty easy to put in yourself. (It's also in the lecture notes.)

(define (operate op arg)
  (let ((fn (get (type-tag arg) op)))
    (if fn
        (fn (contents arg))
        (error "Bad operation " op " for data " arg) )))

SICP has its own version of operate called apply-generic. The difference is apply-generic can handle any number of arguments, not just one, and it uses lists of types in the get/put table to take that into account.

Example: Student Records

Every TA likes to keep their records differently, which causes huge headaches for Brian! Fortunately, each of them uses tagged data to store their student records:

Message Passing

Message passing is yet another major way of organizing code: by attaching it to your data. You can then send your data messages that tell it what operation to perform. We implement this by representing our data with procedures, whose argument is the message.

Message passing is an important piece of object-oriented programming, which we'll be exploring in full next week!

Back to Jordy's home page | Course home page