Object-Oriented Design – Can It Be Seen as a Finite State Machine?

finite-state machineobject-oriented

This might be a philosophical/fundamental question, but I just want to clarify it.

In my understanding a Finite State Machine is a way of modeling a system in which the system's output will not only depend on the current inputs, but also the current state of the system. Additionally, as the name suggests it, a finite state machine can be segmented in a finite N number of states with its respective state and behavior.

If this is correct, shouldn't every single object with data and function members be a state in our object oriented model, making any object oriented design a finite state machine?

If that is not the interpretation of a FSM in object design, what exactly people mean when they implement a FSM in software? am I missing something?

Thanks

Best Answer

Any single-threaded program running on a machine with a finite amount of storage can be modelled as a finite state machine. A particular state in the finite state machine will represent the specific values of all relevant storage—local variables, global variables, heap storage, data currently swapped out in virtual memory, even the content of relevant files. In other words, there will be a lot of states in that finite state model, even for quite trivial programs.

Even if the only state your program has is a single global variable of a 32-bit integer type, that implies at least 2^32 (more than 4 billion) states. And that's not even taking into account the program counter and call stack.

A push-down automaton model is more realistic for this kind of thing. It's like a finite automaton, but has a built-in concept of a stack. It's not really a call-stack as in most programming languages, though.

There's a Wikipedia explanation, but don't get bogged down in the formal definition section.

Push-down automata are used to model general computations. Turing machines are similar~~, but IIRC not identical — though their computation capabilities are equivalent~~.

Thankyou to kevin cline for pointing out the error above - as Wikipedia also points out, push-down automata are more powerful than finite state machines, but less powerful than Turing machines.

I honestly don't know where this brain fart came from - I do know that context sensitive grammars are more powerful than context free, and that context sensitive grammars can't be parsed using a simple push-down automaton. I even know that while it's possible to parse any unambiguous context-free grammar in linear time, it generally takes more than a (deterministic) push-down automaton to do that. So how I could end up believing a push-down automaton is equivalent to a Turing machine is bizarre.

Maybe I was thinking of a push-down automaton with some extra machinery added, but that would be like counting a finite automaton as equivalent to a push-down automaton (just add and exploit a stack).

Push-down automata are important in parsing. I'm familiar enough with them in that context, but I have never really studied them as computer-science models of computation, so I can't give much more detail than I already have.

It is possible to model a single OOP object as finite state machine. The state of the machine will be determined by the states of all member variables. Normally, you'd only count the valid states between (not during) method calls. Again, you'll generally have a lot of states to worry about—it's something you might use as a theoretical model, but you wouldn't want to enumerate all those states, except maybe in a trivial case.

It is fairly common, though, to model some aspect of the state of an object using a finite state machine. A common case is AI for game objects.

This is also what's typically done when defining a parser using a push-down automaton model. Although there are a finite set of states in a state model, this only models part of the state of the parser—additional information is stored in extra variables alongside that state. This solves e.g. the 4-billion-states-for-one-integer issue—don't enumerate all those states, just include the integer variable. In a sense it's still part of the push-down automaton state, but it's a much more manageable approach than in effect drawing 4 billion state bubbles on a diagram.

Related Solutions

Finite-State Machine – How to Recover from FSM Breakdown

I am sure you already know this but just in case:

Make sure every node in the state diagram has an outgoing arc for EVERY legal kind of input (or divide the inputs into classes, with one outbound arc for each class of input).

Every example I have seen of a state machine uses only one outbound arc for ANY erroneous input.

If there is no definite answer as to what an input will do every time, it is either an error condition, or there is another input that is missing (that should consistently result an arc for the inputs going to a new node).

If a node doesn't have an arc for one type of input, then that is an assumption the input will never occur in real life (this is a potential error condition that would not be handled by the state machine).
Make sure the state machine can only take or follow only ONE arc in response to the input received (not more than one arc).

If there are different kinds of error scenarios, or kinds of inputs that cannot be identified at state machine design time, the error scenarios and unknown inputs should arc to a state with a completely separate path separate from the "normal arcs".

I.E. if an error or unknown is received in any "known" state, then the arcs followed as a result of the error-handling/unknown input should Not go back into any states the machine would be in if it only received known inputs.
Once you reach a terminal (end) state you shouldn't be able to return to a non-terminal only to the one starting (initial) state.
For one state machine there should not be more than one starting or initial state (based on the examples I've seen).
Based on what I have seen one state machine can only represent the state of one problem or scenario.
There should never be multiple possible states at one time in one state diagram.
If I see the potential for multiple concurrent states this tells me I need to split the state diagram up into 2 or more separate state machines that have the potential each state to be independently modified.

C# – Dependency injection with Finite State Machines and the Interface Segregation Principle

It seems to me that you want to genericize the Head First example, so that it can accept an arbitrary collection of actions.

In C# you can have first-class functions, which means that you can pass functions to your finite state machine and have it maintain those functions in a list. Something like:

interface IState
{
    void AddStep(Action<T> action);
}

And then just pass your function to the AddStep method for insertion into the list by the state machine.

public class StateMachine : IState
{
    List<Action<T>> actions;

    public void AddStep(Action<T> action)
    {
        actions.Add(action);
    }
}

Then you just add your actions.

var machine = new StateMachine();
machine.AddStep(x => Console.WriteLine(x.ToString()));

Best Answer

Related Solutions

Finite-State Machine – How to Recover from FSM Breakdown

C# – Dependency injection with Finite State Machines and the Interface Segregation Principle

Related Topic