Inside F#

Brian's thoughts on F# and .NET

Catamorphisms, part seven

Posted by Brian on June 7, 2008

The code in the previous blog entry was difficult to read due to the use of explicit continuations.  Today I’ll show how to make the code more readable using a continuation monad.  I’ll also discuss F# "computation expressions" (a.k.a. "workflows") in a little more depth.

(Today’s blog entry is probably the most "advanced" that I’ve written, as it deals with three advanced functional programming concepts (catamorphisms, continuations, and monads) simultaneously.  I’ll try to revert back to some beginner/intermediate F# topics (that may attract a wider audience) in future blog entries… but today I am just writing about things that tickle my fancy.)

The trouble with continuations

Continuations are an almost indispensable mechanism for achieving certain goals.  For example, in the previous entry I showed how to use KFold to process arbitrary tree-like data structures without using the call stack.  This is a win when you need to process large, arbitrarily-shaped (e.g. unbalanced trees) data.  However the resulting code suffered a bit in terms of readability.  Last time we ended up with code like

let Change5to0bstExplicitContinuations tree = 
    KFoldTree (fun x kl kr (Node(_,oldL,oldR)) k -> 
        if x < 5 then 
            kr (fun newR -> 
            k (Node(x, oldL, newR))) 
        elif x > 5 then 
            kl (fun newL -> 
            k (Node(x, newL, oldR))) 
        else 
            k (Node(0,oldL,oldR)) 
    ) (fun t k -> k t) tree

for changing one value to another in a binary search tree.  The weird bits now are that our lambdas take an extra "k" parameter at the end of the parameter list, and we write code using the "k" variables rather awkwardly.  Compare the code above to a simple, non-tail-recursive implementation of the same method which doesn’t use a fold:

let rec Change5to0bstUsingStack tree =
    match tree with
    | Node(x,oldL,oldR) ->
        if x < 5 then
            let newR = Change5to0bstUsingStack oldR
            Node(x, oldL, newR)
        elif x > 5 then
            let newL = Change5to0bstUsingStack oldL
            Node(x, newL, oldR)
        else
            Node(0, oldL, oldR)
    | Leaf -> tree

The main difference I want to highlight is this

            kr (fun newR -> 
            k (Node(x, oldL, newR))) 

versus this

            let newR = Change5to0bstUsingStack oldR
            Node(x, oldL, newR)

The latter code looks much more familiar, whereas the former code that explicitly uses continuations looks kind of odd/backwards and uses weird lambdas and parens that are hard to read/parse at a glance.

It turns out that we can leverage F# computation expressions to get better syntax for the continuation-version of the code.  By coding up the continuation monad, we can use continuation workflows, so that that little code snippet becomes

            let! newR = kr               
            return Node(x, oldL, newR)

In the long run, this is much more readable an understandable (especially if there are more than 2 lines of code) than the explicit continuations version.  But the "let!" and "return" keywords are pretty new to us (we saw them in passing in a previous blog about async workflows), so let’s pause and talk a little about F# computation expressions first.

How to read F# computation expressions

F# computation expressions are a syntax sugar for writing code where a portion of that code deals with a particular monad.  (I’m continuing to defer the discussion of exactly what a monad is, but if you’ve been keeping up with previous blog entries I’ve written, you know that parsers can be expressed as a monad, and asynchronous computations can be expressed through monads, and today we’ll see a monad of continuations.  Monads have many uses, but they are very abstract, and thus hard to explain without a lot of examples already under your belt.)  A computation expression takes this general form:

    foo { comp_expr_code }

where "foo" is a "builder" object for a particular monad, and then comp_expr_code is code written using a special subset of F# that can be used inside computation expressions.

Consider this "normal" F# code:

    let x = 3
    f()
    let y = g(x)
    h(y)
    x + y

Assuming that all these functions and values have nothing to do with the "foo" monad, we can lift this code into a computation expression for foos thusly:

    foo {
        let x = 3 
        do f() 
        let y = g(x) 
        do h(y) 
        return x + y
    }

When moving code into a computation expression, "let"s are unchanged, functions that are called just for effects are prefixed with "do", and the final value is prefixed with the "return" keyword.  The result is code with pretty much the same meaning, except that the whole expression has been lifted into the "foo" monad, which may change its final value and type.  If in this example, "x" and "y" had type "int", then the normal code results in an "int", whereas the computation expression results in a value of type "Foo<int>" where "Foo" is some data type associated with the monad described by builder "foo".

A concrete example will help – consider asynchronous computations.  In the example above, if "foo" is replaced with "async", then the result of the whole expression is an "Async<int>" – an asynchronous computation that will eventually yield a value of type "int".  Recall that "Async<‘a>" is the data type that describes asynchronous computations, and "async" is the corresponding "builder" object for the asynchronous monad ("async" and "Async<‘a>" are defined in the F# Control library).

In addition to "let", "do" and "return", which operate on "normal" values, there are corresponding keywords "let!", "do!", and "return!" which operate on monadic values.  In our previous example, "g" was a function that returned an "int", and "h" was a function that returned "unit".  Suppose, instead, that "g" returns a "Foo<int>" and "h" returns "Foo<unit>".  In that case, we could write

   foo {
        let x = 3 
        do f() 
        let! y = g(x) 
        do! h(y) 
        return x + y
    }

where we have added the "!" (usually pronounced "bang") to the lines using "g" and "h".  The "!" says that the expression being processed is monadic, and should be processed according to the semantics given by the corresponding builder object.  The results of these monadic computations still have "normal" values – so for example, even though "g" returns a "Foo<int>", the "let!" ensures that the type of "y" is simply "int".

Again, a concrete example helps – consider again async computations.  Suppose "g" returns an Async<int>.  The "let!" says to run that async computation to completion until it yields an "int" value, and then bind that value to "y".  Similarly, if "foo" were "async", then "do!" would run its async computation to completion to produce an effect.

In short, inside a computation expression, you use "let", "do", and "return" for "normal" values, and you use "let!", "do!", and "return!" for values with a monadic type that need special processing specific to the particular monad we are in (as described by the builder object).  As with LINQ in C#, it’s all just syntax sugar – the compiler desugars the code snippet above into

    foo.Delay(     fun () -> 
    let x = 3  
    do f()  
    foo.Bind(g(x), fun->
    foo.Bind(h(y), fun () ->
    foo.Return(x+y))))))

