Path: utzoo!attcan!uunet!cs.utexas.edu!rutgers!uwvax!tank!uxc!uxc.cso.uiuc.edu!ux1.cso.uiuc.edu!uicsrd.csrd.uiuc.edu!jaxon
From: jaxon@uicsrd.csrd.uiuc.edu
Newsgroups: comp.lang.apl
Subject: Re: Problem with )COPY
Message-ID: <49700010@uicsrd.csrd.uiuc.edu>
Date: 25 Apr 89 22:09:00 GMT
References: <575@moore.UUCP>
Lines: 50
Nf-ID: #R:moore.UUCP:575:uicsrd.csrd.uiuc.edu:49700010:000:2642
Nf-From: uicsrd.csrd.uiuc.edu!jaxon    Apr 25 17:09:00 1989


There is no  )SYMB or )SYMBOL command in the ISO standard.
There is none in Unisys'  APLB.

In general, any physically limited resource ought to be made virtual.

In APLB we made the "binding" between a name and a value be represented
by an object in the virtual workspace.  The symbol table is just a function
that maps names into bindings, and the memory used to store or compute that
function is entirely its own concern.  Now the tokenizer (and other parts 
of our incremental compiler), and the system functions that take names
as arguments lookup names in the symbol table.  BUT what they get back is
a "binding cell", not a "symbol table index".

All the usual APL computations act on these binding cells:
    Assignments directly modify the "value" component.
    References read the current "value" component.
    Localization hides the old "value" somewhere and replaces it with NIL.
    
None of these incur a symbol table lookup, and none depend upon the
arrangement or size of the symbol table.  Knuth (vol. 1) describes a few
ways to expand and contract hash tables that are now safe to use.

The only wrinkle is deciding how long a "binding cell" object must be kept
alive.  Ordinary objects can be collected when there are no more references
in the live workspace.  But the symbol table always has a reference, so it
looks alive even when it's not.  The extra cost is not very significant, and
there are many ways to keep these costs out of high frequency control paths.
Basically wherever you delete a reference that may be a "binding cell",
if the new reference count is 1, and the value is NIL, then the symbol table
can forget about the binding cell, and it can be collected.  

)ERASE does not remove a binding cell from the symbol table unless there
are no more references to that cell (e.g. in function lines).

In APLB we managed to essentially eliminate symbol-table lookup cost using
these techniques.  But we did not provide "ambivalent user functions".  In
fact we are seriously opposed to the APL2 notation for ambivalent function
templates because their scheme requires a use of #NC (Name Class), which
costs 1 symbol table lookup, to determine the valence of the current call
(something which the interpreter just figured out a microsecond ago).  If 
you add in a collection of dyadic functions that have been modified to
protect themselves from IBM's silly extension by testing #NC 'LEFT' on
each line [1], then lookups become more frequent, and the implementer has
to find a very low cost resizeable hash scheme.

Isn't anyone angry about APL2-style ambivalence?

regards - greg jaxon -
jaxon@uicsrd.uiuc.edu