schemeevaluationletletrec

Why does let not allow mutually recursive definitions, whereas letrec can?

I suspect that I fundamentally misunderstand Scheme's evaluation rules. What is it about the way that let and letrec are coded and evaluated that makes letrec able to accept mutually recursive definitions whereas let cannot? Appeals to their basic lambda forms may be helpful.

Solution

  • let can't create mutually-recursive functions in any obvious way because you can always turn let into lambda:

    (let ((x 1))
  ...)
-->
((λ (x)
   ...)
 1)

    and similarly for more than one binding:

    (let ((x 1)
      (y 2))
  ...)
-->
((λ (x y)
   ...)
 1 2)

    Here and below, --> means 'can be translated into' or even 'could be macroexpanded into'.

    OK, so now consider the case where the x and y are functions:

    (let ((x (λ (...) ...))
      (y (λ (...) ...)))
  ...)
-->
((λ (x y)
   ...)
 (λ (...) ...)
 (λ (...) ...))

    And now it's becoming fairly clear why this can't work for recursive functions:

    (let ((x (λ (...) ... (y ...) ...))
      (y (λ (...) ... (x ...) ...)))
  ...)
-->
((λ (x y)
   ...)
 (λ (...) (y ...) ...)
 (λ (...) (x ...) ...))

    Well, let's make this more concrete to see what goes wrong: let's consider a single recursive function: if there's a problem with that then there certainly will be problems with sets of mutually recursive functions.

    (let ((factorial (λ (n)
                   (if (= n 1) 1
                       (* n (factorial (- n 1)))))))
  (factorial 10))
-->
((λ (factorial)
   (factorial 10))
 (λ (n)
   (if (= n 1) 1
       (* n (factorial (- n 1))))))

    OK, what happens when you try to evaluate the form? We can use the environment model as described in SICP . In particular consider evaluating this form in an environment, e, in which there is no binding for factorial. Here's the form:

    ((λ (factorial)
   (factorial 10))
 (λ (n)
   (if (= n 1) 1
       (* n (factorial (- n 1))))))

    Well, this is just a function application with a single argument, so to evaluate this you simply evaluate, in some order, the function form and its argument.

    Start with the function form:

    (λ (factorial)
  (factorial 10))

    This just evaluates to a function which, when called, will:

    1. create an environment e' which extends e with a binding of factorial to the argument of the function;
    2. call whatever is bound to factorial with the argument 10 and return the result.

    So now we have to evaluate the argument, again in the environment e:

    (λ (n)
  (if (= n 1) 1
      (* n (factorial (- n 1)))))

    This evaluates to a function of one argument which, when called, will:

    1. establish an environment e'' which extends e with a binding of n to the argument of the function;
    2. if the argument isn't 1, will try to call some function bound to a variable called factorial, looking up this binding in e''.

    Hold on: what function? There is no binding of factorial in e, and e'' extends e (in particular, e'' does not extend e'), but by adding a binding of n, not factorial. Thus there is no binding of factorial in e''. So this function is an error: you will either get an error when it's evaluated or you'll get an error when it's called, depending on how smart the implementation is.

    Instead, you need to do something like this to make this work:

    (let ((factorial (λ (n) (error "bad doom"))))
  (set! factorial
        (λ (n)
          (if (= n 1) 1
              (* n (factorial (- n 1))))))
  (factorial 10))
-->
((λ (factorial)
   (set! factorial
         (λ (n)
           (if (= n 1) 1
               (* n (factorial (- n 1))))))
   (factorial 10))
 (λ (n) (error "bad doom")))

    This will now work. Again, it's a function application, but this time all the action happens in the function:

    (λ (factorial)
  (set! factorial
        (λ (n)
          (if (= n 1) 1
              (* n (factorial (- n 1))))))
  (factorial 10))

    So, evaluating this in e results in a function which, when called will:

    1. create an environment e', extending e, in which there is a binding of factorial to whatever its argument is;
    2. mutate the binding of factorial in e', assigning a different value to it;
    3. call the value of factorial in e', with argument 10, returning the result.

    So the interesting step is (2): the new value of factorial is the value of this form, evaluated in e':

    (λ (n)
  (if (= n 1) 1
      (* n (factorial (- n 1)))

    Well, this again is a function which, when called, will:

    1. create an environent, e'', which extends e' (NOTE!) with a binding for n;
    2. if the value of the binding of n is not 1, call whatever is bound to factorial in the e'' environment.

    And now this will work, because there is a binding of factorial in e'', because, now, e'' extends e' and there is a binding of factorial in e'. And, further, by the time the function is called, e' will have been mutated so that the binding is the correct one: it's the function itself.

    And this is in fact more-or-less how letrec is defined. In a form like

    (letrec ((a <f1>)
         (b <f2>))
  ...)

    First the variables, a and b are bound to some undefined values (it is an error ever to refer to these values). Then <f1> and <f2> are evaluated in some order, in the resulting environment (this evaluation should not refer to the values that a and b have at that point), and the results of these evaluations are assigned to a and b respectively, mutating their bindings and finally the body is evaluated in the resulting environment.

    See for instance R6RS (other reports are similar but harder to refer to as most of them are PDF):

    The <variable>s are bound to fresh locations, the <init>s are evaluated in the resulting environment (in some unspecified order), each <variable> is assigned to the result of the corresponding <init>, the <body> is evaluated in the resulting environment, and the values of the last expression in <body> are returned. Each binding of a <variable> has the entire letrec expression as its region, making it possible to define mutually recursive procedures.

    This is obviously something similar to what define must do, and in fact I think it's clear that, for internal define at least, you can always turn define into letrec:

    (define (outer a)
  (define (inner b)
    ...)
  ...)
-->
(define (outer a)
  (letrec ((inner (λ (b) ...)))
    ...))

    And perhaps this is the same as

    (letrec ((outer
          (λ (a)
            (letrec ((inner
                      (λ (b)
                        ...)))
              ...)))))

    But I am not sure.

    Of course, letrec buys you no computational power (neither does define): you can define recursive functions without it, it's just less convenient:

    (let ((facter
       (λ (c n)
         (if (= n 1)
             1
             (* n (c c (- n 1)))))))
  (let ((factorial
         (λ (n)
           (facter facter n))))
    (factorial 10)))

    or, for the pure of heart:

    ((λ (facter)
   ((λ (factorial)
      (factorial 10))
    (λ (n)
      (facter facter n))))
 (λ (c n)
   (if (= n 1)
       1
       (* n (c c (- n 1))))))

    This is pretty close to the U combinator, or I always think it is.

    Finally, it's reasonably easy to write a quick-and-dirty letrec as a macro. Here's one called labels (see the comments to this answer):

    (define-syntax labels
  (syntax-rules ()
    [(_ ((var init) ...) form ...)
     (let ((var (λ x (error "bad doom"))) ...)
       (set! var init) ...
       form ...)]))

    This will work for conforming uses, but it can't make referring to the initial bindings of the variables is an error: calling them is, but they can leak out. Racket, for instance, does some magic which makes this be an error.