State machines are a fundamental computer science concept and in many senarios they are the simplest way to implement a process or program. However, most programming languages don't support them natively. Is there a technical limitation to do it? And if not, are there any programming languages that do support state machines in their standard libraries?
$\begingroup$
$\endgroup$
7
4 Answers
$\begingroup$
$\endgroup$
A state machine is basically a loop around a switch case construct, which exists in pretty much almost every language I know in a form or another.
So I'm curious of the one languages you found out that do, according to your wording, implement state machines natively, since to me most of all do so.
$\begingroup$
$\endgroup$
All imperative code is a state machine. The current state is called the program counter or in high-level languages the line number.
It's possible to construct an explicit state machine so that the state corresponds to some variable in your code, and the transitions are specific blocks of code. You can write this yourself, but it's a reasonably common transformation as it allows you to interleave the execution of different pieces of code.
The feature which uses this transformation - the ability to interleave the execution of different pieces of code - is often called "coroutines". C++ coroutines are implemented this way. However, coroutines can also be implemented using stack switching, which does not construct a state machine. Lua coroutines are implemented this way - although since the stack in this case is part of the interpreter state, from the perspective of outside the interpreter you can see them as explicit state machines.
$\begingroup$
$\endgroup$
In a language with Proper Tail Calls, implementing a State Machine is trivial: each state is a subroutine, each transition is a subroutine call, choosing the transition is done using the programming language's builtin feature for conditions (e.g. switch in ECMAScript).
In an OO language (or any other language with dynamic ad-hoc polymorphism) with Proper Tail Calls, we can go one step further and make the message dispatch algorithm implement the choice of transition for us.
In a language with flexible syntax, we can typically get very close to a formal state machine syntax. In a language with programmable syntax, we can not just get close, we can make our syntax identical to a formal state machine syntax.
All of this can generally be done in a few lines of code, without the need of any special language features. It is generally preferred to make languages powerful enough that the programmer can provide their own abstractions, instead of the language designer having to provide the abstractions for the programmer. (This at least applies to general purpose languages. Domain-specific languages are a different beast. In DSLs, restricting the programmer's capabilities is often a good thing.)
Lots of languages actually provide regex as part of the language and/or the library. Regex are supersets of regular expressions, and can thus directly express State Machines operating on character strings.
$\begingroup$
$\endgroup$
Suppose that you have a (finite) list of Boolean values and that you would like to count the number of occurrences of True. This (infinite) state machine's state-transition function is
$$ f (x, u) := \begin{cases} x + 1 & \text{if } u = \texttt{True} \\ x &\text{if } u = \texttt{False} \end{cases} $$
Suppose further that the initial state is $x_0 = 0$ and that the input sequence is
$$[ \texttt{False}, \texttt{True}, \texttt{True}, \texttt{False}, \texttt{True} ]$$
Hence,
$$ 0 \xrightarrow{\texttt{False}} 0 \xrightarrow{\texttt{True}} 1 \xrightarrow{\texttt{True}} 2 \xrightarrow{\texttt{False}} 2 \xrightarrow{\texttt{True}} 3$$
In Haskell,
type State = Integer
type Input = Bool
-- initial state
x0 :: State
x0 = 0
-- state-transition function
f :: State -> Input -> State
f x True = x + 1
f x False = x
-- sequence of inputs
us :: [ Input ]
us = [ False, True, True, False, True ]
-- compute sequence of states
xs :: [ State ]
xs = scanl f x0 us
After having loaded this Haskell script on GHCi,
λ> xs
[0,0,1,2,2,3]
However, if you only want the final state, use (left fold) function foldl instead of (cumulative left fold) function scanl, as follows.
λ> foldl f x0 us
3
foldlandscanl. The way I see it, they exist to simulate finite state machines. $\endgroup$