Now, it just so happens that, given particular interesting definitions of "Delay", "Bind", and "Return", you can make that little code snippet have all kinds of interesting effects (like async, or parsing, or continuations, or …) – that is the magic of monads.  But we’re getting ahead of ourselves – for now, at least you have a cursory introduction to the F# computation expression syntax.

Defining a continuation monad

A continuation monad in F# can be defined like so:

type ContinuationBuilder() =
    member this.Return(x) = (fun k -> k x)
    member this.ReturnFrom(x) = x
    member this.Bind(m,f) = (fun k -> m (fun a -> f a k))
    member this.Delay(f) = f()
let K = new ContinuationBuilder()

Unless you are trying to understand the mechanics of what is going on very deeply, you can pretty much just gloss over that definition – continuation monads are well-understood, and that’s what it looks like to write one in F#.  Generally this is code that would be off in a library somewhere, but this code isn’t in any of the standard F# libraries, so I’m writing it myself.

What is important is that, with this thing in hand, we can now write "continuation workflows", which are just computation expressions that use the "K" builder object to produce values in the monad of continuations.  Let’s see how to use it.

Leveraging the continuation monad to make our code more readable

Consider again our code that was traversing a binary search tree to replace values:

let Change5to0bstExplicitContinuations tree = 
    KFoldTree (fun x kl kr (Node(_,oldL,oldR)) k -> 
        if x < 5 then 
            kr (fun newR -> 
            k (Node(x, oldL, newR))) 
        elif x > 5 then 
            kl (fun newL -> 
            k (Node(x, newL, oldR))) 
        else 
            k (Node(0,oldL,oldR)) 
    ) (fun t k -> k t) tree

We can rewrite this code using the continuation monad thusly:

let Change5to0bst tree =
    KFoldTree (fun x kl kr (Node(_,oldL,oldR)) -> K { 
        if x < 5 then
            let! newR = kr               
            return Node(x, oldL, newR)
        elif x > 5 then
            let! newL = kl
            return Node(x, newL, oldR) 
        else
            return Node(0,oldL,oldR)
    }) (fun t -> K { return t } ) tree

