ploeh blog danish software design
Hello, pure command-line interaction
A gentle introduction to modelling impure interactions with pure code.
Dependency Injection is a well-described concept in object-oriented programming, but as I've explained earlier, its not functional, because it makes everything impure. In general, you should reject the notion of dependencies by instead designing your application on the concept of an impure/pure/impure sandwich. This is possible more often than you'd think, but there's still a large group of applications where this will not work. If your application needs to interact with the impure world for an extended time, you need a way to model such interactions in a pure way.
This article introduces a way to do that.
Command line API #
Imagine that you have to write a command-line program that can ask a series of questions and print appropriate responses. In the general case, this is a (potentially) long-running series of interactions between the user and the program. To keep it simple, though, in this article we'll start by looking at a degenerate example:
Please enter your name. Mark Hello, Mark!
The program is simply going to request that you enter your name. Once you've done that, it prints the greeting. In object-oriented programming, using Dependency Injection, you might introduce an interface. Keeping it simple, you can restrict such an interface to two methods:
public interface ICommandLine { string ReadLine(); void WriteLine(string text); }
Please note that this is clearly a toy example. In later articles, you'll see how to expand the example to cover some more complex interactions, but you could also read a more realistic example already. Initially, the example is degenerate, because there's only a single interaction. In this case, an impure/pure/impure sandwich is still possible, but such a design wouldn't scale to more complex interactions.
The problem with defining and injecting an interface is that it isn't functional. What's the functional equivalent, then?
Instruction set #
Instead of defining an interface, you can define a discriminated union that describes a limited instruction set for command-line interactions:
type CommandLineInstruction<'a> = | ReadLine of (string -> 'a) | WriteLine of string * 'a
You may notice that it looks a bit like the above C# interface. Instead of defining two methods, it defines two cases, but the names are similar.
The ReadLine case is an instruction that an interpreter can evaluate. The data contained in the case is a continuation function. After evaluating the instruction, an interpreter must invoke this function with a string. It's up to the interpreter to figure out which string to use, but it could, for example, come from reading an input string from the command line. The continuation function is the next step in whatever program you're writing.
The WriteLine case is another instruction for interpreters. The data contained in this case is a tuple. The first element of the tuple is input for the interpreter, which can choose to e.g. print the value on the command line, or ignore it, and so on. The second element of the tuple is a value used to continue whatever program this case is a part of.
This enables you to write a small, specialised Abstract Syntax Tree (AST), but there's currently no way to return from it. One way to do that is to add a third 'stop' case. If you're interested in that option, Scott Wlaschin covers this as one iteration in his excellent explanation of the AST design.
Instead of adding a third 'stop' case to CommandLineInstruction<'a>, another option is to add a new wrapper type around it:
type CommandLineProgram<'a> = | Free of CommandLineInstruction<CommandLineProgram<'a>> | Pure of 'a
The Free case contains a CommandLineInstruction that always continues to a new CommandLineProgram value. The only way you can escape the AST is via the Pure case, which simply contains the 'return' value.
Abstract Syntax Trees #
With these two types you can write specialised programs that contain instructions for an interpreter. Notice that the types are pure by intent, although in F# we can't really tell. You can, however, repeat this exercise in Haskell, where the instruction set looks like this:
data CommandLineInstruction next = ReadLine (String -> next) | WriteLine String next deriving (Functor) type CommandLineProgram = Free CommandLineInstruction
Both of these types are pure, because IO is nowhere in sight. In Haskell, functions are pure by default. This also applies to the String -> next function contained in the ReadLine case.
Back in F# land, you can write an AST that implements the command-line interaction shown in the beginning of the article:
// CommandLineProgram<unit> let program = Free (WriteLine ( "Please enter your name.", Free (ReadLine ( fun s -> Free (WriteLine ( sprintf "Hello, %s!" s, Pure ()))))))
This AST defines a little program. The first step is a WriteLine instruction with the input value "Please enter your name.". The WriteLine case constructor takes a tuple as input argument. The first tuple element is that prompt, and the second element is the continuation, which has to be a new CommandLineInstruction<CommandLineProgram<'a>> value.
In this example, the continuation value is a ReadLine case, which takes a continuation function as input. This function should return a new program value, which it does by returning a WriteLine.
This second WriteLine value creates a string from the outer value s. The second tuple element for the WriteLine case must, again, be a new program value, but now the program is done, so you can use the 'stop' value Pure ().
You probably think that I should quit the mushrooms. No one in their right mind will want to write code like this. Neither would I. Fortunately, you can make the coding experience much better, but you'll see how to do that later.
Interpretation #
The above program value is a small CommandLineProgram<unit>. It's a pure value. In itself, it doesn't do anything.
Clearly, we'd like it to do something. In order to make that happen, you can write an interpreter:
// CommandLineProgram<'a> -> 'a let rec interpret = function | Pure x -> x | Free (ReadLine next) -> Console.ReadLine () |> next |> interpret | Free (WriteLine (s, next)) -> Console.WriteLine s next |> interpret
This interpreter is a recursive function that pattern-matches all the cases in any CommandLineProgram<'a>. When it encounters a Pure case, it simply returns the contained value.
When it encounters a ReadLine value, it calls Console.ReadLine (), which returns a string value read from the command line. It then pipes that input value to its next continuation function, which produces a new CommandLineInstruction<CommandLineProgram<'a>> value. Finally, it pipes that continuation value recursively to itself.
A similar treatment is given to the WriteLine case. Console.WriteLine s writes s to the command line, where after next is recursively piped to interpret.
When you run interpret program, you get an interaction like this:
Please enter your name. ploeh Hello, ploeh!
The program is pure; the interpret function is impure.
Syntactic sugar #
Clearly, you don't want to write programs as ASTs like the above. Fortunately, you don't have to. You can add syntactic sugar in the form of computation expressions. The way to do that is to turn your AST types into a monad. In Haskell, you'd already be done, because Free is a monad. In F#, some code is required.
Source functor #
The first step is to define a map function for the underlying instruction set union type. Conceptually, when you can define a map function for a type, you've created a functor (if it obeys the functor laws, that is). Functors are common, so it often pays off being aware of them.
// ('a -> 'b) -> CommandLineInstruction<'a> -> CommandLineInstruction<'b> let private mapI f = function | ReadLine next -> ReadLine (next >> f) | WriteLine (x, next) -> WriteLine (x, next |> f)
The mapI function takes a CommandLineInstruction<'a> value and maps it to a new value by mapping the 'underlying value'. I decided to make the function private because later, I'm also going to define a map function for CommandLineProgram<'a>, and I don't want to confuse users of the API with two different map functions. This is also the reason that the name of the function isn't simply map, but rather mapI, where the I stands for instruction.
mapI pattern-matches on the (implicit) input argument. If it's a ReadLine case, it returns a new ReadLine value, but it uses the mapper function f to translate the next function. Recall that next is a function of the type string -> 'a. When you compose it with f (which is a function of the type 'a -> 'b), you get (string -> 'a) >> ('a -> 'b), or string -> 'b. You've transformed the 'a to a 'b for the ReadLine case. If you can do the same for the WriteLine case, you'll have a functor.
Fortunately, the WriteLine case is similar, although a small tweak is required. This case contains a tuple of data. The first element (x) isn't a generic type (it's a string), so there's nothing to map. You can use it as-is in the new WriteLine value that you'll return. The WriteLine case is degenerate because next isn't a function, but rather a value. It has a type of 'a, and f is a function of the type 'a -> 'b, so piping next to f returns a 'b.
That's it: now you have a functor.
(In order to keep the category theorists happy, I should point out that such functors are really a sub-type of functors called endo-functors. Additionally, functors must obey some simple and intuitive laws in order to be functors, but that's all I'll say about that here.)
Free monad #
There's a reason I spend so much time talking about functors. The goal is syntactic sugar. You can get that with computation expressions. In order to create a computation expression builder, you need a monad.
You need a recipe for creating a monad. Fortunately, there's a type of monad called a free monad. It has the virtue that it enables you to create a monad from any functor.
Just what you need.
In Haskell, this happens automatically when you declare type CommandLineProgram = Free CommandLineInstruction. Thanks to Haskell's type system, Free is automatically a Monad when the underlying type is a Functor. In F#, you have to work for your monads, but the fact that Haskell can automate this means that there's a recipe that you can follow.
Earlier in this article, I mentioned in passing that there are alternative ways in which you can define a 'stop' case for your instruction set. The reason I chose to separate the API into two types (an 'instruction set', and a 'program') is that the instruction set is the underlying functor. The 'program' is part of the free monad. The other part is a bind function (that obeys the monad laws).
// ('a -> CommandLineProgram<'b>) -> CommandLineProgram<'a> // -> CommandLineProgram<'b> let rec bind f = function | Free instruction -> instruction |> mapI (bind f) |> Free | Pure x -> f x
This recursive function pattern-matches on the (implicit) CommandLineProgram<'a> argument. In the Pure case, the 'return' value x has the type 'a, which fits as input for the f function. The result is a value of type CommandLineProgram<'b>.
In the Free case, the instruction is a functor with the map function mapI. The first argument to the mapI function must be a function with the type 'a -> 'b. How can you compose such a function?
If you partially apply the recursive bind function with f (that is: bind f), you get a function of the type CommandLineProgram<'a> -> CommandLineProgram<'b>. This fits with mapI, because instruction has the type CommandLineInstruction<CommandLineProgram<'a>> (refer back to the definition of the Free case if need to convince yourself of that). The result of calling mapI with instruction is a CommandLineInstruction<CommandLineProgram<'b>> value. In order to turn it into a CommandLineProgram<'b> value, you wrap it in a new Free case.
Although this required a bit of explanation, defining a bind function for a free monad is a repeatable process. After all, in Haskell it's automated. In F#, you have to explicitly write the code, but it follows a recipe. Once you get the hang of it, there's not much to it.
Functor #
You'll occasionally need to explicitly use the bind function, but often it'll 'disappear' into a computation expression. There are other building blocks to an API than a bind function, though. You may, for example, need a map function:
// ('a -> 'b) -> CommandLineProgram<'a> -> CommandLineProgram<'b> let map f = bind (f >> Pure)
This makes CommandLineProgram<'a> a functor as well. This is the reason I made mapI private, because mapI makes the instruction set a functor, but the API is expressed in terms of AST programs, and it should be consistent. Within the same module, map should work on the same data type as bind.
Notice that map can be defined as a composition of bind and Pure. This is part of the recipe. For a free monad, the map function always looks like that. The f function is a function with the type 'a -> 'b, and Pure is a case constructor with the type 'b -> CommandLineProgram<'b>. Notice that I've used 'b for the generic type argument instead of the usual 'a. Hopefully, this makes it clear that when you compose these two functions together (f >> Pure), you get a function of the type ('a -> 'b) >> ('b -> CommandLineProgram<'b>), or 'a -> CommandLineProgram<'b>. That's just the type of function needed for the bind function, so the whole composition turns out to type-check and work as intended.
API #
In order to work with an API, you need the ability to create values of the API's type(s). In this case, you must be able to create CommandLineProgram<'a> values. While you can create them explicitly using the ReadLine, WriteLine, Free, and Pure case constructors, it'll be more convenient if you have some predefined functions and values for that.
// CommandLineProgram<string> let readLine = Free (ReadLine Pure) // string -> CommandLineProgram<unit> let writeLine s = Free (WriteLine (s, Pure ()))
In the ReadLine case, there's no input to the instruction, so you can define readLine as a predefined CommandLineProgram<string> value.
The WriteLine case, on the other hand, takes as an input argument a string to write, so you can define writeLine as a function that returns a CommandLineProgram<unit> value.
Computation expression #
The addition of map and supporting API is, to be honest, a bit of digression. You're going to use these functions later, but they aren't required in order to create a computation expression builder. All you need is a bind function and a way to lift a raw value into the monad. All of these are in place, so the builder is a matter of delegation:
type CommandLineBuilder () = member this.Bind (x, f) = CommandLine.bind f x member this.Return x = Pure x member this.ReturnFrom x = x member this.Zero () = Pure ()
This is a fairly minimal builder, but in my experience, most of times, this is all you need.
Create an instance of the CommandLineBuilder class, and you can write computation expressions:
let commandLine = CommandLineBuilder ()
I usually put such an object in a module with an [<AutoOpen>] attribute, so that it's available as a global object.
Producing ASTs with pretty code #
Using the commandLine computation expression is like using the built-in async or seq expressions. You can use it to rewrite the above AST as readable code:
// CommandLineProgram<unit> let program = commandLine { do! CommandLine.writeLine "Please enter your name." let! name = CommandLine.readLine do! sprintf "Hello, %s!" name |> CommandLine.writeLine }
This produces the same AST as before, but with much more readable syntax. The AST is the same, and you can use the above interpret function to run it. The interaction is the same as before:
Please enter your name. Free Hello, Free!
This is, obviously, a toy example, but in coming articles, you'll see how to gradually enhance the code to perform some more complex interactions.
Summary #
Functional programming emphasises pure functions, and a separation of pure and impure code. The simplest way to achieve such a separation is to design your code as an impure/pure/impure sandwich, but sometimes this isn't possible. When it's not possible, an alternative is to define an instruction set for an AST, and turn it into a free monad in order to enable enough syntactic sugar to keep the code readable.
While this may seem complicated, it has the benefit of making impurities explicit in the code. Whenever you see a CommandLineProgram value, you know that, at run-time, something impure is likely to happen. It's not uncontrolled impurity, though. Inside a CommandLineProgram, only reading from, and writing to, the command line will happen. It's not going to generate random values, change global variables, send an email, or any other unpredictable operation - that is, unless the interpreter does that...
Next: A pure command-line wizard.
Pure interactions
Long-running, non-deterministic interactions can be modelled in a pure, functional way.
In a previous article, you can read why Dependency Injection and (strict) functional programming are mutually exclusive. Dependency Injection makes everything impure, and if nothing is pure, then it's hardly functional. In Dependency rejection, you can see how you can often separate impure and pure code into an impure/pure/impure sandwich.
Micro-operation-based architectures #
The impure/pure/impure sandwich architecture works well in scenarios with limited interaction. Some data arrives at the boundary of the system, the system responds, and that's it. That, however, describes a significant fraction of all software running in the world today.
Any HTTP-based application (web site, REST API, most SOAP services) fits the description: an HTTP request arrives, and the server responds with an HTTP response. In a well-designed and well-running system, you should return the response within seconds, if not faster. Everything the software needs in order to run to completion is either part of the request, or part of the application state. You may need to query a database to gather more data based on the incoming request, but you can still gather most data from impure sources, pass it all to your pure core implementation, get the pure values back and return the response.
Likewise, asynchronous message-based systems, such as pub/sub, Pipes and Filters, Actor-based systems, 'SOA done right', CQRS/Event Sourcing, and so on, are based on short-lived, stateless interactions. Similar to HTTP-based applications, there's often (persisted) application state, but once a message arrives at a message handler, the software should process it as quickly as possible. Again, it can read extra (impure) data from a database, pass everything to a pure function, and finally do something impure with the return value.
Common for all such systems is that while they can handle large volumes of data, they do so as the result of a multitude of parallel, distinct, and isolated micro-operations.
Interactive software #
There is, however, another category of software. We could call it 'interactive software'. As the name implies, this includes everything with a user interface, but can also be a long-running batch job, or, as you've already seen, time-sensitive software.
For such software, the impure/pure/impure sandwich architecture is no longer possible. Just think of a UI-based program, like an email client. You compose and send an email, receive a response, then compose a reply, and so on. Every send and receive is impure, as is all the user interface rendering. What happens next depends on what happened before, and everything that happens in the real world is impure.
Have we finally identified the limitations of functional programming?
Hardly. In this series of articles, I'm going to show you how to model pure interactions:
- Hello, pure command-line interaction
- A pure command-line wizard
- Combining free monads in Haskell
- Combining free monads in F#
- F# free monad recipe
This series of articles gives you a comprehensive walkthrough of pure interactions and free monads in F#. For a motivating example, see Pure times, which presents a more realistic example that, on the other hand, doesn't go to the same level of detail.
Summary #
The solution to the problem of continuous impure interactions is to model them as a instructions in a (domain-specific) Abstract Syntax Tree (AST), and then using an impure interpreter for the pure AST. You can model the AST as a (free) monad in order to make the required syntax nice.
Pure times in F#
A Polling Consumer implementation written in F#.
Previously, you saw how to implement a Polling Consumer in Haskell. This proves that it's possible to write pure functional code modelling long-running interactions with the (impure) world. In this article, you'll see how to port the Haskell code to F#.
For reference, I'll repeat the state transition diagram here:
For a complete description of the goals and constraints of this particular Polling Consumer implementation, see my earlier Type Driven Development article, or, even better, watch my Pluralsight course Type-Driven Development with F#.
State data types #
The program has to keep track of various durations. You can model these as naked TimeSpan values, but in order to add extra type safety, you can, instead, define them as separate types:
type PollDuration = PollDuration of TimeSpan type IdleDuration = IdleDuration of TimeSpan type HandleDuration = HandleDuration of TimeSpan type CycleDuration = { PollDuration : PollDuration HandleDuration : HandleDuration }
This is a straightforward port of the Haskell code. See the previous article for more details about the motivation for doing this.
You can now define the states of the finite state machine:
type State<'msg> = | ReadyState of CycleDuration list | ReceivedMessageState of (CycleDuration list * PollDuration * 'msg) | NoMessageState of (CycleDuration list * PollDuration) | StoppedState of CycleDuration list
Again, this is a straight port of the Haskell code.
From instruction set to syntactic sugar #
The Polling Consumer must interact with its environment in various ways:
- Query the system clock
- Poll for messages
- Handle messages
- Idle
type PollingInstruction<'msg, 'next> = | CurrentTime of (DateTimeOffset -> 'next) | Poll of (('msg option * PollDuration) -> 'next) | Handle of ('msg * (HandleDuration -> 'next)) | Idle of (IdleDuration * (IdleDuration -> 'next))
Once more, this is a direct translation of the Haskell code, but from here, this is where your F# code will have to deviate from Haskell. In Haskell, you can, with a single line of code, declare that such a type is a functor. This isn't possible in F#. Instead, you have to explicitly write a map function. This isn't difficult, though. There's a reason that the Haskell compiler can automate this:
// ('a -> 'b) -> PollingInstruction<'c,'a> -> PollingInstruction<'c,'b> let private mapI f = function | CurrentTime next -> CurrentTime (next >> f) | Poll next -> Poll (next >> f) | Handle (x, next) -> Handle (x, next >> f) | Idle (x, next) -> Idle (x, next >> f)
The function is named mapI, where the I stands for instruction. It's private because the next step is to package the functor in a monad. From that monad, you can define a new functor, so in order to prevent any confusion, I decided to hide the underlying functor from any consumers of the API.
Defining a map function for a generic type like PollingInstruction<'msg, 'next> is well-defined. Pattern-match each union case and return the same case, but with the next function composed with the input function argument f: next >> f. In later articles, you'll see more examples, and you'll see how this recipe is entirely repeatable and automatable.
While a functor isn't an explicit concept in F#, this is how PollingInstruction msg next is a Functor in Haskell. Given a functor, you can produce a free monad. The reason you'd want to do this is that once you have a monad, you can get syntactic sugar. Currently, PollingInstruction<'msg, 'next> only enables you to create Abstract Syntax Trees (ASTs), but the programming experience would be cumbersome and alien. Monads give you automatic do notation in Haskell; in F#, it enables you to write a computation expression builder.
Haskell's type system enables you to make a monad from a functor with a one-liner: type PollingProgram msg = Free (PollingInstruction msg). In F#, you'll have to write some boilerplate code. First, you have to define the monadic type:
type PollingProgram<'msg, 'next> = | Free of PollingInstruction<'msg, PollingProgram<'msg, 'next>> | Pure of 'next
You already saw a hint of such a type in the previous article. The PollingProgram<'msg, 'next> discriminated union defines two cases: Free and Pure. The Free case is a PollingInstruction that produces a new PollingProgram as its next step. In essence, this enables you to build an AST, but you also need a signal to stop and return a value from the AST. That's the purpose of the Pure case.
Such a type is only a monad if it defines a bind function (that obey the monad laws):
// ('a -> PollingProgram<'b,'c>) -> PollingProgram<'b,'a> // -> PollingProgram<'b,'c> let rec bind f = function | Free instruction -> instruction |> mapI (bind f) |> Free | Pure x -> f x
This bind function pattern-matches on Free and Pure, respectively. In the Pure case, it simply uses the underlying result value x as an input argument to f. In the Free case, it composes the underlying functor (mapI) with itself recursively. If you find this step obscure, I will not blame you. Just like the implementation of mapI is a bit of boilerplate code, then so is this. It always seems to work this way. If you want to dig deeper into the inner workings of this, then Scott Wlaschin has a detailed explanation.
With the addition of bind PollingProgram<'msg, 'next> becomes a monad (I'm not going to show that the monad laws hold, but they do). Making it a functor is trivial:
// ('a -> 'b) -> PollingProgram<'c,'a> -> PollingProgram<'c,'b> let map f = bind (f >> Pure)
The underlying PollingInstruction type was already a functor. This function makes PollingProgram a functor as well.
It'll be convenient with some functions that lifts each PollingInstruction case to a corresponding PollingProgram value. In Haskell, you can use the liftF function for this, but in F# you'll have to be slightly more explicit:
// PollingProgram<'a,DateTimeOffset> let currentTime = Free (CurrentTime Pure) // PollingProgram<'a,('a option * PollDuration)> let poll = Free (Poll Pure) // 'a -> PollingProgram<'a,HandleDuration> let handle msg = Free (Handle (msg, Pure)) // IdleDuration -> PollingProgram<'a,IdleDuration> let idle duration = Free (Idle (duration, Pure))
currentTime and poll aren't even functions, but values. They are, however, small PollingProgram values, so while they look like values (as contrasted to functions), they represent singular executable instructions.
handle and idle are both functions that return PollingProgram values.
You can now implement a small computation expression builder:
type PollingBuilder () = member this.Bind (x, f) = Polling.bind f x member this.Return x = Pure x member this.ReturnFrom x = x member this.Zero () = this.Return ()
As you can tell, not much is going on here. The Bind method simply delegates to the above bind function, and the rest are trivial one-liners.
You can create an instance of the PollingBuilder class so that you can write PollingPrograms with syntactic sugar:
let polling = PollingBuilder ()
This enables you to write polling computation expressions. You'll see examples of this shortly.
Most of the code you've seen here is automated in Haskell. This means that while you'll have to explicitly write it in F#, it follows a recipe. Once you get the hang of it, it doesn't take much time. The maintenance overhead of the code is also minimal, because you're essentially implementing a universal abstraction. It's not going to change.
Support functions #
Continuing the port of the previous article's Haskell code, you can write a pair of support functions. These are small PollingProgram values:
// IdleDuration -> DateTimeOffset -> PollingProgram<'a,bool> let private shouldIdle (IdleDuration d) stopBefore = polling { let! now = Polling.currentTime return now + d < stopBefore }
This shouldIdle function uses the polling computation expression defined above. It first uses the above Polling.currentTime value to get the current time. While Polling.currentTime is a value of the type PollingProgram<'b,DateTimeOffset>, the let! binding makes now a simple DateTimeOffset value. Computation expressions give you the same sort of syntactic sugar that do notation does in Haskell.
If you add now to d, you get a new DateTimeOffset value that represents the time that the program will resume, if it decides to suspend itself for the idle duration. If this time is before stopBefore, the return value is true; otherwise, it's false. Similar to the Haskell example, the return value of shouldIdle isn't just bool, but rather PollingProgram<'a,bool>, because it all takes place inside the polling computation expression.
The function looks impure, but it is pure.
In the same vein, you can implement a shouldPoll function:
// CycleDuration -> TimeSpan let toTotalCycleTimeSpan x = let (PollDuration pd) = x.PollDuration let (HandleDuration hd) = x.HandleDuration pd + hd // TimeSpan -> DateTimeOffset -> CycleDuration list -> PollingProgram<'a,bool> let private shouldPoll estimatedDuration stopBefore statistics = polling { let expectedHandleDuration = statistics |> List.map toTotalCycleTimeSpan |> Statistics.calculateExpectedDuration estimatedDuration let! now = Polling.currentTime return now + expectedHandleDuration < stopBefore }
This function uses two helper functions: toTotalCycleTimeSpan and Statistics.calculateExpectedDuration. I've included toTotalCycleTimeSpan in the code shown here, while I'm skipping Statistics.calculateExpectedDuration, because it hasn't changed since the code I show in my Pluralsight course. You can also see the function in the GitHub repository accompanying this article.
Compared to shouldIdle, the shouldPoll function needs an extra (pure) step in order to figure out the expectedHandleDuration, but from there, the two functions are similar.
Transitions #
All building blocks are now ready for the finite state machine. In order to break the problem into manageable pieces, you can write a function for each state. Such a function should take as input the data associated with a particular state, and return the next state, based on the input.
The simplest transition is when the program reaches the end state, because there's no way out of that state:
// CycleDuration list -> PollingProgram<'a,State<'b>> let transitionFromStopped s = polling { return StoppedState s }
The data contained in a StoppedState case has the type CycleDuration list, so the transitionFromStopped function simply lifts such a list to a PollingProgram value by returning a StoppedState value from within a polling computation expression.
Slightly more complex, but still simple, is the transition out of the received state. There's no branching logic involved. You just have to handle the message, measure how much time it takes, append the measurements to previous statistics, and return to the ready state:
// CycleDuration list * PollDuration * 'a -> PollingProgram<'a,State<'b>> let transitionFromReceived (statistics, pd, msg) = polling { let! hd = Polling.handle msg return { PollDuration = pd; HandleDuration = hd } :: statistics |> ReadyState }
This function uses the Polling.handle convenience function to handle the input message. Although the handle function returns a PollingProgram<'a,HandleDuration> value, the let! binding inside of a polling computation expression makes hd a HandleDuration value.
The data contained within a ReceivedMessageState case is a CycleDuration list * PollDuration * 'msg tuple. That's the input argument to the transitionFromReceived function, which immediately pattern-matches the tuple's three elements into statistics, pd, and msg.
The pd element is the PollDuration - i.e. the time it took to reach the received state. The hd value returned by Polling.handle gives you the time it took to handle the message. From those two values you can create a new CycleDuration value, and cons (::) it onto the previous statistics. This returns an updated list of statistics that you can pipe to the ReadyState case constructor.
ReadyState in itself creates a new State<'msg> value, but since all of this takes place inside a polling computation expression, the return type of the function becomes PollingProgram<'a,State<'b>>.
The transitionFromReceived function handles the state when the program has received a message, but you also need to handle the state when no message was received:
// IdleDuration -> DateTimeOffset -> CycleDuration list * 'a // -> PollingProgram<'b,State<'c>> let transitionFromNoMessage d stopBefore (statistics, _) = polling { let! b = shouldIdle d stopBefore if b then do! Polling.idle d |> Polling.map ignore return ReadyState statistics else return StoppedState statistics }
This function first calls the shouldIdle support function. Similar to Haskell, you can see how you can compose larger PollingPrograms from smaller PollingProgram values - just like you can compose 'normal' functions from smaller functions.
With the syntactic sugar in place, b is simply a bool value that you can use in a standard if/then/else expression. If b is false, then return a StoppedState value; otherwise, continue with the next steps.
Polling.idle returns the duration of the suspension, but you don't actually need this data, so you can ignore it. When Polling.idle returns, you can return a ReadyState value.
It may look as though that do! expression is a blocking call, but it really isn't. The transitionFromNoMessage function only builds an Abstract Syntax Tree, where one of the instructions suggests that an interpreter could block. Unless evaluated by an impure interpreter, transitionFromNoMessage is pure.
The final transition is the most complex, because there are three possible outcomes:
// TimeSpan -> DateTimeOffset -> CycleDuration list // -> PollingProgram<'a,State<'a>> let transitionFromReady estimatedDuration stopBefore statistics = polling { let! b = shouldPoll estimatedDuration stopBefore statistics if b then let! pollResult = Polling.poll match pollResult with | Some msg, pd -> return ReceivedMessageState (statistics, pd, msg) | None, pd -> return NoMessageState (statistics, pd) else return StoppedState statistics }
In the same way that transitionFromNoMessage uses shouldIdle, the transitionFromReady function uses the shouldPoll support function to decide whether or not to keep going. If b is false, it returns a StoppedState value.
Otherwise, it goes on to poll. Thanks to all the syntactic sugar, pollResult is an 'a option * PollDuration value. As always, when you have a discriminated union, you can handle all cases with pattern matching (and the compiler will help you keep track of whether or not you've handled all of them).
In the Some case, you have a message, and the duration it took to poll for that message. This is all the data you need to return a ReceivedMessageState value.
In the None case, you also have the poll duration pd; return a NoMessageState value.
That's four transition functions that you can combine in a single function that, for any state, returns a new state:
// TimeSpan -> IdleDuration -> DateTimeOffset -> State<'a> // -> PollingProgram<'a,State<'a>> let transition estimatedDuration idleDuration stopBefore = function | ReadyState s -> transitionFromReady estimatedDuration stopBefore s | ReceivedMessageState s -> transitionFromReceived s | NoMessageState s -> transitionFromNoMessage idleDuration stopBefore s | StoppedState s -> transitionFromStopped s
You simply pattern-match the (implicit) input argument with the four state cases, and call the appropriate transition function for each case.
Interpretation #
The transition function is pure. It returns a PollingProgram value. How do you turn it into something that performs real work?
You write an interpreter:
// PollingProgram<Msg,'a> -> 'a let rec interpret = function | Pure x -> x | Free (CurrentTime next) -> DateTimeOffset.Now |> next |> interpret | Free (Poll next) -> Imp.poll () |> next |> interpret | Free (Handle (msg, next)) -> Imp.handle msg |> next |> interpret | Free (Idle (d, next)) -> Imp.idle d |> next |> interpret
A PollingProgram is either a Pure or a Free case. In the Free case, the contained data is a PollingInstruction value, which can be one of four separate cases. With pattern matching, the interpreter handles all five cases.
In the Pure case, it returns the value, but in all the Free cases, it recursively calls itself after having first followed the instruction in each PollingInstruction case. For instance, when the instruction is CurrentTime, it invokes DateTimeOffset.Now, passes the return value (a DateTimeOffset value) to the next continuation, and then recursively calls interpret. The next instruction, then, could be another Free case, or it could be Pure.
The other three instruction cases delegate to implementation functions defined in an Imp module. I'm not going to show them here. They're normal, although impure, F# functions.
Execution #
You're almost done. You have a function that returns a new state for any given input state, as well as an interpreter. You need a function that can repeat this in a loop until it reaches StoppedState:
// TimeSpan -> IdleDuration -> DateTimeOffset -> State<Msg> -> State<Msg> let rec run estimatedDuration idleDuration stopBefore s = let ns = PollingConsumer.transition estimatedDuration idleDuration stopBefore s |> interpret match ns with | PollingConsumer.StoppedState _ -> ns | _ -> run estimatedDuration idleDuration stopBefore ns
This function calls PollingConsumer.transition with the input state s, which returns a new PollingProgram<Msg,PollingConsumer.State<Msg>> value that you can pipe to the interpret function. That gives you the new state ns. If ns is a StoppedState, you return; otherwise, you recurse into run for another round.
Finally, you can write the entry point for the application:
[<EntryPoint>] let main _ = let timeAtEntry = DateTimeOffset.Now printOnEntry timeAtEntry let stopBefore = timeAtEntry + limit let estimatedDuration = TimeSpan.FromSeconds 2. let idleDuration = TimeSpan.FromSeconds 5. |> IdleDuration let durations = PollingConsumer.ReadyState [] |> run estimatedDuration idleDuration stopBefore |> PollingConsumer.durations |> List.map PollingConsumer.toTotalCycleTimeSpan printOnExit timeAtEntry durations // Return 0. This indicates success. 0
This defines an estimated duration of 2 seconds, an idle duration of 5 seconds, and a maximum run time of 60 seconds (limit). The initial state is ReadyState with no prior statistics. Pass all these arguments to the run function, and you have a running program.
This function also uses a few printout functions that I'm not going to show here. When you run the program, you should see output like this:
Started polling at 11:18:28. Polling Handling Polling Handling Polling Sleeping Polling Sleeping Polling Handling Polling Handling Polling Sleeping Polling Sleeping Polling Sleeping Polling Handling Polling Sleeping Polling Sleeping Polling Sleeping Polling Sleeping Polling Handling Stopped polling at 11:19:26. Elapsed time: 00:00:58.4428980. Handled 6 message(s). Average duration: 00:00:01.0550346 Standard deviation: 00:00:00.3970599
It does, indeed, exit before 60 seconds have elapsed.
Summary #
You can model long-running interactions with an Abstract Syntax Tree. Without computation expressions, writing programs as 'raw' ASTs would be cumbersome, but turning the AST into a (free) monad makes it all quite palatable.
Haskell code with a free monad can be ported to F#, although some boilerplate code is required. That code, however, is unlikely to be much of a burden, because it follows a well-known recipe that implements a universal abstraction.
For more details on how to write free monads in F#, see Pure interactions.
Pure times in Haskell
A Polling Consumer implementation written in Haskell.
As you can read in the introductory article, I've come to realise that the Polling Consumer that I originally wrote in F# isn't particularly functional. Being the friendly and productive language that it is, F# doesn't protect you from mixing pure and impure code, but Haskell does. For that reason, you can develop a prototype in Haskell, and later port it to F#, if you want to learn how to solve the problem in a strictly functional way.
To recapitulate, the task is to implement a Polling Consumer that runs for a predefined duration, after which it exits (so that it can be restarted by a scheduler).
The program is a finite state machine that moves between four states. From the ready state, it'll need to decide whether to poll for a new message or exit. Polling and handling takes time (and at compile-time we don't know how long), and the program ought to stop at a pre-defined time. If it gets too close to that time, it should exit, but otherwise, it should attempt to handle a message (and keep track of how long this takes). You can read a more elaborate description of the problem in the original article.
State data types #
The premise in that initial article was that F#'s type system is so powerful that it can aid you in designing a good solution. Haskell's type system is even more powerful, so it can give you even better help.
The Polling Consumer program must measure and keep track of how long it takes to poll, handle a message, or idle. All of these are durations. In Haskell, we can represent them as NominalDiffTime values. I'm a bit concerned, though, that if I represent all of these durations as NominalDiffTime values, I may accidentally use a poll duration where I really need a handle duration, and so on. Perhaps I'm being overly cautious, but I like to get help from the type system. In the words of Igal Tabachnik, types prevent typos:
newtype PollDuration = PollDuration NominalDiffTime deriving (Eq, Show) newtype IdleDuration = IdleDuration NominalDiffTime deriving (Eq, Show) newtype HandleDuration = HandleDuration NominalDiffTime deriving (Eq, Show) data CycleDuration = CycleDuration { pollDuration :: PollDuration, handleDuration :: HandleDuration } deriving (Eq, Show)
This simply declares that PollDuration, IdleDuration, and HandleDuration are all NominalDiffTime values, but you can't mistakenly use a PollDuration where a HandleDuration is required, and so on.
In addition to those three types of duration, I also define a CycleDuration. This is the data that I actually need to keep track of: how long does it take to handle a single message? I'm assuming that polling for a message is an I/O-bound operation, so it may take significant time. Likewise, handling a message may take time. When deciding whether to exit or handle a new message, both durations count. Instead of defining CycleDuration as a newtype alias for NominalDiffTime, I decided to define it as a record type comprised of a PollDuration and a HandleDuration. It's not that I'm really interested in keeping track of these two values individually, but it protects me from making stupid mistakes. I can only create a CycleDuration value if I have both a PollDuration and a HandleDuration value.
In short, I'm trying to combat primitive obsession.
With these duration types in place, you can define the states of the finite state machine:
data PollingState msg = Ready [CycleDuration] | ReceivedMessage [CycleDuration] PollDuration msg | NoMessage [CycleDuration] PollDuration | Stopped [CycleDuration] deriving (Show)
Like the original F# code, state data can be represented as a sum type, with a case for each state. In all four cases, a CycleDuration list keeps track of the observed message-handling statistics. This is the way the program should attempt to calculate whether it's safe to handle another message, or exit. Two of the cases (ReceivedMessage and NoMessage) also contain a PollDuration, which informs the program about the duration of the poll operation that caused it to reach that state. Additionally, the ReceivedMessage case contains a message of the generic type msg. This makes the entire PollingState type generic. A message can be of any type: a string, a number, or a complex data structure. The Polling Consumer program doesn't care, because it doesn't handle messages; it only schedules the polling.
This is reminiscent of the previous F# attempt, with the most notable difference that it doesn't attempt to capture durations as Timed<'a> values. It does capture durations, but not when the operations started and stopped. So how will it know what time it is?
Interactions as pure values #
This is the heart of the matter. The Polling Consumer must constantly look at the clock. It's under a deadline, and it must also measure durations of poll, handle, and idle operations. All of this is non-deterministic, so not pure. The program has to interact with impure operations during its entire lifetime. In fact, its ultimate decision to exit will be based on impure data. How can you model this in a pure fashion?
You can model long-running (impure) interactions by defining a small instruction set for an Abstract Syntax Tree (AST). That sounds intimidating, but once you get the hang of it, it becomes routine. In later articles, I'll expand on this, but for now I'll refer you to an excellent article by Scott Wlaschin, who explains the approach in F#.
data PollingInstruction msg next = CurrentTime (UTCTime -> next) | Poll ((Maybe msg, PollDuration) -> next) | Handle msg (HandleDuration -> next) | Idle IdleDuration (IdleDuration -> next) deriving (Functor)
This PollingInstruction sum type defines four cases of interaction. Each case is
- named after the interaction
- defines the type of data used as input arguments for the interaction
- and also defines a continuation; that is: a function that will be executed with the return value of the interaction
Handle case contains all three elements: the interaction is named Handle, the input to the interaction is of the generic type msg, and the continuation is a function that takes a HandleDuration value as input, and returns a value of the generic type next. In other words, the interaction takes a msg value as input, and returns a HandleDuration value as output. That duration is the time it took to handle the input message. (The intent is that the operation that 'implements' this interaction also actually handles the message, whatever that means.)
Likewise, the Idle interaction takes an IdleDuration as input, and also returns an IdleDuration. The intent here is that the 'implementation' of the interaction suspends itself for the duration of the input value, and returns the time it actually spent in suspension (which is likely to be slightly longer than the requested duration).
Both CurrentTime and Poll, on the other hand, are degenerate, because they take no input. You don't need to supply any input argument to read the current time. You could model that interaction as taking () ('unit') as an input argument (CurrentTime () (UTCTime -> next)), but the () is redundant and can be omitted. The same is the case for the Poll case, which returns a Maybe msg and how long the poll took.
(The PollingInstruction sum type defines four cases, which is also the number of cases defined by PollingState. This is a coincidence; don't read anything into it.)
The PollingInstruction type is generic in a way that you can make it a Functor. Haskell can do this for you automatically, using the DeriveFunctor language extension; that's what deriving (Functor) does. If you'd like to see how to explicitly make such a data structure a functor, please refer to the F# example; F# can't automatically derive functors, so you'll have to do it manually.
Since PollingInstruction is a Functor, we can make a Monad out of it. You use a free monad, which allows you to build a monad from any functor:
type PollingProgram msg = Free (PollingInstruction msg)
In Haskell, it's literally a one-liner, but in F# you'll have to write the code yourself. Thus, if you're interested in learning how this magic happens, I'm going to dissect this step in the next article.
The motivation for defining a Monad is that we get automatic syntactic sugar for our PollingProgram ASTs, via Haskell's do notation. In F#, we're going to write a computation expression builder to achieve the same effect.
The final building blocks for the specialised PollingProgram API is a convenience function for each case:
currentTime :: PollingProgram msg UTCTime currentTime = liftF (CurrentTime id) poll :: PollingProgram msg (Maybe msg, PollDuration) poll = liftF (Poll id) handle :: msg -> PollingProgram msg HandleDuration handle msg = liftF (Handle msg id) idle :: IdleDuration -> PollingProgram msg IdleDuration idle d = liftF (Idle d id)
More one-liners, as you can tell. These all use liftF to turn PollingInstruction cases into PollingProgram values. The degenerate cases CurrentTime and Poll simply become values, whereas the complete cases become (pure) functions.
Support functions #
You may have noticed that until now, I haven't written much 'code' in the sense that most people think of it. It's mostly been type declarations and a few one-liners. A strong and sophisticated type system like Haskell's enable you to shift some of the programming burden from 'real programming' to type definitions, but you'll still have to write some code.
Before we get to the state transitions proper, we'll look at some support functions. These will, I hope, serve as a good introduction to how to use the PollingProgram API.
One decision the Polling Consumer program has to make is to decide whether it should suspend itself for a short time. That's easy to express using the API:
shouldIdle :: IdleDuration -> UTCTime -> PollingProgram msg Bool shouldIdle (IdleDuration d) stopBefore = do now <- currentTime return $ d `addUTCTime` now < stopBefore
The shouldIdle function returns a small program that, when evaluated, will decide whether or not to suspend itself. It first reads the current time using the above currentTime value. While currentTime has the type PollingProgram msg UTCTime, due to Haskell's do notation, the now value simply has the type UTCTime. This enables you to use the built-in addUTCTime function (here written using infix notation) to add now to d (a NominalDiffTime value, due to pattern matching into IdleDuration).
Adding the idle duration d to the current time now gives you the time the program would resume, were it to suspend itself. The shouldIdle function compares that time to the stopBefore argument (another UTCTime value). If the time the program would resume is before the time it ought to stop, the return value is True; otherwise, it's False.
Since the entire function is defined within a do block, the return type isn't just Bool, but rather PollingProgram msg Bool. It's a little PollingProgram AST, but it looks like imperative code.
You sometimes hear the bon mot that Haskell is the world's greatest imperative language. The combination of free monads and do notation certainly makes it easy to define small grammars (dare I say DSLs?) that look like imperative code, while still being strictly functional.
The crux is that shouldIdle is pure. It looks impure, but it's not. It's an Abstract Syntax Tree, and it only becomes non-deterministic if interpreted by an impure interpreter (more on that later).
The purpose of shouldIdle is to decide whether or not to idle or exit. If the program decides to idle, it should return to the ready state, as per the above state diagram. In this state, it needs to decide whether or not to poll for a message. If there's a message, it should be handled, and all of that takes time. In the ready state, then, the program must figure out how much time it thinks that handling a message will take.
One way to do that is to consider the observed durations so far. This helper function calculates the expected duration based on the average and standard deviation of the previous durations:
calculateExpectedDuration :: NominalDiffTime -> [CycleDuration] -> NominalDiffTime calculateExpectedDuration estimatedDuration [] = estimatedDuration calculateExpectedDuration _ statistics = toEnum $ fromEnum $ avg + stdDev * 3 where fromCycleDuration :: CycleDuration -> Float fromCycleDuration (CycleDuration (PollDuration pd) (HandleDuration hd)) = toEnum $ fromEnum $ pd + hd durations = fmap fromCycleDuration statistics l = toEnum $ length durations avg = sum durations / l stdDev = sqrt (sum (fmap (\x -> (x - avg) ** 2) durations) / l)
I'm not going to dwell much on this function, as it's a normal, pure, mathematical function. The only feature I'll emphasise is that in order to call it, you must pass an estimatedDuration that will be used when statistics is empty. This is because you can't calculate the average of an empty list. This estimated duration is simply your wild guess at how long you think it'll take to handle a message.
With this helper function, you can now write a small PollingProgram that decides whether or not to poll:
shouldPoll :: NominalDiffTime -> UTCTime -> [CycleDuration] -> PollingProgram msg Bool shouldPoll estimatedDuration stopBefore statistics = do let expectedHandleDuration = calculateExpectedDuration estimatedDuration statistics now <- currentTime return $ expectedHandleDuration `addUTCTime` now < stopBefore
Notice that the shouldPoll function looks similar to shouldIdle. As an extra initial step, it first calculates expectedHandleDuration using the above calculateExpectedDuration function. With that, it follows the same two steps as shouldIdle.
This function is also pure, because it returns an AST. While it looks impure, it's not, because it doesn't actually do anything.
Transitions #
Those are all the building blocks required to write the state transitions. In order to break down the problem in manageable chunks, you can write a transition function for each state. Such a function would return the next state, given a particular input state.
While it'd be intuitive to begin with the ready state, let's instead start with the simplest transition. In the end state, nothing should happen, so the transition is a one-liner:
transitionFromStopped :: Monad m => [CycleDuration] -> m (PollingState msg) transitionFromStopped statistics = return $ Stopped statistics
Once stopped, the program stays in the Stopped state. This function simply takes a list of CycleDuration values and elevates them to a monad type. Notice that the return value isn't specifically a PollingProgram, but any monad. Since PollingProgram is a monad, that'll work too, though.
Slightly more complicated than transitionFromStopped is the transition from the received state. There's no branching in that case; simply handle the message, measure how long it took, add the observed duration to the statistics, and transition back to ready:
transitionFromReceived :: [CycleDuration] -> PollDuration -> msg -> PollingProgram msg (PollingState msg) transitionFromReceived statistics pd msg = do hd <- handle msg return $ Ready (CycleDuration pd hd : statistics)
Again, this looks impure, but the return type is PollingProgram msg (PollingState msg), indicating that the return value is an AST. As is not uncommon in Haskell, the type declaration is larger than the implementation.
Things get slightly more interesting in the no message state. Here you get to use the above shouldIdle support function:
transitionFromNoMessage :: IdleDuration -> UTCTime -> [CycleDuration] -> PollingProgram msg (PollingState msg) transitionFromNoMessage d stopBefore statistics = do b <- shouldIdle d stopBefore if b then idle d >> return (Ready statistics) else return $ Stopped statistics
The first step in transitionFromNoMessage is calling shouldIdle. Thanks to Haskell's do notation, the b value is a simple Bool value that you can use to branch. If b is True, then first call idle and then return to the Ready state; otherwise, exit to the Stopped state.
Notice how PollingProgram values are composable. For instance, shouldIdle defines a small PollingProgram that can be (re)used in a bigger program, such as in transitionFromNoMessage.
Finally, from the ready state, the program can transition to three other states, so this is the most complex transition:
transitionFromReady :: NominalDiffTime -> UTCTime -> [CycleDuration] -> PollingProgram msg (PollingState msg) transitionFromReady estimatedDuration stopBefore statistics = do b <- shouldPoll estimatedDuration stopBefore statistics if b then do pollResult <- poll case pollResult of (Just msg, pd) -> return $ ReceivedMessage statistics pd msg (Nothing , pd) -> return $ NoMessage statistics pd else return $ Stopped statistics
Like transitionFromNoMessage, the transitionFromReady function first calls a supporting function (this time shouldPoll) in order to make a decision. If b is False, the next state is Stopped; otherwise, the program moves on to the next step.
The program polls for a message using the poll helper function defined above. While poll is a PollingProgram msg (Maybe msg, PollDuration) value, thanks to do notation, pollResult is a Maybe msg, PollDuration value. Matching on that value requires you to handle two separate cases: If a message was received (Just msg), then return a ReceivedMessage state with the message. Otherwise (Nothing), return a NoMessage state.
With those four functions you can now define a function that can transition from any input state:
transition :: NominalDiffTime -> IdleDuration -> UTCTime -> PollingState msg -> PollingProgram msg (PollingState msg) transition estimatedDuration idleDuration stopBefore state = case state of Ready stats -> transitionFromReady estimatedDuration stopBefore stats ReceivedMessage stats pd msg -> transitionFromReceived stats pd msg NoMessage stats _ -> transitionFromNoMessage idleDuration stopBefore stats Stopped stats -> transitionFromStopped stats
The transition function simply pattern-matches on the input state and delegates to each of the four above transition functions.
A short philosophical interlude #
All code so far has been pure, although it may not look that way. At this stage, it may be reasonable to pause and consider: what's the point, even?
After all, when interpreted, a PollingProgram can (and, in reality, almost certainly will) have impure behaviour. If we create an entire executable upon this abstraction, then we've essentially developed a big program with impure behaviour...
Indeed we have, but the alternative would have been to write it all in the context of IO. If you'd done that, then you'd allow any non-deterministic, side-effecty behaviour anywhere in your program. At least with a PollingProgram, any reader will quickly learn that only a maximum of four impure operations can happen. In other words, you've managed to control and restrict the impurity to exactly those interactions you want to model.
Not only that, but the type of impurity is immediately visible as part of a value's type. In a later article, you'll see how different impure interaction APIs can be composed.
Interpretation #
At this point, you have a program in the form of an AST. How do you execute it?
You write an interpreter:
interpret :: PollingProgram Message a -> IO a interpret program = case runFree program of Pure r -> return r Free (CurrentTime next) -> getCurrentTime >>= interpret . next Free (Poll next) -> pollImp >>= interpret . next Free (Handle msg next) -> handleImp msg >>= interpret . next Free (Idle d next) -> idleImp d >>= interpret . next
When you turn a functor into a monad using the Free constructor (see above), your functor is wrapped in a general-purpose sum type with two cases: Pure and Free. Your functor is always contained in the Free case, whereas Pure is the escape hatch. This is where you return the value of the entire computation.
An interpreter must match both Pure and Free. Pure is easy, because you simply return the result value.
In the Free case, you'll need to match each of the four cases of PollingInstruction. In all four cases, you invoke an impure implementation function, pass its return value to next, and finally recursively invoke interpret with the value returned by next.
Three of the implementations are details that aren't of importance here, but if you want to review them, the entire source code for this article is available as a gist. The fourth implementation is the built-in getCurrentTime function. They are all impure; all return IO values. This also implies that the return type of the entire interpret function is IO a.
This particular interpreter is impure, but nothing prevents you from writing a pure interpreter, for example for use in unit testing.
Execution #
You're almost done. You have a function that returns a new state for any given input state, as well as an interpreter. You need a function that can repeat this in a loop until it reaches the Stopped state:
run :: NominalDiffTime -> IdleDuration -> UTCTime -> PollingState Message -> IO (PollingState Message) run estimatedDuration idleDuration stopBefore state = do ns <- interpret $ transition estimatedDuration idleDuration stopBefore state case ns of Stopped _ -> return ns _ -> run estimatedDuration idleDuration stopBefore ns
This recursive function calls transition with the input state. You may recall that transition returns a PollingProgram msg (PollingState msg) value. Passing this value to interpret returns an IO (PollingState Message) value, and because of the do notation, the new state (ns) is a PollingState Message value.
You can now pattern match on ns. If it's a Stopped value, you return the value. Otherwise, you recursively call run once more.
The run function keeps doing this until it reaches the Stopped state.
Finally, then, you can write the entry point for the program:
main :: IO () main = do timeAtEntry <- getCurrentTime let estimatedDuration = 2 let idleDuration = IdleDuration 5 let stopBefore = addUTCTime 60 timeAtEntry s <- run estimatedDuration idleDuration stopBefore $ Ready [] timeAtExit <- getCurrentTime putStrLn $ "Elapsed time: " ++ show (diffUTCTime timeAtExit timeAtEntry) putStrLn $ printf "%d message(s) handled." $ report s
It defines the initial input parameters:
- My wild guess about the handle duration is 2 seconds
- I'd like the idle duration to be 5 seconds
- The program should run for 60 seconds
Ready []. These are all the arguments you need to call run.
Once run returns, you can print the number of messages handled using a (trivial) report function that I haven't shown (but which is available in the gist).
If you run the program, it'll produce output similar to this:
Polling Handling Polling Handling Polling Handling Polling Sleeping Polling Handling Polling Sleeping Polling Handling Polling Handling Polling Sleeping Polling Sleeping Polling Sleeping Polling Sleeping Polling Sleeping Polling Handling Polling Handling Polling Handling Polling Handling Polling Sleeping Polling Elapsed time: 56.6835022s 10 message(s) handled.
It does, indeed, exit before 60 seconds have elapsed.
Summary #
You can model long-running interactions with an Abstract Syntax Tree. Without do notation, writing programs as 'raw' ASTs would be cumbersome, but turning the AST into a (free) monad makes it all quite palatable.
Haskell's sophisticated type system makes this a fairly low-hanging fruit, once you understand how to do it. You can also port this type of design to F#, although, as you shall see next, more boilerplate is required.
Next: Pure times in F#.
Pure times
How to interact with the system clock using strict functional programming.
A couple of years ago, I published an article called Good times with F#. Unfortunately, that article never lived up to my expectations. Not that I don't have a good time with F# (I do), but the article introduced an attempt to model execution durations of operations in a functional manner. The article introduced a Timed<'a> generic type that I had high hopes for.
Later, I published a Pluralsight course called Type-Driven Development with F#, in which I used Timed<'a> to implement a Polling Consumer. It's a good course that teaches you how to let F#'s type system give you rapid feedback. You can read a few articles that highlight the important parts of the course.
There's a problem with the implementation, though. It's not functional.
It's nice F# code, but F# is this friendly, forgiving, multi-paradigmatic language that enables you to get real work done. If you want to do this using partial application as a replacement for Dependency Injection, it'll let you. It is, however, not functional.
Consider, as an example, this function:
// (Timed<TimeSpan list> -> bool) -> (unit -> Timed<'a>) -> Timed<TimeSpan list> // -> State let transitionFromNoMessage shouldIdle idle nm = if shouldIdle nm then idle () |> Untimed.withResult nm.Result |> ReadyState else StoppedState nm.Result
The idle function has the type unit -> Timed<'a>. This can't possibly be a pure function, since a deterministic function can't produce a value from nothing when it doesn't know the type of the value. (In F#, this is technically not true, since we could return null for all reference types, and 'zero' for all value types, but even so, it should be clear that we can't produce any useful return value in a deterministic manner.)
The same argument applies, in weaker form, to the shouldIdle function. While it is possible to write more than one pure function with the type Timed<TimeSpan list> -> bool, the intent is that it should look at the time statistics and the current time, and decide whether or not it's 'safe' to poll again. Getting the current time from the system clock is a non-deterministic operation.
Ever since I discovered that Dependency Injection is impossible in functional programming, I knew that I had to return to the Polling Consumer example and show how to implement it in a truly functional style. In order to be sure that I don't accidentally call an impure function from a 'pure' function, I'll first rewrite the Polling Consumer in Haskell, and afterwards translate the Haskell code to F#. When reading, you can skip the Haskell article and go directly to the F# article, or vice versa, if you like.
Next: Pure times in Haskell.
Fractal trees with PureScript
A fractal tree drawn with PureScript
Last week, I attended Mathias Brandewinder's F# (and Clojure) dojo in Copenhagen, and had great fun drawing a fractal tree in F# together with other attendees. Afterwards, I started thinking that it'd be fairly easy to port the F# code to Haskell, but then I reconsidered. The combination of Haskell, Windows, and drawing sounded intimidating. This seemed a good opportunity to take PureScript for a spin, because that would enable me to draw the tree on an HTML canvas.
In case you're wondering, a fractal tree is simply a tree that branches infinitely in (I suppose) a deterministic fashion. Here's an example of the output of the code of this article:
This is my first attempt at PureScript, and I think I spent between five and ten hours in total. Most of them I used to figure out how to install PureScript, how to set up a development environment, and so on. All in all I found the process pleasing.
While it's a separate, independent language, PureScript is clearly a descendant of Haskell, and the syntax is similar.
Separating data from effects #
In functional programming, you routinely separate data from effects. Instead of trying to both draw and calculate branches of a tree in a single operation, you figure out how to first define a fractal tree as data, and then subsequently you can draw it.
A generic binary tree is a staple of functional programming. Here's one way to do it:
data Tree a = Leaf a | Node a (Tree a) (Tree a)
Such a tree is either a leaf node with a generically typed value, or an (intermediate) node with a value and two branches, which are themselves (sub)trees.
In a sense, this definition is an approximation, because a 'real' fractal tree has no leafs. In Haskell you can easily define infinite trees, because Haskell is lazily evaluated. PureScript, on the other hand, is eagerly evaluated, so infinite recursion would require jumping through some hoops, and I don't think it's important in this exercise.
While the above tree type can contain values of any type, in this exercise, it should contain line segments. One way to do this is to define a Line record type:
data Line = Line { x :: Number, y :: Number, angle :: Number, length :: Number, width :: Number }
This is a type with five labelled values, all of them numbers. x and y are coordinates for the origin of the line, angle defines the angle (measured in radians) from the origin, and length the length of the line. In a similarly obvious vein, width denotes the width of the line, although this data element has no impact on the calculation of the tree. It's purely a display concern.
Given the first four numbers in a Line value, you can calculate the endpoint of a line:
endpoint :: forall r. { x :: Number , y :: Number , angle :: Number , length :: Number | r } -> Tuple Number Number endpoint line = -- Flip the y value because Canvas coordinate system points down from upper -- left corner Tuple (line.x + line.length * cos line.angle) (-(-line.y + line.length * sin line.angle))
This may look more intimidating than it really is. The first seven lines are simply the (optional) type declaration; ignore that for a minute. The function itself is a one-liner, although I've formatted it on several lines in order to stay within an 80 characters line width. It simply performs a bit of trigonometry in order to find the endpoint of a line with an origin, angle, and length. As the code comment states, it negates the y value because the HTML canvas coordinate system points down instead of up (larger y values are further towards the bottom of the screen than smaller values).
The function calculates a new set of coordinates for the endpoint, and returns them as a tuple. In PureScript, tuples are explicit and created with the Tuple data constructor.
In general, as far as I can tell, you have less need of tuples in PureScript, because instead, you have row type polymorphism. This is still a new concept to me, but as far as I can tell, it's a sort of static duck typing. You can see it in the type declaration of the endpoint function. The function takes a line argument, the type of which is any record type that contains x, y, angle, and length labels of the Number type. For instance, as you'll soon see, you can pass a Line value to the endpoint function.
Creating branches #
In a fractal tree, you calculate two branches for any given branch. Typically, in order to draw a pretty picture, you make the sub-branches smaller than the parent branch. You also incline each branch an angle from the parent branch. While you can hard-code the values for these operations, you can also pass them as arguments. In order to prevent an explosion of primitive function arguments, I collected all such parameters in a single data type:
data FractalParameters = FractalParameters { leftAngle :: Number, rightAngle :: Number, shrinkFactor :: Number }
This is a record type similar to the Line type you've already seen.
When you have a FractalParameters value and a (parent) line, you can calculate its branches:
createBranches :: FractalParameters -> Line -> Tuple Line Line createBranches (FractalParameters p) (Line line) = Tuple left right where Tuple x y = endpoint line left = Line { x: x, y: y, angle: pi * (line.angle / pi + p.leftAngle), length: (line.length * p.shrinkFactor), width: (line.width * p.shrinkFactor) } right = Line { x: x, y: y, angle: pi * (line.angle / pi - p.rightAngle), length: (line.length * p.shrinkFactor), width: (line.width * p.shrinkFactor) }
The createBranches function returns a tuple of Line values, one for the left branch, and one for the right branch. First, it calls endpoint with line. Notice that line is a Line value, and because Line defines x, y, angle, and length labels, it can be used as an input argument. This type-checks because of row type polymorphism.
Given the endpoint of the parent line, createBranches then creates two new Line values (left and right) with that endpoint as their origins. Both of these values are modified with the FractalParameters argument, so that they branch off to the left and the right, and also shrink in an aesthetically pleasing manner.
Creating a tree #
Now that you can calculate the branches of a line, you can create a tree using recursion:
createTree :: Int -> FractalParameters -> Line -> Tree Line createTree depth p line = if depth <= 0 then Leaf line else let Tuple leftLine rightLine = createBranches p line left = createTree (depth - 1) p leftLine right = createTree (depth - 1) p rightLine in Node line left right
The createTree function takes a depth argument, which specifies the depth (or is it the height?) of the tree. The reason I called it depth is because createTree is recursive, and depth controls the depth of the recursion. If depth is zero or less, the function returns a Leaf node containing the input line.
Otherwise, it calls createBranches with the input line, and recursively calls createTree for each of these branches, but with a decremented depth. It then returns a Node containing the input line and the two sub-trees left and right.
This implementation isn't tail-recursive, but the above image was generated with a recursion depth of only 10, so running out of stack space wasn't my biggest concern.
Drawing the tree #
With the createTree function you can create a fractal tree, but it's no fun if you can't draw it. You can use the Graphics.Canvas module in order to draw on an HTML canvas. First, here's how to draw a single line:
drawLine :: Context2D -> Line -> Eff (canvas :: CANVAS) Unit drawLine ctx (Line line) = do let Tuple x' y' = endpoint line void $ strokePath ctx $ do void $ moveTo ctx line.x line.y void $ setLineWidth line.width ctx void $ lineTo ctx x' y' closePath ctx
While hardly unmanageable, I was surprised that I wasn't able to find a pre-defined function that would let me draw a line. Perhaps I was looking in the wrong place.
With this helper function, you can now draw a tree using pattern matching:
drawTree :: Context2D -> Tree Line -> Eff (canvas :: CANVAS) Unit drawTree ctx (Leaf line) = drawLine ctx line drawTree ctx (Node line left right) = do drawLine ctx line drawTree ctx left drawTree ctx right
If the input tree is a Leaf value, the first line matches and the function simply draws the line, using the drawLine function.
When the input tree is a Node value, the function first draws the line associated with that node, and then recursively calls itself with the left and right sub-trees.
Execution #
The drawTree function enables you to draw using a Context2D value, which you can create from an HTML canvas:
mcanvas <- getCanvasElementById "canvas" let canvas = unsafePartial (fromJust mcanvas) ctx <- getContext2D canvas
From where does the "canvas" element come? Ultimately, PureScript compiles to JavaScript, and you can put the compiled script in an HTML file together with a canvas element:
<body> <canvas id="canvas" width="800" height="800"></canvas> <script src="index.js" type="text/javascript"></script> </body>
Once you have a Context2D value, you can draw a tree. Here's the whole entry point, including the above canvas-finding code:
main :: Eff (canvas :: CANVAS) Unit main = do mcanvas <- getCanvasElementById "canvas" let canvas = unsafePartial (fromJust mcanvas) ctx <- getContext2D canvas let trunk = Line { x: 300.0, y: 600.0, angle: (pi / 2.0), length: 100.0, width: 4.0 } let p = FractalParameters { leftAngle: 0.1, rightAngle: 0.1, shrinkFactor: 0.8 } let tree = createTree 10 p trunk drawTree ctx tree
After it finds the Context2D value, it hard-codes a trunk Line and a set of FractalParameters. From these, it creates a tree of size 10 and draws the tree in the beginning of this article.
You can fiddle with the parameters to your liking. For example, you can make the right angle wider than the left angle:
let p = FractalParameters { leftAngle: 0.1, rightAngle: 0.2, shrinkFactor: 0.8 }
This produces an asymmetric tree:
In order to compile the code, I used this command:
$ pulp browserify -t html/index.js
This compiles the PureScript code to a single index.js file, which is output to the html directory. This directory also contains the HTML file with the canvas.
You can find the entire PureScript file in this Gist.
Summary #
It was fun to try PureScript. I've been staying away from JavaScript-based development for many years now, but if I ever have to do some client-side development, I may consider it. So far, I've found that PureScript seems viable for drawing. How good it is if you need to interact with 'normal' web-pages or SPAs, I don't know (yet).
If you have some experience with Haskell, it looks like it's easy to get started with PureScript.
Using Polly with F# async workflows
How to use Polly as a Circuit Breaker in F# async workflows.
Release It! describes a stability design pattern called Circuit Breaker, which is used to fail fast if a downstream service is experiencing problems.
I recently had to add a Circuit Breaker to an F# async workflow, and although Circuit Breaker isn't that difficult to implement (my book contains an example in C#), I found it most prudent to use an existing implementation. Polly seemed a good choice.
In my F# code base, I was already working with an 'abstraction' of the type HttpRequestMessage -> Async<HttpResponseMessage>: given an HttpClient called client, the implementation is as simple as client.SendAsync >> Async.AwaitTask. Since SendAsync can throw HttpRequestException or WebException, I wanted to define a Circuit Breaker policy for these two exception types.
While Polly supports policies for Task-based APIs, it doesn't automatically work with F# async workflows. The problem is that whenever you convert an async workflow into a Task (using Async.AwaitTask), or a Task into an async workflow (using Async.StartAsTask), any exceptions thrown will end up buried within an AggregateException. In order to dig them out again, I first had to write this function:
// Exception -> bool let rec private isNestedHttpException (e : Exception) = match e with | :? AggregateException as ae -> ae.InnerException :: Seq.toList ae.InnerExceptions |> Seq.exists isNestedHttpException | :? HttpRequestException -> true | :? WebException -> true | _ -> false
This function recursively searches through all inner exceptions of an AggregateException and returns true if it finds one of the exception types I'm interested in handling; otherwise, it returns false.
This predicate enabled me to write the Polly policy I needed:
open Polly // int -> TimeSpan -> CircuitBreaker.CircuitBreakerPolicy let createPolicy exceptionsAllowedBeforeBreaking durationOfBreak = Policy .Handle<AggregateException>(fun ae -> isNestedHttpException ae) .CircuitBreakerAsync(exceptionsAllowedBeforeBreaking, durationOfBreak)
Since Polly exposes an object-oriented API, I wanted a curried alternative, so I also wrote this curried helper function:
// Policy -> ('a -> Async<'b>) -> 'a -> Async<'b> let private execute (policy : Policy) f req = policy.ExecuteAsync(fun () -> f req |> Async.StartAsTask) |> Async.AwaitTask
The execute function executes any function of the type 'a -> Async<'b> with a Polly policy. As you can see, there's some back-and-forth between Tasks and async workflows, so this is probably not the most efficient Circuit Breaker ever configured, but I wagered that since the underlying operation was going to involve an HTTP request and response, the overhead would be insignificant. No one has complained yet.
When Polly opens the Circuit Breaker, it throws an exception of the type BrokenCircuitException. Again because of all the marshalling, this also gets wrapped within an AggregateException, so I had to write another function to unwrap it:
// Exception -> bool let rec private isNestedCircuitBreakerException (e : Exception) = match e with | :? AggregateException as ae -> ae.InnerException :: Seq.toList ae.InnerExceptions |> Seq.exists isNestedCircuitBreakerException | :? CircuitBreaker.BrokenCircuitException -> true | _ -> false
The isNestedCircuitBreakerException is similar to isNestedHttpException, so it'd be tempting to refactor. I decided, however, to rely on the rule of three and leave both functions as they were.
In my F# code I prefer to handle application errors using Either values instead of relying on exceptions, so I wanted to translate any BrokenCircuitException to a particular application error. With the above isNestedCircuitBreakerException predicate, this was now possible with a try/with expression:
// Policy -> ('a -> Async<'b>) -> 'a -> Async<Result<'b, BoundaryFailure>> let sendUsingPolicy policy send req = async { try let! resp = req |> execute policy send return Result.succeed resp with e when isNestedCircuitBreakerException e -> return Result.fail Controllers.StabilityFailure }
This function takes a policy, a send function that actually sends the request, and the request to send. If all goes well, the response is lifted into a Success case and returned. If the Circuit Breaker is open, a StabilityFailure value is returned instead.
Since the with expression uses an exception filter, all other exceptions will still be thrown from this function.
It might still be worthwhile to look into options for a more F#-friendly Circuit Breaker. One option would be to work with the Polly maintainers to add such an API to Polly itself. Another option would be to write a separate F# implementation.
Comments
There are two minor points I want to address: * I think instead of the recursive search for a nested exception you can use AggregateException.Flatten() |> Seq.exists ...
* And I know that you know that a major difference between
Async and Task is that a Task is typically started whereas an Async is not.
So it might be irritating that calling execute already starts the execution. If you wrapped the body of execute inside another async block it would be lazy as usual, I think.
Simple holidays
A story about arriving at the simplest solution that could possibly work.
The Zen of Python states: Simple is better than complex. If I've met a programmer who disagrees with that, I'm not aware of it. It's hardly a controversial assertion, but what does 'simplicity' mean? Can you even identify a simple solution?
I often see software developers defaulting to complex solutions, because a simpler solution isn't immediately obvious. In retrospect, a simple solution often is obvious, but only once you've found it. Until then, it's elusive.
I'd like to share a story in which I arrived at a simple solution after several false starts. I hope it can be an inspiration.
Dutch holidays #
Recently, I had to write some code that takes into account Dutch holidays. (In order to address any confusion that could arise from this: No, I'm not Dutch, I'm Danish, but currently, I'm doing some work on a system targeting a market in the Netherlands.) Specifically, given a date, I had to find the latest possible Dutch bank day on or before that date.
For normal week days (Monday to Friday), it's easy, because such a date is already a bank date. In other words, in that case, you can simply return the input date. Also, in normal weeks, given a Saturday or Sunday, you should return the preceding Friday. The problem is, however, that some Fridays are holidays, and therefore not bank days.
Like many other countries, the Netherlands have complicated rules for determining official holidays. Here are some tricky parts:
- Some holidays always fall on the same date. One example is Bevrijdingsdag (Liberation Day), which always falls on May 5. This holiday celebrates a historic event (the end of World War II in Europe), so if you wanted to calculate bank holidays in the past, you'd have to figure out in which year this became a public holiday. Surely, at least, it must have been 1945 or later.
- Some holidays fall on specific week days. The most prominent example is Easter, where Goede Vrijdag (Good Friday) always (as the name implies) falls on a Friday. Which Friday exactly can be calculated using a complicated algorithm.
- One holiday (Koningsdag (King's Day)) celebrates the king's birthday. The date is determined by the currently reigning monarch's birthday, and it's called Queen's Day when the reigning monarch is a queen. Obviously, the exact date changes depending on who's king or queen, and you can't predict when it's going to change. And what will happen if the current monarch abdicates or dies before his or her birthday, but after the new monarch's birthday? Does that mean that there will be no such holiday that year? Or what about the converse? Could there be two such holidays if a monarch abdicates after his or her birthday, and the new monarch's birthday falls later the same year?
Figuring out if a date is a bank day, then, is what you might call an 'interesting' problem. How would you solve it? Before you read on, take a moment to consider how you'd attempt to solve the problem. If you will, you can consider the test cases immediately below to get a better sense of the problem.
Test cases #
Here's a small set of test cases that I wrote in order to describe the problem:
| Test case | Input date | Expected output |
|---|---|---|
| Monday | 2017-03-06 | 2017-03-06 |
| Tuesday | 2017-03-07 | 2017-03-07 |
| Wednesday | 2017-03-08 | 2017-03-08 |
| Thursday | 2017-03-09 | 2017-03-09 |
| Friday | 2017-03-10 | 2017-03-10 |
| Saturday | 2017-03-11 | 2017-03-10 |
| Sunday | 2017-03-12 | 2017-03-10 |
| Good Friday | 2017-04-14 | 2017-04-13 |
| Saturday after Good Friday | 2017-04-15 | 2017-04-13 |
| Sunday after Good Friday | 2017-04-16 | 2017-04-13 |
| Easter Monday | 2017-04-17 | 2017-04-13 |
| Ascension Day - Thursday | 2017-05-25 | 2017-05-24 |
| Whit Monday | 2110-05-26 | 2110-05-23 |
| Liberation Day | 9713-05-05 | 9713-05-04 |
Option: query a third-party service #
How would you solve the problem? The first solution that occurred to me was to use a third-party service. My guess is that most developers would consider this option. After all, it's essentially third-part data. The official holidays are determined by a third party, in this case the Dutch state. Surely, some Dutch official organisation would publish the list of official holidays somewhere. Perhaps, if you're lucky, there's even an on-line service you can query in order to download the list of holidays in some machine-readable format.
There are, however, problems with this alternative: if you query such a service each time you need to find an appropriate bank date, how are you going to handle network errors? What if the third-part service is (temporarily) unavailable?
Since I'm trying to figure out bank dates, you may already have guessed that I'm handling money, so it's not desirable to simple throw an exception and say that a caller would have to try again later. This could lead to loss of revenue.
Querying a third-party service every time you need to figure out a Dutch bank holiday is out of the question for that reason. It's also likely to be inefficient.
Option: cache third-party data #
Public holidays rarely change, so your next attempt could be a variation of the previous. Use third-party data, but instead of querying a third-party service every time you need the information, cache it.
The problem with caching is that you're not guaranteed that the data you seek is in the cache. At application start, caches are usually empty. You'd have to rely on making one good query to the third-party data source in order to put the data in the cache. Only if that succeeds can you use the cache. This, again, leaves you vulnerable to the normal failure modes of distributed computing. If you can't reach the third-party data source, you have nothing to put in the cache.
This can be a problem at application start, or when the cache data expires.
Using a cache reduces the risk that the data is unavailable, but it doesn't eliminate it. It also adds complexity in the form of a cache that has to be configured and managed. Granted, you can use a reusable cache library or service to minimise that cost, so it may not be a big deal. Still, when making a decision about application architecture, I think it helps to explicitly identify advantages and disadvantages.
Using a cache felt better to me, but I still wasn't happy. Too many things could go wrong.
Option: persistent cache #
An incremental improvement on the previous option would be to write the cache data to persistent storage. This takes care of the issue with the cache being empty at application start-up. You can even deal with cache expiry by keep using stale data if you can't reach the 'official' source of the data.
It leaves me a bit concerned, though, because if you allow the system to continue working with stale data, perhaps the application could enter a state where the data never updates. This could happen if the official data source moves, or changes format. In such a case, your application would keep trying to refresh the cache, and it would permanently fail. It would permanently run with stale data. Would you ever discover that problem?
My concern is that the application could silently fail. You could counter that by logging a warning somewhere, but that would introduce a permanent burden on the team responsible for operating the application. This isn't impossible, but it does constitute an extra complexity. This alternative still didn't feel good to me.
Option: cron #
Because I wasn't happy with any of the above alternatives, I started looking for different approaches to the problem. For a short while, I considered using a .NET implementation of cron, with a crontab file. As far as I can tell, though there's no easy way to define Easter using cron, so I quickly abandoned that line of inquiry.
Option: Nager.Date #
I wasn't entirely done with idea of calculating holidays on the fly. While calculating Easter is complicated, it can be done; there is a well-defined algorithm for it. Whenever I run into a general problem like this, I assume that someone has already done the required work, and this is also the case here. I quickly found an open source library called Nager.Date; I'm sure that there are other alternatives, but Nager.Date looks like it's more than good enough.
Such a library would be able to calculate all holidays for a given year, based on the algorithms embedded in it. That looked really promising.
And yet... again, I was concerned. Official holidays are, as we've already established, politically decided. Using an algorithmic approach is fundamentally wrong, because that's not really how the holidays are determined. Holidays are defined by decree; it just so happens that some of the decrees take the form of an algorithm (such as Easter).
What would happen if the Dutch state decides to add a new holiday? Or to take one away? Of when a new monarch is crowned? In order to handle such changes, we'd now have to hope that Nager.Date would be updated. We could try to make that more likely to happen by sending a pull request, but we'd still be vulnerable to a third party. What if the maintainer of Nager.Date is on vacation?
Even if you can get a change into a library like Nager.Date, how is the algorithmic approach going to deal with historic dates? If the monarch changes, you can update the library, but does it correctly handle dates in the past, where the King's Day was different?
Using an algorithm to determine a holiday seemed promising, but ultimately, I decided that I didn't like this option either.
Option: configuration file #
My main concern about using an algorithm is that it'd make it difficult to handle arbitrary changes and exceptional cases. If we'd use a configuration file, on the other hand, we could always edit the configuration file in order to add or remove holidays for a given year.
In essence, I was envisioning a configuration file that simply contained a list of holidays for each year.
That sounds fairly simple and maintainable, but from where should the data come?
You could probably download a list of official holidays for the next few years, like 2017, 2018, 2019, and so on, but the list would be finite, and probably not cover more than a few years into the future.
What if, for example, I'd only be able to find an official list that goes to 2020? What will happen, then, when our application enters 2021? To the rest of the code base, it'd look like there were no holidays in 2021.
At this time we can expect that new official lists have been published, so a programmer could obtain such a list and update the configuration file when it's time. This, unfortunately, is easy to forget. Four years in the future, perhaps none of the original programmers are left. It's more than likely that no one will remember to do this.
Option: algorithm-generated configuration file #
The problem that the configuration data could 'run out' can be addressed by initialising the configuration file with data generated algorithmically. You could, for example, ask Nager.Date to generate all the holidays for the next many years. In fact, the year 9999 is the maximum year handled by .NET's System.DateTime, so you could ask it to generate all the holidays until 9999.
That sounds like a lot, but it's only about half a megabyte of data...
This solves the problem of 'running out' of holiday data, but still enables you to edit the holiday data when it changes in the future. For example, if the King's Day changes in 2031, you can change all the King's Day values from 2031 onward, while retaining the correct values for the previous years.
This seems promising...
Option: hard-coded holidays #
I almost decided to use the previous, configuration-based solution, and I was getting ready to invent a configuration file format, and a reader for it, and so on. Then I recalled Mike Hadlow's article about the configuration complexity clock.
I'm fairly certain that the only people who would be editing a hypothetical holiday configuration file would be programmers. In that case, why put the configuration in a proprietary format? Why deal with the hassle of reading and parsing such a file? Why not put the data in code?
That's what I decided to do.
It's not a perfect solution. It's still necessary to go and change that code file when the holiday rules change. For example, when the King's Day changes, you'd have to edit the file.
Still, it's the simplest solution I could come up with. It has no moving parts, and uses a 'best effort' approach in order to guarantee that holidays will always be present. If you can come up with a better alternative, please leave a comment.
Data generation #
Nager.Date seemed useful for generating the initial set of holidays, so I wrote a small F# script that generated the necessary C# code snippets:
#r @"packages/Nager.Date.1.3.0/lib/net45/Nager.Date.dll" open System.IO open Nager.Date let formatHoliday (h : Model.PublicHoliday) = let y, m, d = h.Date.Year, h.Date.Month, h.Date.Day sprintf "new DateTime(%i, %2i, %2i), // %s/%s" y m d h.Name h.LocalName let holidays = [2017..9999] |> Seq.collect (fun y -> DateSystem.GetPublicHoliday (CountryCode.NL, y)) |> Seq.map formatHoliday File.WriteAllLines (__SOURCE_DIRECTORY__ + "/dutch-holidays.txt", holidays)
This script simply asks Nager.Date to calculate all Dutch holidays for the years 2017 to 9999, format them as C# code snippets, and write the lines to a text file. The size of that file is 4 MB, because the auto-generated code comments also take up some space.
First implementation attempt #
The next thing I did was to copy the text from dutch-holidays.txt to a C# code file, which I had already prepared with a class and a few methods that would query my generated data. The result looked like this:
public static class DateTimeExtensions { public static DateTimeOffset AdjustToLatestPrecedingDutchBankDay( this DateTimeOffset value) { var candidate = value; while (!(IsDutchBankDay(candidate.DateTime))) candidate = candidate.AddDays(-1); return candidate; } private static bool IsDutchBankDay(DateTime date) { if (date.DayOfWeek == DayOfWeek.Saturday) return false; if (date.DayOfWeek == DayOfWeek.Sunday) return false; if (dutchHolidays.Contains(date.Date)) return false; return true; } #region Dutch holidays private static DateTime[] dutchHolidays = { new DateTime(2017, 1, 1), // New Year's Day/Nieuwjaarsdag new DateTime(2017, 4, 14), // Good Friday/Goede Vrijdag new DateTime(2017, 4, 17), // Easter Monday/ Pasen new DateTime(2017, 4, 27), // King's Day/Koningsdag new DateTime(2017, 5, 5), // Liberation Day/Bevrijdingsdag new DateTime(2017, 5, 25), // Ascension Day/Hemelvaartsdag new DateTime(2017, 6, 5), // Whit Monday/Pinksteren new DateTime(2017, 12, 25), // Christmas Day/Eerste kerstdag new DateTime(2017, 12, 26), // St. Stephen's Day/Tweede kerstdag new DateTime(2018, 1, 1), // New Year's Day/Nieuwjaarsdag new DateTime(2018, 3, 30), // Good Friday/Goede Vrijdag // Lots and lots of dates... new DateTime(9999, 5, 6), // Ascension Day/Hemelvaartsdag new DateTime(9999, 5, 17), // Whit Monday/Pinksteren new DateTime(9999, 12, 25), // Christmas Day/Eerste kerstdag new DateTime(9999, 12, 26), // St. Stephen's Day/Tweede kerstdag }; #endregion }
My old computer isn't happy about having to compile 71,918 lines of C# in a single file, but it's doable, and as far as I can tell, Visual Studio caches the result of compilation, so as long as I don't change the file, there's little adverse effect.
Unit tests #
In order to verify that the implementation works, I wrote this parametrised test:
public class DateTimeExtensionsTests { [Theory] [InlineData("2017-03-06", "2017-03-06")] // Monday [InlineData("2017-03-07", "2017-03-07")] // Tuesday [InlineData("2017-03-08", "2017-03-08")] // Wednesday [InlineData("2017-03-09", "2017-03-09")] // Thursday [InlineData("2017-03-10", "2017-03-10")] // Friday [InlineData("2017-03-11", "2017-03-10")] // Saturday [InlineData("2017-03-12", "2017-03-10")] // Sunday [InlineData("2017-04-14", "2017-04-13")] // Good Friday [InlineData("2017-04-15", "2017-04-13")] // Saturday after Good Friday [InlineData("2017-04-16", "2017-04-13")] // Sunday after Good Friday [InlineData("2017-04-17", "2017-04-13")] // Easter Monday [InlineData("2017-05-25", "2017-05-24")] // Ascension Day - Thursday [InlineData("2110-05-26", "2110-05-23")] // Whit Monday [InlineData("9713-05-05", "9713-05-04")] // Liberation Day public void AdjustToLatestPrecedingDutchBankDayReturnsCorrectResult( string sutS, string expectedS) { var sut = DateTimeOffset.Parse(sutS); var actual = sut.AdjustToLatestPrecedingDutchBankDay(); Assert.Equal(DateTimeOffset.Parse(expectedS), actual); } }
All test cases pass. This works in [Theory], but unfortunately, it turns out, it doesn't work in practice.
When used in an ASP.NET Web API application, AdjustToLatestPrecedingDutchBankDay throws a StackOverflowException. It took me a while to figure out why, but it turns out that the stack size is smaller in IIS than when you run a 'normal' .NET process, such as an automated test.
System.DateTime is a value type, and as far as I can tell, it uses some stack space during initialisation. When the DateTimeExtensions class is first used, the static dutchHolidays array is initialised, and that uses enough stack space to exhaust the stack when running in IIS.
Final implementation #
The stack space problem seems to be related to DateTime initialisation. If I store a similar number of 64-bit integers in an array, it seems that there's no problem.
First, I had to modify the formatHoliday function:
let formatHoliday (h : Model.PublicHoliday) = let t, y, m, d = h.Date.Ticks, h.Date.Year, h.Date.Month, h.Date.Day sprintf "%19iL, // %i-%02i-%02i, %s/%s" t y m d h.Name h.LocalName
This enabled me to generate a new file with C# code fragments, but now containing ticks instead of DateTime values. Copying those C# fragments into my file gave me this:
public static class DateTimeExtensions { public static DateTimeOffset AdjustToLatestPrecedingDutchBankDay( this DateTimeOffset value) { var candidate = value; while (!(IsDutchBankDay(candidate.DateTime))) candidate = candidate.AddDays(-1); return candidate; } private static bool IsDutchBankDay(DateTime date) { if (date.DayOfWeek == DayOfWeek.Saturday) return false; if (date.DayOfWeek == DayOfWeek.Sunday) return false; if (dutchHolidays.Contains(date.Date.Ticks)) return false; return true; } #region Dutch holidays private static long[] dutchHolidays = { 636188256000000000L, // 2017-01-01, New Year's Day/Nieuwjaarsdag 636277248000000000L, // 2017-04-14, Good Friday/Goede Vrijdag 636279840000000000L, // 2017-04-17, Easter Monday/ Pasen 636288480000000000L, // 2017-04-27, King's Day/Koningsdag 636295392000000000L, // 2017-05-05, Liberation Day/Bevrijdingsdag 636312672000000000L, // 2017-05-25, Ascension Day/Hemelvaartsdag 636322176000000000L, // 2017-06-05, Whit Monday/Pinksteren 636497568000000000L, // 2017-12-25, Christmas Day/Eerste kerstdag 636498432000000000L, // 2017-12-26, St. Stephen's Day/Tweede kerstdag 636503616000000000L, // 2018-01-01, New Year's Day/Nieuwjaarsdag 636579648000000000L, // 2018-03-30, Good Friday/Goede Vrijdag // Lots and lots of dates... 3155171616000000000L, // 9999-05-06, Ascension Day/Hemelvaartsdag 3155181120000000000L, // 9999-05-17, Whit Monday/Pinksteren 3155372928000000000L, // 9999-12-25, Christmas Day/Eerste kerstdag 3155373792000000000L, // 9999-12-26, St. Stephen's Day/Tweede kerstdag }; #endregion }
That implementation still passes all tests, and works at in practice as well.
Conclusion #
It took me some time to find a satisfactory solution. I had more than once false start, until I ultimately arrived at the solution I've described here. I consider it simple because it's self-contained, deterministic, easy to understand, and fairly easy to maintain. I even left a comment in the code (not shown here) that described how to recreate the configuration data using the F# script shown here.
The first solution that comes into your mind may not be the simplest solution, but if you take some time to consider alternatives, you may save yourself and your colleagues some future grief.
Comments
What do you think about creating an "admin page" that would allow users to configure the bank holidays themselves (which would then be persisted in the application database)? This moves the burden of correctness to the administrators of the application, who I'm sure are highly motivated to get this right - as well as maintain it. It also removes the need for a deployment in the face of changing holidays.
For the sake of convenience, you could still "seed" the database with the values generated by your F# script
jadarnel27, thank you for writing. Your suggestion could be an option as well, but is hardly the simplest solution. In order to implement that, I'd need to add an administration web site for my application, program the user interface, connect the administration site and my original application (a REST API) to a persistent data source, write code for input validation, etcetera.
Apart from all that work, the bank holidays would have to be stored in an out-of-process data store, such as a database or NoSQL data store, because the REST API that needs this feature is running in a server farm. This adds latency to each lookup, as well as a potential error source. What should happen if the connection to the data store is broken? Additionally, such a data store should be backed up, so we'd also need to establish an operational procedure to ensure that that happens.
It was never a requirement that the owners of the application should be able to administer this themselves. It's certainly an option, but it's so much more complex than the solution outlined above that I think one should start by making a return-on-investment analysis.
Another option: Calculate the holidays! I think you might find som useful code in my HolidaysAPI. It is even in F#, and the Web project is based upon a course or blog post by you.
Alf, thank you for writing. Apart from the alternative library, how is that different from the option I covered under the heading Option: Nager.Date?
Great post, thanks. The minor point here is that it is probably not so effective to do Contains over long[]. I'd consider using something that can check the value existance faster.
EQR, thank you for writing. The performance profile of the implementation wasn't my main concern with this article, so it's likely that it can be improved.
I did do some lackadaisical performance testing, but didn't detect any measurable difference between the implementation shown here, and one using a HashSet. On the other hand, there are other options I didn't try at all. One of these could be to perform a binary search, since the array is already ordered.
Hi Mark, thanks for this post. One small note on your selection of bank holidays. Liberation day is an official bank holiday, but only for civil servants, for us 'normal' people this only happens every 5 years. This is reflected in Nager.Date wrong here
Thomas, thank you for writing. That just goes to show, I think, that holiday calculation is as complicated as any other 'business logic'. It should be treated as such, and not as an algorithmic calculation.
A reusable ApiController Adapter
Refactor ApiController Adapters to a single, reusable base class.
Regular readers of this blog will know that I write many RESTful APIs in F#, using ASP.NET Web API. Since I like to write functional F#, but ASP.NET Web API is an object-oriented framework, I prefer to escape the object-oriented framework as soon as possible. (In general, it makes good architectural sense to write most of your code as framework-independent as possible.)
(Regular readers will also have seen the above paragraph before.)
To bridge the gap between the object-oriented framework and my functional code, I implement Controller classes like this:
type CreditCardController (imp) = inherit ApiController () member this.Post (portalId : string, req : PaymentDtr) : IHttpActionResult = match imp portalId req with | Success (resp : PaymentDtr) -> this.Ok resp :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _
The above example is a Controller that handles incoming payment data. It immediately delegates all work to an injected imp function, and pattern matches on the return value in order to return correct responses.
This CreditCardController extends ApiController in order to work nicely with ASP.NET Web API, while the injected imp function is written using functional programming. If you want to be charitable, you could say that the Controller is an Adapter between ASP.NET Web API and the functional F# API that actually implements the service. If you want to be cynical, you could also call it an anti-corruption layer.
This works well, but tends to become repetitive:
open System open System.Web.Http type BoundaryFailure = | RouteFailure | ValidationFailure of string | IntegrationFailure of string type HomeController (imp) = inherit ApiController () [<AllowAnonymous>] member this.Get () : IHttpActionResult = match imp () with | Success (resp : HomeDtr) -> this.Ok resp :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _ type CreditCardController (imp) = inherit ApiController () member this.Post (portalId : string, req : PaymentDtr) : IHttpActionResult = match imp portalId req with | Success (resp : PaymentDtr) -> this.Ok resp :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _ type CreditCardRecurrentStartController (imp) = inherit ApiController () member this.Post (portalId : string, req : PaymentDtr) : IHttpActionResult = match imp portalId req with | Success (resp : PaymentDtr) -> this.Ok resp :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _ type CreditCardRecurrentController (imp) = inherit ApiController () member this.Post (portalId : string, transactionKey : string, req : PaymentDtr) : IHttpActionResult = match imp portalId transactionKey req with | Success (resp : PaymentDtr) -> this.Ok resp :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _ type PushController (imp) = inherit ApiController () member this.Post (portalId : string, req : PushRequestDtr) : IHttpActionResult = match imp portalId req with | Success () -> this.Ok () :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _
At this point in our code base, we had five Controllers, and they all had similar implementations. They all pass their input parameters to their injected imp functions, and they all pattern match in exactly the same way. There are, however, small variations. Notice that one of the Controllers expose an HTTP GET operation, whereas the other four expose a POST operation. Conceivably, there could also be Controllers that allow both GET and POST, and so on, but this isn't the case here.
The parameter list for each of the action methods also vary. Some take two arguments, one takes three, and the GET method takes none.
Another variation is that HomeController.Get is annotated with an [<AllowAnonymous>] attribute, while the other action methods aren't.
Despite these variations, it's possible to make the code less repetitive.
You'd think you could easily refactor the code by turning the identical pattern matches into a reusable function. Unfortunately, it's not so simple, because the methods used to return HTTP responses are all protected (to use a C# term for something that F# doesn't even have). You can call this.Ok () or this.NotFound () from a derived class, but not from a 'free' let-bound function.
After much trial and error, I finally arrived at this reusable base class:
type private Imp<'inp, 'out> = 'inp -> Result<'out, BoundaryFailure> [<AbstractClass>] type FunctionController () = inherit ApiController () // Imp<'a,'b> -> 'a -> IHttpActionResult member this.Execute imp req : IHttpActionResult = match imp req with | Success resp -> this.Ok resp :> _ | Failure RouteFailure -> this.NotFound () :> _ | Failure (ValidationFailure msg) -> this.BadRequest msg :> _ | Failure (IntegrationFailure msg) -> this.InternalServerError (InvalidOperationException msg) :> _
It's been more than a decade, I think, since I last used inheritance to enable reuse, but in this case I could find no other way because of the design of ApiController. It gets the job done, though:
type HomeController (imp : Imp<_, HomeDtr>) = inherit FunctionController () [<AllowAnonymous>] member this.Get () = this.Execute imp () type CreditCardController (imp : Imp<_, PaymentDtr>) = inherit FunctionController () member this.Post (portalId : string, req : PaymentDtr) = this.Execute imp (portalId, req) type CreditCardRecurrentStartController (imp : Imp<_, PaymentDtr>) = inherit FunctionController () member this.Post (portalId : string, req : PaymentDtr) = this.Execute imp (portalId, req) type CreditCardRecurrentController (imp : Imp<_, PaymentDtr>) = inherit FunctionController () member this.Post (portalId : string, transactionKey : string, req : PaymentDtr) = this.Execute imp (portalId, transactionKey, req) type PushController (imp : Imp<_, unit>) = inherit FunctionController () member this.Post (portalId : string, req : PushRequestDtr) = this.Execute imp (portalId, req)
Notice that all five Controllers now derive from FunctionController instead of ApiController. The HomeController.Get method is still annotated with the [<AllowAnonymous>] attribute, and it's still a GET operation, whereas all the other methods still implement POST operations. You'll also notice that the various Post methods have retained their varying number of parameters.
In order to make this work, I had to make one trivial change: previously, all the imp functions were curried, but that doesn't fit into a single reusable base implementation. If you consider the type of FunctionController.Execute, you can see that the imp function is expected to take a single input value of the type 'a (and return a value of the type Result<'b, BoundaryFailure>). Since any imp function can only take a single input value, I had to uncurry them all. You can see that now all the Post methods pass their input parameters as a single tuple to their injected imp function.
You may be wondering about the Imp<'inp, 'out> type alias. It's not strictly necessary, but helps keep the code clear. As I've attempted to indicate with the code comment above the Execute method, it's generic. When used in a derived Controller, the compiler can infer the type of 'a because it already knows the types of the input parameters. For example, in CreditCardController.Post, the input parameters are already annotated as string and PaymentDtr, so the compiler can easily infer the type of (portalId, req).
On the other hand, the compiler can't infer the type of 'b, because that value doesn't relate to IHttpActionResult. To help the compiler, I introduced the Imp type, because it enabled me to concisely annotate the type of the output value, while using a wild-card type for the input type.
I wouldn't mind getting rid of Controllers altogether, but this is as close as I've been able to get with ASP.NET Web API.
Comments
I find a few issues with your blog post. Technically, I don't think anything you write in it is wrong, but there are a few of the statements I find problematic in the sense that people will probably read the blog post and conclude that "this is the only solution because of X" when in fact X is trivial to circumvent.
The main issue I have with your post is the following:
You'd think you could easily refactor the code by turning the identical pattern matches into a reusable function. Unfortunately, it's not so simple, because the methods used to return HTTP responses are all protected (to use a C# term for something that F# doesn't even have). You can call this.Ok () or this.NotFound () from a derived class, but not from a 'free' let-bound function.
As stated earlier, there is nothing in your statement that is technically wrong, but I'd argue that you've reached the wrong conclusion due to lack of data. Or in this case familiarity with Web API and it's source code. If you go look at the source for ApiController, you will notice that while true, the methods are protected, they are also trivial one-liners (helper methods) calling public APIs. It is completely possible to create a helper ala:
// NOTE: Untested let handle (ctrl: ApiController) = function | Success of result -> OkNegotiatedContentResult (result, ctrl) | Failure RouteFailure -> NotFoundResult (ctrl) | Failure (ValidationFailure msg) -> BadRequestErrorMessageResult (msg, ctrl) | Failure (IntegrationFailure msg) -> ExceptionResult ((InvalidOperationException msg), ctrl)
Another thing you can do is implement IHttpActionResult on your discriminate union, so you can just return it directly from you controller, in which case you'd end up with code like this:
member this.Post (portalId : string, req : PaymentDtr) = imp portalId req
It's definitely a bit more work, but in no way is it undoable. Thirdly, Web API (and especially the new MVC Core which has taken over for it) is incredibly pluggable through it's DI. You don't have to use the base ApiController class if you don't want to. You can override the resolution logic, the handing of return types, routing, you name it. It should for instance be entirely doable to write a handler for "controllers" that look like this:
[<Controller>] module MyController = [<AllowAnonymous>] // assume impl is imported and in scope here - this controller has no DI let post (portalId : string) (req : PaymentDtr) = impl portalId req
This however would probably be a bit of work requiring quite a bit of reflection voodoo. But somebody could definitely do it and put it in a library, and it would be nuget-installable for all.
Anyways, I hope this shows you that there are more options to solve the problem. And who knows, you may have considered all of them and concluded them unviable. I've personally dug through the source code of both MVC and Web API a few times which is why I know a bunch of this stuff, and I just figured you might want to know some of it too :).
Aleksander, thank you for writing. I clearly have some scars from working with ASP.NET Web API since version 0.6 (or some value in that neighbourhood). In general, if a method is defined on ApiController, I've learned the hard way that such methods tend to be tightly coupled to the Controller. Often, such methods even look into the untyped context dictionary in the request message object, so I've gotten used to use them whenever they're present.
These scars have prevented me from pushing the envelope on the 'new' methods that return various IHttpActionResult objects, but as you write, they truly are thin wrappers over constructors.
This does, indeed, enable us to write the mapping of result values as a let-bound function. Thank you for pointing that out!
Mine ended up looking like the following. We've added a few more success and error cases since I originally wrote this article, so it looks more complex than the initial example.
let toHttpResult (controller : ApiController) result : IHttpActionResult = match result with | Success (OK resp) -> OkNegotiatedContentResult (resp, controller) :> _ | Success (Created (resp, location)) -> CreatedNegotiatedContentResult (location, resp, controller) :> _ | Failure RouteFailure -> NotFoundResult controller :> _ | Failure (ValidationFailure msg) -> BadRequestErrorMessageResult (msg, controller) :> _ | Failure (IntegrationFailure msg) -> let resp = controller.Request.CreateErrorResponse ( HttpStatusCode.InternalServerError, msg) ResponseMessageResult resp :> _ | Failure StabilityFailure -> let resp = new HttpResponseMessage (HttpStatusCode.ServiceUnavailable) resp.Headers.RetryAfter <- RetryConditionHeaderValue (TimeSpan.FromMinutes 5.) ResponseMessageResult resp :> _
Letting my BoundaryFailure discriminated union implement IHttpActionResult sounds promising, but how would that be possible?
The interface has a single method with the type CancellationToken -> Task<HttpResponseMessage>. In order to create e.g. NotFoundResult, you need either an HttpRequestMessage or an ApiController, and none of those are available when IHttpActionResult.ExecuteAsync is invoked.
When it comes to not having to derive from ApiController, I'm aware that even on the full .NET framework (we're not on .NET Core), 'all' the framework needs are IHttpController instances. As you imply, plugging into the framework is likely to be non-trivial, and so far, I haven't found that such an effort would be warranted. I might use it if someone else wrote it, though :)
Dependency rejection
In functional programming, the notion of dependencies must be rejected. Instead, applications should be composed from pure and impure functions.
This is the third article in a small article series called from dependency injection to dependency rejection. In the previous article in the series, you learned that dependency injection can't be functional, because it makes everything impure. In this article, you'll see what to do instead.
Indirect input and output #
One of the first concepts you learned when you learned to program was that units of operation (functions, methods, procedures) take input and produce output. Input is in the form of input parameters, and output is in the form of return values. (Sometimes, though, a method returns nothing, but we know from category theory that nothing is also a value (called unit).)
In addition to such input and output, a unit with dependencies also take indirect input, and produce indirect output:
When a unit queries a dependency for data, the data returned from the dependency is indirect input. In the restaurant reservation example used in this article series, when tryAccept calls readReservations, the returned reservations are indirect input.
Likewise, when a unit invokes a dependency, all arguments passed to that dependency constitute indirect output. In the example, when tryAccept calls createReservation, the reservation value it uses as input argument to that function call becomes output. The intent, in this case, is to save the reservation in a database.
From indirect output to direct output #
Instead of producing indirect output, you can refactor functions to produce direct output.
Such a refactoring is often problematic in mainstream object-oriented languages like C# and Java, because you wish to control the circumstances in which the indirect output must be produced. Indirect output often implies side-effects, but perhaps the side-effect must only happen when certain conditions are fulfilled. In the restaurant reservation example, the desired side-effect is to add a reservation to a database, but this must only happen when the restaurant has sufficient remaining capacity to serve the requested number of people. Since languages like C# and Java are statement-based, it can be difficult to separate the decision from the action.
In expression-based languages like F# and Haskell, it's trivial to decouple decisions from effects.
In the previous article, you saw a version of tryAccept with this signature:
// int -> (DateTimeOffset -> Reservation list) -> (Reservation -> int) -> Reservation // -> int option
The second function argument, with the type Reservation -> int, produces indirect output. The Reservation value is the output. The function even violates Command Query Separation and returns the database ID of the added reservation, so that's additional indirect input. The overall function returns int option: the database ID if the reservation was added, and None if it wasn't.
Refactoring the indirect output to direct output is easy, then: just remove the createReservation function and return the Reservation value instead:
// int -> (DateTimeOffset -> Reservation list) -> Reservation -> Reservation option let tryAccept capacity readReservations reservation = let reservedSeats = readReservations reservation.Date |> List.sumBy (fun x -> x.Quantity) if reservedSeats + reservation.Quantity <= capacity then { reservation with IsAccepted = true } |> Some else None
Notice that this refactored version of tryAccept returns a Reservation option value. The implication is that the reservation was accepted if the return value is a Some case, and rejected if the value is None. The decision is embedded in the value, but decoupled from the side-effect of writing to the database.
This function clearly never writes to the database, so at the boundary of your application, you'll have to connect the decision to the effect. To keep the example consistent with the previous article, you can do this in a tryAcceptComposition function, like this:
// Reservation -> int option let tryAcceptComposition reservation = reservation |> tryAccept 10 (DB.readReservations connectionString) |> Option.map (DB.createReservation connectionString)
Notice that the type of tryAcceptComposition remains Reservation -> int option. This is a true refactoring. The overall API remains the same, as does the behaviour. The reservation is added to the database only if there's sufficient remaining capacity, and in that case, the ID of the reservation is returned.
From indirect input to direct input #
Just as you can refactor from indirect output to direct output can you refactor from indirect input to direct input.
Again, in statement-based languages like C# and Java, this may be problematic, because you may wish to defer a query, or base it on a decision inside the unit. In expression-based languages you can decouple decisions from effects, and deferred execution can always be done by lazy evaluation, if that's required. In the case of the current example, however, the refactoring is easy:
// int -> Reservation list -> Reservation -> Reservation option let tryAccept capacity reservations reservation = let reservedSeats = reservations |> List.sumBy (fun x -> x.Quantity) if reservedSeats + reservation.Quantity <= capacity then { reservation with IsAccepted = true } |> Some else None
Instead of calling a (potentially impure) function, this version of tryAccept takes a list of existing reservations as input. It still sums over all the quantities, and the rest of the code is the same as before.
Obviously, the list of existing reservations must come from somewhere, like a database, so tryAcceptComposition will still have to take care of that:
// ('a -> 'b -> 'c) -> 'b -> 'a -> 'c let flip f x y = f y x // Reservation -> int option let tryAcceptComposition reservation = reservation.Date |> DB.readReservations connectionString |> flip (tryAccept 10) reservation |> Option.map (DB.createReservation connectionString)
The type and behaviour of this composition is still the same as before, but the data flow is different. First, the function queries the database, which is an impure operation. Then, it pipes the resulting list of reservations to tryAccept, which is now a pure function. It returns a Reservation option that's finally mapped to another impure operation, which writes the reservation to the database if the reservation was accepted.
You'll notice that I also added a flip function in order to make the composition more concise, but I could also have used a lambda expression when invoking tryAccept. The flip function is a part of Haskell's standard library, but isn't in F#'s core library. It's not crucial to the example, though.
Evaluation #
Did you notice that in the previous diagram, above, all arrows between the unit and its dependencies were gone? This means that the unit no longer has any dependencies:
Dependencies are, by their nature, impure, and since pure functions can't call impure functions, functional programming must reject the notion of dependencies. Pure functions can't depend on impure functions.
Instead, pure functions must take direct input and produce direct output, and the impure boundary of an application must compose impure and pure functions together in order to achieve the desired behaviour.
In the previous article, you saw how Haskell can be used to evaluate whether or not an implementation is functional. You can port the above F# code to Haskell to verify that this is the case.
tryAccept :: Int -> [Reservation] -> Reservation -> Maybe Reservation tryAccept capacity reservations reservation = let reservedSeats = sum $ map quantity reservations in if reservedSeats + quantity reservation <= capacity then Just $ reservation { isAccepted = True } else Nothing
This version of tryAccept is pure, and compiles, but as you learned in the previous article, that's not the crucial question. The question is whether the composition compiles?
tryAcceptComposition :: Reservation -> IO (Maybe Int) tryAcceptComposition reservation = runMaybeT $ liftIO (DB.readReservations connectionString $ date reservation) >>= MaybeT . return . flip (tryAccept 10) reservation >>= liftIO . DB.createReservation connectionString
This version of tryAcceptComposition compiles, and works as desired. The code exhibits a common pattern for Haskell: First, gather data from impure sources. Second, pass pure data to pure functions. Third, take the pure output from the pure functions, and do something impure with it.
It's like a sandwich, with the best parts in the middle, and some necessary stuff surrounding it.
Summary #
Dependencies are, by nature, impure. They're either non-deterministic, have side-effects, or both. Pure functions can't call impure functions (because that would make them impure as well), so pure functions can't have dependencies. Functional programming must reject the notion of dependencies.
Obviously, software is only useful with impure behaviour, so instead of injecting dependencies, functional programs must be composed in impure contexts. Impure functions can call pure functions, so at the boundary, an application must gather impure data, and use it to call pure functions. This automatically leads to the ports and adapters architecture.
This style of programming is surprisingly often possible, but it's not a universal solution; other alternatives exist.
Comments
Hi, Thank you for this blog post series. I also read your other posts on ports and adapters and the proposed architecture makes sense in terms of how it works, but I struggle to see the benefit in a real world application. Maybe let me explain my question with a quick example.
In the 2nd blog post of this series you demonstrated this function:
// int -> (DateTimeOffset -> Reservation list) -> (Reservation -> int) -> Reservation
// -> int option
let tryAccept capacity readReservations createReservation reservation =
let reservedSeats =
readReservations reservation.Date |> List.sumBy (fun x -> x.Quantity)
if reservedSeats + reservation.Quantity <= capacity
then createReservation { reservation with IsAccepted = true } |> Some
else NoneIf I understand it correctly this function is pure if readReservations and createReservation are both pure otherwise it is impure.
I also understand the benefit of having a pure function, because it is a lot easier to understand the code, test the code and reason about it. That makes sense as well :).
So in the 3rd blog post you make tryAccept a pure function, by removing the function dependencies and replacing it with simple values:
// int -> Reservation list -> Reservation -> Reservation option
let tryAccept capacity reservations reservation =
let reservedSeats = reservations |> List.sumBy (fun x -> x.Quantity)
if reservedSeats + reservation.Quantity <= capacity
then { reservation with IsAccepted = true } |> Some
else NoneHowever this was only possible because you essentially moved the impure code into another new function:
// Reservation -> int option
let tryAcceptComposition reservation =
reservation.Date
|> DB.readReservations connectionString
|> flip (tryAccept 10) reservation
|> Option.map (DB.createReservation connectionString)So after all the application hasn't really reduced the total number of impure functions (still 3 in each case - readReservations, createReservation and tryAccept[Composition]).
The only difference I see is that one impure function has been refactored into 2 functions - one pure and one impure. Considering that the original tryAccept function was already fully testable from a unit testing point of view and quite readable what is the benefit of this additional step? I would almost argue that the original tryAccept function was even easier to read/understand than the combination of tryAccept and tryAcceptComposition. I understand that impure functions like this are not truly functional, but in a real world application you must have some impure functions and I would like to better understand where trade-off benefit of that additional step is? Am I missing something else?
Dustin, thank you for writing. There are several answers to your question, depending on the perspective one is interested in. I'll see if I can cover the most important ones.
Is it functional? #
On the most fundamental level, I'm interested in learning functional programming. In order to do this, I seek out strictly functional solutions to problems. Haskell is a great help in that endeavour, because it's not a hybrid language. It only allows you to do functional programming.
Does it make sense to back-port Haskell solutions to F#, then? That depends on what one is trying to accomplish, but if the goal is nothing but learning how to do it functionally, then that goal is accomplished.
Toy examples #
On another level, the example I've presented here is obviously nothing but a toy example. It's simplified, because if I presented readers with a more realistic example, the complexity of the real problem could easily drown out the message of the example. Additionally, most readers would probably give up reading.
I'm asking my readers to pretend that the problem is more complex than the one I present here; pretend that this problem is a stand-in for a harder problem.
In this particular context, there could be all sorts of complications:
- Reservations could be for time slots instead of whole dates. In order to keep the example simple, I treat each reservation as simply blocking out an entire date. I once dined at a restaurant where they started serving at 19:00, and if you weren't there on time, you'd miss the first courses. Most restaurants, though, allow you to make reservations for a particular time, and many have more than one serving on a single evening.
- Most restaurants have tables, not seats. Again, the same restaurant I mentioned above seated 12 people at a bar-like arrangement facing the kitchen, but most restaurants have tables of varying sizes. If they get a reservation for three people, they may have to reserve a table for four.
- Perhaps the restaurant would like to implement a feature where, if it receives a reservation that doesn't fill out a table (like a reservation for three people, and only four-people tables are left), it'd defer the decision to see if a 'better' reservation arrives later.
- Some people make reservations, but never show up. For that reason, a restaurant may want to allow a degree of overbooking, just like airlines. How much overbooking to allow is a business decision.
- A further wrinkle on the overbooking business rule is that you may have a different overbooking policy for Fridays than for, say, Wednesdays.
- Perhaps the restaurant would like to implement a waiting-list feature as well.
Separation of concerns #
In my experience, there's an entire category of software defects that occur because of state mutation in business logic. You could have an area of your code that calls other code, which calls other code, and so on, for several levels of nesting. Somewhere, deep in the bowels of such a system, a conditional statement flips a boolean flag that consequently impact how the rest of the program runs. I've seen plenty of examples of such software, and it's inhumane; it doesn't fit within human cognitive limits.
Code that allows arbitrary side-effects is difficult to reason about.
Knowing that an subgraph of your call tree is pure reduces defects like that. This is nothing but another way to restate the command-query separation principle. In F#, we still can't be sure unless we exert some discipline, but in Haskell, all it takes is a look at the type of a function or value. If it doesn't include IO, you know that it's pure.
Separating pure code from impure code is separation of concern. Business logic is one concern, and I/O is another concern, and the better you can separate these, the fewer sources of defects you'll have. True, I haven't reduced the amount of code by much, but I've separated concerns by separating the code that contains (side) effects from the pure code.
Testability #
It's true that the partial application version of tryAccept is testable, because it has isolation, but the tests are more complicated than they have to be:
[<Property(QuietOnSuccess = true)>] let ``tryAccept behaves correctly when it can accept`` (NonNegativeInt excessCapacity) (expected : int) = Tuple2.curry id <!> Gen.reservation <*> Gen.listOf Gen.reservation |> Arb.fromGen |> Prop.forAll <| fun (reservation, reservations) -> let capacity = excessCapacity + (reservations |> List.sumBy (fun x -> x.Quantity)) + reservation.Quantity let readReservations = ((=!) reservation.Date) >>! reservations let createReservation = ((=!) { reservation with IsAccepted = true }) >>! expected let actual = tryAccept capacity readReservations createReservation reservation Some expected =! actual [<Property(QuietOnSuccess = true)>] let ``tryAccept behaves correctly when it can't accept`` (PositiveInt lackingCapacity) = Tuple2.curry id <!> Gen.reservation <*> Gen.listOf Gen.reservation |> Arb.fromGen |> Prop.forAll <| fun (reservation, reservations) -> let capacity = (reservations |> List.sumBy (fun x -> x.Quantity)) - lackingCapacity let readReservations _ = reservations let createReservation _ = failwith "Mock shouldn't be called." let actual = tryAccept capacity readReservations createReservation reservation None =! actual
(You can find these tests in commit d2387cceb81eabc349a63ab7df1249236e9b1d13 in the accompanying sample code repository.) Contrast those dependency-injection style tests to these tests against the pure version of tryAccept:
[<Property(QuietOnSuccess = true)>] let ``tryAccept behaves correctly when it can accept`` (NonNegativeInt excessCapacity) = Tuple2.curry id <!> Gen.reservation <*> Gen.listOf Gen.reservation |> Arb.fromGen |> Prop.forAll <| fun (reservation, reservations) -> let capacity = excessCapacity + (reservations |> List.sumBy (fun x -> x.Quantity)) + reservation.Quantity let actual = tryAccept capacity reservations reservation Some { reservation with IsAccepted = true } =! actual [<Property(QuietOnSuccess = true)>] let ``tryAccept behaves correctly when it can't accept`` (PositiveInt lackingCapacity) = Tuple2.curry id <!> Gen.reservation <*> Gen.listOf Gen.reservation |> Arb.fromGen |> Prop.forAll <| fun (reservation, reservations) -> let capacity = (reservations |> List.sumBy (fun x -> x.Quantity)) - lackingCapacity let actual = tryAccept capacity reservations reservation None =! actual
They're simpler, and since they don't use mocks, they're more robust. They were easier to write, and I subscribe to the spirit of GOOS: if test are difficult to write, the system under test should be simplified.
Hi Mark,
Thanks for your talk at NDC last month, and for writing this series! I feel that the functional community (myself included) has a habit of using examples that aren't obviously relevant to the sort of line-of-business programming most of us do in our day jobs, so articles like this are sorely needed.
We talked a little about this in person after your talk at the conference: I wanted to highlight a potential criticism of this style of programming. Namely, there's still some important business logic being carried out by your tryAcceptComposition function, like checking the capacity on the requested reservation date. How do you unit test that readReservations is called with the correct date? Likewise, how do you unit test that rejected reservations don't get saved? Real world business logic isn't always purely functional in nature. Sometimes the side effects that your code performs are part of the requirements.
The Haskell philosophy isn't about rejecting side effects outright - it's about measuring and controlling them. I wouldn't write tryAcceptComposition using IO. Instead I'd program to the interface, not the implementation, using an mtl-style class to abstract over monads which support saving and loading reservations.
class Monad m => MonadReservation m where
readReservations :: ConnectionString -> Date -> m [Reservation]
createReservation :: ConnectionString -> Reservation -> m ReservationId
tryAcceptComposition :: MonadReservation m => Reservation -> m (Maybe ReservationId)
tryAcceptComposition r = runMaybeT $ do
reservations <- lift $ readReservations connectionString (date r)
accepted <- MaybeT $ return $ tryAccept 10 reservations r
lift $ createReservation connectionString acceptedCode that lives in a MonadReservation context can read and create reservations in the database but nothing else; it doesn't have all the power of IO. During unit testing I can use an instance of MonadReservation that returns canned values, and in production I can use a monad that actually talks to the database.
Since type classes are syntactic sugar for passing an argument, this is really just a nicer way of writing your original DI-style code. I don't advocate the "free monad" style that's presently trendy in Scala-land because I find it unnecessarily complex. 90% of the purported advantages of free monads are already supported by simpler language features.
I suppose the main downside of this design is that you can't express it in F#, at least not cleanly. It relies on type classes and higher-kinded types.
Hope you find this interesting, I'd love to hear what you think!
Benjamin
Benjamin, thank you for writing. The alternative you propose looks useful in Haskell, but, as you've already suggested, it doesn't translate well into F#.
I write F# code professionally, whereas so far, I've only used Haskell to critique my F# code. (If someone who reads this comment would offer to pay me to write some Haskell code, please get in touch.) In other words, I still have much to learn about Haskell. I think I understand as much, however, that I'd be able to use your suggested design to unit test tryAcceptComposition using the Identity monad for Stubs, or perhaps MonadWriter or MonadState for Mocks. I'll have to try that one day...
In F#, I write integration tests. Such tests are important regardless, and often they more closely relate to actual requirements, so I find this a worthwhile effort anyway.
Hi Mark,
thanks for the post series, which I find interesting and needed. There is one part of your post that I find deserves further exploration. You write:
in statement-based languages like C# and Java, this may be problematic, because you may wish to defer a query, or base it on a decision inside the unit. In expression-based languages you can decouple decisions from effects, and deferred execution can always be done by lazy evaluation, if that's required.Firstly, I would say that you can write expression-based programs in any language that has expressions, which naturally includes C# and Java. But that's not particularly relevant to this discussion.
More to the point, you're glossing over this as though it were a minor detail, when in fact I don't think it is. Let's explore the case in which "you may wish to defer a query, or base it on a decision inside the unit". The way you do this "by lazy evaluation" would be - I assume - by passing a function as an argument to your unit. But this is then effectively dependency injection, because you're passing in a function which has side effects, which will be called (or not) from the unit.
So, it seems to me that your technique of extracting side effects out of the unit provides a good general guideline, but not a completely general way to replace dependency injection.
Enrico, thank you for writing. There's a lot to unpack in that quote, which was one of the reasons I didn't expand it. It would have made the article too long, and wandered off compared to its main point. I don't mind going into these details here, though.
Direction of data #
In order to get the obvious out of the way first, the issue you point out is with my refactoring of indirect input to direct input. Refactoring from indirect to output to direct output is, as far as I can tell, not on your agenda. Designing with direct input in mind seems uncontroversial to me, so that makes sense.
No hard rules #
On this blog, I often write articles as I figure out how to deal with problems. Sometimes, I report on my discoveries at a time where I've yet to accumulate years of experience. What I've learned so far is that dependency injection isn't functional. What I'm still exploring is what to do instead.
It's my experience that the type of refactoring I demonstrate here can surprisingly often be performed. I don't want to claim that it's always possible to do it like this. In fact, I'm still looking for good examples where this will not be possible. Whenever I think of a simple enough example that I could share it here, I always realise that if only I simplify the problem, I can put it into the shape seen here.
My thinking is, however, constrained by my professional experience. I've been doing web (service) development for so many years now that it constraints my imagination. When you execution scope is exclusively a single HTTP request at a time, you tend to keep things simple. I'd welcome a simplified, but still concrete example where the impure/pure/impure sandwich described here isn't going to be possible.
This may seem like a digression, but my point is that I don't claim to be the holder of a single, undeniable truth. Still, I find that this article describes a broadly applicable design and implementation technique.
Language specifics #
The next topic we need to consider is our choice of language. When I wrote that deferred execution can always be done by lazy evaluation, that's exactly how Haskell works. Haskell is lazily evaluated, so any value passed as direct input can be unevaluated until required. That goes for IO as well, but then, as we've learned, you can't pass impure data to a pure function.
All execution is, in that sense, deferred, unless explicitly forced. Thus, any potential need for deferred execution has no design implications.
F#, on the other hand, is an eagerly evaluated language, so there, deferred execution may have design implications.
Performance #
Perhaps it's my lack of imagination again, but I can't think of a well-designed system where deferred execution is required for purposes of correctness. As far as I can tell, deferred execution is a performance concern. You wish to defer execution of a query because that operation takes significant time.
That's a real concern, but I often find that people worry too much about performance. Again, this is probably my lack of wider experience, as I realise that performance can be important in smart phone apps, games, and the like. Clearly, performance is also important in the world of REST APIs, but I've met a lot of people who worry about performance without ever measuring it.
When you start measuring performance, you'll often be surprised to discover where your code spends actual time. So my design approach is always to prioritise making the system work first, and then, if there are performance problems, figure out how to tweak it so that it becomes satisfactory. In my experience, such tweaking is only necessary now and then. I'm not claiming that my code is the fastest it could be, but it's often fast enough, and as easy to maintain as I can make it.
The need for data #
Another concern is the need for data. If you consider the above tryAccept function, it always uses reservations. Thus, there's no gain in deferring the database query, because you'll always need the data.
Deferred execution is only required in those cases where you have conditional branching, and only in certain cases do you need to read a particular piece of data.
Even conditional branching isn't enough of a criterion, though, because you could have branching where, in 99.9 % of the cases, you'd be performing the query anyway. Would you, then, need deferred execution for the remaining 0.1 % of the cases?
Lazy sequences #
Still, let's assume that we've implemented a system using pure functions that take pure data, but to our dismay we discover that there's one query that takes time to execute, and that we truly only need it some of the time. In .NET, there are two distinct situations:
- We need a scalar value
- We need a collection of values
IEnumerable<T> in C#) as input. These can be implemented as lazily evaluated sequences, which gives us the deferred execution we need.
Lazy scalar values #
This leaves the corner case where we need a lazily evaluated scalar value. In such cases, I may have to make a concession to performance in my function design, but I wouldn't change the argument to a function, but rather to a lazy value.
Lazy values are deferred, but memoised, which is the reason I'd prefer them over function arguments.
In a previous comment, you said:
I'd welcome a simplified, but still concrete example where the impure/pure/impure sandwich described here isn't going to be possible.
I have on two occasions stumbled into cases where I can't find a good way to pull this off. The reason may be that there's a workflow seemingly consisting of several impure steps interleaved with pure decisions. The cases are similar, so I will share one of them as an example.
We have an API for allowing users to register. We also have a separate API for two-factor authentication (2FA). When users register, they have to complete a "proof" using the 2FA API to verify ownership of their mobile number.
The 2FA API has two relevant endpoints used internally by our other APIs: One is used for creating a proof, and returns a proof ID that can be passed on to the API client. This endpoint is used when a client makes a request without a proof ID, or with an invalid proof ID. The other endpoint is used for verifying that a proof has been completed. This endpoint is used when a client supplies a proof ID in the request.
(The 2FA API also has endpoints the client uses to complete the proof, but that is not relevant here.)
When a user registers, this is the workflow:
Here is a simple implementation of the workflow using "dependency injection" (I will skip the actual composition function, similar to your tryAcceptComposition, which is not interesting here):
let completeRegistrationWorkflow
(createProof: Mobile -> Async<ProofId>)
(verifyProof: Mobile -> ProofId -> Async<bool>)
(completeRegistration: Registration -> Async<unit>)
(proofId: ProofId option)
(registration: Registration)
: Async<CompleteRegistrationResult> =
async {
match proofId with
| None ->
let! proofId = createProof registration.Mobile
return ProofRequired proofId
| Some proofId ->
let! isValid = verifyProof registration.Mobile proofId
if isValid then
do! completeRegistration registration
return RegistrationCompleted
else
let! proofId = createProof registration.Mobile
return ProofRequired proofId
}
There are two decisions that are pure and could conceivably be extracted to a pure (non-DI) function, indicated by blue in the flowchart:
- Initially: Should we create a new proof or verify an existing proof? (based on whether the client supplied a proof ID)
- After verifying a supplied proof: Should we complete the registration or create a new proof? (based on whether the supplied proof ID was valid)
My question then, is this: Is it possible to refactor this to direct input/output, in a way that actually reduces complexity where it matters? (In other words, in a way where the decisions mentioned above are part of a pure, non-DI function?)
Otherwise, I just want to say that this series has helped me become a better F# programmer. Since originally reading it, I have consistently tried to design for direct input/output as opposed to using "dependency injection", and my code has become better for it. Thanks!
Christer, thank you for writing. That was such a fruitful question that I wrote a new article in order to answer it. I hope you find it useful, but if not, let's continue the discussion there or here, dependening on what makes most sense.
Hi Mark, excelent post series, thank you. Right after finishing this post I had the same questions Dustin Moris Gorski had and I think I still have some, even after your answer.
For simplicity's sake, I'll represent TryAccept as 3 operations: read, calculate and maybe create. Both read and create are injected so that I can change their implementations at runtime, if necessary. That is the same exact representation for both the C# and F# codes that use DI, and also the tryAcceptComposition code, with the difference that tryAcceptComposition depends on the actual implementation of DB, so it's relatively more brittle than the DI alternatives.
Although TryAccept and TryAcceptComposition are doing the same thing, I'm still trying to think why the latter looks more functional than the first and whether DI is really not necessary. I got to 2 conclusions and I wanted to know your opinion about them:
1) The difference between the 2 implementations (TryAccept and TryAcceptComposition) is that the first is following an imperative style, while the second is purely declaritive, with one big composition. Both implementations perform the exact same operations, evoking the same dependencies, but with different code styles.
2) If we try and take your style of sandwich to extremes and push dependencies to the very edges of the application, to the point where it's just a simple big composition with dependencies at the beginning and end, we my replace "injection" with import statements, importing our dependencies in the same place the composition is written. I don't think this would work in every scenario as operations in the middle of this composition would need access to dependencies too (which could them be pushed out like TryAccept, but could make the code less readable). Do you think this is doable?
Danilo, thank you for writing. Regarding your first point, I'm not sure I follow. Both functions are written in F#, which is an expression-based language (at least when you ignore the interop parts). Imperative code is usually defined as coding with assignments rather than expressions. There's no assignments here.
Also, tryAccept and tryAcceptComposition aren't equivalent. One is a specialisation of the other, so to speak. You can't change the behaviour of tryAcceptComposition unless you edit the actual code. You can, on the other hand, change the observable behaviour of tryAccept by composing it with different impure actions.
As to your second observation:
"I don't think this would work in every scenario as operations in the middle of this composition would need access to dependencies too"I'm still keen on getting some compelling examples of this. Christer van der Meeren kindly tried to supply such an example, but it turned out as another fine sandwich. This happens conspicuously often.
I've never claimed that the sandwich architecture is always possible, but every time I try to find a compelling counter-example, it usually turns out to be refactorable into a sandwich after all. Do, however, refer to the comments to that later article.
Hi Mark, I found myself thinking about this early this morning and wondering about scenarios where injecting dependencies may still be "functional" (i.e. pure) and would like your input. It also incorporates TDD (or at least testing strategies).
Here's my example: I was recently refactoring some code that was structured like this (C#-ish pseudo-code):
if (shouldNotify(record, supportingRecord, settings))
{
generateEmail(...);
record.status = calculateStatusAfterEmail(record, supportingRecord);
}
else
{
record.status = calculateStatusWithoutEmail(record, supportingRecord);
}
Let's gloss over the side-effects all over the place here and just focus on the flow.
To ease unit testing, I extracted these private methods into a separate interface and am injecting it into this flow. Call me lazy, but I wanted to just mock/stub the results of these pure calls when testing the overall flow and wrote separate tests on the implementation of the new interface that could focus on all the different combinations of values. Is that a strategy you would support/recommend, or would you hesitate to extract pure functions from an implementation just to ease testing? I also convinced myself that I could justify this on the grounds of following the Single Responsibility Principle (i.e. this flow should not need to be modified if the status calculation logic changes).
Your thoughts? By the way, your new dependency injection strategies is on its way to me, perhaps that book will provide me with your views on that, but I couldn't resist posting it here.
Sven, thank you for writing. I think that your question deserves a longer answer than what you'll get here. It's a topic that for some time I've been contemplating giving a more detailed treatment. It's a rich enough subject that a couple of articles would be required. I'm still pondering how to organise such content.
The short answer is that I'm increasingly looking for alternatives to the sort of interaction-based testing you imply. I think that my article series on the benefits of state-based testing outlines most of my current thinking on the topic.
I read over all the comments and I would like clarification on when logic is required for resolving the dependency being provided. Benjamin Hodgson asked this:
Namely, there's still some important business logic being carried out by your tryAcceptComposition function, like checking the capacity on the requested reservation date. How do you unit test that readReservations is called with the correct date?
Suppose the readRervations didn't just get all reservations from the dabatase just to process for one restaurant or on one day. Thus the restaurant ID and date may be needed to fetch the correct reservations, and this logic would have to happen outside of the unit. I think you touched on this complication in a response above, but I'd like to confirm if I am understanding your responses correctly: you simply perform this logic outside of the unit and have an integration test for the entire workflow?
Chris, thank you for writing. There are more nuances to that question than might be immediately apparent. At least, I'll answer the question in several ways.
First, I'd like to challenge the implicit assumption that one must always test everything. What to test and what not to test depend on multiple independent forces, such as how costly an error might be, how likely an error is to occur, and so on.
Take, as an example, the code base that accompanies my book Code That Fits in Your Head. This code base is also a restaurant reservation system, but has a realistic level of complexity, so I think it might better highlight the sort of considerations that might be warranted. The code that is most relevant to the question is this snippet from ReservationsController.TryCreate:
var reservations = await Repository .ReadReservations(restaurant.Id, reservation.At) .ConfigureAwait(false); var now = Clock.GetCurrentDateTime(); if (!restaurant.MaitreD.WillAccept(now, reservations, reservation)) return NoTables500InternalServerError(); await Repository.Create(restaurant.Id, reservation) .ConfigureAwait(false);
How likely is it that the code changes in such a way that it calls ReadReservations with the wrong input? Either because the original programmer who wrote the code made a mistake, or because a later developer introduced a change in which this code calls ReadReservations with incorrect input?
Now, such errors certainly do occur. Programmers are human, and to err is human.
Still, it's important to keep in mind that the risk of introducing an error into a code base is proportional to the amount of code. The more code, the more errors you'll have. This goes for test code as well. You can also, inadvertently, introduce errors into a test.
You can counteract some of that by writing the test first. That's the reasons it's so important to see a test fail. Only by seeing it fail can you feel confident that it verifies something real.
So, depending on circumstances, it may be relevant and important to write a test that verifies that ReadReservations is called with the correct arguments. Still, I think it's important to weigh advantages and disadvantages before blindly insisting that it's necessary to protect against such a contingency.
When I originally wrote the above code, I wrote no unit test that explicitly verify whether ReadReservations is called with the correct arguments. After all, in that context, there's only one DateTime value in scope: reservation.At. (This is not entirely true, because now is also a DateTime value, but as the code is written, it's not available for ReadReservations because it's retrieved after the ReadReservations call. But see below.)
In a context like this, you'd have to go out of your way to call ReadReservations with the wrong date. You could create a value on the spot, like this:
var reservations = await Repository .ReadReservations(restaurant.Id, new DateTime(2021, 12, 19, 18, 30, 0)) .ConfigureAwait(false);
or this:
var reservations = await Repository .ReadReservations(restaurant.Id, reservation.At.AddDays(1)) .ConfigureAwait(false);
None of these are impossible, but I do consider them to be conspicuous. You don't easily make those kinds of mistakes. You'd almost have to go out of your way to make these mistakes, and a good pairing partner or code review ought to catch such a mistake.
Another option is if someone finds a good reason to reorder the code:
var now = Clock.GetCurrentDateTime(); var reservations = await Repository .ReadReservations(restaurant.Id, now) .ConfigureAwait(false);
In this example, now is available to ReadReservations, and perhaps a later edit might introduce the error of calling it with now.
This is perhaps a more realistic, honest mistake.
None of the 171 unit tests in the code base catch any of the above three mistakes.
Is the code base unsafe, then?
No, because as luck would have it, an integration test (NoOverbookingRace) fails on any of these three edits. I admit that this is just a fortunate accident. I added that particular integration test for another reason: to reproduce an unrelated bug that occurred in 'production'.
I usually try to base the amount of testing I ask from a team on the quality of the team. The more I trust that they pair-program or perform regular code reviews, the less I insist on test coverage, and vice versa.
In summary, though, if I find that it's important to verify that ReadReservations was called with the correct arguments, I'd favour a state-based integration test.
Comments
Good introduction to the notion of programs-as-embedded-languages here, thanks for writing it!
In my experience a majority of
Freeinterpreters fit into thefoldFreepattern. Saves you the repetitous bits of yourinterpretfunction:Anyway, I just wanted to give an alternative viewpoint on the topic of
Freewhich will hopefully be some food for thought. I'm generally not an advocate of theFreeapproach to modelling effectful computation. I don't think it has much of an advantage over the old fashionedmtlstyle, especially since you have only one effect and only one interpreter. I'd have written your interface like this:It's a clearer, more direct expression of the monadic interface, in my opinion, and it admits simpler implementations (and it's faster because GHC can specialise and inline everything). Computations with access to only a
MonadPollcontext can only perform polling actions, so it's still pure, and you can swap out different implementations ofMonadPoll(eg, for testing) by writing types with different instances. You can do eg this if you need "decorator"-style interpreters. The main downside of themtlstyle is the "n^2 instances problem" (thoughGeneralizedNewtypeDerivingdoes somewhat ease the pain).Kiselyov has some good lecture notes about using the
mtlstyle to model abstract syntax trees and compositional interpreters. I probably wouldn't go that far if I were building a compiler! Type classes are good at effect systems and algebraic data types are good at syntax trees, and while each job can be done by either it pays to pick your tools carefully.Having said all that, the
Freeapproach is probably more attractive in F#, because it doesn't feature type classes or higher kinds. AndFreehas other uses outside of the world of effect systems.Hope all the above is interesting to you!
Benjamin
Benjamin, thank you for writing. It is, indeed, interesting to me, and I appreciate that you took the time to write such a helpful and concise comment.
I wasn't aware of
foldFree, but I can see that I'll have to look into it.One day (soon), I'll have to try writing a small Haskell program using the
mtlstyle instead. It looks as though the code would be quite similar, although the types are different. Are these approaches isomorphic?In any case, I hope that I'm not coming off as being too authoritative. In some sense, this blog often serves as my own elaborate journal documenting what I've been learning recently. I hope that what I write is mostly correct, but I don't presume that what I write is the one and only truth; it's bound by my knowledge at the time of writing. I still have much to learn, and I'm always happy when people help me expand my horizon.
I think that you hit the nail concerning F#. One of my motivations for exploring this space was to figure out what can be done in F#. As far as I can tell, the
mtlstyle doesn't translate well to F#. You can debate whether or not free monads translate well to F#, but at least the concept does carry over.Yep, they're isomorphic, in that you can round-trip in either direction between the two representations -
to . from = from . to = id:instance MonadPoll msg (Free (PollingInstruction msg)) where currentTime = liftF (CurrentTime id) poll = liftF (Poll id) handle msg = liftF (Handle msg id) idle d = liftF (Idle d id) to :: (forall m. MonadPoll msg m => m a) -> Free (PollingInstruction msg) a to x = x from :: MonadPoll msg m => Free (PollingInstruction msg) a -> m a from x = foldFree eta where eta (CurrentTime k) = k <$> currentTime eta (Poll k) = k <$> poll eta (Handle msg k) = k <$> handle msg eta (Idle d k) = k <$> idle dBut the representations being isomorphic doesn't mean they're equally convenient. (Another example of this would be lenses: van Laarhoven lenses (à la
lens) are isomorphic to "costate comonad coalgebra" (ieget/set) lenses, but they're much more composable.)Benjamin
Benjamin, thank you once again for writing. It's amazing that not only are they isomorphic, but you can actually prove it with code. I have to admit, though, that I haven't tried compiling or running your code yet. First, I need to digest this.
I was never under the impression that I knew most of what there was to know, but by Jove!, poking at Haskell unearths fathomless depths of knowledge of which I still only glance the surface. It's occasionally frustrating, but mostly exhilarating.