Комбинаторное программирование

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Парадигмы программирования
 • Императивная
(контрастирует с декларативной)
Процедурная
Структурная
Аспектно-ориентированная
Объектно-ориентированная
Агентно-ориентированная
Компонентно-ориентированная
Прототипно-ориентированная
Обобщённое программирование

 • Декларативная
(контрастирует с императивной)

Чистота языка
Чистота функции
Функциональная
В терминах Рефал-машины
Аппликативная
Комбинаторная
Бесточечная[en]
(чистая конкатенативная)
Логическая
Ограничениями

 • Конкатенативная
 • Векторная[en]
 • Метапрограммирование

Языково-ориентированная
Предметно-ориентированная
Пользователями[en]
Автоматизация процесса программирования
Рефлексивность
Гомоиконность[en]

 • Связанные темы

Программирование в крупном и мелком масштабе[en]
Модульность
Полиморфизм
Продолжения и CPS[en]*
Параллелизм и конкурентность

 • Методы и алгоритмы

Автоматное
Динамическое
Потоков данных
Событийно-ориентированное
Реактивное
Сервис-ориентированное

Комбинáторное программирование (англ. function-level programming) — это парадигма программирования, не требующая явного упоминания аргументов определяемой функции (программы) и использующая вместо переменных комбинаторы и композицию функций (но не λ-абстракцию). Таким образом комбинаторное программирование можно считать особой разновидностью функционального. Разновидностью комбинаторного можно считать конкатенативное программирование.

История возникновения[править | править вики-текст]

Идея описания функций без обращения к их аргументам берет свои корни из математики. В 1924 г., ещё до создания лямбда-исчисления, Шейнфинкель создал комбинáторную логику — формализм, на котором основана описываемая здесь парадигма (подобно тому, как классическое функциональное программирование основано на лямбда-исчислении Чёрча).

Парадигму программирования, основанную на комбинаторной логике впервые описал Джон Бэкус в своей знаменитой тьюринговской лекции «Можно ли освободить программирование от стиля фон Неймана»[1][2] На основе данных идей Бэкус создал языки FP (англ.) и FL (англ.).

Неявное программирование в J и K[править | править вики-текст]

В языках J и K (современных разновидностях APL) этот подход известен как неявное программирование (англ. tacit programming).

Вот классический пример на языке J — определение функции (в терминах J — глагола) для вычисления среднего арифметического:

avg =. +/ % #

Здесь +/ — монада (унарная операция) суммирования списка, % диада (бинарная операция) деления, а # диада взятия длины списка. Данная конструкция (предложение языка J) читается «среднее есть сумма, поделенная на длину». Подобные конструкции из трёх функций-глаголов в J принято называть «вилками».

Бесточечный стиль современных функциональных языков[править | править вики-текст]

За пределами сообщества APL, в функциональных языках семейства ML и Haskell на комбинаторное программирование часто ссылаются как на бесточечный стиль (стиль, свободный от указателей англ. point-free programming, используется также несколько уничижительная игра слов англ. pointless programming).

К примеру, простую функцию суммирования списков на Haskell мы можем «в лоб» определить с помощью рекурсии:

sum (x:xs) = x + (sum xs)
sum [] = 0

Это определение легко упростить, используя комбинатор foldr:

sum xs = foldr (+) 0 xs

и, наконец, мы можем перевести его в бесточечную форму, свободную от явных имён параметров:

sum  = foldr (+) 0

Другие языки[править | править вики-текст]

По большей части «свободными от указателей» являются конкатенативные языки. В классическом Форте свобода от именованных переменных достигается не математически, путём определения функций в виде комбинации каких-то других функций, а императивно, путём последовательных манипуляций со стеком. Впрочем, в современных конкатенативных языках, таких как Фактор, имеется тенденция к использованию функциональных комбинаторов, а не явных манипуляций со стеком.

Возможно использование данного стиля в нефункциональных языках, не поддерживающих функции высшего порядка и частичное применение. Функции высшего порядка можно имитировать, к примеру, с помощью объектов. Для имитации частичного применения служит паттерн «Curried Object», описанный в статье Джеймса Нобла.[3]

Примечания[править | править вики-текст]

  1. J. Backus. Can programming be liberated from the von neumann style? Communications of the ACM, 21(8):613-641, 1978. (PDF, ~3MB)
  2. Gerard O’Regan. Ch. 7. John Backus // Giants of Computing: A Compendium of Select, Pivotal Pioneers. — Springer, 2013. — С. 31. — 306 с. — ISBN 9781447153405.
  3. «Arguments and results» (Формат PostScript, 808KB)

Ссылки[править | править вики-текст]