layout: post
title: “Worked example: A stack based calculator”
description: “Using combinators to build functionality”
nav: thinking-functionally
seriesId: “Thinking functionally”
seriesOrder: 13

categories: [Combinators, Functions, Worked Examples]

In this post, we’ll implement a simple stack based calculator (also known as “reverse Polish” style). The implementation is almost entirely done with functions, with only one special type and no pattern matching at all, so it is a great testing ground for the concepts introduced in this series.

If you are not familiar with a stack based calculator, it works as follows: numbers are pushed on a stack, and operations such as addition and multiplication pop numbers off the stack and push the result back on.

Here is a diagram showing a simple calculation using a stack:

Stack based calculator diagram

The first steps to designing a system like this is to think about how it would be used. Following a Forth like syntax, we will give each action a label, so that the example above might want to be written something like:

  1. EMPTY ONE THREE ADD TWO MUL SHOW

We might not be able to get this exact syntax, but let’s see how close we can get.

The Stack data type

First we need to define the data structure for a stack. To keep things simple, we’ll just use a list of floats.

  1. type Stack = float list

But, hold on, let’s wrap it in a single case union type to make it more descriptive, like this:

  1. type Stack = StackContents of float list

For more details on why this is nicer, read the discussion of single case union types in this post.

Now, to create a new stack, we use StackContents as a constructor:

  1. let newStack = StackContents [1.0;2.0;3.0]

And to extract the contents of an existing Stack, we pattern match with StackContents:

  1. let (StackContents contents) = newStack
  2. // "contents" value set to
  3. // float list = [1.0; 2.0; 3.0]

The Push function

Next we need a way to push numbers on to the stack. This will be simply be prepending the new value at the front of the list using the “::“ operator.

Here is our push function:

  1. let push x aStack =
  2. let (StackContents contents) = aStack
  3. let newContents = x::contents
  4. StackContents newContents

This basic function has a number of things worth discussing.

First, note that the list structure is immutable, so the function must accept an existing stack and return a new stack. It cannot just alter the existing stack. In fact, all of the functions in this example will have a similar format like this:

  1. Input: a Stack plus other parameters
  2. Output: a new Stack

Next, what should the order of the parameters be? Should the stack parameter come first or last? If you remember the discussion of designing functions for partial application, you will remember that the most changeable thing should come last. You’ll see shortly that this guideline will be born out.

Finally, the function can be made more concise by using pattern matching in the function parameter itself, rather than using a let in the body of the function.

Here is the rewritten version:

  1. let push x (StackContents contents) =
  2. StackContents (x::contents)

Much nicer!

And by the way, look at the nice signature it has:

  1. val push : float -> Stack -> Stack

As we know from a previous post, the signature tells you a lot about the function.
In this case, I could probably guess what it did from the signature alone, even without knowing that the name of the function was “push”.
This is one of the reasons why it is a good idea to have explicit type names. If the stack type had just been a list of floats, it wouldn’t have been as self-documenting.

Anyway, now let’s test it:

  1. let emptyStack = StackContents []
  2. let stackWith1 = push 1.0 emptyStack
  3. let stackWith2 = push 2.0 stackWith1

Works great!

Building on top of “push”

With this simple function in place, we can easily define an operation that pushes a particular number onto the stack.

  1. let ONE stack = push 1.0 stack
  2. let TWO stack = push 2.0 stack

But wait a minute! Can you see that the stack parameter is used on both sides? In fact, we don’t need to mention it at all. Instead we can skip the stack parameter and write the functions using partial application as follows:

  1. let ONE = push 1.0
  2. let TWO = push 2.0
  3. let THREE = push 3.0
  4. let FOUR = push 4.0
  5. let FIVE = push 5.0

Now you can see that if the parameters for push were in a different order, we wouldn’t have been able to do this.

While we’re at it, let’s define a function that creates an empty stack as well:

  1. let EMPTY = StackContents []

Let’s test all of these now:

  1. let stackWith1 = ONE EMPTY
  2. let stackWith2 = TWO stackWith1
  3. let stackWith3 = THREE stackWith2

These intermediate stacks are annoying ? can we get rid of them? Yes! Note that these functions ONE, TWO, THREE all have the same signature:

  1. Stack -> Stack

