Funksjonelt programmeringssystem

Begrepet Functional Programming System (forkortet FP-system ) beskriver et konsept med funksjonelle programmeringsspråk utviklet av John W. Backus . Backus startet med observasjonen at vanlige programmeringsspråk representerer dataprogrammer som en liten seriell datamanipulering, ettersom de er basert på von Neumann-maskinmodellen. Ifølge Backus resulterer dette i to problemer. På den ene siden er det vanskelig å parallellisere von Neumann-programmene. På den annen side at det er vanskelig å argumentere formelt om egenskapene til Von Neumann-programmer eller å transformere dem. Den funksjonell programmering System løser disse problemene ved å lage et program fra en sammensetning . Ved å gjøre dette overføres større mengder strukturerte data fra en funksjon til en annen, som teknisk muliggjør parallell behandling. Backus vurderte også å gjøre denne måten å jobbe til grunnlag for en ny dataarkitektur som utnytter denne muligheten. ${\ displaystyle P}$${\ displaystyle P = F_ {n} \ circ F_ {n-1} \ circ F_ {n-2} \ circ .. \ circ F_ {1}}$

I en tale i anledning overrekkelsen av Turing Awards til Backus i 1977 presenterte sistnevnte ideen om FP-systemer. Tittelen på foredraget var: Kan programmering frigjøres fra von Neumann-stilen? En funksjonell stil og dens algebra av programmer . I et annet essay bestemte Backus seg for å bruke begrepet funksjonsnivåprogrammering .

Funksjonelt program for beregning av skalarproduktet

Med beregningen av skalarproduktet, gir Backus et lærerikt eksempel for anvendelse av Functional Programming System .

Funksjonen ("Inner Product"), som bestemmer skalarproduktet til to vektorer, er sammensatt av sammenkoblet beregning av de tre funksjonene og (i denne rekkefølgen), som uttrykkes som en funksjonssammensetning som følger : ${\ displaystyle IP}$${\ displaystyle Trans, (\ alpha \ times)}$${\ displaystyle (/ +)}$

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

Her er en funksjon som transponerer en matrise . I FP er for eksempel dette forholdet notert som følger for en matrise : ${\ 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}}}$

Symbolene og betegner funksjonalitet . Disse tar på seg andre funksjoner for å skape nye funksjoner. In der Form overtar den tosifrede multiplikasjonsfunksjonen og gir en funksjon som gjelder for alle elementene i en bestått parliste. Resultatet av beregningen er da listen over de enkelte produktene. På moderne programmeringsspråk kalles dette for det meste funksjonelt . Backus kaller dem også . ${\ displaystyle \ alpha}$${\ displaystyle /}$${\ displaystyle (\ alpha \ times)}$${\ displaystyle \ alpha}$${\ displaystyle \ times}$${\ displaystyle \ times}$${\ displaystyle \ alpha}$mapApplyToAll

Funksjonen tilsvarer til slutt omtrent funksjonen eller i vanlig funksjonell programmering. Backus navngir det , noe som betyr at uttrykket representerer en funksjon som setter inn operasjonen mellom to elementer i en gitt liste . Så det gjelder . ${\ displaystyle /}$reducefoldInsert${\ displaystyle (/ +)}$${\ displaystyle +}$${\ displaystyle (/ +) (<2,3,4>) = 2 + 3 + 4 = 9}$

Beregningen av den skalære produktfunksjonen brukes på de to vektorene og kan deretter forstås som følger: ${\ 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 \ ganger): << 1,6>, <2,5>, <3,4 >>) \\ & = (/ +): <\ times: <1,6>, \ times: <2,5>, \ times: <3,4 >> \\ & = (/ +): <6,10,12> \\ & = +: <6, +: <10.12 >> \\ & = 28 \ end {align}}}$

Den aritmetiske prosessen representerer altså en prosesseringsrørledning uten en intern tilstand, som konverterer inngangen til utgangen i tre separate arbeidstrinn. Arbeidstrinnene i seg selv kan parallelliseres i forskjellige grader. Det vil også være mulig å lage en maskinvareledning for programmet . ${\ displaystyle IP}$

Notasjoner i FP-systemet

Backus bruker en notasjon som er løst basert på matematiske konvensjoner og supplerer dette med McCarthys betingede uttrykk og en rekursiv representasjon for WHILE loops. Det er avgjørende at hver enhet representerer en funksjon og derfor er kompatibel med komposisjonsoperatøren . ${\ displaystyle \ circ}$

