Immutable Objects

wiki

This page concerns topics of immutability [6] / const-ness [4] in Lua.

Overview of Concepts

According to [Papurt, 1], "An immutable entity never changes value, but immutability manifests in two ways. A strictly immutable entity gets an initial value at creation and holds that value until termination. In contextual immutability, an otherwise modifiable entity is held modifiable in a specific context.". Certain values in Lua have strict immutability, such as strings, numbers, and booleans (as well as functions barring upvalues and environments). Lua tables are mutable, but strict immutability can be simulated to some extent (bar rawset) via metamethods, as shown in ReadOnlyTables. Userdata can provide stronger enforcement. In contrast, Lua local variables are mutable (in terms of the association between variable and value, not the value itself), while global variables are implemented as tables and so share the same conditions as tables. Though a variable might be thought of as a constant (e.g. math.pi) if it is not normally mutated in practice, this is only a convention not enforced by the Lua compiler or runtime. Contextual immutability (or "const correctness") is less common in languages, though it is widely used in C/C++ and extended in D ([Wikipedia:Const correctness]). Contextual immutability provides a read-only "view" of the object.

We also have the question of transitivity of immutability--if some object is immutable, whether other objects reachable from that object are also immutable. For example, if document.page[i] retrieves the page i of a document, and if document is contextually immutable, then is the page retrieved from document.page[i] contextually immutable too? In C, we have distinctions of const pointer, pointer to a const, and const pointer to a const, as well as const methods returning const pointers (allowing transitivity in the previous example). In D, full transitivity is more builtin. [4][1][5]

Below are approaches of simulating various immutability effects in Lua.

Immutability of constants

A common convention (not enforced by the compiler) is to name variables that are never modified in ALL_CAPS. See LuaStyleGuide.

local MAX_SIZE = 20

for i=1,MAX_SIZE do print(i) end

Immutability of tables (read-only tables)

Tables can be made mostly immutable via metamethods. See ReadOnlyTables.

Immutability of userdata

Userdata provides some of the characteristics of tables. However, one possible advantage is that immutability of userdata can be more strongly enforced on the Lua-side compared to Lua tables.

Immutability of function objects

Functions can store data in upvalues, environment variables, or in storage areas accessible through other function calls (e.g. databases). A function can be considered immutable when it is pure [1]. Things that can make a function impure include changes to upvalues (if it has upvalues), changes to the environment (if it uses environment variables), and calls to other impure functions (stored in upvalues or environment variables). There are some simple steps a function implementation can take to prevent those things:

do
  local sqrt = math.sqrt -- make the environment variable "math.sqrt"
                         -- a lexical to ensure it is never redefined
  function makepoint(x,y)
    assert(type(x) == 'number' and type(y) == 'number')
    -- the upvalues x and y are only accessible inside this scope.
    return function()
      return x, y, sqrt(x^2 + y^2)
    end
  end
end
local x,y = 10,20
local p = makepoint(x,y)
print(p()) --> 10  20  22.360679774998
math.sqrt = math.cos  -- this has no effect
x,y = 50,60           -- this has no effect
print(p()) --> 10  20  22.360679774998

External routines may still have access to environment variables and upvalues of such a function. The environment of a function can change via setfenv [2]. Though the implementation of a function f might not use environment variables, this will still affect the result of any getfenv(f) calls from outside the function, so in this way functions are not immutable. Secondly, the upvalues actually are modifiable via debug.setupvalue [3], but the debug interface is considered a backdoor.

See SimpleTuples for further description on using functions to represent immutable tuples.

Immutability of strings

Lua strings are immutable and interned. This has some implications [4]. To create a string that differs in only one-character from an existing 100 MB string requires creating an entirely new 100 MB string since the original string cannot be modified.

Some have implemented (mutable) string buffers in terms of userdata.

In the Lua C API, string buffers [5] are mutable.

Simulating contextual immutability in Lua at run-time

Here's a quick example of how contextual immutability might be simulated at run-time in Lua: [2]

-- converts a mutable object to an immutable one (as a proxy)
local function const(obj)
  local mt = {}
  function mt.__index(proxy,k)
    local v = obj[k]
    if type(v) == 'table' then
      v = const(v)
    end
    return v
  end
  function mt.__newindex(proxy,k,v)
    error("object is constant", 2)
  end
  local tc = setmetatable({}, mt)
  return tc
end

-- reimplementation of ipairs,
-- from http://lua-users.org/wiki/GeneralizedPairsAndIpairs
local function _ipairs(t, var)
  var = var + 1
  local value = t[var]
  if value == nil then return end
  return var, value
end
local function ipairs(t) return _ipairs, t, 0 end


-- example usage:

local function test2(library)  -- example function
  print(library.books[1].title)
  library:print()

  -- these fail with "object is constant"
  -- library.address = 'brazil'
  -- library.books[1].author = 'someone'
  -- library:addbook {title='BP', author='larry'}
end

local function test(library)  -- example function
  library = const(library)

  test2(library)
end

