layout: post
title: “Thirteen ways of looking at a turtle (part 2)”
description: “Continuing with examples of event sourcing, FRP, monadic control flow, and an interpreter.”

categories: [Patterns]

This post is part of the F# Advent Calendar in English 2015 project.
Check out all the other great posts there! And special thanks to Sergey Tihon for organizing this.

In this two-part mega-post, I’m stretching the simple turtle graphics model to the limit while demonstrating partial application, validation, the concept of “lifting”,
agents with message queues, dependency injection, the State monad, event sourcing, stream processing, and an interpreter!

In the previous post, we covered the first nine ways of looking at a turtle. In this post, we’ll look at the remaining four.

As a reminder, here are the thirteen ways:

and 2 bonus ways for the extended edition:

It’s turtles all the way down!

All source code for this post is available on github.


10: Event sourcing — Building state from a list of past events

In this design, we build on the “command” concept used in the Agent (way 5)
and Batch (way 9) approaches, but replacing “commands” with “events” as the method of updating state.

The way that it works is:

  • The client sends a Command to a CommandHandler.
  • Before processing a Command, the CommandHandler first rebuilds the current state
    from scratch using the past events associated with that particular turtle.
  • The CommandHandler then validates the command and decides what to do based on the current (rebuilt) state.
    It generates a (possibly empty) list of events.
  • The generated events are stored in an EventStore for the next command to use.

Thirteen ways of looking at a turtle (part 2) - 图1

In this way, neither the client nor the command handler needs to track state. Only the EventStore is mutable.

The Command and Event types

We will start by defining the types relating to our event sourcing system. First, the types related to commands:

  1. type TurtleId = System.Guid
  2. /// A desired action on a turtle
  3. type TurtleCommandAction =
  4. | Move of Distance
  5. | Turn of Angle
  6. | PenUp
  7. | PenDown
  8. | SetColor of PenColor
  9. /// A command representing a desired action addressed to a specific turtle
  10. type TurtleCommand = {
  11. turtleId : TurtleId
  12. action : TurtleCommandAction
  13. }

Note that the command is addressed to a particular turtle using a TurtleId.

Next, we will define two kinds of events that can be generated from a command:

  • A StateChangedEvent which represents what changed in the state
  • A MovedEvent which represents the start and end positions of a turtle movement.
  1. /// An event representing a state change that happened
  2. type StateChangedEvent =
  3. | Moved of Distance
  4. | Turned of Angle
  5. | PenWentUp
  6. | PenWentDown
  7. | ColorChanged of PenColor
  8. /// An event representing a move that happened
  9. /// This can be easily translated into a line-drawing activity on a canvas
  10. type MovedEvent = {
  11. startPos : Position
  12. endPos : Position
  13. penColor : PenColor option
  14. }
  15. /// A union of all possible events
  16. type TurtleEvent =
  17. | StateChangedEvent of StateChangedEvent
  18. | MovedEvent of MovedEvent

It is an important part of event sourcing that all events are labeled in the past tense: Moved and Turned rather than Move and Turn. The event are facts — they have happened in the past.

The Command handler

The next step is to define the functions that convert a command into events.

We will need:

  • A (private) applyEvent function that updates the state from a previous event.
  • A (private) eventsFromCommand function that determines what events to generate, based on the command and the state.
  • A public commandHandler function that handles the command, reads the events from the event store and calls the other two functions.

Here’s applyEvent. You can see that it is very similar to the applyCommand function that we saw in the previous batch-processing example.

  1. /// Apply an event to the current state and return the new state of the turtle
  2. let applyEvent log oldState event =
  3. match event with
  4. | Moved distance ->
  5. Turtle.move log distance oldState
  6. | Turned angle ->
  7. Turtle.turn log angle oldState
  8. | PenWentUp ->
  9. Turtle.penUp log oldState
  10. | PenWentDown ->
  11. Turtle.penDown log oldState
  12. | ColorChanged color ->
  13. Turtle.setColor log color oldState

The eventsFromCommand function contains the key logic for validating the command and creating events.

  • In this particular design, the command is always valid, so at least one event is returned.
  • The StateChangedEvent is created from the TurtleCommand in a direct one-to-one map of the cases.
  • The MovedEvent is only created from the TurtleCommand if the turtle has changed position.
  1. // Determine what events to generate, based on the command and the state.
  2. let eventsFromCommand log command stateBeforeCommand =
  3. // --------------------------
  4. // create the StateChangedEvent from the TurtleCommand
  5. let stateChangedEvent =
  6. match command.action with
  7. | Move dist -> Moved dist
  8. | Turn angle -> Turned angle
  9. | PenUp -> PenWentUp
  10. | PenDown -> PenWentDown
  11. | SetColor color -> ColorChanged color
  12. // --------------------------
  13. // calculate the current state from the new event
  14. let stateAfterCommand =
  15. applyEvent log stateBeforeCommand stateChangedEvent
  16. // --------------------------
  17. // create the MovedEvent
  18. let startPos = stateBeforeCommand.position
  19. let endPos = stateAfterCommand.position
  20. let penColor =
  21. if stateBeforeCommand.penState=Down then
  22. Some stateBeforeCommand.color
  23. else
  24. None
  25. let movedEvent = {
  26. startPos = startPos
  27. endPos = endPos
  28. penColor = penColor
  29. }
  30. // --------------------------
  31. // return the list of events
  32. if startPos <> endPos then
  33. // if the turtle has moved, return both the stateChangedEvent and the movedEvent
  34. // lifted into the common TurtleEvent type
  35. [ StateChangedEvent stateChangedEvent; MovedEvent movedEvent]
  36. else
  37. // if the turtle has not moved, return just the stateChangedEvent
  38. [ StateChangedEvent stateChangedEvent]

