Lisp s 表达式的平面求值

Question

我试图弄清楚如何实现 Lisp 评估 非递归。我的基于 C 的评估器是Minimal Lisp文件 l1.c。然而，其中的几个函数再次递归为 eval：eval、apply、evargs、evlist 以及 Lisp Ops DefineFunc、whileFunc、setqFunc、ifFunc...

我正在尝试找出一个平坦的评估。我可以想出一些可能的方法：

1. 转换为字节码并在VM中执行
2. 实现一个扁平的 Forth 求值器并在 Forth 中实现 Lisp 求值，这就是lf.f所做的事情。
3. 另一种可能性可能是将 l1.c 中的所有递归函数加入到一个大 switch 循环中。局部变量将被连接到基于堆的结构中，对递归子函数的调用将由基于堆的返回堆栈实现。

我的问题是：是否有算法/论文/实现以不同的方式进行平面评估。我正在寻找一种不转换为字节码但类似于使用下推堆栈的无递归“深度优先遍历”的实现。我想对原始的 s 表达式进行操作。

答案：在 C 语言中实现求值器时，您需要在平面循环中实现整个过程，手动实现返回堆栈和堆栈帧，使用 goto 和 switch() 对控制流进行建模。这是一个例子：flat。

Answer 1

Lisp 的一个非常重要的方面，事实上也是随后的许多函数式语言的一个重要方面，就是它是组合性的。这意味着表达式的含义是使用其子表达式的含义来定义的，或者换句话说，求值的定义本质上是递归的。在非函数式语言中，表达式与语句之间存在一些差异，但即使表达式也不受某种方式的限制，因此递归也包含在定义中。语言定义的递归性不那么明显的唯一情况可能是汇编语言。（当然，即使存在意义的定义也需要归纳。）

因此，与某些递归定义的斗争eval是你会失败的。如果您编译为机器代码，则该代码将是递归的（并且生成代码也将是递归的）。如果您通过 Forth 求值器进行求值，那么该求值器仍然是递归的。即使您遵循其他答案中的 CPS 建议，您最终也只会得到另一种堆栈编码。

所以最重要的是，你能得到的最好的方法是不直接使用机器堆栈的堆栈编码——没有实质性的区别，但你通常会损失性能（因为CPU非常有效地处理堆栈，并且编码它在堆上的速度会更慢）。

Answer 2

当在 C 中实现 Lisp 求值器时，C 编译器使用堆栈来生成子例程调用的控制流。要在 C 中实现无堆栈求值器，您需要使用 goto 和 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;
}

得到

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;