SICP recursive let definition

Question

For

(let ((fact 
        (lambda (n)
            (if (= n 1)
                1
                (* n (fact (- n 1)))))))
(fact 10))

Scheme gives an error, i wanted to confirm if my reasoning is correct,

Since (let ((var1 arg1)) body) is equivalent to evaluating the body in an environment where var1 is bound to arg1.

Above, when we are trying to calculate arg1 before the bind call, we do not find the reference as that is exactly what we are trying to bind for it to be available

But then why does this not throw

(let ((fact (lambda (n) 
             (if (= n 1) 1 (* n (fact (- n 1))))))) 
  (display 10))

as we are trying to make the binding there as well.

Also why doesn't this throw then

(define factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n (factorial (- n 1))))))
          
(factorial 10)

Mark Saving Mark Saving · Accepted Answer · 2021-06-07T05:00:00

The reason is that the "variable fact is not bound" error occurs only when we actually try to look up the value of "fact". Consider

(let ((fact (lambda (n) (if (= n 0)
                            1
                            (* n (fact (- n 1)))))))
 (fact 0))

This does not cause an error because we do not enter the else clause and therefore do not attempt to use the value of the unbound variable fact. However, trying the same thing with 1 does give us the error.

We do not run into an error when using define because define and let have different rules. In a let binding, you create a new lexical scope, and the binding of fact in the let binding does not "leak out" from the let to the outside world. Since the right side of a let assignment must only refer to bindings from the outside world, the right side cannot refer to the binding fact.

However, in a define statement, the whole point is to introduce a new binding in the current scope (not create a new scope). In a define binding, the right side of the assignment must refer only to variables from the outside world - but this potentially includes the variable being defined, as long as accessing it is hidden behind a lambda and hence done lazily.

In fact, consider the following:

(define is-even
  (lambda (n) (or (= n 0)
                  (is-odd (- n 1)))))

(define is-odd
  (lambda (n) (and (not (= n 0))
                   (is-even (- n 1)))))

(display (is-odd 55))

In this case, by the time we actually call is-even, is-odd is defined in the same scope as is-even and hence we can look up its value. Similarly, when we call is-odd, is-even is already defined and hence we have a binding for its value.

Note that the following does not work:

(define is-even
  (lambda (n) (or (= n 0)
                  (is-odd (- n 1)))))

(display (let ((is-odd (lambda (n) (and (not (= n 0))
                                        (is-even (- n 1))))))
            (is-odd 55)))

This is because the is-odd binding here is not in the same scope as is-even. It is defined in a more local binding than is-even is. The is-odd being referred to in the is-even definition cannot be the same is-odd as created in the let statement, because this is-odd is a local binding and thus cannot be referred to in the wider scope that is-even is defined in.

If we were using the old-fashioned LISP notion of "dynamic scope", also known as "call-by-name semantics", the latter example would work perfectly fine. However, Scheme does not support dynamic scope (which is definitely for the best in my view).

SICP recursive let definition

1 Answers