This is the first of a series of posts that explore functional programming in F#. My original intent in this post was to explore how to manage state in a pure functional program by implementing a very simple stack machine in F#. It turns out that this exercise illustrates, in a very short piece of code, several important principles of functional programming in F# and consequently provides a simple, succint general introduction to functional programming in F#.

In order to provide a basis for comparison, I first provide an imperative implementation of the stack machine. Then I provide an initial functional implementation of the stack machine and work through three incremental improvements that nicely illustrate some key functional techniques.

## A Very Simple Stack Machine (VSSM)

VSSM is a very simple stack machine for processing lists of arithmetic operations on integers. It consists of a data structure for maintaining its state and a set of operations for performing simple integer arithmetic. Conceptually, the machine’s state is maintained as a simple stack of integers. Its arithmetic operations remove the top two elements from the stack, apply the appropriate arithmetic function to these two elements and place the result on the top of the stack. The machine’s operations are defined in Table 1.

Operation | Description |
---|---|

Push(x) where x is an integer | Pushes x onto the stack. |

Add | Pops value2 from the stack. Pops value1 from the stack. Pushes the sum of value1 and value2 onto the stack. |

Subtract | Pops value2 from the stack. Pops value1 from the stack. Pushes the difference of value1 and value2 onto the stack. |

Multiply | Pops value2 from the stack. Pops value1 from the stack. Pushes the product of value1 and value2 onto the stack. |

Divide | Pops value2 from the stack. Pops value1 from the stack. Pushes the quotient of value1 and value2 onto the stack. |

Table 2 illustrates how VSSM operates on a simple list of test operations.

Operation | Resulting Stack | Comment |
---|---|---|

Push(4) | 4 | 4 is placed on the top of the stack. |

Push(3) | 3,4 | 3 is placed on the top of the stack. The stack now contains two elements. |

Subract | 1 | The top two elements are removed from the stack and subtracted. The result (1) is placed on the top of the stack. |

Push(1) | 1,1 | 1 is placed on the top of the stack. The stack now contains two elements. |

Add | 2 | The top two elements are removed from the stack and added. The result (2) is placed on the top of the stack. |

Push(5) | 5,2 | 5 is placed on the top of the stack. The stack now contains 2 elements. |

Multiply | 10 | The top two elements are removed from the stack and multiplied. The result (10) is placed on the top of the stack. |

## Representing VSSM Operations with an F# Discriminated Union

In F#, discriminated unions provide a mechanism for defining data types whose values can be any one of a set of alternative cases. Listing 1, for instance, uses a discriminated union to define a Pet data type consisting of four possible cases: Dog, Cat, Bird and Fish.

type Pet = | Dog | Cat | Bird | Fish

Discriminated unions are perfect for representing VSSM operations. Listing 2 uses a discriminated union to define an Operation type that has cases for Push, Add, Subtract, Multiply, and Divide.

type Operation = | Add | Subtract | Multiply | Divide | Push of int

Discriminated union cases can be associated with values of a particular type. For instance, the Push case of Operation is associated with the integer value that the operation places on the machine’s stack. In F#, we define Push with the notation Push of int, and we reference an instance of Push with an expression of the form Push(x) where x is the integer placed on the stack.

We will use the list of Operations in Listing 3 as test data for each of the VSSM implementations.

let testOperations = [Push(4); Push(3); Subtract; Push(1); Add; Push(5); Multiply]

## An Imperative Implementation of VSSM

Listing 4 contains the complete imperative implementation of VSSM.

open System open System.Collections.Generic type Operation = | Add | Subtract | Multiply | Divide | Push of int let testOperations = [Push(4); Push(3); Subtract; Push(1); Add; Push(5); Multiply] let executeOperations operations = let stack = new Stack<int>() for operation in operations do match operation with | Add -> let oper2 = stack.Pop() let oper1 = stack.Pop() stack.Push(oper1 + oper2) | Subtract -> let oper2 = stack.Pop() let oper1 = stack.Pop() stack.Push(oper1 - oper2) | Multiply -> let oper2 = stack.Pop() let oper1 = stack.Pop() stack.Push(oper1 * oper2) | Divide -> let oper2 = stack.Pop() let oper1 = stack.Pop() stack.Push(oper1 / oper2) | Push(i) -> stack.Push(i) printfn "The result is %d" (stack.Peek()) executeOperations testOperations

The machine’s state is maintained with a .Net Stack object, and each of the machine’s operations is implemented using standard stack operations.

The function executeOperations uses F# pattern matching to identify the type of each operation. F# pattern matching provides a mechanism for matching against constant values, structural components of values (e.g., head and tail of a list), discriminated union cases and several other types of patterns. The code in Listing 4 uses pattern matching on the case of the Operation discriminated union to identify the type of each operation.

