Lambda the Ultimate

One point, which I'll set out here for whatever it's worth.  How the familiar task of partially evaluating programs based on lambda-calculus relates to the unfamiliar task of partially evaluating programs involving fexprs.  (Mentioned way down in Section 15.4 of my dissertation.)  Short version, the part of the calculus that deals only with fexprs —never touching source symbols, pairs, or non-fexpr procedures— is essentially lambda-calculus.  So that in learning to partially evaluate in the presence of fexprs, the fexprs are the part we already have experience dealing with.  It's the machinery for evaluating source expressions that's new.

A bit more depth.  Pure vau-calculus has three parts:

• a part that models source expressions, and has in itself no reduction rules.  (Source expression as operands can be completely analyzed by fexprs, and the fact they're irreducible is why one doesn't get the sort of trivialization Wand studied; but I digress. :-)
• a part that models fexprs and committed calls to fexprs.  (Fexprs themselves aren't source expressions, though they may result from evaluating source expressions; pairs are passive data structures, not committed calls.)  The reduction rule at the heart of this part is called the beta rule.
• a part that models evaluation of source expressions.  The reduction rules of this part look like the main routines of a meta-circular evaluator for (pure) Kernel, with rules for symbols, pairs, and self-evaluating atoms, and a rule for evaluating the operands of an application (but not for calling a fexpr, as that's the beta rule).

The main point here is simply that the second part is pretty much lambda-calculus:  up to superficial notation, its terms are lambda expressions (fexprs) and "applications" (committed fexpr calls), and its reduction is via the beta rule.  All the interesting new stuff, both strong and weak, is in the third part, the machinery of evaluation that we need in order to figure out when we can safely assume enough (stable bindings etc.) to reduce things to the second part.

Well I have given this idea some thought, but it's been a couple of months since I worked on it. Nevertheless I will share a couple of points and an idea for an simpler preliminary partial evaluator while I study my notes a little so that I can hopefully expand on this later on.

I base my work on a pure and simplified subset of Kernel. It is my idea that once this smaller problem is resolved attention can be put to add the features removed, individually and see how they affect the simple design. The work is currently suspended as I diverted my attention to writing a proper interpreter for Kernel, though I will resume it, probably in a couple of months when the interpreter is stabilized. The subset of Kernel I use doesn't have mutation of any kind (no pair mutation, no environment mutation). It also lacks first-class continuations and cyclic structures. Only the fundamental data types and functions are present. In this way I avoid the problem of environment stability and some difficult to analyze termination conditions so I can concentrate strictly on the partial evaluation of a language with fexprs.

While it's true that it seems intuitive, and even straight-forward to partially evaluate some fexprs (especially the ones that are "macro-like"), the real problem is constructing a partial evaluator that is in one hand powerful enough to detect the most number of "replacements" and in the other hand, always (well, with some assumptions of course) terminates.

There are two main mechanisms that could be applied to partially evaluate a fexpr call. One can replace the fexpr call altogether: for example replacing a call to $cond with a chain of $if's (this works perfectly for the "macro-like" fexprs). One can also replace part of the structure of the fexpr call, without altering the head of the list: for example replacing each of the clauses and bodies of a $cond, but keeping the $cond and the structure. Some times only the second is possible: for example a call to $vau can't in general be replaced, but the body can be replaced, for example to change symbols to be looked in the standard environment with the combiners they will certainly evaluate to. When both these strategies can be used, some heuristics should be applied to decide which one to use and it may even depend on the interpreter used.

Of course not only fexprs calls should be considered: partial evaluation of applicatives is a must, because they are used in the body of fexprs to manipulate the s-expressions (car, cdr, length, list, list*, etc). Also the main evaluation methods are applicatives: eval & apply. So for example, in the process of replacing a call to $lambda for the equivalent (wrap ($vau ...)) the partial evaluator has to be able to decompose the $lambda s-expression and reconstruct it, and correctly interpret the meaning of the call to eval.

I believe that an online partial evaluator - that is, one that works in one pass - is the only way to work on this. I can think of no way of separating the analysis from the partial evaluation (as in offline PE) that would work for Kernel (but would of course love to be proven wrong!).

A very important matter is the representation of the data structures in the partial evaluator. As Kernel source code has almost no meaning in itself, depending heavily on the environment in which is to be evaluated, the partial evaluator has to have a good representation of environments, allowing partial information about the bindings of an environment. In the same way partial information about pairs and list should be supported. Having a strong yet flexible representation, is critical for both the power and the termination analysis of the partial evaluator (especially online PE) and is perhaps the most important part of the design.

Other point to consider is that there are two things the partial evaluator should try to do: one thing is deciding what the result of an evaluation is (as a data structure of the partial evaluator) and another is constructing an object that evaluates to an equivalent (or the same) object in that environment. That is, given an expression "expr" to be evaluated in an environment "env", we should be able to at least have an idea of what object is the result of such evaluation (For example: a list of 3 elements, an operative that does this and that, or the number 3) and if possible we should also generate a different expression "expr'" that when eval'ed in "env" returns an object equivalent (including side-effects if present) to the result of eval'ing "expr". This is trivial if "expr" has an external representation and is self-evaluating (like a number), mildly annoying if it has no external representation or isn't self-evaluating (like a standard combiner, or a symbol or par) and could even be very difficult or impossible. But in any case it is important that we have a good representation of what object is returned because this is a recursive process: to be able to know what some expression will evaluate to in some environment, we will need to know what some other expressions evaluate to in the same or other environments. Even if we can't replace some expression by a simpler one, having information about the result of the evaluation will be vital to replace other expressions.

Finally I would like to put forward an idea that I was entertaining before suspending work in the partial evaluator. As was stated, Kernel source code has little to no meaning without an environment in which to be evaluated. This is so because Kernel has no reserved words: all combiners, even the most basic as $vau, $if and +, are represented in source code as symbols that should be searched for in the environment. Of course most of the times these are unbound by the program and the bindings are taken from the ground environment. This process however takes precious time that most interpreters of other languages don't have to pay. A first step, even simpler than full partial evaluation would be a program (a Kernel combiner) that takes Kernel source code as input (destined to be evaluated in a standard environment) and returns a new object that represents the same code, but with all possible symbols replaced by the standard combiners. Of course this program still has to perform some kind of partial evaluation / abstract interpretation to determine which symbol is evaluated where and what the bindings are, but it seems to me that the termination conditions of this would be more simple. If a symbol can't be proven to be always evaluated or if it doesn't always evaluate to the standard combiner it should be left as-is. This program seems a little less daunting to write, easier to test and could serve as a first pass to a full partial evaluator/compiler.

Appendix B of my dissertation has some interesting thoughts on this subject. (I wrote that appendix relatively early in my marathon dissertation process, and had forgotten how much there actually is there; several things worth thinking on, anyway.)