Sistem de programare funcțional

Termenul Sistem funcțional de programare ( sistem FP prescurtat ) descrie un concept de limbaje funcționale de programare dezvoltat de John W. Backus . Backus a pornit de la observația că limbajele de programare obișnuite reprezintă programele de calculator ca o manipulare a datelor serializate la scară mică, deoarece acestea se bazează pe modelul mașinii von Neumann. Potrivit lui Backus, acest lucru duce la două probleme. Pe de o parte, că programele von Neumann sunt dificil de paralelizat. Pe de altă parte, este dificil să se argumenteze formal despre proprietățile programelor Von Neumann sau să le transforme. Sistemul de programare funcțională abordează aceste probleme prin construirea unui program dintr-o compoziție . Procedând astfel, cantități mai mari de date structurate sunt transmise de la o funcție la alta, ceea ce permite tehnic procesarea paralelă. Backus a considerat, de asemenea, ca acest mod de lucru să fie baza unei noi arhitecturi de calculatoare care profită de această posibilitate. ${\ displaystyle P}$${\ displaystyle P = F_ {n} \ circ F_ {n-1} \ circ F_ {n-2} \ circ .. \ circ F_ {1}}$

Într-un discurs cu ocazia prezentării Premiilor Turing către Backus în 1977, acesta din urmă a prezentat ideea sistemelor FP. Titlul prelegerii a fost: Programarea poate fi eliberată de stilul von Neumann? Un stil funcțional și algebra sa de programe . Într-un alt eseu, Backus a decis să folosească termenul de programare la nivel de funcție .

Program funcțional pentru calcularea produsului scalar

Cu calculul produsului scalar, Backus oferă un exemplu instructiv pentru aplicarea sistemului de programare funcțională .

Funcția („Produs interior”), care determină produsul scalar al doi vectori, este compusă din calculul concatenat al celor trei funcții și (în această ordine), care este exprimată ca o compoziție a funcției după cum urmează : ${\ displaystyle IP}$${\ displaystyle Trans, (\ alfa \ times)}$${\ displaystyle (/ +)}$

${\ displaystyle {\ begin {align} IP & = (/ +) \ circ (\ alpha \ times) \ circ Trans \ end {align}}}$

Iată o funcție care transpune o matrice . În FP, de exemplu, această relație este notată după cum urmează pentru o matrice : ${\ displaystyle Trans}$${\ displaystyle {\ bigl (} {\ begin {smallmatrix} 3 & 4 \\ 7 & 1 \\ - 1 & 0 \ end {smallmatrix}} {\ bigr)}}$

${\ displaystyle {\ begin {align} Trans (<< 3.4>, <7.1>, <- 1.0 >>) & = << 3.7, -1>, <4.1.0 >> \ end {align}}}$

Simbolurile și denotă funcționalități . Acestea preiau alte funcții pentru a crea funcții noi. In der Form preia funcția de multiplicare din două cifre și oferă o funcție care se aplică tuturor elementelor unei liste de perechi trecute. Rezultatul calculului este apoi lista produselor individuale. În limbajele de programare moderne, acest lucru se numește mai ales funcțional . Backus îi numește și pe ei . ${\ displaystyle \ alpha}$${\ displaystyle /}$${\ displaystyle (\ alpha \ times)}$${\ displaystyle \ alpha}$${\ displaystyle \ times}$${\ displaystyle \ times}$${\ displaystyle \ alpha}$mapApplyToAll

Funcția corespunde în cele din urmă aproximativ cu funcția sau în programarea funcțională obișnuită. Backus o numește , ceea ce înseamnă că expresia reprezintă o funcție care inserează operația între două elemente într-o listă dată . Deci se aplică . ${\ displaystyle /}$reducefoldInsert${\ displaystyle (/ +)}$${\ displaystyle +}$${\ displaystyle (/ +) (<2,3,4>) = 2 + 3 + 4 = 9}$

Calculul funcției produsului scalar se aplică celor doi vectori și poate fi apoi înțeles astfel: ${\ displaystyle IP}$${\ displaystyle <1,2,3>}$${\ displaystyle <6,5,4>}$

${\ displaystyle {\ begin {align} & IP: << 1,2,3>, <6,5,4 >> \\ & = (/ +) \ circ (\ alpha \ times) \ circ trans: < <1,2,3>, <6,5,4 >> \\ & = (/ +) \ circ (\ alfa \ times) :( trans: << 1,2,3>, <6,5, 4 >>) \\ & = (/ +): ((\ alfa \ times): << 1,6>, <2,5>, <3,4 >>) \\ & = (/ +): <\ times: <1,6>, \ times: <2,5>, \ times: <3,4 >> \\ & = (/ +): <6,10,12> \\ & = +: <6, +: <10.12 >> \\ & = 28 \ end {align}}}$

Procesul aritmetic reprezintă astfel o conductă de procesare fără o stare internă, care convertește intrarea în ieșire în trei pași de lucru separați. Pașii de lucru înșiși pot fi paralelați la diferite grade. De asemenea, ar fi posibil să creați o conductă hardware pentru program . ${\ displaystyle IP}$

