Yesterday we beefed up procedures, giving them persistent memory (internal state) and the ability to have their own specially assigned internal procedures. Using lambda and let we can mix and match procedures and internal state. We can define a group of procedures that share state so that any of the procedures can refer to (read) or modify (write) their shared locations in memory but no procedures outside the group can read or write to these locations.

An object in object-oriented programming sometimes behaves like memory and sometimes behaves like a procedure or, rather, like a whole passel of procedures. Imagine a procedure called make_room that takes two arguments, integers corresponding to the width and length of a room in inches, and returns a "room object".

> (define annes_living_room (make_room 100 200))

We could ask annes_living_room to tell us its width or compute its area.

> (annes_living_room "width")
100
> (annes_living_room "area")
20000

It might even be smart enough to make metric conversions.

> (annes_living_room "area" "meters")
12.9032

We could change the dimensions of the room, read or write the width and length in any units, ask annes_living_room to, say, display itself as a rectangle in a graphical interface or alter the way in which it's displayed, say, by rotating the rectangle a specified angle in a specified direction about its centroid. We could combine annes_living_room object with, say, annes_kitchen object to create a composite object with associated composite information and compositing procedures. In general, annes_living_room would be a single source for information about Anne's living room and procedures for doing things with and to this information.

The above syntax is pretty clunky but it's just syntax and the syntax for object oriented languages like C++ and Java will appear pretty clunky the first time you encounter it. For instance, in Java, we might create a new room and assign it to the variable annes_living_room with the following incantation:

annes_living_room Room = new Room (width.100,length.200) ;

Refer to the width of this room in a program as:

annes_living_room.width

Refer to (compute in this case) the area of annes_living_room as:

annes_living_room.area 

Refer to the area in alternative units of measure as:

annes_living_room.area("meters")

And perhaps request that annes_living_room "rotate itself" 180 degrees in a counter clockwise direction (- Pi radians) and then "draw itself" at coordinates 500 by 500 in some (unspecified) graphics window as:

annesLivingRoom.rotate(- Pi) ;
annesLivingRoom.draw(500, 500) ;

The syntax doesn't really matter that much (unless, of course, you're struggling to write a program in a particular language with a tricky or unnatural syntax). What matters is that objects have (mutable) state and can perform all sorts of useful computations; you tend to stop thinking of them as data or procedures and start thinking of them as a repository for a particular sort of knowledge or expertise. Some programmers like to think of objects as entities that you can send messages to requesting them to provide services. Objects often refer to other objects and may even have a set of objects exclusively cached away in their internals.

It's a very powerful way of thinking about programs and, as I mentioned yesterday, it provides the basis for an engineering discipline that supports the design and development of very large programs consisting of millions of lines of code.

There's another aspect of object-oriented programming that I'll mention in passing as it is often touted as one of the principal useful characteristics of this model of computation. In Java and C++, programs are organized in terms of classes. A class is like a library in that it provides a particular set of capabilities. But the important thing about a class, apart from allowing you to generate instances of that class and thereby directly take advantage of the class's capabilities, is that you can extend the class by adding new capabilities or altering existing ones.

Imagine that we have a class called Rectangle that has a width and length and supports being drawn in a graphics window, rotated, resized and, perhaps, labeled, shaded and painted different colors. Now it probably took someone a lot of effort to create this class and it doesn't make sense for me to repeat this work and perhaps not even do as good a job. But I want to create a Room class that computes its area and performs various conversions and performs other functions that are particular to the needs of my program.

In Java, C++, C#, Smalltalk or any number of other object-oriented programming language, I would define the Room class to be a subclass of the Rectangle class and inherit most if not all of the capabilities of the Rectangle class. An instance of the Room class such as annes_living_room would behave like a Rectangle except in cases where I've explicitly overridden a Rectangle capability. So I'll be able to draw and rotate a Room without ever having explicitly written any code to perform these operations.

This is great if you're smart or lazy or both. Before you write a program to do anything, you typically check to see if there is class that does most of what you want to do and then you simply adapt it for your particular purposes by defining a new class that inherits what you want from the original class. Really well-written classes become widely used and widely available and programmers end up being much more efficient by reusing other programmer's code (see the August 24, 2002 entry for more about object-oriented programming).

You don't need to use an object-oriented programming language to program in an object-oriented style or take advantage of the ability of object-oriented programming languages to structure large programs. My initial exposure to object-oriented programming came soon after I started programming in Lisp, first in a dialect called T and then later in a dialect called Zeta both of which had object-oriented extensions. I found the object-oriented viewpoint more useful for understanding existing programs than for structuring my own.

When I discovered how to implement objects in Lisp, the big eye opener for me was the fact that I could invent my own languages and create my own syntax to suit the problem at hand or my own idiosyncratic perspectives on computing. I loved to create my own Lisp-implemented variants of object-oriented programming languages. Conversely, programming in Smalltalk, an early object-oriented programming language, changed the way I thought about writing programs in Lisp. One of Alan Perlis's Epigrams in Programming (number 19) reads "A language that doesn't affect the way you think about programming, is not worth knowing" and I've certainly only persisted in using and learning languages that provided such an added benefit.

