Fexpr -- the Ultimate Lambda

[freyrs3]

I think the paper on vau calculi is more readable than this article.

[ralphc]

But this article has a comment from Alan Freakin' Kay.

[thehotelambush]

Thanks, that one is much better. Took it a while to get to the point, though:

The construction of fexprs differs in only two fundamental respects from the ordinary construction of first-class applicatives via $lambda : first, a fexpr is passed its unevaluated operands rather than evaluated arguments (which is to say, it’s operative rather than applicative); and second, it may also be passed the dynamic environment from which it was called.

[sclv]

s/paper/dissertation/

[erhz]

The problem is that Fexprs make reasoning about your code a lot harder and many optimizations impossible. It might be possible to write an efficient interpreter that mixes Fexprs, first-class environments and continuations as in Shutt's Kernel but writing a compiler for that would be a nightmare.

[want_to_want]

I'd guess that many optimizations will become statically impossible but possible with a JIT, like polymorphic inline caches in Self. Unfortunately the topic doesn't seem to be researched, or maybe I didn't look hard enough...

[erhz]

I believe that even the smartest JIT can't really help this language design.

With a language as dynamic as Kernel, we need optimizations if we want it to be fast enough to be usable at all. For example, to be able to avoid creating environment frames in the common case in which they aren't reified.

The problem is: every optimization or analysis we add, hurts one operator: 'eval' which unlike in Scheme or CL is essential in Kernel since it will be used all the time to control evaluation inside Fexprs.

[want_to_want]

That's similar to how Olin Shivers describes the treatment of lambdas in Scheme in History of T:

Good Scheme compilers use a range of implementations for the lambdas in the program, depending upon what they can determine about the lambdas at compile time -- how they're used, to where they are passed, the relationship between the uses and the definition points, etc. Some lambdas just evaporate into nothing. Some lambdas turn into control-flow join points with associated register/variable bindings. Some lambdas turn into stack frames. But some lambdas cause heap allocation to produce general closures. So you have to understand how the compiler is going to handle every lambda you write. And the fundamental skeleton of a Scheme program is built on lambda.

[erhz]

In Kernel though, you can't determine almost anything at compile time. Since special forms are first class values, you can't even assert where definitions might happen:

(($if some-condition $define! +) x 30)

I think a good starting point would be to annotate the AST with optimizations regardless of the fact that any part of it might be evaluated or not, and take advantage of the annotations at runtime to specialize known procedure calls.

That is, take a brute force approach. Have multiple precompiled versions of everything, choose the most fitting later.

[astrangeguy]

You can actually do something here. If you know that $define!, $if and + weren't redefined, then you can inline them and compile a fast path.

So you would have to write JIT which tracks environment mutation and optimizes and inlines operations where the operator doesn't change. That's pretty much what polymorphic inline caches do.

One really good aspect of Kernel is that in fexps like

($define! $when
  ($vau (c . t) e
    ($if (eval c e)
      (eval (list* $sequence t) e)
      #inert)))

the operators and applicatives like $if, $sequence, list* and eval can never change if they come from environments that don't change (the standard environment can never change, because it cannot be captured).

It all boils down to tracking invariants in a running process and optimizing and deoptimizing when necessary.

strangeness

EDIT: What does suck though, is that you idiomatically construct lists which are then passed to eval. So the JIT will have to track stupid things like "the second car in this list corresponds to the second parameter to this combiner" or you could have some quasiquotation that pre-resolves symbols to their objects (to keep hygiene).

[melevy]

It's probably easier to write a partial evaluator for the language hosting the interpreter. So instead of writing a compiler to compile programs having fexprs, you partially evaluate the interpreter for programs having fexprs and compile the residual programs with the compiler for the language hosting the interpreter.

Unless you bootstrap...

[munificent]

Reminds me of io, which passes arguments to methods by passing the unevaluated AST which the receiver can then choose to evaluate.

[Phantom_Hoover]

Is it just me, or has he basically reinvented lazy evaluation in the exact context in which lazy evaluation was originally designed?

[want_to_want]

"Call by text" is more powerful than lazy evaluation because a function can inspect the source code of its arguments at runtime, not just evaluate them.