Notări în sistemul FP

Backus folosește o notație care se bazează pe convenții matematice și o completează cu expresiile condiționate ale lui McCarthy și o reprezentare recursivă pentru buclele WHILE. Este crucial ca fiecare entitate să reprezinte o funcție și, prin urmare, să fie compatibilă cu operatorul de compoziție . ${\ displaystyle \ circ}$

Numere ca selectori

Limbajul de programare vector APL a avut o influență decisivă asupra sistemului de programare funcțională bazat pe Combinator de către John Backus, care funcționează fără o listă de variabile lambda ; în schimb selectoarele (numerele) sunt folosite pentru a alege valorile dintr-o secvență.

1:<x1,...,xn> → x1i:<x1,...,xi,...,xn> → xi

Număr fix de combinatoare / forme funcționale

Combinând ...	... Formă
cerere	f : x	= f (x)
compoziţie	(f o g): x	= f (g (x))
constructie	[ f 1 , f 2 , ... , f n ]  : x	= < f 1 : x , f 2 : x , ... , f n : x >
condiție	(p → f ; g): x	= dacă p: x = T atunci f: x în caz contrar dacă p: x = F atunci g: x în caz contrar ⊥
constant	~ x: y	= dacă y = ⊥ atunci ⊥ altfel x
Introduce	( / f): < x 1 , x 2 , ..., x n >	= f: < x 1 , f: < x 2 , ... f: < x n-1 , x n >>>
Aplica la toate	( α f): < x 1 , x 2 , ..., x n >	= < f: x 1 , f: x 2 , ..., f: x n >
De la binar la unar	bu fx
În timp ce bucla	(în timp ce pf): x	= dacă p: x = T atunci (în timp ce pf) : (f : x) altfel dacă p: x = F atunci x altfel ⊥

și definirea funcțiilor monadice:

Def Name ≡ Term

Cu ⊥ Backus însemna valoarea „jos”, o valoare precum „nedefinit” sau „excepție”. T și F sunt valorile pentru „adevărat” și „fals”.

Dezvoltarea ulterioară a sistemelor FP

O echipă formată din John Backus, John Williams și Edward Wimmers a dezvoltat succesorul FL (Function-Level Programming) la Centrul de Cercetare IBM Almaden în 1989 . Cu acest concept, ar trebui să poți rearanja programele la fel de confortabil pe cât se pot rearanja ecuațiile în matematică, transparența referențială trebuind să fie garantată pentru acest lucru. Aceasta ar trebui să servească o nouă dimensiune a optimizării programului (EFL). Cu FL, Backus a vrut să transforme „informatica de atunci” într-o disciplină de inginerie. Din nou, unele dezvoltări ulterioare ale FL sunt J (aplicație precum APL) și PLaSM, un limbaj de programare pentru geometrie.

Implementări FP

• FP INTERACTIV, pagina de ajutor pentru aceasta
• Compilator FP care se compilează la C, repo la
• Interpret Fp în Lisp
• Trivia FP, repo FP la
• Plasm ( P rogramming La nguage pentru S Olid M odeling), un limbaj de programare funcțional pentru utilizare în CAD , care de la Universitatea Roma Tre este dezvoltat.

Vezi si

• Limbaj de programare algebric

literatură

• Wolfram-Manfred Lippe : Programare funcțională și aplicativă: elemente de bază, limbaje, tehnici de implementare . Prima ediție. Springer , Berlin 2009, ISBN 978-3-540-89091-1 ( previzualizare limitată în căutarea cărților Google). 
• Alberto Paoluzzi ea: Programare geometrică pentru proiectarea asistată de computer . Prima ediție. Wiley , Chichester 2003, ISBN 978-0-471-89942-6 ( previzualizare limitată în Căutare de cărți Google). 

Dovezi individuale

1. ↑ Lippe 2009, p. 73
2. ↑ Programarea poate fi eliberată de stilul von Neumann? Un stil funcțional și algebra sa de programe Universitatea Stanford, 1978 (PDF; 2,87 MB)
3. ↑ Programe de nivel funcțional ca obiecte matematice (PDF)
4. ↑ FP INTERACTIV
5. ↑ INTERACTVE FP - Ajutor
6. ↑ Furry Paws , un compilator FP
7. ↑ fp-interpret-in-lisp
8. ↑ Interpret FP, creat în Delphi
9. ↑ Limbaj funcțional PLaSM pentru calcul cu geometrie. Alberto Paoluzzi ( Universitatea din Roma III ), accesat la 27 noiembrie 2010 . 

Link-uri web

• Critica eseului Backus de Edsger W. Dijkstra (PDF; 143 kB)
• John Backus: Programare la nivel de funcție și limbajul FL , 1987 (video)
• Proiectul FL: Proiectarea unui limbaj funcțional (PDF; 315 kB)
• Manual de limbaj FL, părțile 1 și 2 (PDF; 20 MB)
• Introducere în FL și PLaSM (PDF)
• FP (engleză)
• Scripturi către sisteme FP