Why won't `let` work for naming internal recur

问题:

Consider the following implementation of a function to compute factorial: [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)))

I attempted to rewrite using let for the inner define:

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

There is no error at define time, but execution results in:

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

How can I make the let version work?

Scheme version is SISC v 1.16.6

[1] Based on the iterative version of factorial in section 1.2.1 of SICP http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

回答1:

How can I make the let version work?

Use letrec instead of let.

回答2:

R. Kent Dvbvig says:

---

In fact, a let expression is a syntactic extension defined in terms of lambda and procedure application, which are both core syntactic forms. In general, any expression of the form

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

is equivalent to the following.

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

---

Which means that fac-tail-2 is equivalent to:

(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

And it becomes clear that the problem is that the fac-tail-helper-2 name visible as a paramenter in the body of the lambda highlighted above, but is not a name within the lambda that is assigned to parameter fac-tail-helper-2.

[1] Section 2.5, "Lambda Expressions" of The Scheme Programming Language, 4th Edition http://scheme.com/tspl4/start.html#SECTGSLAMBDA

回答3:

Two other alternatives, being added for completeness.

The Scheme Programming Language, 4th Edition Section 3.2 has two other alternatives for using let and recursive functions. http://scheme.com/tspl4/further.html#./further:h2

The first is clever and not recommended. It involves adding a parameter to the lambda that is a lambda that it calls, and then passing itself in to get everthing started.

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

And simpler is the named let which could be used insead of letrec for single recursion.

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

Though that version hides an implicit lambda definition that is being tied to fac-tail-helper.