Scala: π and Streams

I finished my course of "Functional Programming Principles in Scala" at coursera¹.

Go me!

Wikipedia³ has an article on how to compute π. The series is provided below (using MathML², which might not work as it should in some browsers) originally proposed by Srinivasa Ramanujan.

$$\frac{1}{\mathrm{\pi }}=\frac{2\sqrt{2}}{9801}{\displaystyle \sum _{k=0}^{\infty }\frac{\left(4k\right)!\left(1103+26390k\right)}{{\left(k!\right)}^4{\mathrm{396}}^{4k}}}$$

Factorial

To compute the equation above, I'm going to use BigDecimals⁵ and I shall have to define some math operations.

So let us start with the Scala version of Factorial, which is equivalent to the Java Version of Factorial of my earlier blog post⁴.

Notes on Scala

I really like how Scala almost always infers the correct type automatically and can redefine common math operators for classes like BigDecimal. When dealing with BigDecimals, this is great. It makes it ideal for DSL, Domain Specific Languages. Compare the factorial calculation with BigDecimals below in Java and Scala for example:

Java:
return factorial(accumulator.multiply(n), n.subtract(BigDecimal.ONE));

Scala:
factorial(accumulator * n, n - 1)

I also like the fact I can define Worksheets in Scala, that are evaluated by the IDE upon saving, printing the results at the end of the line. For mathematicians it's the computerized equivalent of paper napkins in Restaurant, only better.

Square Root

There is a Square Root function available in the math library of Scala⁶, but it doesn't work with BigDecimals (def sqrt(x: Double): Double).

A way to compute a square root is using "Heron's method"⁷. That one can also be defined using recursion, similar to the Factorial above.

It is quite obvious that there is a problem in the code above. It is recursive, and the recursion never stops, leading sooner or later to a nice StackOverflow Error.

Some ways to solve it is to limit the number of iterations, or stop once the precision is adequate. An example of the first is seen below, where the number of iterations is 100.

But, it is slightly ugly. During the course, I learned that Scala tries to adhere to the Rules of Mathematics more than to the Rules of Programming. We should be able to define a pure function, without having the computer explode.

Streams

Scala has several ways in which functions get evaluated:

strict evaluation

Functions get evaluated immediately. For normal parameters and val definitions. This is the default.

lazy evaluation

Functions get evaluated when the function is called for the first time, and the value is cached and not recomputed.

by-name evaluation

Functions get evaluated each time the function is called. For "def" functions.

Streams are a way of creating data structures that are not evaluated immediately. An example of the use is shown in the following implementation of squareRoot:
The above example, barring the Stream calls, is equivalent to the first example of the squareRoot. Thusly we have defined something much more equivalent to an infinite series.

As you can see squareRoot(2) will get evaluated to Stream(1, ?). So only the head is evaluated, the first guess, and the rest is deferred, visible by means of a "?".

In order to force the evaluation of the rest, you can try for example squareRoot(2).take(5).toList, where take creates a new Stream that has a fixed length of 5. The toList forces the evaluation, as a list only knowns strict evaluation.

Now we should have all the ingredients to implement the equation visible at the top of this blog.

Computing π

In the example above, the actual number of terms in the series is 5, which is sufficient as the series converges extraordinarily rapidly to π.

In the example above, we are also using our new squareRoot function, this time with the number of iterations set to 120.

Of course, actually producing the exact result is impossible, but in Mathematics, I find that in most cases the definition is the important part, in order to reason about it.

References

[1] Coursera - Functional Programming Principles in Scala

https://class.coursera.org/progfun-004

[2] MathML

http://www.w3.org/Math/

[3] Wikipedia - Approximations of π

http://en.wikipedia.org/wiki/Approximations_of_%CF%80

[4] Recursive Factorial in Java

http://randomthoughtsonjavaprogramming.blogspot.nl/2014/05/tail-recursion.html

[5] scala.math.BigDecimal

http://www.scala-lang.org/api/current/index.html#scala.math.BigDecimal

[6] Scala Math Package

http://www.scala-lang.org/api/current/index.html#scala.math.package

[7] Wikipedia - Methods of computing square root

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Wikipedia - Arbitrary precision arithmetic

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

Tail Recursion

As I work my way through my Course on Scala², I'm learning a thing or two about functional programming. I am also learning a lot about recursion.

Some of it is also applicable to Java.

It was sufficiently new and surprising to me that I felt it deserved a blogpost. You can find all sorts of information about it elsewhere on the web as well.

No Recursion

What we are used to programming in Java is working iteratively, i.e. loops.

So, let us say we wish to compute the factorial³, we simply use a loop.

Recursion

However, computing a Factorial has always been a very often used example to demonstrate the power of Recursion.


Unfortunately, there's a problem regarding recursion in Java.

Seeing as the method is calling itself, it keeps pushing the stack frames of the method on the stack, before calling itself. This causes a huge increase in memory, as you no doubt know. For all but trivial problems, this results in:

Testcase: factorialTest[28](FactorialTest): Caused an ERROR 
java.lang.StackOverflowError
at java.math.BigDecimal.negate(BigDecimal.java:2088)
at java.math.BigDecimal.subtract(BigDecimal.java:1267)
at recursion.Recursion.factorial(Recursion.java:30)

The above message is from the JUnit tests in my project⁶. It works fine, up to the last testcase, where a factorial of 10000 is requested.

Tail Recursion

The following is almost verbatim from the Scala course²:

“In general, if the last action of a function consists of calling a function (which may be the same), such final calls are called tail calls¹.”

“If a function calls itself as its last action, this is called tail recursion.”

“If a function calls itself as its last action, the function's stack frame can be reused. This is called tail recursion optimization.”

In the example of the chapter above, unfortunately, the recursion is not actually tail recursion. As you can see, after the recursion there is still the small matter of the multiplication to do. The multiplication is actually the last operation of the method.

So we need to rewrite the factorial to make use of an accumulator.

“Tail recursive functions are iterative processes.”

This means that a tail recursive function, if the compiler is any good, can be changed into what is effectively a loop. For more in depth information on what happens, see [5].

Notes

Scala does implement Tail Recursion Optimization. Unfortunately, Java does not. This means that in my project⁶ the last test case will fail in Recursion.java as well as TailRecursion.java with a StackOverflowError.

Tail recursion is often used in functional programming, and Java 8 has introduced lambdas which make functional programming a reality for Java. Therefore it is a shame that this optimization is not provided in Java (yet).

Efforts are underway to remedy this⁴.

I hear the syntax would look something like this:

return goto factorial(accumulator.multiply(n), n.subtract(BigDecimal.ONE));

One of the disadvantages is that this optimization makes it (a little) harder to examine stack-traces. But in my opinion, we can surmount this small obstacle easily.

References

[1] Wikipedia - Tail call

http://en.wikipedia.org/wiki/Tail_call

[2] Coursera - Functional Programming Principles in Scala

https://www.coursera.org/course/progfun

[3] Wikipedia - Factorial

http://en.wikipedia.org/wiki/Factorial

[4] OpenJDK Wiki - TailCalls

https://wiki.openjdk.java.net/display/mlvm/TailCalls

[5] Dr Dobb's - Tail Call Optimization and Java

http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044

[6] GitHub - Three Java implementations of Factorial (n!) using NoRecursion, Recursion and TailRecursion

https://github.com/maartenl/recursion

Scala Documentation - Glossary

http://docs.scala-lang.org/glossary/