Finally, the commandHandler is the public interface. It is passed in some dependencies as parameters: a logging function, a function to retrieve the historical events
from the event store, and a function to save the newly generated events into the event store.

  1. /// The type representing a function that gets the StateChangedEvents for a turtle id
  2. /// The oldest events are first
  3. type GetStateChangedEventsForId =
  4. TurtleId -> StateChangedEvent list
  5. /// The type representing a function that saves a TurtleEvent
  6. type SaveTurtleEvent =
  7. TurtleId -> TurtleEvent -> unit
  8. /// main function : process a command
  9. let commandHandler
  10. (log:string -> unit)
  11. (getEvents:GetStateChangedEventsForId)
  12. (saveEvent:SaveTurtleEvent)
  13. (command:TurtleCommand) =
  14. /// First load all the events from the event store
  15. let eventHistory =
  16. getEvents command.turtleId
  17. /// Then, recreate the state before the command
  18. let stateBeforeCommand =
  19. let nolog = ignore // no logging when recreating state
  20. eventHistory
  21. |> List.fold (applyEvent nolog) Turtle.initialTurtleState
  22. /// Construct the events from the command and the stateBeforeCommand
  23. /// Do use the supplied logger for this bit
  24. let events = eventsFromCommand log command stateBeforeCommand
  25. // store the events in the event store
  26. events |> List.iter (saveEvent command.turtleId)

Calling the command handler

Now we are ready to send events to the command handler.

First we need some helper functions that create commands:

  1. // Command versions of standard actions
  2. let turtleId = System.Guid.NewGuid()
  3. let move dist = {turtleId=turtleId; action=Move dist}
  4. let turn angle = {turtleId=turtleId; action=Turn angle}
  5. let penDown = {turtleId=turtleId; action=PenDown}
  6. let penUp = {turtleId=turtleId; action=PenUp}
  7. let setColor color = {turtleId=turtleId; action=SetColor color}

And then we can draw a figure by sending the various commands to the command handler:

  1. let drawTriangle() =
  2. let handler = makeCommandHandler()
  3. handler (move 100.0)
  4. handler (turn 120.0<Degrees>)
  5. handler (move 100.0)
  6. handler (turn 120.0<Degrees>)
  7. handler (move 100.0)
  8. handler (turn 120.0<Degrees>)

NOTE: I have not shown how to create the command handler or event store, see the code for full details.

Advantages and disadvantages of event sourcing

Advantages

  • All code is stateless, hence easy to test.
  • Supports replay of events.

Disadvantages

  • Can be more complex to implement than a CRUD approach (or at least, less support from tools and libraries).
  • If care is not taken, the command handler can get overly complex and evolve into implementing too much business logic.

The source code for this version is available here.


11: Functional Retroactive Programming (stream processing)

In the event sourcing example above, all the domain logic (in our case, just tracing the state) is embedded in the command handler. One drawback of this is that,
as the application evolves, the logic in the command handler can become very complex.

A way to avoid this is to combine “functional reactive programming” with event sourcing
to create a design where the domain logic is performed on the “read-side”, by listening to events (“signals”) emitted from the event store.

In this approach, the “write-side” follows the same pattern as the event-sourcing example.
A client sends a Command to a commandHandler, which converts that to a list of events and stores them in an EventStore.

However the commandHandler only does the minimal amount of work, such as updating state, and does NOT do any complex domain logic.
The complex logic is performed by one or more downstream “processors” (also sometimes called “aggregators”) that subscribe to the event stream.

Thirteen ways of looking at a turtle (part 2) - 图2

You can even think of these events as “commands” to the processors, and of course, the processors can generate new events for another processor to consume,
so this approach can be extended into an architectural style where an application consists of a set of command handlers linked by an event store.

This techique is often called “stream processing”.
However, Jessica Kerr once called this approach “Functional Retroactive Programming” — I like that, so I’m going to steal that name!

Thirteen ways of looking at a turtle (part 2) - 图3

Implementing the design

For this implementation, the commandHandler function is the same as in the event sourcing example, except that no work (just logging!) is done at all. The command handler only rebuilds state
and generates events. How the events are used for business logic is no longer in its scope.

The new stuff comes in creating the processors.

However, before we can create a processor, we need some helper functions that can filter the event store feed to only include turtle specific events,
and of those only StateChangedEvents or MovedEvents.

  1. // filter to choose only TurtleEvents
  2. let turtleFilter ev =
  3. match box ev with
  4. | :? TurtleEvent as tev -> Some tev
  5. | _ -> None
  6. // filter to choose only MovedEvents from TurtleEvents
  7. let moveFilter = function
  8. | MovedEvent ev -> Some ev
  9. | _ -> None
  10. // filter to choose only StateChangedEvent from TurtleEvents
  11. let stateChangedEventFilter = function
  12. | StateChangedEvent ev -> Some ev
  13. | _ -> None

Now let’s create a processor that listens for movement events and moves a physical turtle when the virtual turtle is moved.

We will make the input to the processor be an IObservable — an event stream — so that it is not coupled to any specific source such as the EventStore.
We will connect the EventStore “save” event to this processor when the application is configured.

  1. /// Physically move the turtle
  2. let physicalTurtleProcessor (eventStream:IObservable<Guid*obj>) =
  3. // the function that handles the input from the observable
  4. let subscriberFn (ev:MovedEvent) =
  5. let colorText =
  6. match ev.penColor with
  7. | Some color -> sprintf "line of color %A" color
  8. | None -> "no line"
  9. printfn "[turtle ]: Moved from (%0.2f,%0.2f) to (%0.2f,%0.2f) with %s"
  10. ev.startPos.x ev.startPos.y ev.endPos.x ev.endPos.y colorText
  11. // start with all events
  12. eventStream
  13. // filter the stream on just TurtleEvents
  14. |> Observable.choose (function (id,ev) -> turtleFilter ev)
  15. // filter on just MovedEvents
  16. |> Observable.choose moveFilter
  17. // handle these
  18. |> Observable.subscribe subscriberFn

