Flat evaluation of Lisp s-expressions

Question

I'm trying to figure out how I could implement Lisp evaluation non-recursive. My C based evaluator is Minimal Lisp file l1.c. However several functions there recurse into eval again: eval, apply, evargs, evlist and also the Lisp Ops defineFunc, whileFunc, setqFunc, ifFunc...

I'm trying to figure out an evaluation that is flat. Some possible ways I could come up with:

1. Transforming to byte code and execute in VM
2. Implement a flat Forth evaluator and implement Lisp evaluation in Forth, this is kind of what lf.f does.
3. Another possibility might be to join all recursinge functions in l1.c into one big switch loop. Local variables would be joined into a heap-based struct, calls to recursing subfunctions would be implemented by a heap-based return-stack.

My question is: Are there algorithms/papers/implementations that do flat evaluation in different ways. I'm searching for an implementation that don't transform into byte-code but something similar to the recursion-less "depth-first traversal" using a pushdown stack. I'd like to operate on the original s-expression.

Answer: when implementing the evaluator in c you need to implement the whole thing in a flat loop, implement the return stack and stackframes by hand, model the control flow using goto and switch(). Here is an example: flat .

Answer 1

See this topic: Continuation Passing Style

Answer 2

A very important aspect of Lisp, and in fact an important aspect of many functional languages that followed, is that it is compositional. This means that the meaning of an expression is defined using the meanings of its subexpressions -- or, in other words, the definition of evaluation is something that is inherently recursive. In non-functional languages there are some differences as in expressions vs statements, but even there expressions are not limited in some way, so recursion is baked into the definition too. Probably the only cases where the recursiveness of the language's definition is not as apparent, are assembly languages. (Though even there a definition of meaning would, of course, require induction.)

So a fight with some recursion definition of eval is something that you will lose. If you go with compilation to machine code, that code will be recursive (and the generating code would be recursive too). If you do the evaluation via a Forth evaluator, then that evaluator would still be recursive. Even if you go with the CPS suggestion in the other answer, you merely end up having yet another encoding of the stack.

So the bottom line is that the best you can get to is some encoding of the stack that doesn't use the machine stack directly -- no substantial difference, but you usually lose performance (since CPUs handle the stack very efficiently, and an encoding of it on the heap is going to be slower).