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:
- Configuration files - code changes its behavior based on data
- Our get/put table - looking up code by operation and data type
- Scheme-1 - the ultimate in DDP; it doesn't do anything on its own, but can do everything
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:
- A student in Ingrid's section is tagged with the word
ingrid
, and is represented by a list containing their first name, last name, and login. - A student in Aditi's section is tagged with the word
aditi
, and is represented by a pair whose car is the login and whose cdr is another pair. That pair's car is their first name and the cdr is their last name. - A student in Darren's section is tagged with the word
darren
, and is represented by a list containing their login, their group number, their first name, and their last name. - A student in Chris's section is tagged with the word
chris
and is represented by a sentence of the wordawesome
, the student's first and last names, and their login.
-
Pick two of these representations and write selectors for the data, then show how you would put them into the get/put table for later use. (Remember that
operate
will strip off the type-tag for you.)(put 'ingrid 'first-name car) (put 'ingrid 'last-name cadr) (put 'ingrid 'login caddr) (put 'aditi 'first-name cadr) (put 'aditi 'last-name cddr) (put 'aditi 'login car) (put 'darren 'first-name caddr) (put 'darren 'last-name cadddr) (put 'darren 'login car) (put 'chris 'first-name (lambda (student) (first (bf student)))) (put 'chris 'last-name (lambda (student) (first (bf (bf student))))) (put 'chris 'login last)
-
Brian needs a list of all student logins in the class. Write a procedure that takes a mixed list of tagged students and returns a list of all of their login IDs.
The list you're given looks something like this:
+---+---+ +---+---+ +---+---+ +---+---+ --->| | | --------->| | | -------->| | | --------->| | | ------> ... +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ v v v v +--------+ +-------+ +--------+ +-------+ | Ingrid | | Aditi | | Darren | | Chris | | [....] | | [...] | | [...] | | [...] | +--------+ +-------+ +--------+ +-------+
So the procedure we want is gonna be something like this:
(define (ids students) (map (lambda (tagged-student) (operate 'login tagged-student)) students))
-
Eric wants to standardize on Ingrid's format because it's simple. Write a procedure that takes a mixed list of tagged students and converts them all to Ingrid's format. (You'll need to write a constructor for Ingrid's format first!)
(define (make-ingrid-student login first-name last-name) (attach-tag 'ingrid (list first-name last-name login)) ) (define (convert-to-ingrid students) (map (lambda (tagged-student) (make-ingrid-student (operate 'login tagged-student) (operate 'first-name tagged-student) (operate 'last-name tagged-student) )) students))
This is worth discussion! Following the convention set in lecture, we make sure the constructor for Ingrid-students tags the data too. SICP takes another route, by putting the constructors in the table and tagging the result whenever they are used. The former way ensures that data is never left without a tag, but the latter would allow you to have data without a tag, which could be useful when working beneath the abstraction barrier. Just make sure you're consistent!
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!
-
Jordy's been really busy and hasn't had time to finish his student records! Write a message-passing implementation for him that keeps track of logins, first names, and last names.
(define (make-jordy-student login first-name last-name) (lambda (message) (cond ((eq? message 'login) login) ((eq? message 'first-name) first-name) ((eq? message 'last-name) last-name) (else (error "Bad message " message)) )))
If we want, we can go ahead and add operations to the
get
/put
table for Jordy-students as well. Message-passing implementations can cooperate with other implementations, as long as they're tagged!(put 'jordy 'first-name (lambda (student) (student 'first-name))) (put 'jordy 'last-name (lambda (student) (student 'last-name))) (put 'jordy 'login (lambda (student) (student 'login)))
Back to Jordy's home page | Course home page