In this case we are just printing the movement — I’ll leave the building of an actual Lego Mindstorms turtle as an exercise for the reader!

Let’s also create a processor that draws lines on a graphics display:

  1. /// Draw lines on a graphics device
  2. let graphicsProcessor (eventStream:IObservable<Guid*obj>) =
  3. // the function that handles the input from the observable
  4. let subscriberFn (ev:MovedEvent) =
  5. match ev.penColor with
  6. | Some color ->
  7. printfn "[graphics]: Draw line from (%0.2f,%0.2f) to (%0.2f,%0.2f) with color %A"
  8. ev.startPos.x ev.startPos.y ev.endPos.x ev.endPos.y color
  9. | None ->
  10. () // do nothing
  11. // start with all events
  12. eventStream
  13. // filter the stream on just TurtleEvents
  14. |> Observable.choose (function (id,ev) -> turtleFilter ev)
  15. // filter on just MovedEvents
  16. |> Observable.choose moveFilter
  17. // handle these
  18. |> Observable.subscribe subscriberFn

And finally, let’s create a processor that accumulates the total distance moved so that we can keep track of how much ink has been used, say.

  1. /// Listen for "moved" events and aggregate them to keep
  2. /// track of the total ink used
  3. let inkUsedProcessor (eventStream:IObservable<Guid*obj>) =
  4. // Accumulate the total distance moved so far when a new event happens
  5. let accumulate distanceSoFar (ev:StateChangedEvent) =
  6. match ev with
  7. | Moved dist ->
  8. distanceSoFar + dist
  9. | _ ->
  10. distanceSoFar
  11. // the function that handles the input from the observable
  12. let subscriberFn distanceSoFar =
  13. printfn "[ink used]: %0.2f" distanceSoFar
  14. // start with all events
  15. eventStream
  16. // filter the stream on just TurtleEvents
  17. |> Observable.choose (function (id,ev) -> turtleFilter ev)
  18. // filter on just StateChangedEvent
  19. |> Observable.choose stateChangedEventFilter
  20. // accumulate total distance
  21. |> Observable.scan accumulate 0.0
  22. // handle these
  23. |> Observable.subscribe subscriberFn

This processor uses Observable.scan to accumulate the events into a single value — the total distance travelled.

Processors in practice

Let’s try these out!

For example, here is drawTriangle:

  1. let drawTriangle() =
  2. // clear older events
  3. eventStore.Clear turtleId
  4. // create an event stream from an IEvent
  5. let eventStream = eventStore.SaveEvent :> IObservable<Guid*obj>
  6. // register the processors
  7. use physicalTurtleProcessor = EventProcessors.physicalTurtleProcessor eventStream
  8. use graphicsProcessor = EventProcessors.graphicsProcessor eventStream
  9. use inkUsedProcessor = EventProcessors.inkUsedProcessor eventStream
  10. let handler = makeCommandHandler
  11. handler (move 100.0)
  12. handler (turn 120.0<Degrees>)
  13. handler (move 100.0)
  14. handler (turn 120.0<Degrees>)
  15. handler (move 100.0)
  16. handler (turn 120.0<Degrees>)

Note that eventStore.SaveEvent is cast into an IObservable<Guid*obj> (that is, an event stream) before being passed to the processors as a parameter.

drawTriangle generates this output:

  1. [ink used]: 100.00
  2. [turtle ]: Moved from (0.00,0.00) to (100.00,0.00) with line of color Black
  3. [graphics]: Draw line from (0.00,0.00) to (100.00,0.00) with color Black
  4. [ink used]: 100.00
  5. [ink used]: 200.00
  6. [turtle ]: Moved from (100.00,0.00) to (50.00,86.60) with line of color Black
  7. [graphics]: Draw line from (100.00,0.00) to (50.00,86.60) with color Black
  8. [ink used]: 200.00
  9. [ink used]: 300.00
  10. [turtle ]: Moved from (50.00,86.60) to (0.00,0.00) with line of color Black
  11. [graphics]: Draw line from (50.00,86.60) to (0.00,0.00) with color Black
  12. [ink used]: 300.00

You can see that all the processors are handling events successfully.

The turtle is moving, the graphics processor is drawing lines, and the ink used processor has correctly calculated the total distance moved as 300 units.

Note, though, that the ink used processor is emitting output on every state change (such as turning), rather than only when actual movement happens.

We can fix this by putting a pair (previousDistance, currentDistance) in the stream, and then filtering out those events where the values are the same.

Here’s the new inkUsedProcessor code, with the following changes:

  • The accumulate function now emits a pair.
  • There is a new filter changedDistanceOnly.
  1. /// Listen for "moved" events and aggregate them to keep
  2. /// track of the total distance moved
  3. /// NEW! No duplicate events!
  4. let inkUsedProcessor (eventStream:IObservable<Guid*obj>) =
  5. // Accumulate the total distance moved so far when a new event happens
  6. let accumulate (prevDist,currDist) (ev:StateChangedEvent) =
  7. let newDist =
  8. match ev with
  9. | Moved dist ->
  10. currDist + dist
  11. | _ ->
  12. currDist
  13. (currDist, newDist)
  14. // convert unchanged events to None so they can be filtered out with "choose"
  15. let changedDistanceOnly (currDist, newDist) =
  16. if currDist <> newDist then
  17. Some newDist
  18. else
  19. None
  20. // the function that handles the input from the observable
  21. let subscriberFn distanceSoFar =
  22. printfn "[ink used]: %0.2f" distanceSoFar
  23. // start with all events
  24. eventStream
  25. // filter the stream on just TurtleEvents
  26. |> Observable.choose (function (id,ev) -> turtleFilter ev)
  27. // filter on just StateChangedEvent
  28. |> Observable.choose stateChangedEventFilter
  29. // NEW! accumulate total distance as pairs
  30. |> Observable.scan accumulate (0.0,0.0)
  31. // NEW! filter out when distance has not changed
  32. |> Observable.choose changedDistanceOnly
  33. // handle these
  34. |> Observable.subscribe subscriberFn

