Комбінаторне програмування – це
Комбінаторне програмування(англ.function-level programming) — це парадигма програмування, що не вимагає явної згадки аргументів визначеної функції (програми) і використовує замість змінних комбінатори та композицію функцій (але не λ- абстракцію). Таким чином комбінаторне програмування можна вважати особливим різновидом функціонального.
Зміст
Історія виникнення
Ідея опису функцій без звернення до їх аргументів бере своє коріння з математики. У 1924 р., ще до створення лямбда-обчислення, Шейнфінкель створив комбінаторну логіку — формалізм, на якому заснована парадигма, що тут описується (подібно до того, як класичне функціональне програмування засноване на лямбда-обчисленні Черча).
Парадигму програмування, засновану на комбінаторній логіці, вперше описав Джон Бекус у своїй знаменитій тьюрингівській лекції «Чи може програмування звільнитися від стилю Фон-Неймана» [1] На основі даних ідей Бекус створив мови FP (англ.) українською. та FL (англ.) україн. .
Неявне програмування в J і K
У мовах J і K - сучасних різновидах APL цей підхід відомий якНеявне програмування(англ.tacit programming).
Ось класичний приклад мовою J - визначення функції (у термінах J - дієслова) для обчислення середнього арифметичного:
Тут +/ — монада (унарна операція) підсумовування списку, % діада (бінарна операція) поділу, а діада взяття довжини списку. Дана конструкція (пропозиція мови J) читається «середнє є сума, поділена на довжину». Подібні конструкції з трьох функцій-дієслів в J прийнято називати «вилками».
Безточковий стиль сучаснихфункціональних мов
За межами спільноти APL, у функціональних мовах сімейства ML і Haskell на комбінаторне програмування часто посилаються як набезточковий стиль(стиль, вільний від покажчиків англ.point-free programming, використовується також дещо зневажлива гра слів англ.(5>pointless programming ).
Наприклад, просту функцію підсумовування списків на Haskellі ми можемо «в лоб» визначити за допомогою рекурсії:
Це визначення легко спростити за допомогою комбінатора foldr :
і, нарешті, ми можемо перевести його в безточкову форму, вільну від явних імен параметрів:
Інші мови
Здебільшого «вільними від покажчиків» так само є конкатенативні мови. У класичному форті свобода від іменованих змінних досягається не математично, шляхом визначення функцій як комбінації якихось інших функцій, а імперативно, шляхом послідовних маніпуляцій зі стеком. Втім, у сучасних конкатенативних мовах, таких як Фактор, є тенденція до використання функціональних комбінаторів, а не явних маніпуляцій зі стеком.
Можливе використання цього стилю в нефункціональних мовах, які не підтримують функції вищого ладу та часткове застосування. Функції вищого порядку можна імітувати, наприклад, з допомогою об'єктів. Для імітації часткового застосування служить патерн Curried Object, описаний у статті Джеймса Нобла. [2] Приклади такого використання можна знайти у статті Є. Кирпічова "Функціональне програмування в Java". [3]