Crumble the brain using Forth?

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



I will consider programming in Forth within the operating system Ubuntu. The 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 tolerable. I use gforth, which can be set as follows:

the

sudo apt-get install gforth

As soon as we have it installed, you can run in terminal Fort in interactive mode using the command:

the

gforth

But before you can write "Hello world" I would like to tell you a bit about the differences of language syntax from the usual us. Certainly, many of you are accustomed to infix records (when the token transaction is between the operands), some is not frightened a prefix entry (when the operator is before the operands), but the Fort went on his way — he uses reverse Polish notation, that is, the Postfix entry. For example, to add two numbers, you need to write:

the

1 2 +

The result of this operation we get 3. But this is not all the features of the Fort. Initially, the core of the language consists of a vocabulary: a set of words with which we can perform a subset of operations on the data. Thus the basic unit of language is actually a WORD. We can use existing words (DUP — duplicate lying on the top of the stack element SWAP — swap top two stack element, and so on) and define your own. In General, the definition of his words, through existing and then new and new words — this is the basic mechanism for programming on Forte.

It all sounds unusual, isn't it? At first glance, it looks very difficult, but actually the Fort is one of the simplest programming languages in terms of compiler implementation, and in terms of the syntactic elements of the language, too.

Okay, like the introductory announced and now you can see Hello world in this language:

the

." Hello world"

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

the

Hello world

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

Forth is a stack-based language, this means that all the transmitted values are placed on the stack, and when we perform some operations on them, then they are removed from the stack. For example, put in a stack of four elements using the following in an interactive shell Forth:

the

1 2 3 4

Now with the help of the operator extracting the top element from the stack ("."). We pull out all elements from the stack:

the

 . . . .

Get the following output:

the

4 3 2 1 ok

We have seen in action the principle of FILO: the first element put on the stack, was removed from the stack last. Let us now try to perform the following arithmetic operation: (2 + 4) * 5 / 10. As a result, we have to get 3. At Forte we the operation can be written as follows:

the

2 4 + 5 * 10 / .

The point at the end of the expression we need in order to bring the topmost element of the stack. At the time of execution "points" this item is just the result we need.
But only these calculations will not get far. Let's see how you can define your own words for example words for the construction of the square. For this we need to recall the word duplicate top stack element DUP:

the

: POW DUP * . ;

All, we have defined a private word, which can be used like this:

the

4 POW

As a result, we get 16. Let us consider in more detail what we have written here. The first thing after the colon we need to give a name to their word, then after the break we start to describe the body of his words. First, we say that we need to duplicate the top element of the stack, and then multiply the top two elements. Here, in fact, we got the word for the exponentiation, we need to remember only that all in the Fort should be separated by a space, for example, such recording will not work:

the

:POW DUP * . ;

In fact, the word engine is very flexible, with it you can create very complex words that can be used to produce more complex words.

In the Fort there is also a branching statement (if) and loop (do... loop), but you can only use them in the definition of the words. And there is one feature in the use if. Let's try to write something using branching:

the

 : 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 not case sensitive, so dup and DUP is the same.

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

the

1 2

the

<

the

.S

Here we first put the two numbers on the stack, then perform the operation of comparing the top two stack elements. She takes them, compares and puts the result onto the stack. The third command lists all the contents of the stack, which will be one single number -1. Minus one in Forth is Boolean "true" and zero is "false".

Therefore, we duplicate the top item in order that it could be used for comparison in the following branches. In principle, if we would write:

the

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

you will get the same result, but this option is not adopted, as we deteriorate the readability of the code. Even though we have reduced the code to two words (dup and drop (delete top element of the stack)), but will worsen the readability.

Now let's consider the cycle:

the

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

Here we print the text 10 times. We first define the word, then in reverse order (we have the same stack-based language) specify the boundaries of the stack (10 0 do) then execute some action (in our case every time with new effluent output text), and then specify that it is a cycle (loop).

In General, we now own some set of syntax elements of the forth language in order to write something more or less complex.

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

the

: recursive FACTORIAL
dup 1 > if
dup 1 - FACTORIAL *
else
drop 1
endif ;

: OURLOOP
swap 1 + swap
do
i . i ." ! = " i FACTORIAL . cr
loop ;

And now try our word in action in action:

the

17 0 OURLOOP

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

This language nicely stretches the brain, broadens the scope of knowledge of programming is not worse, than Haskell, for example. And finally, a joke about Forth:

"Yoda the Jedi master's speech the secret is out — Forte programmer simply old there is it"

Article based on information from habrahabr.ru