With these changes, the output of drawTriangle looks like this:

  1. [ink used]: 100.00
  2. [turtle ]: Moved from (0.00,0.00) to (100.00,0.00) with line of color Black
  3. [graphics]: Draw line from (0.00,0.00) to (100.00,0.00) with color Black
  4. [ink used]: 200.00
  5. [turtle ]: Moved from (100.00,0.00) to (50.00,86.60) with line of color Black
  6. [graphics]: Draw line from (100.00,0.00) to (50.00,86.60) with color Black
  7. [ink used]: 300.00
  8. [turtle ]: Moved from (50.00,86.60) to (0.00,0.00) with line of color Black
  9. [graphics]: Draw line from (50.00,86.60) to (0.00,0.00) with color Black

and there are no longer any duplicate messages from the inkUsedProcessor.

Advantages and disadvantages of stream processing

Advantages

  • Same advantages as event-sourcing.
  • Decouples stateful logic from other non-intrinsic logic.
  • Easy to add and remove domain logic without affecting the core command handler.

Disadvantages

  • More complex to implement.

The source code for this version is available here.


Episode V: The Turtle Strikes Back

So far, we have not had to make decisions based on the turtle’s state. So, for the two final approaches, we will change the
turtle API so that some commands may fail.

For example, we might say that the turtle must move within a limited arena, and a move instruction may cause the turtle to hit the barrier.
In this case, the move instruction can return a choice of MovedOk or HitBarrier.

Or let’s say that there is only a limited amount of colored ink. In this case, trying to set the color may return an “out of ink” response.

So let’s update the turtle functions with these cases. First the new response types for move and setColor:

  1. type MoveResponse =
  2. | MoveOk
  3. | HitABarrier
  4. type SetColorResponse =
  5. | ColorOk
  6. | OutOfInk

We will need a bounds checker to see if the turtle is in the arena.
Say that if the position tries to go outside the square (0,0,100,100), the response is HitABarrier:

  1. // if the position is outside the square (0,0,100,100)
  2. // then constrain the position and return HitABarrier
  3. let checkPosition position =
  4. let isOutOfBounds p =
  5. p > 100.0 || p < 0.0
  6. let bringInsideBounds p =
  7. max (min p 100.0) 0.0
  8. if isOutOfBounds position.x || isOutOfBounds position.y then
  9. let newPos = {
  10. x = bringInsideBounds position.x
  11. y = bringInsideBounds position.y }
  12. HitABarrier,newPos
  13. else
  14. MoveOk,position

And finally, the move function needs an extra line to check the new position:

  1. let move log distance state =
  2. let newPosition = ...
  3. // adjust the new position if out of bounds
  4. let moveResult, newPosition = checkPosition newPosition
  5. ...

Here’s the complete move function:

  1. let move log distance state =
  2. log (sprintf "Move %0.1f" distance)
  3. // calculate new position
  4. let newPosition = calcNewPosition distance state.angle state.position
  5. // adjust the new position if out of bounds
  6. let moveResult, newPosition = checkPosition newPosition
  7. // draw line if needed
  8. if state.penState = Down then
  9. dummyDrawLine log state.position newPosition state.color
  10. // return the new state and the Move result
  11. let newState = {state with position = newPosition}
  12. (moveResult,newState)

We will make similar changes for the setColor function too, returning OutOfInk if we attempt to set the color to Red.

  1. let setColor log color state =
  2. let colorResult =
  3. if color = Red then OutOfInk else ColorOk
  4. log (sprintf "SetColor %A" color)
  5. // return the new state and the SetColor result
  6. let newState = {state with color = color}
  7. (colorResult,newState)

With the new versions of the turtle functions available, we have to create implementations that can respond to the error cases. That will be done in the next two examples.

The source code for the new turtle functions is available here.


12: Monadic control flow

In this approach, we will reuse the turtle workflow from way 8.
This time though, we will make decisions for the next command based on the result of the previous one.

Before we do that though, let’s look at what effect the change to move will have on our code. Let’s say that we want to move forwards a few times using move 40.0, say.

If we write the code using do! as we did before, we get a nasty compiler error:

  1. let drawShape() =
  2. // define a set of instructions
  3. let t = turtle {
  4. do! move 60.0
  5. // error FS0001:
  6. // This expression was expected to have type
  7. // Turtle.MoveResponse
  8. // but here has type
  9. // unit
  10. do! move 60.0
  11. }
  12. // etc

Instead, we need to use let! and assign the response to something.

In the following code, we assign the response to a value and then ignore it!

  1. let drawShapeWithoutResponding() =
  2. // define a set of instructions
  3. let t = turtle {
  4. let! response = move 60.0
  5. let! response = move 60.0
  6. let! response = move 60.0
  7. return ()
  8. }
  9. // finally, run the monad using the initial state
  10. runT t initialTurtleState

The code does compile and work, but if we run it the output shows that, by the third call, we are banging our turtle against the wall (at 100,0) and not moving anywhere.

  1. Move 60.0
  2. ...Draw line from (0.0,0.0) to (60.0,0.0) using Black
  3. Move 60.0
  4. ...Draw line from (60.0,0.0) to (100.0,0.0) using Black
  5. Move 60.0
  6. ...Draw line from (100.0,0.0) to (100.0,0.0) using Black

