Factor pt. 1 - Concatenative basics

As I mentioned in my previous post, concatenative programming (CP) is cool in theory, but it is different enough that it requires breaking out of the standard imperative mindset. Concatenative advocates claim (quite boldly) that thinkng in CP enforces clean code because ugly code is never more efficient. Let me show you how to think concatenatively so you can decide for yourself.

Terminology and language choice

Things I should've mentioned in the first paragraph

In my CP tutorials I will be using a language called Factor, for the following reasons:

• As far as I'm aware, Factor is the most developed concatenative language
• It has a lot of useful high level libraries
• It is one of two concatenative languages I can program in
• It has syntax highlighting on dev.to
• You can easily download it for most systems
• It has a great interactive environment with all docs built in

Factor can be used as a high level language but exposes low level functionality for the brave folks and compiles to efficient machine code. If you prefer something meant for low level programming try Forth - much older but still well documented and with similar syntax.

Speaking of syntax: Factor doesn't have much of it. In CP there are only functions operating on the program's state, so there is no need for any operators, parentheses or indentation. Because of that Factor functions are called "words" and their names can contain any non-white characters. Every program is just a sequence of words separated with white characters.

Why don't you go and install Factor and open Listener for yourself so that we can take a look at some code!
If you have any burning questions regarding any Factor word just type \ questionable-word help into the Listener and you will get an interactive help that will hopefully satisfy your appetite for information.

The stack

Our lord and saviour

Factor is a stack-based language, meaning its primary way of storing data is on a stack. Factor's stack is like a pile of books: you can put values on top of it and take values from the top. It is easy to access objects near the top of the stack, but trying to operate on deeper stuff is risky. Factor's stack doesn't consist of books though, it holds values like integers, strings or arrays.

In my code examples I will show code and it's effect on the stack like this:

Code will be shown here
! S: The final stack state from bottom to top goes here

So code that puts some literal integers onto the stack will look like this:

9 3 2 5 1 2 5 0
! S: 9 3 2 5 1 2 5 0

Any number in Factor is a word that pushes this number onto the stack. In this example 9 was executed first so number 9 is at the bottom of the stack and 0 was executed last so number 0 is at the top. ! is a word indicating that the rest of the line is a comment and shouldn't be executed.

So far we've seen how to put numbers on a stack. To operate on them Factor offers all the usual arithmetic operations: +, -, *, / and so forth. To add 1 and 2 together you would write:

1 2 +
! S: 3

"What is that weird order?" you might ask? It's called Reverse Polish Notation and it's the natural way of ordering stuff for a stack-based language. What the + word does is take two values on top of the stack and replace them with their sum. It is not an operator - it doesn't care what words are around it. It only operates on the stack, so in order to add 1 and 2 they have to already be on the stack.

This order - operands first and then operator - facilitates arithmetics without parenthesis. Any order of operations is obvious from the order in which those operations are written. No ambiguity, no precedence rules, just execution from left to right. For example, an operation (3 + 4) * 2 - 5 would be written as 3 4 + 2 * 5 -, and 3 + 4 * (2 - 5) would be 3 4 2 5 - * +. If you have the Listener running (or rather - listening) you can enter each of these examples word by word and see how it ends up with the correct answer in the correct order. You can get accustomed to the idea by trying it out on a piece of paper as well.

Stack shuffling

Getting things where we need them

Because the stack is used for most of the operations, the values we need to operate on at a given moment aren't always in the right positions. This is where the stack shuffling words come into play: they are used to rearrange the top of the stack to fit our needs. Most popular shuffling words include:

• dup ( a -- a a ) - duplicates the top value on the stack
• drop ( a -- ) - removes the top value from the stack
• swap ( a b -- b a ) - swaps two values on top of the stack
• over ( a b -- a b a ) - copies the second value from the top and puts it on top of the stack
• nip ( a b -- b ) - removes the second value from the top of the stack

Each of them has a version that works on two values at once:

• 2dup ( a b -- a b a b)
• 2drop ( a b -- )
• 2swap ( a b c d -- c d a b)

And so on...

All of these are used constantly in Factor programs. You want to square the number on top of the stack?

3 dup *
! S: 9

You want to subtract the number on top of the stack from 10?

3 10 swap -
! S: 7

You want to get rid of all the stuff you put on the stack when playing with the Listener? Just dump a couple of 4dups and enjoy the clean slate!

Defining new words

Factorisation incoming

In CP it is very easy to take any piece of code and define a new word that executes it. You don't have to care about giving your operators all operands or naming variables, after all you can split the code at (almost) any point and both parts would be valid Factor programs. That's where the name concatenative comes from.

Defining a new word uses a syntax word :. Syntax words work differently from normal words - they work with what is written after them instead of with the stack. They introduce the tiny amount of syntax Forth has and are usually used to define new words. Syntax of : is : name stack-effect body ;. Let's see this on the squaring example from before:

: sq ( x -- x^2 ) dup * ;
3 sq
! S: 9

• : is the syntax word that parses the definition
• ( x -- x^2 ) is a stack effect declaration. I will talk about them in a minute
• dup * is the body of the word. These words will be invoked each time sq is called
• ; indicates the end of the : definition. Code after the semicolon resumes normal interpretation

You should define a new word every time:

• There is a piece of code you are using in three or more places
• You feel the need to use a comment to explain what a piece of code does
• Your word definition has more than three lines

This is called factoring and it is the essence of writing clean and self-commenting code. Factor is optimised for calling words from within words so don't worry about inefficiency.

Stack effects

A wannabe type system

You have definitely noticed the syntax ( x y -- z ) used in a couple of places in this article and maybe you have even guessed what it means. It's called a "stack effect description" and it shows what effect the function has on the stack. It is required in every : definition to make compilation more efficient and to make sure you know what you are doing with your code.

The part before the -- needs to include a word for every stack element expected by the word and the part after it includes a word for every stack element left by the word, including all expected elements. You have already seen a lot of examples in the stack-shuffling section. The stack effect description can be as verbose as you like, ranging from ( url http-server -- post-request ) to ( a b -- c ). It is only required that the number of words matches affected elements, but good stack effects make the code cleaner and more understandable.

Conclusion

And what's coming next

This article explained the very basics of concatenative programming in Forth: literals, stack shuffling and word definitions. In the next tutorial I will show you how Factor handles control flow and collections such as arrays and hashtables. Stay tuned for the next week!