Adventures inAdvanced Symbolic Programming (part 1)

Gerry Sussman and Chris Hanson are giving a series of 5 whirlwind lectures on advanced symbolic programming. I'm sitting in and I figure I'll make some comments here (rather than distract from the class). My hope is that the lectures will be available on-line sometime.


The first part of today's lecture was about using generic functions. This was pretty straightforward stuff, but there were a couple of interesting details. First of all, the generic arithmetic was extended to handle functions: (f + g)(x) = f(x) + g(x) Then, with the addition of hyperreals to the numeric tower, it was possible to compute differentials. Finally, by adding symbolic quantities to the numeric tower, you could compute derivatives of functions.

The non-obvious thing to me was that you could compute derivatives symbolically by using symbolic hyperreals, and that you need to compute the differentials using a two-tuple. This is going to sound completely opaque to anyone reading this, so I'd better go into more detail.

Consider a rational number. One way of looking at it is as if it is simply a pair of integers with some weird rules for addition, subtraction, multiplication and division. Now consider a complex number. Again, it is simply a pair of numbers with some weird rules for addition, subtraction, multiplication and division. A hyperreal is the same sort of thing: a pair of numbers with some weird rules for addition, subtraction, multiplication and division.

Now suppose we re-define the primitive +, -, *, and /. We allow them to take symbols as arguments. When given a symbol, we return an s-expression result. Now if we have previously defined rationals as being a pair of numbers with weird rules for addition, subtraction, etc., we can get symbolic rationals automagically by allowing the primitives to take symbolic arguments. (The rules for rational arithmetic being based on the underlying arithmetic primitives.) With a couple of additional rules for constructing rationals from symbols, we're all set for symbolic rational arithmetic.

We can do a similar trick with complex numbers.

And we can do a similar trick with the hyperreals. But here's a more interesting trick: A hyperreal [a, b] has a standard part `a' and an infinitessimal part 'b'. So the symbolic hyperreal [x, 1] means `x + dx'. Now consider the function (lambda (a) (* a a a)), the cube function. If we apply it to the symbolic number x and the symbolic hyperreal [x,1], and subtract the two, f(x + dx) - f(x), and then extract the differential part, we have the derivative. And sure enough, if we evaluate this in the interpreter:

(print-expression ((D (lambda (a) (* a a a))) 'x))
=> (* 3 (expt x 2))

Now that's cool.

I have some more thoughts on this, but I think they can wait for later in the week.