Making decisions based on a response

Let’s say that our response to a move that returns HitABarrier is to turn 90 degrees and wait for the next command. Not the cleverest algorithm, but it will do for demonstration purposes!

Let’s design a function to implement this. The input will be a MoveResponse, but what will the output be? We want to encode the turn action somehow, but the raw turn function needs
state input that we don’t have. So instead let’s return a turtle workflow that represents the instruction we want to do, when the state becomes available (in the run command).

So here is the code:

  1. let handleMoveResponse moveResponse = turtle {
  2. match moveResponse with
  3. | Turtle.MoveOk ->
  4. () // do nothing
  5. | Turtle.HitABarrier ->
  6. // turn 90 before trying again
  7. printfn "Oops -- hit a barrier -- turning"
  8. do! turn 90.0<Degrees>
  9. }

The type signature looks like this:

  1. val handleMoveResponse : MoveResponse -> TurtleStateComputation<unit>

which means that it is a monadic (or “diagonal”) function — one that starts in the normal world and ends in the TurtleStateComputation world.

These are exactly the functions that we can use “bind” with, or within computation expressions, let! or do!.

Now we can add this handleMoveResponse step after move in the turtle workflow:

  1. let drawShape() =
  2. // define a set of instructions
  3. let t = turtle {
  4. let! response = move 60.0
  5. do! handleMoveResponse response
  6. let! response = move 60.0
  7. do! handleMoveResponse response
  8. let! response = move 60.0
  9. do! handleMoveResponse response
  10. }
  11. // finally, run the monad using the initial state
  12. runT t initialTurtleState

And the result of running it is:

  1. Move 60.0
  2. ...Draw line from (0.0,0.0) to (60.0,0.0) using Black
  3. Move 60.0
  4. ...Draw line from (60.0,0.0) to (100.0,0.0) using Black
  5. Oops -- hit a barrier -- turning
  6. Turn 90.0
  7. Move 60.0
  8. ...Draw line from (100.0,0.0) to (100.0,60.0) using Black

You can see that the move response worked. When the turtle hit the edge at (100,0) it turned 90 degrees and the next move succeeded (from (100,0) to (100,60)).

So there you go! This code demonstrates how you can make decisions inside the turtle workflow while the state is being passed around behind the scenes.

Advantages and disadvantages

Advantages

  • Computation expressions allow the code to focus on the logic while taking care of the “plumbing” — in this case, the turtle state.

Disadvantages

  • Still coupled to a particular implementation of the turtle functions.
  • Computation expressions can be complex to implement and how they work is not obvious for beginners.

The source code for this version is available here.


13: A turtle interpreter

For our final approach, we’ll look at a way to completely decouple the programming of the turtle from its interpretation.

This is similar to the batch processing using command objects approach,
but is enhanced to support responding to the output of a command.

Designing an interpreter

The approach we will take is to design an “interpreter” for a set of turtle commands, where the client provides the commands to the turtle,
and responds to outputs from the turtle, but the actual turtle functions are provided later by a particular implementation.

In other words, we have a chain of interleaved commands and turtle functions that look like this:

Thirteen ways of looking at a turtle (part 2) - 图4

So how can we model this design in code?

For a first attempt, let’s model the chain as a sequence of request/response pairs. We send a command to the turtle and it responds appropriately with
a MoveResponse or whatever, like this:

  1. // we send this to the turtle...
  2. type TurtleCommand =
  3. | Move of Distance
  4. | Turn of Angle
  5. | PenUp
  6. | PenDown
  7. | SetColor of PenColor
  8. // ... and the turtle replies with one of these
  9. type TurtleResponse =
  10. | Moved of MoveResponse
  11. | Turned
  12. | PenWentUp
  13. | PenWentDown
  14. | ColorSet of SetColorResponse

The problem is that we cannot be sure that the response correctly matches the command. For example, if I send a Move command, I expect to get a MoveResponse, and never
a SetColorResponse. But this implementation doesn’t enforce that!

We want to make illegal states unrepresentable — how can we do that?

The trick is to combine the request and response in pairs. That is, for a Move command, there is an associated function which is given a MoveResponse as input, and similarly for each other combination.
Commands that have no response can be considered as returning unit for now.

  1. Move command => pair of (Move command parameters), (function MoveResponse -> something)
  2. Turn command => pair of (Turn command parameters), (function unit -> something)
  3. etc

The way this works is that:

  • The client creates a command, say Move 100, and also provides the additional function that handles the response.
  • The turtle implementation for the Move command (inside the interpreter) processes the input (a Distance) and then generates a MoveResponse.
  • The interpreter then takes this MoveResponse and calls the associated function in the pair, as supplied by the client.

By associating the Move command with a function in this way, we can guarantee that the internal turtle implementation must accept a distance and return a MoveResponse, just as we want.

The next question is: what is the something that is the output? It is the output after the client has handled the response — that is, another command/response chain!

So we can model the whole chain of pairs as a recursive structure:

Thirteen ways of looking at a turtle (part 2) - 图5

Or in code:

  1. type TurtleProgram =
  2. // (input params) (response)
  3. | Move of Distance * (MoveResponse -> TurtleProgram)
  4. | Turn of Angle * (unit -> TurtleProgram)
  5. | PenUp of (* none *) (unit -> TurtleProgram)
  6. | PenDown of (* none *) (unit -> TurtleProgram)
  7. | SetColor of PenColor * (SetColorResponse -> TurtleProgram)

I’ve renamed the type from TurtleCommand to TurtleProgram because it is no longer just a command, but is now a complete chain of commands and associated response handlers.