Tall som velgere

Vektorprogrammeringsspråket APL hadde en avgjørende innflytelse på det Combinator-baserte funksjonelle programmeringssystemet av John Backus, som fungerer uten en lambda-variabelliste ; i stedet brukes velgere (tall) for å velge verdier fra en sekvens.

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

Fast antall kombinatorer / funksjonelle former

Kombinerer ...	... Form
applikasjon	f : x	= f (x)
sammensetning	(f o g): x	= f (g (x))
konstruksjon	[ f 1 , f 2 , ... , f n ]  : x	= < f 1 : x , f 2 : x , ... , f n : x >
tilstand	(p → f ; g): x	= Dersom p: x = T deretter f: x ellers dersom p: x = F deretter g: x ellers ⊥
konstant	~ x: y	= hvis y = ⊥ så ⊥ ellers x
Sett inn	( / f): < x 1 , x 2 , ..., x n >	= f: < x 1 , f: < x 2 , ... f: < x n-1 , x n >>>
Gjelder for alle	( α f): < x 1 , x 2 , ..., x n >	= < f: x 1 , f: x 2 , ..., f: x n >
Binær til unary	bu fx
Mens løkke	( mens pf): x	= Dersom p: x = T deretter ( mens pf) : (f : x) ellers dersom p: x = F da x ellers ⊥

og definisjonen av monadiske funksjoner:

Def Name ≡ Term

Med ⊥ betydde Backus verdien "bunn", en verdi som "udefinert" eller "unntak". T og F er verdiene for "true" og "false".

Videreutvikling av FP-systemer

Et team bestående av John Backus, John Williams og Edward Wimmers utviklet etterfølgeren FL (Function-Level Programming) ved IBM Almaden Research Center i 1989 . Med dette konseptet burde man kunne omorganisere programmer så komfortabelt som man kan omorganisere ligninger i matematikk, referansetransparens måtte garanteres for dette. Dette skal tjene en ny dimensjon av programoptimalisering (EFL). Med FL ønsket Backus å gjøre den ”daværende informatikken” til en ingeniørfag. Igjen er noen videreutviklinger av FL J (applikasjon som APL) og PLaSM, et programmeringsspråk for geometri.

FP-implementeringer

• INTERAKTIV FP, hjelpeside for dette
• FP kompilator som kompilerer seg til C, repo til
• Fp tolk i Lisp
• FP trivia, FP repo til
• Plasm ( P rogramming La nguage for S olid M odeling), et funksjonelt programmeringsspråk for bruk i CAD , som ved Roma Tre University er utviklet.

Se også

• Algebraisk programmeringsspråk

litteratur

• Wolfram-Manfred Lippe : Funksjonell og applikativ programmering: Grunnleggende, språk, implementeringsteknikker . 1. utgave. Springer , Berlin 2009, ISBN 978-3-540-89091-1 ( begrenset forhåndsvisning i Google-boksøk). 
• Alberto Paoluzzi ea: Geometrisk programmering for datamaskinstøttet design . 1. utgave. Wiley , Chichester 2003, ISBN 978-0-471-89942-6 ( begrenset forhåndsvisning i Google Book Search). 

Individuelle bevis

1. ↑ Lippe 2009, s. 73
2. ↑ Kan programmering frigjøres fra von Neumann-stilen? En funksjonell stil og programmets algebra Stanford University, 1978 (PDF; 2,87 MB)
3. ↑ Funksjonsnivåprogrammer som matematiske objekter (PDF)
4. ↑ INTERAKTIV FP
5. ↑ INTERACTVE FP - Hjelp
6. ↑ Furry Paws , en FP-kompilator
7. ↑ fp-tolk-i-lisp
8. ↑ FP-tolk, opprettet i Delphi
9. ↑ PLaSM funksjonelt språk for databehandling med geometri. Alberto Paoluzzi ( University of Rome III ), åpnet 27. november 2010 . 

weblenker

• Kritikk av Backus-essayet av Edsger W. Dijkstra (PDF; 143 kB)
• John Backus: Funksjonsnivåprogrammering og FL-språket , 1987 (video)
• FL-prosjektet: Design of a Functional Language (PDF; 315 kB)
• FL språkhåndbok, del 1 og 2 (PDF; 20 MB)
• Introduksjon til FL og PLaSM (PDF)
• FP (engelsk)
• Skript til FP-systemer