Implementing tables - advice wanted

[Richard A. O'Keefe]

"Joe Armstrong \(AL/EAB\)" <joe.armstrong@REDACTED> wrote:
	   I've been thinking a bit about tables in Erlang.
	
	   Erlang really really really (^100) needs tables.
	
I have written about this in detail suggesting Erlang-appropriate
syntax, an adequate set of built in functions, and explaining how
they can be implemented efficiently.

	   In a Daghstuhl meeting we has a session on the theme "all you need
	are tables - virtually all dynamically typed languages (except Erlang)
	have tables. In Lua they are called tables, in Python dictionaries, in
	JavaScript associative arrays - the semantics of all these things are
	slightly different but essentially they are the same.
	
There is one essential difference:  Python, Ruby, Javascript, Perl, Icon,
... all have MUTABLE tables.  Erlang data structures are not mutable.
This has consequences for implementation.

	   Keys are strings or integers, conseqative ranges of integers
	(very useful for arrays) are handled in a special manner.
	
The most appropriate keys for Erlang would seem to be atoms.

	   I'm wondering about how to implement tables.
	
	   Let's choose "@" as the table constructor (just about the only
	character
	left, that's unused.
	
		X = @{name="fred", age=23, footSize = 42}
		Name = X.name,
		...
The syntax I proposed uses <{...}> for anonymous psi-terms and
<name{...}> for named psi-terms, e.g.,
	X = <person{name = fred, age = 23, foot_size = 42}>

	   Now how could I implement this?
	
Very very cheaply.  Basically, a psi-term is
    a tuple, with a different tag,
    whose first element points to a tuple containing the name (if any)
    and the keys, in a standard order.

There is again quite an important difference between the way Erlang
would use something like this and the way we'd use hash tables; Erlang
uses _pattern matching_, so that

    <person{age = Age, name = Name}> = X

is a normal thing to do.  With keys in standard order, this can be done
in a linear scan.  For something like

    get(X, name)

a binary search is required, but immutable psi-terms are unlikely to
grow large enough for binary search (especially if cunningly done) to
be a performance issue at all.

Psi-terms are a good, perhaps even the ideal, replacement for records.
The analogy with *mutable* hash tables in other languages, which get
*used* in completely different ways, is probably misleading.

That's not to say that a mutable hash table data type would be of no
use.  It already exists, courtesy of the process dictionary, and if
you want a light-weight way to implement these things, building on
top of the process dictionary rather than ets is probably the way to go.