GoKawiilFEXPR vs. vtable: how LispE evaluates instructions
The LispE paradox: it is an interpreter of compiled objects.
Ah!!! The famous opposition between interpreter and compiler. On one side, you keep the original code, which buys you flexibility and malleability, with little room for machine-level optimization. On the other, compilation hands you an efficient binary, but one horribly local to the machine it was compiled for. At least, you can usually optimize in every direction, though the code is forever frozen in its form. Except that for a Lisp, that's a bit of a shame. Building an ultra-optimized Lisp but losing homoiconicity along the way is not exactly optimal.
But LispE is a walking paradox, because LispE refuses this choice: it elects to be an interpreter of compiled objects. I know, put that way it sounds very hard-boiled. And yet... What LispE proposes is to turn each instruction of the language into a derived class that exposes an eval method. Every class has its own override of eval. And since all these classes derive from a single mother class with an original and evocative name, Element, you can build a C++ vector that holds them all. And that is where the miracle happens: the AST is kept alive, but each node is an object that can be optimized to the hilt with the full C++ arsenal.
The claim of this text is that this miracle rests on a single equivalence, which the rest of the argument makes precise and defends:
datum: f() ⟺ F.eval() instruction: f(a₁,..,aₙ) ⟺ F(a₁,..,aₙ).eval()
where F is an instance of a class derived from a universal root class, holding its arguments as sub-nodes, and eval is a method without arguments, uniform across the whole hierarchy. A datum is the zero-arity case, an instruction with no sub-node whose eval returns itself. We will see that the equivalence holds only if F is immutable, and that everything LispE does with its instructions follows from this.
But first, let us go back in time, back to a far-distant era when people asked real questions about Lisp, back to the debate over FEXPRs.
1. What is a FEXPR?
In the earliest Lisps (Lisp 1.5, MacLisp), an operator could be of two kinds:
... continue reading