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

concatenative
Функциональное программирование снова в моде. В зависимости от того, предпочитаете ли вы классику или хардкор, страдаете от навязанных промышленных стандартов или вы просто хипстер, вашим любимым предпочтением может быть Scala, Haskell, F# или даже старый добрый Lisp. Такие сочетания слов, как функция высшего порядка, отсутствие побочных эффектов, и даже монады, ласкают слух всех «неокрепших юных умов», будь-то ребят из JetBrains или студента, впервые увидевшего SICP.

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

Что такое конкатенативное программирование



Конкатенация — это соединение нескольких строк. Язык, в котором обычным соединением двух фрагментов кода получается их композиция, называется конкатенативным[1]. Каждый из этих кусков кода — функция, которая берет в качестве аргумента стек и в качестве результата его же, стек, и возвращает. Поэтому чаще такие языки называют стековыми (stack-based).

Стековые языки живы и существуют. Благодаря быстродействию и легковесности трансляторов они применяются и в реальном мире. JVM, самая, пожалуй, распространенная виртуальная машина в мире; CPython, ещё одна стековая виртуальная машина[2], которая используется во множестве высоконагруженных проектов, таких как Youtube и BitTorrent; в языке PostScript, использующийся сейчас в высокопроизводительных топовых принтерах, наконец, старый добрый Forth, до сих пор встречающийся для программирования микроконтроллеров и встроенных систем. Все они по-своему замечательны, но стоит заметить, что хотя общие принципы схожи, но по большому счёту речь пойдет о языках более высокого уровня, таких как Faсtor, Joy или Cat.

Функции



В конкатенативных языках всё является функцией, но для сравнения с остальными языками посмотрим на пример функции возведения в квадрат с определением. Непоколебимый императивный С:

int square(int x)
{
    return x * x;
}

Функциональный Scheme:

(define square
  (lambda (x) 
    (* x x)))

Конкатенативный Joy:

DEFINE square == dup * .


Конкатенативный Factor:
: square ( x -- y ) dup *;


Конкатенативный Cat:
define square {
    dup *
}


Здесь dup создает копию аргумента, находящегося на вершине стека, и кладёт эту копию туда же.
* — это обычная функция умножения
*:: (int) → (int) → (int)
, которая “ожидает” на стеке два аргумента; в данном случае два самых последних в стеке — это копия одного и того же числа. Если теперь мы захотим воспользоваться этой функцией нам будет достаточно написать 3 square, где 3 — тоже функция с сигнатурой
3::() →  (int)
, т.е. возвращающая сама себя. На самом деле более корректно говорить, что это тип с рядным полиморфизмом (row polymorphism) и возвращает она весь текущий стек.[5]

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

"Hello world" print


Мы кладём в стек строку «Hello World», а затем функцией print извлекаем элемент с вершины стека и выводим его на экран.

10 [ "Hello, " "Factor" append print ] times


Здесь используется операции над цитатами, о которых будет сказано чуть позже, но довольно очевидно, что в стек кладется 10 и цитата, а times выполняет код из цитаты указанное количество раз. Код внутри цитаты просто последовательно кладет в стек две строки, затем соединяет их и выводит на экран.

Попробовать небольшой конкатенативный язык прямо в браузере можно на trybrief.com. Как нетрудно заметить интерпретатор написан на javascript и довольно прост, его можно посмотреть на ./Engine.js. У Cat, интерпретатор которого был изначально реализован на C#, а теперь на очень многих других языках, также есть онлайн js-интерпретатор.

Цитаты и комбинаторы.



Возможность брать куски кода в цитаты ([ ]), дает возможность писать собственные управляющие конструкции. Цитаты — это функции, которые возвращают содержимое процитированного выражения. Функция цитирования в таком случае будет следующего типа.

quote :: (T) → (() → T). 


Например, запись [5] в квадратных скобках возвратит не само число 5 целого типа, а его цитату. Понятнее, когда речь идет о выражении, например о [5 6 +]. Без цитирования произойдет вычисление числа 11 и помещение его в стек, цитирование же поместит в стек само выражение 5 6 +, с которым можно взаимодействовать многими разными способами.
Комбинаторы это функции, которые ожидают одну или несколько цитат из стека и применяет их особым образом к остальному стеку.

