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

Комбинаторно програмиране (англ. програмиране на функционално ниво ) Дали е парадигма за програмиране, която не изисква изрично споменаване на аргументите на функцията (програмата), която се дефинира и използва комбинатори и състав на функции (но не λ-абстракция) вместо променливи. По този начин комбинаторното програмиране може да се счита за специален вид функционалност.

Съдържание

История на произхода

Идеята за описване на функции, без да се позовава на техните аргументи, има своите корени в математиката. През 1924 г., дори преди създаването на ламбда изчислението, Шейнфинкел създава комбинаторна логика - формализмът, на който се основава описаната тук парадигма (подобно на това как класическото функционално програмиране се основава на ламбда смятането на Църквата).

Парадигмата за програмиране, базирана на комбинаторната логика, е описана за пръв път от Джон Бакус в известната му лекция на Тюринг „Може ли програмирането да се освободи от стила на Фон Нойман“ [1] Въз основа на тези идеи Бакус създава FP езиците. и FL (англ.) руски. .

Имплицитно програмиране в J и K

В езиците J и K, съвременните вкусове на APL, този подход е известен като Неявно програмиране (англ. мълчаливо програмиране ).

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

Тук +/е монадата (унарна операция) обобщение на списъка,% диада (двоична операция) разделение и # диада за вземане на дължината на списъка. Тази конструкция (J изречение на език) гласи "средната стойност е сумата, разделена на дължината". Такива конструкции на три глаголни функции в J обикновено се наричат ​​„вилици".

Безсмисленият стил на съвременните функционални езици

Извън APL общността, на функционалните езици на семействата ML и Haskell, комбинаторното програмиране често се нарича безсмислен стил (стил, без английски указатели. безточково програмиране , използва се също донякъде унизителна английска игра на думи. безсмислено програмиране ).

Например можем да дефинираме проста функция за сумиране на списъци в Haskell, използвайки рекурсия:

Тази дефиниция може лесно да бъде опростена с помощта на комбинатора за сгъване:

и накрая, можем да го преобразуваме в безсмислена форма, без изрични имена на параметри:

Други езици

В по-голямата си част „без указател“ са обединяващи езици. В класическия форт свободата от именувани променливи се постига не математически, чрез дефиниране на функции като комбинация от някои други функции, а задължително, чрез последователни манипулации на стека. Съвременните конкатенативни езици като Factor са склонни да използват функционални комбинатори, а не изрични манипулации на стека.

Възможно е да се използва този стил в нефункционални езици, които не поддържат функции от по-висок ред и частично приложение. Функциите от по-висок порядък могат да бъдат имитирани, като например се използват обекти. Моделът "Curried Object", описан в статията от Джеймс Нобъл, се използва за симулиране на частично приложение. [2] Примери за такова използване могат да бъдат намерени в статията на Е. Кирпичев „Функционално програмиране в Java“. [3]