Я могу понять, как создать и подумать об исчислении SKI и BCKW, но я никогда не смогу найти практическое применение. Может быть, я недостаточно глубоко смотрю? То есть, мне интересно, если (пример только, пожалуйста, я не подразумеваю, что это правда). Java Servlets широко используют S, а генераторы Python - пример BCW, и я просто не могу видеть сквозь лес деревьев?Практическое применение исчисления SKI и BCKW
В Haskell это everywhere!
<$>flippureid<*>joinС точки Haskell зрения, <$> означает "делать в контексте".
(+2) <$> (*3) средство добавить два после умножения на три.(+2) <$> [1,2,3] означает добавить два в каждый элемент в списке.(+2) <$> (read . getLine) означает добавить два в номер, который я только что прочитал.(+2) <$> someParser означает добавить два в номер, который я только что разобрал.Вещи, имеющие контекст, называются Функторы. Все ваши итераторы на Java/Python/C++ - это просто странные наивысшие версии функторов.
Другое соединение: комбинатор S и K вместе являются завершающими. В Haskell pure и <*> вместе образуют аппликативный функтор.
Конечно, понимание того, как подходят другие комбинаторы, потребует изучения Haskell. Но этот пример показывает, как комбинаторы настолько укоренены в языке.
Хотя расчеты лямбда и SKI не отражают системы ввода и вывода большинства языков программирования (таких как графика, сетевые соединения или, возможно, даже стандартный ввод и вывод), способ структурирования практического компьютерного программирования соответствует Lambda (и, следовательно, SKI и BCKW), такие как идея рекурсии и несколько способ ее функционирования. Многие из этих языков программирования имеют лямбда-абстракции для использования в качестве функций.
Это все о контроле.
Возможно, начать на более низком уровне. Аппликативная система - это просто система, в которой объекты могут быть применены к другим объектам. Простым примером аппликативной системы является bash. ls | more Можно предположить, что они находятся в какой-то среде, и что вышеупомянутое означает ls в среде, а затем делать больше. В аппликативных обозначениях это more @ (ls @ environment) Однако можно было сделать более сложные вещи, такие как ls | шаблон grep | подробнее Итак, теперь в прикладной нотации это больше @ ((grep @ pattern) @ (ls @ environment)). Извещение grep @ pattern. Grep применяется к шаблону, который возвращает программу в соответствие с этим шаблоном в результате ls. Это точка приложения, применение программы к аргументам, создание новых программ из «атомных» (так называемых встроенных) программ. Однако мы не можем делать слишком много программирования только с примитивным приложением или встроенными. Нам нужен способ структурирования нашего вклада и применения наших примитивов на наш вклад.
Это где лямбда приходит. С помощью лямбда можно обобщить (Grep @ рисунок) Для применения Grep к любому входу, (Grep @ X) Однако, мы должны иметь способ, чтобы получить вход в Grep. Таким образом, мы обычно используем функции. f (X) = grep @ X Вышеупомянутый процесс называется абстрагированием аргумента. Но нет оснований думать, что имя f является специальным, поэтому у нас есть синтаксис для него: lambda X. grep @ X Затем лямбда X. grep @ X может быть применена к входу, а вход будет заменен на тело и оценен. Однако замена может стать беспорядочной, связанные переменные могут быть сложными для реализации на машине. S-K-I (или B, C, K, W) дает возможность делать лямбда-материал без подстановки и вместо этого просто заменяет приложения.
Напомним, приложение - вот что это такое. Очень удобно рассуждать на уровне применения программы к чему-то (возможно, к другой программе). Лэмбда-исчисление дает возможность структурировать вход и применение программ к аргументам. SKI дает возможность делать лямбда без явного подмены.
Следует отметить, что сокращение SKI по своей сути является ленивым, поэтому, возможно, потребуется некоторое рассмотрение в реальном использовании SKI для структурирования приложения. Действительно, аргументы теперь могут быть полностью оценены и также могут быть частичным приложением. Можно обойти это с теорией типов и только оценивать программу на ее входе, если программа находится в главном положении приложения. То есть, если писать с закрытыми лямбда-терминами, переводиться в SKI, , то если p @ arg1 @ .... Должно быть, если p - примитивная программа, то переписывание завершено, и поэтому все это аргументы 1) доступны, 2) полностью оценены.Тем не менее, я этого не доказал, и это может быть неверно при достаточно сильной теории типов ...
Расчеты SKI и BCKW отличаются от исчисления лямбда (который имеет хорошо известные приложения в концепции функционального программирования), потому что они находятся в point-free form. См. Также tacit programming. Они составляют основу понимания того, как создавать функциональные программы без названных аргументов.
Мы видим его применение на определенных языках (например, Joy и Cat). Я один раз posted on Lambda-the-Ultimate.org о связи SK исчисления с Cat и радость.
Для чего его ценность: расчеты BCKW и SKI (или SK) практически идентичны, но основа BCKW вышла из моды.