Francis Cheng: Proper Tail Calls and State Machines

It turns out that Proper Tail Calls (PTC) are handy if you want to create a simple "state machine" or "finite state machine" (See my previous post if you don't know what PTC is). A state machine is a way to create a model for the way an object behaves. For example, let's create a state machine model for a United States traffic light. First I'll use a design pattern to create one, then I'll show you a completely different approach using PTC. Here are the components of the model:

Finite number of states. There are three states in our example: red, yellow, and green.
Input. This is an event-driven model, so the input is an event that signifies a light change.
Finite number of transitions. There are three transitions in our example: red to green, green to yellow, and yellow to red.

There are many different ways to implement a state machine. You can use a series of if/else statements or a switch clause that controls the transitions from state to state, but that approach doesn't scale well. Instead, we'll use the state design pattern, originally presented by Gamma, et. al. in their famous "Design Patterns" book.

Traffic Light Using the State Pattern

First we start with a class that Gamma calls the "context", which in our case is a class I'll call TrafficLight. This class is sort of the "master" class that we'll use to represent the state machine. Second, we'll create an interface, let's call it IState, that contains methods that represent all the behaviors in our state machine. Well, in our case there's only one behavior, which is changeColor(). Third, we'll implement this interface with classes that represent each of our states. We'll have three classes: RedLight, YellowLight, and GreenLight, all of which will implement the IState interface.

For simplicity's sake, I'm just making my variables public and I'm ignoring the need for event listeners and a timer. Also, I'm including only the RedLight class because the YellowLight and GreenLight classes are essentially the same:

TrafficLight Class

public class TrafficLight extends Sprite
{
	public var redLight:IState;
	public var yellowLight:IState;
	public var greenLight:IState;
	
	private var state:IState = redLight;
	
	public function TrafficLight()
	{
		redLight = new RedLight(this);
		yellowLight = new YellowLight(this);
		greenLight = new GreenLight(this);

	}
	
	public function changeColor(newState:IState):void
	{
		state = newState;
	}
}

IState Interface

public interface IState
{
	function changeColor():void;
}

RedLight Class

public class RedLight implements IState
{
	private var _light:TrafficLight;
	
	public function RedLight(light:TrafficLight) {
		_light = light;
	}
	
	public function changeColor() :void	{
		_light.changeColor(_light.greenLight);
	}
}

That's a lot of structure for a simple model, but the payoff is that you have a model that's easy to extend. For example, we could easily adapt this state machine to handle British traffic lights that have an extra state where red and yellow both appear. All it would take is a new RedYellowLight class and minor changes to the TrafficLight and RedLight classes. Now let's take a different approach that uses PTC.

Traffic Light with PTC

When I mean different, I mean that we'll leave the nicely structured world of class-based programming and enter the wild world of dynamic programming. So turn off Strict mode and let's not worry about type annotations. If we have PTC at our disposal, we can use it to design a quick and easy state machine that uses a function to represent each state. It can't get much simpler than that. When it is time to transition to a new state we make a tail call to the appropriate function.

var cycles = 250;

function redLight () {
	trace("RED");
	cycles--;
	if (cycles == 0) {
		return;
	}
	return greenLight();
}

function yellowLight() {
	trace("YELLOW");
	return redLight();
}

function greenLight() {
	trace("GREEN");
	return yellowLight();
}

redLight();

I added a variable named cycles to control the number of times the program runs. What's interesting is that if I set cycles to anything over 252, I get a stack overflow error. I'm only decrementing in the redLight function, so that means each decrement of cycles represents three functions placed on the stack. So the error appears after a little more 750 of those functions are placed onto the stack. Clearly, you wouldn't want to use this technique in ActionScript today, but if PTC becomes part of ActionScript, the stack overflow error would not occur because each tail call function would replace the preceding call on the stack. Of course, this is not necessarily a better way to implement a state machine, but it is an alternative that certainly has an appealing simplicity to it. It may not scale as well as the design pattern technique, but may come in handy for implementing simple games.

Here are some links to resources about state machines:

6.3 Proper Tail Calls, from Programming in Lua, by Roberto Ierusalimschy
Finite State Machines in JavaScript, by Edward J. Pring
Finite State Machine, Wikipedia Article
Finite State Machines for AI in ActionScript
Creating a video player using the state design pattern and ActionScript 3.0, by Bill Sanders.

Francis Cheng

ActionScript, ECMAScript and the Flash Platform

Proper Tail Calls and State Machines

Traffic Light Using the State Pattern

Traffic Light with PTC

Post a comment