Комбинаторное программирование
Комбинато́рное программи́рование (англ. function-level programming) — парадигма программирования, использующая принципы комбинáторной логики, то есть не требующая явного упоминания аргументов определяемой функции (программы) и использующая вместо переменных комбинаторы и композиции. Является особой разновидностью функционального программирования, но, в отличие от основного его направления, комбинаторное программирование не использует λ-абстракцию.
Концептуализировал и популяризовал парадигму Джон Бэкус в тьюринговской лекции 1977 года «Можно ли освободить программирование от стиля фон Неймана»[1], в которой представил язык FP[англ.]. В конце 1980-х Бэкус с коллегами из Алмаденского исследовательского центра IBM в развитие идей FP и конкатенативной парадигмы разработали язык FL[англ.]. При этом элементы конкатенативного программирования проявляются уже в APL, а в более поздних его разновидностях — языках J и K — заимствованы многие идеи FP, и оформлены в концепцию бесточечного стиля, которая применима не только для функционального программирования в строгом смысле (в частности, элементы такого стиля имеют место в оболочках UNIX при применении конвейеров для перенаправления ввода-вывода).
Пример для языка J: определение функции (в терминах J — «глагола») для вычисления среднего арифметического:
avg =. +/ % #
где +/ — «монада» (унарная операция) суммирования списка, % — «диада» (бинарная операция) деления, а # — «диада» взятия длины списка. Данная конструкция (в терминах J — «предложение») читается «среднее есть сумма, поделённая на длину». Подобные конструкции из трёх функций-глаголов в J принято называть «вилками».
Выразительные возможности современных универсальных функциональных языков, таких как ML и Haskell, позволяют достаточно комфортно оставаться в парадигме комбинаторного программирования, то есть, не прибегать к λ-абстракции и переменным вообще. Например, функция суммирования списков на Haskell с использованием комбинатора foldr:
sum = foldr (+) 0
Фактически, конкатенативное программирование обеспечивает бесточечный стиль, притом в ранних конкатенативных языках, таких как Форт, свобода от именованных переменных достигается не математически, путём определения функций в виде комбинации каких-то других функций, а императивно, путём последовательных манипуляций со стеком. В современных конкатенативных языках, таких как Factor, имеется тенденция к использованию функциональных комбинаторов, а не явных манипуляций со стеком.
Возможно также использование бесточечного стиля и в языках, не поддерживающих функции высшего порядка и частичное применение, например, посредством имитации функций высшего порядка посредством шаблона Curried Object[2].
Примечания
- ↑ Джон Бэкус. Можно ли освободить программирование от стиля фон Неймана? Функциональный стиль и соответствующая алгебра программ // Лекции лауреатов премии Тьюринга = Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. — М.: Мир, 1993. — С. 84—158. — 560 с. — 2000 экз. — ISBN 5-03-002130-2.
- ↑ «Arguments and results» Архивная копия от 24 июня 2016 на Wayback Machine (Формат PostScript, 808KB)
Ссылки
- Бесточечный стиль (рус.) — раздел в статье Евгения Кирпичёва Элементы функциональных языков в 3-м выпуске журнала Практика функционального программирования
- Денис Москвин. Сечения композиции как инструмент бесточечного стиля в 4-м выпуске журнала Практика функционального программирования
- Pure Functions in APL and J (англ.) — использование неявного программирования в языках семейства APL
- Е. Кирпичёв. Функциональное программирование в Java
