Stack-oriented Programming Language - Algorithm of Computation On Stack

Algorithm of Computation On Stack

Assume we have a postfix stack based programming language, like PostScript. To understand how a stack-oriented programming language works, in calculating an expression such as 2 3 mul, we can use a simple thought experiment.

Say you are standing at the end of a conveyor belt (the input), onto which someone has placed (in sequence) plates marked 2, 3, and mul. You can take the plate at the end of the conveyor (2), but you can't see or take further plates from the conveyor until you do something with the plate you've just taken. The only way you can store plates is in a stack, and you can only add or remove a plate on top of the stack, not in the middle. You also have a supply of blank plates (and a marker), and you can discard plates (but this is permanent). Can you perform the calculation?

Yes, you take plate 2 and put it on the stack, then take plate 3 and put it on the stack. Next, you take the mul plate. This is an instruction to you. You will take the top two plates off the stack, multiply their labels (2 and 3), and write the result (6) on a new plate. The two old plates (2 and 3) and the mul plate are then discarded, and the new plate gets put on the stack. With no more plates remaining on the conveyor, the result of the calculation (6) is shown on the plate at the top of the stack.

This is of course a very simple calculation. What if we wanted to calculate something like (2 + 3) × 11 + 1 ? If we first write it into postfix form, that is, 2 3 add 11 mul 1 add, we can perform the calculation in exactly the same manner and achieve the correct result. The steps of the calculation are shown in the table below. Each column shows an input element (the plate at the end of the conveyor), and the contents of the stack after processing that input.

After processing all the input, we see the stack contains 56, which is the answer.

We can conclude from this the following: a stack based programming language has only one way of handling data, by taking one piece of data from the top of the stack, known as popping, and putting data back on the top of the stack, known as pushing. Any expression that can be written "conventionally" or in another programming language can be written in postfix (or prefix) form and thus be amenable to be interpreted by a stack-oriented programming language.