Monads Are Useful

August 16, 2022

Ok, the title of this post is clickbait. Monads aren’t always useful. But (I forgot who said this) every other Tuesday, they turn out to be absolutely indispensable tools in your high-level programming toolbox.

Alright, so what made me write this post?

I’m working on a RPN calculator (basically a Forth). I’ve used a few different calculators, and I think it’s high time I make my own. I’m also using Common Lisp, for reasons you can find here.

Side note: If you don’t know Common Lisp and Haskell at least moderately well, this post will probably read like gibberish. Read Practical Common Lisp and Learn You a Haskell, and this post will make more sense (in fact, I referenced some Haskell code from LYAH while writing this code).

First Idea

Since RPN calculators rely on a stack, I need a stack. Great. In Common Lisp, I don’t even need to make a new data structure - I’ll just consider any list to be a stack. I can push and pop elements with the functions #'push and #'pop. Easy.

Here’s an example:

(setf stack '())
(push 10 stack)
(push 20 stack)
(print (pop stack))  ; 20
(print stack)        ; (10)

However, here’s the first issue. Mutable state is bad (most of the time). In addition, I want to be able to support undo, which means that I would have to save intermediate states of the stack. And if, for example, a pop fails, I’ll have to roll back the state. Basically, it’s a lot of annoying bookkeeping, and it will probably scale badly. And besides, I’m using Common Lisp! There must be an easier and more elegant solution.

Second idea

Here’s the second thing I thought of. What if I could define any old function, and I could apply it to the stack for predictable results?

For example, I could do:

(defun stack-add (a b)
  (list (+ a b)))
  
(defun stack-dup (a)
  (list a a))
  
(defun stack-swap (a b)
  (list b a))

Then, I could write some magical stack-apply function which would take a stack and apply the function to the top n values, pushing the result back on to the stack. For example:

(defun stack-apply (stack fn)
  (let ((len (length stack))
        (arity (length (arglist fn))))
    (if (< len arity)
        nil
        (multiple-value-bind (top bottom)
            (split stack arity)
          (append (apply fn top) bottom)))))

Note that I used a function called arglist (from the trivial-arguments package) in order to determine how many arguments a function needs. I also wrote a utility function called split that would split a list into two partitions based on a given index (for example, (split '(1 2 3 4 5) 2) would return (1 2) and (3 4 5)).

However, there’s still a problem. These functions are not composable.

Say I wanted to define a function which was equivalent to doing a swap then a dup. With this system, there’s no way of specifying that. Not to mention, how would I figure out the arity of a function that is composed of multiple other functions?

Sure, I could define a stack “action” to be a list of functions to apply in a row. However, there’s another issue still. I want to be able to query information about the stack (for example, the top value on the stack) in between functions and use that information in further actions. With this system, it’s just not possible without some complex environment hacking (that’s not worth doing).

So, I’m at a dead end.

Third Idea

Say I wanted to implement a function that would add the 1st and 3rd values of the stack.

I want to be able to do something like this:

(defun stack-foo (stack)
  (swap stack) ; swap the first two elements
  (setf b (pop stack)) ; pop off the middle element
  (add stack) ; add a and c
  (push b) ; push the middle element back onto stack
  (swap stack))

Sure, the code is longer and more convoluted, but I’m able to use existing stack functions together in order to define more complex behaviors. And notice that I popped off an element, saved the value, then pushed it back onto the stack later.

However, now I’m back to the whole mutable state thing. How can I keep some of the imperative behavior without having to dealing with a whole lot of mutable state? Well, I can start with making the stack immutable. Instead of writing functions that change the state of an object, I’ll write functions that return a whole new object (but one that can safely share memory with previous objects, since they will never be mutated).

For example:

(defun new-stack () nil)

(defun stack-push (stack element)
  (cons element stack))
  
(defun stack-pop (stack element)
  (cdr stack))
  
(defun stack-top (stack)
  (car stack))

Now, I can write something like

(defun stack-add (stack)
  (setf a (stack-top stack))
  (setf stack% (stack-pop stack))
  (setf b (stack-top stack%))
  (setf stack%% (stack-pop stack%))
  (setf stack%%% (stack-push stack%% (+ a b)))
  stack%%%)

Immediately, you can tell that this will be annoying to code. I have to keep track of a bunch of temporary variables and thread them through the correct functions. If I’m gonna program like this, I might as well use Python or C. Yes, the code is composable, but at what cost?

What I really want is to be able to write something like the following and have it “just work”.

(def-stack-action add
  (a <- pop)
  (b <- pop)
  (push (+ a b)))
;; hmmm, this looks a lot like Haskell's do notation...

Finally, I realized: I needed a monad.

Fourth Idea

Essentially, a monad would allow me to write short, concise code while having the same behavior as using temporary, mutable variables. However, all of the state management would be implemented as part of the monad and pushed into the background. I could write concise, clean, and composable code!

What I needed all this time was the State monad (which can easily be used to “store” the current state of a stack). A monad is basically a specific type of software pattern that satisfies certain mathematical properties and can be used to abstract away common behavior. There are different types of monads that are useful for different purposes. My preferred definition of a monad is a monoid in the category of endofunctors a composable computational context.

Side note: This is where things might get confusing - go properly learn what a monad is and come back after.

 Now, I didn’t realize this until after, but the State monad has a slightly misleading name. It does not actually store any state (in contrast with the Maybe monad, which can be interpreted as “wrapping” a value). Rather, the State monad encapsulates a stateful computation. You can then bind multiple stateful computations together in order to get a useful action that can be applied to a stack. This is the exact behavior I was looking for.

I defined the State monad in Common Lisp as follows (it can also be implemented purely with macros, as seen here)

;; A Monadic interface specifies two functions: return and bind (>>=)

;; Essentially, State monad contains a lambda that takes
;; a state and then returns (optionally) a return value
;; paired with a new state
;; In psuedo-haskell:
;;    State :: state -> (return_type, state)

;; The most basic State action: returns a given value
;; and leaves the state unchanged
(defun return (return-value)
  (lambda (state) (cons return-value state)))

;; bind :: State -> (a -> State) -> State
;; Takes a stateful computation and uses its return
;; value to produce another stateful computation, which
;; then becomes "bound" to the first
(defun >>= (state-action produce-new-action)
  (lambda (state)
    (let* ((res (funcall state-action state))
           (return-value (car res))
           (new-state (cdr res))
           (next-state (funcall produce-new-action return-value)))
      (funcall next-state new-state))))
 
;; We also provide an extra function to "run" a state
;; action on a given initial state.
;; This function will return the final state after
;; each action is executed.
(defun run-state (initial-state action)
  (cdr (funcall action initial-state)))

If you’re having trouble figuring out what the above code is doing, don’t worry. Just know that the State monad basically lets you abstract code that looks like this (in pseudo-python):

def action(initial_state):
	(ret1, state1) = stateful_computation1(initial_state)
	(ret2, state2) = stateful_computation2(state1)
	(ret3, state3) = stateful_computation3(state2)
	print(ret1 + ret2 + ret3)
	return state3

into this:

def action():
  ret1 <- stateful_computation1
  ret2 <- stateful_computation2
  ret3 <- stateful_computation3
  print(ret1 + ret2 + ret3)

runState(initial_state, action)

Now, we can define some primitive stack actions as follows:

;; returns the top element of the stack
;; keeps the state the same
(defun top ()
  (lambda (stack) (cons (car stack) stack)))

;; returns the top element of the stack
;; drops the top value of the stack
(defun pop ()
  (lambda (stack) (cons (car stack) (cdr stack))))

;; does not return any value
;; pushes an element onto the stack
(defun push (x)
  (lambda (stack) (cons nil (cons x stack))))

;; does not return any value
;; duplicates the top value of the stack
(defun dup ()
  (lambda (stack) (cons nil (cons (car stack) stack))))

Now, we can use these primitives to produce more complicated actions like the following:

(defun stack-add ()
  (>>= (pop) (lambda (a)
    (>>= (pop) (lambda (b)
      (push (+ a b)))))))

But of course, this is a little hard to read… Let’s clean it up with a recursive macro.

(defun do-rec (lines)
  (if (= 1 (length lines))
      (car lines)  ;; `do { action }` is equivalent to just `action`
      (let ((line (car lines)))
        (cond
          ;; matches (binding <- action)
          ;; yes, I'm using infix notation in Lisp, sue me
          ((and (< 2 (length line))
                (eq '<- (cadr line)))
           `(>>= ,(cddr line) (lambda (,(car line))
                                ,(do-rec (cdr lines)))))
          ;; support for basic let statements
          ((eq 'let (car line))
           `(let ((,(cadr line) ,(caddr line)))
              ,(do-rec (cdr lines))))
          ;; ignore previous return value (uses >> instead of >>=)
          (t `(>> ,line (lambda ()
                          ,(do-rec (cdr lines)))))))))


(defmacro do-notation (&rest lines)
  (do-rec lines))

;; Same as bind, but ignores the previous return value
(defun >> (state action)
  (>>= state (lambda (s)
    (declare (ignorable s))
    (funcall action))))

Finally, we can now write:

;; adds the top 2 stack elements
(defun add ()
  (do-notation
    (a <- pop)
    (b <- pop)
    (push (+ a b)))

;; swaps the top 2 stack elements
(defun swap ()
  (do-notation
    (a <- pop)
    (b <- pop)
    (push b)
    (push a)))
    
;; turns [x y z] into [x z y]
(defun swapd ()
  (do-notation
    (a <- pop)
    (swap)
    (push a)))

Yay! We finally have composable stateful computations! (Of course, I don’t need to use this nice-looking do notation - I can still use >>= and >> to programmatically chain actions together.)

Conclusion

It turns out a monad turned out to be exactly what I needed for my project! If I hadn’t remembered that State monads exist, I’m not really sure what I would have done. I think I probably would have just ended up with some half-baked command pattern-like thing.

Anyway, I need to stop yak shaving and go back to actually implementing a useful calculator. I hope you enjoyed reading this post!

PS

If you want to see the working code for yourself, see here: zack466/rpncalc (in state.lisp).

I macro-ified most of the state monad implementation and added some extra utilities.

However, the functionality itself should all still be the same as in this article.