Re: S&I's idea of EQ?

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

Rozas is correct that closing a lambda expression can be as cheap as
consing, and that the closure may not be necessary if the procedure
receiving it is known to the compiler.  (My example wasn't very good
for another reason as well, namely that the map procedure is going
to cons anyway.)

That's not to say that closing a lambda expression is as cheap as a
variable reference.  Consider an 8 MHz 68000 without wait states.
Assuming a stop and copy garbage collector that can traverse and copy
1 megabyte of live storage in 5 seconds, a heap at equilibrium, and a
50% load factor, it takes 5 microseconds to reclaim each byte of storage.
Hence a cons would take 40 microseconds in gc time alone.  In interpreted
Scheme 312 consing or closing takes an additional 30 microseconds in the
storage allocator; compiling would reduce that to 20 microseconds.
Overall that's 70 microseconds in interpreted code, 60 in compiled code.

A variable reference takes 12 to 30 microseconds in interpreted Scheme
312, and would take .5 to 6 microseconds in compiled code.  Thus
variable references in compiled code are an order of magnitude faster
than closing a lambda expression.

You can reduce the storage allocation and gc time by using a more
sophisticated garbage collector, but if you're going to go to the
trouble of doing that then you're probably going to use an optimizing
compiler and the average variable reference should be closer to 1
microsecond than to 6 microseconds.

If variable references are slow in MIT Scheme, I suspect the problem
lies not with environments as first class objects but with the fact
that MIT Scheme allows the environment structure to be side effected
by internal definitions that do not appear at the head of the lambda
body in which they appear.  It appears to me that the authors of S&ICP
considered such side effects to be an MIT extension to Scheme that
other implementations do not have to support; the relevant footnotes
are in chapter 1, footnote 23, page 28; in chapter 5, footnote 21, page
440; in chapter 5, footnote 40, page 487; in chapter 5, footnote 42,
page 490.

One of the problems with using an operational definition such as a
meta-circular interpreter to specify the semantics of a programming
language is that it is never clear whether a feature is incidental to
that particular interpreter or a universal feature that must be
supported by all interpreters.  It is clear, for example, that
the interpreter in chapter 4 of S&ICP creates a new closure every
time it encounters a lambda expression, but it is equally clear that
if you take the car of such a closure you get the symbol PROCEDURE.
That's why I prefer a denotational semantics.

Peace, Will