Defining multiple local functions with “let over lambda” form in Scheme

Question

I was curious about defining multiple lexically scoped functions in Scheme that can call each other. Working in SICP, I produced the following function using block structure to solve Exercise 1.8 (calculating cube-root using Newton's method):

(define (cbrt x)
  (define (good-enough? guess prev-guess)
    (< (/ (abs (- guess prev-guess))
          guess)
       0.001))
  (define (improve guess)
    (/ (+ (/ x (square guess))
          (* 2 guess))
       3))
  (define (cbrt-iter guess prev-guess)
    (if (good-enough? guess prev-guess)
        guess
        (cbrt-iter (improve guess)
                   guess)))
  (cbrt-iter 1.0 0.0))

This works fine, but it got me wondering how Scheme (and perhaps Common Lisp) might handle this same scenario using lexical scoping and the let form. I tried to implement it using let with the following kludgy code:

(define (cbrt x)
  (let ((calc-cbrt
         (lambda (guess prev-guess)
           (let ((good-enough?
                  (lambda (guess prev-guess)
                    (< (/ (abs (- guess prev-guess))
                          guess)
                       0.001))))
             (good-enough? guess prev-guess))
           (let ((improve
                  (lambda (guess)
                    (/ (+ (/ x (square guess))
                          (* 2 guess))
                       3))))
             (improve guess))
           (let ((cbrt-iter
                  (lambda (guess prev-guess)
                    (if (good-enough? guess prev-guess)
                        guess
                        (cbrt-iter (improve guess)
                                   guess)))))
             (cbrt-iter 1.0 0.0)))))
    (calc-cbrt 1.0 0.0)))

The problem that I see below is when cbrt-iter attempts to call the good-enough? procedure. Since the good-enough? procedure is only local to the scope of the first nested let block, cbrt-iter has no way to access it. It seems that this can be solved by nesting the cbrt-iter function within the enclosing let of good-enough, but this seems also very kludgy and awkward.

What is the define form doing that is different in this case? Is the define form expanding to lambda expressions instead of the "let over lambda" form (I recall something similar being done in the Little Schemer book using the form ((lambda (x) x x) (lambda (y) ...)), but I am not sure how this would work). Also, by way of comparison, how does Common Lisp handle this situation - is it possible to use lexically scoped defun's ?

As described in the answers there are other forms of let such as let* and letrec which allow a set of bindings in a let to 'see' previous (let*) or each other (letrec). docs.racket-lang.org/reference/let.html — karmakaze

Fixnum Fixnum · Accepted Answer · 2012-10-31T01:33:16

First of all, you don't need to introduce a new procedure calc-cbrt - you could just call calc-iter instead.

Second, the meaning of define and let are quite different. Define installs the definitions into the local scope, as in your example. However, let expressions are just syntactic sugar for lambda expressions (see SICP section 1.3 for details). As a result (and as you mention), variables declared via (let (<decl1> ...) <body>) are only visible inside <body>. So, your pattern of (let <decls1> <body1>) (let <decls2> <body2>) ... doesn't work, since none of the definitions will "survive" to be seen in other scopes.

So, we should write something like this:

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...))
         (cbrt-iter (lambda ...)))
     (cbrt-iter 1.0 0.0)))

Now, at least, the call to cbrt-iter can see the definition of cbrt-iter.

But there's still a problem. When we evaluate (cbrt-iter 1.0 0.0), we evaluate the body of cbrt-iter where guess and prev-guess take the values 1.0 and 0.0. But, in the body of cbrt-iter, the variables improve and good-enough? aren't in scope.

You might be tempted to use nested lets, which is often a good choice:

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...)))
     (let ((cbrt-iter (lambda ...)))
       (cbrt-iter 1.0 0.0))))

The problem is that cbrt-iter needs to call itself, but it's not in scope until the body of the inner let!

The solution here is to use letrec, which is like let but makes the new bindings visible inside all the declarations as well as the body:

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...)))
     (letrec ((cbrt-iter (lambda ...)))
       (cbrt-iter 1.0 0.0))))

We can even use letrec to create mutually recursive procedures, just as we could with define.

Unfortunately, it would take me some time to explain how letrec and define actually work, but here's the secret: they both use mutation internally to create circularity in the environment data structure, allowing recursion. (There is also a way to create recursion using only lambda, called the Y combinator, but it's rather convoluted and inefficient.)

Luckily, all these secrets will be revealed in Chapter 3 and Chapter 4!

For another perspective, you might take a look at Brown University's online PL class, which basically goes straight to this topic (although it omits define), but I find that SICP is better at forcing you to understand the sometimes complex environment structures that are created.

Defining multiple local functions with “let over lambda” form in Scheme

1 Answers