По сути цитаты — это обычные списки. Их можно соединять с другими цитатами, производить различные манипуляции в стеке, а затем применять с помощью разных комбинаторов. Например, комбинатор fold сворачивает список в значение, пример суммирующий элементы списка (Joy):

[2 5 3]  0  [+]  fold


Быстрая сортировка с рекурсивным комбинатором binrec в Joy:

DEFINE qsort ==
   [small]
   []
   [uncons [>] split]
   [[swap] dip cons concat]
   binrec .


Ничего не мешает реализовать монады как в Factor и да, Faсtor, например, умеет оптимизировать хвостовую рекурсию.

Управляющие конструкции.



Благодаря цитированию и комбинаторам можно использовать текущие или создавать собственные управляющие конструкции. Пример для if (Factor):

= [ 23 ] [ 17 ] if


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

: sign-test ( n -- )
    dup 0 < [
        drop "отрицательное"
    ] [
        zero? [ "ноль" ] [ "положительное" ] if
    ] if print ;


Функция определяет знак числа. if оперирует двумя цитатами, выделенными квадратными скобками и находящихся в стеке выше, чем выражение dup 0 <. В случае если число лежащее на вершине стека при вызове sign-test (т.е. аргумент функции) меньше нуля — применяется первая цитата, которая помещает в стек «отрицательное» (выбрасывая оттуда проверяемое число, которое было скопировано). В случае, если число больше выполняется вторая цитата, внутри содержащая ещё одно условие. После этого в стеке находится строка, обозначающая знак числа, эта строка и выводится функцией print.

Преимущества:



Скорость и оптимизируемость.

    :A 1 2 + print    
    :add2 2 + ;
    :B a add2 print


В данном случае A = B благодаря ассоциативности композиции. Программа на конкатенативном языке делится на кусочки, которые собираются после компиляции. По сути это обычный map-reduce, быстрый и позволяющий компилировать каждый кусок кода параллельно.
Рефакторинг. Если вы видите два одинаковых участка кода выносите их в отдельную функцию. Используйте комбинаторы, цитирование и собственные управляющие конструкции. Примеры оптимизаций на языке Cat:

