Mash the brain with Forth?

Sometimes there is a desire to stretch your brain, which is steeped in object-oriented programming, with something new and unusual. Of course, any functional programming language such as Haskell, Erlang, Lisp, or OCaml can come to the rescue in this situation. But now even they can hardly surprise anyone. No, I want something completely different. In such a situation, Forth is a stack-based programming language to help us.


')
I will consider programming on Forth within the framework of the Ubuntu operating system. A list of compilers for other operating systems can be found here . You can also use the online interpreter Forth, but it does not work very well, but is tolerable. I will use gforth, which can be set as follows:

sudo apt-get install gforth 

Everything, as soon as we installed it, can be launched in the Forth terminal interactively by running the command:

 gforth 

But before I write “Hello world” I would like to talk a little about the differences between the syntax of this language and the usual one. Surely, many of you are accustomed to the infix notation (when the operation sign stands between operands), some will not be scared by the prefix notation (when the operator is standing before the operands), but the Fort has gone its own way - it uses the reverse Polish notation, that is, the postfix notation. For example, to add two numbers, you need to write this:

 1 2 + 

As a result of this operation, we get 3. But this is not all 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. In this case, the main unit of the language itself is the WORD. We can use existing words (DUP - duplicate the element lying on top of the stack, SWAP - swap the top two elements of the stack, and so on), and define our own. In general, it is the definition of one’s words, through the available, and then more and more new and new words - this is the main mechanism of programming on Forte.

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

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

 ." Hello world" 

If we execute this command interactively, then in response we will receive:

 Hello world 

But in reality this shows nothing 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 passed values ​​are put on the stack, and when we perform some operations on them, they are removed from the stack. For example, put four elements on the stack by doing the following in the interactive shell Forth:

 1 2 3 4 

Now with the help of the operator to retrieve the top element from the stack ("."). We will pull all items from the stack:

  . . . . 

We get the following output:

 4 3 2 1 ok 

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

 2 4 + 5 * 10 / . 

We need a point at the end of the expression in order to output the top element of the stack. At the time of the "point", this element will be the result we need.

But only such calculations 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 * . ; 

Everything, we have defined our own word, which can be used like this:

 4 POW 

As a result, we get 16. Let's take a closer look at what we wrote here. First, after the colon, we need to give a name to our word, then after the 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 two top elements. Here, in fact, we got the word for the exponentiation, you just need to remember that everything in Forte needs to be separated by a space, for example, such a record will not work:

 :POW DUP * . ; 

In fact, the mechanism for defining words is very flexible, with the help of it you can create very complex words that can be used to produce even more complex words.

The Forte also has a branch statement (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, the Fort is case-insensitive, so dup and DUP are one and the same.

As can be seen 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 item is removed from the stack, that is, we cannot use it again. This can be verified by sequentially executing three commands:

 1 2 

 < 

 .S 

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

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

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

we will get the same result, but this option is not accepted, as we deteriorate the readability of the code. Although we have reduced the code by two words (dup and drop (removal of the top element of the stack)), but it will worsen readability.

Now let's look at the cycle:

  : 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 stack language), we indicate the stack boundaries (10 0 do), then we perform some actions (in our case, we print the text each time), and then we indicate that this is a cycle ( loop).

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

Let's define a word that calculates 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 ; 

And now let's try our word in action in action:

 17 0 OURLOOP 

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

This language is not bad knead the brain, pushing the scope of ideas about programming is no worse than Haskell, for example. And finally, a joke about Forth:

"Yoda Jedi Master's Speech is a mystery revealed - there is just an old programmer on Forte"