c++ - 使用堆栈而不是递归实现 Lisp eval

Question

我正在查看 howtowriteaprogram.blogspot.com/2010/11/lisp-interpreter-in-90-lines-of-c.html并希望了解如何在不使用递归的情况下实现 eval() 函数，而是将其作为使用堆栈的迭代函数。

这里是 eval() 的代码，摘自这篇文章:

////////////////////// 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);
}

我首先被绊倒的地方是想知道如何用堆栈实现“if”逻辑。如果您将条件(第一个单元格)放在堆栈上并进行下一次迭代，您如何知道返回到您随后决定是否分支到“then”或“else”单元格/节点的点？

这同样适用于任何其他逻辑:例如，如果我将用于“定义”的单元格放在堆栈上并转到下一次迭代，一旦它被评估，我怎么知道返回去同一个地方？

Answer 1

我做过两次。曾经in Common Lisp一次in Brainfuck .基本思想是执行原语和应用程序或将元素插入堆栈。每个部分都有一个目标，因此评估过程严重依赖于按地址改变 cons 单元。一个例子。 # 是实际地址而不是符号:

(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>

结果 (a . b) 在地址为#result 的汽车中找到。

#preapply 是一个处理特殊形式的原语，如 if、lambda 和 flambda。它还插入结构，以便在它是一个函数时评估每个参数。 #apply 对于原语以及 lambda 的堆栈和环境操作来说很简单。

在我的实现中，特殊形式和原始函数的地址最低，因此原始函数只是内存中的一个特殊位置。