Monthly Archives: April 2012

Print all natural numbers up to 100 without loops nor conditionals.

This week I had to come up with an exercise for a lecture I was giving on Javascript’s support of higher order functions, anonymous functions and lexical scope, and was hard pressed to find something other than the canonical text book examples of map, find, fold etc. But I did want something bigger, something that made the students think about how to use it in a way that to work it without using higher order functions would be quite awkward.

So I ended up remembering an old interview question I’ve read about a few years ago. I’m not very fond of those interview questions, but as a problem leading to a solution based on clever use of the techniques exposed in the class this one did fit quite well. Here’s how the question go, if my memory serves me well:

Write a program to print all the natural numbers up to 100 (inclusive) without making use of any form of loop or conditional structure and without writing the numbers by hand.

When I’ve seen this for the first time I got quite a lot of head scratching going on. I thought about crazy ways to do this with the tools I was more used to, the imperative object oriented languages and they didn’t quite feel right. Then it dawned on me that it’d be fairly simple if only I changed the focus to the tools I was used to and decided to try something else — functional programming.

You see, I had recently learned from friend of mine about something called Church Numerals when he tried to explain to me what he had learned in college about Lambda Calculus and the idea behind them inspired me to come up with a solution based on function composition.

The idea itself was very simple, too! All I needed was to codify part of the problem as a function that printed a number and incremented it, and come up with functional composition tools to call that function 100 times. So here’s how the code ended up being written in Scheme:

And then I simply ported this code to Javascript so I could take to my students as a solution to the problem in case they needed it:

So that was it and I thought it was a nice solution. I shared it with my buddies on Google + and thought it was finished… except it wasn’t. Speaking with one of my colleagues at work he mentioned that it’d look quite odd in a language without support for closures, so I decided to take a stab at doing it in Java and coming up with “closures” of my own:

But then it was really unfair to Java. I mean, we’re trying to bend it to a solution using a paradigm not supported by the language! I kept thinking and came up with a very simple implementation in Java, although I do consider it cheating:

And why do I consider it cheating, do I hear you asking? That’s because, although we’re not writing any loop construct, the loop is clearly there through the recursion. And, even if we are not making any conditional processing, the compiler puts a test there to test if n is zero, and throw an exception if it is. Of course, since this version “cheats” to have a loop and conditional in disguise, it’s also the most flexible by far. It can print any number supported by the int data type as long as we don’t overflow our stack.

After reading this I figured that, if I was to cheat, I could cheat it in order to make it even simpler. I mean, if the problem only limits that we don’t write loops nor conditionals, we can easily make the compiler write them for us and call it a day. So I whipped out my C++ compiler and fed it the following code:

So, the compiler got quite busy looping over my array and calling the default constructor, stopping when he finished the whole array, but I didn’t write a single loop, right? After that I was too tired to continue coming up with weird implementations but I’m sure there are people out there that can make them quite interesting. I ended up writing an ugly beast in Scheme that did away with all the lambdas using macros, and I’m pretty sure the same can be done with C++ templates although I don’t know how. And I’m sure someone can make it work in C, although I can’t think of a version that doesn’t simulate closures right now. Anyway, that’s all for today, folks!