1169737
На самом деле на определенном уровне абстракции они ничем не отличаются. Любая аппликативная программа может быть чисто синтаксически переписана в программу без аппликаций и без параметров функций. Например, нумерал Черча для числа n в лямбда-исчислении применяет функциональный аргумент n раз:
Соответственно, рекурсивное применение f эн раз ты можешь записать как композицию: f . f . (n раз) . f, например:
Но одно имя у нас остается - сам функциональный параметр f до сих пор именованный. Тут уже нужно применить немного СМЕКАЛОЧКИ. Для простоты давай запишем функцию композиции явно:
То есть мы берем аргумент f и возвращаем функцию, которая берет аргумент g и возвращает функцию, которая уже берет наконец x и применяет к нему сперва g, а потом f (впрочем, порядок применения нам сейчас все равно не важен). То есть:
Значит:
Внимательно посмотрим на определение двойки. Мы берем аргумент, применяем к нему функцию compose, а потом результат этого применения применяем к аргументу еще раз. Чтобы структура кода была видна яснее, забудем на секунду, что f тоже является функцией (чтобы не путаться), и перепишем тело двойки, переименовав compose в F, а старый f - ну, например в икс:
Так понятнее, что происходит, да? (F x) возвращает некую функцию, и мы ее опять применяем к икс. Вынесем это действие в отдельный комбинатор с каким-нибудь незамысловатым именем:
Тогда:
Точно так же, как вместо g = \x -> f x мы можем просто написать g = f, так и тут мы можем опустить формальный параметр и явное создание лямбды, потому что (sup compose) уже возвращает ровно то, что нам нужно! То есть мы полностью избавились от имен, а значит - полностью избавились от аппликации, заменив ее композицией.
Далее, нетрудно заметить, что определение тройки включает в себя определение двойки, и в целом имеет ту же форму:
Если от использовании цифры 2 в качестве имени функции у кого-то взрывается мозг, то можно просто мысленно заменить "2" на "two". Ок? Проехали. Вот что действительно важно - мы облажались с нашим комбинатором. Он оказался недостаточно общим: оказывается, нам нужно к аргументу применять еще одну функцию (двойку) перед применением другой функции (compose). Почему тогда при определении двойки нам это не понадобилось? Ну, потому что единица на самом деле ничего не делает. Тройка рекурсивно применяет данную ей функцию трижды, двойка - дважды, а единица - один раз. Ну, то есть она просто применяет данную ей функцию. То есть она ничем от этой функции и не отличается. Напоминаю:
Короче, с двойкой нам просто повезло. А единица - это identity function, которая возвращает свой аргумент неизмененным. На всякий случай сразу запишем эту мысль:
И сразу пофиксим наш комбинатор sup. Теперь будем принимать две функции F и G вместо одной F, ну и заодно имя покороче сделаем:
То есть мы применяем f к икс, получаем некую функцию f'. Далее мы применяем g к икс, получаем некое значение x'. И наконец применяем f' к x':
Новое определение двойки с этим комбинатором выглядит так:
Здесь мы использовали identity function, чтобы передать наш аргумент в S без изменений. А вот для тройки вместо I уже нужно использовать кое-что другое:
Напоминаю, что "2" - это имя функции, слабонервные мысленно заменяют на "two". Также напоминаю, что порядок композиции не важен (у нас же везде одна и та же функция: f . f . f...), поэтому мы можем поменять f и (2 f) местами. (На самом деле можно было и сразу написать все в нужном порядке, гхм; ну не переписывать же мне сейчас половину поста, правда?)
А теперь самое интересное. Двойку можно развернуть, подставив вместо имени функции ее тело:
Поскольку у нас нет никаких именованных формальных параметров, такая подстановка возможна, и нам не нужно ничего переименовывать или изобретать сложные правила аппликации. С обычными лямбдами такой трюк, очевидно, не прокатит:
Иными словами, любое имя функции может быть заменено на ее тело, и наоборот - любой (синтаксически корректный) фрагмент программы может быть "вырезан" в отдельную функцию и заменен ее именем. Следующие этому принципу языки называются конкатенативными; конкатенация термов в них обозначает не применение функции к аргументу (f x), а композицию двух функций (g f).
Благодаря этому, среди прочего, обычные функции вида (a b) можно обобщить до функций, возвращающих произвольное количество значений: (a b c ... x y z ...) - подробнее об этом можно почитать в [$]. А еще там есть очень классные комбинаторы, абстрагирующие разные паттерны рекурсии - эдакий фикспоинт на стероидах.
Кстати, внимательный читатель мог заметить, что 0 (ноль) в комбинаторную форму мы так и не перевели. Оставляю это внимательному читателю в качестве упражнения; а заодно можно и ознакомиться с полной версией исчисления "лыжных комбинаторов" [@] и посмотреть на альтернативные (минимальные и не очень) базисы [&].
Такие дела.
- http://evincarofautumn.blogspot.ru/2012/02/why-concatenative-programming-matters.html
- [@]: https://en.wikipedia.org/wiki/SKI_combinator_calculus
- https://en.wikipedia.org/wiki/Church_encoding
- http://concatenative.org:8080/wiki/view/Concatenative%20language
- [$]: http://www.kevinalbrecht.com/code/joy-mirror/forth-joy.html
- [&]: http://tunes.org/~iepos/joy.html
- http://kittenlang.org/
- http://factorcode.org/
- http://www.nsl.com/k/xy/xy.htm
- http://thinking-forth.sourceforge.net/#21CENTURY