Subject: Re: Are shared-structure mutations actually important?
From: (Rob Warnock)
Date: Wed, 19 Nov 2008 22:02:06 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
Kaz Kylheku  <> wrote:
| ["Followup-To:" header set to comp.lang.lisp.]
| Rob Warnock <> wrote:
| > In Lisp, variables per se are never mutated:
| A variable is by definition a named quantity which can be muteted.

Whose "definition"? ;-}  ;-}  Seriously, it varies. I was trying to
make a distinction between C-like languages and Lisp-family languages,
but even within the latter it varies [and note that Ray Dillinger tends
to be more of a Schemer than a Lisper, so that matters].

CLHS says this (which is not as precise about the semantics as it
might be IMHO):

    variable n. a binding in the ``variable'' namespace.
                See Section (Symbols as Forms).

    binding n. an association between a name and that which the name
               denotes. ``A lexical binding is a lexical association
               between a name and its value.'' When the term binding is
               qualified by the name of a namespace, such as ``variable''
               or ``function,'' it restricts the binding to the indicated
               namespace, as in: ``let establishes variable bindings.''
               or ``let establishes bindings of variables.''

    mutate v.  [Not defined]

    3.1.1 Introduction to Environments
    A binding is an association between a name and that which the
    name denotes. Bindings are established in a lexical environment
    or a dynamic environment by particular special operators.
    A single name can simultaneously have more than one associated
    binding per environment, but can have only one associated binding
    per namespace. Symbols as Forms
    A variable can store one object. The main operations on a
    variable are to read[1] and to write[1] its value.
    Non-constant variables can be assigned by using setq or bound[3]
    by using let.

    assign v.t. (a variable) to change the value of the variable in
	       a binding that has already been established.
	       See the special operator setq.

    write v.t. 1. (a binding or slot or component) to change the value
	       of the binding or slot.

Note already some confusion appearing between "assigning...the value
of the variable" "changing the value of the binding".

Scheme (well, R5RS) makes it a bit more clear (maybe):

    3.1 Variables, syntactic keywords, and regions
    An identifier may name a type of syntax, or it 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. By abuse of terminology, the variable 
    is sometimes said to name the value or to be bound to the value.
    This is not quite accurate, but confusion rarely results from this

Except in this thread, apparently!  ;-}

I was trying to *not* abuse the terminology, but seem to have failed.
Let me try again following the Scheme terminology more closely. The
main point I was trying to make when I said "In Lisp, variables per se
are never mutated" was that *which* location a variable is bound to is
never changed during the life of that variable [modulo copying GC issues!].

And when I said "A variable *binding* may be mutated to refer to another
object" I simply meant that the value stored *in* a binding's location
*can* be changed.

NOTA BENE: In neither Scheme not Lisp can the programmer get any
"handle" on the location to which a variable is bound other than
via the variable itself. That is, the "address" of the location is
always implicit and inaccessible [which is why copying GC works].

| > 1. A variable *binding* may be mutated to refer to another object
| >    [e.g., as with a simple SETQ].
| Mutating a binding means modifying the environment so that a name which
| refers to a memory location now refers to a different memory location.

I disagree. You're talking about *extending* the environment, perhaps,
creating a *new* binding that *shadows* a previous binding, but that
does *not* mutate the previous binding, which still refers to the
same (previous) location. Bindings themselves are immutable once

| This isn't what happens when we store a new value in a variable.
| The binding stays the same.

(*sigh*) I guess it depends on what you mean by the "binding"
and by "mutation of a binding". I was using "binding" to mean
the association between a variable (an identifier in some visible
variable environment) and the location to which it is bound.
By "mutation of the binding" I -- imprecisely, confusingly,
perhaps -- meant changing the contents of the location to which
the variable is bound. I probably should have said "mutation of
the binding's value".

| > 2. The *object* a variable is currently bound to may be mutated
| A variable isn't bound to a value. A variable is a binding between
| a symbol and a memory location, according to some environment.
| The variable stores the object by means of this bound memory location.

Exactly, with the caveat that the object isn't necessarily *in* the
bound memory location, but is only *denoted* by it! Which is the only
way that two different bindings could denote "the same" object.

Note: Yes, this "denotation" smells suspiciously like what is called
a "pointer" in other languages, and *would* be a pointer except that
there is no way within Scheme/Lisp to get a handle on either it *or*
the bound location in which it resides.

See if you can agree with this version of my previous points #1 & #2:

1. Once established, a variable binding [the association between an
   identifier and a memory location, according to some environment]
   cannot be changed [though it can be shadowed, by extending that

2. Assigning to a variable (or equivalently, to a binding) changes
   which object is denoted by the memory location of the binding.

And now we should add a third:

3. "The same" object may be denoted simultaneously by multiple
   distinct variable bindings.

And perhaps even a fourth, for implementers only:  ;-}

4. Immutable objects may be freely copied and/or represented as
   "immediate" denotations provided that there is no way within
   the language to tell that such copying has been done; i.e.,
   that such copies are in all respects "the same" as the objects
   copied from.


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607