Re: Are Associative Arrays unique to Perl?

[SNOBOL4 tables - associative arrays - implemented as linear lists]
This is true for the original implementation, usually known these days
as MAINBOL. The reason for it is historical: Tables were added to
SNOBOL4 relatively late. The SNOBOL4 "virtual machine" (a language
called SIL) already had support for a notion of "pair blocks" - linear
lists of descriptors (the fundamental SIL "word") in which the pairs of
successive descriptors - designated A and B descriptors - where
"associated" in some way. Originally, these were used to maintain a few
simple association lists. For example, SNOBOL4 has a concept of
"keywords" - certain names, when acted on by the "&" operator, provide
access to internal quantities. A pair block mapped keyword names to the
internal routines that implemented them. SNOBOL4 used "associated
variables" for I/O - read from INPUT and you get the next input "card";
assign to OUTPUT, and the value assigned gets written. I/O associations
were maintained in pair blocks.


SIL had a pair of operations, something like LOCAD and LOCBD, which did
a "locate by A (B) descriptor" - i.e., walk the pair block, looking for
a match in either the A or B field to a given value. There was also, as
I recall, an operation to add a new pair to a pair block, automatically
relocating it to a larger block of memory if necessary. Pair blocks in
the original implementation were all small, and the search, while
linear, was done within the implementation, not by the interpreter, so
didn't contribute much cost.


Given the availability of this implementation, one could very quickly
implement TABLE's using pair blocks. It's interesting that SNOBOL4 did
*not* provide the ability to find the key, given the value - a simple
use of LOCBD in place of LOCAD. I suspect this was done because the
implementors expected to replace the pair-block implementation with
something faster *eventually*; but it never happened. All subsequent
implementations of SNOBOL have used hash tables or some other such data
structure to implementation TABLE's. (Of course, in such an
implementation, reversing the lookup to find the value rather than the
key would be quite expensive.)


It's probably also true that few "naturally occurring" SNOBOL4 programs
were likely to find that even the "dumb" implementation of TABLE's was
the limiting factor in their performance.
-- Jerry
--

Return to the comp.compilers page.
Search the comp.compilers archives again.