next up previous contents
Next: 6.3 Defining assembler instructions Up: 6 The GAMA Previous: 6.1 Memory organization

6.2 Hash tables, jump tables, and the module system

In the GAMA, hash tables are simply areas in Memory occupying three memory cells for each hash table entry. The use of three cells was motivated by the intended usage of hash tables as jump tables: the first cell contains the key (the name of a procedure), the second contains an address (the entry point of the procedure), and the third cell contains further information (concerning the procedure).

The following functions are defined on hash tables:

These hash tables are the basis of the GAMA module system: a hash table can be viewed as a name space containing all addresses and further information concerning all procedures of a module.

The reason why addresses are stored independently of the other information is that the hash tables are used as jump tables: a machine instruction like call does not have the name of a procedure as argument but only the address of the second memory cell in the corresponding hash table entry, thus avoiding to look up the address in the hash table at run time.

The following diagram shows how a hash table entry for a procedure f/2 is used: at the address 1000, a call to f/2 is expressed as call 101 where 101 is the address of the memory cell in the hash table which contains the entry point for f/2:

tex2html_wrap3281

Since abstract machines for PROLOG- and LISP-like languages are highly dynamic in that they allow procedures to change even at run time, procedures are not jumped at directly but via jump tables. This has the effect that, if a procedure is changed (recompiled), none of the procedures calling this procedure have to be changed.


next up previous contents
Next: 6.3 Defining assembler instructions Up: 6 The GAMA Previous: 6.1 Memory organization

Harold Boley (boley@informatik.uni-kl.de)