## A Functional Implementation of VSSM

#### An Immutable Representation of VSSM State

A function has side-effects if it modifies the program’s state. Stack.Push and Stack.Pop, used in Listing 14, are examples of functions with side-effects. They modify the Stack object’s state by adding or removing elements. The Stack object is an example of a mutable data structure. Mutable data structures are data structures that can be modified.

The avoidance of side-effects is one of the key objectives of functional programming. Advocates of functional programming claim a number of benefits for the absence of side-effects including a greater ease of reading and reasoning about the code and an increased ability to execute parts of a computation in parallel. These benefits are realized in pure functional programming by banning the use of mutable data structures. So the key problem of providing a functional implementation of VSSM is how to represent the state of the machine without appealing to a mutable stack object of some kind.

Our functional implementation of VSSM will use F# lists to represent the machine’s state at any point in time. F# lists are ordered series of elements of the same data type. You can use a semicolon-delimited series of elements enclosed in square brackets to define a list. For instance, the following expression represents a list of 5 integers.

[1; 3; 5; 9; 11]

It is conventional to refer to the first element of the list as the *head* of the list and the list of all elements except the first as the *tail* of the list. Among the List functions provided by F# are List.head and List.tail which return respectively the head and tail of a list. The following are some examples that illustrate the use of these functions.

List Expression | Evaluates To |
---|---|

List.head([1; 3; 5; 9; 11]) | 1 |

List.tail([1; 3; 5; 9; 11]) | [3; 5; 9; 11] |

List.head(List.tail([1; 3; 5; 9; 11])) | 3 |

List.tail(List.tail([1; 3; 5; 9; 11])) | [5; 9; 11] |

The implementation of processOperation in Listing 6 will use these functions for accessing components of the list representing the VSSM’s state.

The :: operator can also be used to construct a list h::t where h is the head of the list and t is its tail. For instance, 1::[3; 5; 9; 11] represents the same list as [1; 3; 5; 9; 11]. This notation is commonly used for creating lists by prepending a new item to an existing list. It can also be used in patterns to match the head and tail of a list.

#### Executing VSSM Operations

The function, processOperation, defined in Listing 6 below, executes a single VSSM operation. Its parameters are a list that represents the current state of the VSSM and an operation. It returns a list that represents the state of the VSSM after the operation is executed. All of the operations are implemented using the standard list functions described above.

let processOperation state operation = match operation with | Add -> List.head(List.tail(state)) + List.head(state)::List.tail(List.tail(state)) | Subtract -> List.head(List.tail(state)) - List.head(state)::List.tail(List.tail(state)) | Multiply -> List.head(List.tail(state)) * List.head(state)::List.tail(List.tail(state)) | Divide -> List.head(List.tail(state)) / List.head(state)::List.tail(List.tail(state)) | Push(i) -> i::state

The Push(x) operation uses the :: operator to create a new list with x at its head. The other operations are implemented by using List.head(state) and List.head(List.tail(state)) to access the top two elements. The resulting state is then constructed by using the :: operator to prepend the result of the appropriate arithmetic operation to List.tail(List.tail(state)).

#### An Incremental Improvement Using Functions as Values

Four of the five operation cases in listing 6 are implemented with code that is identical except for the arithmetic operator. In F#, we can factor this code into a separate function that takes the arithmetic function as a parameter. applyBinaryOp, defined in Listing 7 below, applies the arithmetic function passed as its second argument to the VSSM state list passed as its first argument and returns the resulting state list. It is called by processOperation with the appropriate arithmetic function for each type of operation.

let applyBinaryOp state op = (op (List.head(List.tail(state))) (List.head(state)))::List.tail(List.tail(state)) let processOperation state operation = match operation with | Add -> applyBinaryOp state (+) | Subtract -> applyBinaryOp state (-) | Multiply -> applyBinaryOp state (*) | Divide -> applyBinaryOp state (/) | Push(i) -> i::state

#### An Incremental Improvement Using List Pattern Matching

We can simplify applyBinaryOp further by using a list pattern in the parameter list. The pattern (op2::op1::remainder) allows us to bind the individual parts of the VSSM state list to the identifiers: op1, op2 and remainder. op2 will be bound to the first element, op1 will be bound to the second element, and remainder will be bound to the remainder of the list. This allows us to eliminate the calls to List.head and List.tail in the function’s body.

let applyBinaryOp (op2::op1::remainder) op = (op op1 op2)::remainder

#### Using Recursion to Maintain State

To implement VSSM, we will need to call processOperation for each operation in the operation list. Consequently, we will need some method of maintaining the VSSM’s state without utilizing a mutable data structure. We will accomplish this with a recursive function that:

