OddThinking

Aside on Church Numerals

Let me start with an aside.

Functional programmer nerds tend to play happily with ideas that either revolutionise the way you look at the rest of programming or leave your brain so far underwater, a mere snorkel won’t do – SCUBA equipment is required.

Church Numerals are an example of one of those ideas applied to the whole of mathematics.

It throws away the whole concept of integers, and replaces them with functions – functions that themselves take another function as a parameters, and apply those parameters to themselves, over and over.

I won’t try to explain them in detail here. If you don’t know what they are, ask a functional programming nerd one day when you’re next to a whiteboard, and when you have plenty of time available afterwards for your brain to slowly rise up from the depths to avoid the bends.

Aside on the Language

I was once paid to work on a compiler for a small functional programming language.

The functional language was cute and very small. I noticed once that the following code was valid:


where where where where where where where where = @where


For the record, it compiled perfectly, first time, and resulting code returned the identity function. I showed it to my supervisor, and he made me add extra code to make “where” a reserved word, and prevent this from compiling!

The Challenge: The Oddness of Two

I set out one week to implement the most complex program ever written in in this little language: a tool to determine whether two was odd or even!

Sure it sounds trivial; you might implement it in a typical language as:


isEven(x) = 2*floor(x/2) == x


or


isEven(x) = x % 2 == 0


or even, as Bream Le Fish once suggested,


isEven(x) = (-1)^x == 1


However, this language had no fancy-pants features like exponentiation, modulo or floor functions. For that matter, it didn’t have any built-in types or integer literals like “2”.

I was confident enough to swim at the deep-end of the lambda-calculus swimming pool back then, so that was not an issue. Church Numerals would provide the concepts of integers, dual-recursion between the isOdd and isEven functions would provide the definitions of odd and even.

A Stumbling Block

I was surprised to find that I couldn’t get the Church Numerals to work. My compiler (perhaps “instrumenter” is a more accurate name) accepted the source, and correctly generated Miranda code, without bothering to specify the typing information. That was normal. Miranda has a type-inference compiler. It looks at the way a variable is used, and determines the appropriate type based on its usage.

The Miranda type-inference engine, however, was balking at my generated code. It was complaining that this Church Numeral thing was a function that took a single parameter which was a function that took a single parameter, which was a function that took a single… well you get the idea. This infinite recursion had it confused – not unreasonably, I might add. I don’t know many languages whose typing systems would accept it.

I played with it for a while, trying different approaches, but I was stuck. I explained to my supervisor my problem, and explained it coudn’t be done.

“Hmmm,” he said, “I seem to remember something about this being mentioned at a conference I was at with David Turner.” I blinked at the name. David Turner invented Miranda, and was a semi-legendary creature to me. “Why don’t you email him and ask him.”

That was the first time I had ever written to a real-live language designer before – I was a little nervous. I was impressed to get a quick response, which explained that this was known issue – I was trying to push the typing system further than it was meant to go. However, there was a work-around. It was an undocumented pragma which, if put at the very, very top of a Miranda program, would switch off the type-inference system. Effectively, that turned Miranda from a strictly typed system (with type-inference to hide that fact) to a loosely-typed system.

Professor Turner was very polite, but I think I could guess what his opinion of this sort of behaviour was. My big clue was the name of the pragma: “%disgusting”.

For the rest of the project, all of my generated code was required to have, at the very, very top, a declaration that this code was, in fact, disgusting!

I meekly accepted my fate, and as a result, I can categorically confirm to you a long suspected result. After only half-a-page of debug output, the result was crystal clear. Two is an even number!