4

我试图弄清楚如何实现 Lisp 评估 non-recursive。我的基于 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。

4

5 回答 5

4

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

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

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

于 2012-10-21T07:46:57.817 回答
3

请参阅此主题：继续传递样式

于 2012-10-21T07:37:02.330 回答
3

在 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;
于 2012-10-29T09:06:20.173 回答
0

我认为您可能缺少的关键见解是，在 lisp 解释器中，最小的函数集被实现为非递归的原语。原语的确切集合各不相同，但包括 cons、car、cdr 和 apply 的“最原始”版本，它执行这些实际功能之一，而不是其自身的解释版本。

你应该查阅 John McCarthy 的原始论文和/或 John Allen 的 Lisp 1.5

于 2012-10-21T08:06:36.927 回答
0

我记得有一本关于 HOPE 编程语言的书。它是一种类似于 ML 的函数式语言。它对其编译器进行了全面的概念描述，并总体上对函数式语言编译器进行了思考。它提出的一个观察结果是关于 Y-combinator 的争论。作者建议处理递归函数的一种可能方法是实现 Y-combinator 并将每个递归函数转换为可以使用 Y-combinator 进行递归的非递归函数。

这将是一种类似的if特殊形式的技巧，它提供（通常就足够了）人们在一种语言中可能需要的各种惰性求值。以类似的方式，您可以限制所有函数递归，但引入一个Y允许递归开始的特殊函数。

于 2012-10-21T12:59:35.980 回答