Denied

As anyone who was following last week’s announcements of the OMGWTF finalists, my own Ecumenicalculator failed to make the cut.

Apparently implementing a four-function calculator without using the language’s arithmetic operators — or numbers, for that matter — didn’t sufficiently tickle the first-round judges’ fancies. I don’t know if there’s going to be some kind of honorable mentions or anything, but implementing Church numerals and Lambda calculus in C++ to implement a calculator has got to be worth some props, right?

Now, some of the finalists look pretty good (judging from the writeups, at least). I do like the concept of an entry whose code base mimics a ailing multi-year development effort, and the one that does input through OCR and does computation symbolically on those user-defined “shapes”, and the one that implemented a virtual integrated circuit and then constructed the computation logic in terms of fundamental electronic components. So this post isn’t entirely sour grapes.

But several of the finalists are pretty hu-hum “let’s see how many pointless intermediate layers and Rube Goldberg chicanery I can fit in.” Yeah, there’s a WTF element to them, but there’s nothing particularly clever to the basic approach aside from finding the most arcane communications channels you can (like X window properties) to use. They’re lacking a unified overarching vision for why things are done the way they are. In Ecumenicalculator, aside from the “let’s not use any normal numbers or arithmetic” concept, all the other apparent strangeness has solid technical justifications for it.

If I had it to do over again, would I chance anything? Absolutely! I didn’t win with Ecumenicalculator, did I?

In hindsight, if I wanted a conceptual WTF approach (instead of Ecumenicalculator’s purely internal WTFery), I would do one based on Digital Rights ‘Rithmetic Management. In DRMCalc, the central premise would consist of two parts:

  1. Arithmetic operations are the precious intellectual property of DRMCalcCorp, and no one must be allowed to have it unless they pay for access.
  2. The user is a dirty rotten thief out to deprive DRMCalcCorp of its livelihood.

In other words, DRMCalc would answer the question “what would happen if the RIAA wrote a calculator?” DRMCalc would have some combination of the following features:

  • Each arithmetic operation (or “advanced” functions like trig) would be a separately installable module, in order to monetize potential revenue streams for increased functionality. (Hey user, if you like addition, you’ll love subtraction, only $49.95 per month!)
  • Each module will require a valid license key to operate. License keys would be based on a public key infrastructure; without the proper encryption and decryption keys, you can’t sign the inputs to the operation or decrypt the output.
  • Each module would phone home to a central server to verify that a license key hasn’t been revoked before accepting it. This would also allow detection of multiple users sharing a license key, which could lead to the key’s revocation.
  • Each module would also phone home each time a calculation is performed for, um, market research purposes. Also, DRMCalcCorp retains the rights to use all calculations you perform. (It’s in paragraph 175 of the EULA.)
  • Since arithmetic is the exclusive intellectual property of DRMCalcCorp, any other calculators on the system are violating DRMCalcCorp’s IP rights. On startup, DRMCalc would launch a stealthy, persistent set of processes to monitor system activity and sabotage any programs that look like they might be a calculator. (For example, running “killall -s SIGFPE gcalctool” will cause any running instance of GNOME’s calculator to think it crashed.) Covert channels are used to report such activity to the central server, since obviously use of an unlicensed calculator violates the EULA.
  • Advanced feature: DRMCalc would launch multiple instances of each module, which would use Byzantine consensus algorithms to prevent malicious user software from degrading DRMCalc’s accuracy. (I hear there’s programs out there that try to sabotage calculators!)
  • Really advanced feature: DRMCalc’s modules would periodically polymorph themselves to stymie reverse engineering efforts.

In other words, massive paranoia. Note that none of this has anything to do with the calculations itself, but rather comes out of a completely warped notion of what the calculator’s operational environment is going to be.

DRMCalc would actually probably be as much fun to write as Ecumenicalculator was, but given that there’d be no point in doing so aside from proving that it could be done, it’s not going to happen.

Crazy Subtraction Algorithm

For the curious, here’s a description of the unusual subtraction algorithm I used in Ecumenicalculator. This algorithm converts subtraction into something that looks like addition of two positive numbers, mostly. It has the advantage of guaranteeing that you’ll never try to borrow from a zero.

As a running example, let’s say we want to compute 937,105 – 172,910.

Step 0: Assure that both numbers are positive and that the second number is smaller than the first. If either of those conditions does not hold, either swap the numbers (and negate the result), or realize that you actually have an addition problem and not a subtraction problem.

Step 1: Line the two numbers up vertically, so that the decimal places line up. This step is the same as “normal” subtraction.

   9  3  7  1  0  5
-  1  7  2  9  1  0
===================

Step 2: Replace each digit in the second number with the value (10 – digit). Yes, this means that any 0 digits turn into a 10 “digit”. Deal with it.

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================

