Re: Proposal: Constant Tables (i.e. composed keys)

[Dirk Laurie <dpl@...>]

On Sat, Aug 13, 2011 at 06:56:48PM +0200, Lars Doelle wrote:
> No, Dirk, please reread my original post. It is all about tables and
> hashing. The problem is rather to use a composed key. How would
> you do that in LUA? This is what i talk about, and the concept of
> tables is clear lacking here, if you like it or not.
> 

OK, just to show I'm not a troll, here is my attempt at implementing
such a feature.

~~~~ file immutable.lua
local ctab = {}		-- table of constant tables

local function ctab_eq(t,s)
    for k,v in pairs(t) do if s[k]~=v then return false end end
    for k,v in pairs(s) do if t[k]~=v then return false end end
    return true
    end

local function ctab_put(hashkey,proxy)
    -- called only when it is known that proxy is not in ctab
    -- keeps a table of arrays that have the same hashkey
    local found = ctab[hashkey]
    if not found then ctab[hashkey]={proxy} return end
    found[#found+1] = proxy
    ctab[hashkey] = found 
    end
    
local function ctab_get(hashkey,rawtable)
    local found = ctab[h]
    if not found then return nil end
    for _,p in ipairs(found) do 
	if ctab_eq(p,rawtable) then return p end end
    end

local function is_mutable(t)
    -- returns nil if t is not a table, false if t is immutable
    if type(t)=='table' then
    return getmetatable(t)==nil or getmetatable(t).__eq~=ctab_eq end
    end

local function hash(t)   -- details unimportant here
    -- this particular function goes via an intermediate string
    local h = 0
    if type(t)~='table' then t=tostring(t) end 
    if type(t)=='string' then  -- 
	for n=1,#t do h=bit32.bxor(h,bit32.lshift(t:byte(n,n),5*((n-1)%7)))
	    end
	return h
	end
    for k,v in pairs(t) do  -- keys ignored for the purpose of hashing
	if is_mutable(v) then
	    error('attempt to create constant table with mutable fields',3)
	else v=tostring(v)
	    end
	h = bit32.bxor(h,hash(v))
	end 
    return h
    end

local function immutable(t)
    if not is_mutable(t) then return t end
    local h = hash(t)
    local known = ctab_get(h,t)
    if known then return known end
    -- see PiL §13.4
    local proxy = {}
    local mt = { 
	__index = t, 
	__eq = ctab_eq,
	__pairs = function() return pairs(t) end,
	__ipairs = function() return ipairs(t) end,
	__newindex = function() 
	    error("attempt to update a read-only table",2)
	    end
    }
    setmetatable(proxy,mt)
    ctab_put(h,proxy)
    return proxy
    end 

return immutable
~~~~

Use like this:

    imm = require "immutable"
    s = imm {n=3,1,2,3}
    t = {1,2,3,4,n=4}
    t[#t] = nil; t.n = t.n -1
    print ( s == t )        --> false
    print ( s == imm(t) )   --> true
    Math = imm(math)
    print (Math.pi)         --> 3.1415926535898
    Math.pi = 22/7          --> gives an error

Warning: The safe thing is to make immutable tables only from table 
    constants.  If you have another reference to the table you are 
    making immutable, that reference is not also immutable.

    math.pi = 22/7
    print (Math.pi)         --> 3.1428571428571

Dirk