In quite a lot of modern scripting languages (e.g. Perl, Python, Ruby, PHP, Lua, JavaScript), associative arrays are supported as a primitive or first-class data type (with various names like map, dictionary, hash, etc.) in a very convenient syntax, making convenient data-driven paradigms possible.
Which language first adopted such a design? And how has this design evolved?
I think the first language that included native support for associated arrays was SNOBOL4 (1967), calling them tables. From THE SNOBOL4 PROGRAMMING LANGUAGE (second edition):
Often it is desirable to associate a group of items with one variable name through numerical indexing or some other identifying property. The SNOBOL4 array and table provide these capabilities with more flexibility than most programming languages. An array is a data element consisting of a set of pointers to other data elements, so that each array element may be any data type, even an array. An element of an array is referenced by using an integer index. A table is similar to an array, except that the reference value need not be an integer, but can be any of several other types. Conversion can be made between tables and arrays.
…
1.13 Tables
Sets of pairs of associated data objects can be created by the use of tables. A table is similar to a one-dimensional array. However, instead of referencing an element with an integer, any data object can be used.
A table is created by the primitive function
TABLE. For exampleT TABLE ( )creates a table and assigns it as value of
T.Elements in the table can be assigned values In a manner similar to array elements.
Examples are
T<'A'> 5and
T T + 1
Tables have varying lengths and are dynamically extended if necessary. Some efficiency can be achieved by specifying an estimate of the size of a table at the time it is created.
TABLE (N)creates a table that initially has room for N entries.
MUMPS (1966) natively supports sparse multi-dimensional arrays, stored as b-trees, but I can’t really find a solid reference that explains the original design.
AWK (1977) natively supports one-dimensional sparse arrays and directly influenced Perl. PHP in turn has borrowed a lot of concepts from Perl (including associative arrays), as the first version of PHP was simply a collection of Perl scripts.
In any case, associative arrays are a fundamental and trivial data type, although implementations have certainly evolved over time, I don’t really think the design changed much.
Which language first adopted such a design? And how was this design evolved?
I don’t know if it was first, but AWK had associative arrays long before Perl, Python, Ruby, PHP, etc. were ever conceived. Update: Yannis says SNOBOL4 had associative arrays before AWK, and it didn’t take much googling to find a page that agrees. Here’s an interesting piece about how associative arrays are implemented in SNOBOL4.
Although other early languages like Lisp may not have explicit support for associative arrays as a built-in type, you can easily implement them in other ways. In Lisp, for example, you could implement an associative array as a list of lists where each sub-list has two items: a key and a value.
Are you interested in the history of the associative array concept, in which values are accessed using a key rather than a numeric index, or are you interested in the history of the algorithm(s) used to implement associative arrays? Hash tables are commonly used to implement associative arrays, but as the SNOBOL4 link above shows, they’re not the only possible implementation.
The idea of associating keys and values certainly predates computer languages and computers at all. Card catalogs and book indices are just two examples of real-world associative arrays.
0