Functional Tuples

lua-users home
wiki

This article describes a novel design pattern for expressing tuples in terms of only functions.

Tuples are immutable sequences of objects. They are present in a number of programming languages including [Python], [Erlang], and indeed most [functional languages]. Lua strings are a particular type of tuple, one whose elements are restricted to single characters.

Because tuples are immutable, they can be shared without copying. On the other hand, they cannot be modified; any modification to a tuple must create a new tuple.

To explain the concept, we implement a point in three-dimensional space as a tuple <x, y, z>

Lua provides a number of ways to implement tuples; the following is an adaptation of an implementation which can be found in the excellent textbook [Structure and Interpretation of Computer Programs].

Following Abelson and Sussman, we represent a tuple as a function of one argument; the argument itself must be a function; we can variously think of it a method or slot-accessor.

To start with, we'll need a constructor function and some member selectors:

function Point(_x, _y, _z)
  return function(fn) return fn(_x, _y, _z) end
end

function x(_x, _y, _z) return _x end
function y(_x, _y, _z) return _y end
function z(_x, _y, _z) return _z end

So what is going on here? Point takes three arguments, the co-ordinates of the point, and returns a function; for these purposes, we will regard the return value as opaque. Calling a Point with a function feeds that function as arguments the objects that make up the tuple; the selectors simply return one of these and ignore the other ones:

> p1 = Point(1, 2, 3)
> =p1(x)
1
> =p1(z)
3

However, we are not limited to selectors; we can write any arbitrary function:

function vlength(_x, _y, _z)
  return math.sqrt(_x * _x + _y * _y + _z * _z)
end

> =p1(vlength)
3.7416573867739

Now, although we cannot modify a tuple, we can write functions which create a new tuple with a specific modification (this is similar to string.gsub in the standard Lua library):

function subst_x(_x)
  return function(_, _y, _z) return Point(_x, _y, _z) end
end
function subst_y(_y)
  return function(_x, _, _z) return Point(_x, _y, _z) end
end
function subst_z(_z)
  return function(_x, _y, _) return Point(_x, _y, _z) end
end

Like gsub, these functions do not affect the contents of the original point:

> p2 = p1(subst_x(42))
> =p1(x)
1
> =p2(x)
42

It is interesting to note that we can use any function which takes an arbitrary sequence of arguments:

> p2(print)
42      2       3

Similarly, we can write functions which combine two points:

function vadd(v2)
  return function(_x, _y, _z)
    return Point(_x + v2(x), _y + v2(y), _z + v2(z))
  end
end

function vsubtract(v2)
  return function(_x, _y, _z)
    return Point(_x - v2(x), _y - v2(y), _z - v2(z))
  end
end

> =p1(vadd(p1))(print)
2       4       6

A close examination of vadd and vsubtract (and, indeed, of the various substitute functions) shows that they are actually creating a temporary function with a closed upvalue (their original argument). However, there is no reason for these functions to be temporary. Indeed, we may actually want to use a specific transformation several times, in which case we could just save it:

> shiftDiagonally = vadd(Point(1, 1, 1))
> p2(print)
42      2       3
> p2(shiftDiagonally)(print)
43      3       4
> p2(shiftDiagonally)(shiftDiagonally)(print)
44      4       5

This might incline us to revisit the definition of vadd to avoid creating and then deconstructing the argument:

function subtractPoint(x, y, z)
  return function(_x, _y, _z) return _x - x, _y - y, _z - z end
end

function addPoint(x, y, z)
  return function(_x, _y, _z) return _x + x, _y + y, _z + z end
end

And while we're at it, let's add a couple of other transformations:

function scaleBy(q)
  return function(_x, _y, _z) return q * _x, q * _y, q * _z end
end

function rotateBy(theta)
  local sintheta, costheta = math.sin(theta), math.cos(theta)
  return function(_x, _y, _z)
    return _x * costheta - _y * sintheta, _x * sintheta + _y * costheta, _z
  end
end

Notice that in rotateBy, we pre-compute the sine and cosine so as to not have to call the math library every time the function is applied.

Now these functions do not return a Point; they simply return the values which make up the Point. To use them, we have to create the point explicitly:

> p3 = Point(p1(scaleBy(10)))
> p3(print)
10      20      30

That is a little fastidious. But as we will see, it has its advantages.

But first, let's look once again at addPoint. It is fine if we have a transformation in mind, but what if we want to shift by a particular point? p1(addPoint(p2)) obviously is not going to work. However, the answer is quite simple:

> centre = Point(0.5, 0.5, 0.5)
> -- This doesn't work
> =p1(subtractPoint(centre))
stdin:2: attempt to perform arithmetic on a function value
stack traceback:
        stdin:2: in function <stdin:2>
        (tail call): ?
        (tail call): ?
        [C]: ?
> -- But this works just fine:
> =p1(centre(subtractPoint))
0.5     1.5     2.5

Moreover, these new functions can be composed; we can, in effect, create a sequence of transformations as a single primitive:

-- A complex transformation
function transform(centre, expand, theta)
  local shift = centre(subtractPoint)
  local exp = scaleBy(expand)
  local rot = rotateBy(theta)
  local unshift = centre(addPoint)
  return function(_x, _y, _z)
    return unshift(exp(rot(shift(_x, _y, _z))))
  end
end

> xform = transform(centre, 10, math.pi / 4)
> =p1(xform)
-6.5710678118655        14.642135623731 25.5

