DP and Recursion

A little thought about Lambda Calculus

Posted by DHZ on February 17, 2019

Functional or imperative ? — DP and Recursion

From the point of view of mathematics, DP and recursion are doing the same thing. More precisely, they are different program implementations of same mathematical solution.

Let’s take Fibonacci, the example that is always be the very first one to demonstrate DP or recursion.The definition of Fibonacci sequence is

fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

(Since we’re interested in recursion, not in the nature of Fibonacci numbers, this post will ignore the matrix form of computing Fibonacci numbers using linear algebra.)

If we just implement it by the definition, the program would be

val fib: Int => Int = n =>
    if (n <= 1) 1
    else
      fib(n - 1) + fib(n - 2)

in Scala or

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

in Haskell

Then you will observe that when calculating every $fib(n)$ , there are $2n$ calls of $fib$ , but only $n$ of them are different, e.g. $fib(5) = fib(4) + fib(3)$ and $fib(4) = fib(3) + fib(2)$ . $fib(3)$ is called twice in calculating $fib(5)$ . By careful calculation, you will find that the running time of the naive recursion is exponential. That’s why we need to use Dynamic Programming, e.g.

val fib: Int => Int = n => {
    val dp = new Array[Int](n + 1)
    dp(0) = 1
    dp(1) = 1
    for (i <- 2 to n)
      dp(i) = dp(i - 1) + dp(i - 2)
    dp(n)
  }

or maybe a more clever way, since we only need to know $fib(n-1)$ and $fib(n-2)$ to calculate $fib(n)$

val fib: Int => Int = n => {
    val dp = Array.fill[Int](2)(1)
    for(i <- 2 to n){
      	/* dp = [fib(i-2), fib(i-1)] */
        val temp = dp(1)
      	dp(1) = dp(0) + dp(1) /* dp(1) = fib(i) */
        dp(0) = temp /* dp(0) = fib(i-1) */
      }
    }

in Scala

Then you might think “Like I said! how can they be equivalent! DP has linear running time here!” Actually, it is really simple to make them be equivalent, when we have a cache to preserve those interim results.

A naive attempt could look something like this:

val cache = new mutable.HashMap[Int,Int]

