Interested Article - Конкатенативный язык программирования
- 2020-12-14
- 1
Конкатенативный язык программирования — язык программирования , основанный на том, что конкатенация двух фрагментов кода выражает их композицию . В таком языке широко используется неявное указание аргументов функций (см. бесточечное программирование ), новые функции определяются как композиция функций, а вместо аппликации применяется конкатенация . Этому подходу противопоставляется аппликативное программирование .
Многие конкатенативные языки используют постфиксную нотацию и стек для хранения аргументов и возвращаемых значений операций, поэтому под конкатенативными языками обычно подразумевают стековые. Однако конкатенативные языки могут быть построены и на других принципах, поэтому термины стековый язык и конкатенативный язык не являются синонимами.
Конкатенативные языки отличаются простотой, эффективностью и удобством в реализации, поэтому самые популярные языки этого типа используются в программируемых калькуляторах и для встраивания в небольшие микропроцессорные системы. Например, конкатенативный язык RPL применяется в программируемых микрокалькуляторах Hewlett-Packard и . Язык программирования 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 и , отличающиеся статической типизацией . Другой современный конкатенативный язык, , отличается минималистичным синтаксисом и очень компактной реализацией (около 1 мегабайта), он используется в генераторе сайтов .
Из специализированных стековых языков наиболее известны PostScript , который используется для описание страниц и их печати, а также RPL , язык программирования калькуляторов и .
Работа со стеком
Большинство конкатенативных языков программирования используют стек для передачи аргументов. Это связано с простотой реализации и свойствами стека, который удобно применять с постфиксной нотацией. Рассмотрим работу со стеком на примере языка 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 (язык программирования)
Примечания
- Jon Purdy. (англ.) . Дата обращения: 23 января 2018. 24 января 2018 года.
- Олег Парамонов. . Дата обращения: 25 января 2018. 26 января 2018 года.
- Xah Lee. (англ.) . Дата обращения: 25 января 2018. 26 января 2018 года.
- potomushto. . Дата обращения: 25 января 2018. 26 января 2018 года.
- Sparist. (англ.) . Дата обращения: 25 января 2018. 10 сентября 2017 года.
- Xah Lee. (англ.) . Дата обращения: 25 января 2018. 26 января 2018 года.
- (англ.) . Дата обращения: 25 января 2018. 26 января 2018 года.
- Jon Purdy. (англ.) . Дата обращения: 25 января 2018. 25 января 2018 года.
Ссылки
- (англ.)
- (англ.)
- (рус.) на Блоге Тру Программиста
- (англ.)
- (англ.)
- (англ.)
- 2020-12-14
- 1