might possiblyYou may be familiar with stack machines. Or maybe not.
So I should introduce them with an example of how they work that you might possibly be familiar with.
Calculating the area of a circle:
A = πr2
And here's one way you might calculate it, if you were thinking like a computer:
remember 3.1415927 (result level 1)
remember the radius (result level 2)
duplicate the last result (result level 3)
multiply the last two results and remember this result instead (result level 2)
multiply the last two results and remember this result instead (result level 1)
print the last result (result level 0)
Yeah, it seems like a lot of work to go to. But it's organized, methodical, etc.
If you notice how the results tend to stack up and then be consumed, you might understand what a stack machine does. Essentially, there is a stack machine hidden in the so-called algebraic notation we were taught in school. Let's take a look at what the stack does in the above:
But there are explicit stack calculators, such as the HP calculators that run in RPN, and the dc (desktop calculator) utility that is standard on most Unix and Unix-like OSses.
If you have a modern Mac or are running a GNU/Linux OS, open up a shell on the desktop and type in, "man dc", without the quotes. Once you've read the manual page, hit the "q" key to quit man and type in, "dc", again, without the quotes. And type in something like the following, assuming the radius is 5:
3.1415927 5 d * * p
and it tells you the area for a radius of 5, 78.5398175. Each number entered is pushed onto the stack. "d" duplicates the top (last value pushed). "*" is what computers often use instead of the × operator that looks like a little "x". Looks confusing at first, but less so once you get used to it. "p" is the print command. Looking at the stack,
Compare that again to the usual (in-order) algebraic formula, with the algebraic operations made explicit (using "*" for muliply):
A = π * ( r * r )
Lets look at what a different calculator available in the Unix toolbox, bc (basic calculator) would accept for input:
a = 3.1415927 * ( 5 * 5 ); print a
Perhaps you will notice that the input to dc directly reflects the organized, methodical operations which I said a computer might perform, whereas the input to bc represents the way we usually write the mathematical expressions.
Let's focus on dc first. (Actually, we'll come back to bc when we talk about having more than one stack.)
The opeand stack is visible and explicit. It allows sub-expressions to be evaluated in stages such that the results of sub-expression can be used by the enclosing expression quite freely. That is, you can take the square of the radius before you multiply it by π, even if you enter π first. Very complicated math can be calculated without storing intermediate results in named memory locations.
But there is something else you can do. Say you make a mistake. The radius is 5, but you type in 4 by accident:
3.1415927 4
p
5 d * * p
Sure, you get extra output, but you didn't have to start all over from scratch.
You're not impressed. You'd just use the backspace key.
Get off my lawn, you young whippersnappers! Let me tell you about how hard it was to use mechanical calculators back in the days when memory wasn't so cheap!!
Heh. Wait. Let me tell you something else.
Backspace can be done without a stack, but it isn't easy to make it work right in all cases.
And what about the undo function? No way you're going to be able to implement undo without something like a stack. (How the effective undo stack is constructed is a separate topic, as is the possibility of using a tree instead. Let's set it aside for now.)
Back when I was a kid, the washing machine controller was a dial. Classic state machine.
The washing machine we own now has pushbuttons and LED readouts. Each pushbutton operates like a dial, and if we find we've made a mistake we have to cycle through that pushbutton's set of settings. (72 liters, 69, 65, 62, 59, ...) Again, a classic state machine. (I want to redesign the controller to be more responsive to humans that make mistakes or change their minds, but that's not what we want to talk about here, even though giving the micro-controller more memory for a stack might help.)
If the barrel goes off balance in the spin cycle, it gets stuck. To get unstuck without human intervention, it skips that spin cycle and goes on to the next cycle. If it's the last spin cycle, it starts to refill and run another rinse cycle to adjust the load so it can try the spin cycle again. That's classic state machine behavior, and an illustration of why mathematicians say you don't really have a stack unless you have more than one memory location in the stack. And a waste of water.
If the second try at the final spin fails to stay balanced long enough to get the spin cycle going, it stops, puts "E2" (or something equally meaningful) on the estimated time remaining0 LED readout and starts beeping for a bit. Then it waits for operator intervention.
Tilt. Classic state machine behavior.
Now wouldn't it be nice if we could store the water after draining it, so that if the barrel tilts we can put the water back and not use new water to re-balance the load? A virtual washing machine in a computer simulation could do exactly that. But, in the real world, the holding tank would take up space and tend to get moldy and dirty.
But with computer programs, especially in modern computers with lots of cheap memory, that's precisely the sort of thing we regularly do.
Formulae that fit into this class of machine won't have something that looks like a stack, nor will they produce graphs that appear to back up and start over.
There is another way to discuss machines of this class. Some mathematical formulae used in numerical analysis will have output that is dependent on a combination of the current input and the current state (as we mentioned in the previous section). If we add one or more previous states to the set of equations, the mathematical automaton defined by the set is in the class of single stack machines.
I'm thinking in terms of attempting to describe the path of an airplane on autopilot in a set of equations. No, I am not actrually thinking of making such an attempt myself, but I'm guessing that such an attempt, if successful, should be in this class.
What about the class of multi-stack machnes, then? The class of machines which run with multiple stacks have output states that do not entirely depend on the combination of past and current states and current inputs. (You can think about the ability to guess future input, but that is actually only sort of relevant to the question.)
So, as a guess, put a human or an AI pilot at the control of an airplane with autopilot. Something like that. And try to describe its path with a system of equations.
Incidentally, a semi-autopilot capable of keeping a plane on keel and on a single heading would usually be implemented as a machine in the stack machine class. Full auto-pilot would require a machine of the mult-stack machine class. The machines and the formulae describing their paths are not in the same class.
Stacks make it easy to recover from mistakes. They also make it possible to use computers to test different solutions to a problem in order, without having to start completely over all the time.
When we humans write down partial solutions so we can back up and try again if one path turns out to be wrong, we are using the same kind of thing.
Stacks make it possible to calculate speculatively.
If you're thinking all that backing up must be slow, you're probably right. Slower than what is a good question, however. Stack machines get slow a lot quicker than simple state-ful machines.
And, if you're thinking it's going to be harder to test a stack machine than a plain state machine, that might be true, too. If you can solve a problem without a stack, it's often worth the trouble to do so.
On the other hand, if you find that a machine has to do a lot of starting over, starting over from scratch will tend to take more time than backing up a ways and starting over from a partial result. It will also take a lot more testing to handle the starting over from scratch.
Using a stack allows machines to be constructed so that the become more general purpose in nature. It would be no stretch or exaggeration to say that stacks are what distinguish modern computers from the machines we have used in the past.
But does the number of stacks tell us anything about the complexity of a machine? Yes, it does.
Let's take a look at stacks and complexity.
Copyright 2011 Joel Matthew Rees