Step 3: Add each column, without propogating any carry digits.

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 15  2  9 15

Step 4: Starting with the rightmost column and working left: if the “digit” is greater than or eqal to 10, subtract 10 from it; otherwise, leave it alone and subtract 1 from the “digit” to the left.

This will be easier to illustrate one column at a time. The rightmost one is 15, so we simply subtract 10:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 15  2  9  5

The second-to-last column is 9, so we leave it alone but subtract 1 from the column to the left of it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 15  1  9  5

The antepenultimate column is now 1, so we leave it alone but subtract 1 from the column to the left of it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6 14  1  9  5

The fourth-from-the-right column is now 14, so we subtract 10 from it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  18  6  4  1  9  5

The fifth-from-the-right column is 6, so we subtract 1 from the column to the left:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
  17  6  4  1  9  5

Finally, the leftmost column is 17, so we subtract 10 from it:

   9  3  7  1  0  5
+  9  3  8  1  9 10
===================
   7  6  4  1  9  5

And lo and behold, 937,105 – 172,910 = 764,195.

Do you see why it works?

OK, here’s why it works. It’s actually very similar to regular subtraction, just with optimistic borrows and doing the operations in a different order. Take an arbitrary column in the original problem, where we want to compute ab. If ab, we simply compute ab = c and are done with it. However, if a < b, we borrow: we compute (a + 10) – b = c and subtract 1 from the column to the left.

In the crazy algorithm, we instead start off by computing a + (10 – b) = d right off the bat. Note that a + (10 – b) = a + 10 – b, which is what we’d normally compute if a borrow were needed. And in fact, if d < 10, then a + 10 – b < 10 and so ab < 0 and a < b, exactly the condition we look for to decide to borrow. Thus, if d < 10, then c = d and we subtract 1 from the column to the left. Otherwise, we compute c = d – 10, which works because d – 10 = a + 10 – b = ab, which is the result for the column if a borrow isn’t needed. Q.E.D.

So there you have it, mathematical proof that this crazy-looking algorithm does in fact work. Also, each column’s intermediate result will always be greater than or equal to 1 (since the “digits” generated in Step 2 always range from 1 to 10 inclusive), so you never wind up trying to borrow from a 0.

And while I proved it for the base-10 case, it generalizes to any arbitrary base, as long as you replace any instances of 10 with your base of choice.

Ecumenicalculator

Behold, my entry to the OMGWTF competition: Ecumenicalculator!

Screenshot of 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.

Entry #100204 Submitted

After much feverish work, my entry to the OMGWTF programming contest has been submitted.

It may not be the most evil code I’ve ever written, but it almost certainly is the most breathtakingly needlessly elaborate code I’ve ever produced.

Of course, you’ll get the details on just what makes this code so amazing once the submission deadline passes, even though I’m pretty sure no one else would be crazy enough to implement what I’ve implemented.

Mwa ha ha ha! Mine is an evil laugh!

OMGWTF++

There are two essential components to my forthcoming entry in the OMGWTF competition. To avoid giving away any details of what I’m up to just yet, we’ll call these two components “the asylum” and “the inmates”.

These code names are obviously meant to evoke the saying “the inmates are running the asylum”. In this case, however, the inmates have also designed the asylum.

As of a few minutes ago, the asylum has been essentially completed. It’s currently filled with licensed architects inspecting the structure to make sure it isn’t going to fall down anytime soon. They’re baffled by some aspects of the design, to be sure, but it seems to be working as planned.

Hopefully they’ll be able to escape before the inmates take over. Then things are going to get seriously crazy. It’s quite likely the end result will be unlike anything anyone has ever created. Probably for good reason.

I’m also finding that C++ is a surprisingly fitting language for this project, both because it has some fairly crazy features (hi, templates!) and because it’s utterly unsuited to the fundamental paradigm those inmates can’t stop talking about.

Comments Off

OMGWTF

I am sorely tempted to enter The Olympiad of Misguided Geeks at Worse Than Failure Programming Contest (a.k.a. OMGWTF). The challenge: to write the most “Clever” (and possibly “Buggy”) calculator possible without being “Ugly” or failing the test cases.

Given the skeleton code provided, all that has to be done is to implement four functions:

  • One that adds two floating point numbers.
  • One that subtracts them.
  • One that multiplies them.
  • One that divides them.

Of course, a “Correct” solution is downright trivial, obvious, and straightforward. “Correct” is also not a judging criterion.

I’ve got some ideas for ways to attack this, though (un)fortunately I don’t see a good way at the moment to use Church numerals with floating point. But that’s hardly my only idea.

Ultimately, the question is: can the Code Master General code like a Code Master Second Lieutenant?

[Editor’s note: This is also not the post I alluded to, um, two posts ago now.]