credit: Pete Markham

Here’s One Programming Paradigm you Probably Haven’t Heard of — Programming Word of the Day

You’ve heard of object oriented, imperative and functional programming. These are all different programming paradigms, or ways of thinking about programs. The reason you’ve heard of these is because they’re really popular paradigms. But they’re not the only ones out there! There are probably more than 20 different programming paradigms in use today, and that’s not counting their various combinations and offshoots.

Today I want to talk about one of those less popular paradigms, and it’s called stack based or stack oriented programming.

The Stack

To understand stack based programming, we first need to understand the concept of a stack. Stacks are very important things in computer science. Stacks help us allocate memory, parse and run code, add a way to undo the last action, etc. They’re behind a bunch of very important algorithms, and they’re the mechanism by which the CPU runs your code. Without stacks we would be doomed.

The stack is called that way because it resembles a stack in real life. Like a stack of cards or a stack of plates in a cupboard. If you want to add a new card into the middle of a stack of cards, you have to pick up the top half in order to place the card in.

A stack in a computer works similarly to that. A stack is a collection of things, but you can’t just put those things wherever you feel like it. Stacks have two important constraints:

1. You can only add stuff to the top of the stack. You can’t insert into an arbitrary position into the stack.
2. You can only get the item that’s on the top of the stack. If you want to get the third item, you would have to remove the first two items.

In programming terms, we can say that the stack is a type with two defined operations: push and pop. A push operation adds a new element to the top of the stack. A pop operation removes the top element from the stack. That's all you can do with a stack.

The fact that stacks are so constrained is exactly what gives them power. Because we can’t arbitrarily add stuff wherever we feel like, the order of items in a stack has significance. This gives stacks properties that other collections lack.

For instance, reversing a string is really easy with a stack. You can go through every character, and push it on the stack. When you do this, the last character in the string will be on the top of the stack.

"PWOTD"
stack: [P, W, O, T, D]

If you then pop every element from the stack, you will get characters in the reverse order.

stack: [P, W, O, T, D]
pop them all:
"DTOWP"

This is the power of stacks: elements that come into the stack in an order, must come out of the stack in the reverse order. This simple fact allows a bunch of algorithms to be implemented simply and efficiently. For instance, you can easily implement a simple calculator using stacks.

3 2 +

This is a plus operation in reverse Polish notation. This just means that the +operator comes after its two operands. If we push all of those elements into a stack, we get a stack of three items.

[3, 2, +]

Our code can then pop the item from the stack, and check what it is. If it’s a +, it knows that it can pop the next two items and add them together. It can then push the result back to the stack.

We can see the true power of this when we want to perform multiple additions.

(3 2 +) 5 +

Let’s push the values on the stack, but this time from right to left.

stack: [+, 5, +, 2, 3]

We will first pop the 3, and push it onto a second stack. We do the same for 2.

ops: [3, 2]
stack: [+, 5, +]

When we perform the next pop, we get a plus. We know that we should sum the two elements we remembered, and push the result on the stack.

ops: [3, 2]
stack: [+, 5, 5]

We start popping again and do the exact same thing. With this algorithm, using two stacks, we can perform an arbitrary amount of operations with very simple code.

As you can see, you can use stacks to implement a bunch of cool functions.

A Language Based on Stacks

We now know that stacks are pretty important and powerful. In fact, they’re powerful enough to make a whole programming language based around them!

A stack based language works by having a global stack that the code implicitly works with. This means that you don’t pass parameters when you call functions: all functions work by pushing and popping onto the global stack.

For instance, in a non stack based language, you would call a function to reverse a string like this:

reversed = reverse("PWOTD")

A stack based language works by pushing values on the stack. When you call a function, it will work with the values you pushed before calling the function.

"PWOTD" reverse

Yes, this is code.

When this program is evaluated, the computer will go left to right and first push “PWOTD”. The second thing it sees is the name of a function, so it will call this function. The function will then pop the string off the stack, and push a reversed string onto the stack. The contents of the stack would then be ["DTOWP"].

Since functions don’t explicitly receive parameters or return values, stack based programmers often just call them words. A stack based language consists of words and values, and everything can be written with those two things.

Let’s look at another example. Say you want to multiply two numbers, and then add another number to the result. In a normal language you would write something like the following:

result = 5 * 3 + 10

While in a stack based language you would write:

5 3 * 10 +

Again, the computer will start evaluating left to right. If it finds a value, it will push it onto the stack. If it finds a word, it will call it. Here’s what the stack contents will look like while the program is being run:

[5]
[5, 3]
called "*", which popped 2 elements and pushed a new one
[15]
[15, 10]
called "+", which popped 2 elements and pushed a new one
[25]

While these examples might be contrived, keep in mind that stack based languages are not at all limited! A modern stack based language like Factor has all the features you’d expect from a language: classes, objects, exception handling, collections, tuples, etc.

In fact, stack based languages can often make complex things simple. If you wanted to filter out users that are older than the age of 25, in a stack based language you could write the following:

users [ .age 25 > ] filter

If you are not used to higher level functions, this explanation might get confusing. Just hold on.

This will first push a list of users onto the stack. So far, so good. The thing inside the square brackets is a function, but in this case it’s also a value, and just like the users array, it will get pushed onto the stack.

The function inside the square brackets is not called yet! The code for the function itself is pushed on the stack.

That function expects a user on the top of the stack. The .age will pop that user, and push its age to the stack. The function will then push the number 25. It will then call > which will pop the two numbers, and push either true or falsedepending on whether the age is larger than 25.

This is what the stack would look like while the function inside the square brackets is being run:

// starting stack
[ User(age: 23) ]
// function starts
[ 23 ] // push .age
[ 23, 25 ] // push 25
[ false ] // call ">"

Finally we come to the word filter. Without getting too much into the weeds here, filter will pop the function inside the square brackets and the list of users. It will then check, for each user, whether the result of the popped function is trueor false. If the result is false, it will discard that user. Ultimately it will push a new list of users onto the stack, containing only users older than 25.

In just a single short line of code we have defined a very complex set of actions. This is why stack based languages are cool: you can do a lot in very short bits of code.

Because there are no variables, every piece of code is completely interchangeable and copy-and-pasteable. For instance, to factor out a few lines from a function is simply a matter of copying and pasting those lines. There’s no need to define a new function and think of the parameters and their names.

Stack based languages are also cool because their simple syntax allows them to support complex language features with their standard library, and not with “baked-in” features inside the actual language. There’s no special syntax for a while loop, it's just a plain old function living in the standard library.

This also means that functions are not a magical concept that exists somewhere on the wibbly wobbly heap of stuff and code (technical term). Functions are just lists of literals and other function names. At any point you can inspect and print the codeof an arbitrary function. Try printing a function in your favorite language!

It’s always good to learn a new paradigm: it will expand your mind and add another tool to your tool belt. I urge you to try out a stack based language, they’re really cool and completely different to what you’re used to. The references section contains some good links to get you started!

References

Concatenative languages, a good intro into what stack based languages are and what are some advantages
http://concatenative.org/wiki/view/Concatenative%20language

Factor tutorial, Factor is a modern stack based language
https://andreaferretti.github.io/factor-tutorial/

A list of programming paradigms according to Wikipedia
https://en.wikipedia.org/wiki/Programming_paradigm

Programming Word of the Day showcases a new term from computer science each week! Go to programmingwords.com to read more and subscribe to a monthly digest of new words!

PWOTD