Let me start with an aside.<\/p>\n
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.<\/p>\n
Church Numerals<\/a> are an example of one of those ideas applied to the whole of mathematics.<\/p>\n 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. <\/p>\n 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.<\/p>\n I was once paid to work on a compiler for a small functional programming language.<\/p>\n The functional language was cute and very small. I noticed once that the following code was valid:<\/p>\n 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<\/em> to make “where” a reserved word, and prevent this from compiling!<\/p>\n 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!<\/p>\n Sure it sounds trivial; you might implement it in a typical language as:<\/p>\n or<\/p>\n or even, as Bream Le Fish once suggested,<\/p>\n 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”.<\/p>\n 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.<\/p>\n 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<\/a> 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.<\/p>\n 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<\/em> accept it.<\/p>\n 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.<\/p>\nAside on the Language<\/h3>\n
\n where where where where where where where where = @where
\n<\/code><\/p>\nThe Challenge: The Oddness of Two<\/h3>\n
\n isEven(x) = 2*floor(x\/2) == x
\n<\/code><\/p>\n
\n isEven(x) = x % 2 == 0
\n<\/code><\/p>\n
\n isEven(x) = (-1)^x == 1
\n<\/code><\/p>\nA Stumbling Block<\/h3>\n