About five years ago, a mathematical puzzle occurred to me. I eventually solved the puzzle, but I don't want to talk about that solution here. Instead, I want to talk about my first attempt at solving the puzzle, which was an utter failure. A glorious, spectacular failure. Perhaps the single most impressive failure of my career. Failures are often much more interesting than successes, but for some unfathomable reason, people are often reluctant to discuss them.
The Puzzle and My “Solution”
You don't need to understand the details of the puzzle to enjoy the failure, so if you're not familiar with SK combinators and their ilk, or if you just can't be bothered, then please skip ahead to the next section.
I was playing around with SK combinators one day when a puzzle occurred to me. Could I introduce new combinators that would allow me to linearize any combinator expression? Combinator expressions are normally binary trees, and are written using parentheses to indicate the tree structure. The convention is that parentheses on the left can be omitted. For example, ((w x) y) z can be written as w x y z, but w (x (y z)) cannot be written without parentheses. I wondered if I could introduce new combinators that would allow me to rewrite any expression into an equivalent expression with no parentheses. I called such a transformation “flattening”.
One of the standard combinators in the SK family is B, which has the rewrite rule
B f g x = f (g x)Reading this rule backwards works well for flattening small expressions—for example,
x (
y z) can be rewritten without parentheses as B
x y z—but I ran into problems using it to flatten larger expressions, so I quickly turned to a variation of B that swaps the first two arguments
R f g x = g (f x) This new combinator works well for flattening expressions of the form
c (
c1 c2 ...
cN). For example,
c (c1 c2 ... c7)
= R (c1 c2 ... c6) c c7
= R (c1 c2 ... c5) R c6 c c7
= R (c1 c2 ... c4) R c5 R c6 c c7
...
= R c1 R c2 R c3 R c4 R c5 R c6 c c7
Now, another combinator F works in conjunction with R to flatten more complicated expressions. F is defined as
F f g x y = f x (g y) For example, we can now rewrite
c1 c2 c3 (
d1 d2 d3)
as follows:
c1 c2 c3 (d1 d2 d3)
= F (c1 c2) (d1 d2) c3 d3
= R c1 F c2 (d1 d2) c3 d3
= F (R c1 F) d1 c2 d2 c3 d3
= R (R c1) F F d1 c2 d2 c3 d3
= R R R c1 F F d1 c2 d2 c3 d3
The complete rules for flattening are
- flatten(c) = c
- flatten(e c) = flatten(e) c
- flatten(c1 (e c2)) = flatten(R e c1 c2)
- flatten(e1 c1 (e2 c2)) = flatten(F e1 e2 c1 c2)
- flatten(e1 e2) = flatten(flatten(e1) flatten(e2))
where each
c is a simple symbol and each
e is an arbitrary expression.
Not So Fast
I run my solution by hand on a few examples and it works great. So I code it up, run it on my examples and get the same answers. Yippee! Next, I run it on a larger example and.........nothing. The computer justs sits there, mocking me. Obviously, I've got a bug somewhere that is causing infinite recursion.
I stare at my program for awhile, but I'm not seeing any bugs. Hmmm. I run it on a different example and it finishes this time. I print out the result and...whoa, that's a lot of output! I wonder how big the transformed expressions are? Ok, calculating the size of the result shouldn't be too hard. I whip up another program and print out a table of the maximum output for an input of size N.
N=1 max output=1
2 2
3 4
4 8
5 16
6 32
.
.
.
.
Quick! Guess the next value in the table! 64, right? RIGHT?!
.
.
.
.
.
7 273
.
.
.
.
.
Huh? 273? What the heck is that?
.
.
.
.
.
8 65,569
.
.
.
.
.
65,569?! You're joking, right?
.
.
.
.
.
9 4,294,967,361
.
.
.
.
.
4 billion? Well, that's just silly.
.
.
.
.
.
10 15,177,100,720,513,508,366,
558,296,147,058,741,458,143,
803,430,094,840,009,779,784,
451,085,189,728,165,691,939
What do you even say to a number like that? That's 1.5x1082. To put that in perspective, the number of atoms in the observable universe is estimated to be about 1080. No wonder my program was running slow! At a few billion operations a second, that calculation should only take about...um...carry the 3...dang, where's Art Benjamin when you need him?...let's just say a long time.
If you're curious, here's the function that describes the size of the biggest possible output for an input of size N:
- Biggest(N) = 2^(N-1), if N <= 6
- Biggest(N) = 2^Biggest(N-3) + 2*Biggest(N-3) + 1, if N > 6
And here's the input of size 10 that gives the absurd result above:
X (X X) (X (X X) (X (X (X X))))
Once I recovered from the shock of this experience, I did eventually come up with a very nice solution to the puzzle, based on ideas from postfix languages like Forth and Postscript, but nothing quite compares with getting an answer like 1.5x1082.
