Subject: Re: bindings, still confused
From: (Rob Warnock)
Date: 2000/08/21
Newsgroups: comp.lang.scheme
Message-ID: <8nqktc$iq7jo$>
Jacob J. A. Koot <> wrote:
| ... I rephrase my question: consider:
| (define counter (let ((n 0)) (lambda () (begin (set! n (add1 n)) n))))
| Does set! modify the closure, or more precisely, does it change the value
| of symbol "counter"?

No, not at all:

	> (define (make-counter)
	    (let ((n 0))
	      (lambda ()
		(set! n (add1 n))
	> (define counter (make-counter))
	> (define old-counter counter)
	> (counter)
	> (eq? counter old-counter)
But it *does* change the value of the location that "n" is bound to
in the environment of the closure, and therefore it *does* "change"
the closure with respect to "procedure equality" with other closures
constructed similarly. E.g.:

	> (define counter-a (make-counter))
	> (define counter-b (make-counter))
	> (eqv? counter-a counter-b)

That is the correct answer, because the internal state allows the two
procedures to "behave differently":

	> (begin (counter-a) (counter-a) (counter-a))
	> (begin (counter-b) (counter-b))
	> (let ((a (counter-a))
		(b (counter-b)))
	    (list a b (eqv? a b)))
	(4 3 #f)

and thus they must *not* compare "eqv?".

In <URL:>
"6.1 Equivalence predicates", R5RS states this quite specifically, with
an example very similar to the above, and also shows a similar pair
of procedures [generated by "gen-loser", q.v.] which, while they have
internal state, are allowed [but not required, note] to compare "eqv?"
since the internal state cannot *ever* be observed!

| On page 182 it is argued, I quote, "Using set-box! changes the contents
| of a box, but the table remains the same". A box pretty much looks like
| the above counter.


| set! does not change the closure. There is my confusion: assuming that set!
| does not modify the counter, we consistently deduce that set! indeed does
| not change the closure. This is a circular argument.

Ah... Perhaps this is your problem: True, "set!" does not modify "the
closure" (which includes its environment), but it certainly *does* modify
the *contents* of a certain *location* which an element of the environment
is bound to. That is, "(set! n {whatever})" does not modify "n", nor does
it modify the binding of "n" to some (otherwise anonymous) location [which
binding occurred during the execution of the "lambda" which created the
closure], but it *does* modify the *contents* of that location. And that
new content is what you'll get the next time you reference "n". (See below.)

| ...the assumption that set! does not change the closure, seems to me
| to be an axiom...

No, because you're putting too much emphasis on the term "the closure".
No circular logic or assumptions or "axioms" are needed at all.

"(set! n {whatever})" does *not* change the closure itself (which is simply
the body of the "lambda" that created it together with the environment --
a set of bindings -- that was in force at the time of execution of the
"lambda"), but it certainly *does* change the contents of *locations*
bound in that environment, and thus can [or in this case, does] change
the external *behavior* of the closure... *WITHOUT* changing its "identity".

See <>
"3.1 Variables, syntactic keywords, and regions" for the precise language
of the standard (which I may be slightly mangling above *and* below with
my edits):

	An identifier may name ... a location where a value can be stored.
	... 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. The value stored in the location to which a
	variable is bound is called the variable's value. ...

	Certain expression types ... create new locations and bind variables
	to those locations. These expression types are called binding

[Note: Both "let" and procedure call (application) are binding constructs.]

	... To each place where an identifier is bound in a program there
	corresponds a region of the program text within which the binding
	is visible. The region is determined by the particular binding
	construct that establishes the binding; if the binding is established
	by a lambda expression, for example, then its region is the entire
	lambda expression. Every mention of an identifier refers to the
	binding of the identifier that established the innermost of the
	regions containing the use.

And you should also look at:

    "3.4 Storage model"
	Variables and objects... implicitly denote locations...
	A new value may be stored into one of these locations using 
	[the "set!" form or some "XXX-set!" procedure] but the [variables
	or object] continues to denote the same locations as before.

    "4.1.4 Procedures"
	A lambda expression evaluates to a procedure. The environment in
	effect when the lambda expression was evaluated is remembered as
	part of the procedure.

    "4.1.6 Assignments"

So back to what I was saying. A "let" or "lambda" binds variables to
(new) locations, and these bindings become part of (or extend) the current
environment. Executing the "lambda" form, in addition, "captures" that
extended environment and stores it and some piece of code (the body of the
lambda) into an object called a "closure". *NOTHING* you can do after that
can "change" that closure -- it's immutable, unalterable, indestructible
(except by being garbage-collected, and that's not observable anyway).

But you *can* change the values of the locations to which variables in
the environment of the closure are bound [that is, provided that the
the body of the lambda contains code which does that].

| That's what made me think of closures whose internal state cannot be
| changed without being changed themselves.

"Internal state" != "closure itself". To think otherwise is a mistake.

| for it implies that changing the value of a symbol, may affect the values of
| other symbols too.

Symbols don't have values[*]; neither do variables per se; only the
*locations* to which variables are bound have values. Yes, you get at
these values by writing the identifier (symbol) for a variable as an
expression, but what you get is the value of the *location* to which
the variable is bound:

    "4.1.1 Variable references"

[*] In the sense you meant. Of course, when quoted, symbols *are* literal
    values, but that's not what you meant.

| Assuming that set! does change the closure

It doesn't. Closures are immutable.

| demanding that assigning a new value to a symbol

You can't assign a value to a symbol, only to the location to which
the variable represented by that symbol (identifier) is bound in the
current environment.

| may imply that repeated applications of the closure return the same value!

Nope. (See above.)

| There are ways out

Yes, read the standard.

| I also find it useful to consider a counter in *austere* oop: the
| object either returns its state without modifying it, or it returns
| a *new* object containing the new state.

But that's not Scheme. In Scheme, "set!" mutates the values of
locations; it does not mutate the "identity"[**] of the location.


[**] Note however that there is no way whatsoever from within Scheme
to "get at" the identity of a location. Even "eq?" only works on *values*,
which are the *contents* of locations, not on locations themselves.
Locations are completely anonymous. (And a good thing, too, for if
they *weren't*, "copying" garbage collectors couldn't work!)

Rob Warnock, 41L-955
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043