In this segment we'll look at the ultimate in simple ISAs and small machine instructions: stack machines.
A stack machine dispenses with general-purpose registers, replacing them with a stack of numerical values, maintained in the CPU, on which all mathematical and comparison operations are performed. (This stack is different from the RTS, which is in memory.)
Machine instructions in stack machines do not have register fields to specify source operands and a target result. Instead, all machine instructions work with the top values in the stack, and any result of an instruction becomes the new top of stack. (In stack terms, each operation "pops" off of the stack its needed operands, performs a computation with them, and "pushes" back the result.)
This means almost all machine instructions can be very short -- just an opcode -- because the operands and target are always at the top of the stack and needn't be specified. This includes even load and store operations to/from memory which are also done onto the top of stack, or from the top of stack.
The great strength of a stack machine is its very short instructions, which are correspondingly fast to load and execute. Its weakness is that it takes more instructions to get anything done.
Can such a limited model really do arbitrary programming operations? Yes.
Here's an example stack machine assembly language, and a summary version of it in the notes. It has exactly 9 instructions. (It would need several more to be complete, but these 9 will do for our example.) Let's review them briefly here, and then look more closely at them in the code below.
Push [constant] onto stack. [Constant] may be any integer, including an address, which may be specified by giving a label in the program.
Pop the top element off of the stack and use it as an address. Fetch the integer at that address and push it onto the stack in place of the address.
Pop the top two elements off of the stack. Use the top element as a value, and the second from top as an address. Put the value at the address.
These all take the top two elements off of the stack and perform the indicated operation on them, leaving the result on the top of the stack. The top of the stack is the second operand; the element below that is the first operand.
Pop the top element off the stack and jump to that location.
Pop the top element two elements off the stack. If the top one is negative, go to the location provided by the second from top.
Given just 9 opcodes, this machine language could use 4 bits for an opcode, and that's all for most instructions. The only exception is the push instruction, which would need more bits for its constant, and thus might take 36 bits.
So, how does such a tiny machine language implement, say, this expression?
x = a - b
Here's a listing. In this listing, we have a small data segment holding x, a, and b, which we'll assume starts at memory address 10000. In the code, =x represents "the memory address of x" as a constant, as in ARM assembly. The comments show the contents of the stack, from TOS downward, after each instruction.
1 push =x @ Stack is =x 2 push =a @ Stack is =a, =x 3 fetch @ Stack is a, =x 4 push =b @ Stack is =b, a, =x 5 fetch @ Stack is b, a, =x 6 sub @ Stack is a-b, =x 7 put @ Stack is empty; x now holds a-b. x: .word a: .word 42 b: .word 10
Let's walk this code through, using the diagram model which starts with an empty stack in the CPU, and the three words x, a, and b in memory starting at location 10,000
It's all in the planning. For instance, putting the address of x onto the stack first, followed by the values of a and b, meant that the right values would be on the stack for the sub, and then for the put.
Question 1
You give it a try. What would be the code for y = a - b*c? Set up initial data so a=42, b=10 and c=3. Remember to respect operator precedence and put multiplication first.
Answer 1
push =y push =a fetch push =b fetch push =c fetch @ Stack is now c, b, a, =y mult @ Stack is b*c, a, =y sub @ Stack is a - b*c, =y put @ Stack is empty; y now holds a - b*c y: .word a: .word 42 b: .word 10 c: .word 3
This code starts by setting up the ultimate target address of y. Then it pushes the values of a, b, and c in that order onto the stack, by a sequence of push [address]-and-fetch pairs. This leaves b and c at TOS so we can first compute their product via the mult. This leaves us with the right operands for the sub (again, the TOS is the second operand), and finally the put.
But does it work with more complex cases? Sure, if you plan it right. Let's try
x = e - (a+b)*(c+123) - (42-d)
Remember as you read the code below, that binary operations use the TOS as the second operand, and the value under TOS as the first operand. This may seem odd, but it means that we push the operands onto the stack in the natural first/second order. Track the stack contents for yourself in the comments, to be sure you understand how the stack will evolve.
push =x @ Stack is =x, which we'll need at the very end. push =e @ Stack is =e, =x fetch @ Stack is e, =x push =a @ Stack is =a, e, =x fetch @ Stack is a, e, =x push =b @ Stack is =b, a, e, =x fetch @ Stack is b, a, e, =x, ready for some math add @ Stack is a+b, e, =x push =c @ Stack is =c, a+b, e, =x fetch @ Stack is c, a+b, e, =x push 123 @ Stack is 123, c, a+b, e, =x add @ Stack is c+123, a+b, e, =x mult @ Stack is (a+b)(c+123), e, =x push 42 @ Stack is 42, (a+b)(c+123), e, =x push =d @ Stack is =d, 42, (a+b)(c+123), e, =x fetch @ Stack is d, 42, (a+b)(c+123), e, =x sub @ Stack is 42-d, (a+b)(c+123), e, =x sub @ Stack is (a+b)(c+123) - (42-d), e, =x sub @ Stack is e - (a+b)*(c+123) - (42-d), =x put @ Stack is empty. X contains computed valuePostfix computation and notation
Notice the pattern in this code. It first prepares operands on the stack, and then performs an operation on them. And it's recursive; "preparation" of each operand may involve a smaller subcomputation, as for
a+b,c+123and42-d. Also, it pre-stacks operands for lower precedence operations first, to be ready once higher precedence operations have left their result on the TOS.This pattern is called postfix computation. And there's a corresponding way to write expressions, called postfix notation because it puts the operator after the two operands. (The standard notation we routinely use is *infix notation since it puts the operator between the operands.)
In postfix notation,
a+bbecomesab+, anda + b*cbecomesa(bc*)+. But, those parentheses are just for clarity, and are never really needed. We could have just writtenabc*+without ambiguity. The only way to interpret that postfix expression is to apply the*tobandcas operands, and then to apply the+toaand the result ofbc*Here are a few more examples to illustrate postfix notation.Traditional "infix" Postfix equivalent a - b - c a b-c- a - (b-c) abc-- (or a(bc-)- for clarity) a - (2 - c*d) a2cd*-- (or a(b(cd*)-)- for clarity) a - (b-c)*2 abc-2*- (a - b - c)*2 ab-c-2* (a - (b-c))*2 abc--2*Question 2
Using those examples as a model, translate the following infix expressions into postfix
a*b - 42*d - e a*b - (42*d - e) a*(b - 42*(d - e)) a*(b - 42)*d - eAnswer 2
a*b - 42*d - e => a b * 42 d * - e - a*b - (42*d - e) => a b * 42 d * e - - a*(b - 42*(d - e)) => a b 42 d e - * - * a*(b - 42)*d - e => a b 42 - * d * e -Question 3
Now try it the other way, translating these postfix expressions back into infix. You'll need parentheses in several cases, but don't add them unless necessary.
a b c d - * - a b - c * d - a b c - * d - e a b + c 123 + * - 42 d - -Answer 3
a b c d - * - => a - b*(c-d) a b - c * d - => (a - b) * c - d a b c - * d - => a*(b-c) - d e a b + c 123 + * - 42 d - - => e - (a+b)*(c+123) - (42-d)Stack machine control structures
OK, but what about loops, ifs and other control structures? The
gotoandgonegbranch instructions are all we need if we plan correctly. Let's try writing stack machine code for this loop:while (i <= 42) i = i + 1;That would be: loopTop: push =afterLoop @ Stack: =afterLoop push 42 push =i fetch @ Stack: i, 42, =afterLoop sub @ Stack: 42 - i, =afterLoop goneg @ Stack: empty. Jump to afterLoop if 42 - i is negative. push =i @ Location for future "put" push =i @ Stack: =i, =i fetch i @ Stack: i, =i push 1 @ Stack: 1, i, =i add @ Stack: i+1, =i put @ Stack: empty. Variable i is incremented. push =loopTop @ Stack: =loopTop goto @ Stack: empty Return to loopTop afterLoop: ........Question 4
What would change above if the loop test were i >= 42?
Answer 4
push =i fetch push 42 @ Stack: 42, i, =afterLoop sub @ Stack: i - 42, =afterLoop goneg @ Stack: empty. Jump to afterLoop if i - 42 is negativeReversing the roles of 42 and i, by switching their order on the stack, results in a test for i >= 42.
Universality of < comparison
You might reasonably wonder if a single conditional instruction
gonegcan cover all possible comparisons. It appears to be capable only of <= tests by checking whether a preceding subtraction had a negative result, and apparently for >= tests by reversing the operands.But in fact, all six comparisons can be rephrased, with some complexity, as logical combinations of just less-than comparisons.
a < b a < b a > b b < a a <= b !(a > b) a >= b exercise a != b a < b || b < a a == b exerciseQuestion 5
Fill in the two "exercise" lines from above.
Answer 5
a >= b !(b > a) a == b !(a < b || b < a)We've seen in earlier code that logical
&&,||and!can be implemented by appropriate combinations of branches. So, thegoneginstruction can deal with arbitrary comparisons and logic. In practice, a stack machine would have more types of comparison instructions to keep code from being needlessly complex, but it's useful to see that <, in principle, is all you need.Practical stack machines
We've now seen three major design philosophies for ISAs: CISC, RISC, and stack machine. If they were gasoline engines, CISC would be a 70s V8 -- powerful but dated. RISC would be a modern efficient 4-cylinder, and stack machines would be one-cylinder small engines for special applications like lawn mowers.
Practical stack machines include very small processors for controlling devices and other specialized applications. And they also include software virtual machines. The Java VM is a notable example.
RPN and HP calculators
Finally, it's worth a brief note that Hewlett Packard calculators understand postfix notation, and can be operated that way. HP uses the alternate term RPN (Reverse Polish Notation) to describe postfix, but it's the same concept. If you can wrap your mind around it, postfix notation is more efficient than infix since it requires no parentheses, so highly technical users sometimes prefer it.