Friday, March 29, 2013

On CPS Part 1

"O, many
Have broke their backs with laying manors on 'em
For this great journey. What did this vanity
But minister communication of
A most poor issue?"
-- Shakespeare
Henry VIII
Act I, Scene I
Lines 83-87

I've moved further along in my journey of functional programming.  I find myself in a densely wooded forest of colossal pine trees.  The smell of juniper fills the air, bring with it memories of winters gone by.  This forest is where continuation lives.

Continuation-passing style is programming with no return, literally there is no return statement when you use continuation-passing style (CPS).  Instead what you do is pass in the function which you would like the function you are calling to return its result to.

Simple CPS example

Say you have function called f and you want f to take what ever value you give it and pass it to another function you give it that well call k.



In F# (on tryfsharp)

let f = fun x k -> k(x)


> val f : x:'a -> k:('a -> 'b) -> 'b


What we do is pass a function through k which takes one argument, like this:


f 5 (printfn "%d")



> 5
val it : unit = ()


FizzBuzz example

Lets do my favorite kata FizzBuzz using CPS.

First we make the fizzer and buzzer.


In F# (on tryfsharp)

let xzz n (w:string) =

    fun x ->
      match x with
      | x when x % n = 0 -> Some(w)
      | _ -> None
  
  let fizz x = (xzz 3 "Fizz") x
  
  let buzz x = (xzz 5 "Buzz") x

> val xzz : n:int -> w:string -> x:int -> string option
> val fizz : x:int -> string option
> val buzz : x:int -> string option


We now have a fizzer and a buzzer which will return string options.

Now let's make the fizzBuzzer using these functions.  We'll also use List.choose so we'll have either ["Fizz"], ["Buzz"], ["Fizz";"Buzz"], or [] as a result of applying fizzer and buzzer against the numerical input.  We'll then use List.reduce to concat the possible ["Fizz";"Buzz"] result.

In F# (on tryfsharp)



let fizzBuzzer n k =
  match [fizz; buzz] |> List.choose (fun f -> f n) with
  | [] -> k(n.ToString())
  | x -> k(x |> List.reduce (+))



> val fizzBuzzer : n:int -> k:(string -> 'a) -> 'a


Note this uses the fizz and buzz from before.

In order to consume this CPS version of FizzBuzz you could do the following:


 let p = (fun x -> printfn "%s" x);;
  fizzBuzzer 2 p;;
  fizzBuzzer 9 p;;
  fizzBuzzer 10 p;;
  fizzBuzzer 30 p;;

> val p : x:string -> unit

> 2
val it : unit = ()
> Fizz
val it : unit = ()
> Buzz
val it : unit = ()
> FizzBuzz
val it : unit = ()

The great thing about CPS with TDD is that you can pass what you are testing its own test case (see Full FizzBuzz example below).  I'll have more on CPS, once I wrap my head around it fully.  I am working on understanding one of the best responses I've seen on StackOverflow.


Full Fizz Buzz example in F# (with FsUnit):

open NUnit.Framework

open FsUnit

let xzz n (w:string) =
  fun x ->
    match x with
    | x when x % n = 0 -> Some(w)
    | _ -> None

let fizz x = (xzz 3 "Fizz") x

let buzz x = (xzz 5 "Buzz") x

let fizzBuzzer n k =
  match [fizz; buzz] |> List.choose (fun f -> f n) with
  | [] -> k(n.ToString())
  | x -> k(x |> List.reduce (+))

[<Test>]
let ``Validate that 2 can be Done`` () =
  (xzz 2 "Done") 2 |> should equal (Some("Done"))

[<Test>]
let ``Validate that 2 can not match`` () =
  (xzz 42 "Wrong") 2 |> should equal None

[<Test>]
let ``Validate that 6 is Fizz`` () =
  fizz 6 |> should equal (Some("Fizz"))

[<Test>]
let ``Validate that 5 is not Fizz`` () =
  fizz 5 |> should equal None

[<Test>]
let ``Validate that 10 is Buzz`` () =
  buzz 10 |> should equal (Some("Buzz"))

[<Test>]
let ``Validate that 3 is not Buzz`` () =
  buzz 3 |> should equal None

[<Test>]
let ``Validate that 2 is 2`` () =
  fizzBuzzer 2 id |> should equal "2"

[<Test>]
let ``Validate that k can be assert`` () =
  fizzBuzzer 2 (fun x -> Assert.AreEqual("2", x))

[<Test>]
let ``Validate that k can be shoulded`` () =
  fizzBuzzer 2 (fun x -> should equal "2" x)

[<Test>]
let ``Validate that 9 is Fizz`` () =
  fizzBuzzer 9 (fun x -> should equal "Fizz" x)

[<Test>]
let ``Validate that 20 is Buzz`` () =
  fizzBuzzer 20 (fun x -> should equal "Buzz" x)

[<Test>]
let ``Validate that 30 is FizzBuzz`` () =
  fizzBuzzer 30 (fun x -> should equal "FizzBuzz" x)