c++ - Implementing Lisp eval with a stack instead of recursion -

i looking @ howtowriteaprogram.blogspot.com/2010/11/lisp-interpreter-in-90-lines-of-c.html , see how implement eval() function without recursion, instead iterative function using stack.

here code eval() taken 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 reference environment exists (when             // lambda being defined) because that's outer environment             // we'll need use when lambda executed             x.env = env;             return x;         }         if (x.list[0].val == "begin") {     // (begin exp*)             (size_t = 1; < 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;     (cell::iter exp = x.list.begin() + 1; exp != x.list.end(); ++exp)         exps.push_back(eval(*exp, env));     if (proc.type == lambda) {         // create environment execution of lambda function         // outer environment 1 existed* @ time         // lambda defined , new inner associations         // parameter names given arguments.         // *although environmet existed @ time lambda defined         // wasn't complete - may have subsequently had         // more symbols defined in 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 function\n";     exit(1); } 

the first place got tripped wondering how implement "if" logic stack. if placed condition (first cell) on stack , went next iteration, how know point decided whether branch "then" or "else" cell/node?

the same apply of other logic though: if, example, place cell 'define' on stack , go next iteration, once evaluated, how know same place?

i've done twice. once in common lisp , once in brainfuck. basic idea primitives , application or push elements stack. each part has target, eval process relies hevily on mutating cons cells address. example. # actual address , not 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 #b) #result                 ->  quote #r (#preapply #r b) #b (#apply #cons #b) #result                 ->  (#preapply #quote b) #b (#apply #cons #b) #result                 ->  (#apply #cons b)  #result                 ->  <empty stack> 

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

the #preapply primitive handles special forms, if, lambda , flambda. pushes structure evaluates each argument when it' function. #apply simple primitives , stack , environment manupilations lambdas.

in implementations special forms , primitive functions has lowest addresses, primitives special location in memory.