3

考虑以下计算阶乘的函数实现:[1]

(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]基于SICP http://mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.1factorial 1.2.1节的迭代版本

4

3 回答 3

8

如何使 let 版本正常工作?

使用letrec而不是let.

于 2010-07-02T22:56:33.517 回答
6

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,但不是lambda分配给参数的名称fac-tail-helper-2

[1] 第4 版 Scheme 编程语言 第 2.5 节“Lambda 表达式” http://scheme.com/tspl4/start.html#SECTGSLAMBDA

于 2010-07-02T22:30:26.087 回答
0

为了完整起见,添加了另外两个替代方案。

Scheme 编程语言,第 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单次递归的命名。

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

尽管该版本隐藏了与 fac-tail-helper 相关联的隐式 lambda 定义。

于 2010-07-06T16:46:05.707 回答