Functional Tuples
 |
||
|
Functional Tuples |
|
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
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 ]]
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.