Lambda the Ultimate

-

`someAdderPrimitiveObject` is a primitive. It does get the expression it was called with and the local environment, but it just evaluates the expression in the local environment directly using the interpreter's internal machinery. It doesn't go through the usual message sending protocol the way you've presented it.

Alternatively, it might be implemented the way Kernel does it, where there's a primitive that wraps other methods and induces argument evaluation. That primitive itself also doesn't need to go through the usual machinery so there's no ping pong.

You can still have this sort of system implement itself, it just needs to have the correct primitives. Some systems require more than others, so you might have an aesthetic preference for systems that require a small number of simple primitives.

Fwiw, some perspective on where the idea for Kernel evaluation came from. (And I'll add a quick remark at the end about message-passing.) Sorry if this runs a bit long, but the ideas involved really are rather subtle imho, and in fact I reacted with incredulity myself when I first came up with the idea for Kernel evaluation.

One day in the late 1990s I was playing around with implementation of a Scheme, or Scheme-like, interpreter, written in C (well, Gnu C). A state of the interpreter was to be made up of a value and a continuation. The continuation would have a method to receive a value, which would return a new state. The interpreter top-level logic would step, by applying the current state's continuation to the current state's value, resulting in a new state; and, repeat, forever. So the continuations did all the real work.

I'd imagined a continuation for handling a procedure call; it would wait to receive the value of some operand evaluation previously scheduled, and would already have, stored in fields of the continuation, a list of operands not yet evaluated, list of arguments (that is, results of previous operand evaluations), pointer to the environment in which to evaluate operands, pointer to a "procedure" object to which to pass the completed argument list, and pointer to another continuation to receive the result returned by the procedure. When this continuation received a value, it would add it to the list of arguments, and either schedule another operand evaluation, setting up a suitable continuation to receive the result, or, if there were no more operands waiting to be evaluated, call the procedure with the completed argument list, scheduling the result to be sent to the stored continuation meant to receive it.

However, this would then require a whole bunch of other continuation types for the various special forms of Scheme. That seemed inelegant. So I had the idea to split the procedure-call continuation into two continuations, essentially a front-end and a back-end. The front-end would do all that same juggling to assemble an argument list by evaluating operands, but then would just send the completed argument list on to whatever continuation it had been told to send its result to — presumably, to a back-end. The back-end would wait patiently to receive a value, presumably the completed argument list, and call the procedure accordingly. With this arrangement, there would be no need for a lot of separate continuation types to handle special forms; just provide a primitive procedure to handle the operand list of that special form, and when evaluating a special form with the appropriate operator, set up a back-end continuation without a front-end, so the procedure will receive the unevaluated operands.

It then quickly occurred to me that I could set up a lambda-like device for creating new, first-class "special forms" (in those first hours, I used the name special-lambda; choosing a better name involved months of researching obscure alphabets). The internal form of an "ordinary" Scheme procedure would then be simply a struct containing a single field pointing to the "special-procedure" to which the argument list should be sent after a front-end continuation has finished building it. The primitive special-procedure that evaluates an expression — there has to be such a primitive — would handle a combination by first evaluating the operator; if the result of operator-evaluation is a special-procedure it would just set up a back-end to receive the operand list, or if the result of operator-evaluation is an ordinary-procedure it would set up a back-end and also set up a front-end.

Notice that the key innovation here is not reduction of the usual processing of an ordinary Scheme procedure call to special-procedure calls that don't evaluate their operands; not, somehow, "elimination" of operand-evaluations; but simply factorization of an ordinary Scheme procedure call into two stages: first, evaluate the operands to produce arguments, and second, apply the underlying special-procedure to the argument list. All the things done before are still done, we're just keeping track of them separately.

Although I was immediately quite excited by this idea, with first class special-procedures constructed by a special-lambda, I was also very leery about it. Even though I see it all now as very elegant, I still remember vividly what it felt like to doubt the whole thing, because my doubt at the time was quite intense. Because it seemed like the spark of evaluation would keep almost going out, only be rekindled just barely. Scheme, after all, has this ubiquitous assumption that all operands are to be evaluated, with just a few special exceptions made for special forms holding back the operand-evaluation that would otherwise occur; but with this new algorithm, it seems, the default is that no operands are evaluated, and the computation has to be constantly nudged along, blowing on that spark of evaluation to keep it from going out: when evaluating a combination, only evaluate the operator, without expecting the operands to be evaluated; and if the operator evaluates to an "ordinary-procedure" (what I'd now call an applicative), only then schedule evaluations of the operands. I just lay down and stared at nothing for hours, that afternoon, convincing myself that it really would work. But this modified evaluator algorithm, in situations where it's doing things that would also work in Scheme, isn't actually doing any less evaluation than Scheme would do — it's just leaving open opportunities where, at the programmer's discretion, the program could deviate from the usual Scheme-like evaluation behavior to do funky new kinds of things. (Those opportunities for deviation are, of course, also why the equational theory of the language is somewhat weakened, but thereon hangs another tale.)

As for message passing, note that the value-and-continuation structure I've described essentially is message-passing; the value is the message. It's all just another way of factoring the tasks that need to be performed; all those tasks have to be in there somewhere, or the system really wouldn't work.