val fib: Int => Int = n => {
  if(cache.contains(n)) cache(n)
    else{
      var temp = 0
      if(n <= 1) temp = 1
      else temp = fib(n-1) + fib(n-2)
      cache(n) = temp
      temp
    }

So theoretically, recursion is equivalent to DP if we add a cache to it. Though there are still some problems with this nifty implementation, it indeed turns the fib that ran in exponential time into a fib which runs in linear time.

One problem is that it complicates our implementation of fib, the other one is that the cache sticks around after the function is finished running. For fib, this is not a problem, but for some algorithms it would be.

Let’s leave the problems to talk later and switch to Haskell now.

In purely functional language like Haskell, it becomes tricky to write DP, since you don’t have mutable variable and loop, but you can still do it by making use of the evaluation strategy called Lazy Evaluation, which means that when a value is needed, it is calculated, and kept ready in case it is asked for again. If we define some list, xs=[0..] and later ask for its 100th element, xs!!99, the 100th slot in the list gets “fleshed out”, holding the number 99 now, ready for next access.

So the implemetation would be

fib = (fibs !!)
    where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The trick is to cause the list to get created, and cause the list not to go away (by way of garbage collection) between calls to fib. The easiest way to achieve this, is to name that list. “If you name it, it will stay.”

A better solution is to write a memofunction to encapsulate the memoization logic. Let’s imagine we already have our magical memo combinator available. How would we use it? The first instinct might be something like this.

memo_fib = memo fib
	where fib 0 = 0
		  fib 1 = 1
		  fib n = fib (n-1) + fib (n-2)

While that certainly does something, it doesn’t do what we want it to do.The problem is that our fib function isn’t aware that there exists a memoized version of it so even if we cache it’s return value, it doesn’t access that cache. It just recursively calls itself. After thinking a bit about this, we might come up with this version, which will be correct and you can also easily extract a memo out by carefully making use of the lazy evaluation mechanism.

memo_fib = memo fib'
    where fib' 0 = 1
          fib' 1 = 1
          fib' n = memo_fib (n - 1) + memo_fib (n - 2)
          
memo f = (map f [0..] !!)

Or we can define a clever open_fib to make it use ‘open recursion’ rather than call itself directly.

open_fib :: (Int -> Int) -> Int -> Int
open_fib memo_fib 0 = 1
open_fib memo_fib 1 = 1
open_fib memo_fib n =  memo_fib (n-1) + memo_fib (n-2)

You can get unmemoized fib by using fix open_fib where fix f = let {x = f x} in x, which means that fib is the minimal fix point of the high-order function open_fib. We call the high-order function that produces a fix point of a function fix-point combinator.

Let’s expand the fix open_fib to explain what happens:

-- fix f = let {g = f g} in g
fix open_fib
= open_fib (fix open_fib)
= (\rec n -> if n <= 1 then 1 else rec (n-1) + rec (n-2)) (fix open_fib)
= \n -> if n <= 1 then 1 else fix open_fib $ (n-1) + fix open_fib $ (n-2)
= \n -> if n <= 1 then 1
    else (if n - 1 <= 1 then 1 else fix open_fib $ (n-2) + fix open_fib $ (n-3))
        +(if n - 2 <= 1 then 1 else fix open_fib $ (n-3) + fix open_fib $ (n-4))
= \n -> if n <= 1 then 1
    else (if n - 1 <= 1 then 1 else 
                               if n - 2 <= 1 then 1 else
                                                    ...)
        +(if n - 2 <= 1 then 1 else
                               if n - 3 <= 1 then 1 else
                                                    ...)

Notice that the use of fix allows us to keep “unravelling” the definition of open_fib: every time we hit the else clause, we product another copy of open_fib via the evaluation rule fix open_fib = open_fib (fix open_fib), which functions as the next call in the recursion chain. Because of the Lazy Evaluation Mechanism, open_fib would only evaluate the fix open_fib inside if it is needed, otherwise if the argument nof open_fib (fix open_fib) is 1 or 0 , then it would just return 1. So eventually we hit the then clause and bottom out of this chain.

Then we are prepared to define the memo combinator, which is a fix point combinator like fix , but generating a memoized memo_fib from open_fib , which can be used in the intuitive way.

memo :: ((Int -> Int) -> Int -> Int) -> Int -> Int
memo f = memo_f
   where memo_f = (memoList !!) 
         memoList = map (f memo_f) [0..]
        
memo_fib = memo open_fib

It only difference between memo and fix is that, we add a list to preserve the intermediate values.

There are two things we can do better. Firstly, the type of our memo function is ((Int -> Int) -> Int -> Int) -> Int -> Int. This means it’s not generic. Secondly, this memoimplementation is still too slow. It requires a traversal of the cache list every time we want to get a value out because lists have linear time indexing. The complexity of our memo_fib function is quadratic or so.To avoid the linear access time in our structure, we can use a binary tree instead of a list. Trees have nice, logarithmic time, access properties that we want.

All implementations of memo combinator above highly depends on Haskell’s Denotational semantics, or more concretely, Lazy Evaluation mechanism.

How do we abstract the memoization logic in an imperative way to solve the problems mentioned above?

Here’s what my first trial:

var fib: Int => Int = n =>
    if (n <= 1) 1
    else
      fib(n - 1) + fib(n - 2)

val memorize:(Int => Int) => Int => Int = f => {
  val cache = new mutable.HashMap[Int,Int]
  new Function[Int,Int] {
    def apply(arg: Int): Int ={
      if(cache.contains(arg)) return cache(arg)
      val temp = f(arg)
      cache(arg) = temp
      return temp
    }
  }
}

fib = memorize(fib)

It seems prefect, but there is a trap. If we change the name of function on line 18 from fib to memo_fib, the memo_fib would be a fake memo_fib which is unmemoized. The reason is that the fib in memorize is still the uncached ` fib, not memo_fib`.

The situation is really the same as we met in writing the Haskell version memo combinator. We saw two solutions, one is to make the fib to call the memorize fib in memorize function, another is that to define an open recursive version of fiband generates memo_fib directly by applying a fix point combinator memo on it.

The first solution is easy to implement

var fib : Int => Int = memorize(n => if (n <= 1) 1 else fib(n-1) + fib(n-2))

Since in most of imperative programming language, the evaluation strategy would be strict which means an expression is evaluated as soon as it is bound to a variable, the fix point combinator we used in Haskell is not working anymore.

We need to try the second solution with another fix point combinator that works in strict programming language, called

Y-Combinator

In order to achieve our objective of “capturing the essence of recursion in a function”, is to write this Fibonacci function without referring to the function in its own body. To put this another way, we’re going to look for an implementation which would let us write Fibonacci as an anonymous function, like this:

n => {
  if (n <= 1) return 1;
/* Problem: we have no name for ourselves that we can use here */
  return ???(n - 1) + ???(n - 2);
}

We can make a similar definition like what we did in Haskell

val genFib :(Int => Int) => Int => Int = fib => n =>
  if (n <= 1) 1
  else fib(n - 1) + fib(n - 2)

Obviously, this is not fib function, but if we call genFib with a fib, that we’ll get thefib that we want out of it. But there is the problem: The way we get the fib is by calling genFib with some argument:

val fib = genFib(?)

But the missing argument fib is the fib itself, which we can only get as the output of genFib:

val fib = genFib(genFib(?))

Which makes us need to write:

val fib = genFib(genFib(genFib(?)))

etc. We’re trapped in an infinite chain here; we need some way to “close the loop.” The y-combinator does this loop-closing. It is a fix point combinator which take genFib as an argument and return the minimum fix point of genFib which is the fib we want.

Since we have this idea, things becomes easier. We are sure that the yCom would look like this:

val yCom = genFib => genFib(f)

f is the result function we want, so we just expand f

val yCom = genFib => genFib(n => yCom(genFib)(n))

And we finished.

val genFib :(Int => Int) => Int => Int = fib => n =>
  if (n <= 1) 1
  else fib(n - 1) + fib(n - 2)

/* actually we can define yCom in type ((a => b) => a => b) => a => b, but in scala */
/* we cannot make arrow function generic. You can define a generic yCom using def keyword.*/
val yCom:((Int => Int) => Int => Int) => Int => Int = 
	gf => gf(n => yCom(gf)(n))

val fib = yCom(genFib)

Let’s break down how this works.

When we call fib n, we’re calling the genFib function returned by yCom. if n <= 1 then it will just return 1. If n > 1 , genFib will create new function called yCom(gf) and call yCom(gf)(n-1) and yCom(gf)(n-2), which is equivalent to call fib(n-1) and fib(n-2). This is exactly the behaviour we want.

The Y-combinator encapsulates the essence of recursion, so we can modify it to make a yComM which provides a recursion which is memoized using a cache.

val yComM: ((Int => Int) => Int => Int, mutable.HashMap[Int, Int]) => 
      Int => Int = (gf, cache) =>
    gf { n =>
      if (cache.contains(n)) cache(n)
      else {
        val temp = yComM(gf, cache)(n)
        cache(n) = temp
        temp
      }
  }

val genFib: (Int => Int) => Int => Int = fib =>
    n =>
      if (n <= 1) 1
      else fib(n - 1) + fib(n - 2)

val memo_fib = yComM(genFib, new mutable.HashMap[Int, Int]())