This means that they can be chained together nicely! The output of one can be fed into the input of the next, as shown below:

  1. let result123 = EMPTY |> ONE |> TWO |> THREE
  2. let result312 = EMPTY |> THREE |> ONE |> TWO

Popping the stack

That takes care of pushing onto the stack ? what about a pop function next?

When we pop the stack, we will return the top of the stack, obviously, but is that all?

In an object-oriented style, the answer is yes. In an OO approach, we would mutate the stack itself behind the scenes, so that the top element was removed.

But in a functional style, the stack is immutable. The only way to remove the top element is to create a new stack with the element removed.
In order for the caller to have access to this new diminished stack, it needs to be returned along with the top element itself.

In other words, the pop function will have to return two values, the top plus the new stack. The easiest way to do this in F# is just to use a tuple.

Here’s the implementation:

  1. /// Pop a value from the stack and return it
  2. /// and the new stack as a tuple
  3. let pop (StackContents contents) =
  4. match contents with
  5. | top::rest ->
  6. let newStack = StackContents rest
  7. (top,newStack)

This function is also very straightforward.

As before, we are extracting the contents directly in the parameter.

We then use a match..with expression to test the contents.

Next, we separate the top element from the rest, create a new stack from the remaining elements and finally return the pair as a tuple.

Try the code above and see what happens. You will get a compiler error!
The compiler has caught a case we have overlooked — what happens if the stack is empty?

So now we have to decide how to handle this.

Generally, I prefer to use error cases, but in this case, we’ll use an exception. So here’s the pop code changed to handle the empty case:

  1. /// Pop a value from the stack and return it
  2. /// and the new stack as a tuple
  3. let pop (StackContents contents) =
  4. match contents with
  5. | top::rest ->
  6. let newStack = StackContents rest
  7. (top,newStack)
  8. | [] ->
  9. failwith "Stack underflow"

Now let’s test it:

  1. let initialStack = EMPTY |> ONE |> TWO
  2. let popped1, poppedStack = pop initialStack
  3. let popped2, poppedStack2 = pop poppedStack

and to test the underflow:

  1. let _ = pop EMPTY

Writing the math functions

Now with both push and pop in place, we can work on the “add” and “multiply” functions:

  1. let ADD stack =
  2. let x,s = pop stack //pop the top of the stack
  3. let y,s2 = pop s //pop the result stack
  4. let result = x + y //do the math
  5. push result s2 //push back on the doubly-popped stack
  6. let MUL stack =
  7. let x,s = pop stack //pop the top of the stack
  8. let y,s2 = pop s //pop the result stack
  9. let result = x * y //do the math
  10. push result s2 //push back on the doubly-popped stack

Test these interactively:

  1. let add1and2 = EMPTY |> ONE |> TWO |> ADD
  2. let add2and3 = EMPTY |> TWO |> THREE |> ADD
  3. let mult2and3 = EMPTY |> TWO |> THREE |> MUL

It works!

Time to refactor…

It is obvious that there is significant duplicate code between these two functions. How can we refactor?

Both functions pop two values from the stack, apply some sort of binary function, and then push the result back on the stack. This leads us to refactor out the common code into a “binary” function that takes a two parameter math function as a parameter:

  1. let binary mathFn stack =
  2. // pop the top of the stack
  3. let y,stack' = pop stack
  4. // pop the top of the stack again
  5. let x,stack'' = pop stack'
  6. // do the math
  7. let z = mathFn x y
  8. // push the result value back on the doubly-popped stack
  9. push z stack''

Note that in this implementation, I’ve switched to using ticks to represent changed states of the “same” object, rather than numeric suffixes. Numeric suffixes can easily get quite confusing.

Question: why are the parameters in the order they are, instead of mathFn being after stack?

Now that we have binary, we can define ADD and friends more simply:

Here’s a first attempt at ADD using the new binary helper:

  1. let ADD aStack = binary (fun x y -> x + y) aStack

But we can eliminate the lambda, as it is exactly the definition of the built-in + function! Which gives us:

  1. let ADD aStack = binary (+) aStack

