Golfing with Lambda Calculus
A little while ago I stumbled upon a golf challenge where you had to do run length encoding (RLE) on an arbitrary string, for example given the input string:
10+[>+>3+>7+>10+4<-]3>2+.>+.7+2.3+.2<2+.>15+.>.3+.6-.8-.2<+.<.
it must be converted to:
++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>++.>+.+++++++..+++.<<++.>+++++++++++++++.>.+++.------.--------.<<+.<.
This can be done very easily in Dart like so:
str.replaceAllMapped(new RegExp(r"(\d+)(.)"), (m) => m.group(2) * int.parse(m.group(1)))
Hah, too easy! So I challenged myself to make one in untyped lambda calculus instead.
Since lambda calculus doesn't have input or output we have to define an encoding scheme for strings, the one I prefer to use is a right-fold list of church encoded character codes. Church numbers are pretty simple, they look like this:
0 = λf.λx.x
1 = λf.λx.f x
5 = λf.λx.f(f(f(f(f x))))
16 = λf.λx.f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f x)))))))))))))))
Right fold lists are similar but f takes a second argument:
"FOOBAR" = [70, 79, 79, 66, 65, 82] = λf.λx.f 70 (f 79 (f 79 (f 66 (f 65 (f 82 x)))))
I started by prototyping in llama, a functional programming language I made that is basically untyped lambda calculus with some syntactic sugar.
The solution to the golf challenge in llama is pretty short considering it lacks pattern matching:
~\code "10+[>+>3+>7+>10+4<-]3>2+.>+.7+2.3+.2<2+.>15+.>.3+.6-.8-.2<+.<."
vFold code <"" 0> (\st\char st \str\num
(\b (uGE char '0') ((uLE char '9') <str~uAdd (uSub char '0')~uMul num 10> b) b) <(vConcat str~vGenerate (uIsZero num 1 num) char) 0>
) tFirst
The source code of the external functions used here can be found at https://lab.pxtst.com/PixelToast/llama/tree/master/stl
If you don't know much functional programming that probably looks like gibberish, in fact it probably looks like gibberish even if you do so i'll explain using dart as an example. In functional programming you can't loop over lists in the traditional sense, the most common operations are mapping and folding:
var input = [1, 2, 3];
// Multiply every element by two using a for loop
var output = [];
for (var x in input) {
output.add(x * 2);
}
// Using map instead
var output = input.map((x) => x * 2);
Mapping is pretty simple to understand, now an example for folding:
var input = [4, 5, 6];
// Get sum using a for loop
var output = 0;
for (var x in input) {
output += x;
}
// Get sum using a fold
var output = input.fold(0, (d, x) => d + x);
Pretty useful, the functional dart equivalent to my solution is:
var code = "10+[>+>3+>7+>10+4<-]3>2+.>+.7+2.3+.2<2+.>15+.>.3+.6-.8-.2<+.<.".codeUnits;
var output = code.fold(["", 0], (st, char) =>
char >= 0x30 && char <= 0x39 ? [
st[0], (char - 0x30) + st[1] * 10
] : [st[0] + new String.fromCharCodes(
new List.filled(st[1] == 0 ? 1 : st[1], char)
), 0])[0];
and finally, the Lambda Calculus code:
(λp.λq.(λb.λg.(λi.(λp.λq.λb.p q b)(q(λq.λj.λl.j((λq.λj.qλq.λl.(λu.g i j(λp.u)(g j(λq.λg.q(b(p(λp.λq.p q))(p(λp.λq.p(p q)))q g))(λp.u)(λu.u qλq.λu.g j i q(b l(p(λp.λq.p(p(p(p q)))))q u))))λp.p(λp.λb.q p((λp.λq.l(λp.l)(λp.λq.p q)(λq.p j q)q)p b))λp.λp.p)l q))(λp.p)(λp.p(λp.λp.p)λp.λp.p)(λp.λq.p)))(b(p(λp.λp.p))(p(λp.λq.p(p q)))))(λp.λq.λb.p(q b))λp.λq.q(λp.λq.λb.p(λp.λb.b(p q))(λp.b)λp.p)p)λp.λq.λb.q(q(q(q(q(q(p q b))))))
I got to this point by inlining all of the external functions used, compressing the large numbers using pow/mul/add, and obfuscating all the variable names. It's impressively small for what it does, ill probably golf with lambda calculus more.