Функциональное программирование / [Из песочницы] Стековые языки программирования

Функциональное программирование снова в моде. В зависимости от того, предпочитаете ли вы классику или хардкор, страдаете от навязанных промышленных стандартов или вы просто хипстер, вашим любимым предпочтением может быть 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 ^[1]. Как нетрудно заметить интерпретатор написан на javascript и довольно прост, его можно посмотреть на ./Engine.js. У Cat, интерпретатор которого был изначально реализован на C#, а теперь на очень многих других языках, также есть онлайн js-интерпретатор ^[2].

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

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

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 ^[3] и да, Faсtor, например, умеет оптимизировать хвостовую рекурсию.

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

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

  = [ 23 ] [ 17 ] if  

Чтобы понять как это работает, рекомендую освежить знания по определению булевых функций ^[4] в лямбда-исчислении. Чуть более сложный пример на 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, различные методы и механизмы, которые позволяют изменить мышление ^[5]. Но такая проблема может настигнуть вас и в вашем любимом Haskell с его бесточечной нотацией композиций функций (в которой как раз присутствуют точки). Записать в постфиксной форме без именованных переменных какое-нибудь сложное алгебраическое выражение также не представляется возможным таким же образом, как мы привыкли с детства. В этом и стоит главная проблема этих языков — в том, что они как и классические функциональные, требуют от вас чуть иного мышления ^[5]. В условиях продакшена, и история о Scala ещё не затихла, требуются языки, привычные всем, потому что всё дело упирается в человеческие ресурсы.

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

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

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

2. Pypy interpreter ^[7]

3. http://docs.factorcode.org/content/article-cookbook-philosophy.html ^[8]

4. Functional Programming in Joy and K ^[9]

5. Why Concatenative Programming Matters? ^[10]

6. Objects and Aspects: Row Polymorphism ^[11]

Автор: potomushto