Re: Proposal: Constant Tables

[Xavier Wang <weasley.wx@...>]

2011/8/13 Lars Doelle <lars.doelle@on-line.de>:
> 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
>
>

maybe you can write you own hash function in lua:

function hash(tbl) ... end
local t = {}
t[hash { a = 1, b = 2 }] = true
print(t[hash {a = 1, b = 2}]) --> true