To understand LIFO (Last-In First-Out) stacks, it is probably easiest to start with stack-based arithmetic; then the extension to language may make more sense.
Consider an arithmetic expression like this:
1 + 2 × 3 - 4 ÷ 5
Anyone past middle school has learned that there is a standard order of operations in such expressions. In the United Sates, we learn the phrase "My Dear Aunt Sally" to remember that Multiplication and Division come before Addition and Subtraction. To change the order, or just to make it explicit, you can use parentheses (...), which say "do what's between us first". The above statement is the same as this one:
1 + (2 × 3) - (4 ÷ 5)
So to find out what the answer is, you first multiply 2 by 3, giving 6, and divide 4 by 5, giving 4/5 or 0.8, and then replace the parenthesized subexpressions with the results:
1 + 6 - 0.8
Which is then easily added to yield the answer of 6.2.
So "1 + 2 × 3 - 4 ÷ 5" is "Mathematish" for something like "multiply two by three; then divide four by five; then add one to the first result and subtract the second result from the sum." As you can see, stating it in English is more awkward than using the symbolic notation.
Expressions like "2 × 3" are said to be written in "infix" notation. That's because when you are meant to perform an operation on two numbers - called a "binary operation" - the symbol that tells you which operation to perform (+, -, ×, ÷) goes between the two numbers you are meant to perform the operation on. So "multiply two by three" is written "2 × 3". This is the normal way of writing things down in mathematics, but there are other options: prefix notation ("× 2 3") and postfix notation ("2 3 ×"). Both prefix and postfix notation have the advantage that they're never ambiguous, and you never need parentheses.
The long expression I started with becomes this in prefix notation:
- + 1 × 2 3 ÷ 4 5
Read it from left to right. First, we find out that we are going to be subtracting one thing from another. Then we find out that we're going to get the first number by adding some other numbers up. The first number we add is 1. The second number in the addition is going to be the result of a multiplication, and the two numbers to multiply are given directly as 2 and 3. So now we can do the multiplication, yielding 6, and the addition, yielding 7. Have to continue to find out what we're subtracting from 7, though. The ÷ tells us it will be the result of a division operation, and the two arguments are again given directly, so we divide 4 by 5, yielding 0.8, and subtract that from 7, giving 6.2.
In postfix notation, it looks like this:
1 2 3 × + 4 5 ÷ -
And right away you may see a big difference. In evaluating a prefix expression, we have to remember what operations we're in the middle of until we finally get numbers to plug in. In evaluating a postfix expression, we never have to remember an operation, but we do have to remember numbers, which we encounter before - sometimes long before - we know what we're going to be doing with them.
Stack-Based Arithmetic
Computer Science has a data structure called a "stack" that is perfect for this sort of evaluation. It is a place to store data that you can only do two things with: give it a piece of data (a number, in this case), or ask it for the last piece of data you gave it. You can only get the data back out in the opposite of the order in which you put it in. So if you give the stack the number 1, then the number 2, and then the number 3, and then ask it for a number back, it will give you 3 first, then 2 the next time you ask, and finally 1.
The name comes from the spring-loaded push-down stacks you see for dishes and trays in large cafeterias - the next dish or tray you pull off the stack is always the last one you put there, because you can only get to the top one at any given time; the others are all down in the hole.
So to process a postfix expression with a stack is easy. Whenever you see a number, you put it in the stack (this is called "pushing", again by analogy with the dish stack). Whenever you see an operator (+, -, × or ÷), you pull (or "pop") the last two numbers out of the stack, perform the operation on them, and push the result back on the stack.
Let's try that on the expression above:
1 2 3 × + 4 5 ÷ -
The stack starts out empty:
First we see a 1, which is a number, so we push it on the stack:
Then we do the same with the 2:
And the 3:
Then we see a ×, so we pop off two numbers and multiply them together. The first pop gives us 3, the second 2; we multiply them together and push the result back on the stack:
Then we see a +, so we pop off two numbers and add them together, pushing the result back on the stack:
Then we see number 4 and push it:
Then we see number 5 and push it:
Then we see ÷, which tells us to pop two numbers off and divide them. Note that the first number we get back from the stack is the divisor, not the dividend - we want 4 ÷ 5, not 5 ÷ 4.
Finally, we see -, which tells us to pop two numbers off and find their difference. Again, note that the first number we get back from the stack is the subtrahend, not the minuend - we want 7 - 0.8, not 0.8 - 7.
Which is our final answer.
RPNnglish
Fith is designed like postfix notation. Nouns get pushed on the stack, and operands like postpositions and verbs and adjectives operate on them.
I don't know Fith, so I'll create an example with English words and just put them together postfix style. Prefix notation is sometimes called "Polish notation" because a Polish mathematician first proposed it, and postfix notation is therefore called "Reverse Polish Notation", or "RPN" for short. So let's call this syntax variation "RPNglish."
Consider a sentence from part 4 of the McGuffey Reader:
The fat hen is on the box.
In RPNglish, then, you might put it this way:
Hen fat the box the on is.
Let's go through it with the stack
The word "hen" is a noun, so we push it:
The word "fat" is a modifier, so we pull the noun, apply the modifier, and push the result (a phrase) back on the stack. (The quotes indicate that even though there are two words, it's just one item on the stack.)
The word "the" is also a modifier, so we do the same thing:
The word "box" is a noun, so we push it:
Then we hit another "the":
The word "on" is a preposition, although in RPNglish it's really a postposition; it turns the noun on top of the stack into an adverbial describing a location:
| "on the box" |
|---|
| "the fat hen" |
|---|
Finally, we have the verb "is", which takes two arguments off the stack and creates a single concept which is the linking of the two arguments;
| "the fat hen is on the box" |
|---|
The transformations from "Hen fat the box the on is" were regular, thanks to the simple organizing force of the stack.
Now, one vital quality of such a language is that you have to be able to tell immediately, upon encountering a word, whether it is an "operand" (to be pushed on the stack) or an "operator" (to modify what's on the stack). This was clear in this simple example, but it isn't true of English in general, because most words have multiple definitions spanning multiple parts of speech. So a postfix language needs either to have morphological indications of function, or to disallow cross-functional homonymy.
© 2005 by Mark Reed. All rights reserved. Used by permission.
|
