Mash the brain with Forth?

Sometimes there is a desire to stretch your brain mired in object-oriented programming with something new and unusual. Of course, any functional programming language, for example, Haskell, Erlang, Lisp or OCaml, can come to the rescue in this situation. But now even with them it is hardly possible to surprise anyone. No, I want something completely different. In such a situation, Forth, a stacked programming language, rushes to our aid.



I will consider programming in Forth as part of the Ubuntu operating system. A list of compilers for other operating systems can be found here . You can also use the online Forth interpreter , but it does not work very well, but bearable. I will use gforth, which can be installed as follows:

sudo apt-get install gforth

Everything, as soon as we installed it, you can start in the Fort terminal in interactive mode by running the command:

gforth

But before writing "Hello world" I would like to talk a little about the differences between the syntax of this language and the usual one for us. Surely, many of you are accustomed to infix notation (when the operation sign is between the operands), some will not be scared by the prefix notation (when the operator is before the operands), but Fort went his own way - he uses the reverse Polish notation, i.e. postfix notation. For example, to add two numbers, you need to write like this:

1 2 +

As a result of this operation, we get 3. But this is far from all the features of the Fort. Initially, the core of this language is a kind of dictionary: a set of words with which we can perform some subset of operations on data. Moreover, the main unit of the language itself is the WORD. We can use existing words (DUP - duplicate the element lying on the top of the stack, SWAP - swap the two upper elements of the stack, and so on), and define our own. In general, it is the definition of one’s own words, through existing, and then more and more new words - this is the main programming mechanism on Fort.

Unusually it all sounds right? At first glance, this looks very complicated, but in fact, Fort is one of the simplest programming languages ​​in terms of implementing the compiler, and in terms of syntax elements of the language too.

Okay, the introduction seems to be voiced and now you can look at Hello world in this language:

." Hello world"

If you execute this command in interactive mode, then in response we get:

Hello world

But in fact, it does not show anything at all! In principle, like any other Hello world in any other programming language. Let's take a look at a few basic principles of writing a Forth program.

Forth is a stack language, which means that all transferred values ​​are pushed onto the stack, and when we perform some operations on them, they are popped out of the stack. For example, put four elements on the stack by doing the following in the Forth interactive shell:

1 2 3 4

Now, using the operator to extract the top element from the stack ("."). We will pull all the items from the stack:

 . . . .

We get the following conclusion:

4 3 2 1 ok

That is, we saw the FILO principle in action: the first element put on the stack was the last to be removed from the stack. Let's now try to perform the following arithmetic: (2 + 4) * 5 / 10. As a result, we should get 3. At Fort we can write this operation like this:

2 4 + 5 * 10 / .

We need the dot at the end of the expression in order to display the top element of the stack. At the time the point is completed, this element will be the result we need.

But just by such calculations you will not go far. Let's see how you can define your own words using the example of a word for squaring a number. To do this, we need to recall the word duplication of the top element of the DUP stack:

: POW DUP * . ;

That's all, we have defined our own word, which can be used like this:

4 POW

As a result, we get 16. Let's look in more detail at what we wrote here. First of all, after the colon, we need to give a name to our word, then after a space we begin to describe the body of our word. First we say that we need to duplicate the top element of the stack, and then multiply the top two elements. So, in fact, we got the word for exponentiation, you just need to remember that everything in Fort should be separated by a space, for example, such a record will not work:

:POW DUP * . ;

In fact, the mechanism for determining words is very flexible, with it you can create very complex words that can be used to obtain even more complex words.

Fort also has a branch operator (if) and a loop (do ... loop), but they can only be used in the definition of words. And there is one feature in using if. Let's try to write something using branching:

 : testif    
    dup 1 = if ." One" else
    dup 2 = if ." Two" else
    dup 3 = if ." Three"
 then then then drop ;

By the way, Fort is case insensitive, so dup and DUP are one and the same.

As you can see from the code, each time before comparing an element, we make a copy of it. This is necessary due to the fact that during the comparison the element is popped from the stack, that is, we cannot use it again. This can be verified by executing three commands in sequence:

1 2

<

.S

Here we first put two numbers on the stack, then perform the operation of comparing the two upper elements of the stack. She takes them out, compares them and puts the result on the stack. The third command displays the entire contents of the stack, which will be a single singular: -1. The minus one in Forth is Boolean "truth" and zero is "false."

Therefore, we duplicate the top element so that it can be used for comparison in the next branch. Basically, if we write like this:

: testif 
    dup 1 = if ." One" else
    dup 2 = if ." Two" else 
    3 = if ." Three"
then then then ;

then we get the same result, but this option is not accepted, since we degrade the readability of the code. Although we have reduced the code by two words (dup and drop (deleting the top element of the stack)), we have reduced readability.

Now let's take a look at the loop:

 : doloop 10 0 do cr ." Some text" loop ;

Here we print the text 10 times. First, we define the word, then in the reverse order (we have the same stack language), specify the boundaries of the stack (10 0 do), then perform some actions (in our case, we print the text each time with a new sink), and then indicate that this is a loop ( loop).

In general, we now own some set of syntactic elements of the Fort language in order to write something more or less complicated.

Let's define a word that would calculate the factorial of a given number:

: FACTORIAL recursive
dup 1 > if
    dup 1 - FACTORIAL *
else
    drop 1
endif ;
: OURLOOP
swap 1 + swap
do
    i . i ." ! = " i FACTORIAL . cr
loop ;

Now try our word in action in action:

17 0 OURLOOP

If this language interests you, then you can safely delve further into it by studying the literature and resources devoted to it. For example, I used the book “Starting FORTH” by Leo Brodie to prepare this article, which is available as a web resource and, by the way, is very pleasant to read.

This language does a good job of stretching the brain, pushing the boundaries of the idea of ​​programming no worse than Haskell, for example. And finally, a joke about Forth:

“The mystery of the Jedi Master’s speech is a secret - Fort is just an old programmer”