Nothing but Functions - Data Structures
So far, we've used JavaScript to build the lambda calculus versions of boolean logic and numbers. Indeed, it should come as no surprise that we can do calculations with functions. Now, let's do something less intuitive: store data using nothing but functions.
Lambda calculus allows functions to access arguments in higher lexical scopes; this mechanism is called a closure. We already saw this in boolean functions, which take two values and always return a specific one. We can take this idea a little further to produce our first data structure, a fixed-length list of values called a tuple.
In mathematics, an "n-tuple" is an ordered list of n values. For example, a 3-tuple might be (2, 3, 5). We won't be able to modify the values, but we can construct new tuples based on old ones. However, we will be able to give the fields names, and the result behaves much like a struct in C or, in most OOP languages, an object with a few read-only properties and no methods.
The trick we use to build these tuples is pretty nifty. Create a function that takes a few values and does nothing with them — that's our data. Then, it returns a function which, when passed an "accessor function", will pass that accessor function all of the values it was storing! Think of the outermost function as the tuple constructor. We can even make helper functions that take a tuple and pass it a function that retrieves a specific value for us. In traditional JavaScript, it might look like this:
function build_3tuple(a, b, c) { //<-- this function is the tuple constructor
return function(accessor) { //<-- this function is the "tuple" itself; it can see a, b, and c from here
accessor(a, b, c);
};
}
function get_a(tuple) {
return tuple(function(a, b, c){ return a; }); //give the tuple a function that just returns 'a'
}
function get_b(tuple) {
return tuple(function(a, b, c){ return b; });
}
function get_c(tuple) {
return tuple(function(a, b, c){ return c; });
}
var tuple = build_3tuple(2, 3, 5); //construct a tuple
tuple(function(a, b, c) {
// do something with the values in the tuple!
});
var b = get_b(tuple);Under our lambda calculus rules, it looks like this:
var BUILD_3TUPLE = a => b => c => f => f(a)(b)(c); // \-- "tuple" --/ var GET_A = t => t(a => b => c => a); //take all the values, but only return the one we want var GET_B = t => t(a => b => c => b); var GET_C = t => t(a => b => c => c); var tuple = BUILD_3TUPLE(N0)(N1)(N2); tuple(a => b => c => .....); //do something with the values in the tuple! var b = GET_B(tuple);
With these tools, we can finally get back to numbers and build our missing functions. The first function to build is the opposite of the successor function, called the predecessor (or "decrement" in software), which simply finds n-1. This function sounds like it should be simple, but consider what it means in terms of lambda calculus numbers. If a "number" is a function that applies some other function that many times, then the "predecessor of a number" is a function that applies some other function one fewer time than it would have normally. You can't un-apply a function, and so we have to be a little more clever.
First, we need a 2-tuple, more commonly called a pair:
var PAIR = a => b => f => f(a)(b); //PAIR(a)(b) constructs a pair which stores "a" and "b" for later var FIRST = p => p(a => b => a); //given a pair "p", get back "a" var SECOND = p => p(a => b => b); //given a pair "p", get back "b" // Then, var three_and_one = PAIR(N3)(N1); FIRST(three_and_one) == N3; SECOND(three_and_one) == N1;
Then, we make a peculiar little function everyone calls "phi" (or "shift-and-increment"). This function takes a pair of numbers, (a, b), and produces a new pair containing the second number and the successor of the second number, (b, b+1). In effect, this acts like increment-but-log-previous: the first half of the pair is always the value before the most recent increment. If we start with (0,0) and then keep passing it to phi(), the next values are (0,1), (1,2), (2,3), (3,4), and so on. If we do this n times, then the second half of the pair is n, but the first half is the predecessor of n! (Or zero if n is zero, since we don't have negative numbers.)
Here's what that looks like in code:
var PHI = p => PAIR(SECOND(p))(SUCC(SECOND(p))); // \-first-/ \-- second ---/ var PRED = n => FIRST(n(PHI)(PAIR(N0)(N0))); // \---/ get the first half of.. // \----/ applying PHI() n times // \----------/ to the pair (0,0)
Then, subtraction is easy: to find m - n, apply PRED() n times to m, that is, starting from m, subtract one n times.
var SUB = m => n => n(PRED)(m);
Now that we have subtraction, things like comparing numbers or testing whether a number is zero become more useful. The ISZERO() function abuses the way number functions behave: every number function will apply the function they are given at least once except zero, which returns the original value. So, it gives the number in question a function that always returns FALSE, and asks it to run "always return FALSE" on the value TRUE. If the function is run even once, the result goes from TRUE to FALSE.
var ISZERO = n => n(x => FALSE)(TRUE);
Finally, we can abuse the unsigned nature of our numbers to construct a less-than-or-equal (LEQ()) function: because any negative number becomes zero, if m minus n is zero, m must be less than or equal to n:
var LEQ = m => n => ISZERO(SUB(m)(n));
If we improve our original math demonstration code,
output(["n","succ","plus","mult","pow","pred","sub(2)","iszero","leq(2)"].join("\t")+"\n");
[N0, N1, N2, N3, N4].forEach(function(n){
output([
l2js_uint(n),
l2js_uint(SUCC(n)),
l2js_uint(PLUS(n)(n)),
l2js_uint(MULT(n)(n)),
l2js_uint(POW(n)(n)),
l2js_uint(PRED(n)),
l2js_uint(SUB(n)(N2)),
l2js_bool(ISZERO(n)),
l2js_bool(LEQ(n)(N2)),
].join("\t")+"\n");
});We now get:
n succ plus mult pow pred sub(2) iszero leq(2) 0 1 0 0 1 0 0 TRUE TRUE 1 2 2 1 1 0 0 FALSE TRUE 2 3 4 4 4 1 0 FALSE TRUE 3 4 6 9 27 2 1 FALSE FALSE 4 5 8 16 256 3 2 FALSE FALSE
Next time, we'll use tuples to build a much more practical data structure: linked lists.