Re: S&I's idea of EQ?

[willc%tekchips%tektronix.csnet@CSNET-RELAY.ARPA]

JINX's messages have helped, but I still do not understand three of
his points:

> By first class environments I do not mean that they can be passed
> around, but that they can be manipulated.  What's the use if they can
> only be passed around?

As numbers demonstrate, it is both possible and useful to manipulate
objects without side effecting them.  As I recall, S&ICP uses only
the make-environment and eval operations on environments, neither of
which mutates an environment.  I can imagine many other
non-side-effecting operations on environments, such as:

    (lookup env id)
    (extend env1 env2)
    (bind-to-fresh-location env id)
    (hide env id)

Someone might want to argue that these operations would be more useful
if they had an exclamation point in their names, but it would take a
real argument; the non-side-effecting versions shouldn't be dismissed
out of hand.

> A cons in MIT-Scheme consists of 4 (move) instructions in compiled
> code (without garbage collection).

It would be wonderful if compiled code could be made to run without
garbage collection.  As Kent Dybvig, David Bartley, and I have pointed
out, a cons is usually more expensive in gc time than in allocation time.

When last I heard, MIT Scheme on the HP 9836 was using a simple stop and
copy collector with essentially the same performance as the one in Scheme
312--that is, on a 12 MHz 68000 without wait states the garbage collector
will run for 3 to 4 seconds per megabyte of live storage.  If the heap is
at equilibrium (i.e., storage is being dropped as fast as it is being
allocated) and the active semispace is half full, then the cost of
allocating 8 bytes of storage cannot be less than 24 to 32 microseconds,
no matter how few instructions are used to allocate the storage.  It
follows that if a variable reference takes 1 microsecond, then creating
a closure is about 25 times as expensive as a variable reference.  If
the active semispace is 75% full, then creating a closure is 75 times
as expensive as a variable reference.

The HP 9836 does not support virtual memory.  Caching or paging would
make consing significantly more expensive than the above calculations
indicate.

The only way to escape from these calculations is to use a more
sophisticated garbage collection algorithm such as the Hewitt-Lieberman
algorithm (or its little brother, generation scavenging).  The worst case
behavior of these algorithms appears to be slightly worse than that of
straight stop and copy, so it is an empirical question how they will
behave in a real Lisp environment.  The only data that I have seen appears
in a 1984 paper by David Moon; he found that the cost of consing was
reduced but remained very significant.  Clearly there is still a shortage
of good data.  If MIT Scheme has changed to use a more sophisticated
collector, then I hope someone will post numbers characterizing its
performance.

>                                                       ...once we
> have accepted that there is no splitting, it seems that the only
> consistent model left is the one that requires every "evaluation" of a
> lambda expression to be consed....Either procedures have associated
> locations or they do not.  

A few months ago I proposed the following consistent semantics:  if eq?
is given procedures as arguments, it returns #!true if the associated
locations are the same.  If the associated locations are different but
the "functional parts" (E* --> K --> C) are equal, then eq? may return
#!true or #!false at its whim.  If the functional parts are not equal,
then eq? must return #!false.

Whether the functional parts are equal is of course noncomputable, but
a semantics doesn't have to be computable.  The fact that eq? can just
return #!false if the associated locations are unequal proves the
existence of a model for this semantics.  The possibility of coalescing
optimizations as performed by compilers like Rabbit and the T3 compiler
prove the existence of other interesting and useful models for this
semantics.

Peace, Will