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

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

Самый распространённый конкатенативный язык — это язык описания страниц PostScript, ограниченное подмножество которого используется в PDF. Однако, PostScript код обычно генерируется программами, написанными на других языках. Другой, достаточно широко известный конкатенативный язык — это Forth.

Также следует отметить язык программируемых микрокалькуляторов Hewlett-Packard HP-28 и HP-48 — RPL. Этот конкатенативный язык со сборкой мусора как и реализующие его калькуляторы достаточно популярны среди инженеров. Родственный ему язык советских ПМК Б3-21, Б3-34, МК-54, МК-61, МК-52, хотя и относится к стековым языкам, из-за своей крайней примитивности (по сути это машинный код) сложно отнести к конкатенативным.

Среди других конкатенативных языков можно отметить Joy, Cat, Factor и FALSE.

Конктенативные языки можно рассматривать как семейство языков, вроде Лисп-языков. Так между всеми диалектами Лиспа (включая Scheme), есть сильное «семейное сходство». Однако есть большая разница в дизайне, реализации и назначении этих языков. Языки программируемых микрокалькуляторов и многие из версий Форта предназначены для встраивания в небольшие микропроцессорные системы; PostScript также является встраиваемым языком, только микропроцессорные системы, интерпретирующие его называются принтерами. Однако другие конкатенативные языки, такие как Joy или Cat разработаны как языки программирования общего назначения или в исследовательских целях.

История и определение

Forth был первым языком данного плана, но только Joy стал тем языком, который получил название конкатенативного. Создатель языка Joy, Manfred von Thun, много писал о конкатенативной теории.

Строго говоря, язык программирования можно назвать конкатенативным (а не аппликативным) когда:

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

В этом определении стек не упоминается; но все конкатенативные языки используют эту структуру данных как самый простой способ передавать от одной операции к другой. Термин «конкатенативный» не общепринят, многие пользователи таких языков предпочитают называть их «стековыми (stack-based)».

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

Постфиксная нотация

Программы на конкатенативных языках имеют сходство с постфиксной нотацией или обратной польской записью (RPN) арифметических выражений. Аргументы, или программный код, чьим результатом являются аргументы предшествуют слову, использующему данные аргументы. Литералы, такие как числа, помещают значения на стек; другие слова могут брать со стека одни значения и помещать на него другие.

Например:

2 3 + .

В языках Forth и Factor это — корректная программа: 2 и 3 — слова литералы, помещающие на стек представляемые ими значения. + — это математический оператор; он снимает со стека два верхних значения и помещает на него их сумму. Наконец, оператор . (точка) снимает вершину стека и печатает её значение на дисплее. Так эта программа выведет число 5.

Управление последовательностью действий

В рамках полноты по Тьюрингу, язык должен иметь некоторые средства управления последовательностью действий — возможность делать переходы или совершать тот или иной выбор на основании значения выражения. Конкатенативные языки реализуют управление последовательностью действий различными способами. Сравним два примера из языков Forth и Factor:

= IF 23 ELSE 17 THEN

= [ 23 ] [ 17 ] if

Оба примера делают одно и то же: сравнивают два верхних элемента стека и, если они равны, оставляют на стеке значение 23; в противном случае — значение 17. В Форте слово IF — специальное; оно приводит к тому, что программный код предшествующий слову ELSE будет выполнен если условие истинно, если же оно ложно, выполняется код после ELSE. В языке Factor, у слова if другая функция; оно принимает условие и две цитаты (quotations)  — программных фрагмента взятых в кавычки; слово if выполняет первую или вторую «цитату», в зависимости от того, является ли выражение истинным. Примерно так же работает оператор ifelse языка PostScript.

Формализация цитирования кода, средства, полностью унаследованного из Лиспа, отличает поздние конкатенативные языки, такие как Factor или PostScript, от ранних, таких как Forth. Слова, оперирующие цитатами, иногда называют комбинаторами.

Определения и лексический анализ

Конкатенативные языки могут значительно различаться в плане синтаксиса, используемого для определения новых слов. Следующие фрагменты кода на языках Cat, Forth или Factor, и Joy делают одно и то же: определяют новое слово с именем add100, которое добавляет 100 к значению на вершине стека.

define add100  { 100 + }

: add100  100 + ;

DEFINE add100 ==  100 + .

Во всех фрагментах тело определения одинаково — это слова 100 +. Разница заключается в словах парсера (parsing words), используемых, чтобы указать транслятору языка, что имеет место определение нового слова. Слова парсера — это своего рода аналог ключевых слов C или специальных операторов в Лиспе: вместо того, чтобы выполнять операции на стеке, они управляют тем, как парсер будет обрабатывать последующие слова.

Это и позволяет определение новых слов. Слова парсера дают конкатенативным языкам аналог Лисповских макросов: программист может определять новый синтаксис.

Стековый эффект

Конкатенативные языки программирования используют нотацию стекового эффекта слова. Стековый эффект слова — это описание того, какие значения слово берёт со стека, а какие оставляет на нём в качестве результата своего выполнения. Как правило, слова имеют устойчивый (consistent) стековый эффект: число аргументов и результатов слова — постоянные величины.

См. также

• Неявное программирование

Внешние ссылки

• Concatenative Languages Wiki (англ.)
• What is a concatenative language (англ.), Christopher Diggins, Dr. Dobb's Journal, 31 декабря 2008
• A Note on Functional Programming in Joy and K (англ.)
• Yahoo Discussion Group on Concatenative Languages (англ.)
• Стековые языки (рус.) на Блоге Тру Программиста