Функциональное программирование снова в моде. В зависимости от того, предпочитаете ли вы классику или хардкор, страдаете от навязанных промышленных стандартов или вы просто хипстер, вашим любимым предпочтением может быть 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. Википедия: Конкатенативное программирование
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
Автор: potomushto
