Subject: Re: Environment model of evaluation [was: Re: The Scheme FAQ]
From: rpw3@rigden.engr.sgi.com (Rob Warnock)
Date: 10 Aug 2001 04:54:38 GMT
Newsgroups: comp.lang.scheme
Message-ID: <9kvpee$a54u4$1@fido.engr.sgi.com>
Bill Richter  <richter@poincare.math.northwestern.edu> wrote:
+---------------
| But I'm not convinced that I have to believe that (cons 1 2) returns a
| pointer to a pair of pointers to 1 & 2.
| I'm willing to believe that the extra layer of pointers is useful.
| Tell me why or if I'm forced to believe in it.
+---------------

You're not. It's a *verbal convenience*, not a requirement of Scheme.

Here, let's finesse this whole discussion by immediately ceasing to use
the term "pointer" entirely, and instead use the term "object designator"[*],
or more briefly (when the "object" context is obvious), just "designator".

Now, what do we want to be true of such designators to make them less
confusing to talk about than "pointers"? I would claim basically just
the following:

1. That the "values" referred to in the Scheme standard, that is, those
   things which are stored in variables and stored in other objects such
   as pairs & vectors [and boxes & structures & class/object slots, for
   those implementations which have such extensions] and passed "by-value"
   in procedure calls and returned as the values of procedures are exactly
   such designators, and nothing else.

2. For any particulary implementation of the language, that their
   underlying representation in the physical machine is a fixed size[**]
   regardless of the type of the Scheme object being designated.

That is, that from the Scheme programmer's point of view at least,
"Everything is a designator."

So (cons 1 2) returns a single designator of a fresh-allocated [as required
by R5RS] object of type pair, whose contents are in turn two designators,
one for the number 1 (an object of type number) and another designator for
the number 2 (also an object of type number).

At this point, you don't know AND SHOULDN'T CARE whether such a designator
is or contains a pointer or "sort of but not quite looks like" a pointer
or *sometimes* is a pointer and sometimes isn't (i.e., may consist of an
immediately-encoded respresentation of the object, for certain objects but
not others) or is -- as in some versions of Smalltalk -- simply a small
integer which indexes into the system object array!!! You shouldn't care.

And indeed, you must *not* care, since different implementations may
make different choices for what an object designator "is", and yet all
of them (barring bugs) implement the correct semantics of Scheme.

So.  Having followed all this (which I sincerely hope), I will now ask
you to take one further step, namely:  When anyone in a Scheme (or Lisp)
discussion uses the word "pointer" [at least when speaking of what a
Scheme programmer sees], would you please simply silently translate
that "p" word to "object designator"? You'll feel ever so much happier,
and yet you won't misinterpret anything in what they're trying to say.

In particular, when someone says that in Scheme (or Lisp), "Everything
is a pointer", just hear "Everything is a designator", and you'll be fine.


-Rob

[*] Picked more-or-less out of the air, not because I know of any
    literature which uses it consistently this way. But I think it
    serves well enough.

[**] Which is *probably* the size of one machine word capable of holding
    a maximum-length machine address for the ABI in use (that is, 32 bits
    on SGI Irix for programs compiled "-n32" but 64 bits for "-64"), though
    I know of at least one implementation of Scheme [Elk 3.0] for which an
    object designator was two such words. Still, the size of a designator
    should be small enough that subroutine calls/returns using them is
    reasonably efficient, and usually that means that they're exactly
    one word (though possibly a "long" one).

    And I know of at least one other implementation, SIOD, for which
    all numbers are C "double"s, and thus the designators for numbers
    are indeed pointers... but for efficiency the implementation
    pre-allocates a certain range of number objects (adjustable, but
    typically [-100..1000]) and requires that all primitive arithmetic
    operations check and use those pre-allocated objects for numerical
    results in that range, so that things like (cons (- 3 2) (/ 10 5))
    *won't* have to allocate anything [except the cons pair, of course].

-----
Rob Warnock, 30-3-510		<rpw3@sgi.com>
SGI Network Engineering		<http://reality.sgi.com/rpw3/> [until 8/15]
1600 Amphitheatre Pkwy.		Phone: 650-933-1673
Mountain View, CA  94043	PP-ASEL-IA