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

When implementing a Lisp-evaluator in C, the C-compiler uses the stack to generate control-flow of subroutine calls. To implement a stack-less evaluator in C you need to write the control-flow by hand using goto and switch():

v *
evargs(ctx *cctx, v *l, v *env)
{
    struct v *r = 0;
    if (l) {
        r = eval(cctx, car(l),env);
        r =  mkCons(r,evargs(cctx, cdr(l),env));
    }
    return r;
}

gets

case EVARGS_0:
    S_SET(0,0);                         /* EVARGS_0: r = 0; */ 
    if (!(v=S(2)))                      /* if (l) */
        goto ret;
    RCALL_EVAL(EVARGS_1, car(v));       /* r = < eval(cctx, car(l),env); > */
    break;    
case EVARGS_1:
    S_SET(3,S(1));                      /* EVARGS_1: < r = ... > */
    RCALL_EVARGS(EVARGS_2, cdr(S(2)));  /*  r =  mkCons(r, < evargs(cctx, cdr(l),env) > ); */
    break;
case EVARGS_2:
    S_SET(0,mkCons(S(3),S(1)));         /* EVARGS_2: < r =  mkCons(r,  evargs(cctx, cdr(l),env)  ); > */
    goto ret;

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).

Answer 3

See this topic: Continuation Passing Style

Answer 4

I think the key insight you may be missing is that in a lisp interpreter, a minimal set of functions are implemented as primitives which are non recursive. The exact set of primitives varies, but includes cons, car, cdr and a "most primitive" version of apply that executes one of these real functions rather than the interpreted version of itself.

You should look up John McCarthy's original papers, and/or John Allen's Lisp 1.5

Answer 5

I remember having a book on HOPE programming language. It is a functional language similar to ML. It had a thorough conceptual description of its compiler, and thoughts about functional language compilers in general. One observation it made was an argument about Y-combinator. The author suggested that one possible way of dealing with recursive functions would be an implementation of Y-combinator and transformation of each recursive function into a non-recursive one that can be made to recur using Y-combinator.

This would be a similar trick you have in if special form, which provides (and usually suffices) for all kinds of lazy evaluations one can require in a language. In a similar way you could restrict all functions from being recursive, but introduces a special Y function that would allow recursion to commence.