Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A composable pattern for pure state machines with effects (draft v3)

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, 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, 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, meant to be idiomatic in a typical imperative context. The pure-impure separation is inspired by functional core, imperative shell; the modeling of novelty and effect by Elm; the hierarchical composition by Harel statecharts.

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

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).

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 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 OutputCommand

	/// In response to an event, a state may transition to some new value, and it may emit a 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*, 
	// 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 OutputCommand (it just creates some
	// line noise later):
	//   func handleEvent(event: InputEvent) -> (Self, OutputCommand)

	/// 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, figure 3:

Drawing of a simple turnstyle state machine, implemented below

/// 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

	// 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)):
			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 }
	
	// 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 {
	func soundTheAlarm()
}

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

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.

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.

Drawing of a keyboard's state machine, separating caps lock and num lock functionality

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.HardwareKeyEvent(event) {
			return mainKeypadState.handleEvent(mainKeypadEvent)
		} else if let numericKeypadEvent = NumericKeypadState.HardwareKeyEvent(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):

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 enums 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)

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, 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.

Hi @andymatuschak,

Great post! There are a lot of similar ideas that can be found in some functional programming literature. I'll sketch a few ideas here -- feel free to follow up if you have any questions.

The simplest command-response interactions can be described, like you do, by a pair of types:

Command : Type
Response : Command -> Type

That is, a type Command (similar to your event) and a function that computes the possible responses to a given command. This description allows you to be a bit more precise about the possible responses for any particular command -- this can help rule out the 'bogus' branches in the handleEvent function.

Given such a structure, you can form a 'free monad' (using some pseudo-Haskell notation):

data Free a where
MkFree : (c : Command) -> (Response c -> Free a) -> Free a
Return : a -> Free a

This is an abstract syntax tree, capturing all possible command-response interactions. You can easily mock/test/inspect such trees; or alternatively, run them by associating some I/O actions with the commands.

This command-response structure is closed under just about anything you could wish for (products, coproducts, composition of the underlying functors, etc.) The 'free monads' have an obvious bind and return.

This simple description doesn't account for state (and in particular, for the situation where certain commands only make sense in a specific state). There's a very pretty account that can handle this -- but it relies on having 'real' dependent types and is harder to write in Haskell/Swift. Check out Peter Hancock & Anton Setzer's work on interaction structures if you want to know more.

This was an interesting read. Thanks for sharing.

Owner

andymatuschak commented Jul 29, 2016

Thank you, @wouter-swierstra! I'm definitely familiar with (and influenced by!) the functional solutions to these problems. My primary goal here is to get the benefits of those solutions in a way that still feels idiomatic in traditional imperative languages.

One note on your formalism, though: doesn't a state machine need to be arrowized? The handling of an event depends not only on the data in the event itself but also on the data describing the "source" state, yeah?

hsavit1 commented Jul 29, 2016

the state machine is the most underrated design pattern in mobile development. thanks for sharing and formalizing this

chucks commented Jul 30, 2016

@andymatuschak, thank you for publishing this! I definitely want to try out some of these concepts. I've been through a few different state machine abstractions in ObjC and C++, and none of them really "fit" my mental model of how I wanted to organize things, and also there were downsides to testing. (Strangely, the last state machine lib I really liked was all in C and was terrible brew of macros and setjmp/longjmp, but in practice there was a nice correspondence between the state diagram and the code one implemented. At that time, testability and composition weren't as much on my radar either :) )

I also very much like how the core concept, the StateType protocol, seems to be both "simple" and "easy".

Thanks for sharing this :)

I'm not clear on where the side effects are handled. If we assume that InsertCoin needs to make an HTTP request to validate the currency of the coin, where does that live? Is handleEvent mutating the state AND handling side effects?

stepanhruda commented Aug 2, 2016

To understand the tradeoffs better, I did a little exercise to remove the invalid state/action combinations using types. It moves it even further away from being a state machine, but someone might appreciate this for reference.

https://gist.github.com/stepanhruda/77c62dfdeb821f597f7ccf14f1042be3

Owner

andymatuschak commented Aug 3, 2016

@danielepolencic: The side effects are handled in the client of the state machine value type. See TurnstyleController for instance.

@stepanhruda: Right! The tricky bit comes in implementing the next layer out: try writing the TurnstyleController for this phrasing of the states.

@adamnemecek: While scan is certainly a very expressive data transform, it has a Turing tarpit element to it: most of the time you don't actually want/need to express your ideas at that level of abstraction! Expressing an idea via scan which can be expressed through a simpler transform puts fewer constraints on the transformation, which makes it harder to read and reason about…

nikki93 commented Aug 4, 2016

@andymatuschak: I like the composition idea, and one question that comes up there is, when you proceed from the root of the state ontology downward, when do things stop being states and start being primitives? For example, in a video game world, you'd have an array of physical objects, say a Player and a Monster being one of them. You'd want to (forgive my syntax, I don't do much Swift, so it'll be pseudocodey) o.handleEvent(TickEvent(dt: <time elapsed>)) or something, which is nice because maybe the World parent-state-object that contains these objects is actually agnostic of their actual type, which achieves a mix of OO-style polymorphism while keeping functional non-mutating ideas (if o.handleEvent(...) just returns a new o, then the parent state object can update its member). Do we recurse the state-ness of our ontology one level deeper and also do it for the Vec2 that is the Player's position?

