Type Driven Development by Mark Seemann
A strong type system can not only prevent errors, but also guide you and provide feedback in your design process.
Have you ever worked in a statically typed language (e.g. C# or Java), only to wish that you'd be allowed to focus on what you're doing, instead of having to declare types of arguments and create new classes all the time?
Have you, on the other hand, ever worked in a dynamic language (e.g. Javascript) and wished you could get static type checking to prevent a myriad of small, but preventable errors?
You can have the best of both worlds, and more! F#'s type system is strong, but non-obtrusive. It enables you to focus on the behaviour of the code you're writing, while still being statically typed.
Not only can it prevent syntax and usage errors, but it can even provide guidance on how to proceed with a given problem.
This is best explained with an example.
Example problem: simulate a continuously running process as a series of discrete processes #
A couple of years ago I had a very particular problem: I needed to simulate a continuously running task using a sequence of discrete processes.
In short, I needed to start a process (in reality a simple .exe file) that would act as a Polling Consumer, but with the twist that it would keep track of time. It would need to run for one minute, and then shut down so that an overall scheduler could start the process again. This was to guarantee that the process would be running on at most one server in a farm.
The Polling Consumer should pull a message off a queue and hand it to some dispatcher, which would then make sure that the message was handled by an appropriate handler. This takes time, so makes the whole process more complex.
If the Polling Consumer estimates that receiving and handling a message takes 200 milliseconds, and it's 100 milliseconds from shutting down, it shouldn't poll for a message. It would take too long, and it wouldn't be able to shut down in time.
My problem was that I didn't know how long it took to handle a message, so the Polling Consumer would have to measure that as well, constantly updating its estimates of how long it takes to handle a message.
This wasn't a harder problem that I could originally solve it in a highly coupled imperative fashion. I wasn't happy with that implementation, though, so I'm happy that there's a much more incremental approach to the problem.
A Finite State Machine #
The first breakthrough came when I realised that I could model the problem as a finite state machine:
The implicit start state is always the Ready state, because when the Polling Consumer starts, it has no message, but plenty of time, so therefore ready for a new message.
From the Ready state, the Polling Consumer may decide to poll for a message; if one is received, the new state is the Received state.
From the Received state, the only legal transition is back into the Ready state by handling the message.
From the Ready state, it may also turn out that there's currently no message in the queue, in which case the new state is the No message state.
In the No message state, the Polling Consumer may decide to idle for perhaps five seconds before transitioning back into the Ready state.
When in the Ready or No message states, the Polling Consumer may also realise that time is running out, and so decide to quit, in which case the (final) state is the End state.
This means that the Polling Consumer needs to measure what it does, and those measurements influence what it decides to do.
Separation of concerns #
It sounds like we have a time concern (do I dare say dimension?), and a concern related to doing something. Given multiple concerns, we should separate them
The first thing I did was to introduce a Timed<'a> generic record type. This represents the result of performing a computation, as well as the times the computation started and stopped. I changed it slightly from the linked article, so here's the updated code for that:
type Timed<'a> = { Started : DateTimeOffset Stopped : DateTimeOffset Result : 'a } member this.Duration = this.Stopped - this.Started module Untimed = let map f x = { Started = x.Started; Stopped = x.Stopped; Result = f x.Result } let withResult newResult x = map (fun _ -> newResult) x module Timed = let capture clock x = let now = clock() { Started = now; Stopped = now; Result = x } let map clock f x = let result = f x.Result let stopped = clock () { Started = x.Started; Stopped = stopped; Result = result } let timeOn clock f x = x |> capture clock |> map clock f
This enables me to capture timing information about any operation, including the transitions between various states in a finite state machine.
The way I modelled the finite state machine for the Polling Consumer explicitly models all states as being instantaneous, while transitioning between states takes time. This means that we can model all transitions as functions that return Timed<'something>.
State data types #
The first step is to model the data associated with each state in the finite state machine. This is an iterative process, but here I'll just show you the final result. If you're interested in seeing this design process in more details, you can watch my Pluralsight course Type-Driven Development with F#.
// Auxiliary types type MessageHandler = unit -> Timed<unit> // State data type ReadyData = Timed<TimeSpan list> type ReceivedMessageData = Timed<TimeSpan list * MessageHandler> type NoMessageData = Timed<TimeSpan list>
All of these types are simply type aliases, so in fact they aren't strictly necessary. It's just helpful to give things a name from time to time.
The auxiliary MessageHandler type is a function that takes nothing (unit) as input, and returns 'timed nothing' as output. You may wonder how that handles a message. The intent is that any MessageHandler function is going to close over a real message: when a client calls it, it handles the message it closes over, and returns the time it took. The reason for this design is that the Polling Consumer doesn't need to 'see' the message; it only needs to know that it was handled, and how long it took. This design keeps the Polling Consumer decoupled from any particular message types.
There are three state data types: one for each state.
Hey! What about the End state?
It turns out that the End state doesn't need any associated data, because once the End state is reached, no more decisions should be made.
As promised, the three other states all contain a Timed<'something>. The timing information tells us when the transition into the given state started and stopped.
The data for the Ready and No message states are the same: Timed<TimeSpan list>, but notice that the TimeSpan list also appears in the Received state. This list of durations contains the statistics that the Polling Consumer measures. Every time it handles a message, it needs to measure how long it took. All such measurements are collected in this TimeSpan list, which must be passed around in all states so that the data isn't lost.
The data for the Received message state is different, because it also contains a MessageHandler. Every time the Polling Consumer receives a message, this message must be composed into a MessageHandler, and the MessageHandler passed as the second element of the state's tuple of data.
With all four states defined, we can now define a discriminated union that models a snapshot of the state machine:
type PollingConsumer = | ReadyState of ReadyData | ReceivedMessageState of ReceivedMessageData | NoMessageState of NoMessageData | StoppedState
That is, a PollingConsumer value represents a state of the Polling Consumer state machine.
Already at this stage, it should be apparent that F#'s type system is a great thinking tool, because it enables you to define type aliases declaratively, with only a single line of code here and there. Still, the advantage of the type system becomes much more apparent once you start to use these types.
Transitions #
With data types defined for each state, the next step of implementing a finite state machine is to define a function for each state. These functions are called transitions, and they should take a concrete state as input, and return a new PollingConsumer value as output. Since there are four concrete states in this example, there must be four transitions. Each should have the type 'concreteData -> PollingConsumer, e.g. ReadyData -> PollingConsumer, ReceivedMessageData -> PollingConsumer, etc.
As you can see, we're already getting guidance from the type system, because we now know the types of the four transitions we must implement.
Let's begin with the simplest one. When the Polling Consumer is Stopped, it should stay Stopped. That's easy. The transition should have the type unit -> PollingConsumer, because there's no data associated with the StoppedState.
Your first attempt might look like this:
let transitionFromStopped () : PollingConsumer = ??
This obviously doesn't compile because of the question marks (which aren't proper F# syntax). Knowing that you must return a PollingConsumer value, which one (of ReadyState, ReceivedMessageState, NoMessageState, or StoppedState) should you return?
Once the Polling Consumer is in the Stopped state, it should stay in the Stopped state, so the answer is easy: this transition should always return the Stopped state:
let transitionFromStopped () : PollingConsumer = StoppedState
It's as easy as that.
Since the (unit) input into the function doesn't do anything, we can remove it, effectively turning this particular function into a value:
let transitionFromStopped : PollingConsumer = StoppedState
This is a degenerate case, and not something that always happens.
Another transition #
Let's do another transition!
Another good example is the transition out of the No message state. This transition must have the type NoMessageData -> PollingConsumer, so you can start typing:
let transitionFromNoMessage (nm : NoMessageData) : PollingConsumer =
This function takes NoMessageData as input, and returns a PollingConsumer value as output. Now you only need to figure out how to implement it. What should it do?
If you look at the state transition diagram, you can see that from the No message state, the Polling Consumer should either decide to quit, or transition back to the Ready state after idling. That's the high-level behaviour we're aiming for, so let's try to put it into code:
let transitionFromNoMessage (nm : NoMessageData) : PollingConsumer = if shouldIdle nm then idle () |> ReadyState else StoppedState
This doesn't compile, because neither shouldIdle nor idle are defined, but this is the overall behaviour we're aiming for.
Let's keep it high-level, so we'll simply promote the undefined values to arguments:
let transitionFromNoMessage shouldIdle idle (nm : NoMessageData) : PollingConsumer = if shouldIdle nm then idle () |> ReadyState else StoppedState
This compiles! Notice how type inference enables you to easily introduce new arguments without breaking your flow. In statically typed languages like C# or Java, you'd have to stop and declare the type of the arguments. If the types you need for those arguments doesn't exist, you'd have to go and create them first. That'd often mean creating new interfaces or classes in new files. That breaks your flow when you're actually trying to figure out how to model the high-level behaviour of a system.
Often, figuring out how to model the behaviour of a system is an exploratory process, so perhaps you don't get it right in the first attempt. Again, with languages like C# or Java, you'd have to waste a lot of time fiddling with the argument declarations, and perhaps the types you'd have to define in order to declare those arguments.
In F#, you can stay focused on the high-level behaviour, and take advantage of type inference to subsequently contemplate if all looks good.
In the transitionFromNoMessage function, the shouldIdle argument is inferred to be of the type NoMessageData -> bool. That seems reasonable. It's a function that determines whether or not to idle, based on a NoMessageData value. Recall that NoMessageData is an alias for Timed<TimeSpan list>, and that all transition functions take time and return Timed<'something> in order to capture the time spent in transition. This means that the time data in NoMessageData contains information about when the transition into the No message state started and stopped. That should be plenty of information necessary to make the decision on whether there's time to idle or not. In a future article, you'll see how to implement a shouldIdle function.
What about the idle argument, then? As the transitionFromNoMessage function is currently written, this argument is inferred to be of the type unit -> ReadyData. Recall that ReadyData is an alias for Timed<TimeSpan list>; what we're really looking at here, is a function of the type unit -> Timed<TimeSpan list>. In other words, a function that produces a Timed<TimeSpan list> out of thin air! That doesn't sound right. Which TimeSpan list should such a function return? Recall that this list contains the statistics for all the previously handled messages. How can a function produce these statistics given nothing (unit) as input?
This seems extra strange, because the statistics are already there, contained in the nm argument, which is a NoMessageData (that is: a Timed<TimeSpan list>) value. The inferred signature of idle suggests that the statistics contained in nm are being ignored.
Notice how the type inference gives us an opportunity to contemplate the current implementation. In this case, just by looking at inferred types, we realise that something is wrong.
Instead, let's change the transitionFromNoMessage function:
let transitionFromNoMessage shouldIdle idle (nm : NoMessageData) = if shouldIdle nm then idle () |> Untimed.withResult nm.Result |> ReadyState else StoppedState
This seems more reasonable: the function idles, but then takes the timing information from idling, but replaces it with the statistics from nm. The inferred type of idle is now unit -> Timed<'a>. That seems more reasonable. It's any function that returns Timed<'a>, where the timing information indicates when idling started and stopped.
This still doesn't look like a pure function, because it relies on the side effect that time passes, but it turns out to be good enough for this purpose.
Higher-order functions #
Perhaps one thing is bothering you: I said that the transition out of the No message state should have the type NoMessageData -> PollingConsumer, but the final version of transitionFromNoMessage has the type (NoMessageData -> bool) -> (unit -> Timed<'a>) -> NoMessageData -> PollingConsumer!
The transitionFromNoMessage function has turned out to be a higher-order function, because it takes other functions as arguments.
Even though it doesn't exactly have the desired type, it can be partially applied. Imagine that you have two functions named shouldIdle' and idle', with the appropriate types, you can use them to partially apply the transitionFromNoMessage function:
let transitionFromNoMessage' = transitionFromNoMessage shouldIdle' idle'
The transitionFromNoMessage' function has the type NoMessageData -> PollingConsumer - exactly what we need!
All transitions #
In this article, you've seen two of the four transitions necessary for defining the behaviour of the Polling Consumer. In total, all four are required:
- ReadyData -> PollingConsumer
- ReceivedMessageData -> PollingConsumer
- NoMessageData -> PollingConsumer
- (StoppedData) -> PollingConsumer
In this article, I will leave it as an exercise to you to implement ReadyData -> PollingConsumer and ReceivedMessageData -> PollingConsumer. If you want to see full implementations of these, as well as a more detailed discussion of this general topic, please watch my Type-Driven Development with F# Pluralsight course.
Imagine that we now have all four transitions. This makes it easy to implement the overall state machine.
State machine #
Here's one way to execute the state machine:
let rec run trans state = let nextState = trans state match nextState with | StoppedState -> StoppedState | _ -> run trans nextState
This run function has the inferred type (PollingConsumer -> PollingConsumer) -> PollingConsumer -> PollingConsumer. It takes a trans function that turns one PollingConsumer into another, as well as an initial PollingConsumer value. It then proceeds to recursively call the trans function and itself, until it reaches a StoppedState value.
How can we implement a PollingConsumer -> PollingConsumer function?
That's easy, because we have all four transition functions, so we can use them:
let transition shouldPoll poll shouldIdle idle state = match state with | ReadyState r -> transitionFromReady shouldPoll poll r | ReceivedMessageState rm -> transitionFromReceived rm | NoMessageState nm -> transitionFromNoMessage shouldIdle idle nm | StoppedState -> transitionFromStopped
The transition function has the type (ReadyData -> bool) -> (unit -> Timed<messagehandler option>) -> (NoMessageData -> bool) -> (unit -> Timed<'a>) -> PollingConsumer -> PollingConsumer. That looks positively horrendous, but it's not so bad; you can partially apply it in order to get a function with the desired type PollingConsumer -> PollingConsumer.
Implicit to-do list #
Even though we now have the run and transition functions, we only have the high-level behaviour in place. We still have a lot of implementation details left.
This is, in my opinion, one of the benefits of this approach to using the low-friction type system: First, you can focus on the desired behaviour of the system. Then, you address various implementation concerns. It's outside-in development.
Another advantage is that at this point, it's quite clear what to do next.
The transitionFromNoMessage function clearly states that it needs the functions shouldIdle and idle as arguments. You can't call the function without these arguments, so it's clear that you must supply them.
Not only did the type system allow us to introduce these function arguments with low friction, but it also tells us the types they should have.
In my Pluralsight course you can see how the transition out of the Ready state also turns out to be a higher-order function that takes two other functions as arguments.
In all, that's four functions we still need to implement before we can use the state machine. It's not going to be possible to partially apply the transition function before these four functions are available.
The type system thereby tells us that we still need to implement these four functions:
- ReadyData -> bool
- unit -> Timed<MessageHandler option>
- NoMessageData -> bool
- unit -> Timed<'a>
run function. Once we can compile a composition of the run function, there are no implementation details left.
Summary #
Although this turned out to be quite a lengthy article, it only provides a sketch of the technique. You can see more code details, and a more in-depth discussion of the approach, in my Type-Driven Development with F# Pluralsight course.
The F# type system can be used in ways that C# and Java's type systems cant:
- Dependencies can be introduced just-in-time as function arguments.
- You can contemplate the inferred types to evaluate the soundness of the design.
- The type system implicitly keeps a to-do list for you.
Update 2017-07-10: See Pure times for a more functional design.
