The Push Monad: Introduction

Chapter 5 of Friendly F# has a great practical explanation of F# computation expressions often called “monads” from their use in computer science and Haskell. The material in Chapter 5 of the book does a lot to demystify the concept, theoretical coverage of which is done well in this Wikipedia article.

Monads are an example of things best grasped by actually doing. So I set out to implement one in my project.

What Friendly F# discussion instills above all (confirmed by the Wiki article) is that a monad in functional programming is a great way to subsume some common side effects or patterns under an explicit syntax that serves several purposes:

• Unclutter the code
• Make the pattern visible thus improving readability, while at the same time
• Avoiding “action at a distance” anti-pattern, where things seem to happen magically but it is extremely hard to figure out what is actually responsible for the magic

In this particular case, the monadic pattern is implied by the Push language: all programs are 100% robust, i.e. all syntactically correct programs execute without throwing an exception and the state of the system is preserved. This means that every time something occurs that makes execution of an operation impossible, we need to “unwind” the system and return it to its state before execution had started. It would be nice to factor all of that out of the implementation so we can concentrate exclusively on semantics of the operations.

So, while implementing Push operations the following must be done:

1. See if there are enough arguments on stack(s). If there were less than enough exit.
2. Start executing the operation. If the operation cannot be completed return everything back to the stack(s), exit. Else:
3. Push result to the appropriate stack.

For instance, here is an implementation of one of Push operations written without the use of monads:

        [<PushOperation("%")>]
        static member Mod() =
            match processArgs2 Float.Me.MyType with
            | [a1; a2] -> 
                if a2.Raw<float>() = 0. 
                then 
                    pushResult a1
                    pushResult a2
                else
                    let quot = Math.Floor(Math.Floor(a1.Raw<float>()) / Math.Floor(a2.Raw<float>()))
                    let res =  a1.Raw<float>() - quot * a2.Raw<float>()
                    pushResult(Float(res))
            | _ -> ()

Here all the steps are recognizable:

1. Pop two arguments from the FLOAT stack using processArgs2. If it returns anything but a list of two values exit.
2. Check if the second argument is 0. If so, return arguments back to the stack and exit, otherwise execute the operation.
3. Push the result back to the FLOAT stack

Here is the monadic version:

    [<PushOperation("%")>]
    static member Mod() =
        let getMod stack = 
            push {
                let! right = popOne stack
                let! left = popOne<float> stack
                if right <> 0. then
                    let quot = Math.Floor(Math.Floor(left) / Math.Floor(right))
                    return! result stack (left - quot * right)
            }
        getMod Float.Me.MyType

We no longer need to explicitly handle the pattern mentioned above. All the steps and branches are contained within our definition of the “push” monad, so no magic here. The reader of the code knows where to look for explanation of the side effects.

If there are less than 2 values on top of the FLOAT stack, execution will not go forward and previous arguments will be returned to the stack.

If the right argument is 0, “unwinding” of the state will also happen automatically without any need to handle this case explicitly.

One other convenience: we can now factor out extracting the value from an object we get from the top of a stack (by calling its Raw<‘a>() function). This is done by implementing the monad and presented through compiler sugar of “let!” assignment. A great improvement on maintainability and ease of implementation.

“Under the hood” details to be discussed in the next post.