Here are the changes relative to the previous version:

  • The final "k" parameter to each lambda has been eliminated.  Since the body of each lambda is now a continuation workflow (code of the form "K { … }"), the result will be a monadic value of the general form "fun k -> …", and so extra "k" parameter is now implicitly handled by the monad.
  • The "continuation-ness" of the "kl" and "kr" parameters is gone.  Recall that these parameters represent recursive calls on the left and right subtrees, respectively.  Whereas previously we had to call them using continuation-style syntax "kr (fun newR -> …", now we call them with more natural syntax "let! newR = kr".  We use the "!" form of "let" because "kr" is a value in the monad ("kr" is a continuation).
  • We don’t have to call a continuation on the final result, we just need to "return" it.  We are returning Nodes, which are "normal" (non-monadic) values, so we use the non-"!" form ("return" rather than "return!"). 

The types and behavior all work out just as in the original version – this code has the same semantics as the original version, it’s just easier on the eyes (especially so once you are already familiar with the F# computation expression syntax).

One more example

Let’s take a look at one more example of applying the continuation monad – using it on the "Eval" function, another running example in this blog series.  (Recall: that example has a data type called "Expr" to represent a tiny expression language, comprising integer constants, binary operators (Plus and Minus), if-then-else expressions, and "print" expressions.)  Here is the previous version of the "Eval" code, using explicit continuations (though slightly reformatted to make for easier comparison with the new version I’m about to show):

let EvalExplicitContinuations expr =  
    KFoldExpr (fun x _ k -> k x) 
              (fun kl op kr _ k -> kl (fun l ->
                                   kr (fun r ->
                                   match op with 
                                   | Plus -> k (l+r)
                                   | Minus -> k (l-r))))
              (fun kc kt ke _ k -> kc (fun c ->
                                   if c <> 0 then
                                       kt (fun t -> k t)
                                   else
                                       ke (fun e -> k e)))
              (fun ke _ k -> ke (fun e ->
                             printf "<%d>" e
                             k e))
              expr

Now here it is rewritten using the continuation monad:

let Eval expr =  
    KFoldExpr (fun x _ -> K { return x } ) 
              (fun kl op kr _ -> K { let! l = kl
                                     let! r = kr
                                     match op with 
                                     | Plus -> return l+r
                                     | Minus -> return l-r } )
              (fun kc kt ke _ -> K { let! c = kc
                                     if c <> 0 then
                                         return! kt
                                     else
                                         return! ke } )
              (fun ke _ -> K { let! e = ke 
                               do printf "<%d>" e
                               return e } )
              expr

This reads so much better.  In the case of binary operators (the second lambda), for example, I can read the code "aloud" as something like "Let ‘l’ be the value of the recursive call on the left-hand subtree, and let ‘r’ be the value of the recursive call on the right-hand subtree.  If the operator is ‘Plus’, return ‘l+r’, else return ‘l-r’."  The previous version with explicit continuations, though equivalent, is much harder to decipher, and doesn’t let you "read it aloud" nearly so easily.

Another thing worth pointing out in this example is the use of the "return!" keyword.  In the case of if-then-else expressions (the third lambda), the "read aloud" version goes something like "Let ‘c’ be the value of the recursive call on the condition expression.  If ‘c’ is non-zero, then the result is the value of recursing on the ‘then’ subtree, else the result is the value of recursing on the ‘else’ subtree."  Since "kt" and "ke" are monadic values (they are continuations that represent the recursive calls into the ‘Then’ and ‘Else’ subtrees), we use the "!" version of "return" to return the value. 

The source code

Here’s the code from today’s blog entry.

type ContinuationBuilder() =
    member this.Return(x) = (fun k -> k x) 
    member this.ReturnFrom(x) = x 
    member this.Bind(m,f) = (fun k -> m (fun a -> f a k))
    member this.Delay(f) = f()
let K = new ContinuationBuilder()

open System

// handy operator
let (===) = fun x y -> Object.ReferenceEquals(x,y) 

type Tree<‘a> = 
    | Node of (*data*)‘a * (*left*)Tree<‘a> * (*right*)Tree<‘a> 
    | Leaf 

//     4
//  2     6
// 1 3   5 7
let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf))
                    Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

let KFoldTree nodeF leafV tree =
    let rec Loop t k =
        match t with
        | Node(x,left,right) -> nodeF x (Loop left) (Loop right) t k
        | Leaf -> leafV t k
    Loop tree (fun x -> x)

