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

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

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

Съдържание

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

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

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

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

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

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

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

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

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

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

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

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

Други езици

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

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

Напишете рецензия на статията "Комбинаторно програмиране"

Бележки

  1. ↑ [www.stanford.edu/class/cs242/readings/backus.pdf J. Backus. Може ли програмирането да бъде освободено от стила на фон нойман? Съобщения на ACM, 21 (8): 613-641, 1978 г.] (PDF,

3MB)

  • ↑Джерард О'Ригън. Гл. 7. John Backus // Giants of Computing: A Compendium of Select, Pivotal Pioneers. - Springer, 2013. - S. 31. - 306 с. - ISBN 9781447153405.
  • ↑ [hillside.net/plop/plop97/Proceedings.ps/noble.ps „Аргументи и резултати“] (PostScript формат 808KB)

    • [fprog.ru/2009/issue3/eugene-kirpichov-elements-of-functional-languages/#htoc6 Безсмислен стил] (руски) - раздел в статията на Евгений Кирпичев [fprog.ru/2009/issue3/eugene-kirpichov- елементи -на-функционални-езици/Елементи на функционални езици] в списание [fprog.ru/2009/issue3/ 3-ти брой] [fprog.ru/ Практическо функционално програмиране]
    • [fprog.ru/2010/issue4/denis-moskvin-compositions-sections/ Денис Москвин. Композиционни раздели като безсмислен инструмент за стил] в [fprog.ru/2009/issue4/ 4-ти брой] на списанието [fprog.ru/ Практическо програмиране]
    • [community.livejournal.com/ru_lambda/10085.html Комбинаторен стил на програмиране] (руски) в [community.livejournal.com/ru_lambda/ ru_lambda]
    • [www.stanford.edu/class/cs242/readings/backus.pdf Може ли програмирането да бъде освободено от стила на фон Нойман?] Лекция на Тюринг от Джон Бакус.
    • [portal.acm.org/citation.cfm?id=114065&dl=GUIDE&coll=GUIDE Чисти функции в APL и J] - използването на имплицитно програмиране на езици от семейство APL
    • Е. Кирпичев. [www.rsdn.ru/article/java/JavaFP.xml Функционално програмиране в Java]

    : неправилно или липсващо изображение

    • Предоставете бележки под линия, за да предоставите по-точни източници.
    • Wikify библиография.

    Откъс от комбинаторно програмиране