layout: post
title: “Thirteen ways of looking at a turtle - addendum”
description: “Bonus ways: An Abstract Data Turtle and a Capability-based Turtle.”

categories: [Patterns]

In this, the third part of my two-part mega-post, I’m continuing to stretch the simple turtle graphics model to the breaking point.

In the first and second post,
I described thirteen different ways of looking at a turtle graphics implementation.

Unfortunately, after I published them, I realized that there were some other ways that I had forgotten to mention.
So in this post, you’ll get to see two BONUS ways.

As a reminder, here were the previous thirteen ways:

All source code for this post is available on github.


14: Abstract Data Turtle

In this design, we use the concept of an abstract data type to encapsulate the operations on a turtle.

That is, a “turtle” is defined as an opaque type along with a corresponding set of operations, in the same way that standard F# types such as List, Set and Map are defined.

That is, we have number of functions that work on the type, but we are not allowed to see “inside” the type itself.

In a sense, you can think of it as a third alternative to the OO approach in way 1 and the functional approach in way 2.

  • In the OO implementation, the details of the internals are nicely encapsulated, and access is only via methods. The downside of the OO class is that it is mutable.
  • In the FP implementation, the TurtleState is immutable, but the downside is that the internals of the state are public, and some clients may have accessed these fields,
    so if we ever change the design of TurtleState, these clients may break.

The abstract data type implementation combines the best of both worlds: the turtle state is immutable, as in the original FP way, but no client can access it, as in the OO way.

The design for this (and for any abstract type) is as follows:

  • The turtle state type itself is public, but its constructor and fields are private.
  • The functions in the associated Turtle module can see inside the turtle state type (and so are unchanged from the FP design).
  • Because the turtle state constructor is private, we need a constructor function in the Turtle module.
  • The client can not see inside the turtle state type, and so must rely entirely on the Turtle module functions.

That’s all there is to it. We only need to add some privacy modifiers to the earlier FP version and we are done!

The implementation

First, we are going to put both the turtle state type and the Turtle module inside a common module called AdtTurtle.
This allows the turtle state to be accessible to the functions in the AdtTurtle.Turtle module, while being inaccessible outside the AdtTurtle.

Next, the turtle state type is going to be called Turtle now, rather than TurtleState, because we are treating it almost as an object.

