Monday, January 12, 2009

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.


steck said...

I wonder if this kind of overloading could be expressed using Haskell type classes? I haven't tried it ...

Haskell type classes enforce typefulness where generics don't. An element of a Haskell type class might be required that its first two arguments be of the same, perhaps unspecified, type, whereas generics don't. So if you have an overloaded * operator, it might be useful to multiply an array by a vector, and type classes might prevent that.

Duncan said...

Are you in Boston now?

Joe Marshall said...

I'm curious as to how one would do this sort of thing in Haskell. Haskell gives you parametric polymorphism, but Gerry is making use of ad hoc polymorphism.

I am in San Francisco. GJS is visiting for this seminar.

steck said...

Haskell gives you a form of ad hoc polymorphism ("How to make ad hoc polymorphism less ad hoc" is the name of the seminal paper) in the form of type classes.

In fact, the point I was making is that you could use type classes to get that ad hoc polymorphism, but the parametric polymorphism might be an obstacle (in some cases).

Paulo J. Matos said...

Awesome seminar. I wonder if the lecture (videos/slides/tutorial, anything) will be online. If any material comes up please let us know!!! :D