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

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

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

Конкатенативные языки отличаются простотой, эффективностью и удобством в реализации, поэтому самые популярные языки этого типа используются в программируемых калькуляторах и для встраивания в небольшие микропроцессорные системы. Например, конкатенативный язык RPL применяется в программируемых микрокалькуляторах Hewlett-Packard HP-28 и HP-48. Язык программирования Forth был реализован на множестве процессоров с очень ограниченными вычислительными возможностями, к примеру, он использовался на компьютере 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. То есть имя любой функции можно заменить на текст её определения и получить правильное выражение. Этот простой принцип определяет специфику конкатенативных языков, их достоинства и недостатки.

Особенности

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

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

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

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

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

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

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

Недостатки:

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

Реализации

Первым конкатенативным языком высокого уровня был 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 она записывается следующим образом:

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 (англ.)