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

Концептуализировал и популяризовал парадигму Джон Бэкус в тьюринговской лекции 1977 года «Можно ли освободить программирование от стиля фон Неймана» , в которой представил язык . В конце 1980-х Бэкус с коллегами из Алмаденского исследовательского центра IBM в развитие идей FP и конкатенативной парадигмы разработали язык . При этом элементы конкатенативного программирования проявляются уже в APL , а в более поздних его разновидностях — языках J и K — заимствованы многие идеи FP, и оформлены в концепцию бесточечного стиля , которая применима не только для функционального программирования в строгом смысле (в частности, элементы такого стиля имеют место в оболочках UNIX при применении конвейеров для перенаправления ввода-вывода ).

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

avg =. +/ % #

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

Выразительные возможности современных универсальных функциональных языков, таких как ML и Haskell , позволяют достаточно комфортно оставаться в парадигме комбинаторного программирования, то есть, не прибегать к λ-абстракции и переменным вообще. Например, функция суммирования списков на Haskell с использованием комбинатора foldr :

sum = foldr (+) 0

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

Возможно также использование бесточечного стиля и в языках, не поддерживающих функции высшего порядка и частичное применение, например, посредством имитации функций высшего порядка посредством шаблона .

Примечания

Ссылки

• (рус.) — раздел в статье Евгения Кирпичёва в журнала
• в журнала
• (англ.) — использование неявного программирования в языках семейства APL
• Е. Кирпичёв.