And another thing being, what if the state at some level of ontology depends on sibling nodes in the ontology in its next-state computation? For example, Monster wants to know the Player's position, if one exists, to walk toward (in our game monsters stalk the player), in its handling of the tick event. Then some times we want to do things like multiple dispatch on collide events, where a Bomb-Player collision occurs differently from a Bomb-Monster collision and so on.

These considerations point toward some things that I think are actually accidental complexity, such as the state-primitive divide (seems everything downward should just be statey), and the first-parameter-polymorphism divide (seems state-types shouldn't own their functions but functions be free and polymorph on any argument or argument-combo, since why are argumentlists different from simply receiving a tuple containing the arguments?).

I think the most interesting aspect of your take on this, for me, is the .handleEvent(...) potentially polymorphing on its state type and parent state types in the composition using that to their advantage to avoid information leaking upward--playing to OO's strengths in a functional world. The 'client handles side effects' element of it is, to me, similar to things like redux-saga, if you consider your redux store to be the toplevel state object and the reducer-composition its .handleEvent(...) method.

In general I am a fan of bringing OO-style polymorphism to functional scan-style statemachines, one idea I've been toying with recently is to remove the class-instance divide (since when do things stop being classes and start being instances of them? check out Smalltalk's metaclass explosion) and use prototype inheritance for the polymorphism and have the prototypes also be in the state themselves. And yes, the parent-pointing edges would be in the state too. This way the world can edit itself, and you can start going toward a live-coding / worldbuilding situation... This sort of thing also I think can start giving us ways to tackle the Expression Problem (http://c2.com/cgi/wiki?ExpressionProblem) which IMO neither sum-type plus case-match style polymorphism (from functional programming) nor inherit-then-override style polymorphism (from OO) give a clean solution for.

itamarst commented Aug 4, 2016

This reminds me a lot of https://github.com/ClusterHQ/machinist; trying to figure out where it differs. I guess Machinist hardcodes what output(==command) and state you get on any particular pair of current state and input. And in Machinist there's no state tracking of e.g. credits, you have to do that on the outside of the state machine. Possibly an easy extension.

jarsen commented Aug 5, 2016

Very fun. I've been working on trying to write an iOS app using a more elm-like architecture. Glad to see someone else's approach. For example, I went with a non-mutating function to update state from events, but after reading your comments on the subject I think I'm convinced to make it mutating.

Have you looked at (and what do you think of) something like (the Redux inspired) ReSwift? I've been using it for work projects and it's been working very well for us.

The main mental block I run into as I'm trying to translate as much of the elm architecture as I can is dealing with UIKit. Navigation, view controllers, etc. How do you deal with the friction between these?

Owner

andymatuschak commented Aug 6, 2016

@nikki93:

when do things stop being states and start being primitives?

This is a great question. In Elm, this pattern is taken to the extreme, and all data is represented in systems like the one I show here.

what if the state at some level of ontology depends on sibling nodes in the ontology in its next-state computation? For example, Monster wants to know the Player's position, if one exists, to walk toward (in our game monsters stalk the player), in its handling of the tick event.

I'd model this by including the associated data in the Monster's tick event. The parent of the Monster and Player states (itself a Cartesian product) would have visibility into both and could construct the event accordingly.

Then some times we want to do things like multiple dispatch on collide events

Yeah, I mention that in my definition of OrthogonalStateMachine. This can already be modeled by the primitives I describe: the parent state is free to dispatch to children as it pleases. One could even define a protocol like DOM event bubbling by creating a more restrictive child of the StateType protocol which includes a method specifying desired event propagation behavior.

I think the most interesting aspect of your take on this, for me, is the .handleEvent(...) potentially polymorphing on its state type and parent state types in the composition using that to their advantage to avoid information leaking upward--playing to OO's strengths in a functional world.

That's a very interesting idea!

This sort of thing also I think can start giving us ways to tackle the Expression Problem

Indeed, my solution fails there: both the set of events and the set of states are closed. This is nice insofar as it makes totality easy to prove but certainly harms expressivity.

@itamarst:

I hadn't seen Machinist—thank you for sharing! It captures many of the same design goals I sought. The one remaining distinction I observe is that Machinist's state machine descriptions are not closed under any kind of composition: you can't form hierarchical transition tables.

PS: It's been a long time since I've seen an Isometric avatar in the wild! I miss those comics. This one used to be mine back in the day…

Owner

andymatuschak commented Aug 6, 2016

@jarsen:

I support Redux's design philosophy. The key challenge with these frameworks, as you ascertain, is in making them work reasonably with UIKit. I tend to achieve this by writing data-driven facades on UIKit classes, but it's annoying enough that I often give up and am forced to return to the buzzing confusion of traditional stateful imperative approaches. This has much to do with why I no longer enjoy writing software for Apple's platforms… :)

From a Swift API design perspective, ReSwift doesn't express the architecture as idiomatically as I might like. I think I see a number of opportunities to make this API surface feel more at home in Swift… but I'll keep my mouth shut there until I actually try them out. :)

AquaGeek commented Aug 11, 2016

@andymatuschak (and everyone else involved), thanks for sharing this!

What's the license?

Owner

andymatuschak commented Aug 17, 2016

@AquaGeek: Good question. This publication is licensed under a Creative Commons Attribution 4.0 International License.

Owner

andymatuschak commented Nov 9, 2016

I've gotten a couple requests, so: the source in this publication is also available under the MIT License.

Copyright (c) 2016 Andy Matuschak

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment