Skip to content

Instantly share code, notes, and snippets.

@hamst

hamst/States-v3.md

Forked from andymatuschak/States-v3.md
Created August 9, 2016 08:04
Show Gist options
  • Save hamst/ac99f35870224f7d33206c3e4a4ac8a0 to your computer and use it in GitHub Desktop.
Save hamst/ac99f35870224f7d33206c3e4a4ac8a0 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @andymatuschak andymatuschak revised this gist Jul 30, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion States-v3.md
    View file
    Original file line number Diff line number Diff line change
    @@ -34,7 +34,7 @@ protocol StateType {
    // If this is confusing, keep in mind that we could equivalently define this as a function
    // which returns both a new state value and an optional OutputCommand (it just creates some
    // line noise later):
    // func handleEvent(event: InputEvent) -> (Self, OutputCommand?)
    // func handleEvent(event: InputEvent) -> (Self, OutputCommand)

    /// State machines must specify an initial value.
    static var initialState: Self { get }
  2. @andymatuschak andymatuschak revised this gist Jul 29, 2016. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions States-v3.md
    View file
    Original file line number Diff line number Diff line change
    @@ -32,8 +32,8 @@ protocol StateType {
    // change; the normal perils of mutability do not apply.
    //
    // If this is confusing, keep in mind that we could equivalently define this as a function
    // which returns both a new state value and an optional Command (it just creates some line
    // noise later):
    // which returns both a new state value and an optional OutputCommand (it just creates some
    // line noise later):
    // func handleEvent(event: InputEvent) -> (Self, OutputCommand?)

    /// State machines must specify an initial value.
  3. @andymatuschak andymatuschak renamed this gist Jul 29, 2016. 1 changed file with 0 additions and 0 deletions.
    0 States-v2.md → States-v3.md
    View file
    File renamed without changes.
  4. @andymatuschak andymatuschak revised this gist Jul 29, 2016. 1 changed file with 9 additions and 7 deletions.
    16 changes: 9 additions & 7 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -16,14 +16,14 @@ The key idea is that states, transitions, and specifications of effect are model
    protocol StateType {
    /// Events are effectful inputs from the outside world which the state reacts to, described by some
    /// data type. For instance: a button being clicked, or some network data arriving.
    associatedtype Event
    associatedtype InputEvent

    /// Commands are effectful outputs which the state desires to have performed on the outside world.
    /// For instance: showing an alert, transitioning to some different UI, etc.
    associatedtype Command
    associatedtype OutputCommand

    /// In response to an event, a state may transition to some new value, and it may emit a command.
    mutating func handleEvent(event: Event) -> Command?
    mutating func handleEvent(event: InputEvent) -> OutputCommand

    // If you're not familiar with Swift, the mutation semantics here may seem like a very big red
    // flag, destroying the purity of this type. In fact, because states have *value semantics*,
    @@ -34,7 +34,7 @@ protocol StateType {
    // If this is confusing, keep in mind that we could equivalently define this as a function
    // which returns both a new state value and an optional Command (it just creates some line
    // noise later):
    // func handleEvent(event: Event) -> (Self, Command?)
    // func handleEvent(event: InputEvent) -> (Self, OutputCommand?)

    /// State machines must specify an initial value.
    static var initialState: Self { get }
    @@ -294,9 +294,9 @@ struct KeyboardState: StateType {
    static let initialState = KeyboardState(mainKeypadState: MainKeypadState.initialState, numericKeypadState: NumericKeypadState.initialState)

    mutating func handleEvent(event: HardwareKeyEvent) -> KeyboardOutputCommand? {
    if let mainKeypadEvent = MainKeypadState.Event(event) {
    if let mainKeypadEvent = MainKeypadState.HardwareKeyEvent(event) {
    return mainKeypadState.handleEvent(mainKeypadEvent)
    } else if let numericKeypadEvent = NumericKeypadState.Event(event) {
    } else if let numericKeypadEvent = NumericKeypadState.HardwareKeyEvent(event) {
    return numericKeypadState.handleEvent(numericKeypadEvent)
    } else {
    return nil
    @@ -560,4 +560,6 @@ I'll save a detailed treatment on this topic for another day.

    ## Acknowledgements

    My thanks to Colin Barrett, Chris Eidhof, Justin Spahr-Summers, and Rob Rix for useful feedback on this draft.
    My thanks to Colin Barrett, Chris Eidhof, Justin Spahr-Summers, and Rob Rix for useful feedback on a first draft of this concept.

    My thanks to Matthew Johnson for suggesting that optionality of `OutputCommand` in `handleEvent()` can itself be optional.
  5. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -153,6 +153,9 @@ protocol DoorHardwareController {

    /// A signal which fires an event whenever the physical door hardware detects a person passing through.
    var opticalPersonPassingSensorSignal: Signal<(), NoError> { get }

    // If the idea of a Signal is not familiar, don't worry about it: it's not terribly
    // important here. This could be a callback or a delegate method instead.
    }

    protocol SpeakerController {
  6. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 0 additions and 7 deletions.
    7 changes: 0 additions & 7 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -158,13 +158,6 @@ protocol DoorHardwareController {
    protocol SpeakerController {
    func soundTheAlarm()
    }

    // Stubs to make the errors go away in Playgrounds:
    struct Signal<A, B> {
    func takeUntilObjectDeallocates(o: AnyObject) -> Signal<A, B> { return self }
    func subscribeNext(nextHandler: (A) -> Void) {}
    }
    struct NoError {}
    ```

    ## Hierarchical state machines
  7. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -73,6 +73,8 @@ enum TurnstyleState: StateType {
    static let initialState = TurnstyleState.Locked(credit: 0)
    private static let farePrice = 50

    // Try to picture the boxes-and-arrows diagram of this state machine using this
    // method. Hopefully the structure makes this translation mostly straightforward.
    mutating func handleEvent(event: Event) -> Command? {
    switch (self, event) {
    case (.Locked(let credit), .InsertCoin(let value)):
  8. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -30,6 +30,11 @@ protocol StateType {
    // mutation becomes mere syntax sugar. From a semantic perspective, any call to this method
    // creates a new instance of StateType; no code other than the caller has visibility to the
    // change; the normal perils of mutability do not apply.
    //
    // If this is confusing, keep in mind that we could equivalently define this as a function
    // which returns both a new state value and an optional Command (it just creates some line
    // noise later):
    // func handleEvent(event: Event) -> (Self, Command?)

    /// State machines must specify an initial value.
    static var initialState: Self { get }
  9. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -2,11 +2,11 @@

    State machines are everywhere in interactive systems, but they're rarely defined clearly and explicitly. Given some big blob of code including implicit state machines, which transitions are possible and under what conditions? What effects take place on what transitions?

    There are [existing design patterns for state machines](https://en.wikipedia.org/wiki/State_pattern), but all the patterns I've seen complect side effects with the structure of the state machine itself. Instances of these patterns are difficult to test without mocking, and they end up with more dependencies. Worse, the classic patterns compose poorly: hierarchical state machines are typically not straightforward extensions.
    There are [existing design patterns for state machines](https://en.wikipedia.org/wiki/State_pattern), but all the patterns I've seen complect side effects with the structure of the state machine itself. Instances of these patterns are difficult to test without mocking, and they end up with more dependencies. Worse, the classic patterns compose poorly: hierarchical state machines are typically not straightforward extensions. The functional programming world has [solutions](https://hackage.haskell.org/package/reactive-banana), but they don't transpose neatly enough to be broadly usable in mainstream languages.

    Here I present a composable pattern for pure state machiness with effects. The pure-impure separation is inspired by _[functional core, imperative shell](https://www.destroyallsoftware.com/talks/boundaries)_; the modeling of novelty and effect by [Elm](http://elm-lang.org); the hierarchical composition by [Harel statecharts](http://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf).
    Here I present a composable pattern for pure state machiness with effects, meant to be idiomatic in a typical imperative context. The pure-impure separation is inspired by _[functional core, imperative shell](https://www.destroyallsoftware.com/talks/boundaries)_; the modeling of novelty and effect by [Elm](http://elm-lang.org); the hierarchical composition by [Harel statecharts](http://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf).

    The solution is implemented in Swift because I'm particularly interested in a solution which makes sense in a fairly typical imperative context, and because Swift's types help illustrate the structure I'm suggesting.
    The solution is implemented in Swift because it's a typical imperative context, and because Swift's types help illustrate the structure I'm suggesting.

    ## The basic types

  10. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 11 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -14,28 +14,28 @@ The key idea is that states, transitions, and specifications of effect are model

    ```swift
    protocol StateType {
    /// Events are effectful inputs from the outside world which the state reacts to, described by some data type.
    /// For instance: a button being clicked, or some network data arriving.
    /// Events are effectful inputs from the outside world which the state reacts to, described by some
    /// data type. For instance: a button being clicked, or some network data arriving.
    associatedtype Event

    /// Commands are effectful outputs which the state desires to have performed on the outside world. For
    /// instance: showing an alert, transitioning to some different UI, etc.
    /// Commands are effectful outputs which the state desires to have performed on the outside world.
    /// For instance: showing an alert, transitioning to some different UI, etc.
    associatedtype Command

    /// In response to an event, a state may transition to some new value, and it may emit a command.
    mutating func handleEvent(event: Event) -> Command?

    // If you're not familiar with Swift, the mutation semantics here may seem like a very big red flag,
    // destroying the purity of this type. In fact, because states have *value semantics*, mutation becomes
    // mere syntax sugar. From a semantic perspective, any call to this method creates a new instance of
    // StateType; no code other than the caller has visibility to the change; the normal perils of mutability
    // do not apply.
    // If you're not familiar with Swift, the mutation semantics here may seem like a very big red
    // flag, destroying the purity of this type. In fact, because states have *value semantics*,
    // mutation becomes mere syntax sugar. From a semantic perspective, any call to this method
    // creates a new instance of StateType; no code other than the caller has visibility to the
    // change; the normal perils of mutability do not apply.

    /// State machines must specify an initial value.
    static var initialState: Self { get }

    // Traditional models often allow states to specific commands to be performed on entry or exit.
    // We could add that, or not.
    // Traditional models often allow states to specific commands to be performed on entry or
    // exit. We could add that, or not.
    }
    ```

  11. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -42,6 +42,7 @@ protocol StateType {
    ## A basic state machine with effects

    Here's an example based on [A Pattern Language of Statecharts](http://industriallogic.net/patterns/P22.pdf), figure 3:

    ![Drawing of a simple turnstyle state machine, implemented below](https://andymatuschak.org/states/figure3.png)

    ```swift
    @@ -162,6 +163,7 @@ struct NoError {}
    ## Hierarchical state machines

    Now, if you have a lot of states, you might want to start grouping them into "child" state machines, especially if there's a significant shared semantic. Here I rephrase the example state machine hierarchically: an inner state machine and an outer one, following figure 6 from "A Pattern Language of Statecharts."

    ![Drawing of the turnstyle state machine, depicted hierarchically](https://andymatuschak.org/states/figure6.png)

    Critically, *no other types* must change: the code above can use HierarchicalTurnstyleState as a drop-in replacement. StateTypes are closed under hierarchical composition. This is a natural consequence of the data-oriented design, which takes advantage of the simpler fact that enums are closed over carrying instances of other enums as an associated value, and that functions are closed over calling other functions. Nothing more complicated is required.
  12. @andymatuschak andymatuschak revised this gist Jul 28, 2016. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions States-v2.md
    View file
    Original file line number Diff line number Diff line change
    @@ -42,7 +42,7 @@ protocol StateType {
    ## A basic state machine with effects

    Here's an example based on [A Pattern Language of Statecharts](http://industriallogic.net/patterns/P22.pdf), figure 3:
    ![figure 3](figure3.png)
    ![Drawing of a simple turnstyle state machine, implemented below](https://andymatuschak.org/states/figure3.png)

    ```swift
    /// First up, the StateType. Note that this type is isolated, pure, trivial to fully test with zero mocks/stubs, etc.
    @@ -162,7 +162,7 @@ struct NoError {}
    ## Hierarchical state machines

    Now, if you have a lot of states, you might want to start grouping them into "child" state machines, especially if there's a significant shared semantic. Here I rephrase the example state machine hierarchically: an inner state machine and an outer one, following figure 6 from "A Pattern Language of Statecharts."
    ![figure 6](figure6.png)
    ![Drawing of the turnstyle state machine, depicted hierarchically](https://andymatuschak.org/states/figure6.png)

    Critically, *no other types* must change: the code above can use HierarchicalTurnstyleState as a drop-in replacement. StateTypes are closed under hierarchical composition. This is a natural consequence of the data-oriented design, which takes advantage of the simpler fact that enums are closed over carrying instances of other enums as an associated value, and that functions are closed over calling other functions. Nothing more complicated is required.

    @@ -271,7 +271,7 @@ The relationship between this kind of composition (orthogonal) and the earlier k

    For instance, a keyboard might have two different state machines running simultaneously: one handles the toggling behavior of the main keypad's caps lock key and its impact on keypad behavior; the other handles the same thing for the numpad and num lock.

    ![keyboard state machine diagram](keyboard.png)
    ![Drawing of a keyboard's state machine, separating caps lock and num lock functionality](https://andymatuschak.org/states/keyboard.png)

    ```swift
    struct KeyboardState: StateType {
    @@ -555,4 +555,4 @@ I'll save a detailed treatment on this topic for another day.

    ## Acknowledgements

    My thanks to Colin Barrett, Justin Spahr-Summers, Rob Rix, and Chris Eidhoff for useful feedback on this draft.
    My thanks to Colin Barrett, Chris Eidhof, Justin Spahr-Summers, and Rob Rix for useful feedback on this draft.
  13. @andymatuschak andymatuschak renamed this gist Jul 28, 2016. 1 changed file with 0 additions and 0 deletions.
    0 States-v2.down → States-v2.md
    View file
    File renamed without changes.
  14. @andymatuschak andymatuschak renamed this gist Jul 28, 2016. 1 changed file with 0 additions and 0 deletions.
    0 States-v2.swift → States-v2.down
    View file
    File renamed without changes.
  15. @andymatuschak andymatuschak created this gist Jul 28, 2016.
    558 changes: 558 additions & 0 deletions States-v2.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,558 @@
    # A composable pattern for pure state machines with effects

    State machines are everywhere in interactive systems, but they're rarely defined clearly and explicitly. Given some big blob of code including implicit state machines, which transitions are possible and under what conditions? What effects take place on what transitions?

    There are [existing design patterns for state machines](https://en.wikipedia.org/wiki/State_pattern), but all the patterns I've seen complect side effects with the structure of the state machine itself. Instances of these patterns are difficult to test without mocking, and they end up with more dependencies. Worse, the classic patterns compose poorly: hierarchical state machines are typically not straightforward extensions.

    Here I present a composable pattern for pure state machiness with effects. The pure-impure separation is inspired by _[functional core, imperative shell](https://www.destroyallsoftware.com/talks/boundaries)_; the modeling of novelty and effect by [Elm](http://elm-lang.org); the hierarchical composition by [Harel statecharts](http://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf).

    The solution is implemented in Swift because I'm particularly interested in a solution which makes sense in a fairly typical imperative context, and because Swift's types help illustrate the structure I'm suggesting.

    ## The basic types

    The key idea is that states, transitions, and specifications of effect are modeled by a _pure value type_; a separate dumb object actuates those effects (as in Elm; or think of the traditional [Command pattern](https://en.wikipedia.org/wiki/Command_pattern)).

    ```swift
    protocol StateType {
    /// Events are effectful inputs from the outside world which the state reacts to, described by some data type.
    /// For instance: a button being clicked, or some network data arriving.
    associatedtype Event

    /// Commands are effectful outputs which the state desires to have performed on the outside world. For
    /// instance: showing an alert, transitioning to some different UI, etc.
    associatedtype Command

    /// In response to an event, a state may transition to some new value, and it may emit a command.
    mutating func handleEvent(event: Event) -> Command?

    // If you're not familiar with Swift, the mutation semantics here may seem like a very big red flag,
    // destroying the purity of this type. In fact, because states have *value semantics*, mutation becomes
    // mere syntax sugar. From a semantic perspective, any call to this method creates a new instance of
    // StateType; no code other than the caller has visibility to the change; the normal perils of mutability
    // do not apply.

    /// State machines must specify an initial value.
    static var initialState: Self { get }

    // Traditional models often allow states to specific commands to be performed on entry or exit.
    // We could add that, or not.
    }
    ```

    ## A basic state machine with effects

    Here's an example based on [A Pattern Language of Statecharts](http://industriallogic.net/patterns/P22.pdf), figure 3:
    ![figure 3](figure3.png)

    ```swift
    /// First up, the StateType. Note that this type is isolated, pure, trivial to fully test with zero mocks/stubs, etc.
    enum TurnstyleState: StateType {
    case Locked(credit: Int)
    case Unlocked
    indirect case Broken(oldState: TurnstyleState)

    enum Event {
    case InsertCoin(value: Int)
    case AdmitPerson
    case MachineDidFail
    case MachineRepairDidComplete
    }

    enum Command {
    case SoundAlarm
    case CloseDoors
    case OpenDoors
    }

    static let initialState = TurnstyleState.Locked(credit: 0)
    private static let farePrice = 50

    mutating func handleEvent(event: Event) -> Command? {
    switch (self, event) {
    case (.Locked(let credit), .InsertCoin(let value)):
    let newCredit = credit + value
    if newCredit >= TurnstyleState.farePrice {
    self = .Unlocked
    return .OpenDoors
    } else {
    self = .Locked(credit: newCredit)
    }
    case (.Locked, .AdmitPerson):
    return .SoundAlarm
    case (.Locked, .MachineDidFail):
    self = .Broken(oldState: self)

    case (.Unlocked, .AdmitPerson):
    self = .Locked(credit: 0)
    return .CloseDoors
    case (.Unlocked, .MachineDidFail):
    self = .Broken(oldState: self)

    case (.Broken, .MachineRepairDidComplete):
    self = .Locked(credit: 0)

    default: break
    // Or should we throw?
    // In a more ideal world, it should be impossible to write code which reaches this line (I discuss
    // how this might be achieved at the very end).
    }

    return nil
    }
    }

    /// Now, an imperative shell that hides the enums and delegates to actuators.
    /// Note that it has no domain knowledge: it just connects object interfaces.
    class TurnstyleController {
    private var currentState = TurnstyleState.initialState
    private let doorHardwareController: DoorHardwareController
    private let speakerController: SpeakerController

    init(doorHardwareController: DoorHardwareController, speakerController: SpeakerController) {
    self.doorHardwareController = doorHardwareController
    self.speakerController = speakerController

    self.doorHardwareController.opticalPersonPassingSensorSignal
    .takeUntilObjectDeallocates(self)
    .subscribeNext { [unowned self] in self.handleEvent(.AdmitPerson) }
    }

    func customerDidInsertCoin(value: Int) {
    self.handleEvent(.InsertCoin(value: value))
    }

    func mechanicDidCompleteRepair() {
    self.handleEvent(.MachineRepairDidComplete)
    }

    private func handleEvent(event: TurnstyleState.Event) {
    switch currentState.handleEvent(event) {
    case .SoundAlarm?:
    self.speakerController.soundTheAlarm()
    case .CloseDoors?:
    self.doorHardwareController.sendControlSignalToCloseDoors()
    case .OpenDoors?:
    self.doorHardwareController.sendControlSignalToOpenDoors()
    case nil:
    break
    }
    }
    }

    protocol DoorHardwareController {
    func sendControlSignalToOpenDoors()
    func sendControlSignalToCloseDoors()

    /// A signal which fires an event whenever the physical door hardware detects a person passing through.
    var opticalPersonPassingSensorSignal: Signal<(), NoError> { get }
    }

    protocol SpeakerController {
    func soundTheAlarm()
    }

    // Stubs to make the errors go away in Playgrounds:
    struct Signal<A, B> {
    func takeUntilObjectDeallocates(o: AnyObject) -> Signal<A, B> { return self }
    func subscribeNext(nextHandler: (A) -> Void) {}
    }
    struct NoError {}
    ```

    ## Hierarchical state machines

    Now, if you have a lot of states, you might want to start grouping them into "child" state machines, especially if there's a significant shared semantic. Here I rephrase the example state machine hierarchically: an inner state machine and an outer one, following figure 6 from "A Pattern Language of Statecharts."
    ![figure 6](figure6.png)

    Critically, *no other types* must change: the code above can use HierarchicalTurnstyleState as a drop-in replacement. StateTypes are closed under hierarchical composition. This is a natural consequence of the data-oriented design, which takes advantage of the simpler fact that enums are closed over carrying instances of other enums as an associated value, and that functions are closed over calling other functions. Nothing more complicated is required.

    ```swift
    enum HierarchicalTurnstyleState: StateType {
    case Functioning(FunctioningTurnstyleState)
    case Broken(oldState: FunctioningTurnstyleState)

    enum Event {
    case InsertCoin(value: Int)
    case AdmitPerson
    case MachineDidFail
    case MachineRepairDidComplete
    }

    typealias Command = FunctioningTurnstyleState.Command // Of course, this could be some more complicated composition.

    static let initialState = HierarchicalTurnstyleState.Functioning(FunctioningTurnstyleState.initialState)

    mutating func handleEvent(event: Event) -> Command? {
    switch (self, event) {
    case (.Functioning(let state), .MachineDidFail):
    self = .Broken(oldState: state)
    case (.Functioning(let state), _) where FunctioningTurnstyleState.Event(event) != nil:
    var newState = state
    let command = newState.handleEvent(FunctioningTurnstyleState.Event(event)!)
    self = .Functioning(newState)
    return command

    case (.Broken(let oldState), .MachineRepairDidComplete):
    self = .Functioning(oldState)

    default:
    break // or maybe throw, etc
    }

    return nil
    }
    }

    // Note that this could be private, or not. It's just as much of a StateType as HierarchicalTurnstyleState.
    enum FunctioningTurnstyleState: StateType {
    case Locked(credit: Int)
    case Unlocked

    enum Event {
    case InsertCoin(value: Int)
    case AdmitPerson
    }

    enum Command {
    case SoundAlarm
    case CloseDoors
    case OpenDoors
    }

    static let initialState = FunctioningTurnstyleState.Locked(credit: 0)
    private static let farePrice = 50

    mutating func handleEvent(event: Event) -> Command? {
    // Now somewhat simpler because the turnstyle can't be broken.
    switch (self, event) {
    case (.Locked(let credit), .InsertCoin(let value)):
    let newCredit = credit + value
    if newCredit >= TurnstyleState.farePrice {
    self = .Unlocked
    return .OpenDoors
    } else {
    self = .Locked(credit: newCredit)
    }
    case (.Locked, .AdmitPerson):
    return .SoundAlarm

    case (.Unlocked, .AdmitPerson):
    self = .Locked(credit: 0)
    return .CloseDoors

    default:
    break // or maybe throw, etc
    }

    return nil
    }
    }

    // Conversion between the layers. You could approach this a variety of ways.
    extension FunctioningTurnstyleState.Event {
    init?(_ event: HierarchicalTurnstyleState.Event) {
    switch event {
    case .InsertCoin(let value):
    self = .InsertCoin(value: value)
    case .AdmitPerson:
    self = .AdmitPerson
    case .MachineDidFail, .MachineRepairDidComplete:
    return nil
    }
    }
    }
    ```

    ## Orthogonal state machines

    The hierarchical state machines introduced above were always alternations: the parent machine is always in a state of one of its child machines. But instead the composition might be a Cartesian product, where the parent runs the child machines simultaneously, and its effective state is a *tuple* of the child states.

    The relationship between this kind of composition (orthogonal) and the earlier kind of composition (alternative) is the same as the relationship between product types (structs, tuples) and sum types (enums), so we see that reflected in the declaration below.

    For instance, a keyboard might have two different state machines running simultaneously: one handles the toggling behavior of the main keypad's caps lock key and its impact on keypad behavior; the other handles the same thing for the numpad and num lock.

    ![keyboard state machine diagram](keyboard.png)

    ```swift
    struct KeyboardState: StateType {
    var mainKeypadState: MainKeypadState
    var numericKeypadState: NumericKeypadState

    enum HardwareKeyEvent {
    // A quick and dirty definition.
    case Alpha(Character)
    case Number(Int)
    case NumLock
    case CapsLock
    }

    static let initialState = KeyboardState(mainKeypadState: MainKeypadState.initialState, numericKeypadState: NumericKeypadState.initialState)

    mutating func handleEvent(event: HardwareKeyEvent) -> KeyboardOutputCommand? {
    if let mainKeypadEvent = MainKeypadState.Event(event) {
    return mainKeypadState.handleEvent(mainKeypadEvent)
    } else if let numericKeypadEvent = NumericKeypadState.Event(event) {
    return numericKeypadState.handleEvent(numericKeypadEvent)
    } else {
    return nil
    }
    }
    }

    enum MainKeypadState: StateType {
    case CapsLockOff
    case CapsLockOn

    enum HardwareKeyEvent {
    case Alpha(Character)
    case CapsLock
    }

    static let initialState = MainKeypadState.CapsLockOff

    mutating func handleEvent(event: HardwareKeyEvent) -> KeyboardOutputCommand? {
    switch (self, event) {
    case (.CapsLockOff, .CapsLock):
    self = .CapsLockOn
    case (.CapsLockOff, .Alpha(let c)):
    return .AlphaNumeric(c)

    case (.CapsLockOn, .CapsLock):
    self = .CapsLockOff
    case (.CapsLockOn, .Alpha(let c)):
    return .AlphaNumeric(c.uppercaseCharacter)
    }

    return nil
    }
    }

    enum NumericKeypadState: StateType {
    case NumLockOff
    case NumLockOn

    enum HardwareKeyEvent {
    case Number(Int)
    case NumLock
    }

    static let initialState = NumericKeypadState.NumLockOn

    mutating func handleEvent(event: HardwareKeyEvent) -> KeyboardOutputCommand? {
    switch (self, event) {
    case (.NumLockOff, .NumLock):
    self = .NumLockOn
    case (.NumLockOff, .Number(let n)):
    if let arrowDirection = ArrowDirection(numericKeypadInput: n) {
    return .Arrow(arrowDirection)
    }

    case (.NumLockOn, .NumLock):
    self = .NumLockOff
    case (.NumLockOn, .Number(let n)):
    return .AlphaNumeric("\(n)".characters.first!)
    }

    return nil
    }
    }

    enum KeyboardOutputCommand {
    case AlphaNumeric(Character)
    case Arrow(ArrowDirection)
    }

    enum ArrowDirection {
    case Up, Down, Left, Right
    }

    extension ArrowDirection {
    // Mapping the numpad keys to arrow keys.
    init?(numericKeypadInput: Int) {
    switch numericKeypadInput {
    case 2: self = .Up
    case 4: self = .Left
    case 6: self = .Right
    case 8: self = .Down
    default: return nil
    }
    }

    }

    // We can various other constructions which might make this kind of glue lighter.
    extension MainKeypadState.HardwareKeyEvent {
    init?(_ hardwareKeyEvent: KeyboardState.HardwareKeyEvent) {
    switch hardwareKeyEvent {
    case .Alpha(let c): self = .Alpha(c)
    case .CapsLock: self = .CapsLock
    case .Number, .NumLock: return nil
    }
    }
    }

    extension NumericKeypadState.HardwareKeyEvent {
    init?(_ hardwareKeyEvent: KeyboardState.HardwareKeyEvent) {
    switch hardwareKeyEvent {
    case .Alpha, .CapsLock: return nil
    case .Number(let n): self = .Number(n)
    case .NumLock: self = .NumLock
    }
    }
    }

    extension Character {
    var uppercaseCharacter: Character {
    return Character(String(self).uppercaseString)
    }
    }
    ```

    Or more generally (but it's ugly and non-idiomatic):

    ```swift
    struct OrthogonalState<StateA: StateType, StateB: StateType>: StateType {
    var stateA: StateA
    var stateB: StateB

    static var initialState: OrthogonalState<StateA, StateB> {
    return OrthogonalState(stateA: StateA.initialState, stateB: StateB.initialState)
    }

    mutating func handleEvent(event: OrthogonalStateEvent<StateA, StateB>) -> OrthogonalStateCommand<StateA, StateB>? {
    // In some orthogonal state machines, certain events will want to be dispatched to both children. We'd need a somewhat more complex structure for that.
    switch event {
    case .A(let event):
    return stateA.handleEvent(event).map(OrthogonalStateCommand.A)
    case .B(let event):
    return stateB.handleEvent(event).map(OrthogonalStateCommand.B)
    }
    }
    }

    // Not allowed to nest types in generic types.
    enum OrthogonalStateEvent<StateA: StateType, StateB: StateType> {
    case A(StateA.Event)
    case B(StateB.Event)
    }

    enum OrthogonalStateCommand<StateA: StateType, StateB: StateType> {
    case A(StateA.Command)
    case B(StateB.Command)
    }

    // But hey, I can now define the same KeyboardState interface as an Adapter on OrthogonalState. Not that this is particularly cleaner, but it does contain less domain knowledge:
    struct KeyboardState2: StateType {
    private typealias OrthogonalStateType = OrthogonalState<MainKeypadState, NumericKeypadState>
    private var orthogonalState: OrthogonalStateType

    enum HardwareKeyEvent {
    // A quick and dirty definition.
    case Alpha(Character)
    case Number(Int)
    case NumLock
    case CapsLock

    private var orthogonalEvent: OrthogonalStateType.Event {
    switch self {
    case .Alpha(let c): return .A(.Alpha(c))
    case .Number(let n): return .B(.Number(n))
    case .NumLock: return .B(.NumLock)
    case .CapsLock: return .A(.CapsLock)
    }
    }
    }

    static let initialState = KeyboardState2(orthogonalState: OrthogonalStateType.initialState)

    mutating func handleEvent(event: HardwareKeyEvent) -> KeyboardOutputCommand? {
    switch orthogonalState.handleEvent(event.orthogonalEvent) {
    case .A(let c)?: return c
    case .B(let c)?: return c
    case nil: return nil
    }
    }
    }
    ```

    ## Alternative approaches, outstanding issues

    ### Functions, not `enum` manipulations

    The use of `enum`s in this pattern is not terribly idiomatic. In a fundamentally imperative language, we usually describe events with methods. Unfortunately, methods aren't as flexible in use-vs-reference as enums, so state machines defined in this way don't compose quite so cleanly.

    Another issue with using functions to specify events is that they make the machine harder to "read" by emphasizing transitions over states. Compare this definition of TurnstyleState to the initial one; I argue it's much harder to picture the boxes-and-diagrams graph. (note that it's impossible to implement `OrthogonalStateType` on top of this structure)

    ```swift
    enum TurnstyleState2 {
    case Locked(credit: Int)
    case Unlocked
    indirect case Broken(oldState: TurnstyleState2)

    enum Command {
    case SoundAlarm
    case CloseDoors
    case OpenDoors
    }

    static let initialState = TurnstyleState2.Locked(credit: 0)
    private static let farePrice = 50

    func insertCoin(value: Int) -> (TurnstyleState2, Command?) {
    switch self {
    case .Locked(let credit):
    let newCredit = credit + value
    if newCredit >= TurnstyleState.farePrice {
    return (.Unlocked, .OpenDoors)
    } else {
    return (.Locked(credit: newCredit), nil)
    }
    case .Unlocked, .Broken:
    return (self, nil)
    }
    }

    func admitPerson() -> (TurnstyleState2, Command?) {
    switch self {
    case .Locked:
    return (self, .SoundAlarm)
    case .Unlocked:
    return (.Locked(credit: 0), .CloseDoors)
    case .Broken:
    return (self, nil)
    }
    }

    func machineDidFail() -> TurnstyleState2 {
    switch self {
    case .Locked, .Unlocked:
    return .Broken(oldState: self)
    case .Broken:
    return self // Or throw?
    }
    }

    func machineRepairDidComplete() -> TurnstyleState2 {
    switch self {
    case .Broken(let oldState):
    return oldState
    case .Locked, .Unlocked:
    return self // Or throw?
    }
    }
    }
    ```

    ### Type-safe state transitions

    All those places where I wrote "or throw?"... can we do better?

    One key issue is that event handlers are fairly indiscriminate. If we're listening to events from some hardware sensor, those events are going to arrive regardless of what our state is, so we have to branch somewhere to decide whether to handle it or not. Right now, we branch in `handleEvent`. If individual states had their own types (only some of which included certain events), we'd just kick the branch up to whatever component dispatches events to states.

    So a rigorous solution must meaningfully affect dispatch of the input events which lead to state changes. One solution (similar to Elm's) would be to allow states to (directly or indirectly) specify which upstream subscriptions are actually active. Those specifications could include enough type information to directly enforce that states only receive events with corresponding transitions.

    I'll save a detailed treatment on this topic for another day.

    ## Acknowledgements

    My thanks to Colin Barrett, Justin Spahr-Summers, Rob Rix, and Chris Eidhoff for useful feedback on this draft.