This is a just-for-fun post. I’ll explore a C# implementation of a theoretical system called Lambda calculus.
It certainly isn’t practical. A calculation of the 25th Fibonacci number (75025) is not complex. An efficient algorithm can calculate it in just a few CPU cycles. A naïve recursive function can calculate it in 3 milliseconds. However, using Church numerals in a Lambda calculus takes 2300 times longer (7100 milliseconds).
The exercise may be pointless from a pragmatic perspective. However, it is interesting to see that the theory can be translated so directly into working C# code.
The Lambda calculus is a theoretical general-purpose model of computing (similar to Turing machines). It is based on function application. It allows you to define functions that call other functions. However, there is no concept of numbers, arithmetic, logical operators or libraries. It is “functions all the way down”.
A base type for the Lambda calculus can be declared in C# as follows:
delegate Fun Fun(Fun fun);
In C# the delegate keyword declares a method or function type: roughly speaking, a function pointer.
Thus, the lambda calculus is about functions that accept functions and that return functions.
Alonzo Church devised a clever scheme for doing arithmetic when you only have functions. He represented numbers by encoding them as repeated function applications. The number one is a function that calls another function once. The number two is a function that calls another function twice. The number three is a function that calls another function three times (and so on).
Using C#, they can be expressed quite simply:
Fun zero = f => x => x;
Fun one = f => x => f(x);
Fun two = f => x => f(f(x));
Fun three = f => x => f(f(f(x)));
Fun four = f => x => f(f(f(f(x))));
Fun five = f => x => f(f(f(f(f(x)))));
You can also download this as a cs file.
two is a function that takes a function (f). It returns a new function.
That new function is a function that accepts a parameter (x). It then returns the result f(f(x)).
Functions that return functions can get very confusing.
It is often easier to look at a chain of functions as just parameters to a single function.
For example, two might be equivalent to something like the following:
public Fun Two(Fun f, Fun x)
{
return f(f(x));
}
The number two is a function that applies another function twice.
Unfortunately, .ToString() does not print a friendly representation.
Without a translation scheme, it is difficult to check any results.
A helper function can translate Church numerals to C# integers. Using external state (a counter), a helper function can count the number of times that it has been invoked:
x => { counter++; return x; }
Of course, this isn’t pure Lambda calculus. This is because translating requires stepping outside the calculus.
The helper function can be wrapped into a utility that converts Church numerals to C# ints:
private static int counter; // Declared at the class level
Func<Fun, int> valn = n =>
{
counter = 0;
n( x => { counter++; return x; } )(null);
return counter;
};
Now, valn(two) will return the C# integer 2.
The successor function computes n + 1 (when given n). This has a straightforward encoding:
Fun successor = n => f => x => f(n(f)(x));
The following is roughly equivalent and might help explain the successor function:
public Fun Successor(ChurchNumber n, Fun f, Fun x)
{
Fun result = n(f, x); // The Church number n applies f to x, n-times
return f(result); // Apply f once more
}
The Wikipedia article on Church encoding has examples of other arithmetic operations. They can be translated almost directly into C#:
Fun predecessor = n => f => x => n(g => h => h(g(f))) ((Fun)(u => x))(u => u);
Fun subtract = m => n => n(pred)(m);
Fun add = m => n => f => x => m(f)(n(f)(x));
Fun multiply = m => n => f => m(n(f));
Fun exp = m => n => n(m);
Arithmetic and conditionals also translate almost one-for-one from the Lambda calculus:
Fun @true = a => b => a;
Fun @false = a => b => b;
Fun and = p => q => p(q)(p);
Fun or = p => q => p(p)(q);
Fun not = p => p(@false)(@true);
Fun isZero = n => n(x => @false)(@true);
// Less-than-or-equal
Fun leq = m => n => isZero(subtract(m)(n));
// Equals
Fun eq = m => n => and(leq(m)(n))(leq(n)(m));
It is similarly helpful to have a C# function that translates from the Lambda calculus to C# bools:
Func<Fun, bool> valb = p => p(@true)(@false) == @true;
valb(p) return the C# bool value true if p is a Church encoding of true.
Finally, it is now possible to implement the Fibonacci sequence.
A naïve C# implementation would look like this:
private static int Fib(int n)
{
if (n <= 1)
return n;
else
return Fib(n - 1) + Fib(n - 2);
}
A Church encoding of a Boolean proposition can be used as an if-then-else statement. The Fibonacci sequence is therefore a direct translation of the C#:
Fun fib = f => n =>
leq(n)(one) // if n <= 1
(x => n(x)) // then return n
(x => (add(f(predecessor(n)))(f(predecessor(predecessor(n)))))(x));
// else return f(n-1) + f(n - 1 - 1);
There are two things to note in fib: sub expressions and recursion.
I have used sub expressions (x => n(x)) rather than simply using n.
In theory, sub expressions are not needed.
However, C# uses tries to evaluate everything as soon as possible (it is eager).
Wrapping up calculation in a function has the effect of delaying evaluation until necessary.
This means that C# doesn’t evaluate the ‘else’ branch when n <= 1.
It avoids stack overflow exceptions.
The Lambda calculus does not allow direct recursion.
As a placeholder for recursion, I used the parameter f.
The parameter f needs to be a function such that f = fib(f).
This is what the Y combinator achieves:
Fun yc = f =>
((Fun)(x => f(x(x))))
(y => f(a => y(b => y(b))(a)));
Finally, this gives a Fibonacci function:
Console.WriteLine(valn(yc(fib)(five)));
Another helpful utility translates integers into Church numerals:
Func<int, Fun> cn = i =>
{
Fun result = zero;
for (int j = 0; j < i; j++)
result = successor(result);
return result;
};
The 25th Fibonacci number is calculated as follows:
Console.WriteLine(valn(yc(fib)(cn(25))));
These can by timed using System.Diagnostics.Stopwatch.
On my computer it takes, on average, 7100 milliseconds for the Church numerals calculation.
In contrast, it takes only 3 milliseconds (averaged over 5000 trials) for the naïve C# implementation.
While Church encoding is slow, I was surprised to find that it was “only” 2300 times slower.
Judging by CPU performance over time this would put a modern processor back to around early 80s performance. Not too bad.
Published 1 March 2015 by Benjamin Johnston.