Finally, the associated module Turtle (that contains the functions) is going have some special attributes:

  • RequireQualifiedAccess means the module name must be used when accessing the functions (just like List module)
  • ModuleSuffix is needed so the that module can have the same name as the state type. This would not be required for generic types (e.g if we had Turtle<'a> instead).
  1. module AdtTurtle =
  2. /// A private structure representing the turtle
  3. type Turtle = private {
  4. position : Position
  5. angle : float<Degrees>
  6. color : PenColor
  7. penState : PenState
  8. }
  9. /// Functions for manipulating a turtle
  10. /// "RequireQualifiedAccess" means the module name *must*
  11. /// be used (just like List module)
  12. /// "ModuleSuffix" is needed so the that module can
  13. /// have the same name as the state type
  14. [<RequireQualifiedAccess>]
  15. [<CompilationRepresentation (CompilationRepresentationFlags.ModuleSuffix)>]
  16. module Turtle =

An alternative way to avoid collisions is to have the state type have a different case, or a different name with a lowercase alias, like this:

  1. type TurtleState = { ... }
  2. type turtle = TurtleState
  3. module Turtle =
  4. let something (t:turtle) = t

No matter how the naming is done, we will need a way to construct a new Turtle.

If there are no parameters to the constructor, and the state is immutable, then we just need an initial value rather than a function (like Set.empty say).

Otherwise we can define a function called make (or create or similar):

  1. [<RequireQualifiedAccess>]
  2. [<CompilationRepresentation (CompilationRepresentationFlags.ModuleSuffix)>]
  3. module Turtle =
  4. /// return a new turtle with the specified color
  5. let make(initialColor) = {
  6. position = initialPosition
  7. angle = 0.0<Degrees>
  8. color = initialColor
  9. penState = initialPenState
  10. }

The rest of the turtle module functions are unchanged from their implementation in way 2.

An ADT client

Let’s look the client now.

First, let’s check that the state really is private. If we try to create a state explicitly, as shown below, we get a compiler error:

  1. let initialTurtle = {
  2. position = initialPosition
  3. angle = 0.0<Degrees>
  4. color = initialColor
  5. penState = initialPenState
  6. }
  7. // Compiler error FS1093:
  8. // The union cases or fields of the type 'Turtle'
  9. // are not accessible from this code location

If we use the constructor and then try to directly access a field directly (such as position), we again get a compiler error:

  1. let turtle = Turtle.make(Red)
  2. printfn "%A" turtle.position
  3. // Compiler error FS1093:
  4. // The union cases or fields of the type 'Turtle'
  5. // are not accessible from this code location

But if we stick to the functions in the Turtle module, we can safely create a state value and then call functions on it, just as we did before:

  1. // versions with log baked in (via partial application)
  2. let move = Turtle.move log
  3. let turn = Turtle.turn log
  4. // etc
  5. let drawTriangle() =
  6. Turtle.make(Red)
  7. |> move 100.0
  8. |> turn 120.0<Degrees>
  9. |> move 100.0
  10. |> turn 120.0<Degrees>
  11. |> move 100.0
  12. |> turn 120.0<Degrees>

Advantages and disadvantages of ADTs

Advantages

  • All code is stateless, hence easy to test.
  • The encapsulation of the state means that the focus is always fully on the behavior and properties of the type.
  • Clients can never have a dependency on a particular implementation, which means that implementations can be changed safely.
  • You can even swap implementations (e.g. by shadowing, or linking to a different assembly) for testing, performance, etc.

Disadvantages

  • The client has to manage the current turtle state.
  • The client has no control over the implementation (e.g. by using dependency injection).

For more on ADTs in F#, see this talk and thread by Bryan Edds.

The source code for this version is available here.


15: Capability-based Turtle

In the “monadic control flow” approach (way 12) we handled responses from the turtle telling us that it had hit a barrier.

But even though we had hit a barrier, nothing was stopping us from calling the move operation over and over again!

Now imagine that, once we had hit the barrier, the move operation was no longer available to us. We couldn’t abuse it because it would be no longer there!

To make this work, we shouldn’t provide an API, but instead, after each call, return a list of functions that the client can call to do the next step. The functions would normally include
the usual suspects of move, turn, penUp, etc., but when we hit a barrier, move would be dropped from that list. Simple, but effective.

This technique is closely related to an authorization and security technique called capability-based security. If you are interested in learning more,
I have a whole series of posts devoted to it.

Designing a capability-based Turtle

The first thing is to define the record of functions that will be returned after each call:

  1. type MoveResponse =
  2. | MoveOk
  3. | HitABarrier
  4. type SetColorResponse =
  5. | ColorOk
  6. | OutOfInk
  7. type TurtleFunctions = {
  8. move : MoveFn option
  9. turn : TurnFn
  10. penUp : PenUpDownFn
  11. penDown : PenUpDownFn
  12. setBlack : SetColorFn option
  13. setBlue : SetColorFn option
  14. setRed : SetColorFn option
  15. }
  16. and MoveFn = Distance -> (MoveResponse * TurtleFunctions)
  17. and TurnFn = Angle -> TurtleFunctions
  18. and PenUpDownFn = unit -> TurtleFunctions
  19. and SetColorFn = unit -> (SetColorResponse * TurtleFunctions)

Let’s look at these declarations in detail.

First, there is no TurtleState anywhere. The published turtle functions will encapsulate the state for us. Similarly there is no log function.

Next, the record of functions TurtleFunctions defines a field for each function in the API (move, turn, etc.):

  • The move function is optional, meaning that it might not be available.
  • The turn, penUp and penDown functions are always available.
  • The setColor operation has been broken out into three separate functions, one for each color, because you might not be able to use red ink, but still be able to use blue ink.
    To indicate that these functions might not be available, option is used again.

We have also declared type aliases for each function to make them easier to work. Writing MoveFn is easier than writing Distance -> (MoveResponse * TurtleFunctions) everywhere!
Note that, since these definitions are mutually recursive, I was forced to use the and keyword.

Finally, note the difference between the signature of MoveFn in this design and the signature of move in the earlier design of way 12.

Earlier version:

  1. val move :
  2. Log -> Distance -> TurtleState -> (MoveResponse * TurtleState)

New version:

  1. val move :
  2. Distance -> (MoveResponse * TurtleFunctions)

On the input side, the Log and TurtleState parameters are gone, and on the output side, the TurtleState has been replaced with TurtleFunctions.

This means that somehow, the output of every API function must be changed to be a TurtleFunctions record.

Implementing the turtle operations

In order to decide whether we can indeed move, or use a particular color, we first need to augment the TurtleState type to track these factors:

  1. type Log = string -> unit
  2. type private TurtleState = {
  3. position : Position
  4. angle : float<Degrees>
  5. color : PenColor
  6. penState : PenState
  7. canMove : bool // new!
  8. availableInk: Set<PenColor> // new!
  9. logger : Log // new!
  10. }

This has been enhanced with

  • canMove, which if false means that we are at a barrier and should not return a valid move function.
  • availableInk contains a set of colors. If a color is not in this set, then we should not return a valid setColorXXX function for that color.
  • Finally, we’ve added the log function into the state so that we don’t have to pass it explicitly to each operation. It will get set once, when the turtle is created.

The TurtleState is getting a bit ugly now, but that’s alright, because it’s private! The clients will never even see it.

With this augmented state available, we can change move. First we’ll make it private, and second we’ll set the canMove flag (using moveResult <> HitABarrier) before returning a new state:

  1. /// Function is private! Only accessible to the client via the TurtleFunctions record
  2. let private move log distance state =
  3. log (sprintf "Move %0.1f" distance)
  4. // calculate new position
  5. let newPosition = calcNewPosition distance state.angle state.position
  6. // adjust the new position if out of bounds
  7. let moveResult, newPosition = checkPosition newPosition
  8. // draw line if needed
  9. if state.penState = Down then
  10. dummyDrawLine log state.position newPosition state.color
  11. // return the new state and the Move result
  12. let newState = {
  13. state with
  14. position = newPosition
  15. canMove = (moveResult <> HitABarrier) // NEW!
  16. }
  17. (moveResult,newState)

We need some way of changing canMove back to true! So let’s assume that if you turn, you can move again.

Let’s add that logic to the turn function then:

  1. let private turn log angle state =
  2. log (sprintf "Turn %0.1f" angle)
  3. // calculate new angle
  4. let newAngle = (state.angle + angle) % 360.0<Degrees>
  5. // NEW!! assume you can always move after turning
  6. let canMove = true
  7. // update the state
  8. {state with angle = newAngle; canMove = canMove}

The penUp and penDown functions are unchanged, other than being made private.

And for the last operation, setColor, we’ll remove the ink from the availability set as soon as it is used just once!

  1. let private setColor log color state =
  2. let colorResult =
  3. if color = Red then OutOfInk else ColorOk
  4. log (sprintf "SetColor %A" color)
  5. // NEW! remove color ink from available inks
  6. let newAvailableInk = state.availableInk |> Set.remove color
  7. // return the new state and the SetColor result
  8. let newState = {state with color = color; availableInk = newAvailableInk}
  9. (colorResult,newState)

Finally we need a function that can create a TurtleFunctions record from the TurtleState. I’ll call it createTurtleFunctions.

Here’s the complete code, and I’ll discuss it in detail below:

  1. /// Create the TurtleFunctions structure associated with a TurtleState
  2. let rec private createTurtleFunctions state =
  3. let ctf = createTurtleFunctions // alias
  4. // create the move function,
  5. // if the turtle can't move, return None
  6. let move =
  7. // the inner function
  8. let f dist =
  9. let resp, newState = move state.logger dist state
  10. (resp, ctf newState)
  11. // return Some of the inner function
  12. // if the turtle can move, or None
  13. if state.canMove then
  14. Some f
  15. else
  16. None
  17. // create the turn function
  18. let turn angle =
  19. let newState = turn state.logger angle state
  20. ctf newState
  21. // create the pen state functions
  22. let penDown() =
  23. let newState = penDown state.logger state
  24. ctf newState
  25. let penUp() =
  26. let newState = penUp state.logger state
  27. ctf newState
  28. // create the set color functions
  29. let setColor color =
  30. // the inner function
  31. let f() =
  32. let resp, newState = setColor state.logger color state
  33. (resp, ctf newState)
  34. // return Some of the inner function
  35. // if that color is available, or None
  36. if state.availableInk |> Set.contains color then
  37. Some f
  38. else
  39. None
  40. let setBlack = setColor Black
  41. let setBlue = setColor Blue
  42. let setRed = setColor Red
  43. // return the structure
  44. {
  45. move = move
  46. turn = turn
  47. penUp = penUp
  48. penDown = penDown
  49. setBlack = setBlack
  50. setBlue = setBlue
  51. setRed = setRed
  52. }

Let’s look at how this works.

First, note that this function needs the rec keyword attached, as it refers to itself. I’ve added a shorter alias (ctf) for it as well.

Next, new versions of each of the API functions are created. For example, a new turn function is defined like this:

  1. let turn angle =
  2. let newState = turn state.logger angle state
  3. ctf newState

This calls the original turn function with the logger and state, and then uses the recursive call (ctf) to convert the new state into the record of functions.

For an optional function like move, it is a bit more complicated. An inner function f is defined, using the orginal move, and then either f is returned as Some,
or None is returned, depending on whether the state.canMove flag is set:

  1. // create the move function,
  2. // if the turtle can't move, return None
  3. let move =
  4. // the inner function
  5. let f dist =
  6. let resp, newState = move state.logger dist state
  7. (resp, ctf newState)
  8. // return Some of the inner function
  9. // if the turtle can move, or None
  10. if state.canMove then
  11. Some f
  12. else
  13. None

Similarly, for setColor, an inner function f is defined and then returned or not depending on whether the color parameter is in the state.availableInk collection:

  1. let setColor color =
  2. // the inner function
  3. let f() =
  4. let resp, newState = setColor state.logger color state
  5. (resp, ctf newState)
  6. // return Some of the inner function
  7. // if that color is available, or None
  8. if state.availableInk |> Set.contains color then
  9. Some f
  10. else
  11. None

Finally, all these functions are added to the record:

  1. // return the structure
  2. {
  3. move = move
  4. turn = turn
  5. penUp = penUp
  6. penDown = penDown
  7. setBlack = setBlack
  8. setBlue = setBlue
  9. setRed = setRed
  10. }

And that’s how you build a TurtleFunctions record!

We need one more thing: a constructor to create some initial value of the TurtleFunctions, since we no longer have direct access to the API. This is now the ONLY public function available to the client!

  1. /// Return the initial turtle.
  2. /// This is the ONLY public function!
  3. let make(initialColor, log) =
  4. let state = {
  5. position = initialPosition
  6. angle = 0.0<Degrees>
  7. color = initialColor
  8. penState = initialPenState
  9. canMove = true
  10. availableInk = [Black; Blue; Red] |> Set.ofList
  11. logger = log
  12. }
  13. createTurtleFunctions state

This function bakes in the log function, creates a new state, and then calls createTurtleFunctions to return a TurtleFunction record for the client to use.

Implementing a client of the capability-based turtle

Let’s try using this now. First, let’s try to do move 60 and then move 60 again. The second move should take us to the boundary (at 100),
and so at that point the move function should no longer be available.

First, we create the TurtleFunctions record with Turtle.make. Then we can’t just move immediately, we have to test to see if the move function is available first:

  1. let testBoundary() =
  2. let turtleFns = Turtle.make(Red,log)
  3. match turtleFns.move with
  4. | None ->
  5. log "Error: Can't do move 1"
  6. | Some moveFn ->
  7. ...

In the last case, the moveFn is available, so we can call it with a distance of 60.

The output of the function is a pair: a MoveResponse type and a new TurtleFunctions record.

We’ll ignore the MoveResponse and check the TurtleFunctions record again to see if we can do the next move:

  1. let testBoundary() =
  2. let turtleFns = Turtle.make(Red,log)
  3. match turtleFns.move with
  4. | None ->
  5. log "Error: Can't do move 1"
  6. | Some moveFn ->
  7. let (moveResp,turtleFns) = moveFn 60.0
  8. match turtleFns.move with
  9. | None ->
  10. log "Error: Can't do move 2"
  11. | Some moveFn ->
  12. ...

And finally, one more time:

  1. let testBoundary() =
  2. let turtleFns = Turtle.make(Red,log)
  3. match turtleFns.move with
  4. | None ->
  5. log "Error: Can't do move 1"
  6. | Some moveFn ->
  7. let (moveResp,turtleFns) = moveFn 60.0
  8. match turtleFns.move with
  9. | None ->
  10. log "Error: Can't do move 2"
  11. | Some moveFn ->
  12. let (moveResp,turtleFns) = moveFn 60.0
  13. match turtleFns.move with
  14. | None ->
  15. log "Error: Can't do move 3"
  16. | Some moveFn ->
  17. log "Success"

If we run this, we get the output:

  1. Move 60.0
  2. ...Draw line from (0.0,0.0) to (60.0,0.0) using Red
  3. Move 60.0
  4. ...Draw line from (60.0,0.0) to (100.0,0.0) using Red
  5. Error: Can't do move 3

Which shows that indeed, the concept is working!

That nested option matching is really ugly, so let’s whip up a quick maybe workflow to make it look nicer:

  1. type MaybeBuilder() =
  2. member this.Return(x) = Some x
  3. member this.Bind(x,f) = Option.bind f x
  4. member this.Zero() = Some()
  5. let maybe = MaybeBuilder()

And a logging function that we can use inside the workflow:

  1. /// A function that logs and returns Some(),
  2. /// for use in the "maybe" workflow
  3. let logO message =
  4. printfn "%s" message
  5. Some ()

Now we can try setting some colors using the maybe workflow:

  1. let testInk() =
  2. maybe {
  3. // create a turtle
  4. let turtleFns = Turtle.make(Black,log)
  5. // attempt to get the "setRed" function
  6. let! setRedFn = turtleFns.setRed
  7. // if so, use it
  8. let (resp,turtleFns) = setRedFn()
  9. // attempt to get the "move" function
  10. let! moveFn = turtleFns.move
  11. // if so, move a distance of 60 with the red ink
  12. let (resp,turtleFns) = moveFn 60.0
  13. // check if the "setRed" function is still available
  14. do! match turtleFns.setRed with
  15. | None ->
  16. logO "Error: Can no longer use Red ink"
  17. | Some _ ->
  18. logO "Success: Can still use Red ink"
  19. // check if the "setBlue" function is still available
  20. do! match turtleFns.setBlue with
  21. | None ->
  22. logO "Error: Can no longer use Blue ink"
  23. | Some _ ->
  24. logO "Success: Can still use Blue ink"
  25. } |> ignore

The output of this is:

  1. SetColor Red
  2. Move 60.0
  3. ...Draw line from (0.0,0.0) to (60.0,0.0) using Red
  4. Error: Can no longer use Red ink
  5. Success: Can still use Blue ink

Actually, using a maybe workflow is not a very good idea, because the first failure exits the workflow!
You’d want to come up with something a bit better for real code, but I hope that you get the idea.

Advantages and disadvantages of a capability-based approach

Advantages

  • Prevents clients from abusing the API.
  • Allows APIs to evolve (and devolve) without affecting clients. For example, I could transition to a monochrome-only turtle by hard-coding None for each color function in the record of functions,
    after which I could safely remove the setColor implementation. During this process no client would break! This is similar to the HATEAOS approach for RESTful web services.
  • Clients are decoupled from a particular implementation because the record of functions acts as an interface.

Disadvantages

  • Complex to implement.
  • The client’s logic is much more convoluted as it can never be sure that a function will be available! It has to check every time.
  • The API is not easily serializable, unlike some of the data-oriented APIs.

For more on capability-based security, see my posts or watch my “Enterprise Tic-Tac-Toe” video.

The source code for this version is available here.

Summary

I was of three minds,
Like a finger tree
In which there are three immutable turtles.
“Thirteen ways of looking at a turtle”, by Wallace D Coriacea

I feel better now that I’ve got these two extra ways out of my system! Thanks for reading!

The source code for this post is available on github.

.