A CPS question and answer

Continuation passing style is a hard concept. Recently one fellow pasted the following piece of Haskell code in IRC and asked for its meaning:

cfold’ f z [] = z
cfold’ f z (x:xs) = f x z (\y -> cfold’ f y xs)

cfold f z l = cfold’ (\x t g -> f x (g t)) z l

It is a fold implemented in continuation passing style. Let's see what we can say about the type of cfold'. The function cfold' takes a function f of three arguments. The first argument of f is of some type t, the second argument is of some type t1, and the third argument is another function. The other function takes one argument of type t1 and its return value is the same as cfold's, that is, t1. Finally the return type of f is t1 as well. The second argument z of cfold' is something of type t1. The third argument of cfold' is a list of ts that is pattern matched in the definitions of cfold'. Thus, the type signature of the whole function is cfold' :: (t -> t1 -> (t1 -> t1) -> t1) -> t1 -> [t] -> t1.

Next, what can we say about the definition of cfold'? When the third argument, that is a list, is an empty list, it returns what ever is the value of its second argument of type t1. If the list is non-empty, we return what is returned by calling f when it is given x -- the head of the list (of type t), then z of type t1, and a function from t1 to t1.

At this point we start calling the first argument of cfold', that is f, a continuation. In the second definition of cfold' the control is passed to a continuation f. The continuation is a recipe of what to do next. The continuation is given the head of the list and a base value for the fold. The trailing anonymous function from t1 to t1 allows the continuation to get the result of the fold for the tail of the list.

Now, given the fold implemented in CPS, how do we, for example, multiply the elements of a list together? The continuation must contain that logic. Our continuation was a function of type (t -> t1 -> (t1 -> t1) -> t1). The first argument was the head of the list, the second argument was the base value for the fold, and the third argument was the way to get result of the fold for the tail of the list. So the definition for the continuation must be something like this:

(\x t g -> (*) x (g t))

It says that given the head of the list, x, a base value for the fold, t, and the function g that yields the result of the fold for the tail of the list when it is given t, the result of the whole fold is the list head multiplied by the value of the fold for the list tail.

Now cfold' alone is not describing much. We define cfold that passes the continuation, that does the actual folding, to cfold'.

If we try cfold with the sum function, a base value of zero and a one element list containing the number one, the expression reduces as below:

cfold (+) 0 [1]
(\f z l -> cfold' (\x t g -> f x (g t)) z l) (+) 0 [1]
cfold' (\x t g -> (+) x (g t)) 0 [1]
(\f z (x:xs) -> f x z (\y -> cfold' f y xs)) (\x t g -> (+) x (g t)) 0 [1]
(\x t g -> (+) x (g t)) 1 0 (\y -> cfold' (\x t g -> (+) x (g t)) y [])
(+) 1 ((\y -> cfold' (\x t g -> (+) x (g t)) y []) 0)
(+) 1 0
1

So for a non-empty list, cfold' calls the continuation, that performs the folding, and for an empty list it returns the base value.

Nondeterminism in Haskell

In nondeterministic programming an expression may have more than one value. In SICP we are given the following logic puzzle with its Scheme solution:

"Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?" (SICP, pp. 418)

A Haskell version of the (almost) same solution follows (Control.Monad and Data.List are needed):

type Name = String
type Floor = Int

adjacent :: Floor -> Floor -> Bool
adjacent a b = abs (a-b) == 1

distinct :: [Floor] -> Bool
distinct l = l == nub l

dinesman :: [[(Name,Floor)]]
dinesman = do
  baker <- [1..5]         
  cooper <- [1..5]         
  fletcher <- [1..5]
  miller <- [1..5]         
  smith <- [1..5]         
  guard (distinct [baker,cooper,fletcher,miller,smith])         
  guard (baker /= 5)         
  guard (cooper /= 1)         
  guard (not (fletcher == 1) || fletcher == 5))         
  guard (miller > cooper)
  guard (not (adjacent smith fletcher))
  guard (not (adjacent fletcher cooper))
  return [("Baker", baker),
          ("Cooper", cooper),
          ("Fletcher", fletcher),
          ("Miller", miller),
          ("Smith", smith)]

Nondeterminism allows us to omit writing the loops that try all possible execution paths. Nondeterministic computing can be imagined as if the computer simultaneously tried all the possible branches of a computation, where the computation branches every time there are multiple choices to proceed, and stops the branches that yield no result, and finally, returns all results from the succeeded branches.

Our nondeterministic process proceeds as follows. Initially we state that each person may live in any five possible floors. That makes 3125 different initial branches to take. The first restriction drops all branches where two or more persons would share the same room. That leaves 120 active branches. The next restriction drops all branches where Baker is living on the top floor. The next restriction drops all branches where Cooper is living on the first floor, etc. Finally what we have is one remaining branch that is the only solution to the problem.

To understand the code, let's take a look on Haskell's MonadPlus class. The class defines two operations:

class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a

The operation mzero denotes failure while the operation mplus denotes choice or combination. Here are the semantics of the operations:

mzero >>= f = mzero
a `mplus` mzero = a
mzero `mplus` b = b
a `mplus` (b `mplus` c) = (a `mplus` b) `mplus` c

The first reads that if a failure is applied on some action, the result is still a failure. The second reads that if something other than a failure is added to a failure, the result is the non-failure thing. The third reads that if a failure is added to something other than a failure, the result is again the non-failure thing. The two previous definitions are thus analogous to logical OR. The last one reads that the mplus binary operation is associative.

It appears that lists are instances of MonadPlus, defined as below:

instance MonadPlus [] where
mzero = []
a `mplus` b = a ++ b

The previous means that with lists, the empty list represents a failure and appending represents combination.

Let's go back to the code. The guard operation which we use to make restrictions on branches is defined as follows:

guard :: MonadPlus m => Bool -> m ()
guard True = return ()
guard False = mzero

So guard is an operation that takes a boolean expression and returns a () value meaning "no information" if the boolean argument evaluates to true, and mzero if the boolean argument evaluates to false.

So when a single branch runs a guard operation in our code, at that point, we have some combination of the floor numbers for each person. If the predicate is true, the branch will continue normally. If the predicate is false, the guard yields a failure. From the definition of MonadPlus, we remember that a failure applied on anything yields a failure. It means that the first failing guard will fail the whole branch. Succeeding branches will return a list of name-floor pairs. The return value of the function is just a combination of the results of all succeeded branches.

Does it work?
>> dinesman
[[("Baker", 3), ("Cooper", 2), ("Fletcher", 4), ("Miller", 5), ("Smith", 1)]]

On self study plans, again

Referring to my previous post, I have now, in the past few days, advanced deep into SICP's interpreter chapter (ch 4). Today I began reading the DIY Scheme interpreter tutorial previously mentioned. I managed to read the first five chapters, and I'm very satisfied so far. The tutorial does not try to teach elementary functional programming concepts, but maintains its scope by just showing how to write real software in Haskell.

Nowadays I'm rather busy writing my LLVM thesis and thus I have not yet got an opportunity to start reading RWH, a promise made a few posts ago.

Yaht is done

Referring to my previous post, I have now finished with Yet Another Haskell Tutorial. My intention was to do all of the exercises. I think I did over 90% of them which is good enough.

As mentioned earlier, my Haskell journey now continues with the Scheme interpreter tutorial. I'm also going to read through RWH as a side-side-project.

My favourite introduction to monads

It is said that the most difficult concept to grasp in Haskell is that of monads. I'm not trying to tell what monads are because it is already been done so many times and I'm not even expert enough to try that. Instead, I'm going to talk about my personal monad-learning experience.

A highly heterogenous set of monad tutorials have been written. Brent Yorgey recently posted a blog entry titled Abstraction, intuition, and the "monad tutorial fallacy" where he pointed out that the numerous metaphors given to monads, each of them purpoted to be _the_ methaphor that should make monads clear for everybody, are not helping but actually harming the learning process. The metaphors are actually hiding essential properties of the concept and thus making learning harder.

I didn't understand monads when I read that they are just like burritos either. I'm still uncomfortable with monads, but after reading several tutorials on the subject, I think I'm now starting to understand what they are useful for in pure, functional programming.

No single monad tutorial can be given the glory of having positively affected most my learning process. I think that after reading several examples of monad usage, I'm gradually grasping the idea of the abstraction they provide. The text that I feel is describing the subject in a very clear way, and that does not hide essential concepts, is Wadler's 1995 paper Monads for functional programming. The paper first describes several examples of tasks that are implemented unwieldy in a pure functional language without side effects. Then it proceeds to show how the same problems can be solved better using monads. The three monadic laws are given, as they should be, and in the end a parser implemented with monads is described.

My point is that people shouldn't be afraid of the original papers. Sometimes they really are useful in _learning_ the subject although occasionally they get lost in their excessively rigorous handling (for being educational for laymen) of the subject.

Recursion with Y

The following is written in Literate Haskell style.

Let us first write a recursive Haskell function that tells if a natural number is even:

> isEven n = if (==) n 0 then True else (if isEven (pred n) then False else True)

From Lambda calculus, we know the Y combinator, which returns the fixed point function for any function f:

> y f = f (y f)

The definition above satisfies the fixed point definition of f(x) = x.

Now let us define the isEven function again now using Y:

> isEven' = y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))

Above, Y binds its function argument on f, which results in a recursive call:

y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True)) = (\f n -> if (==) n 0 then True else (if f (pred n) then False else True)) (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True)))

Partial application results in:

(\n -> if (==) n 0 then True else (if (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))) (pred n) then False else True))

Now let's ensure that the halting conditon for the recursion works. Let's pass it a zero:

(\n -> if (==) n 0 then True else (if (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))) (pred n) then False else True)) 0 = if (==) 0 0 then True else (if (y (\f n -> if (==) n 0 then True else (if f (pred 0) then False else True))) (pred n) then False else True)

The first condition evaluates to True and thus the whole expression evaluates to True.

If we pass an argument larger than zero, call it $, we get:

if (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))) (pred $) then False else True)

The first condition above is the recursive function itself, which returns True for zero. So we pass it the predecessor of n. If the predecessor of n is even, n itself must be odd. Otherwise n is even.

Now we can test that it works for some small values:

map (\n -> (n, isEven' n)) [0..5]
[(0,True),(1,False),(2,True),(3,False),(4,True),(5,False)]

Self study plans

Self studying is always fun. Currently, I'm learning Haskell by reading Yaht and doing all the exercises in it. Almost done. In paraller, I'm reading through SICP which Santa brought kindly to me. The idea is to kill two birds with one stone (that's a terrible, violent idiom!) by writing a Scheme interpreter in Haskell. There is a promising tutorial to do just that in Wikibooks. After Yaht is done and the interpreter chapter been read in SICP, I plan to start the interpreter project.

And the bad news: the taocp project is currently halted :(