November 11, 2014 at 18:32Human Face Stack Programming
I think many of you have found articles and books on stack programming and the Forth language on the Internet. First, a wave of enthusiasm: how simple, logical, understandable and powerful! And why are these ideas so insignificant? Why do so few programmers really use languages like Fort? After some time, a wave of disappointment sets in: yes, an interesting idea, but how hard it is to read the source code, how dubious is the work with variables, strings and fractional numbers! An interesting toy, useful to a group of byte-mechanics, no more.
Often this is where it ends. But personally, I could not reconcile with the idea that elegant concatenative programming would remain in the shadow of other ideas. Yes, difficulty reading the source code. Yes, one line syndrome. Yes, each time to understand the algorithm, you have to translate the program in your imagination and imagine a stack while reading the source code. But are these really disadvantages that are necessarily inherent in stack languages and without which stack programming would cease to be stack? Is it really impossible to at least smooth out such shortcomings and make life easier for programmers? It turns out you can and should!
I first found the phrase “one line syndrome” in Barron's Introduction to Programming Languages. And although the term is not widely used, it expressively characterizes many languages.
One-line syndrome is characteristic of those languages that allow the free structure of the source code of the program and have short, and sometimes completely single-character keywords. The programmer is trying to “cram” as many keywords as possible into one line, which is why the programs do not look very readable. This syndrome is especially pronounced in APL and its descendants, in Brainfuck and, of course, in Fort. Look again at the illustration at the beginning of the post and count how many words there are on average per line.
But this is a solvable problem. In Fort, one-line syndrome appeared thanks to the addictions of Moore, who loves short and meaningful English words. Unfortunately, such words quickly end, and Moore does not like suffixes and prefixes (the so-called namespaces on the knee). Therefore, now the whole world is enjoying laconic hieroglyphs in the spirit of "@! C @ C! / MOD CR \ S P" stuck in one line. The problem is easily solved by selecting more successful words. Why write:
If I may:
Better yet:
But such an entry will be discussed below.
Another challenge is the management structure inside out. They are, of course, elegant in terms of ideas and implementation, but how is such code difficult to read:
In this example, the code blocks are elementary and the entire definition of the word is in full view. But it’s worth complicating it at least a little, as the program will seem unreadable to the author a week after writing.
The most common if and while from imperative programming rush to the rescue:
Maybe they are not so powerful and expandable, but they are very understandable and practical. And if you really want to create something like arithmetic if from the good old Fortran, the mechanism of code blocks at the top of the stack can be included in the language as an additional element and used not everywhere, but only where it is really necessary and justified. Fortunately, such a mechanism does not ask for a meal, and the implementation will not be too complicated.
As for the Fort, he has another problem with this: all the same words. Moore did not want to add identical ending words like END to complex constructions, so IF, DO and other words should be covered with their unique words. Therefore, we see all these IF ELSE THEN, which lead even experienced programmers to a dead end. If you really don’t want to complicate the parser and the word mechanism, why not enter words like END-IF? This is due to Moore's dislike of suffixes and prefixes. But, like the first problem, this point is also easily solved and is not a specific drawback of stack languages.
Due to a number of features of the program in Fort and other stacked languages, it is difficult to read and understand their essence. The thing is that every time you read a block of code in which a new word is entered, you have to interpret the program in your imagination and at every step imagine what elements are in what order on the stack and how the functions work with them. Needless to say, this is very tiring and unproductive in places. But the most unpleasant thing is that, in contrast to the previous features, which simply historically have been so unfortunate, the need for such an interpretation is an eternal companion to stack programming.
Of course, it is impossible to get rid of this drawback, but there are ways that can greatly facilitate the work of a programmer in reading the source code. And most importantly: the first steps have already been taken. Indeed, Fort programmers have adopted a certain notation to facilitate reading the source code:
Such comments make it easier to understand the numbers on the stack, their number and order. You do not need to strain your imagination every time to understand how many numbers and in what sequence you need to put on the stack before calling the function and how many numbers on the stack will remain as a result of the calculations. But here's the mystery: if such comments are very clear and useful, why do Fort programmers write them only at the beginning of the definition of a word, and even then not always? What religion prevents a drop dup swap rot from writing such an explanatory comment after the heap?
Back to the second code example. Of course, this is a case in a vacuum, but in real complex programs such comments will be in place:
There is no need for the programmer every time after all these swap, rot, and + to model in the head the order of numbers on the stack. You just need to run your eyes through the comments. But here is a new problem: the records
AND
are similar. It’s just that the first record was made in a declarative style, and the second in an imperative style. That is, lines in the program are constantly duplicated. With the same success, we can talk about the convenience of assembler: write code with a bunch of mov and ret on the left, and a = a + 1 in the comments on the right, and then talk about readability. Well yes, read the comments. But they can be invented to write so that when using any programming language they will be read very easily and clearly. Of course, it does not follow from this that such languages are convenient. They can be arbitrarily bad in terms of reading the source code.
There is a natural desire to combine (ab - abab) and over over. Indeed, if you write comments in a specific notation, then the compiler can parse them and manually add the necessary words to rearrange the elements of the stack. Comments in parentheses are completely ignored and are intended for human use only. Comments in square brackets are needed by both the person and the translator. The translator analyzes such comments in which the person writes what he needs, and not how to arrive at such a result. That is, you can work with the stack in a declarative style.
Consider the main, so to speak, varieties of such expressions:
1. define foo [bar] or [bar - foo]
After the name of the new function in square brackets, specify the number of arguments that should be on top of the stack. If when calling any function that requires three arguments, there will be only two arguments on the stack, then the traditional Fort system will throw an error: the stack is empty. But with such comments, the compiler will be able to “peek” into the comment and determine the names of the missing arguments: yeah, the argument r is not enough when calling the function foo. Agree, this is much more informative than the lean "stack is empty." Naturally, all of the above applies only to working in interactive mode, when the source code is available. After compilation, these comments will disappear, they are only needed for debugging and reading the source code. For comparison, error output in gforth:
2. [ab -> a]
The following types of expressions differ from purely descriptive ones with the word ->, which is similar to the word in classical comments. If the number of elements on the left is greater than the number of elements on the right, then the translator concludes: some elements need to be discarded, they are no longer needed. If the element is on the top of the stack, then this design is converted to drop, but if it is not, the translator first permutes the elements of the stack so that the garbage is on top of the stack, after which drop will be applied. Needless to say, how such a record makes life easier for the programmer if you need to remove, say, two elements from the middle of the stack. Let the translator decide how best to do this, the programmer only describes what he needs.
3. [ab -> ba]
Such expressions mean a rearrangement of elements: the number of elements to the left and to the right of the word -> is the same and the elements themselves are the same. It remains only to choose the optimal permutation scheme. Let the machine do it, people are so arranged that long chains of over swap drop rot introduce them into a stupor.
4. [ab -> aabb]
The number of elements on the left is less than the number of elements on the right. This suggests that some elements need to be duplicated. But what kind of elements are these and in what order should they be arranged, let the translator decide. It is inconvenient for a person to think in terms of swap dup rot dup.
5. [ab -> ab]
Nothing has changed, a purely descriptive construction. An application example is given below.
Naturally, in such declarative expressions you can use the usual comments:
Let us describe some of the words of Fort in a new form:
Imagine a stack consisting of 32-bit cells in which integers are stored. Such a stack is good for everyone: both the speed of arithmetic operations and the convenience of working with variable addresses. But if we need to multiply 3.14 by 4? Where to put the fractional number? If you organize the stack as a collection of 64-bit cells that store floating point numbers and store integers as fractional with a zero fractional part, then such advantages as the speed of arithmetic operations evaporate immediately.
We introduce the second stack for floating point numbers. The cells in it will be, say, 64-bit, but there will be fewer. All numbers without a point are placed on the vertices of the integer stack, and all numbers with a point (albeit with a zero fractional part) are stored in the float stack. That is, we can multiply the mentioned numbers as follows:
where * f multiplies fractional numbers (similar to + f, -f, and so on).
We also introduce a new declarative expression:
[stack: abc -> stack: abc]
Which takes elements from one stack and puts them in another:
The numbers 4.0 and 5.0 will appear in the fractional stack. The reverse operation "cuts off" the fractional part.
Define new words:
Similarly with the return stack.
The post turned out to be quite voluminous and sometimes controversial, so a significant part of the material will be in the second part. Again, the ideas and criticisms from the discussion will adjust the writing plan.
Often this is where it ends. But personally, I could not reconcile with the idea that elegant concatenative programming would remain in the shadow of other ideas. Yes, difficulty reading the source code. Yes, one line syndrome. Yes, each time to understand the algorithm, you have to translate the program in your imagination and imagine a stack while reading the source code. But are these really disadvantages that are necessarily inherent in stack languages and without which stack programming would cease to be stack? Is it really impossible to at least smooth out such shortcomings and make life easier for programmers? It turns out you can and should!
Problem One: Single Line Syndrome
I first found the phrase “one line syndrome” in Barron's Introduction to Programming Languages. And although the term is not widely used, it expressively characterizes many languages.
One-line syndrome is characteristic of those languages that allow the free structure of the source code of the program and have short, and sometimes completely single-character keywords. The programmer is trying to “cram” as many keywords as possible into one line, which is why the programs do not look very readable. This syndrome is especially pronounced in APL and its descendants, in Brainfuck and, of course, in Fort. Look again at the illustration at the beginning of the post and count how many words there are on average per line.
But this is a solvable problem. In Fort, one-line syndrome appeared thanks to the addictions of Moore, who loves short and meaningful English words. Unfortunately, such words quickly end, and Moore does not like suffixes and prefixes (the so-called namespaces on the knee). Therefore, now the whole world is enjoying laconic hieroglyphs in the spirit of "@! C @ C! / MOD CR \ S P" stuck in one line. The problem is easily solved by selecting more successful words. Why write:
: FOR-EXAMPLE OVER OVER + ROT ROT - * ;
If I may:
define for-exemple (a b -- {a+b}*{a-b})
over over
(a b -- a b a b)
+
(a b -- a b a+b=c)
rot rot
(a b c -- c a b)
- *
end
Better yet:
define for-exemple [a b -- r]
[a b -> a b a b]
+
[a b c (=a+b) -> c a b]
- /
end
But such an entry will be discussed below.
Problem Two: Code Inside Out
Another challenge is the management structure inside out. They are, of course, elegant in terms of ideas and implementation, but how is such code difficult to read:
: sign-test ( n -- )
dup 0 < [
drop "отрицательное"
] [
zero? [ "ноль" ] [ "положительное" ] if
] if print ;
In this example, the code blocks are elementary and the entire definition of the word is in full view. But it’s worth complicating it at least a little, as the program will seem unreadable to the author a week after writing.
The most common if and while from imperative programming rush to the rescue:
define sign-test [x]
[x -> x x]
0 > if
"Больше нуля"
else
"Меньше или равно нулю"
end-ifprint-string
end
Maybe they are not so powerful and expandable, but they are very understandable and practical. And if you really want to create something like arithmetic if from the good old Fortran, the mechanism of code blocks at the top of the stack can be included in the language as an additional element and used not everywhere, but only where it is really necessary and justified. Fortunately, such a mechanism does not ask for a meal, and the implementation will not be too complicated.
As for the Fort, he has another problem with this: all the same words. Moore did not want to add identical ending words like END to complex constructions, so IF, DO and other words should be covered with their unique words. Therefore, we see all these IF ELSE THEN, which lead even experienced programmers to a dead end. If you really don’t want to complicate the parser and the word mechanism, why not enter words like END-IF? This is due to Moore's dislike of suffixes and prefixes. But, like the first problem, this point is also easily solved and is not a specific drawback of stack languages.
Problem Three: Interpretation in the Head
Due to a number of features of the program in Fort and other stacked languages, it is difficult to read and understand their essence. The thing is that every time you read a block of code in which a new word is entered, you have to interpret the program in your imagination and at every step imagine what elements are in what order on the stack and how the functions work with them. Needless to say, this is very tiring and unproductive in places. But the most unpleasant thing is that, in contrast to the previous features, which simply historically have been so unfortunate, the need for such an interpretation is an eternal companion to stack programming.
Of course, it is impossible to get rid of this drawback, but there are ways that can greatly facilitate the work of a programmer in reading the source code. And most importantly: the first steps have already been taken. Indeed, Fort programmers have adopted a certain notation to facilitate reading the source code:
( до -- после )
Such comments make it easier to understand the numbers on the stack, their number and order. You do not need to strain your imagination every time to understand how many numbers and in what sequence you need to put on the stack before calling the function and how many numbers on the stack will remain as a result of the calculations. But here's the mystery: if such comments are very clear and useful, why do Fort programmers write them only at the beginning of the definition of a word, and even then not always? What religion prevents a drop dup swap rot from writing such an explanatory comment after the heap?
Back to the second code example. Of course, this is a case in a vacuum, but in real complex programs such comments will be in place:
define for-exemple (a b -- {a+b}/{a-b})
over over
(a b -- a b a b)
+
(a b -- a b a+b=c)
rot rot
(a b c -- c a b)
- /
end
There is no need for the programmer every time after all these swap, rot, and + to model in the head the order of numbers on the stack. You just need to run your eyes through the comments. But here is a new problem: the records
(a b -- a b a b)
AND
over over
are similar. It’s just that the first record was made in a declarative style, and the second in an imperative style. That is, lines in the program are constantly duplicated. With the same success, we can talk about the convenience of assembler: write code with a bunch of mov and ret on the left, and a = a + 1 in the comments on the right, and then talk about readability. Well yes, read the comments. But they can be invented to write so that when using any programming language they will be read very easily and clearly. Of course, it does not follow from this that such languages are convenient. They can be arbitrarily bad in terms of reading the source code.
There is a natural desire to combine (ab - abab) and over over. Indeed, if you write comments in a specific notation, then the compiler can parse them and manually add the necessary words to rearrange the elements of the stack. Comments in parentheses are completely ignored and are intended for human use only. Comments in square brackets are needed by both the person and the translator. The translator analyzes such comments in which the person writes what he needs, and not how to arrive at such a result. That is, you can work with the stack in a declarative style.
Consider the main, so to speak, varieties of such expressions:
1. define foo [bar] or [bar - foo]
After the name of the new function in square brackets, specify the number of arguments that should be on top of the stack. If when calling any function that requires three arguments, there will be only two arguments on the stack, then the traditional Fort system will throw an error: the stack is empty. But with such comments, the compiler will be able to “peek” into the comment and determine the names of the missing arguments: yeah, the argument r is not enough when calling the function foo. Agree, this is much more informative than the lean "stack is empty." Naturally, all of the above applies only to working in interactive mode, when the source code is available. After compilation, these comments will disappear, they are only needed for debugging and reading the source code. For comparison, error output in gforth:
: add-x-y ( x y -- x+y ) compiled
+ ; ok
4 5 add-x-y . 9 ok
4 add-x-y .
:6: Stack underflow
4 >>>add-x-y<<< .
Backtrace:
$7FF17383C310 +
ok
2. [ab -> a]
The following types of expressions differ from purely descriptive ones with the word ->, which is similar to the word in classical comments. If the number of elements on the left is greater than the number of elements on the right, then the translator concludes: some elements need to be discarded, they are no longer needed. If the element is on the top of the stack, then this design is converted to drop, but if it is not, the translator first permutes the elements of the stack so that the garbage is on top of the stack, after which drop will be applied. Needless to say, how such a record makes life easier for the programmer if you need to remove, say, two elements from the middle of the stack. Let the translator decide how best to do this, the programmer only describes what he needs.
3. [ab -> ba]
Such expressions mean a rearrangement of elements: the number of elements to the left and to the right of the word -> is the same and the elements themselves are the same. It remains only to choose the optimal permutation scheme. Let the machine do it, people are so arranged that long chains of over swap drop rot introduce them into a stupor.
4. [ab -> aabb]
The number of elements on the left is less than the number of elements on the right. This suggests that some elements need to be duplicated. But what kind of elements are these and in what order should they be arranged, let the translator decide. It is inconvenient for a person to think in terms of swap dup rot dup.
5. [ab -> ab]
Nothing has changed, a purely descriptive construction. An application example is given below.
Naturally, in such declarative expressions you can use the usual comments:
dup rot +
[a b -> a b (a + b)]
Let us describe some of the words of Fort in a new form:
define dup [x]
[x -> x x]
end
define drop [x]
[x -> ]
end
define swap [x y]
[x y -> y x]
end
define over [x y z]
[x y -> x y x]
end
define rot [x y z]
[x y z -> y z x]
end
Problem Four: Floating-Point Numbers
Imagine a stack consisting of 32-bit cells in which integers are stored. Such a stack is good for everyone: both the speed of arithmetic operations and the convenience of working with variable addresses. But if we need to multiply 3.14 by 4? Where to put the fractional number? If you organize the stack as a collection of 64-bit cells that store floating point numbers and store integers as fractional with a zero fractional part, then such advantages as the speed of arithmetic operations evaporate immediately.
We introduce the second stack for floating point numbers. The cells in it will be, say, 64-bit, but there will be fewer. All numbers without a point are placed on the vertices of the integer stack, and all numbers with a point (albeit with a zero fractional part) are stored in the float stack. That is, we can multiply the mentioned numbers as follows:
4.0 3.14 *f
where * f multiplies fractional numbers (similar to + f, -f, and so on).
We also introduce a new declarative expression:
[stack: abc -> stack: abc]
Which takes elements from one stack and puts them in another:
4 5
[integer: z1 z2 -> float: z1 z2]
2 times print-float end-times
The numbers 4.0 and 5.0 will appear in the fractional stack. The reverse operation "cuts off" the fractional part.
Define new words:
define integer->float [x]
[integer: x -> float: x]
end
define float->integer [x]
[float: x -> intger: x]
end
Similarly with the return stack.
The post turned out to be quite voluminous and sometimes controversial, so a significant part of the material will be in the second part. Again, the ideas and criticisms from the discussion will adjust the writing plan.