代码之家 › 专栏 › 技术社区 › Shannon Severance

为什么“let”不能用于命名内部递归过程?

let factorial scheme lambda

Shannon Severance · 技术社区 · 15 年前

考虑以下函数的实现来计算阶乘:[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}

我怎么做 让 版本工作?

方案版本为SISC V 1.16.6

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

3 回复 | 直到 15 年前

Norman Ramsey 15 年前

如何使let版本工作?

使用 letrec 而不是 let .

Robert Harvey 15 年前

R.Kent Dvvvig说:

事实上,A 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-尾-助手-2 .

[1]第2.5节“lambda表达式” 方案设计语言,第4版 http://scheme.com/tspl4/start.html#SECTGSLAMBDA

Shannon Severance 15 年前

另外两个备选方案,为了完整性而添加。

方案设计语言,第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))))

更简单的是 让 可用于插入 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))))))

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