[plt-scheme] Semantics of let

On Thu, 23 Feb 2006, Greg Woodhouse wrote:

> > (run)
> >> (let ((f (lambda (x) (if (= x 0) 1 (* x (f (- x 1))))))) (f 3))
> 6

Hi Greg,

The lambda's closure here should NOT contain a binding for f.  That's the
job of the separate 'letrec' form.


> What I do is maintain a list of "frames" (actually hash tables), and
> with each let, I add a new frame to the front of the list and add the
> binging there. When looking up a value, I start at the head of the list,
> and go on to the next frame if I don't find a binding.

Sounds ok so far: so you have a chained set of environment frames.


> Similarly, to apply a lambda expression, I create a new frame and enter
> bindings for the formals and evaluate the body.

Ah.  Let's stop at this point.

>From what environment are you chaining that new frame to?  Be careful
here: the difference between chaining to the current dynamic environment
vs the the one that is captured in the lambda closure makes all the
difference between dynamic vs lexical scope.

Without seeing any more code, I think the most likely explanation is that
you've just implemented dynamic scope, which lets your recursive
definitions work.  Shriram's notes on this in Chapter Five of PLAI cover
this problem and approaches to attack it.

I might be misremembing, but I think the book "Essentials of Programming
Languages" also mentioned that this mistake very prevalent among early
Lisp implementations because it made recursive functions "work" for many
common cases without one having to worry about properly implementing
lexical scope.

So if this is the mistake you've made --- implementing dynamic scope ---
at least be comforted that you're not the first one to do so.  *grin*