One enormous benefit that this carries is that once xform is created, it can execute without creating a single heap-object. All memory consumption is on the stack. Of course, that is a little disngenuous -- quite a lot of storage allocation is done to create the tuple (a function closure and three upvalues) and to create individual transformers.

Furthermore, we have not yet managed to deal with some important syntax issues, like how to make these tuples actually usable by an average programmer.

--RiciLake

Generalized to Arbitrary Size N

To make the above scheme work for tuples of arbitrary size, we can use CodeGeneration as shown below--DavidManura.

function all(n, ...) return ... end     -- return all elements in tuple
function size(n) return n end           -- return size of tuple
function first(n,e, ...) return e end     -- return first element in tuple
function second(n,_,e, ...) return e end  -- return second element in tuple
function third(n,_,_,e, ...) return e end -- return third element in tuple
local nthf = {first, second, third}
function nth(n)
  return nthf[n] or function(...) return select(n+1, ...) end
end

local function make_tuple_equals(n)
  local ta, tb, te = {}, {}, {}
  for i=1,n do
    ta[#ta+1] = "a" .. i
    tb[#tb+1] = "b" .. i
    te[#te+1] = "a" .. i .. "==b" .. i
  end
  local alist = table.concat(ta, ",")
  if alist ~= "" then alist = "," .. alist end
  local blist = table.concat(tb, ",")
  if blist ~= "" then blist = "," .. blist end
  local elist = table.concat(te, " and ")
  if elist ~= "" then elist = "and " .. elist end
  local s = [[
    local t, n1 %s = ...
    local f = function(n2 %s)
      return n1==n2 %s
    end
    return t(f)
  ]]
  s = string.format(s, alist, blist, elist)
  return assert(loadstring(s))
end

local cache = {}
function equals(t)
  local n = t(size)
  local f = cache[n]; if not f then
    f = make_tuple_equals(n)
    cache[n] = f
  end
  return function(...) return f(t, ...) end
end

local function equals2(t1, t2)
  return t1(equals(t2))
end

local ops = {
  ['#'] = size,
  ['*'] = all,
}
local ops2 = {
  ["number"]   = function(x) return nth(x) end,
  ["function"] = function(x) return x end,
  ["string"]   = function(x) return ops[x] end
}

local function make_tuple_constructor(n)
  local ts = {}
  for i=1,n do ts[#ts+1] = "a" .. i end
  local slist = table.concat(ts, ",")
  local c = slist ~= "" and "," or ""
  local s =
    "local ops2 = ... " ..
    "return function(" .. slist .. ") " ..
    "  return function(f) " ..
     "    return (ops2[type(f)](f))(" ..
                 n .. c .. slist .. ") end " ..
    "end"
  return assert(loadstring(s))(ops2)
end

local cache = {}
function tuple(...)
  local n = select('#', ...)
  local f = cache[n]; if not f then
    f = make_tuple_constructor(n)
    cache[n] = f
  end
  return f(...)
end

Test:

-- test suite
local t = tuple(1,nil,2,nil)
;(function(a,b,c,d) assert(a==1 and b==nil and c==2 and d==nil) end)(t(all))
;(function(a,b,c,d) assert(a==1 and b==nil and c==2 and d==nil) end)(t '*')
assert(t(size) == 4)
assert(t '#' == 4)
assert(t(nth(1)) == 1 and t(nth(2)) == nil and t(nth(3)) == 2 and
       t(nth(4)) == nil)
assert(t(1) == 1 and t(2) == nil and t(3) == 2 and t(4) == nil)
assert(t(first) == 1 and t(second) == nil and t(third) == 2)
local t = tuple(3,4,5,6)
assert(t(nth(1)) == 3 and t(nth(2)) == 4 and t(nth(3)) == 5 and
       t(nth(4)) == 6)
assert(t(first) == 3 and t(second) == 4 and t(third) == 5)
assert(tuple()(size) == 0 and tuple(3)(size) == 1 and tuple(3,4)(size) == 2)
assert(tuple(nil)(size) == 1)
assert(tuple(3,nil,5)(equals(tuple(3,nil,5))))
assert(not tuple(3,nil,5)(equals(tuple(3,1,5))))
assert(not tuple(3,nil)(equals(tuple(3,nil,5))))
assert(not tuple(3,5,nil)(equals(tuple(3,5))))
assert(tuple()(equals(tuple())))
assert(tuple(nil)(equals(tuple(nil))))
assert(tuple(1)(equals(tuple(1))))
assert(not tuple(1)(equals(tuple())))
assert(not tuple()(equals(tuple(1))))
assert(equals2(tuple(3,nil,5), tuple(3,nil,5)))
assert(not equals2(tuple(3,nil,5), tuple(3,1,5)))


-- example
function trace(f)
  return function(...)
    print("+function")
    local t = tuple(f(...))
    print("-function")
    return t(all)
  end
end
local test = trace(function (a,b,c)
  print("test",a+b+c)
end)
test(2,3,4)
--[[OUTPUT:
+function
test    9
-function
]]

Comments

I think this page is misleading. These are not tuples. Tuples are only useful if they compare by value so they can be indexed on (i.e. can be used as table keys). Without this property they are no better than tables. See [1] for an n-tuple implementation using an internal indexing tree. --CosminApreutesei.

See Also


RecentChanges · preferences
edit · history
Last edited September 12, 2014 3:09 pm GMT (diff)