Ecumenicalculator
Behold, my entry to the OMGWTF competition: Ecumenicalculator!
What makes this apparently simple program WTF-worthy? Just this: it doesn’t use numbers.
Nowhere in the backend code will you see ints, shorts, longs, floats, doubles, or any other numerical types, or any operations on them, or invocations on any functions that accept or return them. (The GUI code does use some ints, but only to the extent that they’re needed to interface with GTK to actually do the drawing, and even then it doesn’t do any math on them.)
How is this possible? Well, the code does use bools, as well as the container classes provided by the STL. And, of course, plenty of my own classes, all of which adhere to the don’t-use-numbers constraint.
OK, but how is this possible? The code uses Church numerals to represent individual digits. So, naturally, I had to implement untyped Lambda calculus in C++.
But of course, Church numerals will only give you nonnegative integers. To represent arbitrary real numbers (OK, technically, only rational numbers), I do what most humans do when writing down numbers: I make a list of digits, with each position being “worth” a different amount. There’s a radix point after the ones digit, and optionally a negative sign in front. I accomplish this mainly by putting multiple Church numerals into an std::list, maintaining an iterator after the ones digit, and a bool to flag for negative numbers.
That’s why the program is called Ecumenicalculator: it does computations on a bunch of Churches working together!
*ducks*
Needless to say, writing something like this without ever explictly using numbers provided by the language can get pretty interesting, especially when you need to do something like reference counting objects (since copying them eats up all available memory). C++ is also most definitely not a language well-suited for implementing untyped Lambda calculus.
Here’s some representative excerpts from the source code to demonstrate some of the hijinks that are going on to pull this off:
static const MyDigit radix (MyDigit ().successor ().successor ().successor ().successor ().successor ().successor ().successor ().successor ().successor ().successor ());[calculator.cpp:39]
Well, how else are you going to get 10 when you haven’t created any other numbers yet? Compute the number after the number after the number after the number after the number after the number after the number after the number after the number after the number after zero!
typedef Curry< Curry< Curry<AddImpl> > > Add;[church.h:235]
How can you not like recursive class template instantiation? Each Lambda expression class’s operator() only takes one argument, so when you need four arguments, you need to do some Currying. Making currying a class template lets you write the currying code once and apply it wherever you want.
Lambda result = band (iszero (sub (_numeral) (rhs._numeral))) (bnot (iszero (sub (rhs._numeral) (_numeral)))) (t) (f);[church.cpp:173-174]
Thanks to operator(), it’s possible to write code that looks downright functional. Can you tell what that line is computing? (Hint: the variables all have obvious names.) Also, I think if I can work in five more sets of parentheses somewhere in there, I become an honorary Lisp programmer.
delete this;[lambda.cpp:71]
You probably never want to do that unless you know what you’re doing.
If you want to see more (including recursive Lambda calculus expressions and a subtraction algorithm that guarantees you’ll never try to borrow from a zero), now that the entry deadline has passed, you can download the source for Ecumenicalculator and try it out.
5 Responses
um… woah…
Awesomely done Paul.
I like the pun in the name, though I’m slightly disappointed you didn’t call it Kuliniculator. I really want to see the “Kulini-” brand grow beyond… well… fiction. I mean seriously if Apple can grow the iBrand, you should be able to out do them, you have an i, plus a Kulin! You should totally be able to beat them.
Oh god, that makes me laugh… awsomeness.
Dammit. Your entry is so much better than mine. I implemented Robinson arithmetic (called it Calc-Q, geddit?), so, kinda similar: L(=; S, 0);
The problem I hit is that the performance was terrible. And I wasn’t even using actual successor functions, just a string representing a series of them. I ended up having to implement a whole bunch of memory munging functions to get some of the test cases working fast enough (~20s for some).
I guess you wouldn’t have that problem with Ecumenicalculator because it doesn’t use an axiomatic approach. To illustrate, mine had to instantiate axiom Q5 600,000 times for one of the test cases. The result was that all the performance crap took all my time, and I couldn’t get the code nicely abstracted and clean. Yours shines.
You got through to the finals, right? You must have. Surely. If you didn’t the whole competition isn’t worth a damn.
Supposedly they already e-mailed the finalists, and I received no such e-mail, so I assume I didn’t make it. They must have something against the theoretical math or comp sci approaches to the problem, instead of just seeing how many pointless layers you can throw into the design without rhyme or reason.
The thing I’m most proud of Ecumenicalculator is that, aside from the decision not to use “normal” numbers, all the other seemingly strange things about its design has a solid and legitimate justification for it.
And my code is no speed demon either. For the more expensive operations (subtraction and division), I pass explicit Successor and Zero expressions just so the runtime can evaluate parts of the expression, instead of just building up a bigger and bigger lambda expression. The reference counting is there because without it, my laptop would run out of memory before getting anywhere close to finishing any nontrivial division problem. Copying doesn’t work so well when you’re making millions of temporary objects, after all.