15 Stateful programs and stateful computations
- What makes a program stateful?
- Writing stateful programs without mutating state
- Generating random structures
- Composing stateful computations
Since chapter 1, I’ve been preaching against state mutation as a side effect that should be avoided at almost any cost, and you’ve seen several examples of refactoring programs to avoid state mutation. In this chapter, you’ll see how the functional approach works when keeping state is a requirement rather than an implementation detail of your program.
But what’s a stateful program exactly? It’s a program whose behavior differs, depending on past inputs or events.1 By analogy, if somebody says, “Good morning,” you’ll probably mindlessly greet them in return. If that person immediately says, “Good morning” again, your reaction will certainly differ: Why in the world would somebody say “Good morning” twice in a row? A stateless program, on the other hand, would keep answering “Good morning” just as mindlessly as before because it has no notion of past inputs. Every time is like the first time.
In this chapter, you’ll see how two apparently contradictory ideas—keeping state in memory and avoiding state mutation—can be reconciled in a stateful functional program. You’ll then see how functions that handle state can be composed using the techniques you learned in chapter 14.
15.1 Programs that manage state
In this section, you’ll see a simple command-line program that enables the user to look up foreign exchange rates (FX rates). A sample interaction with the program would be as follows (bold letters indicate user input):
Enter a currency pair like 'EURUSD', or 'q' to quit usdeur fetching rate... 0.9162 gbpusd fetching rate... 1.2248 q
If you’ve downloaded the code samples, you can try it out for yourself:
The following listing shows an initial stateless implementation.
Listing 15.1 Stateless implementation of a simple program to look up FX rates
WriteLine("Enter a currency pair like 'EURUSD', or 'q' to quit"); for (string input; (input = ReadLine().ToUpper()) != "Q";) WriteLine(RatesApi.GetRate(input)); static class RatesApi { public static decimal GetRate(string ccyPair) { WriteLine($"fetching rate..."); // ... ❶ } }
❶ Performs a web request to fetch the requested rate
You can disregard the implementation details of RatesApi.GetRate; all we care about is that it takes a currency pair identifier such as EURUSD (for Euros/US Dollars) and returns the exchange rate.
The program works, but if you repeatedly ask it for the same currency pair, it will perform an HTTP request every time. There are several reasons why you might want to avoid unnecessary remote requests, such as performance, network use, or cost incurred per request. Next, we’ll introduce an in-memory cache to avoid looking up rates we’ve already retrieved.
15.1.1 Caching data in memory
We want to store rates in a cache when they’re retrieved and only make HTTP requests for rates we haven’t requested before, as figure 15.1 shows. (In practice, you’d want values stored in the cache to expire after some time, but I’ll disregard this requirement in order to concentrate on the essential aspects of keeping state.)
Of course, as functional programmers, we want to do this without state mutation. What will be the type of the program’s state? A dictionary would be a natural choice, mapping each pair identifier (such as EURUSD) to the corresponding exchange rate. Just to make sure we don’t mutate it, let’s make it an immutable dictionary: ImmutableDictionary<string, decimal>. And because that’s quite an ugly type, we’ll alias it as Rates to make the code less verbose.
The following listing provides an implementation that stores already retrieved rates in the cache and only calls the remote API if the rate wasn’t previously retrieved. It does this without state mutation.
Listing 15.2 Stateful implementation keeping a cache of rates
using Rates = System.Collections.Immutable ❶ .ImmutableDictionary<string, decimal>; ❶ public class Program { public static void Main() { WriteLine("Enter a currency pair like 'EURUSD', or 'q' to quit"); MainRec(Rates.Empty); ❷ } static void MainRec(Rates cache) { var input = ReadLine().ToUpper(); if (input == "Q") return; var (rate, newState) = GetRate(input, cache); ❸ WriteLine(rate); MainRec(newState); ❹ } static (decimal, Rates) GetRate(string ccyPair, Rates cache) { if (cache.ContainsKey(ccyPair)) ❺ return (cache[ccyPair], cache); ❺ var rate = RatesApi.GetRate(ccyPair); ❻ return (rate, cache.Add(ccyPair, rate)); ❼ } }
❶ A readable name for the program state
❷ Sets up an initial state and passes control to MainRec
❸ Gets a result as well as the new state
❹ Recursively calls itself with the new state
❺ Uses the cached rate if available
❼ Returns a tuple with the retrieved rate and the updated state of the program
Look at the signatures of the two GetRate functions:
The first signature is the stateless version; the second is the stateful version. The latter also takes (along with the requested currency pair) the current state of the program, and it returns (along with the resulting rate) the new state of the program.
Important If global variables can’t be mutated, you must pass state around via arguments and return values. This is the key to writing stateful applications without mutation.
Let’s now move up to MainRec (for recursive), which contains the basic control flow of the program. The thing to note here is that it takes as an input parameter the current state of the program, which it passes on to GetRate to retrieve the new state (along with the rate, which is printed). It ends by calling itself with the new state.
Finally, Main simply calls MainRec with the initial state of the program, which is an empty cache. You can view the entire program execution as a loop with MainRec recursively calling itself, passing the current version of the state as a parameter.
Note that although there are no global variables in the program, it’s still a stateful program. The program keeps some state in memory, which affects how the program operates.
Generally speaking, recursion is a risky business in C#, as it can blow the stack if more than about 10,000 recursive calls are made. If you want to avoid the recursive definition, you can use a loop instead. The following listing shows the Main method rewritten to use a loop.
Listing 15.3 Converting a recursive function to a loop
public static void Main() { WriteLine("Enter a currency pair like 'EURUSD', or 'q' to quit"); var state = Rates.Empty; ❶ for (string input; (input = ReadLine().ToUpper()) != "Q";) { var (rate, newState) = GetRate(input, state); state = newState; ❷ WriteLine(rate); } }
❷ Reassigns the state variable for the next iteration
Here, instead of the recursive call, we keep a local mutable variable, state, which is reassigned to the new state as needed. We’re not mutating any global state, so the fundamental idea still holds.
For the remaining examples in this chapter, I’ll stick to the recursive version, which I find cleaner. In a real-life application, you’ll want to use the iterative version to avoid stack overflow.
15.1.2 Refactoring for testability and error handling
You’ve seen how you can create a stateful program that doesn’t require mutation. Before we move on, I’d like to make some improvements to the program in order to illustrate some of the ideas around testability and error handling, which you saw in previous chapters.
You’ll notice that although there are no side effects in terms of state mutation, there are I/O side effects everywhere, so the program isn’t at all testable. We can refactor GetRate to take the function performing the HTTP request as an input argument, following the pattern explained in chapter 3:
static (decimal, Rates) GetRate (Func<string, decimal> getRate, string ccyPair, Rates cache) { if (cache.ContainsKey(ccyPair)) return (cache[ccyPair], cache); var rate = getRate(ccyPair); return (rate, cache.Add(ccyPair, rate)); }
Now GetRate has no side effects other than those that may occur by calling the given delegate getRate. As a result, it’s easy to unit test this function by providing a delegate with a predictable behavior. MainRec could likewise be brought under test by injecting functions to invoke for I/O.
Next, there’s no error handling at all: if you enter the name of a currency pair that doesn’t exist, the program crashes. Let’s put Try to good use. First, we’ll wrap the stateless GetRate method in a Try:
static class RatesApi { public static Try<decimal> TryGetRate(string ccyPair) ❶ => () => GetRate(ccyPair); static decimal GetRate(string ccyPair) // ... ❷ }
❶ The safe function returns a Try.
❷ The unsafe version works just like before.
The stateful Program.GetRate method must now change its signature to not take a function returning a decimal but a Try<decimal>. Accordingly, its return type will also be wrapped in a Try. Here’s the signature before and after:
before : (string→decimal)→string→(decimal, Rates) after : (string→Try<decimal>)→string→Try<(decimal, Rates)>
The following listing shows the refactored implementation.
Listing 15.4 The program refactored to use Try for error handling
public class Program { public static void Main() => MainRec("Enter a currency pair like 'EURUSD', or 'q' to quit" , Rates.Empty); static void MainRec(string message, Rates cache) { WriteLine(message); var input = ReadLine().ToUpper(); if (input == "Q") return; GetRate(RatesApi.TryGetRate, input, cache).Run().Match ( ex => MainRec($"Error: {ex.Message}", cache), result => MainRec(result.Rate.ToString(), result.NewState) ); } static Try<(decimal Rate, Rates NewState)> GetRate (Func<string, Try<decimal>> getRate, string ccyPair, Rates cache) { if (cache.ContainsKey(ccyPair)) return Try(() => (cache[ccyPair], cache)); else return from rate in getRate(ccyPair) select (rate, cache.Add(ccyPair, rate)); } }
You could try it out for yourself with
Here’s a sample interaction with the program:
Enter a currency pair like 'EURUSD', or 'q' to quit eurusd fetching rate... 1.2066 eurusd 1.2066 ❶ rubbish fetching rate... Error: The given key 'BISH' was not present in the dictionary. ❷ q
Notice how we were able to add testability and error handling in a relatively painless way without puffing up the implementation with interfaces, try-catch statements, and so on. Instead, we have more powerful function signatures and more explicit relationships between functions via parameter passing.
15.1.3 Stateful computations
As you’ve seen in this section, if you want to handle state functionally (without state mutation), state must be made available to functions as an input argument, and functions that affect the state must return the updated state as part of their result. The remaining part of this chapter focuses on stateful computations, which are functions that interact with some state.
NOTE Stateful computations are functions that take a state (as well as, potentially, other arguments) and return a new state (along with, potentially, a return value). They’re also called state transitions.
Stateful computations may appear both in stateful and stateless programs. You’ve already seen a few examples. In the previous scenario, GetRate is a stateful computation because it takes some state (the cache) along with a currency pair and returns the updated state along with the requested rate. In chapter 13, the static Account class contained only stateful computations, each taking an AccountState (along with a command) and returning a new AccountState (along with an event to store), although in this case, things were slightly complicated by the result being wrapped in a Validation.
If you want to combine several stateful computations (the process of always passing the state into a function), extracting it from the result and passing it to the next function can become quite tedious. Fortunately, stateful computations can be composed monadically in a way that hides the state-passing, as you’ll see next.
The rest of this chapter contains advanced material, which is not required to understand the following chapters, in case you decide to skip to the next chapter.
15.2 A language for generating random data
Random data has many legitimate practical uses, including property-based testing (which I discussed in chapter 10), load testing (where you generate lots of random data and then bombard your system to see how it holds up), and simulation algorithms like Monte Carlo. In this context, I’m mainly interested in presenting random generation as a good introductory example of how stateful computations compose. To get started, type the following into the REPL:
var r = new Random(100); r.Next() // => 2080427802 r.Next() // => 341851734 r.Next() // => 1431988776
Because you’re explicitly passing the value 100 as a seed for the random generator, you should get exactly the same results. As you can see, it’s not that random after all. It’s next to impossible to get real randomness with our current computers; instead, we use pseudo-random generators, which use a scrambling algorithm to deterministically produce an output that looks random. Typically, you don’t want to get the same sequence of values every time, so a Random instance is usually initialized without an explicit seed; in this case, the current time is used.
If Random is deterministic, how does it produce a different output every time you call Next? The answer is that Random is stateful: every time you call Next, the state of the Random instance is updated. In other words, Next has side effects.
Next is called with no input arguments and yields an int as its explicit output. But it has an implicit input (the current state of the Random instance) that determines the output, as well as another implicit output, that is, the new state of the Random instance. This will in turn determine the output of the following call to Next.
We’re going to create a side-effect-free random generator where all inputs and outputs are explicit. Generating a number is a stateful computation because it requires a seed, and it must also generate a new seed to be used in the following generation. We don’t want to only generate integers but values of any type, so the type of a generator function can be captured with the following delegate:
A Generator<T> is a stateful computation that takes an int value as a seed (the state) and returns a tuple consisting of the generated T and a new seed, which can be used to generate a subsequent value. In arrow-notation, the signature for Generator<T> is
To run a generator, we can define the following Run methods:
public static T Run<T>(this Generator<T> gen, int seed) => gen(seed).Value; public static T Run<T>(this Generator<T> gen) => gen(Environment.TickCount).Value;
The first overload runs the generator with the given seed and returns the generated value, disregarding the state. The second overload uses the clock to get a different seed value each time it’s called (it’s therefore impure and not testable, unlike the first overload). Next, let’s create some generators.
15.2.1 Generating random integers
The basic building block we need is a generator that scrambles the seed value into a new int. The following listing shows one possible implementation.
Listing 15.5 A stateful computation returning a pseudorandom number
public static Generator<int> NextInt = (seed) => { seed ^= seed >> 13; seed ^= seed << 18; int result = seed & 0x7fffffff; return (result, result); };
This is a generator that, when given a seed, scrambles it to obtain another integer that looks unrelated.2 It then returns that value both as a result value and as a seed to be used in the following computation.
Things start to get exciting when you want to generate more complex values. It turns out that if you can generate a random int, you can generate random values for arbitrarily complex types. But let’s start with baby steps: Knowing you can generate a random int, how could you write a generator for a simpler type such as a Boolean?
15.2.2 Generating other primitives
Remember, a generator takes a seed and returns a new value (in this case, the generated Boolean) along with a new seed. The skeleton of a Generator<bool> would be as follows:
public static Generator<bool> NextBool = (seed) => { bool result = // ??? int newSeed = // ??? return (result, newSeed); };
How can we go about implementing it? We already have a generator for an int, so we can generate an int and return true/false depending on whether it's even/odd. We also need to return a new seed, and for this, we can take advantage of the new seed computed when generating the int. Essentially, we’re using NextInt, transforming the resulting int into a bool and reusing the seed. Figure 15.2 illustrates this.
The implementation is as follows:
public static Generator<bool> NextBool = (seed) => { var (i, newSeed) = NextInt(seed); return (i % 2 == 0, newSeed); };
Now, let’s think of this differently. What we’re doing here is effectively mapping a function that turns an int into a bool while reusing the new seed returned by the existing NextInt generator. We can generalize this pattern to define Map: if you have a Generator<T> and a function f : T → R, you can obtain a Generator<R> as follows: run the generator to obtain a T and a new seed; apply f to obtain an R; return the resulting R along with the new seed. The following listing shows the implementation of Map.
Listing 15.6 Definition of Map for Generator<T>
public static Generator<R> Map<T, R> ( this Generator<T> gen, Func<T, R> f ) => seed => ❶ { var (t, newSeed) = gen(seed); ❷ return (f(t), newSeed); ❸ };
❶ Map returns a generator that, when given a seed...
❷ ... runs the given generator gen to obtain a T and a new seed...
❸ ... then uses f to turn the T into an R, which is returned along with the new seed.
We can now define generators for types that carry less information than an int (such as bool or char) much more concisely, as in the following listing.
Listing 15.7 Building upon NextInt to generate other types
public static Generator<bool> NextBool => from i in NextInt ❶ select i % 2 == 0; ❷ public static Generator<char> NextChar => from i in NextInt select (char)(i % (char.MaxValue + 1));
❷ ...returns whether it’s even
That’s much more readable because we don’t have to explicitly worry about the seed, and we can read the code in terms of “generate an int, and return whether it’s even.”
15.2.3 Generating complex structures
Now let’s move on and see how we can generate more complex values. Let’s try to generate a pair of integers. We’d have to write something like this:
public static Generator<(int, int)> PairOfInts = (seed0) => { var (a, seed1) = NextInt(seed0); var (b, seed2) = NextInt(seed1); return ((a, b), seed2); };
Here you see that for each stateful computation (or for each time we generate a random value), we need to extract the state (the newly created seed) and pass it on to the next computation. This is rather noisy. Fortunately, we can do away with the explicit state-passing by composing the generators with a LINQ expression as the following listing shows.
Listing 15.8 Defining a function that generates a pair of random integers
public static Generator<(int, int)> PairOfInts => from a in NextInt ❶ from b in NextInt ❷ select (a, b); ❸
❶ Generates an int and calls it a
❷ Generates another int and calls it b
This is much more readable, but under the covers, it’s the same as before. This works because I’ve defined an implementation of Bind/SelectMany that takes care of “threading the state,” passing it from one computation to the next. Graphically, figure 15.3 shows how Bind works. Listing 15.9 shows the corresponding code.
Listing 15.9 Definition of Bind for Generator<T>
public static Generator<R> Bind<T, R> ( this Generator<T> gen, Func<T, Generator<R>> f ) => seed0 => { var (t, seed1) = gen(seed0); return f(t)(seed1); };
Now we have all the building blocks to generate arbitrarily complex types. Say we want to create an Option<int>. That’s easy—generate a Boolean for the state of the Option and an int for the value:
public static Generator<Option<int>> OptionInt => from some in NextBool from i in NextInt select some ? Some(i) : None;
This should look familiar. You saw some similar code in section 10.1.3 when we were using FsCheck to define property tests and we needed to provide a method for generating random Options. Indeed, FsCheck’s random generator is defined along the same lines as this one.
The following listing shows a slightly more complex example, that of generating a sequence of ints.
Listing 15.10 Generating a list of random numbers
public static Generator<IEnumerable<int>> IntList => from empty in NextBool from list in empty ? Empty : NonEmpty select list; static Generator<IEnumerable<int>> Empty => Generator.Return(Enumerable.Empty<int>()); static Generator<IEnumerable<int>> NonEmpty => from head in NextInt from tail in IntList select List(head).Concat(tail); public static Generator<T> Return<T>(T value) => seed => (value, seed);
Let’s start with the top-level IntList. We generate a random Boolean to tell us if the sequence should be empty.3 If so, we use Empty, which is a generator that always returns an empty sequence; otherwise, we return a non-empty sequence by calling NonEmpty. This generates an int as the first element and a random sequence to follow it. Note that Empty uses the Return function for Generator, which lifts a value into a generator that always returns that value and doesn’t affect the state it’s given.
What about generating a string? A string is essentially a sequence of characters, so we can generate a list of ints, convert each int to a char, and build a string from the resulting sequence of characters. As you can see, we follow this approach to generate a language for combining generators of various types into generators for arbitrarily complex types.
15.3 A general pattern for stateful computations
There are many other scenarios in which we may want to compose several stateful computations, other than generating random values. For this, we can use a more general delegate, StatefulComputation:
A StatefulComputation<T> is a function in this form:
T is the function’s result value, and S is the state.4 You can compare this to the signature of Generator<T> to see how similar they are:
With Generator, the state that gets passed in and out is always an int. With the more general StatefulComputation, the state could be of an arbitrary type S. Thus, we can define Map and Bind in the same way (the only difference being an additional type parameter) and let them take care of threading the state between one computation and the next.
In chapter 11, we discussed trees, and you saw how you could define a Map function that creates a new tree, where each element is the result of applying a function to each value in the original tree. Imagine that you now want to assign a number to each element, as figure 15.4 shows.
This operation is similar to Map in the sense that you must traverse the tree and apply a function to each element. But, additionally, you must keep some state (a counter value) that needs to be incremented as you visit each element and used to label each leaf.
Let’s start by defining a Numbered<T> type that wraps a T and a number:
This means the operation we’re trying to model can be expressed as a function from Tree<T> to Tree<Numbered<T>>.
The following listing shows an initial implementation that traverses the tree, explicitly passing the state (a counter value) around.
Listing 15.11 Numbering the leaves of a tree by explicitly passing state
using LaYumba.Functional.Data.BinaryTree; public Tree<Numbered<T>> Number<T>(Tree<T> tree) => Number(tree, 0).Tree; ❶ (Tree<Numbered<T>> Tree, int Count) Number<T> ( Tree<T> tree, int count ) => tree.Match ( Leaf: t => ( Tree.Leaf(new Numbered<T>(t, count)), ❷ count + 1 ❸ ), Branch: (l, r) => { var (left, count1) = Number(l, count); ❹ var (right, count2) = Number(r, count1); ❹ return (Tree.Branch(left, right), count2); ❺ } );
❶ Calls the stateful overload, passing 0 as the initial state
❷ Labels this leaf with the current count
❸ Returns the incremented count as the new state
❹ Recursively calls Number on the left and right subtrees
❺ Returns the new tree with the updated count
We start the computation with a count of 0. The numbering function simply matches on the type of tree. If it’s a leaf, then it contains a T, so Number returns a pair, containing as the result a Numbered<T> (wrapping the T and the current count) and as the new state the incremented counter. If it’s a branch, then we recursively call Number on the left and right subtrees. Because each of these operations returns an updated state, we must thread the state along and return it in the result value.
Although I find the preceding solution satisfactory, it’s true that manually passing state along introduces some noise. We can get rid of that by refactoring the code to use the StatefulComputation delegate instead.
We’ll start by defining a simple stateful computation that takes an int (the state, which in this case is the counter) and returns the counter as the value and the incremented state as the new state:
static StatefulComputation<int, int> GetAndIncrement = count => (count, count + 1); GetAndIncrement(0) // => (0, 1) GetAndIncrement(6) // => (6, 7)
Remember, a stateful computation returns both a value and a new state. GetAndIncrement returns the current counter value as the returned value and the incremented counter as the new state.
The interesting thing about GetAndIncrement is that it allows you to peek into the state: because the current counter value becomes the inner value of the computation, you can refer to it in a LINQ expression. You can see this in the following code, where we assign the current count value to the count variable.
The following listing shows how we can rewrite our tree numbering function using LINQ to take care of passing the state.
Listing 15.12 Numbering the leaves of a tree using LINQ
StatefulComputation<int, Tree<Numbered<T>>> Number<T> ( Tree<T> tree ) => tree.Match ( Leaf: t => from count in GetAndIncrement ❶ select Tree.Leaf(new Numbered<T>(t, count)), ❷ Branch: (left, right) => from newLeft in Number(left) from newRight in Number(right) select Tree.Branch(newLeft, newRight) );
❶ Assigns the current count to the count variable, while assigning the incremented count to the state
❷ The result is a new leaf containing the original leaf value, numbered with the current count.
As you can see, when you’re composing a sequence of several stateful computations as in the Branch case, LINQ can really improve readability. Otherwise, I find that passing the state around explicitly is clearer. Note that the preceding function returns a computation, which does nothing until it’s given an input state:
Although stateful computations are ubiquitous, the need to chain several computations isn’t as frequent. It does crop up often in certain areas, though, such as simulations or parsers. A functional parser, for example, is usually modeled as a function that takes a string (the state), consumes part of the string, and produces a result consisting of a structured representation of what’s been parsed and the remainder of the string that’s left to parse (the new state).
Summary
-
When writing stateful programs, you can avoid changing state as a side effect by always passing the state explicitly as part of your functions' input and output.
-
Stateful computations are functions in the form
S→(T,S). They take some state and return a value as well as an updated state. -
Stateful computations can be composed monadically to reduce the syntactic burden of passing the state from one computation to the next.
1 This means that a program may be considered stateful/stateless depending on where you draw the program boundary. You may have a stateless server that uses a DB to keep state. If you consider both as one program, it’s stateful; if you consider the server in isolation, it’s stateless.
2 The specifics of the algorithm are irrelevant for the purposes of this discussion. There are many algorithms for generating pseudorandom numbers.
3 This means that, statistically, half the generated lists will be empty, a quarter of the lists will have one element, and so on, so this generator is unlikely to produce a long list. You can follow a different approach and generate a random length first, presumably within a given range, and then populate the values. As this shows, once you start to generate random data, it’s important to define parameters that govern the random generation.
4 In FP lingo, this is called the state monad. This is a truly terrible name to describe a function that takes some state as an argument. This unfortunate name is probably the greatest hurdle to understanding it.