-- define an object representing a library, as an example.
local library = {
  books = {}
}
function library:addbook(book)
  self.books[#self.books+1] = book
  -- warning: rawset ignores __newindex metamethod on const proxy.
  -- table.insert(self.books, book)
end
function library:print()
  for i,book in ipairs(self.books) do
    print(i, book.title, book.author)
  end
end

library:addbook {title='PiL', author='roberto'}
library:addbook {title='BLP', author='kurt'}

test(library)

The key line is "library = const(library)", which converts a mutable parameter to an immutable one. const returns a proxy object that wraps the given object, allowing reading of the object's fields but not writing to them. It provides a "view" of the object (think: databases).

Notice that recursive call v = const(v) provides a type of transitivity to the immutability.

There are some caveats to this approach noted in the above code. The methods of the original object are not passed the original object but rather a proxy to the object. Those methods therefore must avoid raw gets and sets (which don't trigger metamethods). Until LuaFiveTwo, we also have the issues with pairs/ipairs/# (see GeneralizedPairsAndIpairs). The above could be extended to support operator overloads.

The above does impose some runtime overhead. However, in production, you could define const as the identity function or even strip out these functions from the source code.

Note: the above is a proof-of-concept and is not necessarily suggested in practice for general use.

Simulating contextual immutability in Lua at compile-time

It might be more desirable to perform the const correctness checks at compile time (static analysis), as in C/C++. A tool for this could be written, e.g., using MetaLua's gg/mlp, Leg, etc. (see LuaGrammar), or perhaps a trick with luac -p -l could be done (e.g. see DetectingUndefinedVariables). Here's how such code "might" look like:

local function test2(library)
  print(library.books[1].title)
  library:print()

  -- these fail with "object is constant"
  -- library.address = 'brazil'
  -- library.books[1].author = 'someone'
  -- library:addbook {title='BP', author='larry'}
  library:print()
end

local function test(library)  --! const(library)
  test2(library)
end

local library = {
  books = {}
}
function library:addbook(book)
  table.insert(self.books[#self.books+1], book)
end
function library:print()
  for i,book in ipairs(self.books) do
    print(i, book.title, book.author)
  end
end

library:addbook {title='PiL', author='roberto'}
library:addbook {title='BLP', author='kurt'}

test(library)

Above, an annotation in the form of a specially formatted comment (--!) is used to indicate to the static analysis checking tool that the given parameter should be treated as constant. How this would work in practice is less clear. Obviously, due to the dynamic nature of Lua, this could only be done in a restricted set of cases (e.g. heavy use of locals that are not modified and assuming globals like table.insert retain their usual semantics).

Runtime constant check on tables

The following library can be used during debugging to ensure that function arguments with names postfixed by "_c" are unchanged across function calls.

-- debugconstcheck.lua
-- D.Manura, 2012-02, public domain.
-- Lua 5.2. WARNING: not well tested; "proof-of-concept"; has big performance impact
-- May fail with coroutines.

local stack = {}
local depth = 0

-- Gets unique identifier for current state of Lua object `t`.
-- This implementation could be improved.
-- Currently it only does a shallow table traversal and ignores metatables.
-- It could represent state with a smaller hash (less memory).
-- Note: false negatives are not serious problems for purposes here.
local function checksum(t)
  if type(t) ~= 'table' then
    return ("(%q%q)"):format(tostring(type(t)), tostring(t))
  end
  local ts = {}
  for k, v in next, t do
    ts[#ts+1] = ('%q%q'):format(tostring(k), tostring(v))
  end
  return '("table"'..table.concat(ts)..')'
end

-- Checks function parameters on call/returns with a debug hook.
debug.sethook(function(op)
  if op ~= 'return' then

    depth = depth + 1
    local info = debug.getinfo(2, 'ufn')
    --print('+', depth, info.name, op)
    local nfound = 0
    for i=1, info.nparams do
      local name, val = debug.getlocal(2, i)
      if name:match('_c$') then -- record state of param on function entry
        stack[#stack+1] = val
        stack[#stack+1] = checksum(val)
        --print(name, stack[#stack])
        nfound = nfound + 1
      end
    end
    if nfound ~= 0 then stack[#stack+1] = nfound; stack[#stack+1] = depth end
  
  else -- 'call' or 'tail call'

    --print('-', depth, debug.getinfo(2, 'n').name)
    if depth == stack[#stack] then -- check state of params on function exit
      table.remove(stack)
      local count = table.remove(stack)
      for i=count,1,-1 do
        local sum = table.remove(stack)
        local val = table.remove(stack)
        local current_sum = checksum(val)
        --print('check', '\n'..sum, '\n'..current_sum)
        if sum ~= current_sum then error("const variable mutated") end
      end
    end
    depth = depth - 1
  
  end
end, 'cr')

return {}

Example (to be run with lua -ldebugconstcheck example.lua:

-- example.lua

local function g(a,b,c)
  b.x=1 -- ok
  table.sort(a) -- bad
end

local function f(a_c, b, c_c)
  return g(a_c, b, c_c)
end

f({'b','a'}, {}, {})

Results:

lua52: ./debugconstcheck.lua:46: const variable mutated
stack traceback:
	[C]: in function 'error'
	./debugconstcheck.lua:46: in function <./debugconstcheck.lua:17>
	example.lua:10: in main chunk
	[C]: in ?