为什么‘Why’不能命名内部递归过程？

Question

考虑计算阶乘的函数的以下实现：

(define fac-tail
  (lambda (n)
    (define fac-tail-helper
      (lambda (n ac)
        (if (= 0 n)
            ac
            (fac-tail-helper (- n 1) (* n ac)))))
    (fac-tail-helper n 1)))

我试图用let重写内部定义：

(define fac-tail-2
  (lambda (n)
    (let ((fac-tail-helper-2
            (lambda (n ac)
              (if (= 0 n)
                  ac
                  (fac-tail-helper-2 (- n 1) (* n ac))))))
    (fac-tail-helper-2 n 1))))

在define时没有错误，但是执行会导致：

#;> (fac-tail-2 4)
Error: undefined variable 'fac-tail-helper-2'.
{warning: printing of stack trace not supported}

如何使let版本工作？

方案版本为SISC v. 1.16.6

1基于factorial迭代版本在http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 1.2.1节中的应用

Answer 1

如何使let版本工作？

使用letrec而不是let。

Answer 2

R. Kent Dvbvig说：

实际上，let表达式是以lambda和过程应用程序定义的语法扩展，两者都是核心的语法形式。一般来说，表单的任何表达式

(let ((var expr) ...) body1 body2 ...) 

与以下内容相同。

((lambda (var ...) body1 body2 ...)
 expr ...)" [1]

这意味着fac-tail-2相当于：

(define fac-tail-2
  (lambda (n)
    ((lambda (fac-tail-helper-2)
       (fac-tail-helper-2 n 1)) ;; <== scope where fac-tail-helper-2 is visible.
     (lambda (n ac) ;; this lambda is assigned to fac-tail-helper-2
       (if (= 0 n)
           ac
           (fac-tail-helper-2 (- n 1) (* n ac))))))) ;; <=== problem

很明显，问题在于，fac-tail-helper-2名称在上面突出显示的lambda主体中作为参数可见，但不是分配给参数fac-tail-helper-2的lambda中的名称。

1第2.5节，方案编程语言的"Lambda表达式“，第4版http://scheme.com/tspl4/start.html#SECTGSLAMBDA

Answer 3

另外两个备选方案，为完整性而添加.

方案编程语言第4版第3.2节为使用let和递归函数提供了另外两种选择。http://scheme.com/tspl4/further.html#./further:h2

第一个是聪明的，不被推荐的。它包括向lambda添加一个参数，即它调用的lambda，然后传入它自己，以启动所有事情。

(define fac-tail-4
  (lambda (n)
    (let ((fac-tail-helper
            (lambda (fac-tail-helper n ac)
              (if (= 0 n)
                  ac
                  (fac-tail-helper fac-tail-helper (- n 1) (* n ac))))))
      (fac-tail-helper fac-tail-helper n 1))))

更简单的是命名为let，可以使用letrec的insead进行单次递归。

(define fac-tail-3
  (lambda (x)
    (let fac-tail-helper ((n x) (ac 1))
      (if (= 0 n)
          ac
          (fac-tail-helper (- n 1) (* n ac))))))

尽管该版本隐藏了一个隐式lambda定义，该定义被绑定到fac-tail-helper。