When is a identifier in a lambda bound?

Question

I am reading SICP. Something is confusing me. These are written by myself to test.

;This procedure bind a symbol `f` to a lambda, and that lambda is not evaluated.
(define f
  (lambda () x))

;create a frame which binds x to 10, and then evaluate f, should return 10.
(let ((x 10))
    (f))

But DrRacket does not accept it.

x: unbound identifier in module in: x

@sepp2k. That code is written by myself. I'm reading chapter 3.2 *The Environment Model of Evaluation*. — Zen, Dec 16 '15 at 15:29

Sylwester · Answer 1 · 2015-12-16T16:55:52.100

It's because of lexical scoping.

(define f
  (lambda () x))

Since x is not in the lexical scope it has to be a global variable. Thus you can do the following:

(define x 10)
(f) ;=> 10

To make it a lexical variable it has to already exist at creation time:

(define f
  (let ((x 10))
    (lambda () x)))

In this example, since x is a bound lexical variable the x in the lambda is the same since the lambda inherits the environment from where it's evaluated.

Yes! A lambda expression is evaluated so that it becomes a procedure object and define assignes the global symbol f to that object.

To prove that try to apply a list structure:

('(lambda (x) x) 10) ; gets error 'application: not a procedure'

In a LISP that has dynamic scoping the procedures doesn't have environments and the environment is takes from the runtime at call time:

(define (test)
  some-value)

(define (call-test)
  (let ((some-value 10))
    (test))) ; => 10

(test) ; => error (unbound variable)

As you might see with dynamic scope it's difficult to tell if a procedure is correct or not as the environment it has when called changes for each call. Lexical scoping is also much easier for a compiler to optimize.

score 1 · Answer 2 · answered Dec 16 '15 at 15:33

Scheme has lexical scoping. What this means is that when the body of a lambda is evaluated, it is evaluated using the environment from where the lambda was created, not from where it was called.

So while there exists an x variable when you call f, that does not matter because Scheme looks for a definition of x in the environment where you defined f where no such variable exists.

score 1 · Accepted Answer · edited May 23 '17 at 12:04

The problem you are seeing here is that x is a free variable. Expressions in Racket (and most languages) can not have free variables (called a "closed term")[2].

If you would have free variables, as x is in your example, you would need to call the function in an environment in which some occurence of x is bound. You achieve that by calling it in a let that binds x.

However, Scheme is lexically scoped[1], which means that it captures the variables from the environment in which it is defined. But you don't have an x defined in the scope in which your lambda is defined. Hence the error.

Some reading to enlighten this:

[1] Static vs Lexical scoping: Static (Lexical) Scoping vs Dynamic Scoping (Pseudocode)

[2] Free variables : https://en.wikipedia.org/wiki/Free_variables_and_bound_variables

When is a identifier in a lambda bound?

3 Answers3