I datalogi danner konstruktioner futureog promisei delaynogle programmeringssprog den evalueringsstrategi, der bruges til parallel computing . Med deres hjælp beskrives et objekt, der kan tilgås for et resultat, hvis beregning muligvis ikke er afsluttet i øjeblikket.
Udtrykket løfte blev opfundet i 1976 af Daniel Friedman og David Wise [1] og Peter Hibbard kaldte det eventuel . [2] Et lignende koncept kaldet fremtiden blev foreslået i et papir fra 1977 af Henry Baker og Carl Hewitt. [3]
Begreberne fremtid , løfte og forsinkelse bruges ret ofte i flæng, men forskellen mellem fremtid og løfte er beskrevet nedenfor . Fremtid er normalt en skrivebeskyttet repræsentation af en variabel, mens løfte er en foranderlig enkelt-tildelingsbeholder , der passerer værdien af fremtiden . [4] En fremtid kan defineres uden at specificere, hvilket løfte værdien kommer fra. Flere løfter kan også knyttes til en enkelt fremtid , men kun ét løfte kan tildele en fremtid en værdi. Ellers skabes fremtid og løfte sammen og bundet til hinanden: fremtid er en værdi, og løfte er en funktion, der tildeler en værdi. I praksis er fremtid returværdien af en asynkron løftefunktion . Processen med at tildele en fremtidig værdi kaldes løsning , opfyldelse eller binding .
Nogle kilder på russisk bruger følgende oversættelser af termer: for fremtidige - fremtidige resultater [5] , futures [6] [7] [8] ; for løfte, et løfte [9] [5] ; for delay — delay.
Det skal bemærkes, at utallige (" fremtidige ") og to-ords (" fremtidig værdi ") oversættelser har meget begrænset anvendelighed (se diskussion ). Især Alice ML-sproget giver futuresførsteklasses egenskaber, herunder at levere futures førsteklasses ML-moduler - future modulesog future type modules[10] - og alle disse termer viser sig at være uoversættelige ved brug af disse varianter. En mulig oversættelse af begrebet i dette tilfælde viser sig at være " fremtidig " - henholdsvis, hvilket giver en gruppe af begreber " førsteklasses futures ", " modul-level futures ", " fremtidige strukturer " og " fremtidige signaturer ". En fri oversættelse af " perspektiv " er mulig med det tilsvarende terminologiske område.
Brugen af fremtiden kan være implicit (enhver reference til fremtiden returnerer en reference til værdien) eller eksplicit (brugeren skal kalde en funktion for at få værdien). Et eksempel er get -metoden for en klasse java.util.concurrent.Futurei Java-sproget . At få en værdi fra en eksplicit fremtid kaldes at stikke eller tvinge . Eksplicitte futures kan implementeres som et bibliotek, mens implicitte futures normalt implementeres som en del af sproget.
Baker og Hewitts artikel beskriver implicitte fremtider, som naturligt understøttes i skuespillerberegningsmodellen og rent objektorienterede sprog som Smalltalk . Friedman og Wises artikel beskriver kun eksplicitte futures, højst sandsynligt på grund af vanskeligheden ved at implementere implicitte futures på konventionelle computere. Vanskeligheden ligger i, at det på hardwareniveau ikke vil være muligt at arbejde med fremtiden som en primitiv datatype som heltal. For eksempel vil brug af append-sætningen ikke være i stand til at behandle 3 + future factorial(100000) . I rent objektsprog og sprog, der understøtter aktørmodellen, kan dette problem løses ved at sende den fremtidige factorial(100000) +[3] besked , hvor fremtiden vil blive bedt om at tilføje 3 og returnere resultatet. Det er værd at bemærke, at tilgangen til at sende beskeder virker, uanset hvor lang tid factorial(100.000) tager at beregne, og den kræver ikke stikning eller forcering.
Ved brug af fremtiden reduceres forsinkelser i distribuerede systemer betydeligt . Ved at bruge futures kan du for eksempel oprette en pipeline fra løfte [11] [12] , som er implementeret på sprog som E og Joule , samt i Argus kaldet call-stream .
Overvej et udtryk, der bruger traditionelle fjernprocedurekald :
t3 := ( xa() ).c( yb() )som kan afsløres som
t1 := xa(); t2 := yb(); t3:= tl.c(t2);I hver erklæring skal du først sende en besked og modtage et svar på den, før du fortsætter med den næste. Lad os antage, at x , y , t1 og t2 er på den samme fjernmaskine. I dette tilfælde, for at fuldføre den tredje påstand, skal du først udføre to overførsler af data over netværket. Derefter vil den tredje sætning udføre en anden dataoverførsel til den samme fjernmaskine.
Dette udtryk kan omskrives ved hjælp af fremtid
t3 := (x <- a()) <- c(y <- b())og oplyses som
t1 := x <- a(); t2:= y <- b(); t3:= t1 <-c(t2);Dette bruger syntaks fra E-sproget, hvor x <- a() betyder "asynkront videresend meddelelse a() til x ". Alle tre variabler bliver fremtidige, og programudførelsen fortsætter. Senere, når man forsøger at få værdien af t3 , kan der være en forsinkelse; brug af en pipeline kan dog reducere dette. Hvis, som i det foregående eksempel, x , y , t1 og t2 er placeret på den samme fjernmaskine, så er det muligt at implementere beregningen af t3 ved hjælp af en pipeline og én dataoverførsel over netværket. Da alle tre beskeder er for variabler placeret på den samme fjernmaskine, behøver du kun at udføre én anmodning og få ét svar for at få resultatet. Bemærk, at overførslen t1 <- c(t2) ikke vil blokere, selvom t1 og t2 var på forskellige maskiner fra hinanden eller fra x og y .
Brug af en pipeline fra et løfte skal skelnes fra at sende en meddelelse parallelt asynkront. På systemer, der understøtter parallel meddelelsesoverførsel, men ikke understøtter pipelines, kan afsendelse af meddelelserne x <- a() og y <- b() fra eksemplet ske parallelt, men at sende t1 <- c(t2) skal vent indtil t1 er modtaget og t2 , selvom x , y , t1 og t2 er på den samme fjernmaskine. Latens-fordelen ved at bruge en pipeline bliver mere væsentlig i komplekse situationer, hvor der skal sendes flere beskeder.
Det er vigtigt ikke at forveksle løftepipeline med meddelelsespipeline i aktørsystemer, hvor det er muligt for en aktør at specificere og begynde at eksekvere adfærd for den næste meddelelse, før den forrige er færdigbehandlet.
I nogle programmeringssprog, såsom Oz , E og AmbientTalk , er det muligt at få en uforanderlig repræsentation af fremtiden, der giver dig mulighed for at få dens værdi efter opløsning, men som ikke tillader dig at løse:
Støtte til uforanderlige repræsentationer er i overensstemmelse med princippet om mindste privilegium , da adgang til en værdi kun kan gives til de objekter, der har brug for det. I systemer, der understøtter pipelines, modtager afsenderen af en asynkron meddelelse (med et resultat) et uforanderligt løfte om resultatet, og modtageren af meddelelsen er en resolver.
På nogle sprog, såsom Alice ML , er futures bundet til en specifik tråd, der evaluerer en værdi. Evaluering kan starte med det samme, når fremtiden skabes, eller dovent , dvs. efter behov. En "doven" fremtid er som en thunk (i form af doven evaluering).
Alice ML understøtter også futures, som kan løses af enhver tråd, og det kaldes også et løfte der . [14] Det er værd at bemærke, at i denne sammenhæng betyder løfte ikke det samme som E-eksemplet ovenfor : Alices løfte er ikke en uforanderlig repræsentation, og Alice understøtter ikke piping fra løfter. Men rørledninger arbejder naturligvis med futures (inklusive dem, der er bundet til løfter).
Hvis en fremtidig værdi tilgås asynkront, såsom ved at sende en besked til den eller vente ved hjælp af en konstruktion wheni E, så er det ikke svært at vente på, at fremtiden løser sig, før man modtager beskeden. Dette er den eneste ting at overveje i rent asynkrone systemer, såsom sprog med en skuespillermodel.
På nogle systemer er det dog muligt at få adgang til den fremtidige værdi med det samme og synkront . Dette kan opnås på følgende måder:
Den første måde er for eksempel implementeret i C++11 , hvor tråden, som du ønsker at få den fremtidige værdi i, kan blokere indtil medlemmet fungerer wait()eller get(). Ved hjælp af wait_for()eller wait_until()kan du udtrykkeligt angive en timeout for at undgå evig blokering. Hvis fremtiden opnås som et resultat af at udføre std::async, så med en blokerende ventetid (ingen timeout) på den ventende tråd, kan resultatet af udførelsen af funktionen modtages synkront.
En I-variabel (på Id -sprog ) er en fremtid med den blokerende semantik beskrevet ovenfor. I-struktur er en datastruktur bestående af I-variable. En lignende konstruktion, der bruges til synkronisering, hvor en værdi kan tildeles flere gange, kaldes en M-variabel . M-variable understøtter atomoperationer med at få og skrive værdien af en variabel, hvor at få værdien returnerer M-variablen til en tom tilstand. [17]
Den parallelle booleske variabel ligner fremtiden, men opdateres under forening på samme måde som booleske variabler i logisk programmering . Derfor kan den være forbundet med mere end én ensartet værdi (men kan ikke vende tilbage til en tom eller uafklaret tilstand). Trådvariabler i Oz fungerer som samtidige booleske variabler med den blokerende semantik beskrevet ovenfor.
Begrænset parallel variabel er en generalisering af parallelle booleske variable med understøttelse af begrænset logisk programmering : en begrænsning kan indsnævre sættet af tilladte værdier adskillige gange. Der er normalt en måde at specificere en thunk på, som vil blive udført ved hver indsnævring; dette er nødvendigt for at understøtte udbredelse af begrænsninger .
Stærkt beregnede trådspecifikke futures kan implementeres direkte i form af ikke-trådspecifikke futures ved at oprette en tråd for at evaluere værdien på det tidspunkt, fremtiden skabes. I dette tilfælde er det ønskeligt at returnere en skrivebeskyttet visning til klienten, så kun den oprettede tråd kan eksekvere fremtiden.
Implementering af implicitte dovne tråd-specifikke futures (såsom i Alice ML) i form af ikke-tråd-specifikke futures kræver en mekanisme til at bestemme det første brugspunkt for en fremtidig værdi (såsom WaitNeeded- konstruktionen i Oz [18] ). Hvis alle værdier er objekter, er det tilstrækkeligt at implementere transparente objekter for at videresende værdien, da den første besked til videresendelsesobjektet vil indikere, at fremtidens værdi skal evalueres.
Ikke-trådspecifikke futures kan implementeres via trådspecifikke futures, forudsat at systemet understøtter meddelelsesoverførsel. En tråd, der kræver en fremtidig værdi, kan sende en besked til den fremtidige tråd. Denne tilgang introducerer imidlertid overflødig kompleksitet. I trådbaserede programmeringssprog er den mest udtryksfulde tilgang sandsynligvis en kombination af ikke-trådspecifikke futures, skrivebeskyttede visninger og enten 'WaitNeeded'-konstruktionen eller understøttelse af gennemsigtig videresendelse.
" Call by future " evalueringsstrategien er ikke-deterministisk : fremtidens værdi vil blive evalueret på et tidspunkt efter oprettelsen, men før brug. Evaluering kan starte umiddelbart efter skabelsen af fremtiden (" ivrig evaluering "), eller kun i det øjeblik, hvor værdien er nødvendig ( doven evaluering , udskudt evaluering). Når først fremtidens resultat er blevet evalueret, genberegnes efterfølgende opkald ikke. Således giver fremtiden både call by need og memoization .
Lazy future - konceptet giver deterministisk doven evaluerings-semantik: evalueringen af den fremtidige værdi starter første gang værdien bruges, som i "call by need"-metoden. Lazy futures er nyttige i programmeringssprog, der ikke giver doven evaluering. For eksempel i C++11 kan en lignende konstruktion oprettes ved at specificere en startpolitik std::launch::syncfor std::asyncog sende en funktion ind, der evaluerer værdien.
I Actor-modellen er et udtryk for formen ''future'' <Expression>defineret som et svar på en Eval- meddelelse i miljø E for forbruger C , som følger: Et fremtidigt udtryk svarer på en Eval- meddelelse ved at sende forbruger C den nyoprettede aktør F (en proxy for svaret med evaluering <Expression>) som returværdi, samtidig med at udtrykket Eval<Expression> -beskeder sendes i miljø E for forbruger C . F : s adfærd defineres således:
Nogle implementeringer af fremtiden kan håndtere anmodninger anderledes for at øge graden af parallelitet. For eksempel kan udtrykket 1 + fremtidig faktoriel(n) skabe en ny fremtid, der opfører sig som tallet 1+faktor(n) .
Fremtids- og løftekonstruktionerne blev først implementeret i programmeringssprogene MultiLisp og Act 1 . Brugen af booleske variabler til interaktion i samtidige logiske programmeringssprog er ret lig fremtiden. Blandt dem er Prolog med Freeze og IC Prolog , en fuldgyldig konkurrenceprimitiv er blevet implementeret af Relational Language , Concurrent Prolog , Guarded Horn Clauses (GHC), Parlog , Strand , Vulcan , Janus , Mozart / Oz , Flow Java og Alice ML . Enkelte I-var- tildelinger fra dataflow - programmeringssprog , der oprindeligt blev introduceret i Id og inkluderet i Reppy Concurrent ML , ligner samtidige booleske variable.
En lovende pipeline-teknik, der bruger futures til at overvinde forsinkelser, blev foreslået af Barbara Liskov og Liuba Shrira i 1988 [19] , og uafhængigt af Mark S. Miller , Dean Tribble og Rob Jellinghaus som en del af Project Xanadu omkring 1989 [20] .
Udtrykket løfte blev opfundet af Liskov og Shrira, selvom de kaldte pipeline-mekanismen call-stream (nu sjældent brugt).
I begge værker og i Xanadus implementering af løftepipelinen var løfter ikke førsteklasses objekter : funktionsargumenter og returværdier kunne ikke være løfter direkte (hvilket komplicerer implementeringen af pipelinen, for eksempel i Xanadu). løfte og opkaldsstrøm blev ikke implementeret i offentlige versioner af Argus [21] (programmeringssproget brugt i Liskovs og Shriras arbejde); Argus stoppede udviklingen i 1988. [22] Implementeringen af pipeline i Xanadu blev først tilgængelig med udgivelsen af Udanax Gold [23] i 1999, og er ikke forklaret i den offentliggjorte dokumentation. [24]
Promise-implementeringer i Joule og E understøtter dem som førsteklasses objekter.
Adskillige tidlige skuespillersprog, herunder Act-sprogene, [25] [26] understøttede parallel meddelelsesoverførsel og meddelelsespipelining, men ikke løftepipelinen. (På trods af muligheden for at implementere løftepipelinen via understøttede konstruktioner, er der ingen beviser for sådanne implementeringer på lovsprog.)
Konceptet Future kan implementeres i form af kanaler : en fremtid er en singleton-kanal, og et løfte er en proces, der sender en værdi til en kanal ved at eksekvere fremtiden [27] . Sådan implementeres futures i samtidige kanalaktiverede sprog som CSP og Go . De futures, de implementerer, er eksplicitte, fordi de tilgås ved at læse fra en kanal, ikke ved normal udtryksevaluering.