In my book I briefly mention (in a footnote I think) the lambda calculus. It’s probably time to expand on that. As I said, the lambda calculus is a mathematical discipline that predates computers, but is amazingly relevant to computer language design. Basically it assumes that there are nothing but functions, each taking only one argument, and it derives all possible computations from them.
I won’t bother describing the specific syntax right now, rather let’s take a look at a translation of some of it into Perl.
First off, functions can only take one argument. So how do we imitate functions, such as addition, that require more than one argument? The answer is a technique called “Currying” (after the mathematician Haskell Curry who gave the better part of his name to a programming language.) To summarise, a “Curried” function of two arguments is a function that takes one argument and returns a function that takes a second argument and returns the result. So for example Currying a perl function add:
|
1 2 3 4 |
my $add = sub { my ($a, $b) = @_; $a + $b; } |
(using anonymous subs throughout for consistency) produces:
|
1 2 3 4 5 6 7 |
my $add = sub { my ($a) = @_; sub { my ($b) = @_; $a + $b; } } |
which you can call like:
|
1 |
$add->(3)->(4); |
to get 7.
More interestingly, we can represent truth and falsehood as functions. Assuming implicit Currying from now on, true can be represented as a function that takes two arguments and returns its first one:
|
1 2 3 4 |
my $true = sub { my ($a, $b) = @_; $a; } |
and false similarily as a function that returns its second argument:
|
1 2 3 4 |
my $false = sub { my ($a, $b) = @_; $b; } |
Now we can represent the conditional if as a function of three arguments:
|
1 2 3 4 |
my $if = sub { my ($test, $consequent, $alternative) = @_; $test->($consequent, $alternative); } |
It just applies the truth value to the consequent and alternative arguments, so if is just syntactic sugar.
What about data structures? The simplest composite data structure is a pair, and we can do that with functions too:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
my $cons = sub { my ($car, $cdr) = @_; sub { my (selector) = @_; $if->($selector, $car, $cdr); } } my $car = sub { my ($pair) = @_; $pair->($true); } my $cdr = sub { my ($pair) = @_; $pair->($false); } |
so a pair is a function that takes a truth value and returns the car if it is true and the cdr if it is false, and car and cdr are functions that pass the appropriate truth value to the pair.
(I need to talk here about Church Numerals, when I can figure them out.)
Currying all of the above is left as an exercise for the reader.
So what does the lambda calculus actually look like? Well, it’s very terse. Functions are created by
where λ.x body
is the argument, and are called like x
where fa
is the function and f
the argument. Of course you can use brackets to disambiguate, but that’s it, nothing more to it. Here’s my attempt at a definition for if:a
|
1 |
λ.t (λ.c (λ.a (tc)a)) |
I hope I got that right: a function taking argument t (test) returning a function taking argument c (consequent) returning a function taking argument a (alternative) which applies t to c, and applies the result to a (remember t is Curried). Phew!
Currying is quite a useful thing to be able to do given support from a language, but it can be difficult to read. For F♮ I hit upon the idea of using a trailing comma to indicate a partial function call:
|
1 2 3 4 5 |
fn add(a,b) { a + b; } def add2 = add(2,); add2(3); // 5 |
Which provides a visual clue to the reader that add() in this example is not being called with all of its arguments and therefore returns a function that expects the rest. Perhaps more practically, something like this is more visually appealing, once you get what the trailing comma means:
|
1 |
map(eval(env,) lst); |
where we map eval with a supplied first argument env over the items of lst. This avoids having to create a closure:
|
1 |
map( fn (l) { eval(env, l) }, lst); |