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. Here's an example of contextual immutability in C:


#include <stdio.h>

struct Point { double x; double y; };



void test(const Point p) {

  printf("%f\n", p.x);

  // p.x = 4.0; // fails: p is immutable here

}



int main() {

  Point p = {2.0, 3.0};

  test(p);

  p.x = 5.0; // p is mutable here

  return 0;

}

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 ?