Конкатенативное программирование — парадигма программирования, в которой композиция функций выражается через конкатенацию строк. Примеры языков: FORTH, Joy, Factor.
Т.е. пусть у нас есть две программы P1 и P2, конкатенация этих двух программ
P1 P2 будет выражать применение P2 к результату выполнения P1.
В конкатенативных языках явных переменных нет, данные передаются неявно, через стек. Программа представляет собой последовательность операторов, каждый из которых выполняет какую либо операцию со стеком. Частный случай: константы — это тоже операторы, которые на стек кладут соответствующее значение.
В конкатенативных языках программирования принято записывать стек, растущий слева направо, причём верхушка стека расположена справа.
Действия операторов принято записывать как
оператор : ... стек до => ... стек после
Например:
+ : ... x y => ... (x+y)
Программа пишется в обратной польской записи или постфиксной записи: сначала записываются операнды, а потом сама операция.
Местность (арность) операции, функции — количество операндов (аргументов) у неё.
Коместность (коарность) — количество возвращаемых значений.
Поскольку местность каждой операции фиксирована, скобки не нужны.
Пример.
Выражение в обычной (инфиксной записи):
(2 - 1) * (3 + 4)
Выражение в постфиксной записи (обратной польской):
2 1 - 3 4 + *
-: 2 и 1,+: 3 и 4,*: 2 1 -, 3 4 +.Можно добавить скобки для наглядности, но их никто не ставит:
((2 1 -) (3 4 +) *)
Местность констант 0 (не принимают аргументов), коместность — 1.
константа : ... => ... константа
Обратная польская запись допускает простую и эффективную реализацию:
Пример:
Стек Программа
... 2 1 - 3 4 + *
↑
... 2 2 1 - 3 4 + *
↑
... 2 1 2 1 - 3 4 + *
↑
... 1 2 1 - 3 4 + *
↑
... 1 3 2 1 - 3 4 + *
↑
... 1 3 4 2 1 - 3 4 + *
↑
... 1 7 2 1 - 3 4 + *
↑
... 7 2 1 - 3 4 + *
↑
программа завершилась
Функции в FORTH принято называть статьями, хранилище функций — словарём.
Программа на языке FORTH состоит из последовательности слов, словом может быть или целочисленная константа, или некоторое имя. Часть слов предопределены (встроены в язык), часть определяются пользователем в виде статей:
Определение статьи выглядит так
: ИМЯ слова… ;
Знак : начинает определение, знак ; — заканчивает.
Для вызовов функций вводится второй стек — стек возвратов. В основном стеке, стеке данных находятся значения, которыми обмениваются операции, в классическом FORTH’е это целые числа. В стеке возвратов хранятся адреса команд в словарных статьях.
Интерпретатор работает в следующем цикле:
Некоторые встроенные слова FORTH:
+, -, *, /.DUP : ... x => ... x x -- дублирует верхушку стека
DROP : ... x => ... -- удаляет слово с верхушки стека
SWAP : ... x y => ... y x -- обменивает местами два слова на верхушке
ROT : ... x y z => ... y z x -- поднимает на верхушку третий по счёту элемент
OVER : ... x y => ... x y x -- копирует подвершину на верхушку
IF ... THEN — если на вершине не ноль, выполняются слова между IF и THEN,
иначе ничего не делается. В обоих случаях число со стека снимается.IF ... ELSE ... THEN — если на верхушке не ноль, он снимается с верхушки
и выполняются слова между IF и ELSE, иначе ноль снимается с верхушки
и выполняются слова между ELSE и THEN.WHILE ... WEND — цикл с предусловием повторяется до тех пор, пока
на верхушке не ноль.. : ... x => ... -- печатает число, снимая его со стека
Пример программы на FORTH. Функция (слово) hypot вычисляет гипотенузу прямоугольного
треугольника:
\ square : ... x => ... x²
: square DUP * ;
\ hypot : ... x y => ... √(x²+y²)
: hypot square SWAP square + SQRT ;
Выполнение слова square:
Стек Программа
--------------------------
... x DUP * ;
↑
... x x DUP * ;
↑
... x² DUP * ;
↑
происходит возврат из square
Выполнение слова hypot:
Стек Программа
--------------------------
... x y square SWAP square + SQRT ;
↑
Когда слово square вызывается, на стек возвратов кладётся указатель
на слово SWAP в определении слова hypot.
Стек Программа
--------------------------
... x y² square SWAP square + SQRT ;
↑
... y² x square SWAP square + SQRT ;
↑
... y² x² square SWAP square + SQRT ;
↑
... y²+x² square SWAP square + SQRT ;
↑
... √(y²+x²) square SWAP square + SQRT ;
↑
происходит возврат из hypot
Пример, характерный для FORTH:
: 2 3 ;
2 2 * .
Она выведет 9, а не 4.
: + - ;
10 5 + .
Выведет 5, а не 15.
Слово с переменным числом параметров:
: SUM DUP WHILE + SWAP DUP WEND DROP ;
Сложит все числа на стеке до ближайшего нуля.
1 2 3 0 4 5 6 SUM => 1 2 3 15
===== ~~~~~~~ ===== ~~
1 2 3 0 4 5 6 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 4 5 6 6 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 4 5 6 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 4 11 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 11 4 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 11 4 4 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 11 4 4 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 11 4 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 0 15 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 15 0 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 15 0 0 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 15 0 0 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 15 0 DUP WHILE + SWAP DUP WEND DROP ;
↑
1 2 3 15 DUP WHILE + SWAP DUP WEND DROP ;
↑