There’s a problem though! Every step needs yet another TurtleProgram to follow — so when will it stop? We need some way of saying that there is no next command.

To solve this issue, we will add a special Stop case to the program type:

  1. type TurtleProgram =
  2. // (input params) (response)
  3. | Stop
  4. | Move of Distance * (MoveResponse -> TurtleProgram)
  5. | Turn of Angle * (unit -> TurtleProgram)
  6. | PenUp of (* none *) (unit -> TurtleProgram)
  7. | PenDown of (* none *) (unit -> TurtleProgram)
  8. | SetColor of PenColor * (SetColorResponse -> TurtleProgram)

Note that there is no mention of TurtleState in this structure. How the turtle state is managed is internal to the interpreter, and is not part of the “instruction set”, as it were.

TurtleProgram is an example of an Abstract Syntax Tree (AST) — a structure that represents a program to interpreted (or compiled).

Testing the interpreter

Let’s create a little program using this model. Here’s our old friend drawTriangle:

  1. let drawTriangle =
  2. Move (100.0, fun response ->
  3. Turn (120.0<Degrees>, fun () ->
  4. Move (100.0, fun response ->
  5. Turn (120.0<Degrees>, fun () ->
  6. Move (100.0, fun response ->
  7. Turn (120.0<Degrees>, fun () ->
  8. Stop))))))

This program is a data structure containing only client commands and responses — there are no actual turtle functions in it anywhere!
And yes, it is really ugly right now, but we will fix that shortly.

Now the next step is to interpret this data structure.

Let’s create an interpreter that calls the real turtle functions. How would we implement the Move case, say?

Well, just as described above:

  • Get the distance and associated function from the Move case
  • Call the real turtle function with the distance and current turtle state, to get a MoveResult and a new turtle state.
  • Get the next step in the program by passing the MoveResult to the associated function
  • Finally call the interpreter again (recursively) with the new program and new turtle state.
  1. let rec interpretAsTurtle state program =
  2. ...
  3. match program with
  4. | Move (dist,next) ->
  5. let result,newState = Turtle.move log dist state
  6. let nextProgram = next result // compute the next step
  7. interpretAsTurtle newState nextProgram
  8. ...

You can see that the updated turtle state is passed as a parameter to the next recursive call, and so no mutable field is needed.

Here’s the full code for interpretAsTurtle:

  1. let rec interpretAsTurtle state program =
  2. let log = printfn "%s"
  3. match program with
  4. | Stop ->
  5. state
  6. | Move (dist,next) ->
  7. let result,newState = Turtle.move log dist state
  8. let nextProgram = next result // compute the next step
  9. interpretAsTurtle newState nextProgram
  10. | Turn (angle,next) ->
  11. let newState = Turtle.turn log angle state
  12. let nextProgram = next() // compute the next step
  13. interpretAsTurtle newState nextProgram
  14. | PenUp next ->
  15. let newState = Turtle.penUp log state
  16. let nextProgram = next()
  17. interpretAsTurtle newState nextProgram
  18. | PenDown next ->
  19. let newState = Turtle.penDown log state
  20. let nextProgram = next()
  21. interpretAsTurtle newState nextProgram
  22. | SetColor (color,next) ->
  23. let result,newState = Turtle.setColor log color state
  24. let nextProgram = next result
  25. interpretAsTurtle newState nextProgram

Let’s run it:

  1. let program = drawTriangle
  2. let interpret = interpretAsTurtle // choose an interpreter
  3. let initialState = Turtle.initialTurtleState
  4. interpret initialState program |> ignore

and the output is exactly what we have seen before:

  1. Move 100.0
  2. ...Draw line from (0.0,0.0) to (100.0,0.0) using Black
  3. Turn 120.0
  4. Move 100.0
  5. ...Draw line from (100.0,0.0) to (50.0,86.6) using Black
  6. Turn 120.0
  7. Move 100.0
  8. ...Draw line from (50.0,86.6) to (0.0,0.0) using Black
  9. Turn 120.0

But unlike all the previous approaches we can take exactly the same program and interpret it in a new way.
We don’t need to set up any kind of dependency injection, we just need to use a different interpreter.

So let’s create another interpreter that aggregates the distance travelled, without caring about the turtle state:

  1. let rec interpretAsDistance distanceSoFar program =
  2. let recurse = interpretAsDistance
  3. let log = printfn "%s"
  4. match program with
  5. | Stop ->
  6. distanceSoFar
  7. | Move (dist,next) ->
  8. let newDistanceSoFar = distanceSoFar + dist
  9. let result = Turtle.MoveOk // hard-code result
  10. let nextProgram = next result
  11. recurse newDistanceSoFar nextProgram
  12. | Turn (angle,next) ->
  13. // no change in distanceSoFar
  14. let nextProgram = next()
  15. recurse distanceSoFar nextProgram
  16. | PenUp next ->
  17. // no change in distanceSoFar
  18. let nextProgram = next()
  19. recurse distanceSoFar nextProgram
  20. | PenDown next ->
  21. // no change in distanceSoFar
  22. let nextProgram = next()
  23. recurse distanceSoFar nextProgram
  24. | SetColor (color,next) ->
  25. // no change in distanceSoFar
  26. let result = Turtle.ColorOk // hard-code result
  27. let nextProgram = next result
  28. recurse distanceSoFar nextProgram

In this case, I’ve aliased interpretAsDistance as recurse locally to make it obvious what kind of recursion is happening.

Let’s run the same program with this new interpreter:

  1. let program = drawTriangle // same program
  2. let interpret = interpretAsDistance // choose an interpreter
  3. let initialState = 0.0
  4. interpret initialState program |> printfn "Total distance moved is %0.1f"

and the output is again exactly what we expect:

  1. Total distance moved is 300.0

