Build for free

Nylas
Blog
Developer how-tos
A small introduction to Stack-Oriented programming

A small introduction to Stack-Oriented programming

Nov 08, 2022 • 6 min read

Jump to section

Stack-Oriented programming is a paradigm that relies on a stack machine model for passing parameters.

Stack-Oriented programming uses Last In, First Out (LIFO). So the last item added to a stack is the first item removed.

Forth was developed in 1970 and it’s considered the first Stack-Oriented Programming Language.

Let’s understand Stack-Oriented programming concepts?

Reverse Polish Notation (RPN) → First operands, then operators.
Stack Manipulation → As everything resides on the stack, we need to use special keywords to manipulate it.
Language Extension → We can create words (much like functions) to extend the functionality of our applications.

What do we need? (RPN)

In this post, we’re going to explore some key fundamentals of Stack-Oriented programming using examples in two of the most known languages.

Forth (1970) → If we’re on a Mac, the best way is to use homebrew and type on the terminal window:

$ brew install gforth

For other systems, you can refer to the download page.

Factor (2003) → If we’re on a Mac, the best way is to use homebrew and type on the terminal window:

$ brew install --cask factor

Then open up your zprofile:

$ nano ~/.zprofile

And type the following and the bottom:

export PATH=/Applications/factor:"$PATH"

Once that’s done, we need to make it available for all new terminal windows:

$ source ~/.zprofile

For other systems, you can refer to the download page.

Reverse Polish Notation (Forth example)

Let’s open up the gforth interpreter to visualize how RPN works. On the terminal type:

$ gforth

And then once inside the interpreter type the following:

4 5 + 2 -
.

We are saying, grab the number four and the number five and then apply the plus operator, the result will remain on the stack. On the second line, we read the value from the stack which is 9 and the number two and apply the minus operator. On the third line, we’re reading the value from the stack, which is going to be seven.

Stack Manipulation (Factor example)

We need to work with the stack, which means that we need some special operator to help us. Let’s open the Factor interpreter by typing on the terminal:

$ factor

Once inside the interpreter, type the following:

5 dup * .
1 2 3 pick . . . .
3 5 drop 2 + .

On the first line we called the number five and then called the dup keyword. The dup keyword will duplicate the top of the stack. Once we have five and five on the stack we’re going to apply the multiplication operator and finally we will display the result by calling the stack using the period.

On the second line, we call one, two and three and then call the pick keyword. The pick keyword will duplicate the last item into the top slot and then by using period four times, we’re going to get all the numbers inside the stack.

On the third line, we have three and five, but when we call the drop keyword, five gets removed from the stack, so we only have three, then we grab two and the plus operator, giving us back the result of five when calling the stack using the period operator.

Language Extension (Forth example)

We can create new words in a very expressive way. They are way simpler than functions in other languages. Let’s create a file called double_expo.fth inside a Forth_Codes folder:

: EXPO DUP * ;
\ Duplicates the top of the stack and then multiplies both values
: DOUBLE 2 * ;
\ Multiplies the top of the stack by 2
: DOUBLE_EXPO EXPO DOUBLE  CR . ;
\ Call the two methods passing the params between them

In order to load this, we just need to call it from the Forth environment:

include double_expo.fth

5 double_expo

We’re declaring the word EXPO which takes the value from the stack, duplicates it and multiplies both.

The word DOUBLE will take the value from the stack and multiply it by two.The word DOUBLE_EXPO will call the words EXPO and DOUBLE to perform the operations and finally will use CR to perform a carriage return and period will return the value from the stack, which means the value 50.

What does a complete application look like? (Factor example)

We’re going to create a Factor application that will request a number and return a Fibonnaci sequence, for example: If we provide the number five, then the output will be:

0 1 1 2 3 5

Inside the Factor environment, type the following commands:

USE: tools.scaffold

“fibo” scaffold-work

This is going to create a fibo folder inside Factor’s installation folder. On a Mac this would be:

/Applications/factor/work/fibo

And inside the fibo folder, we will find a fibo.factor file that we need to update with the following source code:

! Copyright (C) 2022 Your_Name.
! See http://factorcode.org/license.txt for BSD license.
USING: math prettyprint kernel io math.parser command-line namespaces sequences ;
IN: fibo

<PRIVATE
: ask-number ( -- ) "Enter a number: " print ;
: read-number ( -- n ) readln string>number ;
: list_fibo ( x -- ) 1 0 pick 1 + [ dup . over over + rot drop ] times 3drop ;
PRIVATE>

: fibo ( -- ) ask-number read-number list_fibo ;
: fibo-run ( -- ) fibo ;

MAIN: fibo-run

Let’s explore the source code. The word fibo-run will call the word fibo. Then, the word fibo will call the words ask-number read-number and list_fibo.

The word ask-number will request a number to be entered. And the word read-number will read that number and convert it into a numeric type.

The word list fibo will receive the number along with 1 and 0. So we’re going to have 5 1 0. The word pick will grab the 5 and add 1 to it, so it becomes 6; which is the number of times we need to loop over the results. Although keep in mind that in the stack we still have 5 0 1.

Inside the loop (between brackets), the word dup will duplicate the current value on the stack (1) and then printed on the screen. The word over will take the middle value and duplicate it, we call it twice so that we can sum the values. 5 0 1 becomes 5 0 1 0 and then 5 0 1 0 1. After the sum, it becomes 5 0 1 1. The word rot rotates the top elements and the word drop gets rid of the last value, so the stack becomes 5 1 1. Finally 3drop will get rid of the 3 elements that remain in the stack.

In order to run this code, we need to open the Factor GUI application (which is called the Listener). And the select Factor → Run Factor Source… or press Command + Option + O.