A Graybeard Reflects

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.

Table 1: VSSM Operations

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.

Table 2: 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 Function Examples

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:

1. recursively traverses the list of operations,
2. calls processOperation to process each operation,
3. 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:

• http://www.fsharp.net
• http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/