CODEWITHSUNDEEP
lambdascopeschemeracketr5rs
wecing
wecing

Reputation: 534

How does lambda deal with unbound variables inside its body in scheme?

In this code snippet:

(begin
  (define f '())
  ((lambda ()
     (set! f (lambda (x) (g x 5)))))
  (define (g x y) (+ x y))
  (f 5))

when (set! f (lambda...)) is evaluated, the variable g is not bound to any location. As the spec for R5RS (link here) says:

The environment in effect when the lambda expression was evaluated is remembered as part of the procedure. When the procedure is later called with some actual arguments, the environment in which the lambda expression was evaluated will be extended by binding the variables in the formal argument list to fresh locations, the corresponding actual argument values will be stored in those locations, and the expressions in the body of the lambda expression will be evaluated sequentially in the extended environment.

where "the environment in effect" at one point is defined as:

An identifier that names a location is called a variable and is said to be bound to that location. The set of all visible bindings in effect at some point in a program is known as the environment in effect at that point.

so the inner lambda should only capture an environment like {f: (location #1)}; and when it is evaluated by calling (f 5) the environment used to evaluate its body should be {f: (location #1), x: (location #2)} which does not contain g.

but DrRacket (and also petite, which is a R6RS implementation) gives 10 on evaluating the above snippet. so the environment does contain g. why?

=====

It seems that scheme requires define statements to appear only at the beginning of <body>. But this code snippet returns 10 as well:

(begin
  (define (f x) (g x 5))
  (define (g x y) (+ x y))
  (f 5))

Upvotes: 0

Views: 499

Answers (2)

Rich Stewart
Rich Stewart

Reputation: 71

So, the R5RS therefore means that

(begin
   (define f '())
   ((lambda () (set! f (lambda (x) (g x 5))) ) )
   (define (g x y) (+ x y))
   (f 5) )

means the same thing as

(letrec
    ((f '())
     (g +)
     (x x)
     (y y) )
 (f 5) )

or, more simply

(let*
    ((g +)
     (f (lambda (x) (g x 5)) ) )
  (f 5) )

In my (limited) experience, it has always been much clearer to program with the the "let" binding forms (let, let*, letrec) in the first place, and avoid set! as much as possible. When I do that, I find my programs are much easier to understand, especially when I come back to look at them months later!

Upvotes: 1

wecing
wecing

Reputation: 534

I think I figured out the reason.

R5RS says:

A <body> containing internal definitions can always be converted into
a completely equivalent letrec expression

where letrec is described as:

The <variable>s are bound to fresh locations holding undefined values,
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 for top-level definitions:

Some implementations of Scheme use an initial environment in which all possible variables are bound to locations, most of which contain undefined values. Top level definitions in such an implementation are truly equivalent to assignments.

So that behavior is acceptable.

Upvotes: 1

Related Questions