Functioneel programmeersysteem

De term Functioneel Programmeersysteem (afgekort FP-systeem ) beschrijft een concept van functionele programmeertalen ontwikkeld door John W. Backus . Backus ging uit van de constatering dat gangbare programmeertalen computerprogramma's vertegenwoordigen als kleinschalige geserialiseerde datamanipulatie, omdat ze gebaseerd zijn op het machinemodel van von Neumann. Volgens Backus levert dit twee problemen op. Enerzijds zijn die programma's van von Neumann moeilijk te parallelliseren. Aan de andere kant dat het moeilijk is om formeel te discussiëren over de eigenschappen van Von Neumann-programma's of om ze te transformeren. Het Functioneel Programmeersysteem pakt deze problemen aan door een programma te construeren vanuit een compositie . Daarbij worden grotere hoeveelheden gestructureerde gegevens van de ene functie naar de andere doorgegeven, wat technisch parallelle verwerking mogelijk maakt. Backus heeft ook overwogen om van deze manier van werken de basis te maken van een nieuwe computerarchitectuur die gebruik maakt van deze mogelijkheid. ${\ weergavestijl P}$${\ displaystyle P = F_ {n} \ circ F_ {n-1} \ circ F_ {n-2} \ circ .. \ circ F_ {1}}$

In een toespraak ter gelegenheid van de uitreiking van de Turing Awards aan Backus in 1977, presenteerde deze laatste het idee van FP-systemen. De titel van de lezing was: Kan programmeren worden bevrijd van de von Neumann-stijl? Een functionele stijl en zijn algebra van programma's . In een ander essay besloot Backus de term programmeren op functieniveau te gebruiken .

Functioneel programma voor het berekenen van het scalaire product

Met de berekening van het scalaire product geeft Backus een leerzaam voorbeeld voor de toepassing van het Functioneel Programmeersysteem .

De functie ("Inner Product"), die het scalaire product van twee vectoren bepaalt, is samengesteld uit de aaneengeschakelde berekening van de drie functies en (in deze volgorde), die als volgt wordt uitgedrukt als een functiesamenstelling : ${\ displaystijl IP}$${\ displaystyle Trans, (\ alpha \ times)}$${\ weergavestijl (/ +)}$

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

Hier is een functie die een matrix transponeert . In FP wordt deze relatie bijvoorbeeld als volgt genoteerd voor een matrix : ${\ weergavestijl Trans}$${\ displaystyle {\ bigl (} {\ begin {smallmatrix} 3 & 4 \\ 7 & 1 \\ - 1 & 0 \ end {smallmatrix}} {\ bigr)}}$

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

De symbolen en duiden functionalen aan . Deze nemen andere functies over om nieuwe functies te creëren. In der Form neemt de tweecijferige vermenigvuldigingsfunctie over en biedt een functie die van toepassing is op alle elementen van een doorgegeven lijst van paren. Het resultaat van de berekening is dan de lijst van de individuele producten. In moderne programmeertalen wordt dit meestal functioneel genoemd . Backus noemt ze ook . ${\ weergavestijl \ alpha}$${\ weergavestijl /}$${\ weergavestijl (\ alpha \ tijden)}$${\ weergavestijl \ alpha}$${\ weergavestijl \ tijden}$${\ weergavestijl \ tijden}$${\ weergavestijl \ alpha}$mapApplyToAll

De functie komt uiteindelijk ongeveer overeen met de functie of in de gebruikelijke functionele programmering. Backus noemt het , wat betekent dat de uitdrukking een functie vertegenwoordigt die de bewerking tussen twee elementen in een gegeven lijst invoegt. Het is dus van toepassing . ${\ weergavestijl /}$reducefoldInsert${\ weergavestijl (/ +)}$${\ weergavestijl +}$${\ weergavestijl (/ +) (<2,3,4>) = 2 + 3 + 4 = 9}$

De berekening van de scalaire productfunctie wordt toegepast op de twee vectoren en kan dan als volgt worden begrepen: ${\ displaystijl IP}$${\ weergavestijl <1,2,3>}$${\ weergavestijl <6,5,4>}$

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

Het rekenproces vertegenwoordigt dus een verwerkingspijplijn zonder interne toestand, die de invoer in drie afzonderlijke werkstappen omzet in de uitvoer. De werkstappen zelf kunnen in verschillende mate worden geparalleliseerd. Het zou ook mogelijk zijn om een ​​hardwarepijplijn voor het programma te maken . ${\ displaystijl IP}$

Notaties in het FP-systeem

