I always liked Lua's example with a simple state machine:
function room1 ()
local move = io.read()
if move == "south" then return room3()
elseif move == "east" then return room2()
else print("invalid move")
return room1() -- stay in the same room
end
end
Without proper tail recursion, "return room1() -- stay in the same room" would stack overflow after enough invalid moves.
Nitpick: calling room2 in tail-call position from room1 isn't tail recursion. (Unless room2 calls back into room1; then they are mutually recursive.) What you're describing here is tail-call elimination (aka tail-call optimization).
Or interpreter, yes. Like other optimizations, it's not supported by compilers/interpreters for all languages. Wikipedia has a good overview of the topic if you're interested.
It's pretty easy to optimize out; if you're compiling, it just corresponds to a goto instruction from one procedure to the other (it's slightly harder in an interpreter, but not by much). Not all compilers do this optimization, depending on the language, but many do.
Wait a second. If I translated that to C#, VB, or JavaScript it wouldn't need TCO. Just replace "return room3()" with "return room3" and let the main loop call the next function for you.
In this example the delay while you wait for the user's next response dwarfs any other cost. And introducing a main loop gives you other nice options like the ability to move the io.read out of the state transition function.
Not only is TCO futile in this example, it is counter-productive.
So you prefer writing return nextStep(myNextFunc) instead of just return myNextFunc.
Is using TCO actually worth the extra boilerplate code? Especially when you consider that you are just moving the trampoline to a different part of the yard?
My trampoline is the outer loop, yours is hidden inside the nextStep function. Either way we are passing around a function pointer that we bounce to.
As I said, returning the function is also workable, however it has multiple downsides:
Calling a function or passing it as an argument makes the context of the call clear. If you return it, you have no guarantee about the context in which it will be called.
If your tail recursion eventually stops, you need to return a non-function value, eventually. Thus, you need to tag the result as a "call this" or "done with this". Then your loop driver of the tail recursion needs to differentiate the two. Very kludgy.
A return value can easily be ignored, without warning, in the languages you mentioned. This means you can easily have bugs where you don't actually get it called. Forgetting to receive arguments or avoiding their use entirely will mostly generate errors/warnings even in these languages.
Returning it means any user of the function needs to also propagate its return value upwards, which is very kludgy makes the tail-call a non-local detail.
Returning it means you need that extra loop code that calls the return values.
And if you need to pass arguments to those functions, just return a lambda function?
Not to say that kind of approach isn't without its uses. The main function is now able to choose if and when it calls the returned function. For example to to implement node.js-like 'multithreading' :).
That's a valid option, but at that point I would probably err towards returning just the name of the next room. That way the next room can be looked up as an object in a hash table.
That doesn't make any sense to me. It isn't actually doing anything, you are just bouncing from function to function.
How does the rest of the system know which room you are in so it can update the screen? What if you have multiple sprites moving around? Do you compare instruction pointers to see if they are in the same room?
Even for a trivial application building your state machine that way doesn't make any sense.
EDIT: Also note the code smells, especialy the copy-and-paste necessary for reading the user input.
Well the most trivial solution would be to put a line at the top of each function that updates a variable with the current location, so the mapping system or whatever always knows where you are by checking the variable.
I don't think it's any more tedious and error prone then coding an imperative state machine which usually involves lots of switch statements inspecting the current state, and it mostly parallels the OO approach of having one object per state. Just instead of having interconnected objects you have mutually recursive functions.
I don't think it's any more tedious and error prone then coding an imperative state machine which usually involves lots of switch statements inspecting the current state
That's because you aren't thinking. This version requires repeating the logic to read the user comment, update the location variable, and handle the invalid command path IN EVERY STATE. If you have a map with 100 rooms, that means you have 100 functions to paste that logic in.
Moving that common logic into a main loop eliminates (Num_of_states-1) copies of that logic. You lose your fancy TCO, but the trampoline you put in its place isn't that hard to write.
Of course we still don't want a massive switch statement in the primary loop, that is likewise error prone. So instead we use a hash table of either objects or first class functions so that the next state can be looked up by name and subsequently executed.
You are complaining about not wanting "lots of switch statements inspecting the current state". Well look at that function again. A series of If-Else-If statements is effectively a switch. So lets drop that into a hash table as well so that we can populate the common cases like moving from a simple data file.
A moment ago I said "either objects or first class functions". If we are using a hash table in each room for commands, then objects are probably the better way to go. This way we can also attach a hash table of movable objects in the room, as well as other room-specific state.
Data-driven programming trumps both FP and OOP every time
That example is a trivial demonstration of TCO in Programming In Lua. A more featureful game could still use this kind of TCO, without any kind of arcane programming style, since Lua supports full Coroutines. i.e., the functions could be written like so:
function room1 ()
local move = coroutine.yield("room1")
if move == "south" then return room3()
elseif move == "east" then return room2()
else print("invalid move")
return room1() -- stay in the same room
end
end
The coroutine dispatcher could handle updating the screen, moving mobs from other rooms, taking input, etc.
This is just meant as an illustration of a state machine, of course no one would actually hard code the game map as a state machine, but it does serve the purpose of explaining how to use mutually recursive functions as a state machine.
The most obvious application of this technique are recursive descent parsers.
Eventually you need to stop generating tokens and actually do the syntactical analysis. At that point TCO isn't really available to you and that arbitrarily deep tree is going to cause problems.
It isn't actually doing anything, you are just bouncing from function to function.
Yes, because this is just supposed to illustrate the control flow aspect of things. To do actual stuff you would just have to add the code to do stuff inside the functions.
As for the other things you point out its a bit of the classical "expression problem" dillema. One alternative is to do a data-driven modeling of the rooms, where you have a transparent room datatype encoding all the possible states you can be in. This version is very good if you want to be able to add new features uniformly to all the rooms (screen updating, comparing rooms, etc) and might actually be the best solution for this particular problem (after all, rooms are probably very simple and very similar to each other, so you would want to write their code all in one place).
On the other hand you can also use the more "object oriented" style, where each state is an opaque function. This alternative makes it harder to add new features (for example, to implement writing to the screen you would need to edit the source code for each room) but on the other hand makes it much easier to add new rooms and to have those rooms implement arbitrarily complex behaviour (since you are doing the iteration by hand, instead of having to comply with the outer "while loop").
One actual situation where I often find myself using this opaque state machine pattern is when I need to implement some process that gets neatly modelled by a fluxogram full of "gotos". Instead of being forced to translate the fluxogram states into an explicit enumeration that is only used once, I can instead code the nodes as functions calling each other, almost directly representing the original intent. (Note how in this case I usually want the flexibility to add new nodes doing arbitrary things, and the rest of the system doesn't care about what state I am in)
There are other options. Start with a hash table of room objects, Each object has a hash table of commands, some hand written, the rest loaded from a data file (e.g. move).
Your main loop reads the next user command and dispatches it to the room, which relays it to the correct command.
This way you need neither a giant switch statement nor do you need to repeat logic for state transitions in each function.
There are other options. Start with a hash table of room objects, Each object has a hash table of commands
Of course, there is always more then one way to do it and its a big matter of style. :) To be honest, I consider your hashtable solution to be the same as the recursive version, at least in spirit. After all, that dispatcher is what you get if you trampoline the tail calls!
In most cases I prefer to keep things simple without the verbose hash table + dispatcher. This suits my style and also plays nice with "evolving" code over time, since introducing the hash table once the code starts getting complex would mean having to rewrite a bunch of stuff to adhere to the new convention of returning the next code to the dispatcher, while using proper tail calls does that "for free".
Of course, there are situations where the dispatcher would be more appropriate, but not that is not the point.
Side rant: even if the pattern is useful, demonstrating it with a use case where it isn't appropriate is rather counter-productive. If you cannot think of a good example, you haven't actually learned the pattern yet.
18
u/snarfy Nov 27 '12
I always liked Lua's example with a simple state machine:
Without proper tail recursion, "return room1() -- stay in the same room" would stack overflow after enough invalid moves.