Category Archives: Functional Programming

UW CSE P 505 – Monads

Posted on by
Reply

Monads were created in response to the problems that arise when a pure functional programming language encounters the dirty impurities of the real world. One particular problem that vexed researchers and developers early on was how to represent file I/O in a language such as Haskell. Take a relatively straightforward method such as a function prints a string to the console. It’s pretty obvious that the entire purpose of the function is so that it can execute a side effect. It’s also not clear that this function has a return value. Indeed, in many procedural languages, methods such as Console.WriteLine in C# have a return type of void. Functions that have side effects and have no return value clearly aren’t functions in the mathematical sense.

To address this issue, languages such as Haskell differentiated between pure functions and actions, the latter which is a value that represents the result of a computation that may cause side effects. A monad encapsulates this notion of computations and their state, and provides a way to transition from one computation to the next based on the resulting action from the previous computation. This is known as the bind method, or simply “>>=”. Essentially, it takes the value “wrapped” in the state of the previous action, performs some computation on the unwrapped value, and then wraps the result with the monad. The other important method, return, explicitly wraps some value type “a” with the monad.
This is very abstract, so let’s look at the Haskell IO monad as an example. The bind method would have a function signature of type:

IO a -> (a -> IO b) -> IO b

In other words, given some action IO a, bind takes a function (call it F) that takes in the unwrapped type a and returns a wrapped type b, applies F to a and returns the resulting b “wrapped” in an IO action. Let’s look at how we would use bind to read a line from the user and output it back to the screen.

The getLine function in Haskell reads a line from standard input and has type IO String. putStrLn has a return type of IO (). We want to call getLine, take the resulting string from that, and call putStrLn with it. In the IO bind method, a is type String, b is type Unit (), and the mapping function F is putStrLn. The (a -> IO b) matches up with (String -> IO ())

The use of bind would look something like this:

getLine >>= \input ->
putStrLn (“You typed “ ++ input)

What this has accomplished is the separation of concerns between the side effects of an action with the results of an action. By encapsulating any state changes brought about by a computation inside of a monad, we retain the ability to interact with the results of these computations in a functional way. Thanks to the syntactic sugar that Haskell monads provide, we also get rid of a lot of boilerplate code that would normally be required to pass the state from one computation to the next, as well as any tedious checking that involves. One can easily imagine a scenario in an imperative language that consists of a series of nested if statements in the code that do null pointer checks on the results from a series of computations. The pseudocode of such a scenario might look like:

httpRequest = parseHttpRequest()
If (httpRequest != null)
{
	queryString = parseQueryString()
	If (queryString != null)
	{
		print(queryString)
	}
}

Haskell provides syntactic sugar in the form of the “do” notation:

Do
	Req <- parseHttpRequest()
	QueryString <- parseQueryString()
        putStrLn QueryString)

Where we could imagine there being some sort of monad that would wrap the imaginary request and querystring types returned from parseHttpRequest and parseQueryString respectively. This looks similar to the imperative style of coding where we define a series of computational, but what’s nice about the monad is that if at any point there is an error in the chain of computations, the rest of the computations in the do block are short circuited, bypassing the need for cumbersome if statements along every step in the computation.

This of course, only scratches the surface of what a monad is and what they can be used for, as evidenced by the plethora of guides out there written about them.

UW CSE P 505 Notes – Continuation Passing Style

Posted on by
Reply

Continuation passing style (CPS) is a style of programming wherein function calls are chained together. Each function in the chain performs some computation on a value and then passes the result of that computation on to the next function in the chain. Using this style, functions do not directly return a value. Instead, they return a function call. Exactly which function is called next is determined by making it an explicit argument to the current function.

Functions written in CPS will have the form … ->(a -> r) -> r in Haskell where “…->” denotes the set of argument values that this function does a computation on. This portion of the function signature would match up exactly with an equivalent function that did not use CPS. For example, a sum function would have signature Int->Int->Int in direct style, and have signature Int->Int->(Int->r)->r in CPS style. The difference lies in the (a -> r) –> r, that is, a function that takes as an argument another function that takes a value and returns a value, and that itself returns a value. (a->r) is the continuation and represents the next function in the chain that will be called. Note that the type of the argument a does not have to match the return type of r. The only constraint is that the return type of the continuation must match up with the return type of the current function.
This is abstract, so some simple examples can help illustrate what is going on. Consider the quadratic equation y =3×2 + 2x + 5. A function that solves for y given a value of x might look something like the following without continuations:

add :: Int -> Int -> Int
add x y = x + y
 
square :: Int -> Int
square x = x * x

mult :: Int -> Int -> Int
mult x y = x * y

solveQuadraticExample :: Int -> Int
solveQuadraticExample x = 
    add (add (mult 3 (square x)) (mult 2 x)) 5

With continuations, the code becomes:

addCont :: Int -> Int -> ((Int -> r) -> r)
addCont x y = \k -> k (x + y)
 
squareCont :: Int -> ((Int -> r) -> r)
squareCont x = \k -> k (x * x)

multCont :: Int -> Int -> ((Int -> r) -> r)
multCont x y = \k -> k (x * y) 
 
solveQuadraticExampleCont :: Int -> ((Int -> r) -> r)
solveQuadraticExampleCont x = (\k ->
multCont 2 x (\twoX ->
    squareCont x (\x2 ->
        multCont 3 x2 (\threeXSquared ->
            addCont threeXSquared twoX (\sum -> 
                addCont sum 5 k)))))

This can be invoked by passing in a top level continuation of type (Int -> r) to the solveQuadraticExampleCont. We can use the identity function:
solveQuadraticExampleCont 3 id which prints out 38 from the ghci REPL. The continuations serve to dictate what happens next with the result of the current function, with the order of operations and the intermediate values calculated made explicit. The continuations are somewhat analogous to callback functions. Event driven frameworks that use callbacks to define what happens next in an asynchronous call are a form of CPS. Indeed in Node JS, you will typically see nested anonymous callback functions chained together, as in this contrived example:

http.createServer(function (req, res) {
  parseHeaders(req, function(headers) {
	parseContentType(headers, function(contentType) {
		//....... do some stuff here
	})
  })
});

Where in the imaginary parseBody and parseQueryString methods, the second argument is a function that represents what is essentially a continuation to call next with the results of the current function. Often times, these callbacks in NodeJS will also have an error argument that is itself an error handling function. The power of continuations lies in this flexibility of being able to control the flow and add new functionality to existing functions (without the need to modify the code which might be in third party libraries) by defining their continuation. Indeed, continuations can be used to implement any form of non-local control flow, from exception handling to implementing Y combinators.