Designing A Calculator with FSM Logic
As far as I can tell, making a calculator is a classic first time programmer’s challenge. So, as I was helping some of my fellow underclassmen learn web dev, I suggested making a calculator! For best practice purposes, I also suggested starting off with brainstorming:
- first, we design how this calculator is going to work,
- then we can implement code for this,
- and finally, we can make it pretty
As we were brainstorming, we naturally through that a coherent design logic for our calculator would be a finite state machine (FSM)!
WAIT 👊. What’s a Finite State Machine (FSM)?
NOTE: If you’re familiar with FSMs, you can skip this section entirely 💁.
An FSM is a mathematical objects made of states, state transitions, and inputs. FSMs are widely used in computer science and engineering to model the behaviors of machines. At any given time, an FSM has one state and can receive inputs. Based on those inputs, the FSM can change both state (through state transitions) and interval variables of the FSM.
HERE’S AN EXAMPLE: The state machine of the human body.
A very simplified human body has 2 states: hungry
and full
. When humans are hungry
, they need food
in order to move back to the being in thefull
state, and at the same time, they may become happy :D
when they get food. Becoming happy in this case would be an internal variable of the state machine, and eating would be an input.
Then, humans use all their energy
(the other input) which makes them hungry
again. They could become SAD 😔 too.
So, inputs essentially lead to state change in a state machine. Here’s what this simple human body state machine would look like when graphically represented:
Ok, let me show you another example!
You’re about to see an FSM that you’re very familiar with but that was just never called an FSM: the state of matter.
Right, isn’t that cool? We learn this in high school, but they never call it that way. Anyway, this state machine has 4 states: PLASMA, GAS, SOLID, LIQUID. There are transitions from states to states, which are inputs that are either caused by nature or by humans. Internal states of this state machines could be, for example, the boiling temperature of the given matter, the name of the given matter, etc.
Why Are (Finite) State Machines Important? 🐍
They provide us with a very systematic way of modelling anything that can happen in real life (such as state of matter). Based on state machines, we can easily use mathematics to derive both properties of those machines. State machines are widely used in probabilistic applications, such as modelling the motion of a robot looking for a reward located somewhere the robot does not know using Markov Random Process (which is also a subset of state machines). State machines also allow to naturally and easily expand our model (both through the design and through code). For example, in the human body, we could add another state, not full / not hungry
, where the human person could be feeling meh
. To add that, we simple create a new state and add some transitions to it.
Of course, there are times when other models are better, but state machines work best for certain kinds of applications.
Finally, if you’re more interested, here’s an article on embeddedrelated.com by Jason Sacks that goes over a lot more details that I did. If you find this interesting, you will love that article.
Back to Calculators
Later on, we decided to use the iPhone’s calculator to identify all the possible states in our calculator state machine simply by playing around doing multiple arithmetic computations. And…
It quickly turned out to be much more complicated than I thought.
Here’s some thought to not using a state machine:
- Designing a calculator without thinking about all the state machine’s logic is very simple. It works well for most operations, and noticing the imperfections in it can be subtle. However, there are operations that simply do not work well, such as
2 + 4 * 2
, which in reality is2 + (4 * 2) = 10
and can be erroneously evaluated as(2 + 4) * 2 = 12
. - Another way to design a calculator is one where the user can input expressions, such as
3 * 4
, which can be easily evaluated with functions likeeval
. Not that I am not suggesting usingeval
(it’s know to be a bad practice); it’s just a quick solution that could help quickly get down to implementing all the UI for the calculator.
However, nicely designing a calculator with a correct finite state machine is not that easy. Nevertheless, I decided to pursue this interesting challenge, and this is what I came up with:
😧 That looks quite complicated. Let me explain. 😤
Note: if you’d like to skip to the end, I posted JavaScript gist code snippet that implements this.
The main idea behind a simple calculator is that we receive inputs, and based on those inputs, we make some operations, and if needed, we change the output display on the screen.
Inputs may be:
- numbers (one of
0,1,2,3,4,5,6,7,8,9,.
. note that I included the.
as a “number”), - operations (one of
+,-,*,/
), - equality (i.e.
=
), or - reset (could be
C
orAC
on iPhone. One of them isclear
which is same asclear entry
and the other isclear all
).
Then, we can denote the inputs as follow:
- Operations are
OP
for+,-,*,/
,OPS
for+,-
, andOPC
for*,/
.C
for complex,S
for simple. - Equality is just
=
. - Input numbers may be one of
fk
,sk
, ortk
.k
actually stands for the new input’s index for numbers such that a number is a sequence of digit charactersf0,f1,f2,...,fk-1
, and the input makes the number becomef0,f1,...,fk
. For example, in123
,f0=1, f1=2, f2=3
andk-1=2
. The inputf3=4
will change that number into1234
. - The reset button is
RES
. This is like pressingAC
orC
on your iPhone’s calculator.
Next, I designed the underlying structure of the calculator as blocks of the form:
|---|-----|---|-----|---|
| F | OP1 | S | OP2 | T |
|---|-----|---|-----|---|
F
stands for “first” as in “first number”OP1
is the first operationS
is stands for “second” as in “second number”OP2
is the second operation, and finallyT
stands for “trailing” as in “trailing number”.
By now, you can probably imagine that we’d be doing operations against the first and second number and against the second number against the trailing number, but how are the operations actually made, what do each of those blocks actually mean, and where does the result get stored? Let me explain all of it!
The State Logic 😋
What we need is to identify all the possible states for this FSM. This is the difficult part. I learned here that this type of calculators try to make the most logical assumption while respecting the rules of mathematics, and it can be beautifully describes with only 7 states! Before diving into these 7 states, first, here’s what the state parameters in a state represent:
F <- the value of the first number
OP1 <- the operation between the first and second number
S <- the value of the second number
OP2 <- the operation between the second number and trailing number
T <- the value of the trailing number
D <- what is displayed on the screen; it can be one of F, S, and T
The inputs that I listed above are what will lead to various state transitions. Now, onto the states:
State 1: INITIAL State
So, the initial state looks like:
F: 0
OP1: +
S: 0
OP2: +
T: 0
D: F
This is the state we start off with. There’s nothing interesting, and the values that we start with are just zeros and +
operations.
Pressing RES
will take us back to the initial state: it essentially has no effect. YES, self loops are allowed in FSMs. 😈
Pressing =
take us to the EQUAL state, which I will get to.
Pressing any number, denoted by fk
(which must be equal to f0
for this input coming from the INITIAL state) will take us to the TRANSITION FROM INITIAL state. I will talk about that state next. The number is denoted with lowercase f
because it will be filled into the first number F
. Note that adding numbers into other blocks will then have to either be sk
or tk
for block S
and block T
respectively.
Finally, pressing any operation OP
will take us to the TRANSITION state. Note that this will change OP1
to become OP
, whatever OP
may be among +,-,*,/
. This state is upcoming as well.
STATE 2: TRANSITION FROM INITIAL
Let me point out that my naming convention here is a bit weird, but I tried my best to give these states meaningful names. 👽
Without further ado, this state looks like this:
F: f0...fk-1
OP1: ~OP1
S: ~S
OP2: ~OP2
T: ~T
D: F
Some things to note: I use the ~
notation to denote that the value of this key is whatever the given state key was before (not that it could be that the state key does not match state key, e.g.: S: ~F
). Some later states will cause these values to change and not be +
or 0
as in the initial state.
So, anyway:
Pressing RES
will take us to TRANSITION FROM INITIAL state (i.e. back to here) if F
is not equal to 0
. It will clear F
(i.e. set it to 0
). Pressing RES
will take us back to INITIAL state if F = 0
. This means all parameters become what they used to be. i.e. F=0, OP1=+, S=0, D=F, OP2=+, T=0
. I will show why this is important at the end.
Pressing any number fk
will take us back to this same state, TRANSITION FROM INITIAL and simply append fk
to f0...fk-1
.
Pressing the =
sign will take us to the EQUAL state. Through this, it will make the evaluation (F) OP1 (S)
and place the result in the F
block when it reaches the equal state.
Finally, pressing any operation OP
will take us to the TRANSITION state. Note that this will change OP1
to become OP
, whatever OP
may be among +,-,*,/
. This will also duplicate F
into S
.
STATE 3: TRANSITION
If you go back to the visual, you will notice that this state is the most frequented state (i.e. has the most arrows coming into it). EQUAL is the second most frequented. Anyway, this state looks like:
F: ~F
OP1: OP
S: ~F
OP2: ~OP2
T: ~T
D: F
Note that to reach this state, one must press an operation OP
; that is the value that OP1
takes! There’s also something funny that happens here: the value of F
gets duplicated into S
. This is an optimization that was made by the iPhone. It’s a design decision that did not have to happen but works very well. Let’s say you press 3
then *
. Then, what happens if you press =
? Do you get a zero because you didn’t type the second number? With this design decision, you’d get a 9
because we assume that you meant 3 * 3
. I think it’s cool that they thought of this!
Then, pressing any OP
leads us back to this state. It simply changes the operation to the new one.
Pressing =
evaluates (F) OP1 (S)
and places the result in F
. Then, it takes us to the EQUAL state. Note that when it takes us to the equal state, both OP
and S
and every other parameters of the state remain unchanged. This is also cool. Do you see why? Maybe it’ll be more obvious once we get into the EQUAL state.
Pressing RES
takes us back to TRANSITION FROM INITIAL. On the way to it, it removes all the values in F
and replaces it with 0
. All the other parameters remain unchanged.
Finally, pressing another number sk
takes us to the TRANSITION FROM TRANSITION state. As you can imagine, this changes the value of S
. Note that as coming from TRANSITION, sk = s0
(the very first index of the second number regardless of what S
currently is, it will overwrite it).
STATE 4: TRANSITION FROM TRANSITION
(That naming though… Sigh) 😞
This state is interesting. It looks like this:
F: ~F
OP1: ~OP1
S: s0...sk-1
OP2: ~OP2
T: ~T
D: S
You can probably note that the display has now changed from F
to S
. Now, we’re displaying the second number!
Pressing sk
takes us back to this same state, it just appends sk
to S
so that it now becomes s0...sk
.
Pressing =
takes us to the EQUAL state. Again, it will evaluate (F) OP1 (S)
and place the result in F
and also keep all other parameters unchanged.
Pressing RES
takes us back to TRANSITION FROM TRANSITION if S
is not equal to 0
. This will clear S
and replaces it with 0
.
Pressing RES
when S = 0
will take us back to INITIAL. This means that everything will get back to what it started off with.
Finally, pressing OP
is the interesting case. There is actually two possible cases here:
- If we press
OPS
, we evaluate the expression(F) OP1 (S)
and place its result onF
. It will also place that same result onS
as well. This is because we’re doing a simple+
or-
operation, so we can just evaluate the pression.OP1
will becomeOPS
, whatever it may be. Then, it will take us back to the TRANSITION state. - If we press
OPC
andOP1 = OPC
, then we do the same as when we pressOPS
except it’sOPC
. of course. - Finally, if we press
OPC
, we will be taken to the TRAILING state ifOP1 is OPS
(i.e. ifOP1
is one of+
or-
). In this state,OP2
is always and becomesOPC
(i.e. one of*
or/
) andOP1
is always anOPS
.S
remains what it was, which iss0...sk-1
, butT
will now get the value ofS
. The displayD
andS
remain unchanged.
STATE 5: TRAILING
Why do we have a trailing state? 👀
Imagine the expression 9+5*2
, should it evaluate to 14*2=28
or should it evaluate to 9+10=19
? If you care about Mathematics, you know that multiplication takes precedence. That is why we have both the TRAILING state and the TRANSITION FROM TRAILING state!
Note that in this state, OP1
is always OPS
and OP2
is always OPC
.
The TRAILING state looks like:
F: ~F
OP1: ~OP1=OPC
S: ~S
OP2: OPC
T: ~S
D: S
Pressing =
takes us to the EQUAL state. The evaluation is different however. First, we evaluate (S) OP2 (T)
, place the result into S
(note that we make this evaluation before moving to the equal state), then we evaluate (F) OP1 (S)
, which places the result into F
(note that we make this evaluation after moving into the equal state). So, now, F
is essentially (F) OP1 ((S) OP2 (T))
. All other expressions remain unchanged.
Pressing RES
will take us to the TRANSITION FROM TRAILING state. This will immediately set T = 0
and all parameters will remain unchanged. The display will become T
. Someone pressing tk = t0
is essentially equivalent to pressing RES
from the TRAILING state.
Pressing OPC
leads us back to the TRAILING state and simply change the OPC
on OP2
.
Pressing OPS
will run the same evaluation done with pressing =
, i.e. it will place (F) OP1 ((S) OP2 (T))
into F
but also on place it on S
. OP1
will be OPS
, whatever it may be, and the display will be F
. Other keys will remain unchanged.
Finally, pressing tk
will take us to the TRANSITION FROM TRAILING state. In this case (i.e. coming from TRAILING), tk = t0
. The display also changes to D=T
.
STATE 6: TRANSITION FROM TRAILING
This state looks like:
F: ~F
OP1: ~OPS
S: ~S
OP2: ~OPC
T: t0...tk-1
D: T
Pressing RES
if T = 0
will take us back to INITIAL state. Everything will be cleared. However, if T
is not equal to 0
, pressing RES
will just clear T
(i.e. set it to 0
) and remain in this state.
Pressing tk
will just append tk
into the current value of T
.
Pressing =
will evaluate the expression just as evaluated when pressing =
during the TRAILING state, and it will take us to the EQUAL state.
Pressing OPC
will take us to the TRAILING state. This will evaluate (S) OP2 (T)
and place the result in both S
and T
. Then, it will change OP2
to be the new input OPC
. The display will change back to S
.
Pressing OPS
will take us to the TRANSITION state. This will evaluate the expression similar to how it’s evaluated in the TRAILING state.
STATE 7: EQUAL STATE
Whew! Finally, the EQUAL state. This state looks like:
F: (F) OP1 (S)
OP1: ~OP1
S: ~S
OP2: ~OP2
T: ~T
D: F
Note that the display in the equal state is always F
.
Pressing =
re-evaluates (F) OP1 (S)
and places the result into F
. Note that S
will remain the same in this case.
Pressing OP
will take us to the TRANSITION state. Then, it will make a copy of F
and place it into S
. Then, OP1
will be the newly received operation.
Pressing fk
will take us to the TRANSITION FROM INITIAL state. In this case, fk = f0
. Everything else will remain unchanged.
Pressing RES
will also take us back to the TRANSITION FROM INITIAL state. However, it will delete F
and replace it with 0
.
The Calculator (an example!)
Parting Notes
This is the calculator shown in the photo above. It’s a really nice state machine that works well for these simple operations, and the design is great because it can be easily expanded to more complicated operations such as sin
or floor
.
I wanted to point out that I didn’t really talk about how we are appending to the numbers. In case fk
(or equivalently sk
and tk
) is .
, we only append when there is no .
in the number. For example, pressing .
when F=243
will make F=243.
. However, pressing .
when F=23.5
will have no effects! Also, pressing any number other than 0
when F=0
needs to change F
into that number (equivalently for S
and T
).
This is definitely not crazy difficult, but I’d say it’s more complicated that it looks, and it’s been a rewarding exercise to actually design this calculator. Here’s code that I wrote that does this in JavaScript (which is meant to be used for a calculator website):
Or, check it out on Github:
Thanks for reading!