// explicit continuations version
let Change5to0bstExplicitContinuations tree = 
    KFoldTree (fun x kl kr (Node(_,oldL,oldR)) k -> 
        if x < 5 then 
            kr (fun newR -> 
            k (Node(x, oldL, newR))) 
        elif x > 5 then 
            kl (fun newL -> 
            k (Node(x, newL, oldR))) 
        else 
            k (Node(0,oldL,oldR)) 
    ) (fun t k -> k t) tree

// plain recursive version (blows stack)   
let rec Change5to0bstUsingStack tree =
    match tree with
    | Node(x,oldL,oldR) ->
        if x < 5 then
            let newR = Change5to0bstUsingStack oldR
            Node(x, oldL, newR)
        elif x > 5 then
            let newL = Change5to0bstUsingStack oldL
            Node(x, newL, oldR)
        else
            Node(0, oldL, oldR)
    | Leaf -> tree

// version using continuation workflow
let Change5to0bst tree =
    KFoldTree (fun x kl kr (Node(_,oldL,oldR)) -> K { 
        if x < 5 then
            let! newR = kr               
            return Node(x, oldL, newR)
        elif x > 5 then
            let! newL = kl
            return Node(x, newL, oldR) 
        else
            return Node(0,oldL,oldR)
    }) (fun t -> K { return t } ) tree

// CreateZeroRightTree : int -> Tree<int>
let CreateZeroRightTree size =
    let rec Loop t n =
        if (n < size) then
            Loop (Node(0,Leaf,t)) (n+1)
        else
            t
    Loop Leaf 0
// make a big tree of 2 million nodes all going to the right
let bigTree = CreateZeroRightTree (2 * 1000 * 1000)
// call our tail-recursive function on it, to prove we get no StackOverflowException
Change5to0bst bigTree

///////////////////////////////////////////////////////////////////////////////////

// types capable of representing a small integer expression language
type Op = 
    | Plus 
    | Minus 
type Expr = 
    | Literal of int 
    | BinaryOp of Expr * Op * Expr     // left, op, right
    | IfThenElse of Expr * Expr * Expr // cond, then, else; 0=false in cond
    | Print of Expr                    // prints, then returns that value

let exprs = [Literal(42) 
             BinaryOp(Literal(1), Plus, Literal(1)) 
             IfThenElse(Literal(1), Print(Literal(42)), Print(Literal(0))) 
            ]
            
let KFoldExpr litF binF ifF printF expr = 
    let rec Loop ex k =
        match ex with 
        | Literal(x) -> litF x ex k
        | BinaryOp(l,op,r) -> binF (Loop l) op (Loop r) ex k
        | IfThenElse(c,t,e) -> ifF (Loop c) (Loop t) (Loop e) ex k
        | Print(e) -> printF (Loop e) ex k
    Loop expr (fun x -> x)

// EvalExplicitContinuations : Expr -> int
let EvalExplicitContinuations expr =  
    KFoldExpr (fun x _ k -> k x) 
              (fun kl op kr _ k -> kl (fun l ->
                                   kr (fun r ->
                                   match op with 
                                   | Plus -> k (l+r)
                                   | Minus -> k (l-r))))
              (fun kc kt ke _ k -> kc (fun c ->
                                   if c <> 0 then
                                       kt (fun t ->
                                       k t)
                                   else
                                       ke (fun e ->
                                       k e)))
              (fun ke _ k -> ke (fun e ->
                             printf "<%d>" e
                             k e))
              expr

// Eval : Expr -> int
let Eval expr =  
    KFoldExpr (fun x _ -> K { return x } ) 
              (fun kl op kr _ -> K { let! l = kl
                                     let! r = kr
                                     match op with 
                                     | Plus -> return l+r
                                     | Minus -> return l-r } )
              (fun kc kt ke _ -> K { let! c = kc
                                     if c <> 0 then
                                         return! kt
                                     else
                                         return! ke } )
              (fun ke _ -> K { let! e = ke 
                               do printf "<%d>" e
                               return e } )
              expr
                     
exprs |> List.iter (fun expr -> printfn "%d" (Eval expr)) 
// 42
// 2
// <42>42
printfn "press a key"
System.Console.ReadKey() |> ignore

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers

%d bloggers like this: