Eksempel på funksjonell programmering. Ulemper med funksjonell programmering

Språk som ligner på funksjonelle bruker et mindre strengt konsept. En funksjon i matematikk kan ikke endre miljøet som kaller den og huske resultatene av sitt arbeid, men gir kun resultatet av funksjonens beregning. Programmering ved hjelp av matematisk konsept funksjoner forårsaker noen vanskeligheter, derfor gir funksjonelle språk, i en eller annen grad, også imperative evner, noe som forverrer utformingen av programmet (for eksempel muligheten for smertefrie ytterligere endringer). En ytterligere forskjell fra imperative programmeringsspråk er den deklarative karakteren til funksjonsbeskrivelser. Tekster til programmer på funksjonelle programmeringsspråk beskrive"hvordan løse et problem", men ikke ordinere rekkefølge av handlinger for løsning. Det første funksjonelle språket designet var Lisp. En variant av dette språket er mye brukt i systemet datastyrt design AutoLISP

Følgende regnes vanligvis som hovedegenskapene til funksjonelle programmeringsspråk:

korthet og enkelhet;
sterk skriving;
modularitet;
funksjoner er beregningsobjekter;
utsatte (late) beregninger.

Noen funksjonelle programmeringsspråk

Miranda (hvilken familie?)

Linker

http://roman-dushkin.narod.ru/fp.html - Et kurs med forelesninger om funksjonell programmering, gitt ved MEPhI siden 2001.

Wikimedia Foundation. 2010.

Se hva "Funksjonelt programmeringsspråk" er i andre ordbøker:

Et programmeringsspråk som lar deg spesifisere et program som et sett med funksjonsdefinisjoner. I funksjonelle programmeringsspråk: funksjoner utveksler data med hverandre uten å bruke mellomliggende variabler og tilordninger;... ... Finansiell ordbok

funksjonelt språk- Et programmeringsspråk der handlinger på data uttrykkes som oppfordringer til funksjonelle prosedyrer. [GOST 19781 90] Støtteobjekter. prosesseringssystemer informasjon programvare EN funksjonelt språk... Teknisk oversetterveiledning

Ruby Semantics: multi-paradigme Utførelsestype: tolk Dukket opp i: 1995 Forfatter(e): Yukihiro Matsumoto Siste versjon: 1.9.1 ... Wikipedia

Funksjonelt språk- 37. Funksjonsspråk Funksjonsspråk Et programmeringsspråk der handlinger på data uttrykkes i form av kall til funksjonelle prosedyrer Kilde: GOST 19781 90: Programvarestøtte for informasjonsbehandlingssystemer. Vilkår og ... ... Ordbok-referansebok med vilkår for normativ og teknisk dokumentasjon

Erlang Fil:Erlang logo.png Semantikk: multi-paradigme: konkurransedyktig, funksjonell programmering Dukket opp i: 1987 Forfatter(e): Datatyping: streng, dynamisk Hovedimplementeringer: E ... Wikipedia

Scheme Semantics: functional Utførelsestype: tolk eller kompilator Vist i: 1970 Forfatter(e): Guy Steele og Gerald Sussman Datatyping ... Wikipedia

Dette begrepet har andre betydninger, se Miranda . Miranda er et funksjonelt programmeringsspråk opprettet i 1985 av David Turner som et standard funksjonelt språk. Den har et strengt polymorf type system, ... ... Wikipedia

Hope er et funksjonelt programmeringsspråk utviklet på begynnelsen av 1980-tallet; er forgjengeren til Miranda- og Haskell-språkene. Byte magazine, august 1985, publiserte først en guide til Hope-språket. Et eksempel på et regneprogram... ... Wikipedia

Dette begrepet har andre betydninger, se SASL. SASL er et fullt funksjonelt programmeringsspråk utviklet av David Turner ved University of St Andrews i 1972, basert på den applikative undergruppen av ISWIM. I 1976... ... Wikipedia

Dette begrepet har andre betydninger, se Scala . Scala Språkklasse: Multiparadigme: funk... Wikipedia

Bøker

Programmering i Clojure. Praksisen med å bruke Lisp i Java-verdenen, Emerick Ch., Carper B., Grand K.. Hvorfor velger mange Clojure? Det er et funksjonelt programmeringsspråk som ikke bare lar deg bruke Java-biblioteker, tjenester og andre JVM-ressurser, men som også konkurrerer med...

String reverse(String arg) ( if(arg.length == 0) ( return arg; ) else ( return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1); ) )
Denne funksjonen er ganske treg fordi den kaller seg selv gjentatte ganger. Det kan være en minnelekkasje her fordi midlertidige objekter opprettes mange ganger. Men dette er en funksjonell stil. Du synes kanskje det er rart hvordan folk kan programmere slikt. Vel, jeg skulle akkurat til å fortelle deg det.

Fordeler med funksjonell programmering

Du tenker nok at jeg ikke kan lage en sak for å rettferdiggjøre det monstrøse innslaget ovenfor. Da jeg først begynte å lære funksjonell programmering, trodde jeg det også. Jeg tok feil. Det er veldig gode argumenter for denne stilen. Noen av dem er subjektive. For eksempel hevder programmerere det funksjonelle programmer lettere å forstå. Jeg vil ikke komme med slike argumenter, for alle vet at letthet å forstå er en veldig subjektiv ting. Heldigvis for meg er det fortsatt mange objektive argumenter.

Enhetstesting

Siden hvert symbol i FP er uforanderlig, har funksjoner ingen bivirkninger. Du kan ikke endre verdiene til variabler, og en funksjon kan ikke endre en verdi utenfor dens omfang og dermed påvirke andre funksjoner (som kan skje med klassefelt eller globale variabler). Dette betyr at det eneste resultatet av funksjonens utførelse er returverdien. Og det eneste som kan påvirke returverdien er argumentene som sendes til funksjonen.

Her er den, den blå drømmen til enhetstestere. Du kan teste hver funksjon i et program med bare de nødvendige argumentene. Det er ikke nødvendig å kalle opp funksjoner i riktig rekkefølge eller gjenskape den riktige eksterne tilstanden. Alt du trenger å gjøre er å sende argumenter som matcher kantsakene. Hvis alle funksjonene i programmet består enhetstester, kan du være mye mer trygg på kvaliteten på programvaren din enn når det gjelder viktige programmeringsspråk. I Java eller C++ er det ikke nok å sjekke returverdien - funksjonen kan endre den eksterne tilstanden, som også er underlagt kontroll. Det er ikke noe slikt problem i FP.

Feilsøking

Hvis et funksjonelt program ikke oppfører seg som du forventer, så er feilsøking en bit av kaken. Du kan alltid reprodusere problemet fordi feilen i funksjonen ikke er avhengig av ekstern kode som tidligere ble utført. I et imperativt program vises feilen bare for en stund. Du må gå gjennom en rekke ikke-bug-trinn på grunn av det faktum at funksjonens drift avhenger av den eksterne tilstanden og bivirkninger av andre funksjoner. I FP er situasjonen mye enklere - hvis returverdien er feil, vil den alltid være feil, uansett hvilke kodebiter som ble utført før.

Når du har reprodusert feilen, er det en triviell oppgave å finne kilden. Det er til og med hyggelig. Så snart du stopper programmet, vil du ha hele anropsstabelen foran deg. Du kan se argumentene til hvert funksjonskall, akkurat som i et imperativt språk. Med den forskjellen at i et imperativt program er dette ikke nok, fordi funksjoner avhenger av verdiene til felt, globale variabler og tilstander til andre klasser. En funksjon i FP avhenger kun av dens argumenter, og denne informasjonen er rett foran øynene dine! Enda mer, i et imperativt program er det ikke nok å sjekke returverdien for å fortelle om et stykke kode oppfører seg riktig. Du må jakte på dusinvis av objekter utenfor funksjonen for å sikre at alt fungerer som det skal. I funksjonell programmering er det bare å se på returverdien!

Når du går gjennom stabelen, legger du merke til argumentene som sendes og returverdiene. Når returverdien avviker fra normen, borer du deg inn i funksjonen og går videre. Dette gjentas flere ganger til du finner kilden til feilen!

Multithreading

Funksjonsprogrammet er umiddelbart klart for parallellisering uten endringer. Du trenger ikke å bekymre deg for vranglås eller løpsforhold fordi du ikke trenger låser! Ikke et enkelt stykke data i et funksjonelt program endres to ganger av samme tråd eller av forskjellige. Dette betyr at du enkelt kan legge til tråder i programmet uten å måtte bekymre deg for problemene som ligger i imperative språk.

Hvis dette er tilfelle, hvorfor brukes funksjonelle programmeringsspråk så sjelden i flertrådede applikasjoner? Faktisk oftere enn du tror. Ericsson Company utviklet et funksjonelt språk kalt Erlang for bruk på feiltolerante og skalerbare telekommunikasjonssvitsjer. Mange la merke til fordelene med Erlang og begynte å bruke den. Vi snakker om telekommunikasjons- og trafikkkontrollsystemer, som ikke er på langt nær så lett skalerbare som typiske systemer utviklet på Wall Street. Faktisk er systemer skrevet i Erlang ikke så skalerbare og pålitelige som Java-systemer. Erlang-systemer er rett og slett superpålitelige.

Historien om multithreading slutter ikke der. Hvis du skriver en i hovedsak en-tråds applikasjon, kan kompilatoren fortsatt optimalisere funksjonsprogrammet for å bruke flere CPUer. La oss se på neste kodebit.

En funksjonell språkkompilator kan analysere koden, klassifisere funksjonene som produserer linjene s1 og s2 som tidkrevende funksjoner, og kjøre dem parallelt. Dette er umulig å gjøre på et imperativt språk, fordi hver funksjon kan endre ekstern tilstand og koden umiddelbart etter samtalen kan avhenge av den. I FP er automatisk analyse av funksjoner og søk etter egnede kandidater for parallellisering en triviell oppgave, som automatisk inline! Slik sett er den funksjonelle programmeringsstilen fremtidssikker. Maskinvareutviklere kan ikke lenger få CPU-en til å fungere raskere. I stedet øker de antallet kjerner og krever en firedobling i multi-threaded databehandlingshastighet. Selvfølgelig glemmer de å si i god tid at din ny prosessor vil vise en økning kun i programmer utviklet under hensyntagen til parallellisering. Det er svært få av disse blant imperativ programvare. Men 100 % av funksjonelle programmer er klare for multithreading ut av esken.

Hot Deployment

I gamle dager måtte du starte datamaskinen på nytt for å installere Windows-oppdateringer. Mange ganger. Etter å ha installert en ny versjon av mediespilleren. Det har vært betydelige endringer i Windows XP, men situasjonen er fortsatt langt fra ideell (i dag lanserte jeg Windows-oppdatering på jobb, og nå vil ikke den irriterende påminnelsen la meg være i fred før jeg starter på nytt). Unix-systemer hadde en bedre oppdateringsmodell. For å installere oppdateringer, måtte jeg stoppe noen komponenter, men ikke hele operativsystemet. Selv om situasjonen ser bedre ut, er den fortsatt ikke akseptabel for en stor klasse serverapplikasjoner. Telekommunikasjonssystemer må være slått på 100 % av tiden, for hvis en oppdatering hindrer en person i å ringe en ambulanse, kan liv gå tapt. Wall Street-firmaer ønsker heller ikke å stenge servere over helgen for å installere oppdateringer.

Ideelt sett må du oppdatere alle nødvendige deler av koden uten å stoppe systemet i prinsippet. I den imperative verden er dette umulig [overs. i Smalltalk er det veldig mulig]. Tenk deg at du laster ut en Java-klasse i farten og laster inn en ny versjon på nytt. Hvis vi gjorde dette, ville alle forekomster av klassen bli ikke-fungerende, fordi tilstanden de lagret ville gå tapt. Vi må skrive vanskelig kode for versjonskontroll. Vi må serialisere alle opprettede forekomster av klassen, deretter ødelegge dem, lage forekomster av en ny klasse, prøve å laste inn de serialiserte dataene i håp om at migreringen vil gå problemfritt og de nye forekomstene vil være gyldige. Dessuten må migreringskoden skrives manuelt hver gang. Og migreringskoden må bevare koblinger mellom objekter. I teorien er det greit, men i praksis vil det aldri fungere.

I et funksjonelt program lagres all tilstand på stabelen som funksjonsargumenter. Dette gjør hot deployment mye enklere! I hovedsak er alt du trenger å gjøre å beregne forskjellen mellom koden på produksjonsserveren og den nye versjonen, og installere endringene i koden. Resten vil bli gjort automatisk av språkverktøyene! Hvis du tror dette er science fiction, tenk deg om to ganger. Ingeniører som jobber med Erlang har oppdatert systemene sine i årevis uten å stoppe arbeidet.

Maskinassisterte prøvetrykk og optimaliseringer

En annen interessant egenskap ved funksjonelle programmeringsspråk er at de kan læres fra et matematisk synspunkt. Siden et funksjonelt språk er en implementering av et formelt system, kan alle matematiske operasjoner brukt på papir brukes på funksjonelle programmer. Kompilatoren kan for eksempel konvertere et stykke kode til et ekvivalent, men mer effektivt stykke, mens den matematisk rettferdiggjør deres ekvivalens. Relasjonelle databaser data har gjennomgått slike optimaliseringer i årevis. Det er ingenting som hindrer deg i å bruke lignende teknikker i vanlige programmer.

I tillegg kan du bruke matematikk for å bevise riktigheten av deler av programmene dine. Hvis du vil, kan du skrive verktøy som analyserer koden din og automatisk lager Unit-tester for kantsaker! Denne funksjonaliteten er uvurderlig for bunnsolide systemer. Ved utvikling av pacemakerovervåking eller lufttrafikkstyringssystemer er slike verktøy et must. Hvis utviklingen din ikke er i det kritiske området viktige applikasjoner, deretter verktøyene automatisk sjekk vil fortsatt gi deg en gigantisk fordel i forhold til konkurrentene dine.

Funksjoner av høyere orden

Husk, da jeg snakket om fordelene med FP, la jeg merke til at "alt ser bra ut, men det er nytteløst hvis jeg må skrive på et klønete språk der alt er endelig." Dette var en misforståelse. Bruken av final overalt ser bare klønete ut i imperative programmeringsspråk som Java. Funksjonelle programmeringsspråk fungerer med andre typer abstraksjoner, de som får deg til å glemme at du noen gang har likt å endre variabler. Et slikt verktøy er høyere ordensfunksjoner.

I FP er ikke en funksjon det samme som en funksjon i Java eller C. Det er et supersett - de kan gjøre det samme som Java-funksjoner og enda mer. La oss si at vi har en funksjon i C:

Int add(int i, int j) ( return i + j; )
I FP er ikke dette det samme som en vanlig C-funksjon. La oss utvide vår Java-kompilator for å støtte denne notasjonen. Kompilatoren må gjøre funksjonserklæringen om til følgende Java-kode (husk at det er en implisitt final overalt):

Klasse add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Add-symbolet er egentlig ikke en funksjon. Dette er en liten klasse med én metode. Nå kan vi sende add som et argument til andre funksjoner. Vi kan skrive det inn i et annet symbol. Vi kan lage forekomster av add_function_t under kjøring, og de vil bli ødelagt av søppelsamleren hvis de ikke lenger er nødvendige. Funksjoner blir grunnleggende gjenstander, som tall og strenger. Funksjoner som opererer på funksjoner (ta dem som argumenter) kalles høyere-ordens funksjoner. Ikke la dette skremme deg. Konseptet med funksjoner av høyere orden er nesten det samme som konseptet med Java-klasser som opererer på hverandre (vi kan sende klasser til andre klasser). Vi kan kalle dem "klasser av høyere orden", men ingen bryr seg med det fordi Java ikke har et strengt akademisk fellesskap bak seg.

Hvordan og når bør du bruke høyere ordensfunksjoner? Jeg er glad du spurte. Du skriver programmet ditt som ett stort monolittisk stykke kode uten å bekymre deg for klassehierarki. Hvis du ser at en kodebit gjentas forskjellige steder, flytter du den inn i en egen funksjon (heldigvis lærer skolene fortsatt hvordan dette skal gjøres). Hvis du legger merke til at noe av logikken i funksjonen din burde oppføre seg annerledes i noen situasjoner, så lager du en funksjon av høyere orden. Forvirret? Her er et ekte eksempel fra arbeidet mitt.

La oss anta at vi har et stykke Java-kode som mottar en melding, transformerer den på forskjellige måter og overfører den til en annen server.

Void handleMessage(Message msg) ( // ... msg.setClientCode("ABCD_123"); // ... sendMessage(msg); ) // ... )
Tenk deg nå at systemet har endret seg, og nå må du distribuere meldinger mellom to servere i stedet for én. Alt forblir uendret bortsett fra klientkoden - den andre serveren ønsker å motta denne koden i et annet format. Hvordan kan vi håndtere denne situasjonen? Vi kan sjekke hvor meldingen skal gå og sette riktig klientkode basert på det. For eksempel slik:

Class MessageHandler ( void handleMessage(Message msg) ( // ... if(msg.getDestination().equals("server1") ( msg.setClientCode("ABCD_123"); ) else ( msg.setClientCode("123_ABC") ; ) // ... sendMessage(msg); ) // ... )
Men denne tilnærmingen skalerer ikke godt. Etter hvert som nye servere legges til, vil funksjonen vokse lineært og å gjøre endringer vil bli et mareritt. Den objektorienterte tilnærmingen består av å isolere en felles superklasse MessageHandler og underklassere logikken for å definere klientkoden:

Abstrakt klasse MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) abstract String getClientCode(); // ... ) class MessageHandlerOne utvider MessageHandler ( String getClientCode() ( returner "ABCD_123"; ) ) klassen MessageHandlerTwo utvider MessageHandler ( String getClientCode() ( returnerer "123_ABCD"; ) )
Nå for hver server kan vi lage en forekomst av den tilsvarende klassen. Det blir mer praktisk å legge til nye servere. Men for dette liten forandring for mye tekst. Jeg måtte lage to nye typer bare for å legge til støtte for annen klientkode! La oss nå gjøre det samme på språket vårt med støtte for funksjoner av høyere orden:

Class MessageHandler ( void handleMessage(Message msg, Function getClientCode) ( // ... Message msg1 = msg.setClientCode(getClientCode()); // ... sendMessage(msg1); ) // ... ) String getClientCodeOne( ) ( return "ABCD_123"; ) String getClientCodeTwo() ( return "123_ABCD"; ) MessageHandler handler = new MessageHandler(); handler.handleMessage(someMsg, getClientCodeOne);
Vi har ikke laget nye typer eller komplisert klassehierarkiet. Vi passerte rett og slett funksjonen som en parameter. Vi oppnådde samme effekt som i den objektorienterte motparten, men med noen fordeler. Vi har ikke bundet oss til noe klassehierarki: vi kan overføre alle andre funksjoner til runtime og endre dem når som helst, samtidig som vi opprettholder et høyt nivå av modularitet med mindre kode. I hovedsak skapte kompilatoren objektorientert lim for oss! Samtidig er alle andre fordeler med FP bevart. Abstraksjonene som tilbys av funksjonelle språk slutter selvfølgelig ikke der. Funksjoner av høyere orden er bare begynnelsen

Currying

De fleste jeg møter har lest boken Design Patterns by the Gang of Four. Enhver programmerer med respekt for seg selv vil si at boken ikke er knyttet til noe spesifikt programmeringsspråk, og mønstrene gjelder for programvareutvikling generelt. Dette er en edel uttalelse. Men det er dessverre langt fra sannheten.

Funksjonelle språk er utrolig uttrykksfulle. I et funksjonelt språk trenger du ikke designmønstre fordi språket er så høyt nivå at du enkelt kan begynne å programmere i konsepter som eliminerer alle kjente programmeringsmønstre. Et av disse mønstrene er adapteren (hvordan er den forskjellig fra fasaden? Det ser ut til at noen trengte å stemple flere sider for å oppfylle vilkårene i kontrakten). Dette mønsteret viser seg å være unødvendig hvis språket støtter karri.

Adaptermønsteret brukes oftest på "standard" abstraksjonsenheten i Java - klassen. I funksjonelle språk brukes mønsteret på funksjoner. Mønsteret tar et grensesnitt og transformerer det til et annet grensesnitt i henhold til visse krav. Her er et eksempel på adaptermønsteret:

Int pow(int i, int j); int square(int i) ( return pow(i, 2); )
Denne koden tilpasser grensesnittet til en funksjon som hever et tall til en vilkårlig potens til grensesnittet til en funksjon som kvadrerer et tall. I akademiske kretser kalles denne enkle teknikken currying (etter logikeren Haskell Curry, som utførte en rekke matematiske triks for å formalisere det hele). Siden funksjoner brukes overalt som argumenter i FP, brukes currying veldig ofte for å bringe funksjoner til grensesnittet som trengs på ett eller annet sted. Siden grensesnittet til en funksjon er dens argumenter, brukes currying for å redusere antall argumenter (som i eksemplet ovenfor).

Dette verktøyet er innebygd i funksjonelle språk. Du trenger ikke manuelt å lage en funksjon som omslutter originalen. Et funksjonelt språk vil gjøre alt for deg. Som vanlig, la oss utvide språket vårt ved å legge til currying.

Square = int pow(int i, 2);
Med denne linjen lager vi automatisk en kvadreringsfunksjon med ett argument. Den nye funksjonen kaller pow-funksjonen, og erstatter 2 som det andre argumentet. Fra et Java-perspektiv vil det se slik ut:

Klasse square_function_t ( int square(int i) ( return pow(i, 2); ) ) square_function_t square = new square_function_t();
Som du kan se, skrev vi ganske enkelt en omslag over den opprinnelige funksjonen. I FP er karry bare en enkel og praktisk måte å lage innpakninger på. Du fokuserer på oppgaven, og kompilatoren skriver den nødvendige koden for deg! Det er veldig enkelt, og skjer hver gang du vil bruke Adapter (innpaknings)-mønsteret.

Lat evaluering

Lat (eller utsatt) evaluering er en interessant teknikk som blir mulig når du forstår den funksjonelle filosofien. Vi har allerede sett følgende kodebit når vi snakker om multithreading:

String s1 = somewhatLongOperation1(); String s2 = somewhatLongOperation2(); String s3 = concatenate(s1, s2);
I imperative programmeringsspråk reiser ikke rekkefølgen av beregningen noen spørsmål. Siden hver funksjon kan påvirke eller avhenge av ekstern tilstand, er det nødvendig å opprettholde en klar rekkefølge av anrop: først somewhatLongOperation1 , så somewhatLongOperation2 , og sammenknytt på slutten. Men ikke alt er så enkelt i funksjonelle språk.

Som vi så tidligere, kan somewhatLongOperation1 og somewhatLongOperation2 kjøres samtidig fordi funksjonene garantert ikke påvirker eller avhenger av den globale tilstanden. Men hva om vi ikke ønsker å utføre dem samtidig, bør vi kalle dem sekvensielt? Svaret er nei. Disse beregningene skal bare kjøres hvis noen annen funksjon er avhengig av s1 og s2. Vi trenger ikke engang å henrette dem før vi trenger dem inne i sammenkoblingen. Hvis vi i stedet for å sette sammen erstatter en funksjon som, avhengig av betingelsen, bruker ett av de to argumentene, kan det hende at det andre argumentet ikke engang beregnes! Haskell er et eksempel på et lat evalueringsspråk. Haskell garanterer ingen anropsordre (i det hele tatt!) fordi Haskell utfører kode etter behov.

Lazy computing har en rekke fordeler i tillegg til noen ulemper. I neste avsnitt skal vi diskutere fordelene og jeg vil forklare hvordan man kan leve med ulempene.

Optimalisering

Lat evaluering gir et enormt potensial for optimaliseringer. En lat kompilator ser på kode på samme måte som en matematiker ser på algebraiske uttrykk - den kan angre ting, kansellere utførelse av visse deler av koden, endre rekkefølgen på kall for større effektivitet, til og med arrangere kode på en slik måte at antallet reduseres av feil, samtidig som integriteten til programmet sikres. Dette er den største fordelen med å beskrive et program med strenge formelle primitiver - koden adlyder matematiske lover og kan studeres matematiske metoder.

Abstrahere kontrollstrukturer

Lazy databehandling gir et så høyt abstraksjonsnivå at fantastiske ting blir mulig. Tenk deg for eksempel å implementere følgende kontrollstruktur:

Med mindre(stock.isEuropean()) ( sendToSEC(lager); )
Vi ønsker at sendToSEC-funksjonen kun skal utføres hvis aksjen ikke er europeisk. Hvordan kan du implementere med mindre? Uten lat evaluering ville vi trenge et makrosystem, men på språk som Haskell er ikke dette nødvendig. Vi kan erklære med mindre som en funksjon!

Ugyldig med mindre(boolsk tilstand, listekode) ( if(!tilstand) kode; )
Merk at koden ikke vil bli utført hvis betingelse == sant. På strenge språk kan ikke denne oppførselen gjentas fordi argumentene vil bli evaluert før med mindre den kalles.

Uendelige datastrukturer

Late språk lar deg lage uendelige datastrukturer, som er mye vanskeligere å lage på strenge språk. - bare ikke i Python]. Tenk deg for eksempel Fibonacci-sekvensen. Det er klart at vi ikke kan beregne en uendelig liste på en begrenset tid og fortsatt lagre den i minnet. På strenge språk som Java ville vi ganske enkelt skrive en funksjon som returnerer et vilkårlig medlem av sekvensen. På språk som Haskell kan vi abstrahere bort og ganske enkelt erklære en uendelig liste over Fibonacci-tall. Siden språket er lat, vil kun de nødvendige delene av listen som faktisk brukes i programmet beregnes. Dette lar deg abstrahere fra stort nummer problemer og se på dem med mer høy level(du kan for eksempel bruke listebehandlingsfunksjoner på uendelige sekvenser).

Feil

Sikkert gratis ost skjer kun i en musefelle. Late beregninger har en rekke ulemper. Dette er hovedsakelig mangler fra latskap. I virkeligheten er direkte rekkefølge av beregninger svært ofte nødvendig. Ta for eksempel følgende kode:

På et lat språk er det ingen som garanterer at den første linjen vil bli utført før den andre! Dette betyr at vi ikke kan gjøre I/O, vi kan ikke bruke native funksjoner normalt (de må tross alt kalles i en bestemt rekkefølge for å gjøre rede for bivirkninger), og vi kan ikke samhandle med utsiden verden! Hvis vi introduserer en mekanisme for å bestille utførelse av kode, vil vi miste fordelen med matematisk strenghet til koden (og da vil vi miste alle fordelene med funksjonell programmering). Heldigvis er ikke alt tapt. Matematikere begynte å jobbe og kom opp med flere teknikker for å sikre at instruksjonene ble utført i riktig rekkefølge uten å miste funksjonsånden. Vi har det beste fra to verdener! Slike teknikker inkluderer fortsettelser, monader og unikhetsskriving. I denne artikkelen skal vi jobbe med fortsettelser, og la monader og entydig skriving ligge til neste gang. Det er interessant at fortsettelser er en veldig nyttig ting som ikke bare brukes til oppgaver streng rekkefølge beregninger. Vi skal snakke om dette også.

Oppfølgere

Fortsettelser i programmering spiller samme rolle som Da Vinci-koden i menneskets historie: en overraskende avsløring av menneskehetens største mysterium. Vel, kanskje ikke akkurat slik, men de river definitivt av dekslene, akkurat som du lærte å ta roten til -1 tilbake i dag.

Når vi så på funksjoner, lærte vi bare halve sannheten, fordi vi antok at en funksjon returnerer en verdi til funksjonen som kaller den. I denne forstand er fortsettelse en generalisering av funksjoner. En funksjon trenger ikke å returnere kontrollen til stedet den ble kalt fra, men kan returnere til et hvilket som helst sted i programmet. "Fortsett" er en parameter vi kan sende til en funksjon for å indikere et returpunkt. Det høres mye skumlere ut enn det faktisk er. La oss ta en titt på følgende kode:

Int i = add(5, 10); int j = kvadrat(i);
Add-funksjonen returnerer tallet 15, som skrives til i på stedet der funksjonen ble kalt. Verdien av i brukes da når du kaller kvadrat. Merk at en lat kompilator ikke kan endre rekkefølgen på beregningene, fordi den andre linjen avhenger av resultatet av den første. Vi kan skrive om denne koden ved å bruke en Continuation Passing Style (CPS), hvor add returnerer en verdi til kvadratfunksjonen.

Int j = add(5, 10, kvadrat);
I dette tilfellet mottar add et ekstra argument - en funksjon som kalles opp etter at add er ferdig. I begge eksemplene vil j være lik 225.

Dette er den første teknikken som lar deg spesifisere rekkefølgen som to uttrykk utføres i. La oss gå tilbake til vårt I/O-eksempel.

System.out.println("Vennligst skriv inn navnet ditt: "); System.in.readLine();
Disse to linjene er uavhengige av hverandre, og kompilatoren står fritt til å endre rekkefølgen som den vil. Men hvis vi omskriver det i CPS, vil vi dermed legge til den nødvendige avhengigheten, og kompilatoren må utføre beregninger etter hverandre!

System.out.println("Vennligst skriv inn navnet ditt: ", System.in.readLine);
I dette tilfellet vil println måtte kalle readLine , gi den resultatet, og returnere resultatet av readLine på slutten. I dette skjemaet kan vi være sikre på at disse funksjonene blir kalt etter tur, og at readLine i det hele tatt vil bli kalt (kompilatoren forventer tross alt å motta resultatet av den siste operasjonen). I tilfelle av Java, returnerer println void. Men hvis en abstrakt verdi (som kan tjene som argument for readLine) ble returnert, ville det løse problemet vårt! Å bygge slike funksjonskjeder forringer selvsagt lesbarheten til koden, men dette kan håndteres. Vi kan legge til syntaktiske funksjoner i språket vårt som lar oss skrive uttrykk som vanlig, og kompilatoren vil automatisk kjede beregninger. Nå kan vi utføre beregninger i hvilken som helst rekkefølge uten å miste fordelene med FP (inkludert muligheten til å studere programmet ved hjelp av matematiske metoder)! Hvis dette er forvirrende, husk at funksjoner bare er forekomster av en klasse med et enkelt medlem. Omskriv eksemplet vårt slik at println og readLine er forekomster av klasser, dette vil gjøre det tydeligere for deg.

Men fordelene med oppfølgere slutter ikke der. Vi kan skrive hele programmet ved hjelp av CPS, slik at hver funksjon kalles med tilleggsparameter, en fortsettelse som resultatet overføres til. I prinsippet kan ethvert program oversettes til CPS hvis hver funksjon behandles som et spesielt tilfelle av fortsettelser. Denne konverteringen kan gjøres automatisk (faktisk gjør mange kompilatorer det).

Så snart vi konverterer programmet til CPS-form, blir det klart at hver instruksjon har en fortsettelse, en funksjon som resultatet vil bli sendt til, som i et normalt program vil være call point. La oss ta en hvilken som helst instruksjon fra det siste eksemplet, for eksempel add(5,10) . I et program skrevet i CPS-form er det klart hva som vil være fortsettelsen - dette er funksjonen som legger til vil kalle ved ferdigstillelse av arbeidet. Men hva blir fortsettelsen i tilfelle et ikke-CPS-program? Vi kan selvfølgelig konvertere programmet til CPS, men er dette nødvendig?

Det viser seg at dette ikke er nødvendig. Ta en nærmere titt på vår CPS-konvertering. Hvis du begynner å skrive en kompilator for den, vil du oppdage at CPS-versjonen ikke trenger en stack! Funksjoner returnerer aldri noe, i den tradisjonelle betydningen av ordet "retur", kaller de ganske enkelt en annen funksjon, og erstatter resultatet av beregningen. Det er ikke nødvendig å skyve argumenter på stabelen før hver samtale og deretter sette dem tilbake. Vi kan ganske enkelt lagre argumentene på et fast minnested og bruke hopp i stedet for en vanlig samtale. Vi trenger ikke å lagre de originale argumentene, fordi de aldri vil være nødvendige igjen, fordi funksjoner ikke returnerer noe!

Dermed trenger ikke programmer i CPS-stil en stabel, men inneholder et tilleggsargument, i form av en funksjon, som skal kalles. Ikke-CPS stil programmer har ikke et ekstra argument, men bruker en stack. Hva er lagret på stabelen? Bare argumenter og en peker til minnestedet hvor funksjonen skal returnere. Vel, har du allerede gjettet? Stabelen lagrer informasjon om fortsettelser! En peker til et returpunkt på stabelen er den samme som funksjonen som skal kalles i CPS-programmer! For å finne ut hva fortsettelsen av add(5,10) er, ta bare returpunktet fra stabelen.

Det var ikke vanskelig. En fortsettelse og en peker til et returpunkt er egentlig det samme, bare fortsettelsen er spesifisert eksplisitt, og derfor kan den avvike fra stedet der funksjonen ble kalt. Hvis du husker at en fortsettelse er en funksjon, og en funksjon i vårt språk er kompilert til en forekomst av en klasse, så vil du forstå at en peker til et returpunkt på stabelen og en peker til en fortsettelse faktisk er det samme , fordi funksjonen vår (som en forekomst av en klasse ) bare er en peker. Dette betyr at du når som helst i programmet ditt kan be om gjeldende fortsettelse (i hovedsak informasjon fra stabelen).

Ok, nå forstår vi hva den nåværende fortsettelsen er. Hva betyr det? Hvis vi tar den nåværende fortsettelsen og lagrer den et sted, vil vi dermed spare Nåværende situasjon program - la oss fryse det. Dette ligner på OS-dvalemodus. Fortsettelsesobjektet lagrer informasjonen som trengs for å gjenoppta programkjøringen fra punktet der fortsettelsesobjektet ble forespurt. operativsystem gjør dette med programmene dine hele tiden når den bytter kontekst mellom tråder. Den eneste forskjellen er at alt er under kontroll av OS. Hvis du ber om et fortsettelsesobjekt (i Scheme gjøres dette ved å kalle oppkall-med-aktuell-fortsettelse-funksjonen), vil du motta et objekt med gjeldende fortsettelse - stabelen (eller i tilfelle av CPS, den neste anropsfunksjonen ). Du kan lagre dette objektet til en variabel (eller til og med på disk). Hvis du bestemmer deg for å "starte" programmet på nytt med denne fortsettelsen, blir tilstanden til programmet ditt "transformert" til tilstanden da fortsettelsesobjektet ble tatt. Dette er det samme som å bytte til en suspendert tråd, eller å vekke operativsystemet etter dvalemodus. Med unntak av at du kan gjøre dette mange ganger på rad. Etter at operativsystemet våkner, blir dvaleinformasjonen ødelagt. Hvis dette ikke ble gjort, ville det være mulig å gjenopprette OS-tilstanden fra samme punkt. Det er nesten som å reise gjennom tiden. Med oppfølgere har du råd til det!

I hvilke situasjoner vil fortsettelse være nyttig? Vanligvis hvis du prøver å etterligne tilstand i systemer som iboende er blottet for tilstand. En utmerket bruk for fortsettelser er funnet i webapplikasjoner (for eksempel i Seaside-rammeverket for Smalltalk-språket). Microsofts ASP.NET strekker seg langt for å lagre staten mellom forespørsler for å gjøre livet ditt enklere. Hvis C# støttet fortsettelser, kan kompleksiteten til ASP.NET halveres ved ganske enkelt å lagre fortsettelsen og gjenopprette den ved neste forespørsel. Fra en webprogrammerers synspunkt ville det ikke være en eneste pause - programmet ville fortsette arbeidet fra neste linje! Fortsettelser er en utrolig nyttig abstraksjon for å løse noen problemer. Med flere og flere tradisjonelle fete klienter som flytter til nettet, vil viktigheten av fortsettelser bare vokse over tid.

Mønstermatching

Mønstertilpasning er ikke en så ny eller innovativ idé. Faktisk har det lite med funksjonell programmering å gjøre. Den eneste grunnen til at det ofte forbindes med FP, er at funksjonelle språk i noen tid har mønstertilpasning, men imperative språk har ikke det.

La oss starte vår introduksjon til mønstertilpasning med følgende eksempel. Her er en funksjon for å beregne Fibonacci-tall i Java:

Int fib(int n) ( if(n == 0) return 1; if(n == 1) return 1; return fib(n - 2) + fib(n - 1); )
Og her er et eksempel på et Java-lignende språk med støtte for mønstertilpasning

Int fib(0) ( return 1; ) int fib(1) ( return 1; ) int fib(int n) ( return fib(n - 2) + fib(n - 1); )
Hva er forskjellen? Kompilatoren implementerer forgreningen for oss.

Bare tenk, det er veldig viktig! Det er egentlig ikke så viktig. Det ble lagt merke til at et stort antall funksjoner inneholder komplekse bryterstrukturer (dette er delvis sant for funksjonelle programmer), og det ble besluttet å markere dette punktet. Funksjonsdefinisjonen er delt opp i flere varianter, og et mønster etableres i stedet for funksjonsargumentene (dette minner om metodeoverbelastning). Når et funksjonskall oppstår, sammenligner kompilatoren argumentene med alle definisjoner på et øyeblikk og velger den mest passende. Vanligvis faller valget på den mest spesialiserte funksjonsdefinisjonen. For eksempel kan int fib(int n) kalles når n er 1, men det vil den ikke, fordi int fib(1) er en mer spesialisert definisjon.

Mønstertilpasning ser vanligvis mer komplisert ut enn i vårt eksempel. For eksempel lar et komplekst mønstertilpasningssystem deg skrive følgende kode:

Int f(int n< 10) { ... } int f(int n) { ... }
Når er mønstertilpasning nyttig? Listen over slike saker er overraskende lang! Hver gang du bruker komplekse nestede if-konstruksjoner, kan mønstertilpasning gjøre en bedre jobb med mindre kode. Et godt eksempel som kommer til hjernen er WndProc-funksjonen, som er implementert i hvert Win32-program (selv om den er skjult for programmereren bak et høyt gjerde av abstraksjoner). Vanligvis kan mønstertilpasning til og med sjekke innholdet i samlingene. For eksempel, hvis du sender en matrise til en funksjon, kan du velge alle matriser hvis første element er lik 1 og hvis tredje element er større enn 3.

En annen fordel med mønstertilpasning er at hvis du gjør endringer, trenger du ikke å grave deg gjennom en stor funksjon. Alt du trenger å gjøre er å legge til (eller endre) noen funksjonsdefinisjoner. Dermed blir vi kvitt et helt lag med mønstre fra den kjente boken til Fire-gjengen. Jo mer komplekse og forgrenede forholdene er, jo mer nyttig vil det være å bruke mønstertilpasning. Når du begynner å bruke dem, vil du lure på hvordan du noen gang klarte deg uten dem.

Nedleggelser

Så langt har vi diskutert funksjonene til FP i sammenheng med "rent" funksjonelle språk - språk som er implementeringer av lambda-kalkulus og ikke inneholder funksjoner som motsier det formelle kirkesystemet. Imidlertid brukes mange funksjoner til funksjonelle språk utenfor lambda-kalkulus. Selv om implementeringen av et aksiomatisk system er interessant fra et programmeringssynspunkt når det gjelder matematiske uttrykk, er dette kanskje ikke alltid aktuelt i praksis. Mange språk foretrekker å bruke elementer av funksjonelle språk uten å følge en streng funksjonell doktrine. Noen slike språk (for eksempel Common Lisp) krever ikke at variabler er endelige - verdiene deres kan endres. De krever ikke engang at funksjoner kun avhenger av argumentene deres - funksjoner har tilgang til tilstander utenfor deres omfang. Men samtidig inkluderer de funksjoner som funksjoner av høyere orden. Funksjonsoverføring på et ikke-rent språk er litt forskjellig fra tilsvarende operasjon innen lambda-regning og krever en interessant funksjon kalt leksikalsk lukking. La oss ta en titt på følgende eksempel. Husk det i i dette tilfellet variabler er ikke endelige, og en funksjon kan få tilgang til variabler utenfor sitt omfang:

Funksjon makePowerFn(int power) ( int powerFn(int base) ( return pow(base, power); ) return powerFn; ) Funksjon kvadrat = makePowerFn(2); kvadrat(3); // returnerer 9
Make-power-fn-funksjonen returnerer en funksjon som tar ett argument og hever det til en viss potens. Hva skjer når vi prøver å evaluere kvadrat(3) ? Den variable kraften er utenfor rekkevidden av powerFn fordi makePowerFn allerede er fullført og stabelen er ødelagt. Hvordan fungerer square da? Språket må liksom lagre betydningen av makt for at kvadratfunksjonen skal fungere. Hva om vi lager en annen kubefunksjon som hever et tall til tredje potens? Språket må lagre to effektverdier for hver funksjon opprettet i make-power-fn. Fenomenet med å lagre disse verdiene kalles lukking. En nedleggelse bevarer ikke bare argumentene til toppfunksjonen. For eksempel kan en lukking se slik ut:

Funksjon makeIncrementer() ( int n = 0; int increment() ( return ++n; ) ) Funksjon inc1 = makeIncrementer(); Funksjon inc2 = makeIncrementer(); inc1(); // returnerer 1; inc1(); // returnerer 2; inc1(); // returnerer 3; inc2(); // returnerer 1; inc2(); // returnerer 2; inc2(); // returnerer 3;
Under utførelse lagres verdiene til n og tellere har tilgang til dem. Dessuten har hver teller sin egen kopi av n, til tross for at de burde ha forsvunnet etter at makeIncrementer-funksjonen kjørte. Hvordan klarer kompilatoren å kompilere dette? Hva skjer bak kulissene til nedleggelser? Heldigvis har vi et magisk pass.

Alt er gjort ganske logisk. Ved første øyekast er det klart at lokale variabler ikke lenger er underlagt scope-regler og levetiden deres er udefinert. Det er klart at de ikke lenger lagres på stabelen - de må holdes på haugen. Lukkingen er derfor laget som den normale funksjonen vi diskuterte tidligere, bortsett fra at den har en ekstra referanse til de omkringliggende variablene:

Klasse some_function_t ( SymbolTable parentScope; // ... )
Hvis en lukking får tilgang til en variabel som ikke er i det lokale omfanget, tar den hensyn til det overordnede omfanget. Det er alt! Closure forbinder den funksjonelle verdenen med OOP-verdenen. Hver gang du oppretter en klasse som lagrer en tilstand og sender den et sted, husk om stenginger. En lukking er bare et objekt som skaper "attributter" i farten, og tar dem utenfor rekkevidden slik at du ikke trenger å gjøre det selv.

Hva nå?

Denne artikkelen berører bare toppen av isfjellet for funksjonell programmering. Du kan grave dypere og se noe virkelig stort, og i vårt tilfelle noe bra. I fremtiden planlegger jeg å skrive om kategoriteori, monader, funksjonelle datastrukturer, typesystemer i funksjonelle språk, funksjonell multithreading, funksjonelle databaser og mange flere ting. Hvis jeg kan skrive (og studere i prosessen) om halvparten av disse emnene, vil ikke livet mitt være forgjeves. I mellomtiden, Google- din trofaste venn.

Fordeler med funksjonell programmering

Du tenker nok at jeg ikke kan lage en sak for å rettferdiggjøre det monstrøse innslaget ovenfor. Da jeg først begynte å lære funksjonell programmering, trodde jeg det også. Jeg tok feil. Det er veldig gode argumenter for denne stilen. Noen av dem er subjektive. For eksempel hevder programmerere at funksjonelle programmer er lettere å forstå. Jeg vil ikke komme med slike argumenter, for alle vet at letthet å forstå er en veldig subjektiv ting. Heldigvis for meg er det fortsatt mange objektive argumenter.

Enhetstesting

Feilsøking

Multithreading

Hvis dette er tilfelle, hvorfor brukes funksjonelle programmeringsspråk så sjelden i flertrådede applikasjoner? Faktisk oftere enn du tror. Ericsson har utviklet et funksjonelt språk kalt Erlang for bruk på feiltolerante og skalerbare telekommunikasjonssvitsjer. Mange la merke til fordelene med Erlang og begynte å bruke den. Vi snakker om telekommunikasjons- og trafikkkontrollsystemer, som ikke er på langt nær så lett skalerbare som typiske systemer utviklet på Wall Street. Faktisk er systemer skrevet i Erlang ikke så skalerbare og pålitelige som Java-systemer. Erlang-systemer er rett og slett superpålitelige.

En funksjonell språkkompilator kan analysere koden, klassifisere funksjonene som produserer linjene s1 og s2 som tidkrevende funksjoner, og kjøre dem parallelt. Dette er umulig å gjøre på et imperativt språk, fordi hver funksjon kan endre ekstern tilstand og koden umiddelbart etter samtalen kan avhenge av den. I FP er automatisk analyse av funksjoner og søk etter egnede kandidater for parallellisering en triviell oppgave, som automatisk inline! Slik sett er den funksjonelle programmeringsstilen fremtidssikker. Maskinvareutviklere kan ikke lenger få CPU-en til å fungere raskere. I stedet øker de antallet kjerner og krever en firedobling i multi-threaded databehandlingshastighet. Selvfølgelig glemmer de å si akkurat i tide at den nye prosessoren din bare vil vise gevinster i programmer designet med parallellisering i tankene. Det er svært få av disse blant imperativ programvare. Men 100 % av funksjonelle programmer er klare for multithreading ut av esken.

Hot Deployment

I gamle dager måtte du starte datamaskinen på nytt for å installere Windows-oppdateringer. Mange ganger. Etter å ha installert en ny versjon av mediespilleren. Det har vært betydelige endringer i Windows XP, men situasjonen er fortsatt langt fra ideell (jeg kjørte Windows Update på jobben i dag, og nå lar den irriterende påminnelsen meg ikke være før jeg starter på nytt). Unix-systemer hadde en bedre oppdateringsmodell. For å installere oppdateringer, måtte jeg stoppe noen komponenter, men ikke hele operativsystemet. Selv om situasjonen ser bedre ut, er den fortsatt ikke akseptabel for en stor klasse serverapplikasjoner. Telekommunikasjonssystemer må være slått på 100 % av tiden, for hvis en oppdatering hindrer en person i å ringe en ambulanse, kan liv gå tapt. Wall Street-firmaer ønsker heller ikke å stenge servere over helgen for å installere oppdateringer.

Maskinassisterte prøvetrykk og optimaliseringer

En annen interessant egenskap ved funksjonelle programmeringsspråk er at de kan læres fra et matematisk synspunkt. Siden et funksjonelt språk er en implementering av et formelt system, kan alle matematiske operasjoner brukt på papir brukes på funksjonelle programmer. Kompilatoren kan for eksempel konvertere et stykke kode til et ekvivalent, men mer effektivt stykke, mens den matematisk rettferdiggjør deres ekvivalens. Relasjonsdatabaser har gjort disse optimaliseringene i årevis. Det er ingenting som hindrer deg i å bruke lignende teknikker i vanlige programmer.

I tillegg kan du bruke matematikk for å bevise riktigheten av deler av programmene dine. Hvis du vil, kan du skrive verktøy som analyserer koden din og automatisk lager Unit-tester for kantsaker! Denne funksjonaliteten er uvurderlig for bunnsolide systemer. Ved utvikling av pacemakerovervåking eller lufttrafikkstyringssystemer er slike verktøy et must. Hvis utviklingen din ikke er innen virksomhetskritiske applikasjoner, vil automatiserte verifiseringsverktøy fortsatt gi deg en stor fordel i forhold til konkurrentene dine.

Funksjoner av høyere orden

I FP er ikke en funksjon det samme som en funksjon i Java eller C. Det er et supersett - de kan gjøre det samme som Java-funksjoner og enda mer. La oss si at vi har en funksjon i C:

Klasse add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Add-symbolet er egentlig ikke en funksjon. Dette er en liten klasse med én metode. Nå kan vi sende add som et argument til andre funksjoner. Vi kan skrive det inn i et annet symbol. Vi kan lage forekomster av add_function_t under kjøring, og de vil bli ødelagt av søppelsamleren hvis de ikke lenger er nødvendige. Funksjoner blir grunnleggende objekter, akkurat som tall og strenger. Funksjoner som opererer på funksjoner (ta dem som argumenter) kalles høyere-ordens funksjoner. Ikke la dette skremme deg. Konseptet med funksjoner av høyere orden er nesten det samme som konseptet med Java-klasser som opererer på hverandre (vi kan sende klasser til andre klasser). Vi kan kalle dem "klasser av høyere orden", men ingen bryr seg med det fordi Java ikke har et strengt akademisk fellesskap bak seg.

La oss anta at vi har et stykke Java-kode som mottar en melding, transformerer den på forskjellige måter og overfører den til en annen server.

Abstrakt klasse MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) abstract String getClientCode(); // ... ) class MessageHandlerOne utvider MessageHandler ( String getClientCode() ( returner "ABCD_123"; ) ) klassen MessageHandlerTwo utvider MessageHandler ( String getClientCode() ( returnerer "123_ABCD"; ) )
Nå for hver server kan vi lage en forekomst av den tilsvarende klassen. Det blir mer praktisk å legge til nye servere. Men det er mye tekst for en så liten endring. Jeg måtte lage to nye typer bare for å legge til støtte for annen klientkode! La oss nå gjøre det samme på språket vårt med støtte for funksjoner av høyere orden:

Currying

Lat evaluering

Lat (eller utsatt) evaluering er en interessant teknikk som blir mulig når du forstår den funksjonelle filosofien. Vi har allerede sett følgende kodebit når vi snakker om multithreading:

Lazy computing har en rekke fordeler i tillegg til noen ulemper. I neste avsnitt skal vi diskutere fordelene og jeg vil forklare hvordan man kan leve med ulempene.

Optimalisering

Lat evaluering gir et enormt potensial for optimaliseringer. En lat kompilator ser på kode på samme måte som en matematiker ser på algebraiske uttrykk - den kan angre ting, kansellere utførelse av visse deler av koden, endre rekkefølgen på kall for større effektivitet, til og med arrangere kode på en slik måte at antallet reduseres av feil, samtidig som integriteten til programmet sikres. Dette er den største fordelen med å beskrive et program ved hjelp av strenge formelle primitiver - koden adlyder matematiske lover og kan studeres ved hjelp av matematiske metoder.

Abstrahere kontrollstrukturer

Lazy databehandling gir et så høyt abstraksjonsnivå at fantastiske ting blir mulig. Tenk deg for eksempel å implementere følgende kontrollstruktur:

Uendelige datastrukturer

Late språk lar deg lage uendelige datastrukturer, som er mye vanskeligere å lage på strenge språk. - bare ikke i Python]. Tenk deg for eksempel Fibonacci-sekvensen. Det er klart at vi ikke kan beregne en uendelig liste på en begrenset tid og fortsatt lagre den i minnet. På strenge språk som Java ville vi ganske enkelt skrive en funksjon som returnerer et vilkårlig medlem av sekvensen. På språk som Haskell kan vi abstrahere bort og ganske enkelt erklære en uendelig liste over Fibonacci-tall. Siden språket er lat, vil kun de nødvendige delene av listen som faktisk brukes i programmet beregnes. Dette lar deg abstrahere fra et stort antall problemer og se på dem fra et høyere nivå (du kan for eksempel bruke funksjoner for å behandle lister på uendelige sekvenser).

Feil

Gratis ost kommer selvfølgelig kun i en musefelle. Late beregninger har en rekke ulemper. Dette er hovedsakelig mangler fra latskap. I virkeligheten er direkte rekkefølge av beregninger svært ofte nødvendig. Ta for eksempel følgende kode:

På et lat språk er det ingen som garanterer at den første linjen vil bli utført før den andre! Dette betyr at vi ikke kan gjøre I/O, vi kan ikke bruke native funksjoner normalt (de må tross alt kalles i en bestemt rekkefølge for å gjøre rede for bivirkninger), og vi kan ikke samhandle med utsiden verden! Hvis vi introduserer en mekanisme for å bestille utførelse av kode, vil vi miste fordelen med matematisk strenghet til koden (og da vil vi miste alle fordelene med funksjonell programmering). Heldigvis er ikke alt tapt. Matematikere begynte å jobbe og kom opp med flere teknikker for å sikre at instruksjonene ble utført i riktig rekkefølge uten å miste funksjonsånden. Vi har det beste fra to verdener! Slike teknikker inkluderer fortsettelser, monader og unikhetsskriving. I denne artikkelen skal vi jobbe med fortsettelser, og la monader og entydig skriving ligge til neste gang. Det er interessant at fortsettelser er en veldig nyttig ting, som ikke bare brukes til å spesifisere en streng rekkefølge av beregninger. Vi skal snakke om dette også.

Oppfølgere

Int j = add(5, 10, kvadrat);
I dette tilfellet mottar add et ekstra argument - en funksjon som kalles opp etter at add er ferdig. I begge eksemplene vil j være lik 225.

Dette er den første teknikken som lar deg spesifisere rekkefølgen som to uttrykk utføres i. La oss gå tilbake til vårt I/O-eksempel.

Men fordelene med oppfølgere slutter ikke der. Vi kan skrive hele programmet ved hjelp av CPS, slik at hver funksjon kalles med en ekstra parameter, en fortsettelse, som resultatet sendes til. I prinsippet kan ethvert program oversettes til CPS hvis hver funksjon behandles som et spesielt tilfelle av fortsettelser. Denne konverteringen kan gjøres automatisk (faktisk gjør mange kompilatorer det).

Ok, nå forstår vi hva den nåværende fortsettelsen er. Hva betyr det? Hvis vi tar den nåværende fortsettelsen og lagrer den et sted, lagrer vi dermed den nåværende tilstanden til programmet - vi fryser den. Dette ligner på OS-dvalemodus. Fortsettelsesobjektet lagrer informasjonen som trengs for å gjenoppta programkjøringen fra punktet der fortsettelsesobjektet ble forespurt. Operativsystemet gjør dette med programmene dine hele tiden når det bytter kontekst mellom tråder. Den eneste forskjellen er at alt er under kontroll av OS. Hvis du ber om et fortsettelsesobjekt (i Scheme gjøres dette ved å kalle oppkall-med-aktuell-fortsettelse-funksjonen), vil du motta et objekt med gjeldende fortsettelse - stabelen (eller i tilfelle av CPS, den neste anropsfunksjonen ). Du kan lagre dette objektet til en variabel (eller til og med på disk). Hvis du bestemmer deg for å "starte" programmet på nytt med denne fortsettelsen, blir tilstanden til programmet ditt "transformert" til tilstanden da fortsettelsesobjektet ble tatt. Dette er det samme som å bytte til en suspendert tråd, eller å vekke operativsystemet etter dvalemodus. Med unntak av at du kan gjøre dette mange ganger på rad. Etter at operativsystemet våkner, blir dvaleinformasjonen ødelagt. Hvis dette ikke ble gjort, ville det være mulig å gjenopprette OS-tilstanden fra samme punkt. Det er nesten som å reise gjennom tiden. Med oppfølgere har du råd til det!

Mønstermatching

La oss starte vår introduksjon til mønstertilpasning med følgende eksempel. Her er en funksjon for å beregne Fibonacci-tall i Java:

Int fib(int n) ( if(n == 0) return 1; if(n == 1) return 1; return fib(n - 2) + fib(n - 1); )
Og her er et eksempel på et Java-lignende språk med støtte for mønstertilpasning

Int fib(0) ( return 1; ) int fib(1) ( return 1; ) int fib(int n) ( return fib(n - 2) + fib(n - 1); )
Hva er forskjellen? Kompilatoren implementerer forgreningen for oss.

Mønstertilpasning ser vanligvis mer komplisert ut enn i vårt eksempel. For eksempel lar et komplekst mønstertilpasningssystem deg skrive følgende kode:

Nedleggelser

Så langt har vi diskutert funksjonene til FP i sammenheng med "rent" funksjonelle språk - språk som er implementeringer av lambda-kalkulus og ikke inneholder funksjoner som motsier det formelle kirkesystemet. Imidlertid brukes mange funksjoner til funksjonelle språk utenfor lambda-kalkulus. Selv om implementeringen av et aksiomatisk system er interessant fra et programmeringssynspunkt når det gjelder matematiske uttrykk, er dette kanskje ikke alltid aktuelt i praksis. Mange språk foretrekker å bruke elementer av funksjonelle språk uten å følge en streng funksjonell doktrine. Noen slike språk (for eksempel Common Lisp) krever ikke at variabler er endelige - verdiene deres kan endres. De krever ikke engang at funksjoner kun avhenger av argumentene deres - funksjoner har tilgang til tilstander utenfor deres omfang. Men samtidig inkluderer de funksjoner som funksjoner av høyere orden. Funksjonsoverføring på et ikke-rent språk er litt forskjellig fra tilsvarende operasjon innen lambda-regning og krever en interessant funksjon kalt leksikalsk lukking. La oss ta en titt på følgende eksempel. Husk at i dette tilfellet er ikke variablene endelige og funksjonen kan få tilgang til variabler utenfor sitt omfang:

Hva nå?

Late beregninger

I tradisjonelle programmeringsspråk (som C++) fører tilkalling av en funksjon til at alle argumenter blir evaluert. Denne metoden for å kalle en funksjon kalles call-by-value. Hvis et argument ikke ble brukt i funksjonen, går resultatet av beregningen tapt, derfor ble beregningen gjort forgjeves. På en måte er det motsatte av call-by-value call-by-necessity. I dette tilfellet evalueres argumentet bare hvis det er nødvendig for å beregne resultatet. Et eksempel på denne virkemåten er konjunksjonsoperatoren fra C++ (&&), som ikke evaluerer verdien av det andre argumentet hvis det første argumentet er usant.

Hvis et funksjonelt språk ikke støtter lat evaluering, kalles det strengt. Faktisk, på slike språk er rekkefølgen for evaluering strengt definert. Eksempler på strenge språk inkluderer Scheme, Standard ML og Caml.

Språk som bruker lat evaluering kalles ikke-strenge. Haskell er et løst språk, akkurat som for eksempel Gofer og Miranda. Slappe språk er ofte rene.

Svært ofte inkluderer strenge språk støtte for noen av de nyttige funksjonene som finnes på ikke-strenge språk, for eksempel uendelige lister. Standard ML leveres med en spesiell modul for å støtte utsatte beregninger. I tillegg støtter Objective Caml det ekstra reserverte ordet lat og en konstruksjon for lister med verdier beregnet etter behov.

Denne delen gir Kort beskrivelse noen funksjonelle programmeringsspråk (svært få).

§ Lisp(Listebehandler). Det regnes som det første funksjonelle programmeringsspråket. Ikke skrevet. Den inneholder mange imperative egenskaper, men generelt sett oppmuntrer den til den funksjonelle stilen til programmering. Bruker call-by-value for beregninger. Det er en objektorientert dialekt av språket - CLOS.

§ JEG SVØMMER(Hvis du ser hva jeg mener). Funksjonell språkprototype. Utviklet av Landin på 60-tallet av 1900-tallet for å demonstrere hva et funksjonelt programmeringsspråk kan være. Sammen med språket utviklet Landin også en spesiell virtuell maskin for å kjøre programmer på ISWIM. Dette virtuell maskin, basert på call-by-value, kalles SECD-maskinen. Syntaksen til mange funksjonelle språk er basert på syntaksen til ISWIM-språket. Syntaksen til ISWIM er lik den til ML, spesielt Caml.

§ Opplegg. En Lisp-dialekt beregnet på vitenskapelig forskning innen datavitenskap. Scheme ble designet med vekt på eleganse og enkelhet i språket. Dette gjør språket mye mindre enn Common Lisp.

§ M.L.(Metaspråk). En familie av strenge språk med et utviklet polymorf type system og parameteriserbare moduler. ML undervises på mange vestlige universiteter (noen til og med som det første programmeringsspråket).

§ Standard ML. Et av de første maskinskrevne funksjonelle programmeringsspråkene. Inneholder noen imperative egenskaper som lenker til foranderlige verdier og er derfor ikke ren. Bruker call-by-value for beregninger. En veldig interessant implementering av modularitet. Kraftig polymorf type system. Den siste språkstandarden er Standard ML-97, som det finnes formelle matematiske definisjoner av syntaksen for, samt den statiske og dynamiske semantikken til språket.

§ Caml lys Og Målsetting Caml. Som Standard ML tilhører den ML-familien. Mål Caml skiller seg fra Caml Light hovedsakelig i sin støtte for klassisk objektorientert programmering. Akkurat som Standard ML er streng, men har noe innebygd støtte for lat evaluering.

§ Miranda. Utviklet av David Turner som et standard funksjonelt språk som brukte lat evaluering. Den har et strengt polymorf type system. I likhet med ML undervises det på mange universiteter. Han hadde stor innflytelse på utviklerne av Haskell-språket.

§ Haskell. Et av de vanligste ikke-strenge språkene. Den har et veldig utviklet skrivesystem. Modulsystemet er noe mindre godt utviklet. Den siste språkstandarden er Haskell-98.

§ Gofer(Bra for ekvasjonelt resonnement). Forenklet Haskell-dialekt. Designet for undervisning i funksjonell programmering.

§ Ren. Spesielt designet for parallell og distribuert programmering. Syntaksen ligner på Haskell. Ren. Bruker utsatte beregninger. Kompilatoren kommer med et sett med biblioteker (I/O-biblioteker) som lar deg programmere et grafisk brukergrensesnitt under Win32 eller MacOS.

La oss minne deg på det den viktigste egenskapen Den funksjonelle tilnærmingen er det faktum at ethvert program utviklet i et funksjonelt programmeringsspråk kan betraktes som en funksjon, hvis argumenter også kan være funksjoner.

Den funksjonelle tilnærmingen ga opphav til en hel familie av språk, hvis stamfar, som allerede nevnt, var programmeringsspråket LISP. Senere, på 70-tallet, ble den originale versjonen av ML-språket utviklet, som senere utviklet seg spesielt til SML, så vel som en rekke andre språk. Av disse er kanskje den "yngste" Haskell-språket, opprettet ganske nylig, på 90-tallet.

En viktig fordel med å implementere funksjonelle programmeringsspråk er den automatiserte dynamiske allokeringen av dataminne for datalagring. I dette tilfellet blir programmereren kvitt behovet for å kontrollere dataene, og kan om nødvendig kjøre "søppelsamling" -funksjonen - tømme minne fra data som programmet ikke lenger trenger.

Komplekse programmer i den funksjonelle tilnærmingen bygges ved å aggregere funksjoner. I dette tilfellet er programteksten en funksjon, der noen av argumentene også kan betraktes som funksjoner. Dermed kommer gjenbruk av kode ned til å kalle en tidligere beskrevet funksjon, hvis struktur, i motsetning til en imperativ språkprosedyre, er matematisk transparent.

Fordi en funksjon er en naturlig formalisme for funksjonelle programmeringsspråk, er implementering av ulike aspekter ved funksjonsrelatert programmering sterkt forenklet. Å skrive rekursive funksjoner blir intuitivt transparent, d.v.s. funksjoner som kaller seg selv som et argument. Implementeringen av behandling av rekursive datastrukturer blir også naturlig.

På grunn av implementeringen av en mønstertilpasningsmekanisme, er funksjonelle programmeringsspråk som ML og Haskell gode for symbolsk behandling.

Naturligvis er funksjonelle programmeringsspråk ikke uten noen ulemper.

Disse inkluderer ofte den ikke-lineære strukturen til programmet og den relativt lave effektiviteten av implementeringen. Den første ulempen er imidlertid ganske subjektiv, og den andre har blitt overvunnet av moderne implementeringer, spesielt en rekke nyere SML-språkoversettere, inkludert en kompilator for Microsoft .NET-miljøet.

For å utvikle profesjonell programvare i funksjonelle programmeringsspråk, må du ha en dyp forståelse av funksjonens natur.

Merk at begrepet "funksjon" i matematisk formalisering og programvareimplementering refererer til forskjellige konsepter.

Dermed er en matematisk funksjon f med et domene av definisjon A og et verdiområde B settet med ordnede par

slik at hvis

(a,b 1) f og (a,b 2) f,

I sin tur er en funksjon i et programmeringsspråk en konstruksjon av dette språket som beskriver reglene for å konvertere et argument (den såkalte faktiske parameteren) til et resultat.

For å formalisere konseptet "funksjon", ble en matematisk teori kjent som lambda-regning konstruert. Mer presist bør denne beregningen kalles beregningen av lambda-konverteringer.

Konvertering refererer til transformasjon av kalkulusobjekter (og i programmering, funksjoner og data) fra en form til en annen. Den opprinnelige oppgaven i matematikk var det et ønske om å forenkle uttrykksformen. I programmering er ikke denne oppgaven så viktig, selv om, som vi skal se senere, bruk av lambda-kalkulus som den første formaliseringen kan bidra til å forenkle typen program, dvs. føre til programkodeoptimalisering.

I tillegg gir konverteringer en overgang til nyinnførte notasjoner og gjør det dermed mulig å representere fagområdet i en mer kompakt eller mer detaljert form, eller med andre ord, matematisk språk, endre abstraksjonsnivå ift fagområde. Denne funksjonen er også mye brukt av objektorienterte og strukturert-modulære programmeringsspråk i hierarkiet av objekter, programfragmenter og datastrukturer. Samspillet mellom applikasjonskomponenter i .NET er basert på samme prinsipp. Det er i denne forstand at overgangen til nye notasjoner er et av de viktigste elementene i programmering generelt, og det er lambda-regning (i motsetning til mange andre grener av matematikk) som representerer en adekvat måte å formalisere renotasjoner.

La oss systematisere utviklingen av teoriene som ligger til grunn for den moderne tilnærmingen til lambda-kalkulus.

La oss vurdere utviklingen av programmeringsspråk som utvikler seg innenfor rammen av den funksjonelle tilnærmingen.

Tidlige funksjonelle programmeringsspråk, som stammer fra det klassiske LISP-språket (LISt Processing), ble designet for å behandle lister, dvs. symbolsk informasjon. I dette tilfellet var hovedtypene et atomelement og en liste over atomelementer, og hovedvekten var på å analysere innholdet i listen.

Utviklingen av tidlige programmeringsspråk ble funksjonelle programmeringsspråk med sterk skriving, et typisk eksempel her er den klassiske ML, og dens direkte etterkommer SML. I sterkt skrevet språk må hver konstruksjon (eller uttrykk) ha en type.

I senere funksjonelle programmeringsspråk er det imidlertid ikke behov for eksplisitt typetilordning, og typene opprinnelig udefinerte uttrykk, som i SML, kan utledes (før programmet kjøres) basert på typene uttrykk som er knyttet til dem .

Det neste trinnet i utviklingen av funksjonelle programmeringsspråk var støtten til polymorfe funksjoner, dvs. funksjoner med parametriske argumenter (analoger matematisk funksjon med parametere). Spesielt støttes polymorfisme i SML, Miranda og Haskell.

På det nåværende utviklingsstadiet har "ny generasjons" funksjonelle programmeringsspråk dukket opp med følgende avanserte evner: mønstertilpasning (Scheme, SML, Miranda, Haskell), parametrisk polymorfisme (SML) og såkalt "lat" (som nødvendig) beregninger (Haskell, Miranda, S.M.L.).

Familien av funksjonelle programmeringsspråk er ganske stor. Dette bevises ikke så mye av den betydelige listen over språk, men av det faktum at mange språk har gitt opphav til hele trender innen programmering. La oss huske at LISP ga opphav til en hel familie av språk: Scheme, InterLisp, COMMON Lisp, etc.

SML-programmeringsspråket var intet unntak, som ble opprettet i form av ML-språket av R. Milner ved MIT (Massachusetts Institute of Technology) og var opprinnelig ment for logiske deduksjoner, spesielt teorembevis. Språk er annerledes sterk skriving, mangler den parametrisk polymorfisme.

Utviklingen av "klassisk" ML har blitt tre moderne språk med nesten identiske evner (parametrisk polymorfisme, mønstertilpasning, "late" beregninger). Dette er SML-språket, utviklet i Storbritannia og USA, CaML, skapt av en gruppe franske forskere ved INRIA Institute, SML/NJ - en dialekt av SML fra New Jersey, og også en russisk utvikling - mosml (den " Moskva" dialekt av ML).

Nærheten til matematisk formalisering og den innledende funksjonelle orienteringen forårsaket følgende fordeler med den funksjonelle tilnærmingen:

1. enkel testing og verifisering av programkode basert på muligheten for å konstruere et strengt matematisk bevis på riktigheten av programmer;

2. forening av presentasjonen av programmet og data (data kan innkapsles i programmet som funksjonsargumenter, betegnelsen eller beregningen av funksjonsverdien kan gjøres etter behov);

3. sikker skriving: ugyldige dataoperasjoner er ekskludert;

4. dynamisk skriving: det er mulig å oppdage skrivefeil under kjøring (fraværet av denne egenskapen i tidlige funksjonelle programmeringsspråk kan føre til at datamaskinens RAM er full);

5. uavhengighet av programvareimplementeringen fra maskinrepresentasjonen av data og systemarkitekturen til programmet (programmereren er fokusert på detaljene i implementeringen, og ikke på funksjonene til maskinrepresentasjonen av data).

Merk at det å realisere fordelene som funksjonelle programmeringsspråk gir avhenger betydelig av valget av programvare og maskinvareplattform.

Hvis .NET-teknologi velges som programvareplattform, nesten uavhengig av maskinvareimplementering, programmerer eller leder programvareprosjekt mottar i tillegg følgende fordeler:

1. integrering av ulike funksjonelle programmeringsspråk (mens man maksimerer fordelene med hvert språk, spesielt gir Scheme en mønstertilpasningsmekanisme, og SML gir muligheten til å beregne etter behov);

2. integrering av ulike tilnærminger til programmering basert på den flerspråklige Common Language Infrastructure, eller CLI (spesielt er det mulig å bruke C# for å gi fordelene med en objektorientert tilnærming og SML - funksjonell, som i dette kurset) ;

3. felles enhetlig skrivesystem Common Type System, CTS (uniform og sikker ledelse typer data i programmet);

4. flertrinns, fleksibelt system for å sikre sikkerheten til programkoden (spesielt basert på monteringsmekanismen).

Hovedtrekkene til funksjonelle programmeringsspråk som skiller dem fra både imperative språk og logiske programmeringsspråk er referansetransparens og determinisme. I funksjonelle språk er det betydelig variasjon i parametere som skriving og regneregler. På mange språk er rekkefølgen for evaluering strengt definert. Men noen ganger inneholder strenge språk støtte for noen nyttige elementer som er iboende i ikke-strenge språk, for eksempel uendelige lister (Standard ML har en spesiell modul for å støtte lat evaluering). I kontrast tillater ikke-strenge språk energisk beregning i noen tilfeller.

Dermed har Miranda lat semantikk, men lar deg spesifisere strenge konstruktører ved å markere konstruktørargumentene på en bestemt måte.

Mange moderne funksjonelle programmeringsspråk er sterkt maskinskrevne språk (sterk skriving). Sterk skriving gir større sikkerhet. Mange feil kan rettes på kompileringsstadiet, slik at feilsøkingsstadiet og den totale programutviklingstiden reduseres. Sterk skriving lar kompilatoren generere mer effektiv kode og dermed fremskynde programkjøringen. Sammen med dette er det funksjonelle språk med dynamisk skriving. Datatypen på slike språk bestemmes under programkjøring (kapittel 3). Noen ganger kalles de "typeløse". Fordelene deres inkluderer det faktum at programmer skrevet på disse språkene har større generalitet. En ulempe kan betraktes som tilskrivelsen av mange feil til programutførelsesstadiet og det tilhørende behovet for å bruke typekontrollfunksjoner og en tilsvarende reduksjon i programmets generalitet. Innskrevne språk bidrar til generering av mer "pålitelig" kode, mens maskinskrevne språk produserer mer "generell" kode.

Det neste kriteriet som funksjonelle programmeringsspråk kan klassifiseres etter kan være tilstedeværelsen av imperative mekanismer. Samtidig er det vanlig å kalle funksjonelle programmeringsspråk som er blottet for imperative mekanismer "rene", og de som har dem kalles "urene". I oversikten over funksjonelle programmeringsspråk nedenfor, vil programmeringsspråk bli referert til som "praktisk" og "akademisk". "Praktiske" språk forstås som språk som har en kommersiell applikasjon (virkelige applikasjoner ble utviklet i dem eller det var kommersielle programmeringssystemer). Akademiske programmeringsspråk er populære i forskningskretser og i feltet datautdanning, men det er praktisk talt ingen kommersielle applikasjoner skrevet på slike språk. De forblir bare et verktøy for å utføre teoretisk forskning innen datavitenskap og er mye brukt i utdanningsprosessen.

En liste over de mest populære funksjonelle programmeringsspråkene er gitt nedenfor ved å bruke følgende kriterier: generell informasjon; skriving; type beregning; renhet.

Vanlig Lisp. Versjon av Lisp, som siden 1970 kan betraktes som en språkstandard, takket være støtte fra laboratoriet kunstig intelligens Massachusetts Institute of Technology, typeløst, energisk, med et stort sett med imperative inneslutninger som tillater tildeling og ødeleggelse av strukturer. Praktisk. Det er nok å si at vektorgrafikkeditoren AutoCAD ble skrevet i Lisp.

Opplegg. En Lisp-dialekt beregnet for vitenskapelig forskning innen informatikk og undervisning i funksjonell programmering. Takket være mangelen på imperative inneslutninger er språket mye mindre enn vanlig lisp. Dateres tilbake til et språk utviklet av J. McCarthy i 1962. Akademisk, typeløs, energisk, ren.

Refal. En familie av språk utviklet av V. F. Turchin. Det eldste medlemmet av denne familien ble først realisert i 1968 i Russland. Det er fortsatt mye brukt i akademiske kretser. Inneholder logiske programmeringselementer (mønstertilpasning). Derfor foreslås Refal-språket i denne lærebok som språk for selvstudium.

Miranda. Sterkt skrevet, støtter brukerdatatyper og polymorfisme. Utviklet av Turner basert på de tidligere SALS- og KRC-språkene. Har lat semantikk. Ingen tvingende inkluderinger.

Haskell. Utviklingen av språket skjedde på slutten av forrige århundre. Allment kjent i akademiske kretser. På noen vestlige universiteter brukes det som hovedspråk for studenter å studere. Et av de kraftigste funksjonelle språkene. Lat språk. Rent funksjonelt språk. Skrevet. Haskell er et flott verktøy for å lære og eksperimentere med komplekse funksjonelle datatyper. Programmer skrevet i Haskell har en betydelig objektkodestørrelse og lav utførelseshastighet.

Ren. En Haskell-dialekt skreddersydd for behovene til praktisk programmering. Som Haskell er det et lat, rent funksjonelt språk, som inneholder typeklasser. Men Clean inneholder også interessante funksjoner som ikke har noe tilsvarende i Haskell. For eksempel er imperative funksjoner i Clean basert på unike typer, ideen om hvilke er lånt fra lineær logikk. Clean inneholder mekanismer som kan forbedre effektiviteten til programmer betydelig. Disse mekanismene undertrykker eksplisitt lat beregninger. Clean-implementeringen er et kommersielt produkt, men en gratisversjon er tilgjengelig for forsknings- og utdanningsformål.

ML (Metaspråk). Utviklet av en gruppe programmerere ledet av Robert Milier på midten av 70-tallet. i Edinburgh (Edinburgh Logic for Computable Functions). Ideen med språket var å lage en mekanisme for å konstruere formelle bevis i et system av logikk for beregnbare funksjoner. I 1983 ble språket revidert for å inkludere konsepter som moduler. Kom til å bli kalt standard ML. ML er sterk maskinskrevet språk med statisk typekontroll og applikativ programkjøring. Den har vunnet stor popularitet i forskningsmiljøer og innen datautdanning.

Funksjonell programmering

1. Introduksjon

Programmer på tradisjonelle programmeringsspråk som C, Pascal, Java, etc. De består av en sekvens av modifikasjoner av verdiene til et visst sett med variabler, som kalles tilstand. Hvis vi ikke vurderer I/O-operasjoner, og heller ikke tar hensyn til at programmet kan kjøre kontinuerlig (dvs. uten stopp, som i tilfellet med serverprogrammer), kan vi gjøre følgende abstraksjon. Før programmet begynner å kjøre, har tilstanden en startverdi σ0, som representerer inngangsverdiene til programmet. Etter at programmet avsluttes, har staten en ny verdi σ0, som inkluderer det som kan anses som "resultatet" av programmet. Under utførelse endrer hver kommando tilstand; derfor går staten gjennom en begrenset sekvens av verdier:

σ = σ0 → σ1 → σ2 → · · · → σn = σ0

Tilstanden endres ved å bruke tilordningskommandoer, skrevet som v=E eller v:=E, der v er en variabel og E er et uttrykk. Disse kommandoene følger etter hverandre; Utsagn som hvis og mens lar deg endre rekkefølgen disse kommandoene utføres i avhengig av gjeldende tilstandsverdi. Denne programmeringsstilen kalles imperativ eller prosedyremessig.

Funksjonell programmering representerer et paradigme som er fundamentalt forskjellig fra modellen presentert ovenfor. Et funksjonelt program er et uttrykk (i matematisk forstand); å utføre programmet betyr å beregne verdien av dette uttrykket.1 Ta hensyn til notasjonen ovenfor, med tanke på at resultatet av arbeidet

1 Bruken av begrepet "beregning" betyr ikke at programmet bare kan operere med tall; Resultatet av beregningen kan være strenger, lister og generelt alle datastrukturer som er tillatt i språket.

imperativt program er fullstendig og unikt bestemt av dets input, kan vi si at slutttilstanden (eller et hvilket som helst mellomliggende) er en funksjon (i matematisk forstand) av starttilstanden, dvs. σ0 = f(σ). Funksjonell programmering bruker dette synspunktet: programmet er et uttrykk som tilsvarer funksjonen f. Funksjonelle programmeringsspråk støtter konstruksjonen av slike uttrykk, jeg tilbyr bredt velge tilsvarende språkkonstruksjoner.

Når du sammenligner de funksjonelle og imperative tilnærmingene til programmering, kan du legge merke til følgende egenskaper til funksjonelle programmer:

Funksjonelle programmer bruker ikke variabler i den forstand at ordet brukes i imperativ programmering. Spesielt funksjonelle programmer bruker ikke oppdragsoperatøren.

Som en konsekvens av forrige punkt er det ingen løkker i funksjonelle programmer.

Å utføre en sekvens av kommandoer i et funksjonelt program er meningsløst fordi en kommando ikke kan påvirke utførelsen av den neste.

Funksjonelle programmer bruker funksjoner på mye mer intrikate måter. Funksjoner kan sendes til andre funksjoner som argumenter og returneres som et resultat, og til og med generelt utføre beregninger som resulterer i en funksjon.

I stedet for løkker, bruker funksjonelle programmer i stor grad rekursive funksjoner.

Ved første øyekast kan den funksjonelle tilnærmingen til programmering virke merkelig, uvanlig og til liten nytte, men følgende hensyn må tas i betraktning.

Først av alt, den imperative stilen i programmering er ikke en hardkodet nødvendighet. Mange av egenskapene til imperative programmeringsspråk er resultatet av abstraksjon fra dataimplementeringsdetaljer på lavt nivå, fra maskinkode til monteringsspråk til språk som Fortran, og så videre. Det er imidlertid ingen grunn til å tro at slike språk reflekterer det mest naturlige språket

en måte for et menneske å kommunisere sine intensjoner til en maskin. Kanskje en mer korrekt tilnærming er at programmeringsspråk blir født som abstrakte systemer for å skrive algoritmer, og deretter blir de oversatt til imperativt dataspråk.

Videre har den funksjonelle tilnærmingen en rekke fordeler fremfor den imperative. For det første korresponderer funksjonelle programmer mer direkte til matematiske objekter, og tillater derfor strenge resonnementer. Still inn verdien av imperativprogrammet, dvs. funksjonen den implementerer kan være ganske vanskelig å evaluere. Derimot kan betydningen av et funksjonsprogram utledes nesten direkte.

Tenk for eksempel neste program i Haskell:

faktoriell n = hvis n == 0 så 1 ellers n * faktoriell (n - 1)

Du kan nesten umiddelbart se at dette programmet tilsvarer følgende delfunksjon:

f(n) = n! n ≥ 0

(Her betyr symbolet at funksjonen er udefinert, siden programmet ikke avsluttes for negative verdier av argumentet.) For et C-program er imidlertid ikke denne korrespondansen åpenbar:

int x = 1; mens (n > 0)

x = x * n; n = n - 1;

En merknad bør også gjøres om bruken av begrepet "funksjon" på språk som C, Java, etc. I matematisk forstand er C-språk "funksjoner" ikke funksjoner fordi:

Betydningen deres kan avhenge av mer enn bare argumentene;

Resultatet av implementeringen av dem kan være forskjelligebivirkninger(for eksempel endre verdiene til globale variabler)

To kall til samme funksjon med de samme argumentene kan gi forskjellige resultater.

Samtidig er funksjoner i funksjonelle programmer faktisk funksjoner i den forstand dette forstås i matematikk. Følgelig gjelder ikke kommentarene ovenfor dem. Det følger at evalueringen av ethvert uttrykk ikke kan ha noen bivirkninger, og derfor påvirker ikke rekkefølgen som underuttrykkene vurderes i resultatet. Dermed kan funksjonelle programmer lett parallelliseres fordi individuelle komponenter av uttrykk kan evalueres samtidig.

2 Grunnleggende om lambdaregning

Akkurat som Turing maskinteori er grunnlaget for imperative programmeringsspråk, tjener lambda-kalkulus som grunnlaget og det matematiske "fundamentet" som alle funksjonelle programmeringsspråk er basert på.

Lambdakalkulus ble oppfunnet på begynnelsen av 1930-tallet av logikeren A. Church, som håpet å bruke den som en formalisme for å rettferdiggjøre matematikk. Snart ble det oppdaget problemer som gjorde det umulig å bruke det i denne egenskapen (nå er det grunn til å tro at dette ikke er helt sant) og lambda-kalkulus forble som en av måtene å formalisere konseptet med en algoritme.

For tiden er lambda-kalkulus den viktigste formaliseringen som brukes i forskning relatert til programmeringsspråk. Dette skyldes sannsynligvis følgende faktorer:

Dette er den eneste formaliseringen som, selv om det medfører noen ulemper, faktisk kan brukes direkte til å skrive programmer.

Lambdaberegning gir en enkel og naturlig modell for viktige konsepter som rekursjon og nestede miljøer.

De fleste konstruksjoner i tradisjonelle programmeringsspråk kan mer eller mindre direkte kartlegges til en konstruksjon lambda-regning.

Funksjonelle språk er i utgangspunktet en praktisk form for syntaktisk notasjon for konstruksjoner av ulike varianter av lambda-kalkulus. Noen moderne språk (Haskell, Clean) har

100 % samsvar med semantikken til semantikken til de implisitte konstruksjonene til lambda-kalkulus.

I matematikk, når det er nødvendig å snakke om en funksjon, er det vanlig å gi denne funksjonen et navn og deretter bruke den, som for eksempel i følgende uttalelse:

La f: R → R defineres med følgende uttrykk:

	(x2 sin(1/x2 ),

Da er ikke f0 (x) integrerbar på intervallet .

Mange programmeringsspråk lar også funksjoner defineres bare ved å tildele noen navn til dem. For eksempel, i C-språket, må en funksjon alltid ha et navn. Dette virker naturlig, men siden funksjoner brukes overalt i funksjonell programmering, kan denne tilnærmingen føre til alvorlige problemer. Tenk deg at vi alltid må operere med aritmetiske uttrykk i lignende stil:

La x = 2 og y = 4. Da er xx = y.

Lambda-notasjon lar deg definere funksjoner med samme letthet som andre matematiske objekter. Lambda uttrykk vi vil kalle en konstruksjon av skjemaet

der E er et uttrykk, muligens ved å bruke variabelen x.

Eksempel. λx.x2 er en funksjon som kvadrerer argumentet.

Ved å bruke lambda-notasjon kan vi tydelig skille tilfeller når vi med et uttrykk på formen f(x) mener funksjonen f selv og dens verdi i punkt x. I tillegg lar lambda-notasjon deg formalisere nesten alle typer matematisk notasjon. Hvis du starter med konstanter og variabler og bygger uttrykk med kun lambda-uttrykk og funksjonsapplikasjoner på argumenter, kan du tenke deg svært komplekse matematiske uttrykk.

Vi vil betegne bruken av funksjonen f på argumentet x som f x, dvs. i motsetning til det som er vanlig i matematikk, vil vi ikke bruke parentes2. Av grunner som vil bli tydelige senere, vil vi anta at å bruke en funksjon på et argument blir stående assosiativt, dvs. f x y

2 Merk at i matematikk skrives uttrykk som sin x uten parentes.

betyr (f(x))(y). Som en forkortelse for uttrykk på formen λx.λy.E, vil vi bruke notasjonen λx y.E (tilsvarende for et større antall argumenter). Vi vil også anta at «omfanget» av lambda-uttrykket strekker seg så langt til høyre som mulig, dvs. for eksempel betyr λx.x y λx.(x y), og ikke (λx.x)y.

Ved første øyekast ser det ut til at vi må innføre en spesiell notasjon for funksjoner av flere argumenter. Imidlertid er det en curry-operasjon 3 som lar deg skrive slike funksjoner i vanlig lambda-notasjon. Tanken er å bruke uttrykk på formen λx y.x + y. Et slikt uttrykk kan betraktes som en funksjon R → (R → R), dvs. hvis brukt på ett argument, er resultatet en funksjon som deretter tar et annet argument. Dermed:

(λx y.x + y) 1 2 = (λy.1 + y) 2 = 1 + 2.

Variabler i lambda-uttrykk kan være frie eller bundne. I et uttrykk på formen x2 + x er variabelen x fri; verdien avhenger av verdien av variabelen x, og generelt kan den ikke være det

Hvis du endrer notasjonen j, vil ikke betydningen av uttrykket endres.

Det skal forstås at i ethvert underuttrykk kan en variabel være fri (som i uttrykket under integralet), men i hele uttrykket er den bundet av noen variabel bindingsoperasjon, for eksempel summeringsoperasjonen. Den delen av uttrykket som er "inne" i bindingsoperasjonen kalles omfang variabel.

I lambda-regning regnes uttrykkene λx.E[x] og λy.E[y] som ekvivalente (dette kalles α-ekvivalens, og prosessen med å konvertere mellom slike par kalles α-transformasjon). Selvfølgelig er det nødvendig å stille betingelsen om at y ikke er en fri variabel i E[x].

3 fra etternavnet til den berømte logikeren Haskell Curry, etter hvem Haskell-programmeringsspråket er oppkalt

3 Lambdaberegning som et formelt system

Lambda-kalkulus er basert på den formelle notasjonen av et lambda-ledd, sammensatt av variabler og noen faste sett med konstanter ved å bruke operasjonen til funksjonsapplikasjon og lambdaabstraksjon. Dette betyr at alle lambda-uttrykk kan deles inn i fire kategorier:

1. Variabler: er utpekt av vilkårlige strenger som består av bokstaver og tall.

2. Konstanter: også angitt med strenger; vi vil bestemme forskjellen fra variabler fra konteksten.

3. Kombinasjoner: , dvs. å bruke funksjon S på argument T; og S og T kan være vilkårlige lambda-uttrykk. Kombinasjonen er skrevet som S T.

4. Abstraksjoner av et vilkårlig lambdaledd S med hensyn til variabelen x, betegnet som λx.S.

Dermed er lambda-begrepet definert rekursivt og grammatikken kan defineres som følgende Backus-Naur-form:

Exp = Var| Konst| Exp Exp| λVar. Exp

I følge denne grammatikken er lambda-termer representert som syntakstrær i stedet for som sekvenser av tegn. Det følger at avtaler om assosiativiteten til operasjonen med å bruke en funksjon, ekvivalensen av uttrykk av formen λx y.S og λx.λy.S, tvetydighet i navnene til konstanter og variabler stammer bare fra behovet for å representere lambda-termer i en form som er praktisk for mennesker, og er ikke en del av det formelle systemet.

3.1 Frie og bundne variabler

I I denne delen formaliserer vi den tidligere gitte intuitive ideen om frie og bundne variabler. Mange gratis

variabler F V (S) lambda-leddet S kan defineres rekursivt som følger:

På samme måte er settet med relaterte variabler BV (S) definert av følgende formler:

BV(x) =

BV(c) =

BV (S T) = BV (S) BV (T)

BV(λx.S) = BV(S)(x)

Her antas det at c er en konstant.

Eksempel. For begrepet S = (λx y.x) (λx.z x) kan det vises at F V (S) = (z) og

BV(S) = (x, y).

3.2 Bytter

Intuitivt, å bruke begrepet λx.S som en funksjon på et argument T resulterer i et begrep S der alle frie forekomster av x er erstattet med T . Overraskende nok er det ikke lett å formalisere denne intuisjonen.

Vi vil betegne operasjonen med å erstatte et ledd S med en variabel x i et annet ledd T som T. Akkurat som i definisjonen av frie og bundne variabler, kan også substitusjonsregler defineres rekursivt. Vanskeligheten er at det er nødvendig å pålegge ytterligere restriksjoner, slik at du kan unngå konflikter i variabelnavn.

3.3 Konvertering

Lambdakalkulus er basert på tre konverteringsoperasjoner som lar deg gå fra ett ledd til et annet som tilsvarer det. I følge etablert tradisjon er disse konverteringene betegnet med de greske bokstavene α, β og η. De er definert som følger:

α-konvertering: λx.S −→ λy.S forutsatt at y / F V (S).

For eksempel, λu.u v −→ λw.w u.

β-konvertering: (λx.S) T −→ S.

β-konverteringen er viktigst for oss, siden den tilsvarer å beregne verdien av en funksjon av et argument. α-konvertering er en hjelpemekanisme for å endre navn på bundne variabler, og η-konvertering er hovedsakelig av interesse når man vurderer lambda-kalkulus fra et logisk snarere enn et programmeringssynspunkt.

3.4 Likestilling av lambdavilkår

Ved å bruke de introduserte konverteringsreglene kan vi formelt definere begrepet likhet mellom lambda-vilkår. To ledd er like hvis man kan gå fra det ene til det andre ved hjelp av en endelig sekvens av konverteringer. La oss definere likhetsbegrepet med følgende uttrykk, der horisontale linjer skal forstås som "hvis utsagnet over linjen er tilfredsstilt, så er utsagnet også sant

under den":

Det er nødvendig å skille begrepet likhet, definert av disse formlene, fra begrepet syntaktisk ekvivalens, som vi vil betegne med det spesielle symbolet ≡. For eksempel, λx.x 6≡λy.y, men λx.x = λy.y. Det er ofte mulig å vurdere den syntaktiske ekvivalensen av ledd opp til α-konverteringer. Vi vil betegne slik ekvivalens med symbolet ≡α. Denne relasjonen er definert på samme måte som likheten av lambda-termer, med unntak av at av alle konverteringer er det bare α-konverteringer som er tillatt. Således er λx.x ≡α λy.y.

3.5 Utvidelse

η-konvertering i lambdaregning uttrykker prinsippet utvidelsesevne. I en generell filosofisk forstand sies to egenskaper å være ekstensjonsmessig ekvivalente hvis de tilhører nøyaktig de samme objektene. I matematikk er det for eksempel tatt i bruk et utvidelsessyn på mengder, dvs. to sett anses som like hvis de inneholder de samme elementene. På samme måte sier vi at to funksjoner er like hvis de har samme domene, og for alle verdier av argumentet i det domenet beregner de det samme resultatet.