Re: S&I's idea of EQ? (long)

[Kent Dybvig <dyb@indiana>]

The cost of closing in the very case you describe is indeed large
in Chez Scheme, as in most later Scheme systems.  Compared with other
costs, the cost of allocation in general is quite high.  Allocation
incurs several direct and indirect costs including (1) the several
instructions to do the allocation, (2) the potential for page faults,
and ultimately (3) garbage collection overhead.  By comparison, all
identifier lookups, whether global, local, or through the closure,
are one instruction (more correctly, one operand of an instruction).
Function call is only a few instructions after pushing the arguments.
Very little allocation is performed by the system, and that is why it
ends up being so fast.  In fact, the only things ever allocated are
closures for lambda expressions that are not directly invoked, boxes
for assigned identifiers, and stack objects for continuations.  Many
programs do no allocation at all and most do little outside explicit
calls to cons and the like.

Chez Scheme always returns the same closure for a lambda with no free
variables, thereby avoiding even the cost of a cons.  When this closure
occurs in a loop, the savings in page faults alone is significant.

However, I do not feel that this emphasis on speed is more important
than emphasis on functionality.  In light of the discussion about using
closures as abstract objects and what I feel to be cleanest, my belated
answer to Jonathan's EQ-Quiz is as follows (no coalescing, no splitting):

T    (eq? (lambda (x) x) (lambda (y) y))
T    (eqv? (lambda (x) x) (lambda (y) y))
T    (let ((x (lambda (z) z))) (eq? x x))
T    (let ((x (lambda (z) z))) (eqv? x x))
T    (let ((x ... any expression evaluating to an exact number ...))
       (eq? x x))
I    (eq? #\x #\x)

I am all in favor of having switches in the system that trade functionality
(flexibility, anyway) for speed, as long as the users knows pretty much
what's going on.  The user can decide if the extra speed is worth the price.
And, as you point out, it is perfectly valid even in the absense of such
a switch for the compiler to do anything it cannot be caught at, including
coalescing or splitting objects.

If anyone cares, I can write a less coherent response related to EQ on
non Von-Neumann architectures, such as the cellular computer of Mago,
where pointers do not exist.  (The earlier remarks about MultiLisp are
relevant only to large-grain architecture, which are essentially parallel
variants of the Von-Neumann architecture.)  My ideas for EQ along these
lines are not completely formed but relate to immedidate (pointer-encoded)
objects also.

Question:  On a machine supporting virtual memory, If EQ is based on the
(virtual) address, what if two pieces of the virtual address space are
mapped to the same physical address?