FEXPRs vs. vtable: how LispE interpreter works
17 points by Claudius
17 points by Claudius
Deeply interesting. LispE is a nice contrast to the usual dynamic type-switching evaluator. Self-evaluating trees was quite elegant as a solution, looks like the object-oriented approach was a really good fit.
As a C programmer, I'm squarely in the evals[] camp since there is no language level dynamic dispatch. This is further complicated by the fact my lisp does expose FEXPRs at the language level, and even makes modular FEXPRs out of things usually inlined in the evaluator, such as if. My evals[] is actually just the normal variable resolution mechanism.
I'm definitely converging towards something that resembles vtables, though. I'm halfway towards implementing shapes for the hash table type, and I've also learned how inline caches work. The final item needed to truly bind these two together is bytecode compilation. I attempted to implement caches and specialized object representations twice now, and was surprised both times by performance regressions, because the deoptimization checks are too expensive without inlining them into bytecode. The tree walking interpreter has become the performance wall.
As for the opaqueness of FEXPRs, I'm hoping that future work on a partial evaluator can work around the issue by pre-evaluating most if not all of the FEXPRs. Languages truly are a lifetime of work...
Actually, I did have a look on Python, and I found it quite interesting that since it is implemented in C, they came up with a system that looks like a lot a vtable mechanism. Creating languages is an endless endeavor. There is something pretty magical about it, when you write your first programs and you see the execution yielding the exact value you expected. We definitely need to keep the conversation alive.
The real point of the article is that you can reason on the AST once it's compiled into pointers. In C you don't even need the vtable: a struct with a pointer to the function implementing the instruction's behavior is enough. The win is that this choice can be made very early, at composition rather than at each step, which removes the cost of selecting the right code and of consulting evals[] on every pass. The catch is exactly the FEXPRs you expose at the language level. You can freeze that function pointer early only for instructions whose behavior is fixed at composition, your EXPRs, and your modular if, as long as it isn't redefined. A FEXPR resolved through variable lookup can't be frozen, by design. So the line between "freeze the pointer now" and "keep resolving it" is the same line as EXPR vs. FEXPR, which is also where your partial evaluator will succeed or stall. It can pre-evaluate the cases that could have been frozen anyway, and only the genuinely late-deciding FEXPRs will remain.