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:
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:
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:
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:
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:
This is going to create a fibo folder inside Factor’s installation folder. On a Mac this would be:
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 ;
: 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 ;
: fibo ( -- ) ask-number read-number list_fibo ;
: fibo-run ( -- ) fibo ;
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.
Once the source code is loaded, we need to type:
This will return the value:
0 1 1 2 3 5 8 13 21 34 55
Here’s a diagram to better visualize the flow:
Hope you like it, Stack-Oriented programming is strange but very useful to learn.
Please enter your email address and receive the latest updates.
Blag aka Alvaro Tejada Galindo
Blag aka Alvaro Tejada Galindo is a Senior Developer Advocate at Nylas. He loves learning about programming and sharing knowledge with the community. When he’s not coding, he’s spending time with his wife, daughter and son. He loves Punk Music and reading all sorts of books.