循环是如何在函数式语言中实现的

Question

在诸如Scheme或 之类的函数式语言中，Lisp存在for和for-all循环。然而for循环需要改变，因为它不是每次迭代的新堆栈帧。由于这些语言中没有明确的突变，这些函数式语言如何实现它们各自的迭代循环？

Answer 1

Scheme 循环是在幕后使用递归实现的；诸如do只是被转换为递归过程的宏的构造。例如，这个循环在典型的过程语言中：

void print(int n) {
    for (int i = 0; i < n; i++) {
        display(i);
    }
}

... 相当于Scheme中的以下过程；在这里你可以看到循环的每个部分（初始化、退出条件、增量、主体）都有一个对应的表达式：

(define (print n)
  (define (loop i)     ; helper procedure, a "named let" would be better
    (when (< i n)      ; exit condition, if this is false the recursion ends
      (display i)      ; body
      (loop (+ i 1)))) ; increment
  (loop 0))            ; initialization

你有没有注意到在调用递归后没有什么可做的了？编译器足够聪明，可以优化它以使用单个堆栈帧，有效地使其与for循环一样高效- 阅读有关尾递归的更多详细信息。为了澄清，在 Scheme 突变中明确可用，请阅读有关set!说明。