Implementing value delegation in Lua

✍️ Written on 2022-05-22 in 1228 words.
Part of cs software-development programming-languages lua

Motivation

For project typho, I built a prototype utilizing Lua. I want to have a specific tree structure for the document where all tree elements inherit from some Node object. To implement this approach, I looked into Lua’s metatable and want to explain my approach here (tested with Lua 5.3 and 5.4).

Our goal

  1. Lua has tables (called hashmap or dictionary in other languages).

  2. I want to declare table P to be the parent of child table C.

  3. If table C has value v, then return v for C[v].

  4. If table C does not have value v, then the value v of table P shall be returned (if it not exists, then nil)

  5. One can set C[v]. This does not affect P.

I called rule #4 “delegation”. Some might be reminded of class-based OOP inheritance, but this is very different. Since we don’t have classes, we don’t have a distinction of classes (blueprint) and objects (instantiation with members). As a result, we cannot inhert from blueprint to blueprint, but only delegate up a hierarchy of objects.

Our goal in code

local P = { ["common"] = true, ["unique"] = true }
local C = { ["common"] = false }

-- prints “true    true”
print(P.common, P.unique)
-- prints      “false    nil”
-- but I want  “false    true”
print(C.common, C.unique)

(Remember, that C.common equals C["common"] in Lua)

Lua metatables

I remembered the concept of metatables wrongfully. I thought that any values are looked up in the table and if it fails, in the metatable. This is exactly the value delegation concept, I am trying to implement. But metatables have a different behavior and the documentation cannot be more explicit:

Every value in Lua can have a metatable. This metatable is an ordinary Lua table that defines the behavior of the original value under certain special operations.

— https://www.lua.org/manual/5.3/manual.html#2.4

So when we apply a special operation (like indexing) to a table, then the metatable is consulted directly. If you declare the special operation in the table directly, this would not change anything since they are not any object’s metatable. The indexing special operation, in particular, is not called if the requested key exists in the table.

And the set of special operations are listed underneath in the documentation. We only care about index and newindex:

__index

The indexing access operation table[key]. This event happens when table is not a table or when key is not present in table. The metamethod is looked up in table.

Despite the name, the metamethod for this event can be either a function or a table. If it is a function, it is called with table and key as arguments, and the result of the call (adjusted to one value) is the result of the operation. If it is a table, the final result is the result of indexing this table with key. (This indexing is regular, not raw, and therefore can trigger another metamethod.)

__newindex

The indexing assignment table[key] = value. Like the index event, this event happens when table is not a table or when key is not present in table. The metamethod is looked up in table.

Like with indexing, the metamethod for this event can be either a function or a table. If it is a function, it is called with table, key, and value as arguments. If it is a table, Lua does an indexing assignment to this table with the same key and value. (This assignment is regular, not raw, and therefore can trigger another metamethod.)

Whenever there is a __newindex metamethod, Lua does not perform the primitive assignment. (If necessary, the metamethod itself can call rawset to do the assignment.)

Illustrating special operations

local T = { }
local M = { ["__index"] = function (self, idx)
  if idx == "attr" then
    return "exists"
  end
end }

-- prints “nil”
print(T["attr"])
setmetatable(T, M)
-- prints “exists”
print(T["attr"])

I think you get the analogous idea for __newindex where we receive arguments (self, idx, value) where value is the value to be set.

Strategy for our goal

  • We specify one object as parent where we delegate value lookups to; we call it _parent (this actually enables an arbitrary long chain; please don’t create cycles)

  • Specifying actually requires setting the parent explicitly. So unlike before, we won’t just call setmetatable but invoke a function preparing the object in a desired manner (the function is called creating_delegating_object).

The solution

local DelegatingMetaTable = {}

DelegatingMetaTable.__index = function (self, key)
    if self._parent ~= nil then
        return self._parent[key]
    end
end

function create_delegating_object(object, parent_values)
    object._parent = parent_values
    setmetatable(object, DelegatingMetaTable)
    return object
end

local p_values = { ["common"] = true, ["unique"] = true }
local c_values = { ["common"] = false }
local p = create_delegating_object(p_values, nil)
local c = create_delegating_object(c_values, p)

-- prints “true    true”
print(p.common, p.unique)
-- prints “false   true”
print(c.common, c.unique)

Conclusion

Lua’s metatable approach is really easy to grasp and very flexible. Our implementation shows a simple delegation mechanism.