And again, we can use partial application to hide the stack parameter. Here’s the final definition:

  1. let ADD = binary (+)

And here’s the definition of some other math functions:

  1. let SUB = binary (-)
  2. let MUL = binary (*)
  3. let DIV = binary (../)

Let’s test interactively again.

  1. let div2by3 = EMPTY |> THREE|> TWO |> DIV
  2. let sub2from5 = EMPTY |> TWO |> FIVE |> SUB
  3. let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB

In a similar fashion, we can create a helper function for unary functions

  1. let unary f stack =
  2. let x,stack' = pop stack //pop the top of the stack
  3. push (f x) stack' //push the function value on the stack

And then define some unary functions:

  1. let NEG = unary (fun x -> -x)
  2. let SQUARE = unary (fun x -> x * x)

Test interactively again:

  1. let neg3 = EMPTY |> THREE|> NEG
  2. let square2 = EMPTY |> TWO |> SQUARE

Putting it all together

In the original requirements, we mentioned that we wanted to be able to show the results, so let’s define a SHOW function.

  1. let SHOW stack =
  2. let x,_ = pop stack
  3. printfn "The answer is %f" x
  4. stack // keep going with same stack

Note that in this case, we pop the original stack but ignore the diminished version. The final result of the function is the original stack, as if it had never been popped.

So now finally, we can write the code example from the original requirements

  1. EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW

Going further

This is fun — what else can we do?

