I recently took Dave Beazley’s week-long course on The Structure and Interpretation of Computer Programs. In this series, I’ll share memorable insights from the course (here’s where you can see all the posts so far).
In this post, we’ll look at some more data representation questions from the second chapter of the book. This set of questions happens to dovetail nicely with some of the material from Crafting Interpreters, so I’ll include some of that here, too.
Let’s talk about programming paradigms and how they affect the way our code bases can change.
Suppose we have two different implementations of a box class.
Bob’s box implementation relies on storing the lower left point, width, and height.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #lang racket | |
| (define (make-bob-box x y w h) | |
| 'bob-box (cons (cons x y) (cons w h))) | |
| (define (bob-width box) | |
| (car (cdr (box)))) | |
| (define (bob-height box) | |
| (cdr (cdr (box)))) | |
| (define b (make-bob-box 1 2 3 4)) | |
| (define (bob-area box) | |
| (* (bob-width box) (bob-height box))) | |
| (define b (make-bob-box 1 2 3 4)) | |
| (bob-area b) ;–> 12 |
Alice’s box implementation relies on storing the locations of opposite corners of the box.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #lang racket | |
| (define (make-alice-box x1 y1 x2 y2) | |
| (cons (cons x1 y1) (cons x2 y2))) | |
| (define (alice-width box) | |
| (abs (– (car (cdr (box)) | |
| (car (car (box))))) | |
| (define (alice-height box) | |
| (abs (– (cdr (cdr (box)) | |
| (cdr (car (box))))) | |
| (define (alice-area box) | |
| (* (alice-width box) | |
| (alice-height box))) | |
| (define a (make-alice-box 1 2 3 4)) | |
| (alice-area a) ;–> 4 |
What happens when we want to allow both of these data representations to work within the same program?
Option 1: Add a type tag to each box
We can attach a specific label to each type of box as a tag, then create methods that switch between the implementations of each type of box after checking that tag. Like this:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #lang racket | |
| (define (attach-tag tag item) | |
| (cons tag item)) | |
| (define (contents tagged-item) | |
| (cdr tagged-item)) | |
| … | |
| (define (bob-width box) | |
| (car (cdr (contents box)))) | |
| (define (bob-height box) | |
| (cdr (cdr (contents box)))) | |
| … | |
| (define (alice-width box) | |
| (abs (– (car (cdr (contents box))) | |
| (car (car (contents box)))))) | |
| (define (alice-height box) | |
| (abs (– (cdr (cdr (contents box))) | |
| (cdr (car (contents box)))))) | |
| … | |
| (define (bob-box? box) | |
| (if (= (car box) 'bob-box) true false)) | |
| (define (alice-box? box) | |
| (if (= (car box) 'alice-box) true false)) | |
| (define (width box) | |
| (cond ((bob-box? box) (bob-width box)) | |
| ((alice-box? box) (alice-width box)))) |
Each time we add a new type of box to our program, we would need to add a case to each method that does this type check.
Option 2: Encapsulate tagged operations within each box
In this case, we have each box, upon creation, call a procedure that accepts a type argument, with type now referring to the operation to be run rather than the type of the box.
As Dave Beazley observes, this produces a syntax similar to the object dot method syntax:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (define (make-bob-box x y width height) | |
| (define (dispatch message) | |
| (cond ((eq? message 'width) width) | |
| ((eq? message 'height) height) | |
| ((eq? message 'type) 'bob-box) | |
| (else (error "Bad method")))) | |
| dispatch) | |
| (define (make-alice-box x1 y1 x2 y2) | |
| (define (dispatch message) | |
| (cond ((eq? message 'width) (abs(– x2 x1))) | |
| ((eq? message 'height) (abs(– y2 y1))) | |
| ((eq? message 'type) 'alice-box) | |
| (else (error "Bad method")))) | |
| dispatch) | |
| (define a (make-alice-box 1 2 3 4)) | |
| (define b (make-bob-box 1 2 3 4)) | |
| (b 'width) ;—> 3 |
Each time we add a new type of operation to our program, we would need to add a case to each box type to execute a message of that name.
See how in both options, we have to go back and change something in the existing code? This has a name: the expression problem.
For this, I appreciate Bob Nystrom’s explanation apropos of a discussion about representing expression types in an object-oriented language. I’m shamelessly pasting the relevant part here for your convenience (sorry, Bob):
For each pair of type and operation, we need a specific implementation. Picture a table:
Rows are types, and columns are operations. Each cell represents the implementation of that operation for that type.
An object-oriented language like Java assumes that all of the code in one row naturally hangs together. It figures all the things you do with a type are likely related to each other, and the language makes it easy to define them together as methods inside the same class.
This makes it easy to extend the table by adding new rows. Simply define a new class. No existing code has to be touched.
But imagine if you want to add a new operation—a new column. In Java, that means cracking open each of those existing classes and adding a method to it.
Functional paradigm languages in the ML family flip that around. There, you don’t have classes with methods. Types and functions are totally distinct. To implement an operation for a number of different types, you define a single function. In the body of that you use pattern matching—sort of a type-based switch on steroids—to implement the operation for each type all in one place.
This makes it trivial to add new operations—simply define another function that pattern matches on all of the types.
But, conversely, adding a new type is hard. You have to go back and add a new case to all of the pattern matches in all of the existing functions.
Each style has a certain “grain” to it. That’s what the paradigm literally means—an object-oriented language wants you to orient your code along the rows of types. A functional language instead encourages you to lump each column’s worth of code together into functions.
This “grain” thing is interesting because it offers us a context-specific attribute with which to judge whether a particular problem might benefit most from an object-oriented solution or a functionally-oriented solution. But what if we need to be able to add rows and columns? Can we make that easier within either of the paradigms?
We can.
Option 3: Dispatch functions through a table, or registry.
This time we’re going to tag each of our box types the way we did in Option 1, and we’ll then register the type-specific method calls in a table whose keys are lists containing the general operation names (like width) plus the tag for the type of box. These keys point to a reference to the type-specific operation to be performed on a box of that type when the general operation name is called.2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #lang racket | |
| (define (register h method tag function) | |
| (hash-set! h (list tag method) function)) | |
| (define (lookup h key) | |
| (hash-ref h key)) | |
| (define h (make-hash)) | |
| (register h 'alice-box 'width alice-width) | |
| (register h 'bob-box 'width bob-width) | |
| (define (width box) | |
| ((lookup h (list 'width (car box))) box)) | |
| (define (height box) | |
| ((lookup h (list 'height (car box))) box)) | |
| (define b (make-bob-box 1 2 3 4)) | |
| (width b) ;–> 3 |
The width and height functions now look up a key containing their name, plus the type tag of the object they’ve been called on, in the hash. So we don’t have to add new cases to those general functions each time we add a new type of box.
This pattern makes it a little easier for us to add new types of objects in functionally-oriented code.
But what if we have object-oriented code?
Option 4: The Visitor Pattern
We didn’t implement this in class. I started to implement this in Scheme at home to show you in a consistent language, but the visitor pattern in Scheme ends up looking enough like Option 1 that it could be confusing as a demonstration. The visitor pattern benefits heavily from the presence of interfaces, which Scheme doesn’t have. So instead I’m going to show this one in Java.
Here’s the setup:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| interface BoxVisitor { | |
| int visitBob(BobBox box); | |
| int visitAlice(AliceBox box); | |
| } | |
| … | |
| abstract class Box { | |
| abstract void accept(BoxVisitor visitor); | |
| } | |
| class BobBox extends Box { | |
| private int x1; | |
| private int y1; | |
| private int width; | |
| private int height; | |
| public BobBox(int x1, int width, int y1, int height) { | |
| this.x1 = x1; | |
| this.y1 = y1; | |
| this.width = width; | |
| this.height = height; | |
| } | |
| @Override | |
| void accept(BoxVisitor visitor) { | |
| visitor.visitBob(this); | |
| } | |
| } | |
| class AliceBox extends Box { | |
| private int x1; | |
| private int x2; | |
| private int y1; | |
| private int y2; | |
| public AliceBox(int x1, int x2, int y1, int y2) { | |
| this.x1 = x1; | |
| this.x2 = x2; | |
| this.y1 = y1; | |
| this.y2 = y2; | |
| } | |
| @Override | |
| void accept(BoxVisitor visitor) { | |
| visitor.visitAlice(this); | |
| } | |
| } |
We have an interface that requires implementers to have a method for each of our two class types. We then create a method on each box that accepts a class implementing that interface and calls its the implementer’s dedicated method for this type of class on itself.
Then, all of the behaviors live together in a class that implements the interface:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class WidthVisitor implements BoxVisitor { | |
| int visitBob(BobBox box) { | |
| return box.getWidth(); | |
| } | |
| int visitAlice(AliceBox box) { | |
| return Math.abs(box.getX2() – box.getX1()); | |
| } | |
| } | |
| class HeightVisitor implements BoxVisitor { | |
| int visitBob(BobBox box) { | |
| return box.getHeight(); | |
| } | |
| int visitAlice(AliceBox box) { | |
| return Math.abs(box.getY2() – box.getY1()); | |
| } | |
| } |
We still have to provide an implementation of the method for each type, but we can keep the behavior together rather than scatter it across all of those types’ classes.
Conclusion
None of these strategies produces a code base for which it is equally convenient to add both classes and behaviors (though Options 3 and 4 aim to make it easier). Understanding the tradeoffs for each of these strategies allows us to choose a paradigm based on our expectations for how the code base is likely to change in the future.
In the next post, we’ll move into Chapter 3 of SICP: Modularity, objects, and state.
2So we have keys that are lists of the general operation name and the specific box type tag. We can do that because we are representing all this in code…for now. Were we doing this with a SQL database, we’re not allowed to use a list as a key. This exemplifies how some of that key concatenation we talked about in the last post might come in handy.
If you liked this piece, you might also like:
The Crafting Interpreters series