Конкатенативный язык программирования

Конкатенативный язык программирования — язык программирования, основанный на том, что конкатенация двух фрагментов кода выражает их композицию. В таком языке широко используется неявное указание аргументов функций (см. бесточечное программирование), новые функции определяются как композиция функций, а вместо аппликации применяется конкатенация^[1]. Этому подходу противопоставляется аппликативное программирование.

Многие конкатенативные языки используют постфиксную нотацию и стек для хранения аргументов и возвращаемых значений операций, поэтому под конкатенативными языками обычно подразумевают стековые. Однако конкатенативные языки могут быть построены и на других принципах, поэтому термины стековый язык и конкатенативный язык не являются синонимами.

Конкатенативные языки отличаются простотой, эффективностью и удобством в реализации, поэтому самые популярные языки этого типа используются в программируемых калькуляторах и для встраивания в небольшие микропроцессорные системы. Например, конкатенативный язык RPL применяется в программируемых микрокалькуляторах Hewlett-Packard HP-28 и HP-48. Язык программирования Forth был реализован на множестве процессоров с очень ограниченными вычислительными возможностями^[2], к примеру, он использовался на компьютере Jupiter ACE с базовой оперативной памятью всего лишь в 1 Кб. Однако из-за своей непривычности и трудности с чтением исходного кода программ конкатенативные языки программирования так и остались нишевыми.

Самый распространённый конкатенативный язык — это язык описания страниц PostScript, ограниченное подмножество которого применяется в PDF. Его интерпретатор встроен во многие высокопроизводительные принтеры.

Язык программирования называется конкатенативным если он удовлетворяет следующим требованиям:

• Элементарное правильно построенное выражение языка — это унарная функция с одним аргументом и одним возвращаемым значением.
• Если X и Y — правильно построенные выражения, то конкатенация X и Y также правильно построена.
• Если Z — конкатенация X и Y, то значение Z — это композиция функций X и Y.

В конкатенативном языке каждое выражение - это функция. Отсутствует специальная операция аппликации, для применения функции к аргументам достаточно поставить имя функции рядом с аргументами, то есть произвести текстовую "склейку" (конкатенацию). Новые функции также определяются конкатенацией, то есть просто последовательностью имён других функций.

Пусть даны функции foo от двух аргументов и bar от одного аргумента. Для того, чтобы применить foo к аргументам, в префиксной нотации достаточно составить подобное выражение:

foo 4 5

Теперь применим функцию bar к результату функции foo:

bar foo 4 5

Наконец, определим функцию baz как конкатенацию трёх функций:

define baz
    bar foo 4
end-define

Выражение baz 8 эквивалентно выражению bar foo 4 8. То есть имя любой функции можно заменить на текст её определения и получить правильное выражение. Этот простой принцип определяет специфику конкатенативных языков, их достоинства и недостатки.

Для того, чтобы конкатенация фрагментов кода всегда выражала их композицию, в языке должны быть функции только от одного аргумента.^[3] В этом случае можно отказаться от явного указания аргумента, поэтому применив единообразную префиксную или постфиксную нотацию можно создать такой язык программирования, в котором конкатенация фрагментов кода выражает их композицию, то есть конкатенативный язык.

Один из простых и эффективных способов реализации этого подхода - применение стека. Функции берут аргументы из стека и помещают результат в стек. Поэтому можно сказать, что в конкатенативных стековых языках программирования функции принимают один аргумент - состояние стека, и возвращают новое состояние стека.^[4] В этих языках обычно используется постфиксная нотация, поскольку стек работает по принципу LIFO.

Есть и другие способы. Например, функция принимает текст программы и возвращает его же с некоторыми изменениями, которые отражают её работу. На этом принципе можно построить очень простой и гибкий гомоиконический язык.^[5] Возможно создать язык вокруг принципа конвейера UNIX: каждая функция принимает строку и возвращает новую строку после обработки.^[6] В отличие от предыдущего принципа, передаваемый функции текст содержит только аргументы, а не всю программу целиком. Эти способы могут работать как с префиксной, так и с постфиксной нотацией.

Вместо стека можно использовать и другие структуры данных, такие как очередь или дек (двухсторонняя очередь)^[7].

Идея конкатенативного языка заключается в следующем: все выражения - это функции, которые принимают некую одну и ту же структуру данных и возвращают её новое состояние. Эта структура данных (стек, дек, очередь, текстовая строка и т.д.) играет роль клея для "склеивания" функций в программу, в ней хранится состояние программы. Этот подход определяет достоинства и недостатки конкатенативных языков.

Достоинства:

• простая и эффективная реализация
• очень простой синтаксис
• лаконичная запись выражений
• удобство в создании предметно-ориентированных языков
• возможности функционального программирования: чистые функции, преобразование функций от нескольких аргументов в функцию от одного аргумента и т.д.
• удобство в применении метода программирования снизу вверх

Недостатки:

• Непривычность из-за повсеместного (за редкими исключениями) использования префиксной или инфиксной нотаций
• Трудности с составлением сложных математических выражений
• Неудобства при работе с функциями от многих аргументов

Первым конкатенативным языком высокого уровня был Forth, разработанный Чарлзом Муром в конце 1960-х — начале 1970-х годов. Он использовал бестиповый стек и отличался простотой реализации и высокой эффективностью, что позволило реализовать трансляторы даже при крайне ограниченных вычислительных ресурсах. Forth существенно повлиял на последующие конкатенативные языки.

