Saturday, October 25, 2014

Do it bottom up in the REPL!

Today I stumbled over a question on StackOverflow, where a poster faced difficulties with some homework. The task was to compute pi with the approximation

pi = 3.0 + 4 / (2*3*4) - 4 / (4*5*6) + 4 / (6*7*8) - ...
and he was getting nonsesical results. It followed 35 lines of Java code (not counting empty lines) and the request for help "because it must be submitted on tuesday".

Doing it the conventional way

It occured to me that Java lures beginners into writing some monolithical main method, and when it doesn't work, debugging begins.

Debugging is in some sense the dual to programming: in imperative programming, we assemble expressions and statements to a whole, the glue is, of course, mutable state. And the debugger is a tool to help you to do the reverse: you split that whole to be able to look at individual statements and expressions.

Doing it the functional way

But how if we could spare us this assembling and disassembling, and instead do it right from the start? This is, of course, not a new idea, and is well known by the name "bottom up". I am, for my part, strongly convinced that this is how to think when working in functional languages.

In praise of the REPL

For this, we need another tool, namely an interpreter, also called REPL (for read-eval-print-loop). As if to underline my theory, there is no REPL in Java (or, at least, it is very uncommon to use one), Frege has no debugger at all, whereas in Haskell, ironically, setting breakpoints is a feature of the interpreter ghci.

Ask a person whose favorite language you don't know to choose two out of compiler, interpreter and debugger. If the answer is "compiler and debugger" you can safely bet on C++, Java or C. If, however, the debugger is the least important tool, you found a functional or declarative programmer.

In the following, I'll work through the example using the Frege REPL, in the hope to show some reader with an imperative mindset how to "go about it" in a functional way. 

Going to the bottom

But before we can go "bottom up", we need to go "top down" mentally. At first, one needs to see that we have to compute a sum whose terms have a nice pattern (except the leading 3.0, of course). The key point is the smallest number in the products that serve to divide 4. Hence, we obviously need the positive even numbers, since the whole thing is based on them.

Going bottom up

We couldn't go deeper anymore for the moment, because we can write this directly in Frege:

frege> [2,4..]

Thanks to foresight of the REPL author, Marimuthu Madasamy, the REPL will print only an initial part of an infinite list, so we won't get kicked out at this point!
Now that we have that list of integers, it is time to remember that we will need floating point numbers instead, because Frege won't let us mix integers and reals in numerical computations. Nothing easier than that! Get back that previous line and change it accordingly:

frege> map Int.double [2,4..]

In principle, we could proceed in this way and modify the last expression further and further, until we arrive at the solution. It is, however, recommended to name important sub-solutions. I usually do this when the expression gets too complex, makes sense on its own or if it is a list I do not want to get recomputed always.

frege> evens = map Int.double [2,4..]
value evens :: [Double]

The friendly type checker ensures us that we have a list of Doubles, as was our intention.
Time to write the code for the terms of the sum:

frege> [ 4 / n*(n+1)*(n+2) | n <- evens ]

Surprise! This result is surely not what we want, as the terms should get smaller and smaller instead of bigger and bigger!
It turns out that the whole product should be in the divisor, not just the first term, so we just forgot a pair of parentheses.

But note how such an error would escape us in a compile-only setting until runtime. The bottom up method already pays off!

frege> [ 4 / (n*(n+1)*(n+2)) | n <- evens ]

Doesn't this look much better?
Now, we know that every second terms needs to be negative. If we only could apply negate to every other term! But wait, we can, of course:

frege> deltas = zipWith ($) (cycle [id,negate]) [4 / (n*(n+1)*(n+2)) | n <- evens]
value deltas :: [Double]

And this is it, essentially! We can now directly write a function that gives us pi, approximated with so many terms:

frege> p n = 3.0 + sum (take n deltas)
function p :: Int -> Double
frege> map p [0..10]
frege> map p [20..40]
frege> map p [1000]
frege> map p [10000]
frege> import Prelude.Floating
frege> Double.pi
frege> Double.pi - p 10000

Why wait until tuesday? We can submit monday.