Thursday, January 15, 2009

Again, we covered some more material that I'm passingly familiar with and I think a lot of Lisp and Scheme hackers would find familiar as well. The first thing was how to introduce implicit backtracking in a combinator-based interpreter. The first step is to curry eval.
(define (eval expression environment)
  ((analyze expression) environment))
This allows us to separate the static analysis of the program from the running of the program with ‘real data’. analyze is really a compiler. Now all the subcases of eval will emit procedures that take a single argument of the environment and return the computed value.

Larceny uses something almost exactly like this in its interpreter. In fact, the Scheme interpreter I'm writing does this as well, although it is difficult to see that because of all the extra cruft to support tail recursion and first-class continuations.

By changing the structure of the interpreter combinators to continuation-passing-style it is reasonably easy to add the McCarthy AMB operator.

Gerry then went on to show that if you can grab the implicit continuation of the underlying language, you can embed AMB directly rather than layering it on in an isolated interpreter. He pointed out that Scheme was one of the few languages that supplied first-class continuations. (I did have to point out that by using the tricks in ‘Continuations from Generalized Stack Inspection’ you can embed first-class continuations in nearly any language, but of course the contortions you have to go through are pretty horrific.)

I'm not sure how much to write here. Since I've been steeping myself in this sort of thing for the past several years, most of this stuff seems fairly straightforward, if esoteric.
Post a Comment