Преподаватель и программист Манфред фон Тун (Manfred von Thun) Университета Ла Троба под влиянием известной лекции Джона Бэкуса «Можно ли освободить программирование от стиля фон Неймана?» разработал стековый язык программирования Joy и заложил теоретические основы конкатенативного программирования. Именно язык Joy впервые был назван конкатенативным.

Под влиянием Forth и Joy Слава Пестов в 2003 году создал стековый язык программирования Factor. Он позиционируется как «практический стековый язык программирования». Позже были разработаны стековые конкатенативные языки Cat и Kitten, отличающиеся статической типизацией. Другой современный конкатенативный язык, min, отличается минималистичным синтаксисом и очень компактной реализацией (около 1 мегабайта), он используется в генераторе сайтов HastySite.

Из специализированных стековых языков наиболее известны PostScript, который используется для описание страниц и их печати, а также RPL, язык программирования калькуляторов HP-28 и HP-48.

Большинство конкатенативных языков программирования используют стек для передачи аргументов. Это связано с простотой реализации и свойствами стека, который удобно применять с постфиксной нотацией. Рассмотрим работу со стеком на примере языка Forth.

В Форте программа состоит из слов, разделённых пробелами. Если слово - это число, то оно кладётся на вершину стека. Если слово - это имя функции, то вызывается эта функция (в терминологии Форта функции называются словами). Она берёт аргументы из стека и кладёт результат на стек. Рассмотрим простейшую программу, которая состоит из четырёх слов:

3 4 + .

Первые два слова - числа, поэтому они помещаются в стек. Затем вызывается функция +, которая берёт два числа из стека, складывает их и кладёт результат на стек. Потом вызывается функция ., которая выводит на экран число из стека. Таким образом аргументы предшествуют функции, поэтому эта нотация называется постфиксной.

Конкатенативные языки общего назначения не получили значительного распространения. Это связано с их специфичными достоинствами и недостатками, которые являются следствием основного принципа: все функции принимают один аргумент и возвращают одно значение. Когда именно это и требуется, то проблем не возникает, а конкатенативные языки позволяют писать очень простые, лаконичные и ясные программы. Предположим, в конкатенативном языке с постфиксной нотацией есть следующие функции, которые принимают и возвращают текстовые строки:

input - возвращает текст, введённый пользователем
print - выводит текст на экран
upcase - меняет в строке строчные буквы на заглавные
first_word - возвращает первое слово в строке (режет строку до первого пробела после первым словом)

Составим с их помощью программу, которая выводит на экран имя пользователя в верхнем регистре:

input first_word upcase print

Трудности возникают тогда, когда нужно использовать функции с разным числом аргументов. В стековом языке требуется размещать аргументы в определённом порядке, нередко приходится менять их местами. Кроме того, если аргумент используется в функции несколько раз, его приходится дублировать. Это приводит к трудно понимаемым выражениям. Например, функция

f x y z = y² + x² − |y|

в стековом языке записывается следующим образом:

f = drop dup dup × swap abs rot3 dup × swap − +

Для преодоления подобных трудностей в современных конкатенативных языках, таких как Kitten и min, явно используются переменные. В языке Kitten переменные объявляются следующим образом:

-> x;           // переменная x получит значение из стека
5 -> y;         // y = 5
1 2 3 -> x y z; // x = 1; y = 2; z = 3

Рассмотрим функцию возведения числа в квадрат. Традиционно для стековых языков в Kitten она записывается следующим образом:^[8]

define square (Int32 -> Int32):
    dup (*)

А так её можно переписать с использованием переменной:

define square (Int32 -> Int32):
    -> x;
    x * x

В данном простейшем примере особенного смысла в этом нет. Однако если в функции аргумент или аргументы используются много раз, применение переменных значительно упрощает написание программы и чтение исходного кода. Фрагмент кода программы, выводящей песенку 99 бутылок пива:

define bottles_of_beer (Int32 -> +IO):
  -> x;
  x verse
  if (x > 1):
    (x - 1) bottles_of_beer

В языке программирования min аналогично применяются символы:

x define  ; символ x получит значение из стека
:x        ; сокращённая запись
8 :x      ; x = 8

Рассмотрим для примера программу на языке min, которая возвращает true если у файла размер более 1 мегабайта и он был недавно изменён:

dup dup
"\.zip$" match
swap fsize 1000000 > and
swap mtime now 3600 - >

Используя символ можно отказаться от дублирования и перестановки элементов стека и значительно улучшить читаемость кода:

:filepath
filepath "\.zip$" match
filepath fsize 1000000 >
filepath mtime now 3600 - >
and and

Использование переменных приближает конкатенативные языки к аппликативным, однако между ними всё равно есть принципиальные различия. В конкатенативных языках у программиста есть выбор: пользоваться стеком (или аналогичным механизмом) или объявить переменные. Кроме того, сам механизм работы с переменными довольно прозрачный и поддающийся контролю. Это даёт гибкость и возможность эффективной и сравнительно простой реализации.

• Функциональное программирование
• Неявное программирование
• Forth
• Joy (язык программирования)
• Cat (язык программирования)

• Why Concatenative Programming Matters (англ.)
• Concatenative Languages Wiki (англ.)
• Стековые языки (рус.) на Блоге Тру Программиста
• Язык программирования Om (англ.)
• Язык программирования Kitten (англ.)
• Язык программирования min (англ.)