Often in the process of solving a particular problem you end up inventing a highly specialized programming language. In some cases, that specialized language is subsequently generalized to solve a wider range of problems. I'll give you an example. Let's consider an alternative algebra problem from the one that started us off in describing the substitution model.

The living room in Anne's house is 28 square meters. She wants to buy a rug that fits exactly in the room. Along one side of the room there is a large fireplace that is 3 meters wide flanked by two identical bookcases which together take up the entire width of the room. The bookcases are 2 meters wide each. What are dimensions of the rug that Anne should buy?

Again we note the known and unknown quantities.

living_room_area = 28

bookcase_width = 2

fireplace_width = 3

living_room_width = fireplace_width + (2 * bookcase_width) 

We have the same general relationship as before,

living_room_area = living_room_length * living_room_width 

but it isn't quite what we need and so we do a little algebra to isolate the unknown variables on one side of the equation.

living_room_length = living_room_area / living_room_width

Substitute the appropriate formula for items that have to be computed.

living_room_length = living_room_area / (fireplace_width + (2 * bookcase_width))

And then perform the necessary calculations by plugging in the numbers and substituting the results back into the formula.

living_room_length = living_room_area / (fireplace_width + (2 * 2)) 

living_room_length = living_room_area / (fireplace_width + 4) 

living_room_length = living_room_area / (3 + 4) 

living_room_length = living_room_area / 7

living_room_length = 28 / 7

living_room_length = 4

This is all fine and well but we can't use the same functions that we defined in Scheme a couple of days ago. Why? Because they only handle one particular case. Given an equation such as the following

living_room_area = living_room_length * living_room_width 

and provided with values for any two of the terms, we can compute the third. Why couldn't we simply provide this equation and have the computer figure out how to supply the missing value when two other values are supplied. A similar question occurred to Ivan Sutherland back in the early 60s when he was implementing Sketchpad, a system that anticipated a bunch of technologies we take for granted today including graphical interfaces and an object-oriented style of programming. Sutherland was interested in displaying graphical objects and he wanted to specify general constraints (equations) governing the position and orientation of these objects and have the computer figure out the consequences of those constraints in drawing the objects on the computer screen. For example, at one point you might say that two rectangles should be drawn so that one is above the other, and later you might add that the bottom of one should be aligned with the top of the other and both enclosed in a third rectangle. If the computer is asked to display these three rectangles, it would be expected to do in such a way that it satisfies all of these constraints.

Later (1977) Alan Borning used the Smalltalk language to develop an elegant design environment based in part on Sutherland's ideas that was used to develop computer simulations [ThingLab: A Constraint-oriented Simulation Laboratory, Technical Report SSL-79-3, Xerox Palo Alto Research Center, 1979]. And still later Abelson and Sussman created a "constraint-oriented" language in Scheme with kudus to both Sutherland and Borning and used it in SICP to illustrate an alternative model of computation.

By the way, the full text of SICP (also called the Wizard book) is available from the MIT Press SICP web site. I really like holding and leafing through well-made books and my copy of SICP in particular, so I suggest you buy a copy from MIT Press (thereby positively reinforcing both the authors and the publishers for producing such interesting books and making them available free on line). But as much as I like my physical copy, I have to say that it's very convenient having an on-line searchable version with all of the code in the book available for download. The SICP site also pointers on how to obtain various implementations of Scheme including DrScheme.

I grabbed all of the code from Chapter 3 on the SICP site, copied the relevant parts into a file called constraints.scm, and then loaded it into DrScheme as follows.

> (load "constraints.scm")

Next I created objects for each of the terms in the following equation, specified that the terms are related to one another through multiplication, and indicated that the cost per square meter will be a particular constant value. The terms in the equation become connector objects that will serve to connect together different constraints. The constraints for this application, called multipliers and adders for obvious reasons, are created and attached to the appropriate connectors.

total_cost = cost_per_square_meter * living_room_area

> (define total_cost (make-connector))
> (define cost_per_square_meter (make-connector))
> (define living_room_area (make-connector))
> (multiplier cost_per_square_meter 
              living_room_area 
              total_cost)
> (constant 5 cost_per_square_meter)

What would you guess that a multiplier constraint does? Think about a multiplier (or adder for that matter) as follows. Suppose that the living_room_area connector suddenly wakes up and realizes it knows it's "value". Well, that might be important information to send along to the multiplier created by the above incantation; so living_room_area wakes up the multiplier and says, "Hey! Here's some new information, check it out and see if you can do anything with it." Perhaps the multiplier checks and finds out that neither the cost_per_square_meter nor the total_cost connectors have values, therefore it can't do anything with the information so it goes back to sleep. Alternatively, perhaps the multiplier checks and cost_per_square_meter has a value (as indicated above) but total_cost currently doesn't; so the multiplier figures out what the value of total_cost should be, tells the total_cost object to wake up and see if anyone else cares about this newly determined value. Note that the multiplier doesn't have to be too smart; just smart enough to handle these three special cases:

