Memoization: Fibonacci Sequence

Memoization is an optimization technique that caches computationally expensive function calls. I first learned of it in Stanford's Algorithms class on Coursera.¹ It is more common in functional programming than object oriented programming because the function being cached can not have any side-effects, and that is, of course, often the case in functional programming. It is also commonly used by lazy data structures. The downside of memoization is that more memory will be used, but for some functions, as you will see below, it is well worth it.

A function that returns the nth Fibonacci number is the quintessential recursive function. I still remember that was the example used when I first learned of recursion. It is actually often implemented inefficiently, though, the standard recursive implementation being O(fib(n)) = 2ⁿ.

Python

Python makes memoization easy because you can decorate any function with a memoization function.

Scala

Scala does not make it that simple. Hopefully it will be built into the language in the future. This naive implementation only caches the original function call. The recursive calls do not know to use the memoized wrapper.


This blog correctly points out this problem with memoizing a recursive function and has a great technical explanation of the solution. In summary, you have to use something called a Y combinator to correctly implement the memoized wrapper function in Scala. It is basically a high-order function that returns a recursive version of a non-recursive function. I will defer to these other resources for a proper definition.


Notes

In Scala, for example, I could get up to n=45 in about 20 seconds with the standard un-memoized Fibonacci implementation. With the correctly memoized version I can run n=1000 in under 1 second because the memoized recursive implementation is O(fib(n)) = n.

The recursive Fibonacci implementation is not tail-recursive (which I covered in a previous blog), so you pretty quickly will hit a stack overflow error. In my Python implementation I even had to explicitly set the recursion limit higher than the default.

Also note the use of currying (which I also covered in a previous blog) in the nonRecursiveFibonacci Scala function.


1 I would highly recommend this class. It is better than the algorithms class I paid for to get my CS degree.

Fixing My Asynchronous Non-blocking I/O Callback Hell With Monads

In my previous post Asynchronous Non-blocking I/O Java Echo Server, I looked at non-blocking I/O from the Java perspective. My echo server used the callback functionality known as a CompletionHandler in Java 7, but it left something to be desired. Mainly I had a callback inside a callback inside a callback. Well, now Java 8 is released and I set out to fix it inspired by Monadic futures in Java 8: How to organize your data and avoid callback hell.

Monads surround computations and can take actions on them. They help chain computations together because they take in an action and then return a new monad surrounding the computations that had the action executed on them.

I am still trying to fully understand monads myself, so I am not going to act like I already do and give detailed information here. I think it's easier to understand from examples, anyway, instead of reading about category theory. The above definition will make more sense after looking at my new server code and seeing the chaining in action.

My New Server Code

A promise is a type of monad common around asynchronous operations. I used the new monadic CompletableFuture class to wrap my asynchronous computations.

My Thoughts

1. I like this better than my Java 7 version in terms of readability, but it would still be a lot cleaner without checked exceptions like in Scala.
2. This is not really non-blocking. Even though it is done asynchronously, I block waiting for a Future to complete three times. There is not a good relationship between Future and CompletableFuture to help avoid this as far as I can tell.
3. This Java 8 version is slower than the Java 7 version. My theory is that, even though the blocking calls are handled asynchronously by the CompletableFuture class, explicitly blocking the thread with the get() instead of letting Java handle it with a callback is what makes the difference.

There is not much Java 8 code out there to look at, so what would make this better? Can I get rid of the blocking get() calls somehow? Why is it slower than the Java 7 version?

Notes

A future represents a result that does not yet exist (and might not ever exist). Futures are read-only. A promise is the container that completes a future. Promises are writable.

UPDATE:

I posted a Scala version of this at Scala Asynchronous IO Echo Server.

Generators: Fibonacci Sequence

A generator returns a sequence of values, but unlike with a function the values are returned one at a time. This requires less memory for representing large (possibly infinite) sequences because the entire sequence is never stored in-memory at once. The sequence is computed, one value at a time, as needed.

Python


Scala

Exploring Tail Recursion

A tail-recursive function does not require a new stack frame for each call. All the recursive calls will execute in a single frame. This is benefiitial because you do not have to worry about recursing too deeply and getting a StackOverflowError, or the overhead of the many function calls.

What makes a function tail-recursive, and not just recursive, is that the call to itself is the last operation in the function. When this happens the compiler can generate bytecodes that are the same as if the function were written with a while-loop. These two examples from Programming in Scala are not only functionally equivalent, but would be optimized to have the same bytecode:


In Scala use the @tailrec annotation so you will get a compiler error if the function's recursion can not be optimized away.

Exploring Partial Functions, Partially Applied Functions, and Currying

I'm trying to learn more about functional programming. This is the third in a series of posts about functional programming concepts with examples in Scala (and in some cases other languages too).

Partial Functions

A partial function is a function only valid over a specific range. Some functions are not valid for all input values, like asymptotic functions or those only applicable to natural numbers.


Partially Applied Functions

A partially applied function is an expression in which you don’t supply all of the arguments needed by the function.


Currying

A curried function is applied to multiple argument lists. The results are chained together. In this simple example, the 2 would be applied to x + y resulting in 2 + y. Then the 3 is applied resulting in 5.

This technique can be used to make method calls look more like native-language support. Here is a non-trivial example from Programming in Scala:

Notes

Partial functions and partially applied functions are not related, except the names are almost the same. I was confused about this when I started to research this post.

The call to partially applied functions returns immediately. Curried functions return another function in the currying chain.