f map g map => [f g] map
[f] map x [g] fold => x [[f' f] g] fold 
[f] filter x [g] fold => x [f [g] [pop] if] fold
[f] map [g] filter x [h] fold => x [f g [h] [pop] if] fold


Сложности



Все недостатки стековых языков очевидно происходят от их особенностей. Это композиция вместо аппликации, это бесточечная нотация, это отсутствие переменных и сложность записи некоторых выражений. Представьте простое выражение в конкатенативном языке 'a b c d'. Если функция c принимает два аргумента, то в аппликативной форме выражение будет записано как d(c(b, a)), если b и c принимают по одному аргументу, то d(c(b(a))); если d функция от двух аргументов, b одного, а c функция не принимающая аргументы, то в аппликативной форме выражение будет иметь вид d(c, b(a)). Нужно очень аккуратно писать код на конкатенативном языке, потому что вам придется понимать в нём абсолютно всё. Этому помогает строгая типизация в Cat, предполагаемая поддержка от IDE, различные методы и механизмы, которые позволяют изменить мышление. Но такая проблема может настигнуть вас и в вашем любимом Haskell с его бесточечной нотацией композиций функций (в которой как раз присутствуют точки). Записать в постфиксной форме без именованных переменных какое-нибудь сложное алгебраическое выражение также не представляется возможным таким же образом, как мы привыкли с детства. В этом и стоит главная проблема этих языков — в том, что они как и классические функциональные, требуют от вас чуть иного мышления. В условиях продакшена, и история о Scala ещё не затихла, требуются языки, привычные всем, потому что всё дело упирается в человеческие ресурсы.

Каждая функция в конкатенативном языке оперирует стеком, и хотя она сама по себе может быть без побочных эффектов, в ней нет никаких присвоений, переменных, но она меняет стек, т.е. глобальное состояние, поэтому вопрос чистоты для многих не очевиден. Однако, для тех высокоуровневых языков, о которых идет речь это не совсем справедливо, ведь это скорее вопрос реализации. А для того чтобы быть применимыми в реальном мире у них есть и переменные для тех редких случаев, когда они нужны (например, SYMBOL: в Factor или объявления функций для повышения читаемости кода), они могут быть достаточно чисты в математическом плане (как Joy[4]) и, как и многие концептуальные различия между подходами, парадигмами и платформами в конце концов быть всего лишь делом вкуса. При условии адекватного подбора инструмента под задачу. Именно поэтому Forth используется во встроенных системах, его транслятор очень легко реализовать и он будет очень небольшого размера.

Я надеюсь кто-нибудь открыл для себя что-то новое. Лично я воодушевился текстом «Почему конкатенативное программирование важно́»[5] и теперь уже несколько дней не могу оторваться от этой темы, и даже будучи в сонном состоянии могу много-много раз произнести слово «конкатенативный».

1. Википедия: Конкатенативное программирование

2. Pypy interpreter

3. http://docs.factorcode.org/content/article-cookbook-philosophy.html

4. Functional Programming in Joy and K

5. Why Concatenative Programming Matters?

6. Objects and Aspects: Row Polymorphism
Поделиться публикацией
Комментарии 27
    +4
    Начало воодушевило, думал весь текст так легко написан, но в итоге кажется, что чтобы яснее раскрыть данную тему потребуется не одна статья такого объема.
      +1
      Да, возможно. Могу лишь предложить поиграться в браузере, посмотреть примитивный kitten, реализованный на haskell, посмотреть Getting Started и примеры на сайтах самих языков, упомянутых в статье. Ну и я всё-таки рекомендую почитать Why Concatenative Programming Matters?[5], которую я даже перевел, надо лишь подготовить форматирование для хабрахабра — в этой статье всё очень подробно.
      +1
      (define question
      (display «Yahoo store has been written on common lisp»))
        0
        Спасибо тегу за отличную подсветку кода (:
        +1
        Юзайте тег source
        (define question
        (display «Yahoo store has been written on common lisp»))
        
          0
          Пардон, ответ на комментарий выше.
            +1
            спасибо, заменил в тексте все pre на source
            0
            Tcl — тоже?
              0
              Тоже, тоже.
              0
              Да вы же забыли самый главный стековый язык! Если регистры добавить к стеку, то в асме только и происходит, что модификация этого стека конкатенацией инструкций!
                +3
                Слова-то одинаковые, но стеки разные. :) Тот же 386 — регистровая машина.
                  +1
                  В каком-то смысле да, если вы имеете ввиду работу с функциями
                          push   offset msg
                          call   printf
                          push   0
                          call   exit
                  

                  но я побоялся ошибиться в этом вопросе, всё-таки виртуальная машина того же Python это очевидный байт-код, который вообще не оперирует регистрами.
                  >>> import dis
                  >>> def f(x):
                  ...     return x + 1
                  >>> dis.dis(f)
                  2         0 LOAD_FAST                0 (x)
                            3 LOAD_CONST               1 (1)
                            6 BINARY_ADD
                            7 RETURN_VALUE
                  
                    0
                    Да, я вроде как по определению приписал регистры к стеку. В сущности они не особенно отличны от ячеек стека, я имею ввиду логически, а не конструктивно.
                  +5
                  Есть такая вещь, как MUCK/MUD — многопользовательские текстовые ролевые игры, предки всех этих ваших WoW’ов. Есть для них популярный движок TinyMUCK. И есть в нём язык MUF — Multi-User Forth. Кто и зачем выбрал стековый язык, остаётся для меня загадкой (икал он, думаю, постоянно), потому что мне, как простому смертному объектно-процедурному программисту, совершенно непонятно, как можно на этом писать код. Шут с ней с польской нотацией, но бесконечное «а стек внезапно кончился»…

                  Хорошо ещё, что MUF нужен был только для сложных вещей, а для простых хватает MPI — write-only лиспо-подобного языка.

                  Собственно, возникает вопрос: а в каких случаях, собственно, оправдано написание кода на стековых языках? Когда это нужно? Когда это лучше и, если такое может быть, удобнее?
                    0
                    1. достаточно компактный код,
                    2. и достаточно быстрый,
                    3. это целая методология программирования — снизу-вверх интерактивно,
                    4. что позволяет легко реализовать и отладить DSL,
                    5. исполнители легко реализуемы (фактически — одна процедура с большим case и простыми командами)
                    6. и поэтому легко переносимы (по сравнению например с VM на регистровом пуле).
                    7. ну и, когда привыкаешь — затягивает.
                      +2
                      Никто не спорит, что на стековом языке легко написать нечитаемые программы, непривычный код, тем более на таком относительно низкоуровневом и устаревшем языке с простым IDE, без системы типов и кучи проверок на этапе компиляции. Автор старается обьяснить, что нужно правильно организовывать свои программы.
                      Конкатенативные языки неплохо подходят для такого dataflow-программирования и с согласен с shambho, это быстрый и компактный язык, код на котором легко рефакторится и оптимизируется. А современные ещё и очень интересны в функциональном плане, о чём я, по-видимому плохо, пытался рассказать. Неважно, что это стековый язык, можно думать в функциональном стиле — писать чистые функции, тестировать их (в том же Factor есть юнит-тесты), создавать модули и библиотеки. Но при этом нет бесконечных скобочных аппликативных вызовов (a(b(c,d,e(f(g(g))))), а есть порядок функцией в соответствии с потоком данных g dup f e d c b a. Если каждая функция описана, ясна и протестирована, а компилятор следит корректностью, то тогда всё нормально.
                        0
                        Мне кажется, что невозможность понять арность функций в выражении «g dup f e d c b a» без просмотра сигнатур оных — уже солидный изъян. Читабельность страдает. Кстати, это выражение должно быть записано как a(b(c(d(e(f(g() g())))))) или, если вы имели ввиду Lisp, как (a (b (c (d (e (f (g) (g))))))). dup ведь копирует вершину стека, так ведь?
                          0
                          Да, действительно, большое спасибо за поправку g() g(), именно пример функции с двумя аргументами. А если разбавить всё это управляющими конструкциями, паттерн маттчингом на несколько строк, то определение унарности функции всё равно требует мысленного синтаксического разбора, который, как мне думается, создает лишь иллюзию повышенной читаемости кода. Дело привычки и только потому, что мозг «кеширует» эти результаты разбора, в данном определенном контексте уже знает сигнатуры каждой функции и с кажущейся легкостью оперирует ими. Но тот же эффект происходит и при чтении больших программ с композицией функций — необязательно в конкатенативном языке, и в функциональных языках с бесточечной нотацией и возможностью каррирования.
                          Конечно, IDE очень сильно может способствовать чтению кода, как и тот факт, что правильно построенный модульный код с несвязанностью позволяет держать «в кэше» лишь небольшую часть функцию.
                          Однако, например для математических формул со множеством операций, такая форма записи может быть крайне неудобной по чисто историческим причинам. Мы привыкли к инфиксной форме, то есть нет смысла ломать себя в том, чему мы умеем с детства и умеем мнгновенно — читать такие выражения хочется в инфиксной форме и тут не обойтись использованием переменных. Но тот же Factor, написанный на самом языке использует переменные менее чем в 1% своего исходного кода.
                        0
                        Поддержу высказавшихся выше: dataflow очень хорошо реализуется на стековых языках, и вполне читаем даже незнакомыми с концепцией людьми.

                        А ещё стековую программу можно очень просто останавливать, делать отпечатки состояния — ведь запомнить то нужно только текущую операцию и стек.
                        Скажем, интерактивный интерпретатор работает как виртуальная машина и сохраняет состояние между сессиями, помнит все новые слова и хранит введенные данные. Можно использовать как песочницу, как калькулятор (правда в ОПН) с памятью, диалоговую экспертную систему, и проч.

                        Также добавлю про DSL: вообще, в стековых языках программа расширяет язык под задачу (т.к. встроенный синтаксис обычно минималистичен), в итоге текст программы может стать вполне литературным ) И при этом в процессе дополнения языка обычно растет уровень абстракции и на определенном уровне в стеке уже могут лежать http-запросы, выборки из БД, целые файловые системы. И этими сущностями манипулируют слова не менее высокоуровневые:
                        Примерно так может выглядеть сервер хранения статики:
                        взять_запрос запрос_картинки?
                        [dup вынуть_имя_файла достать_из_статики упаковать_картинку_в_ответ]
                        [drop "Отдаём только картинки" упаковать_строку_в_ответ] if
                        ответить
                          0
                          «Расширение языка» происходит и про объектно-ориентированном, и при процедурном программировании.

                          if (запрос_картинки(взять_запрос()))
                              упаковать_картинку_в_ответ(достать_из_статики(вынуть_имя_файла(взять_запрос())))
                          else
                              упаковать_строку_в_ответ("Отдаём только картинки")
                          

                          if (запрос.взять().запрос_картинки)
                              ответ.упаковать_картинку(статика.достать(запрос.взять().имя_файла))
                          else
                              ответ.упаковать_строку("Отдаём только картинки")
                          

                          Что из этого более приближено к естественным языкам — вопрос открытый. Пока у функций ровно один аргумент, польская нотация выглядит приятно, но как только аргументов несколько — лично у меня мозг начинает с трудом справляться с логикой (хотя, может, дело привычки). If задом-наперёд точно читаемости не способствует. Читаешь огромный блок кода, а в конце высняется, что он выполняется только при каком-то условии.

                          У объектного и процедурного стиля вызов методов цепочкой выглядит не так опрятно, как в стековом для одноаргументных функций, но зато сразу, с высоты птичьего полёта (по началу строк), видна общая логика:

                          если (что-то там с запросом)
                              упаковать картинку каким-то там способом
                          иначе
                              упаковать строку каким-то там способом
                          

                          Когда код нужно читать и анализировать, это очень сильно помогает.
                            0
                            Ось ООП/не-ООП и ось ФП/императив — практически ортогональны.
                            В стековом языке отлично реализуется ООП, если он нужен для задачи.

                            if перед ветками или после — это конкретная форма записи выражений: префиксная, или постфиксная. И она никак не связана с парадигмой ООП/не-ООП.
                            Вот в функциональных языках if/then имеет другой смысл — условная конструкция не осуществляет управление потоком исполнения, а является вычислимым выражением (и поэтому всегда имеет ветку else)

                            В стековом языке постфиксную запись ветвления можно превратить в префиксную, только это не нужно — язык то весь постфиксный!
                              0
                              А процедурное программирование — это просто программирование машины с Неймановской архитектурой. Т.е. если мы программируем последовательность действий, которые работают с памятью, наше программирование — процедурное.
                              Стек — память? -Да. Операции над стеком последовательны и меняют стек? -Да. Стековые языки — процедурные.
                              0
                              Существуют конкатенативные языки с прямой польской нотацией, например Om, по ссылке помимо устранения недостатка с затруднением чтения кода, который вы упомянули, ещё несколько важных преимуществ. А бывают и не только стековые. Посмотрел чуть ли не их все, о пока теоретический язык по пятой ссылке из топика самый привлекательный. С арностью можно таки совладать без IDEшных подстветок просто скобками, например сводя все к монадам:
                              [split ':'] '23:50:12'

                              Однако, пока не видел языка, синтаксис которого бы явно к такому склонял, скобками или переносом на новую строку.
                              Пока только начал читать про всё это, больше вопросов, чем ответов.
                          0
                          Добавлю в общую копилку:

                          Язык программирования retro (похож на forth, виртуальная машина реализована на многих популярных языках программирования);
                          Конкатенативный язык программирования графики.
                            0
                            С каких это пор CFDG — конкатенативный язык? Он не отвечает определению из Википедии (ни русской, ни английсокой) и не похож на все эти Форт'ы.
                              0
                              Честно говоря, не помню, с чего я это взял. На форты он действительно не похож. Но у меня сложилось впечатление, что читал о нем ранее именно в этом ключе. Ну и язык не обязательно должен быть похож на FORTH и иметь обратную польскую запись, чтобы относиться к этой касте. Если ошибся, извините, что ввел вас в заблуждение.
                                0
                                Сначала это вообще был язык определения формальных грамматик. В новой версии в него добавили кучу фич, в т.ч. возможность определять функции и вводить переменные, и его уже можно назвать языком программирования. Но не конкатенативным.

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

                          Самое читаемое