Re: keys in tables

[Eric Jacobs <eric@...>]

On Sat, 10 Dec 2005 17:00:31 GMT
Gavin Wraith <gavin@wra1th.plus.com> wrote:

> Somebody must have asked this before! Is there anybody
> who can claim to have written a Lua program that uses
> a table whose keys are neither numbers nor strings,
> and for which this feature is essential?

Yes, I use this quite often. It's a big win for Lua that
it supports this.

> When I first learned that Lua allowed any non-nil value
> as a key, I thought "Wow - democracy for table-keys".
> That was quite a time ago. But what properties do we actually
> require of keys in a table? 1) that keys are distinguishable,
> and sometimes 2) that keys form a linear order. Can anybody
> suggest any other qualities that might be desirable?

Non-synthesizability is an important option to have. What this means is
that if you see someone has a value at point B, you know that ultimately
that value had to have come from point A. This means you can use
reachability analysis to prove useful things about your program.

Some applications:

1. Ancillary data. Sometimes you want to have several modules attach
data to an object, and they don't necessarily know about each other. In
other languages where you're restricted to a string key, if both modules
say happen to choose "obj.foo", there would be a namespace collision.
But democratic Lua actually gives you two ways to avoid this, both of
which rely on using a table as key:

weakTable[obj] = value

or

local opaqueKey = {}
obj[opaqueKey] = value

In either case, in order to access the attribute value, the user must
explicitly have access to weakTable or opaqueKey respectively. They
cannot accidentally synthesize an equivalent for those objects the
way that can happen for value types.

2. Security. With some customization to the Lua environment, you can
expand on this concept to prevent intentional collisions as well as
accidental ones. You'd have to make sure that the user couldn't peek
into your table using pairs() (nor the debug interfaces,etc.), but once
you did, you could know that the user wouldn't be able to get anything
out of your table if they didn't possess one of your keys. There are a
variety of useful security patterns, like sealer/unsealer:

function makeSealerUnsealer()
    local s = {}
    local u = {}
    function s:seal(val)
        return { [u]=val }
    end
    function u:unseal(seal)
        return seal[self]
    end
    return s, u
end

u:unseal(s:seal(x)) == x

which is analogous to public/private key encryption, but where we
rely on the VM's support of closures' privacy rather than obscure
numeric properties for security.

(I hope this makes a case for virtualizable __pairs, btw.)

-Eric