The LIFO Stack - A Gentle Guide
The LIFO Stack - A Gentle Guide
Written by Harry Fairhead   
Article Index
The LIFO Stack - A Gentle Guide
The Function Stack

 

The Function Stack

LIFO stacks seem fun but do they have any real value in computing?

There are so many applications it is difficult to know where to begin but the factor that unites them all is the way that a LIFO stack alters the order of things in a regular way.

For example, when a programmer writes a subroutine or function call:

Call Sub1
Instruction

Then control is passed to the part of the program labelled Sub1 and when Sub1 is complete it executes a Return which passes control back to the instruction following the call.

This allows programmers to break a program down into modules, which can be called as and when needed.

Now how do you think that this valuable facility is implemented?

You could just keep the return address stored in a fixed location and when the “Return” instruction is given all that happens is that the fixed location is used to get the return address.

Fine but what if the programmer writes another Call within Sub1? 

Of course. it is legal and useful to allow a subroutine to call a subroutine and so on. You can’t cope with this using a single location to store the return address – you have to store all the return addresses.

The clue as to how this should be done comes from a consideration of how the “Return” instruction should work.

If you call Sub1, and it then calls Sub2 which then calls Sub3 then the first return should take us back to the instruction following call Sub2, and the second return takes us back to the instruction following call Sub1.

That is, the returns work in the opposite order to the calls – now you should be thinking “stack!”

The subroutine facility is usually implemented using a stack.

When a call is made the return address is pushed onto the stack and the return simply pops the latest return address from the top of the stack. It all takes care of itself and as long as we don’t run out of stack space you can call as many subroutines as you like.

Stack oriented languages

This use of stacks to implement subroutine/function call and return has proved so useful that it has more or less taken over our approach to programming languages.

Almost all modern languages have become so stack oriented that their entire structure is based on the use of a stack.

For example, many languages make use of parameters which can be passed to a subroutine or function.

These are usually pushed onto the stack before the function is called. They are accessible to the subroutine as items on the stack along with the return address.

The called subroutine cleans the stack up by removing all the parameters before it ends. It can also leave results on the stack for the calling program to make use of. In other words functions communicate with each other by storing data on the stack.

In other words the LIFO property allows function calls to be correctly nested and for parameters and results to be passed.

In addition functions generally create all their variables on the stack – so called local variables because they exist for as long as the subroutine is active and then they are gone.In other words all of a functions local variables are erased when the function returns and the stack is cleaned up.

This is the reason why function local variables have function scope and why they override variables declared in the calling programming.

The use of the stack to implement all of these facilities has had a radical effect on the design or programming languages and made things that were once seen as difficult very easy indeed.

The first language to be “stack oriented” was Algol, but all of the block structured modern languages – Pascal, Modula, C, C++, C#, VB, Java and so on - owe it and the LIFO stack a debt.

However, as with all good things it is very possible to take things too far. There was a time when the stack was thought to be so important that machines and languages were based on it and nothing but it!

The reason is due to the simple fact that a stack can be used to evaluate an arithmetic expression or any expression that uses operators.

Banner

 

 

Stacking Operators

When you write down an operator expression – for example, 2+3*4 – you don’t perform the operations in the order they are written.

That is, 2+3*4 is not 2+3 multiplied by 4 it is 3*4 plus 2 which is 14 not 20.

Given that this is another “alter the order of things” problem you should again be thinking “stack”!

In this case the method is slightly more complicated than the shunting algorithm but not much. The simplest way of doing it is to have two stacks – one for the values and one for the operators, but it can be done using just one stack quite easily,

All you do is assign each operator a priority. For example, + is priority 1 and * is priority 2.

You then scan the expression from left to right stacking each item as you go on its appropriate stack.

Before you stack an operator however you compare its priority with the operator on the top of the stack. If the current operator has a higher priority then you pop it off the stack and make it operate on the top two items on the value stack – pushing the answer back on the value stack.

When the scan is completed the final answer is evaluated by popping each operator off the operator stack and using it on the top two items on the value stack, pushing the result back on until all the operators are used up.

The answer is then the single value on the stack.

In the case of the expression 2+3*4 this would result in the following steps –

 

arith

 

Try the same method on 2*3+4 and you will discover that when you reach the + operator the 2*3 is automatically calculated before the + is pushed onto the operator stack (because the * has a higher priority and we have to evaluate the top two items on the stack using it and push the result back on the stack)..

Reverse Polish -RPN

This stack operator algorithm is well known and there are lots of variations on it. It also gives rise to the once very well-known Reverse Polish (RP) notation.

If you write operator expressions so that each operator acts on the two items to its left then the expression can be evaluated using an even simpler stack algorithm.

For example, in RP the expression 2+3*4 would be written 2, 3,4*,+ and it can be evaluated simply by scanning from left to right and pushing values on the stack.

Each time you hit an operator you pop the top two items from the stack, apply the operator and push the result back on the stack.

When you get to the end of the RP expression the result is on the top of the stack.

Try it and you will discover it works. In fact you can use a stack to convert standard operator, known as infix, expressions to RP.

Back in the days when hardware was more expensive it was thought to be a good idea to get people to work directly in RP. You could and still can buy calculators that work in RP notation.

To add 2 and 3 you enter 2, then 3 and press the plus button.

Burroughs even built a mainframe computer that didn’t have any other type of working memory than a stack. Everything it did was effectively in RP notation applied to the central stack. The stack machine architecture was simple but not fast enough to compete with more general architectures.

However the stack approach to computing hasn't completely died a death. For example, the difference between the usual Java Virtual Machine - JVM and the one used in Android - Dalvik is the use of a stack. The standard JVM is  register based machine but this is too expensive and power hungry for a mobile device hence the Dalvik VM is a stack oriented VM.

Forth

Perhaps the longest standing overuse of the stack approach was, and is, the language Forth and its many derivatives.

It turns out that with a little effort you can build an entire programming language that can be written down as operators in RP notation.

Of course making it work is just a matter of using a stack to push operators and operands onto.This makes it easy to implement but arguably difficult to use.

However the fun that people had thinking in RP is such that they became really good at it!

The fascination for this sort of language is so great that you still find it in use in niche environments particularly where hardware is limited and it has its enthusiast following.

The LIFO stack is a wonderful invention but it isn’t the only thing computer science has to offer us as a practical tool!

If all you know is the LIFO stack then everything looks like a pop or push.

Related Articles

Introduction to data structures

Stack architecture demystified

Reverse Polish Notation - RPN

Brackets are Trees

Javascript data structures - Stacks

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin.

 
 

 

blog comments powered by Disqus

 
Banner


Introduction To The Genetic Algorithm

Genetic algorithms pop up all over computer science and applied computing. They are simple, easy to apply and easy to understand. What mystery remains is why they work at all? How can something seemin [ ... ]



Advanced Hashing

Hashing is arguably one of the great ideas of computing and it has hidden depths. Extensible hashing and perfect hashing are ideas that are worth exploring.


Other Articles
 

<ASIN:B000TDRHG8>

<ASIN:B00004TFL6>

<ASIN:0201914654>

<ASIN:0201657880>

 <ASIN:007136207X>
<ASIN:0735617805>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2017 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.