[L-lang-devel] Hash table support

[Matthieu Lemerre]

I added support for Hash Tables into CVS.  This required some support
from several parts of L, which are now cleaner. I'm going to explain
how the implementation works, because it is quite general and will be
applied to other important data types in the future.

Use
===

To create a Hash Table, one wust has to do:
   
  let htable = Hash(Int, Float);

Access can be done using the postfix square brackets:
  
  htable[3] = 25; 
  let a = htable[3]

Any datatype that is a Word can be used as a key:

  let htable = Hash (Symbol, Int);  
  htable['foo'] = bar;

In the case of symbols, you can also use the dot notation:

  htable['foo'] == htable.foo; //true.

How it works
============

In short, access to htable is converted to calls to a puthash/gethash
function (currently written in C).  The whole point is: when to use
puthash and when to use gethash.

If you write: 

  let a = htable[3];

then it must be converted to:

  let a = gethash(3, htable);

but if you write

  htable[3] = a;

Then the conversion would be

  puthash(3, a, htable);

The distinction is done because in one case, the hash table is used as
a lvalue (left value, at the left of the = sign), and in the other in
a right value (or just value).

Use of the dot notation
***********************

It is the parser that converts a.b into a['b'] (also for struct
access). That's why it can works only with Symbols.

Expansion and left expansion
****************************

Besides the normal expander, a new "left_expander" has been added. Its
purpose is to make possible the transformation of:

  f(a) = g

Into:
  
  f''(a, g')

Where g' is the regular expansion of g, but f'' is the left expansion
of f.  In such a situation, there must be a left expander associated
to the symbol f, and g' must be expandable.

Accessers and left accessers
****************************

a[b] is in fact parsed as [](a,b).  The [] function is called
"access".  Depending on the type of a, different access can be done:
field access on a struct, array access on an array, or hash access on
a hash.

So, we have a record that associates a type with an accesser or left
accesser function.  The record is usually created at type definition.


Misc notes
==========

- We called these data structures Hash Tables (because they are
usually named like this), but they are really associative arrays.  In
the current implementation uses Judy, that is a trie and not a hash
table.

- String handling is not done for now.  Note that you can have
  Hash(String, Type); but the comparison would be done on the start
  address, not with memcmp().  A Hash_String data structure would be
  necessary for that. In the future, we should warn the user when he
  tries to use String as a from type.

- Current use of Hash_Table is not safe, because when the result is
  not found, the gethash operation returns Null.  In the future, we
  could add the check when the type cannot be Null, and maybe throw an
  exception.

- The hash are simple for now: when the result is not found, Null is
  returned.  If a different behaviour is needed, we could just use a
  different type: for instance, a BiHash type that would check if the
  result of the first hash is null, and if so, creates a second hash.
  We'll see that when we have a Graph library.