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
– karmakaze, Commented May 30, 2019 at 19:23

Fixnum · Accepted Answer · 2012-10-31 02:04:06Z

2

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.

edited Oct 31, 2012 at 2:04

answered Oct 31, 2012 at 1:33

Fixnum

1,8621 gold badge14 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

dtg Over a year ago

You mentioned the Y-combinator - I remember seeing this in the Little Schemer book using the looping combinator (i.e. (lambda (x) x x)). Just to be clear - this is not how define is actually implemented?

Fixnum Over a year ago

No! The define form adds a binding to the current environment, and the letrec form extends the environment with your new variable bound to an undefined value, then sets the value to the value you specified. These both use mutation (i.e., aren't purely functional) under the hood, but are far more sensible for practical programming than using the Y combinator.

newacct Over a year ago

Scheme actually defines internal defines to be completely equivalent to letrec (in R5RS, schemers.org/Documents/Standards/R5RS/HTML/…) or letrec* (in R6RS, r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.3)

dtg Over a year ago

Thank you for the information. I will get some more practice using the letrec form.

Collectives™ on Stack Overflow

Defining multiple local functions with "let over lambda" form in Scheme

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related