Комбінаторне програмування

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

Концептуалізував та популяризував парадигму Джон Бекус в тюрінговскій лекції 1977 року «Чи можливо звільнити від стилю програмування фон Неймана», в якій представив мову ^[en]. Наприкінці 1980-х Бекус із колегами з ^[en] в розвиток ідей FP і конкатенативної парадигми розробили мову ^[en]. При цьому елементи конкатенативне програмування проявляються вже в APL, а в пізніших його різновидах — мовами J и K — запозичені багато ідей FP, і оформлені в концепцію безточкового стилю, який може бути застосований не тільки для функціонального програмування в строгому сенсі (Зокрема, елементи такого стилю мають місце в оболонках UNIX при застосуванні конвеєрів для перенаправлення вводу-виводу.

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

avg =. +/ % #

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

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

sum = foldr (+) 0

Фактично, конкатенативне програмування забезпечує безточковий стиль, притому в ранніх конкатенативного мовах, таких як Форт, свобода від іменованих змінних досягається не математично, шляхом визначення функцій у вигляді комбінації якихось інших функцій, а імперативно, шляхом послідовних маніпуляцій зі стеком. В сучасних конкатенативних мовах, таких як ^[en], є тенденція до використання функціональних комбінаторів, а не явних маніпуляцій зі стеком.

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

Зноски

1. Джон Бекус. Чи можливо звільнити від стилю програмування фон Неймана? Алгебра програм у функціональному стилі // Лекції лауреатів премии Тюрінга = Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. — Світ, 1993. — С. 84—158. — 2000 прим. — .
2. «Arguments and results» [ 24 Червня 2016 у Wayback Machine.] (Формат PostScript, 808KB)