Proposal: Constant Tables

[Lars Doelle <lars.doelle@...>]

Hi All,


reviewing the tables, i found them limited w.r.t. composed keys.
To ensure, all keys stay the same during their existience, tables
as possible (and only) structuring technic are only identified
by their pointer (i.e. object name).

--

Practical example:

  Key1 = { first="John", last="Doe" }
  Key2 = { first="John", last="Doe" }

When using a key like the above for an table, currently Key1
and Key2 would identify different entries, i.e. are of no use.

Though one could try to encode such a key into a string, this
approach has several problems:

a) Later access to the components is more costly and would
   involve some kind of matching.

b) Encoding could become exponential in case of structure
   sharing:

   Key1     = { "bla", "bla" }
   Key2     = { Key1,  Key1  }
   Key(I+1) = { KeyI,  KeyI  }

--

My proposal to resolve the issue adding a 'constant' attribute
to tables. Technically, this would work as follows:

  Table.todata( tbl ) : produces a 'constant' copy of 'tbl'

The effect is basically the same as it now for creation of strings.
All constant tables are kept in a global map guaranteeing their
uniqueness.

Once created, they cannot longer be modified in any respect.
This guarantees, that their content never changes and their
pointer uniquely identifies their content.

The equality of constant tables is by their content. Because
constant tables can only contain constant tables /older/ than
itself, the (hash) values of the components are already known.

Note that the semantic is non-recursive. If 'tbl' contains a
pointer to itself, the resulting constant version will still
refer to 'tbl' as before, not to the constant version.

More formally, 'constant' tables do not longer behave like
objects, but become /data/ by the Table.todata conversion.
It is possible to extend this conversion for recursive, i.e.
cyclic structures, but the infrastructure, i.e. common hash
table over all constant tables would remain the same. Only
a new function Table.torecdata( tbl, ... ) would be needed.

Thus the cost of implementing the feature is relative low.
It fits well into the structure of LUA and removes a significant
restriction on the usibily of tables, w.r.t. their keys.

It is candidate of an extension for the LUA machinery, as
it is not possible in LUA itself to define 'Table.todata' in any
reasonable way, even if promissing never to change the
content of 'tbl'. The reason for this is that hashing is not
available at user space. One cannot get the hash value of
strings nor tables, thus leaving only to implement one own's
hashing of all data, which is only costly and complicate in
user space and does not guarantee the proposed semantics.


Kind regards

  Lars Dölle