- recursively traverses the list of operations,
- calls processOperation to process each operation,
- recursively passes the state returned by processOperation to itself so that it is available for the next operation.

In this way, the VSSM machine state is maintained in a parameter of a recursive function call. This function, processOperations, is implemented in Listing 9.

let rec processOperations state operations = match operations with | [] -> state | head::tail -> processOperations (processOperation state head) tail

processOperations takes two parameters: a list that represents the current program state and a list of Operations. The function performs a list pattern match against the list of Operations. If the list is not empty, the function calls processOperation to apply the function at the head of the list to the current state. Then it calls itself with the returned state and the tail of the Operations list. This continues until it reaches the end of the Operations list and the empty list ([]) is passed as the second parameter. This matches the first case and the function simply returns the final state as it is. The recursion unwinds without further modification to the machine state.

#### An Incremental Improvement Using the Fold Function

The maintenance of program state through the use of a parameter to a recursive function is called the accumulator pattern. This pattern is so common in functional programming that most functional languages provide a higher-order function that generalizes it. This function, called *fold*, provides a general method for doing what processOperations does. It takes three parameters: a function that takes a state and an item and returns a new state, an initial state value, and a list. When it executes, the fold function accumulates state in precisely the same way as processOperations. In fact, we can replace processOperations with a single call to fold as follows:

let result = List.fold processOperation [] testOperations

In this case, List.fold takes the processOperation function, the empty list as the initial VSSM state, and a list of Operations to perform. It executes the list of operations and accumulates the VSSM’s state in exactly the same manner as processOperations in Listing 9.

#### The Final Functional Implementation

Listing 11 contains the complete implementation of the final version in the functional style.

open System type Operation = | Add | Subtract | Multiply | Divide | Push of int let testOperations = [Push(4); Push(3); Subtract; Push(1); Add; Push(5); Multiply] let applyBinaryOp (op2::op1::remainder) op = (op op1 op2)::remainder let processOperation state operation = match operation with | Add -> applyBinaryOp state (+) | Subtract -> applyBinaryOp state (-) | Multiply -> applyBinaryOp state (*) | Divide -> applyBinaryOp state (/) | Push(i) -> i::state let result = List.fold processOperation [] testOperations printfn "the result is %d" (List.head(result))

## F# Resources

The following are useful introductory F# texts. I found Smith’s book to be especially clear and useful. Petricek’s book is useful for people who want to also explore functional programming in C#.

- Petricek, Tomas (2009).
*Real World Functional Programming With Examples in F# and C#*. Manning Publications - Pickering, Robert (2007).
*Foundations of F#*. Apress - Smith, Chris (2009).
*Programming F#*. O’Reilly

The following websites provide additional resources:

Excellent write up on functional programming. After going through the pain of developing the functional implementation, do you think its truly better than your imperative, or even a object oriented implementation?

Isaac, that is an excellent question. I am somewhat more comfortable with the imperative implementation, but I don’t consider myself a good judge at this point. My brain is conditioned by 30 years of imperative programming. My intent is to keep exploring until I can resolve that question for myself.

Every time I see a code example like this, when I get to the end I feel cheated. I dont see any real value in using functional languages, and I could only imagine the nightmares that would ensue using this stuff on real projects.

Functional programming has been dead for eons. There’s a reason for that.

Bobx, I understand your sentiment. I also have difficulty thinking through how these concepts can be applied to large, real-life applications. However, I don’t know if that is just because I am used to thinking about the problems in a different way. For me, this is the beginning of an experiment that will help answer that question.

Functional programming dead for eons? That’s news to me. It’s experiencing a renaissance at the moment.

The value of FP is in simplifying code, and especially in minimising the mutable state within a program. Minimising mutable state is especially important in concurrent programming, but even in single-threaded programs, reducing the mutable state can make it easier to reason about.

I’ve found my code becoming more functional recently. I find it an easier way to write code which is robust. (And reusable, and simple.)

Why do you feel cheated?

Functional programming is a fairly common thing even in the world of OO. If you’ve ever seen yourself write the words “public static void” you have just used functional programming ideals.

Since when did public static /void/ become functional?

Consider re-ordering the arguments for applyBinaryOp…

let applyBinaryOp op = function

op2::op1:remainder -> (op op1 op2)::remainder

_ -> failwith “Not enough items on the stack”

Adding this one line of code allows you to at least catch the one error path (that I can see)

Thanks, Paul.

Functional languages are suited to very particular types of problem to get the value of using them over procedural/object oriented languages. I don’t think your implementation of VSSM (while being quite interesting) is really the best example of where a functional language would be useful.