Backus gebruikt een notatie die losjes gebaseerd is op wiskundige conventies en vult deze aan met McCarthy's voorwaardelijke expressies en een recursieve representatie voor WHILE-lussen. Het is van cruciaal belang dat elke entiteit een functie vertegenwoordigt en daarom compatibel is met de compositie- operator. ${\ weergavestijl \ cirkel}$

Nummers als selectors

De vectorprogrammeertaal APL had een beslissende invloed op het op Combinator gebaseerde functionele programmeersysteem van John Backus, dat werkt zonder een lijst met lambda-variabelen ; in plaats daarvan worden selectors (nummers) gebruikt om waarden uit een reeks te kiezen.

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

Vast aantal combiners / functionele vormen

Combineren...	... Vorm
toepassing	f : x	= f (x)
samenstelling	(v o g): x	= f (g (x))
bouw	[ f 1 , f 2 , ... , f n ]  : x	= < f 1 : x , f 2 : x , ... , f n : x >
staat	(p → f ; g): x	= als p: x = T dan f: x anders als p: x = F dan g: x anders ⊥
constante	~ x: ja	= als y = ⊥ dan ⊥ anders x
Invoegen	( / f): < x 1 , x 2 , ..., x n >	= f: < x 1 , f: < x 2 , ... f: < x n-1 , x n >>>
Toepassen op alles	( Α f): < x 1 , x 2 , ..., x n >	= < f: x 1 , f: x 2 , ..., f: x n >
Binair naar Unair	bu fx
Herhalingslus	( terwijl pf): x	= als p: x = T dan ( terwijl pf) : (f : x) anders als p: x = F dan x anders ⊥

en de definitie van monadische functies:

Def Name ≡ Term

Met ⊥ bedoelde Backus de waarde “bottom”, een waarde als “undefined” of “exception”. T en F zijn de waarden voor "true" en "false".

Verdere ontwikkeling van FP-systemen

Een team bestaande uit John Backus, John Williams en Edward Wimmers ontwikkelde in 1989 de opvolger FL (Function-Level Programming) in het IBM Almaden Research Center . Met dit concept zou men programma's net zo gemakkelijk moeten kunnen herschikken als vergelijkingen in de wiskunde, hiervoor moest referentiële transparantie gegarandeerd zijn. Dit zou een nieuwe dimensie van programma-optimalisatie (EFL) moeten dienen. Met FL wilde Backus van de "toen nog computerwetenschap" een technische discipline maken. Weer enkele verdere ontwikkelingen van FL zijn J (applicatie zoals APL) en PLASM, een programmeertaal voor geometrie.

FP-implementaties

• INTERACTIEVE FP, helppagina hiervoor
• FP-compiler die zichzelf compileert naar C, repo naar
• Fp-tolk in Lisp
• FP trivia, FP repo naar
• Plasma ( P ROGRAMMERING La nguage voor S olid M odeling), een functionele programmeertaal voor gebruik in CAD , waarbij de Roma Tre University ontwikkeld.

Zie ook

• Algebraïsche programmeertaal

literatuur

• Wolfram-Manfred Lippe : Functioneel en applicatief programmeren: basis, talen, implementatietechnieken . 1e editie. Springer , Berlijn 2009, ISBN 978-3-540-89091-1 ( beperkte preview in Google Book Search). 
• Alberto Paoluzzi ea: Geometrisch programmeren voor computerondersteund ontwerp . 1e editie. Wiley , Chichester 2003, ISBN 978-0-471-89942-6 ( beperkt voorbeeld in Zoeken naar boeken met Google). 

Individueel bewijs

1. ↑ Lippe 2009, blz. 73
2. ↑ Kan programmeren worden bevrijd van de Von Neumann-stijl? Een functionele stijl en zijn algebra van programma's Stanford University, 1978 (PDF; 2,87 MB)
3. ↑ Programma's op functieniveau als wiskundige objecten (PDF)
4. ↑ INTERACTIEVE FP
5. ↑ INTERACTVE FP - Help
6. ↑ Furry Paws , een FP-compiler
7. ↑ fp-tolk-in-lisp
8. ↑ FP-interpreter, gemaakt in Delphi
9. ↑ PLASM functionele taal voor rekenen met geometrie. Alberto Paoluzzi ( Universiteit van Rome III ), geraadpleegd op 27 november 2010 . 

web links

• Kritiek op het Backus-essay van Edsger W. Dijkstra (PDF; 143 kB)
• John Backus: Programmeren op functieniveau en de FL-taal , 1987 (video)
• Het FL-project: ontwerp van een functionele taal (PDF; 315 kB)
• FL Taalhandleiding, deel 1 en 2 (PDF; 20 MB)
• Inleiding tot FL en PLASM (PDF)
• FP (Engels)
• Scripts naar FP-systemen