Creating a “turtle program” workflow

That code for creating a program to interpret was pretty ugly! Can we create a computation expression to make it look nicer?

Well, in order to create a computation expression, we need return and bind functions, and those require that the
TurtleProgram type be generic.

No problem! Let’s make TurtleProgram generic then:

  1. type TurtleProgram<'a> =
  2. | Stop of 'a
  3. | Move of Distance * (MoveResponse -> TurtleProgram<'a>)
  4. | Turn of Angle * (unit -> TurtleProgram<'a>)
  5. | PenUp of (unit -> TurtleProgram<'a>)
  6. | PenDown of (unit -> TurtleProgram<'a>)
  7. | SetColor of PenColor * (SetColorResponse -> TurtleProgram<'a>)

Note that the Stop case has a value of type 'a associated with it now. This is needed so that we can implement return properly:

  1. let returnT x =
  2. Stop x

The bind function is more complicated to implement. Don’t worry about how it works right now — the important thing is that the types match up and it compiles!

  1. let rec bindT f inst =
  2. match inst with
  3. | Stop x ->
  4. f x
  5. | Move(dist,next) ->
  6. (*
  7. Move(dist,fun moveResponse -> (bindT f)(next moveResponse))
  8. *)
  9. // "next >> bindT f" is a shorter version of function response
  10. Move(dist,next >> bindT f)
  11. | Turn(angle,next) ->
  12. Turn(angle,next >> bindT f)
  13. | PenUp(next) ->
  14. PenUp(next >> bindT f)
  15. | PenDown(next) ->
  16. PenDown(next >> bindT f)
  17. | SetColor(color,next) ->
  18. SetColor(color,next >> bindT f)

With bind and return in place, we can create a computation expression:

  1. // define a computation expression builder
  2. type TurtleProgramBuilder() =
  3. member this.Return(x) = returnT x
  4. member this.Bind(x,f) = bindT f x
  5. member this.Zero(x) = returnT ()
  6. // create an instance of the computation expression builder
  7. let turtleProgram = TurtleProgramBuilder()

We can now create a workflow that handles MoveResponses just as in the monadic control flow example (way 12) earlier.

  1. // helper functions
  2. let stop = fun x -> Stop x
  3. let move dist = Move (dist, stop)
  4. let turn angle = Turn (angle, stop)
  5. let penUp = PenUp stop
  6. let penDown = PenDown stop
  7. let setColor color = SetColor (color,stop)
  8. let handleMoveResponse log moveResponse = turtleProgram {
  9. match moveResponse with
  10. | Turtle.MoveOk ->
  11. ()
  12. | Turtle.HitABarrier ->
  13. // turn 90 before trying again
  14. log "Oops -- hit a barrier -- turning"
  15. let! x = turn 90.0<Degrees>
  16. ()
  17. }
  18. // example
  19. let drawTwoLines log = turtleProgram {
  20. let! response = move 60.0
  21. do! handleMoveResponse log response
  22. let! response = move 60.0
  23. do! handleMoveResponse log response
  24. }

Let’s interpret this using the real turtle functions (assuming that the interpretAsTurtle function has been modified to handle the new generic structure):

  1. let log = printfn "%s"
  2. let program = drawTwoLines log
  3. let interpret = interpretAsTurtle
  4. let initialState = Turtle.initialTurtleState
  5. interpret initialState program |> ignore

The output shows that the MoveResponse is indeed being handled correctly when the barrier is encountered:

  1. Move 60.0
  2. ...Draw line from (0.0,0.0) to (60.0,0.0) using Black
  3. Move 60.0
  4. ...Draw line from (60.0,0.0) to (100.0,0.0) using Black
  5. Oops -- hit a barrier -- turning
  6. Turn 90.0

Refactoring the TurtleProgram type into two parts

This approach works fine, but it bothers me that there is a special Stop case in the TurtleProgram type. It would nice if we could somehow
just focus on the five turtle actions and ignore it.

As it turns out, there is a way to do this. In Haskell and Scalaz it would be called a “free monad”, but since F# doesn’t support typeclasses,
I’ll just call it the “free monad pattern” that you can use to solve the problem. There’s a little bit of boilerplate that
you have to write, but not much.

The trick is to separate the api cases and “stop”/“keep going” logic into two separate types, like this:

  1. /// Create a type to represent each instruction
  2. type TurtleInstruction<'next> =
  3. | Move of Distance * (MoveResponse -> 'next)
  4. | Turn of Angle * 'next
  5. | PenUp of 'next
  6. | PenDown of 'next
  7. | SetColor of PenColor * (SetColorResponse -> 'next)
  8. /// Create a type to represent the Turtle Program
  9. type TurtleProgram<'a> =
  10. | Stop of 'a
  11. | KeepGoing of TurtleInstruction<TurtleProgram<'a>>

Note that I’ve also changed the responses for Turn, PenUp and PenDown to be single values rather than a unit function. Move and SetColor remain as functions though.

In this new “free monad” approach, the only custom code we need to write is a simple map function for the api type, in this case TurtleInstruction:

  1. let mapInstr f inst =
  2. match inst with
  3. | Move(dist,next) -> Move(dist,next >> f)
  4. | Turn(angle,next) -> Turn(angle,f next)
  5. | PenUp(next) -> PenUp(f next)
  6. | PenDown(next) -> PenDown(f next)
  7. | SetColor(color,next) -> SetColor(color,next >> f)

The rest of the code (return, bind, and the computation expression) is
always implemented exactly the same way, regardless of the particular api.
That is, more boilerplate is needed but less thinking is required!

The interpreters need to change in order to handle the new cases. Here’s a snippet of the new version of interpretAsTurtle:

  1. let rec interpretAsTurtle log state program =
  2. let recurse = interpretAsTurtle log
  3. match program with
  4. | Stop a ->
  5. state
  6. | KeepGoing (Move (dist,next)) ->
  7. let result,newState = Turtle.move log dist state
  8. let nextProgram = next result // compute next program
  9. recurse newState nextProgram
  10. | KeepGoing (Turn (angle,next)) ->
  11. let newState = Turtle.turn log angle state
  12. let nextProgram = next // use next program directly
  13. recurse newState nextProgram

And we also need to adjust the helper functions when creating a workflow. You can see below that we now have slightly
more complicated code like KeepGoing (Move (dist, Stop)) instead of the simpler code in the original interpreter.

  1. // helper functions
  2. let stop = Stop()
  3. let move dist = KeepGoing (Move (dist, Stop)) // "Stop" is a function
  4. let turn angle = KeepGoing (Turn (angle, stop)) // "stop" is a value
  5. let penUp = KeepGoing (PenUp stop)
  6. let penDown = KeepGoing (PenDown stop)
  7. let setColor color = KeepGoing (SetColor (color,Stop))
  8. let handleMoveResponse log moveResponse = turtleProgram {
  9. ... // as before
  10. // example
  11. let drawTwoLines log = turtleProgram {
  12. let! response = move 60.0
  13. do! handleMoveResponse log response
  14. let! response = move 60.0
  15. do! handleMoveResponse log response
  16. }

But with those changes, we are done, and the code works just as before.

Advantages and disadvantages of the interpreter pattern

Advantages

  • Decoupling. An abstract syntax tree completely decouples the program flow from the implementation and allows lots of flexibility.
  • Optimization. Abstract syntax trees can be manipulated and changed before running them, in order to do optimizations or other transformations. As an example, for the turtle program,
    we could process the tree and collapse all contiguous sequences of Turn into a single Turn operation.
    This is a simple optimization which saves on the number of times we need to communicate with a physical turtle. Twitter’s Stitch library
    does something like this, but obviously, in a more sophisticated way. This video has a good explanation.
  • Minimal code for a lot of power. The “free monad” approach to creating abstract syntax trees allows you to focus on the API and ignore the Stop/KeepGoing logic, and also means that only a minimal amount of code needs to be customized.
    For more on the free monad, start with this excellent video and then see this post
    and this one.

Disadvantages

  • Complex to understand.
  • Only works well if there are a limited set of operations to perform.
  • Can be inefficient if the ASTs get too large.

The source code for this version is available here (original version)
and here (“free monad” version).


Review of techniques used

In this post, we looked at thirteen different ways to implement a turtle API, using a wide variety of different techniques. Let’s quickly run down all the techniques that were used:

  • Pure, stateless functions. As seen in all of the FP-oriented examples. All these are very easy to test and mock.
  • Partial application. As first seen in the simplest FP example (way 2), when the turtle functions had the logging function applied so that the main flow could use piping,
    and thereafter used extensively, particularly in the “dependency injection using functions approach” (way 7).
  • Object expressions to implement an interface without creating a class, as seen in way 6.
  • The Result type (a.k.a the Either monad). Used in all the functional API examples (e.g. way 4) to return an error rather than throw an exception.
  • Applicative “lifting” (e.g. lift2) to lift normal functions to the world of Results, again in way 4 and others.
  • Lots of different ways of managing state:
    • mutable fields (way 1)
    • managing state explicitly and piping it though a series of functions (way 2)
    • having state only at the edge (the functional core/imperative shell in way 4)
    • hiding state in an agent (way 5)
    • threading state behind the scenes in a state monad (the turtle workflow in ways 8 and 12)
    • avoiding state altogether by using batches of commands (way 9) or batches of events (way 10) or an interpreter (way 13)
  • Wrapping a function in a type. Used in way 8 to manage state (the State monad) and in way 13 to store responses.
  • Computation expressions, lots of them! We created and used three:
    • result for working with errors
    • turtle for managing turtle state
    • turtleProgram for building an AST in the interpreter approach (way 13).
  • Chaining of monadic functions in the result and turtle workflows. The underlying functions are monadic (“diagonal”) and would not normally compose properly,
    but inside a workflow, they can be sequenced easily and transparently.
  • Representing behavior as a data structure in the “functional dependency injection” example (way 7) so that a single function could be passed in rather than a whole interface.
  • Decoupling using a data-centric protocol as seen in the agent, batch command, event sourcing, and interpreter examples.
  • Lock free and async processing using an agent (way 5).
  • The separation of “building” a computation vs. “running” it, as seen in the turtle workflows (ways 8 and 12) and the turtleProgram workflow (way 13: interpreter).
  • Use of event sourcing to rebuild state from scratch rather than maintaining mutable state in memory, as seen in the event sourcing (way 10)
    and FRP (way 11) examples.
  • Use of event streams and FRP (way 11) to break business logic into small, independent, and decoupled processors rather than having a monolithic object.

I hope it’s clear that examining these thirteen ways is just a fun exercise, and I’m not suggesting that you immediately convert all your code to use stream processors and interpreters! And, especially
if you are working with people who are new to functional programming, I would tend to stick with the earlier (and simpler) approaches unless there is a clear benefit in exchange for the extra complexity.


Summary

When the tortoise crawled out of sight,
It marked the edge
Of one of many circles.
“Thirteen ways of looking at a turtle”, by Wallace D Coriacea

I hope you enjoyed this post. I certainly enjoyed writing it. As usual, it ended up much longer than I intended, so I hope that the effort of reading it was worth it to you!

If you like this kind of comparative approach, and want more, check out the posts by Yan Cui, who is doing something similar on his blog.

Enjoy the rest of the F# Advent Calendar. Happy Holidays!

The source code for this post is available on github.