For my money, the types of large, real-life applications that would benefit the most from functional languages are those where rules are king, like banking, payroll or insurance. Try building a tax calculator in C# vs F# and you’ll feel the benefit. The classic functional example is the fox, chicken and seeds puzzle, define a set of rules of what can cross together and let the language do the black magic to work out the answer.

Personally I wish Microsoft would just implement Prolog for the CLR.

David, you make a really good point. A particular paradigm may be more suited to some problems than others. This lends some credibility to multi-paradigm languages like F#. I will take a look at the fox, chicken and seeds puzzle. Thanks.

I think F#’s place is anywhere in an application where you have very complex logic that in C# would take countless loops, ifs and switch to represent. I don’t think it will ever become that popular due to the high learning curve but it’s good that Microsoft has provided it.

Nice article. Why don’t you try to improve the imperative code a little? Like replacing the two pops plus operation with a call to a function that takes the stack and an operation.

I meant:

open System

open System.Collections.Generic

type Operation =

| Add

| Subtract

| Multiply

| Divide

| Push of int

let testOperations = [Push(4); Push(3); Subtract; Push(1); Add; Push(5); Multiply]

let applyBinaryOp (stack : Stack) (op : int -> int -> int) =

let oper2 = stack.Pop()

let oper1 = stack.Pop()

stack.Push(oper1 + oper2)

let executeOperations operations =

let stack = new Stack()

for operation in operations do

match operation with

| Add -> applyBinaryOp stack (+)

| Subtract -> applyBinaryOp stack (-)

| Multiply -> applyBinaryOp stack (*)

| Divide -> applyBinaryOp stack (/)

| Push(i) -> stack.Push(i)

printfn “The result is %d” (stack.Peek())

executeOperations testOperations

Nice improvement. I think you meant to say “op” instead of “+” in applyBinaryOp.

The functional solution is already shorter thanks to pattern matching, making it preferable to the imperative one in my eyes.

If you add error handling into the program, I expect the functional solution will look even nicer. Functional purity, even if only “piece-wise” is the key to avoid corrupt states in the presence of exceptions.

The OCD part of me says you can simplify the functional solution slightly, albeit at the expense of clarity:

open System

type Operation =

….| BinOp of (int -> int -> int)

….| Push of int

let processOperation state operation =

….match state, operation with

….| (op2::op1::remainder), BinOp(f) -> (f op1 op2)::remainder

….| _, Push(i) -> i::state

let processOperations = List.fold processOperation []

let testOperations = [Push(4); Push(3); BinOp(-); Push(1); BinOp(+); Push(5); BinOp(*)]

let result = processOperations testOperations

printfn “the result is %d” (List.head(result))

(replace …. with spaces).

You could also swap the arguments in “let processOperation state operation =” and in applyBinaryOp with this change, you could abstract the state from the code of this function!

let processOperation operation =

match operation with

| Add -> applyBinaryOp (+)

| Subtract -> applyBinaryOp (-)

| Multiply -> applyBinaryOp (*)

| Divide -> applyBinaryOp (/)

| Push(i) -> (fun state -> i::state)

This makes use of currying!

Though I noticed that the functional implementation appears a little shorter than the imperative version, I am not sure what you would be gaining by using a functional language.

In the 90s I became somewhat fluent in Prolog. It was all the rage back then and the claim was that it would revolutionize the way we program. It didn’t. Prolog met its limits with the implementation of approximately 2000 expert systems and then it passed into history.

I see a similar fate for functional programming since it lends itself well to certain types of processes but beyond that I don’t see it competing well with standard 3rd generation languages. It is simply too esoteric for most professional developers and cannot compare to the base of knowledge that already exists for the popular development languages that are in use today.

A very interesting post. I’m in a similar state with F#: namely, questioning whether such a thing is basically worth it. The trouble with the language in general, for me, is that it seems very write-only — I have trouble looking at it and telling what it’s supposed to be doing… comes down to familiarity, I suppose, but the mindset required is so at odds with the way I normally think about programming that it seems to me to be completely backwards thinking. Do you find this – that you have to trick your brain into thinking backwards to get anything out of it?

The other part of what I’m wondering about is whether shorter source code necessarily means a shorter compiled program: in other words, could it be that the compiler is creating something horrendously complex just to give us the luxury of writing a few less lines of source? If so, then there’s a problem…

Is it a problem, really? Even if the binary increases with 10% or something, it’s usually cheaper to buy additional storage than additional programmer time.

Yes, there is very much a different mindset required. It is a different way of thinking about the problem. I suspect, as you indicate, that this becomes more natural with practice.

Oh, good! I’m glad it’s not just me, then!