Pull to refresh

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

ProgrammingForth
Sandbox
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
Tags:конкатенативное программированиефункциональное программированиестековые языкиfactorforthjoycatstack-based languagesconcatenative programming
Hubs: Programming Forth
Total votes 56: ↑51 and ↓5+46
Views14K

Popular right now