How is "letrec" implemented without using "set!"?

Question

How can letrec be implemented without using set!?

It seems to me that set! is an imperative programming construct, and that by using it, one loses the benefits of functional programming.

Nb

Answer 1

I know usually we ask content to be copied but there is no short answer to your question. http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Lobachevsky

The Dybvig et al. paper is a good one. There's also a nice discussion on Lambda the Ultimate from a few years ago about implementing letrec in terms of lambda. (Having said all that, I agree with sacundim's comment that "just because a functional feature is implemented with imperative code behind the scenes, that doesn't make the feature imperative".) – Rodd

Answer 2

No. Just because a functional feature is implemented with imperative code behind the scenes, that doesn't make the feature be imperative. Our computing machines are all imperative; so at some point all functional code must be implemented by translation into imperative code!

The key thing to understand here is this: functional programming pertains to interface, not to implementation. A piece of code is functional if that code itself is unable to observe any side effects—even if side effects are in fact happening behind the scenes. I.e., if you check the value of the same binding of the same variable multiple times, you will get the same value—even if that value, behind the scenes, was put there by a use of set!.

In the case of letrec, there is a little catch here: the result is undefined if the evaluation of any of the bindings in the letrec causes another one to be derefenced. So, the result of this code is undefined:

(letrec ((foo bar)
         (bar 7))
  (cons foo bar))

The value of foo in the body of the letrec is undefined. The result of the following, on the other hand, is defined:

(letrec ((foo (lambda () bar))
         (bar 7))
  (cons (foo) bar))

This is because evaluating the lambda captures the reference to bar, but the actual value is not looked up until the closure is executed in the body.

Andrien