especially state machines and how they are handled in Ireland and also from a theoretical
point of view. So, it's up to you. Thank you.
All right. Yes, he said, like, I'm relatively young but I know a school guy, so I code in
V-man and use Ireland. So, this went too fast already. I work in Erlang Solutions. We do
like Erlang stuff, so concurrency, scalability, the useful things that most of you would be
hopefully familiar and we also contribute a lot to open source. This talk is going to
be about state machines, as you heard. First, a question of protocols. What are protocols?
I wanted to make a survey and ask you and so on, but we have limited time, so I'm going
to answer the question already. System of rules. A few examples. Okay, I need to point
here for this to work. Protocol defines the system of rules for syntax, semantics of the
project, the program that you want to write. Some examples, the usual ones are TCP for
network communication, is connection oriented, stream oriented, messages are ordered and
they are acknowledged. Another common example, TLS for privacy, integrity and authenticity,
encryption, very important. I hope that everybody has HTTPS enabling the browsers by default.
Some other examples are file formats or markup languages. Parsers for them can also be implemented
as state machines. The two classic examples, XML and JSON. XML is particularly interesting
to me because I work in XMPP messaging server written in Erlang, of course. If you saw our
talk in CodeBeam, for those that are following CodeBeam, Pablo and me, we talked about the
state machine re-implementation in Mongo's IM. This is a bit of a continuation to that.
Some more complex protocols can be implemented as state machines like HTTP and as I mentioned,
XMPP, which is my specialty, which is extensible, that's the X and my favorite part of the whole
thing, it's an instant messaging protocol that also has presences, the green bubble,
whether your friend is connected or not and it also does contact list maintenance on the
core protocol, 500 extensions and build your own. This is the state machine diagram for
the protocol. Much like a flow chart on steroids, I really like that analogy. With the state
machines, we are like the usual thing, how you think about state machines, you draw the
state with some arrows, the arrows have tags about how you transition to the next state.
Finest state machines give you a way to visualize a system that can be very complex.
Why state machines? State machines can be seen as a model. We want to model the behavior of
protocol that can be very complex like TLS or HTTP, most of you will be familiar, XMPP,
my specialty. Let's talk a little bit quickly about state machines in particular. A few
formalities. I studied mathematics in university, I'm excited by these weird symbols, but some
people can find them off-putting, so I will try to make it pleasant. A few terminologies,
we define an alphabet, terminologies, you use Greek symbols, mathematicians, which are the
input symbols, zeros and ones, or ASCII characters, UTF-8, or complex symbols treated as a single
element, half, and you can do equivalences. One of the weakest ones is the regular grammars,
it's how you do regexes. A regex, this thing that right ones are never read, but very powerful,
is theoretically equivalent to a state machine. Again, this is jumping too fast. Something a
little bit more powerful is the partial automata, I'm not going to focus on this one too much,
use a key difference, then nothing else parsed, now it has one more thing, it's the same thing
before, plus a stack, and the stack behaves as you would expect. The function that used to take
the state and the input symbol also takes the stack and the output of the function is whether
you pop something from the stack or you push something on the stack. It's safe to consume a
string that you give to this PDA as it arrives to one of the final states with an empty stack.
There are equivalent definitions, not all definitions require the empty stack, but I choose
that one. They are equivalent to context-free grammars, parsers, but not compilers. Why a compiler?
So in tree, the thing about being context-free is that it doesn't remember symbols that were
defined before. So for a compiler, for example, the usual regex compiler for C that needs to remember
the definition when you say int e and then you use e later below, parser doesn't remember that,
you need symbol tables, parser only builds the syntax tree. And the fancy one, the computer,
theoretically, Turing machines, which is again the same thing, but nothing else is supplanted by a
tape that is infinite. It is equivalent whether it's finite in one side and infinite in the other,
all of those are equivalents, whether it has two tapes is also equivalent, will arrive to that.
The function takes the tape and the action go one to the left and write something, go one to the
right and write something. Very similar, a Turing machine is said to consume a string
when the next step is undefined. When it holds, you have all heard of the holding problem.
There is no way to know whether a Turing machine will hold. That is important. They are equivalent
to interested grammars, compilers in the Chomsky hierarchy that are like four levels.
The three things that I describe are zero, one and four, there is something in the level three
that is not directly useful for the moment. So I skip that. So how do they compare? This goes very
fast sometimes. So that's the power that they have. A Turing machine can do all the others.
PDA can do the one over there. So that's the power that they can do. They contain the power of each
other. Two FSMs running together has still the same theoretical power, the same thing that a PDA
with a finite buffer or a PDA with a finite state machine is still as powerful as one PDA.
Turing machines, whether it's multi-tape, tape one banded on one side, they are all equivalent
again. A Turing machine doesn't get more powerful by giving it 100 tapes. It gets maybe more
performant theoretically, but the problems that it can solve are all the same. And a PDA with two
stacks is really a Turing machine when you know you can just go in both directions. So when you
give the PDA two stacks, you build a Turing machine. So conceptually, finite state machines can keep
track of one thing, the state. The push-down automata can keep track of two things, the state and the
top of the stack. And a Turing machine can keep track of infinite things. When I was going through
the mathematics and I came to this conclusion, I found this funny for a completely unrelated reason.
In the European languages, I mean to human languages,
used to have the concept of dual as something different to singular and plural.
The function that it computes depends on one thing to things or an infinite number of them.
The function that was defined before. So in the European languages, as I said,
they had this special concept of the dual. And I found it very funny how informal human languages
used to have such a thing as a dual, as a different grammatical category than one and infinite.
When you build the declinations, they had a different thing. Why do I know this strange thing
about languages? Because I live in Poland. So Slavic languages have some remnants of that
dual concept. So there is this famous joke of in Polish you have like 100 ways to
declinate number two. And you have more ways to declinate number two than you have number three
because of that all dual. So two is special. I live in Poland, but I'm not Polish. It's challenging.
So do FSMs produce output? Let's go move slowly to what is useful here.
We can define finite state transducers, which same thing than before and then nothing else is
supplanted by another output alphabet. The function takes the state and the input and decides the
next state and a symbol for the output. It's a to consume a string the same and they are also
equivalent to regular grammars. When it comes to the problems they can solve, again, they're all
equivalent. You get fancier tools, but there are properties that are going to be all the same.
You will see in a second there are many, but let's focus on two ways of defining transducers,
the milley machines and Moore machines, whether the output, I have a laser, yes, whether the output
symbol depends on the input and the previous state or only on the previous state. There is a way to
define Moore machines from a milley machine, but not the other way around, so milley has a
bit more powerful. Now something a bit more useful, how do they compare? They are still
the same than the FSM machines, but this can be composed. We are getting into a bit of engineering.
We are almost there. Not that much. This is a thing, laser. Yes, oh god. Come on,
sometimes. So given three sets of states, three alphabets, one machine goes from one state and
one alphabet to the next state and the other alphabet. The second machine uses the same
the output of the previous as its input, so you can define the composition as a state machine
that takes the first alphabet and the first set of inputs and gives you the third alphabet and set
of inputs. Composition, cool. Why? Because you can implement all these things as state machines and
the output of one is the input of the next. So my stack on XMPP, you can implement TCP as a state
machine. Have you heard of the Erlang socket, the new socket? It's implemented in TCP on top of
gain state them. If you go to the source code. So I have the output of one state them, throwing
into the output of the next state them. TLS is also implemented as a gain state them,
throwing output to my thing, to the XML parser that throws its output to the XMPP protocol.
So we are composing things. One last theoretical thing. The unions of FSMs that is
uniting all the states and strings, it's also an FSM intersection, so the states and its input
symbols in common gives you a very small FSM. It's also an FSM reversing, still an FSM,
empty, so no states and no input is also an FSM that when you do union and concatenation with
another FSM does nothing and homomorphism, so a function that transforms alphabets and
states into other alphabets and states preserves the structure of an FSM. So FSMs are a semi-ring.
This is an algebraic structure. Why is it useful to have search algebras? To prove things
that you cannot prove with Turing machines because they do not form an algebra.
So now let's do something engineering, state them. So as I said before, it's a Melly machine.
It gets the input and the alphabets, it produces the states and alphabets, it produces the next,
you follow, I hope. We can consider that the input are the messages in the mailbox and the output
symbols are side effects, like for example sending messages to another mailbox.
Gain state them. I'm a big fan. I love it, but I know that people sometimes don't use it because
maybe it's confusing or I don't know, complicated. So I'm going to try to explain one thing that is
very useful here. An extended mailbox. This is a discussion that the OTP team, when they put the
pull request for gain state them, there is a big discussion with over a thousand messages that was
probably forgotten, but when they discovered gain state them and I liked it, I went to the source
and I read that super long thing. And there are useful things said there. A way to visualize a
gain state them. Imagine that it has one queue, that is something more than the process mailbox,
with like three pointers. The head pointing at the oldest event and the tail pointing at the youngest
and current is where I am now. You can move where current is with some of the actions that gain
state them gives you, for example postponing an event. Postponing an event means that current moves
to the next, but the event is not forgotten. There is a different action that will put current
again in the head. Not postponing and you consume it is removed from the queue. When the state changes,
current goes again to head. Next event inserts things where current is and not at the tail.
And timeouts inserts things at the tail. So the engine, the gain state them implementation
allows you to extend the inputs that your formal state machine is going to get. How does it work?
Imagine that we are here, we have event one and we decide to postpone it. What happens?
It's still on the mailbox. We just are now going to deal with event two. Now we decide to do some
stuff and then go to the next state. So that has been processed and current because we changed the
state goes back to the previous. Now we are again going to handle event one and this time we decide
to not change the state, but we generate new inputs as if this process has received a message.
But this event A, which is ad hoc, we just created it, is inserted where current is. So it's the next
event that we are going to handle. We can decide to postpone it. Now we are going to handle event
three. With event three we do some stuff, but we don't generate events. Imagine that there is
middle code here doing. So event three has been dealt with. Now you go to event four and you decide
to postpone event four, but also insert and event B. So event four goes behind, you insert and event
B, you get the idea. So the engine gives you a way to extend the process queue. What am I doing with time?
Oh, one more important power. I'm not going to have time for everything. One more useful power of
the state machines. Managing accidental complexity. There is a talk that I want to recommend. It's
quite an old one, maybe something like 10 or 15 years ago by Ulf Rieger, where he was complaining
about some limitations of GANFSM, but even GAN server that we all use. Very useful talk and I have
one tiny answer to that with the new GAN state that didn't exist back then. Typical state on, off,
but you can imagine that you're switching a light, but your switch talks to a
through a cable protocol to the light machine. So when the user says on, this is a GAN server,
you say and the state is off, you send a request to on, you wait for the answer on, it's on, vice versa,
relatively intuitive code. Now imagine that that request through the cable protocol was not
synchronous and imagine that the switches cannot block. It needs to do other stuff. So you send
an asynchronous request to the light, hey, turn on yourself and continue doing other things, but then
the user sends more off and on. What do you decide to do here? It's not part of the protocol. The
events are now asynchronous and out of order. There is no global ordering. So there are some
questions like you need to choose what to do. Sometimes this, this is the, so we can use a
state machine. They use all the way. The name of the function is the name of the state and you can
postpone things if you are already running a request, you postpone it and when if the user
press on like a hundred times, by the time they like says on, then you have changed the state and
you're going to handle all those. It's already on, so just do nothing. But the code is terribly
symmetric. It feels repetitive. So problems, there is no ordering when things are asynchronous.
Tying yourself to the ordering of events leads to accidental complexity. This is the
point of Ulfiger when the order changes, the whole implementation changes. It grows relative to
the number of states. This is super simple. It's a like that goes on and off. But imagine
complicated protocols and for example a middle layer between a very talkative protocol and a
like one and code reuse. So I really like the handle event way of handling things. It's a single
function callback that gets a simple the state and the data. By the way, it's very confusing
because we are used to the state of the process for the server thing. But in the state, the state is
the state machine state. So the other thing where you save like, I don't know, the socket, for example,
is called data. So just confusing terminology. This, you can just pattern match whether you're
in the same state and the previous function that was terribly repetitive is now in a single
function head. This is, I believe, a way to answer to the problem that Ulf raised and now I'm
exactly on time. One more slide. A way to answer to that problem and in a way that you can reuse
code, that you can decide the order of events because you can postpone things and you can also
insert things. Quickly here, why I use on the XMPP, we had like this implementation. There is only
one thing that I really like here. The composing. As I said before, you have the TCP state machines
that go to TLS that goes to XML that goes to messaging. So if we want to implement this on a
single process, this can be, for example, this is a simplification on my data. I have a parser and
the crypto library that when I get that TCP payload, this is how we do it in Mongoose. I am not
TCP, TCP we just use TCP to complicate it. So it's a separate process. But crypto and XML parsers,
we implemented on the spot. There is a C code that the parsers, part of the XML, for example,
it gives you a new parser with a buffer and the XML structure that then you can use to generate
the events that my protocol cares about, the XML payloads. That's one use case that we have.
That's me. You can find me by that picture in all the places. Those are some of the projects I
work in and I was going to say questions, but we are one minute late. Thank you.