Implementing Lisp eval with a stack instead of recursion

Question

I am looking at howtowriteaprogram.blogspot.com/2010/11/lisp-interpreter-in-90-lines-of-c.html and would like to see how I could implement the eval() function without recursion, but instead as an iterative function using a stack.

Here is the code for eval() taken from the article:

////////////////////// eval

cell eval(cell x, environment * env)
{
    if (x.type == Symbol)
        return env->find(x.val)[x.val];
    if (x.type == Number)
        return x;
    if (x.list.empty())
        return nil;
    if (x.list[0].type == Symbol) {
        if (x.list[0].val == "quote")       // (quote exp)
            return x.list[1];
        if (x.list[0].val == "if")          // (if test conseq [alt])
            return eval(eval(x.list[1], env).val == "#f" ? (x.list.size() < 4 ? nil : x.list[3]) : x.list[2], env);
        if (x.list[0].val == "set!")        // (set! var exp)
            return env->find(x.list[1].val)[x.list[1].val] = eval(x.list[2], env);
        if (x.list[0].val == "define")      // (define var exp)
            return (*env)[x.list[1].val] = eval(x.list[2], env);
        if (x.list[0].val == "lambda") {    // (lambda (var*) exp)
            x.type = Lambda;
            // keep a reference to the environment that exists now (when the
            // lambda is being defined) because that's the outer environment
            // we'll need to use when the lambda is executed
            x.env = env;
            return x;
        }
        if (x.list[0].val == "begin") {     // (begin exp*)
            for (size_t i = 1; i < x.list.size() - 1; ++i)
                eval(x.list[i], env);
            return eval(x.list[x.list.size() - 1], env);
        }
    }
                                            // (proc exp*)
    cell proc(eval(x.list[0], env));
    cells exps;
    for (cell::iter exp = x.list.begin() + 1; exp != x.list.end(); ++exp)
        exps.push_back(eval(*exp, env));
    if (proc.type == Lambda) {
        // Create an environment for the execution of this lambda function
        // where the outer environment is the one that existed* at the time
        // the lambda was defined and the new inner associations are the
        // parameter names with the given arguments.
        // *Although the environmet existed at the time the lambda was defined
        // it wasn't necessarily complete - it may have subsequently had
        // more symbols defined in that environment.
        return eval(/*body*/proc.list[2], new environment(/*parms*/proc.list[1].list, /*args*/exps, proc.env));
    }
    else if (proc.type == Proc)
        return proc.proc(exps);

    std::cout << "not a function\n";
    exit(1);
}

The first place I got tripped up is wondering how you would implement the "if" logic with a stack. If you placed the condition (first cell) on the stack and went to the next iteration, how would you know to get back to the point where you then decided whether to branch to the "then" or "else" cell/node?

The same would apply to any of the other logic though: If, for example, I place the cell for 'define' on the stack and go to the next iteration, once that is evaluated, how would I know to get back to the same place?

Answer 1

I've done it twice. Once in Common Lisp and once in Brainfuck. The basic idea is to do the primitives and application or push elements to be stack. Each part has a target, thus the eval process relies hevily on mutating cons cells by address. An example. # is the actual address and not a symbol:

(cons 'a 'b) 
#result      ->

cons 
#x
(#preapply #x 'a 'b)
#result              ->

(#preapply #cons 'a 'b) ->

'a
#a
'b
#b
(#apply #cons #a #b)
#result                 ->

quote
#r
(#preapply #r a)
#a
'b
#b
(#apply #cons #a #b)
#result                 ->

'b
#b
(#apply #cons #a #b)
#result                 ->

'b
#b
(#apply #cons a #b)
#result                 ->

quote
#r
(#preapply #r b)
#b
(#apply #cons a #b)
#result                 ->

(#preapply #quote b)
#b
(#apply #cons a #b)
#result                 ->

(#apply #cons a b) 
#result                 ->

<empty stack>

The result, (a . b) is found in the car of the cons with address #result.

The #preapply is a primitive that handles special forms, like if, lambda and flambda. It also pushes the structure so that it evaluates each argument when it' a function. #apply is simple for primitives and stack and environment manupilations for lambdas.

In my implementations The special forms and the primitive functions has the lowest addresses, thus primitives are just a special location in memory.