If cost_per_square_meter and living_room_area have values, then set

total_cost = cost_per_square_meter * living_room_area.

If cost_per_square_meter and total_cost have values, then set

living_room_area = total_cost / cost_per_square_meter.

Finally, if living_room_area and total_cost have values, then set

cost_per_square_meter = total_cost / living_room_area 

Now we'll do something very similar with the next equation.

> (define living_room_width (make-connector))
> (define living_room_length (make-connector))
> (multiplier living_room_width 
              living_room_length
              living_room_area)
> (constant 4 living_room_length)

And again

living_room_width = fireplace_width + total_bookcase_width

> (define fireplace_width (make-connector))
> (define total_bookcase_width (make-connector))
> (adder fireplace_width 
         total_bookcase_width
         living_room_width)
> (constant 3 fireplace_width)

And finally

total_bookcase_width = number_of_bookcases * bookcase_width

> (define number_of_bookcases (make-connector))
> (define bookcase_width (make-connector))
> (multiplier number_of_bookcases
              bookcase_width
              total_bookcase_width)
> (constant 2 number_of_bookcases)

All of the constraints are related to the other constraints they depend on through the connectors. Abelson and Sussman provide the abstraction of a probe that you can attach to a connector as though attaching an oscilloscope or voltmeter probe to a wire in a circuit. The probe then reads off the value of the connector whenever it changes. We'll put a probe on two of the connectors.

> (probe "bookcase width" bookcase_width)
Probe: bookcase width = ?
> (probe "total cost" total_cost)
Probe: total cost = ?

The reply from the interpreter indicates that currently the constraint system has no values for these terms. So let's set one of them. Let's try the easy case first corresponding to the case handled by our simple functional solution that we implemented the other day.

> (set-value! bookcase_width 2 'user)
Probe: bookcase width = 2
Probe: total cost = 140
done

Works as expected. Let's undo that last operation and then set the total cost to see if the constraint system can work backwards as it were.

> (forget-value! bookcase_width 'user)
Probe: bookcase width = ?
Probe: total cost = ?
done

Looks like the values have returned to being unknown. So lets set total_cost to be 140 and let the values propagate backwards through the constraints.

> (set-value! total_cost 140 'user)
Probe: total cost = 140
Probe: bookcase width = 2
done
> 

That's the answer we were looking for; the constraint solver will calculate the right values as long as there is enough information to do so. By the way, why do you think that the probes responded in a different order this time? The order of computation is determined in all cases by the topology of the connections and constraints.

This really cries out for a diagram or graphic which I've resisted introducing so far in this journal. I want this journal to be casual and, to my sensibility, CAD (computer aided design) drawings with perfect little boxes and arrows and text seem a little too anal (as in overly fussy, compulsive or, borrowing from Freud, anal retentive). I do, however, like drawing diagrams on the white board with colorful magic markers and so I thought I'd try to simulate this by using a graphics tablet and a program for manipulating bit mapped images. If this works, then I'll use it as my preferred method for inserting diagrams and drawings into my journal entries.

I'm going to use a tablet that combines a pressure-sensitive pad and pen technology with a liquid crystal display (LCD), so that it will seem that I'm drawing directly on the screen. This technology has been around for awhile now and so most of you will have seen it in some form or another, e.g., credit card authorization at grocery stores or signing for packages, but I can't help wondering what Ivan Sutherland would have thought if he could have seen my tablet back in 1963 as he worked on his Ph.D. thesis at MIT. I bet it would have seemed a logical extension of his work on Sketchpad.

I expect that it might be tricky to write legibly and at the same time small enough to create a suitably compact image so I'll begin by establishing some abbreviations to use in the drawing:

total_cost = TC
living_room_area = LR-Area
cost_per_square_meter = Cost/M2
living_room_width = LR-Width
living_room_length = LR-Length
fireplace_width = FP-Width
total_bookcase_width = TBC-Width
number_of_bookcases = #-BC
bookcase_width = BC-Width

Took me about an hour with several false starts. I didn't worry about the colors too much but it did take me a while before I was satisfied with my pen strokes. Even so, the lines look a little jagged and wobbly; I expect my drawings on the white board would appear similarly jagged if I ever took the time to examine them closely.

I created a single image with four layers. On the first layer, I drew the basic diagram with a box for each multiplier and adder and a wire (line) for each connector using the convention in SICP. On the second layer, I used a red pen to set the constants to their values. The third layer shows the propagation resulting from setting the total_cost (TC) to be 140 the and the fourth later shows the propagation resulting from setting the book_case width (BC-Width) to be 2. I then created three images.

In the first image, I turned on only layers one and two:

In the second, I turned on layers one, two and three to illustrate the propagation forward from TC:

And in the third, I turned on layers one, two and four to illustrate the propagation backward from TC:

This illustrates another model of computation, based on the propagation of constraints in this case and inspired or at least facilitated in part by thinking in terms of object-oriented programming. That's more than enough for today; my back feels way over constrained and the pain is propagating up to my neck and shoulders. I need a swim and bicycle ride.