Kombinatorisk programmering ( engelsk funktionsnivåprogrammering ) är ett programmeringsparadigm som använder principerna för kombinatorisk logik , det vill säga det kräver inte explicit omnämnande av argumenten för den definierade funktionen (programmet) och använder kombinatorer och kompositioner istället för variabler . Det är en speciell typ av funktionell programmering , men till skillnad från dess huvudriktning använder kombinatorisk programmering inte λ-abstraktion .
Paradigmet konceptualiserades och populariserades av John Backus i Turings föreläsning 1977 "Är det möjligt att frigöra programmering från von Neumann-stilen" [1] , där han introducerade FP- språket . I slutet av 1980-talet utvecklade Backus och kollegor vid IBM Almaden Research Center språket FL som en utveckling av FP:s idéer och det konkatenativa paradigmet . Samtidigt förekommer element av konkatenativ programmering redan i APL , och i dess senare varianter - språk J och K - är många idéer om FP lånade och inramade i konceptet meningslös stil , som inte bara är tillämpligt för funktionell programmering i strikt mening (särskilt delar av sådana stilar förekommer i UNIX- skal när man använder rör för I/O-omdirigering ).
Exempel för J-språket: definiera en funktion (i termer av J - "verb") för att beräkna det aritmetiska medelvärdet:
avg =. +/ % #var +/ är "monad" (unär operation) för listsummation, % är "dyad" (binär operation) för division och # är "dyad" för att ta längden på listan. Denna konstruktion (i termer av J - "mening") lyder " genomsnittet är summan dividerat med längden ". Liknande konstruktioner av tre funktionsverb i J kallas "gafflar".
Expressiviteten hos moderna universella funktionella språk, som ML och Haskell , gör det ganska bekvämt att stanna i det kombinatoriska programmeringsparadigmet, det vill säga att inte tillgripa λ-abstraktion och variabler alls. Till exempel, funktionen Haskell list summa med hjälp av kombinatorn foldr:
sum = foldr (+) 0Faktum är att konkatenativ programmering ger en meningslös stil, dessutom, i tidiga konkatenativa språk, såsom Forth , uppnås frihet från namngivna variabler inte matematiskt, genom att definiera funktioner som en kombination av några andra funktioner, utan imperativt genom successiva stackmanipulationer . Moderna konkatenativa språk som Factor tenderar att använda funktionella kombinatorer snarare än explicita stackmanipulationer.
Det är också möjligt att använda den prickfria stilen på språk som inte stöder funktioner av högre ordning och partiell tillämpning, till exempel genom att efterlikna funktioner av högre ordning genom mönstret Curried Object [2] .