Well, we can define a few more core helper functions:

  1. /// Duplicate the top value on the stack
  2. let DUP stack =
  3. // get the top of the stack
  4. let x,_ = pop stack
  5. // push it onto the stack again
  6. push x stack
  7. /// Swap the top two values
  8. let SWAP stack =
  9. let x,s = pop stack
  10. let y,s' = pop s
  11. push y (push x s')
  12. /// Make an obvious starting point
  13. let START = EMPTY

And with these additional functions in place, we can write some nice examples:

  1. START
  2. |> ONE |> TWO |> SHOW
  3. START
  4. |> ONE |> TWO |> ADD |> SHOW
  5. |> THREE |> ADD |> SHOW
  6. START
  7. |> THREE |> DUP |> DUP |> MUL |> MUL // 27
  8. START
  9. |> ONE |> TWO |> ADD |> SHOW // 3
  10. |> THREE |> MUL |> SHOW // 9
  11. |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5

Using composition instead of piping

But that’s not all. In fact, there is another very interesting way to think about these functions.

As I pointed out earlier, they all have an identical signature:

  1. Stack -> Stack

So, because the input and output types are the same, these functions can be composed using the composition operator >>, not just chained together with pipes.

Here are some examples:

  1. // define a new function
  2. let ONE_TWO_ADD =
  3. ONE >> TWO >> ADD
  4. // test it
  5. START |> ONE_TWO_ADD |> SHOW
  6. // define a new function
  7. let SQUARE =
  8. DUP >> MUL
  9. // test it
  10. START |> TWO |> SQUARE |> SHOW
  11. // define a new function
  12. let CUBE =
  13. DUP >> DUP >> MUL >> MUL
  14. // test it
  15. START |> THREE |> CUBE |> SHOW
  16. // define a new function
  17. let SUM_NUMBERS_UPTO =
  18. DUP // n
  19. >> ONE >> ADD // n+1
  20. >> MUL // n(n+1)
  21. >> TWO >> SWAP >> DIV // n(n+1) / 2
  22. // test it
  23. START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW

In each of these cases, a new function is defined by composing other functions together to make a new one. This is a good example of the “combinator” approach to building up functionality.

Pipes vs composition

We have now seen two different ways that this stack based model can be used; by piping or by composition. So what is the difference? And why would we prefer one way over another?

The difference is that piping is, in a sense, a “realtime transformation” operation. When you use piping you are actually doing the operations right now, passing a particular stack around.

On the other hand, composition is a kind of “plan” for what you want to do, building an overall function from a set of parts, but not actually running it yet.

So for example, I can create a “plan” for how to square a number by combining smaller operations:

  1. let COMPOSED_SQUARE = DUP >> MUL

I cannot do the equivalent with the piping approach.

  1. let PIPED_SQUARE = DUP |> MUL

This causes a compilation error. I have to have some sort of concrete stack instance to make it work:

  1. let stackWith2 = EMPTY |> TWO
  2. let twoSquared = stackWith2 |> DUP |> MUL

And even then, I only get the answer for this particular input, not a plan for all possible inputs, as in the COMPOSED_SQUARE example.

The other way to create a “plan” is to explicitly pass in a lambda to a more primitive function, as we saw near the beginning:

  1. let LAMBDA_SQUARE = unary (fun x -> x * x)

This is much more explicit (and is likely to be faster) but loses all the benefits and clarity of the composition approach.

So, in general, go for the composition approach if you can!

The complete code

Here’s the complete code for all the examples so far.

  1. // ==============================================
  2. // Types
  3. // ==============================================
  4. type Stack = StackContents of float list
  5. // ==============================================
  6. // Stack primitives
  7. // ==============================================
  8. /// Push a value on the stack
  9. let push x (StackContents contents) =
  10. StackContents (x::contents)
  11. /// Pop a value from the stack and return it
  12. /// and the new stack as a tuple
  13. let pop (StackContents contents) =
  14. match contents with
  15. | top::rest ->
  16. let newStack = StackContents rest
  17. (top,newStack)
  18. | [] ->
  19. failwith "Stack underflow"
  20. // ==============================================
  21. // Operator core
  22. // ==============================================
  23. // pop the top two elements
  24. // do a binary operation on them
  25. // push the result
  26. let binary mathFn stack =
  27. let y,stack' = pop stack
  28. let x,stack'' = pop stack'
  29. let z = mathFn x y
  30. push z stack''
  31. // pop the top element
  32. // do a unary operation on it
  33. // push the result
  34. let unary f stack =
  35. let x,stack' = pop stack
  36. push (f x) stack'
  37. // ==============================================
  38. // Other core
  39. // ==============================================
  40. /// Pop and show the top value on the stack
  41. let SHOW stack =
  42. let x,_ = pop stack
  43. printfn "The answer is %f" x
  44. stack // keep going with same stack
  45. /// Duplicate the top value on the stack
  46. let DUP stack =
  47. let x,s = pop stack
  48. push x (push x s)
  49. /// Swap the top two values
  50. let SWAP stack =
  51. let x,s = pop stack
  52. let y,s' = pop s
  53. push y (push x s')
  54. /// Drop the top value on the stack
  55. let DROP stack =
  56. let _,s = pop stack //pop the top of the stack
  57. s //return the rest
  58. // ==============================================
  59. // Words based on primitives
  60. // ==============================================
  61. // Constants
  62. // -------------------------------
  63. let EMPTY = StackContents []
  64. let START = EMPTY
  65. // Numbers
  66. // -------------------------------
  67. let ONE = push 1.0
  68. let TWO = push 2.0
  69. let THREE = push 3.0
  70. let FOUR = push 4.0
  71. let FIVE = push 5.0
  72. // Math functions
  73. // -------------------------------
  74. let ADD = binary (+)
  75. let SUB = binary (-)
  76. let MUL = binary (*)
  77. let DIV = binary (../)
  78. let NEG = unary (fun x -> -x)
  79. // ==============================================
  80. // Words based on composition
  81. // ==============================================
  82. let SQUARE =
  83. DUP >> MUL
  84. let CUBE =
  85. DUP >> DUP >> MUL >> MUL
  86. let SUM_NUMBERS_UPTO =
  87. DUP // n
  88. >> ONE >> ADD // n+1
  89. >> MUL // n(n+1)
  90. >> TWO >> SWAP >> DIV // n(n+1) / 2

Summary

So there we have it, a simple stack based calculator. We’ve seen how we can start with a few primitive operations (push, pop, binary, unary) and from them, build up a whole domain specific language that is both easy to implement and easy to use.

As you might guess, this example is based heavily on the Forth language. I highly recommend the free book “Thinking Forth”, which is not just about the Forth language, but about (non object-oriented!) problem decomposition techniques which are equally applicable to functional programming.

I got the idea for this post from a great blog by Ashley Feniello. If you want to go deeper into emulating a stack based language in F#, start there. Have fun!