3
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ There isn't really much to implement for a state machine $\endgroup$
    – gnasher729
    Nov 1 '21 at 20:07
  • 3
    $\begingroup$ In a programming language that supports mutable state (Jave, C/C++, Python, ...) the program itself is a kind of state machine. The state is the state of its variables, and the transitions are described by the program itself. So we do not really need a separate library, just good support to define datatypes that directly represent states (so that we do not need to encode them with something silly, such as strings or integers). $\endgroup$ Nov 1 '21 at 20:16
  • 2
    $\begingroup$ I am assuming you are studying CS, or have studied. Please be careful with assuming all formal concepts around computing being taught in CS is directly useful in programming, they are not. They are however useful gadgets for making proofs. A professor I once took some courses under, and who was fond of pop culture quotes, offered me the following wisdom when I asked him about some issues I had with implementing RegExp using state machines; he sighed and said "Stop trying to hit me, and just hit me", meaning stop trying to simulate the solution to your problem, and just compute it directly. $\endgroup$
    – soren-n
    Nov 2 '21 at 1:33
  • $\begingroup$ @AndrejBauer I am surprised you haven't mentioned Haskell's foldl and scanl. The way I see it, they exist to simulate finite state machines. $\endgroup$ Nov 4 '21 at 13:59
  • $\begingroup$ @RodrigodeAzevedo: you make a good point. Notice that I was talking about how mutable state is essentially an automaton, so it doesn't make so much sense to mention folds in that context. But you're always free to make your own comment or answer, in which you explain how state machines are manifested in declarative programming. $\endgroup$ Nov 4 '21 at 15:45
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.