Inom datavetenskap utgör konstruktioner futureoch i vissa programmeringsspråk den utvärderingsstrategi sompromise används för parallell beräkning . Med deras hjälp beskrivs ett objekt som kan nås för ett resultat, vars beräkning kanske inte är klar för tillfället. delay
Termen löfte myntades 1976 av Daniel Friedman och David Wise [1] och Peter Hibbard kallade det eventual . [2] Ett liknande koncept som kallas framtiden föreslogs i ett papper från 1977 av Henry Baker och Carl Hewitt. [3]
Termerna framtid , löfte och fördröjning används ganska ofta omväxlande, men skillnaden mellan framtid och löfte beskrivs nedan . Future är vanligtvis en skrivskyddad representation av en variabel, medan löfte är en föränderlig enstaka tilldelningsbehållare som passerar värdet av framtiden . [4] En framtid kan definieras utan att specificera vilket löfte värdet kommer ifrån. Dessutom kan flera löften associeras med en enda framtid , men bara ett löfte kan tilldela ett värde till en framtid. Annars skapas framtid och löfte tillsammans och bundna till varandra: framtid är ett värde, och löfte är en funktion som tilldelar ett värde. I praktiken är framtid returvärdet för en asynkron löftesfunktion . Processen att tilldela ett framtida värde kallas att lösa , uppfylla eller binda .
Vissa källor på ryska använder följande översättningar av termer: för framtida - framtida resultat [5] , terminer [6] [7] [8] ; för löfte, ett löfte [9] [5] ; för fördröjning — fördröjning.
Det bör noteras att oräkneliga (" framtida ") och två ord (" framtida värde ") översättningar har mycket begränsad tillämplighet (se diskussion ). Speciellt Alice ML-språket tillhandahåller futuresförstklassiga egenskaper, inklusive tillhandahållande futures av förstklassiga ML-moduler - future modulesoch future type modules[10] - och alla dessa termer visar sig vara oöversättbara med dessa varianter. En möjlig översättning av termen i detta fall visar sig vara " framtid " - respektive, vilket ger en grupp termer " förstklassiga terminer ", " terminer på modulnivå ", " framtidsstrukturer " och " framtidssignaturer ". En fri översättning av " perspektiv " är möjlig, med motsvarande terminologiska intervall.
Användningen av framtiden kan vara implicit (alla referenser till framtiden returnerar en referens till värdet) eller explicit (användaren måste anropa en funktion för att få värdet). Ett exempel är get -metoden för en klass java.util.concurrent.Futurei Java-språket . Att få ett värde från en explicit framtid kallas stinging eller forcering . Explicita framtider kan implementeras som ett bibliotek, medan implicita framtider vanligtvis implementeras som en del av språket.
Baker och Hewitts artikel beskriver implicita framtider, som naturligt stöds i skådespelarens beräkningsmodell och rent objektorienterade språk som Smalltalk . Friedman och Wises artikel beskriver endast explicita framtider, troligen på grund av svårigheten att implementera implicita framtider på konventionella datorer. Svårigheten ligger i att det på hårdvarunivå inte kommer att vara möjligt att arbeta med framtiden som en primitiv datatyp som heltal. Till exempel, att använda append-satsen kommer inte att kunna bearbeta 3 + future factorial(100000) . I rent objektspråk och språk som stöder aktörsmodellen kan detta problem lösas genom att skicka det framtida factorial(100000) +[3] -meddelandet , där framtiden kommer att bli tillsagd att lägga till 3 och returnera resultatet. Det är värt att notera att tillvägagångssättet för meddelandeförmedling fungerar oavsett hur lång tid factorial(100000) tar att beräkna, och kräver inte stickning eller forcering.
När du använder framtiden minskar förseningarna i distribuerade system avsevärt . Till exempel, genom att använda terminer, kan du skapa en pipeline från löfte [11] [12] , som är implementerad i språk som E och Joule , såväl som i Argus som kallas call-stream .
Överväg ett uttryck som använder traditionella fjärranrop :
t3 := ( xa() ).c( yb() )som kan avslöjas som
t1 := xa(); t2 := yb(); t3:= tl.c(t2);I varje uttalande måste du först skicka ett meddelande och få ett svar på det innan du fortsätter med nästa. Låt oss anta att x , y , t1 och t2 finns på samma fjärrmaskin. I det här fallet, för att slutföra det tredje påståendet, måste du först utföra två överföringar av data över nätverket. Sedan kommer den tredje satsen att utföra ytterligare en dataöverföring till samma fjärrmaskin.
Detta uttryck kan skrivas om med hjälp av framtid
t3 := (x <- a()) <- c(y <- b())och avslöjas som
tl := x <- a(); t2:= y <- b(); t3:= tl <-c(t2);Detta använder syntax från E-språket, där x <- a() betyder "asynkront vidarebefordra meddelande a() till x ". Alla tre variablerna blir framtida och programexekveringen fortsätter. Senare, när man försöker få värdet på t3 , kan det bli en fördröjning; Användning av en pipeline kan dock minska detta. Om, som i föregående exempel, x , y , t1 och t2 är placerade på samma fjärrmaskin, är det möjligt att implementera beräkningen av t3 med hjälp av en pipeline och en dataöverföring över nätverket. Eftersom alla tre meddelanden är för variabler som finns på samma fjärrdator behöver du bara utföra en begäran och få ett svar för att få resultatet. Observera att överföringen t1 <- c(t2) inte blockeras även om t1 och t2 var på olika maskiner från varandra eller från x och y .
Att använda en pipeline från ett löfte bör särskiljas från att skicka ett meddelande parallellt asynkront. På system som stöder parallell meddelandeöverföring men som inte stöder pipelines, kan sändning av meddelandena x <- a() och y <- b() från exemplet göras parallellt, men att skicka t1 <- c(t2) måste vänta tills t1 tas emot och t2 , även om x , y , t1 och t2 är på samma fjärrmaskin. Latensfördelen med att använda en pipeline blir mer betydande i komplexa situationer där flera meddelanden måste skickas.
Det är viktigt att inte blanda ihop löftespipeline med meddelandepipeline i aktörssystem, där det är möjligt för en aktör att specificera och börja exekvera beteende för nästa meddelande innan det föregående har avslutat behandlingen.
I vissa programmeringsspråk, som Oz , E och AmbientTalk , är det möjligt att få en oföränderlig representation av framtiden som låter dig få dess värde efter upplösning, men som inte tillåter dig att lösa:
Stöd för oföränderliga representationer är förenligt med principen om minsta privilegium , eftersom tillgång till ett värde endast kan ges till de objekt som behöver det. I system som stöder pipelines får avsändaren av ett asynkront meddelande (med ett resultat) ett oföränderligt löfte om resultatet, och mottagaren av meddelandet är en resolver.
På vissa språk, som Alice ML , är terminer knutna till en specifik tråd som utvärderar ett värde. Utvärderingen kan starta omedelbart när framtiden skapas, eller lat , d.v.s. efter behov. En "lat" framtid är som en thunk (när det gäller lat utvärdering).
Alice ML stöder även terminer, som kan lösas av vilken tråd som helst, och det kallas också för ett löfte där . [14] Det är värt att notera att i det här sammanhanget betyder löfte inte detsamma som E-exemplet ovan : Alices löfte är inte en oföränderlig representation, och Alice stöder inte piping från löften. Men pipelines fungerar naturligtvis med terminer (inklusive de som är bundna till löften).
Om ett framtida värde nås asynkront, till exempel genom att skicka ett meddelande till det eller vänta med hjälp av en konstruktion wheni E, är det inte svårt att vänta på att framtiden ska lösas innan meddelandet tas emot. Detta är det enda att tänka på i rent asynkrona system, som språk med skådespelaremodell.
På vissa system är det dock möjligt att komma åt det framtida värdet omedelbart och synkront . Detta kan uppnås på följande sätt:
Det första sättet är till exempel implementerat i C++11 , där tråden som du vill få det framtida värdet i kan blockera tills medlemmen fungerar wait()eller get(). Med wait_for()eller wait_until()kan du uttryckligen ange en timeout för att undvika evig blockering. Om framtiden erhålls som ett resultat av att exekvera std::async, då med en blockerande väntan (ingen timeout) på den väntande tråden, kan resultatet av exekvering av funktionen tas emot synkront.
En I-variabel (på Id- språk ) är en framtid med den blockerande semantiken som beskrivs ovan. I-struktur är en datastruktur som består av I-variabler. En liknande konstruktion som används för synkronisering, där ett värde kan tilldelas flera gånger, kallas en M-variabel . M-variabler stöder atomoperationer för att hämta och skriva värdet på en variabel, där att få värdet returnerar M-variabeln till ett tomt tillstånd. [17]
Den parallella booleska variabeln liknar framtiden, men uppdateras under unifiering på samma sätt som booleska variabler i logisk programmering . Därför kan det associeras med mer än ett enhetligt värde (men kan inte återgå till ett tomt eller olöst tillstånd). Trådvariabler i Oz fungerar som samtidiga booleska variabler med den blockerande semantiken som beskrivs ovan.
Begränsad parallell variabel är en generalisering av parallella booleska variabler med stöd för begränsad logisk programmering : en begränsning kan begränsa uppsättningen av tillåtna värden flera gånger. Det finns vanligtvis ett sätt att specificera en thunk som kommer att exekveras vid varje avsmalning; detta är nödvändigt för att stödja spridning av restriktioner .
Kraftigt beräknade trådspecifika terminer kan implementeras direkt i termer av icke-trådspecifika terminer genom att skapa en tråd för att utvärdera värdet vid den tidpunkt då framtiden skapas. I det här fallet är det önskvärt att returnera en skrivskyddad vy till klienten, så att endast den skapade tråden kan exekvera framtiden.
Att implementera implicita lata trådspecifika futures (som i Alice ML) i termer av icke-trådspecifika futures kräver en mekanism för att bestämma den första användningspunkten för ett framtida värde (som WaitNeeded- konstruktionen i Oz [18] ). Om alla värden är objekt, är det tillräckligt att implementera transparenta objekt för att vidarebefordra värdet, eftersom det första meddelandet till vidarebefordranobjektet kommer att indikera att framtidens värde måste utvärderas.
Icke-trådspecifika terminer kan implementeras via trådspecifika terminer, förutsatt att systemet stöder meddelandeöverföring. En tråd som kräver ett framtida värde kan skicka ett meddelande till den framtida tråden. Detta tillvägagångssätt introducerar dock överflödig komplexitet. I trådbaserade programmeringsspråk är det mest uttrycksfulla tillvägagångssättet förmodligen en kombination av icke-trådspecifika framtider, skrivskyddade vyer och antingen 'WaitNeeded'-konstruktionen eller stöd för transparent vidarebefordran.
Utvärderingsstrategin " call by future " är icke-deterministisk: framtidens värde kommer att utvärderas någon gång efter skapandet, men före användning. Utvärdering kan starta omedelbart efter skapandet av framtiden (" ivriga utvärdering "), eller bara i det ögonblick då värdet behövs ( lat utvärdering , uppskjuten utvärdering). När resultatet av framtiden väl har utvärderats, räknas inte efterföljande samtal om. Således ger framtiden både samtal efter behov och memoisering .
Lazy future- konceptet tillhandahåller deterministisk lazy evaluation-semantik: utvärderingen av det framtida värdet börjar första gången värdet används, som i metoden "call by need". Lata terminer är användbara i programmeringsspråk som inte ger lat utvärdering. Till exempel i C++11 kan en liknande konstruktion skapas genom att specificera en startpolicy std::launch::syncför std::asyncoch skicka in en funktion som utvärderar värdet.
''future'' <Expression>I Actor-modellen definieras ett uttryck av formen som ett svar på ett Eval- meddelande i miljö E för konsument C , enligt följande: Ett framtida uttryck svarar på ett Eval- meddelande genom att skicka konsument C den nyskapade aktör F (en proxy för svaret med utvärdering <Expression>) som returvärde, samtidigt som uttrycket Eval<Expression> meddelanden skickas i miljö E för konsument C . Beteendet hos F definieras så här:
Vissa framtida implementeringar kan hantera förfrågningar annorlunda för att öka graden av parallellitet. Till exempel kan uttrycket 1 + framtida faktorial(n) skapa en ny framtid som beter sig som talet 1+faktor(n) .
Framtids- och löfteskonstruktionerna implementerades först i programmeringsspråken MultiLisp och Act 1 . Användningen av booleska variabler för interaktion i samtidiga logiska programmeringsspråk är ganska lik framtiden. Bland dem är Prolog med Freeze och IC Prolog , en fullfjädrad konkurrenskraftig primitiv har implementerats av Relational Language , Concurrent Prolog , Guarded Horn Clauses (GHC), Parlog , Strand , Vulcan , Janus , Mozart / Oz , Flow Java och Alice ML . Enstaka I-var- tilldelningar från dataflödesprogrammeringsspråk , ursprungligen introducerade i Id och inkluderade i Reppy Concurrent ML , liknar samtidiga booleska variabler.
En löftesteknik för pipeline som använder terminer för att övervinna förseningar föreslogs av Barbara Liskov och Liuba Shrira 1988 [19] , och oberoende av Mark S. Miller , Dean Tribble och Rob Jellinghaus som en del av Project Xanadu runt 1989 [20] .
Termen löfte myntades av Liskov och Shrira, även om de kallade pipelinemekanismen call-stream (används nu sällan).
I båda verken, och i Xanadus implementering av löftespipelinen, var löften inte förstklassiga objekt : funktionsargument och returvärden kunde inte vara löften direkt (vilket komplicerar implementeringen av pipelinen, till exempel i Xanadu). löfte och samtalsström implementerades inte i offentliga versioner av Argus [21] (programmeringsspråket som används i Liskovs och Shriras arbeten); Argus upphörde med utvecklingen 1988. [22] Implementeringen av pipeline i Xanadu blev tillgänglig först med releasen av Udanax Gold [23] 1999, och förklaras inte i den publicerade dokumentationen. [24]
Promise-implementationer i Joule och E stöder dem som förstklassiga objekt.
Flera tidiga Actor-språk, inklusive Act-språken, [25] [26] stödde parallell meddelandeöverföring och meddelandepipelining, men inte löftespipelinen. (Trots möjligheten att implementera löftespipelinen via konstruktioner som stöds, finns det inga bevis för sådana implementeringar på lagens språk.)
Konceptet Future kan implementeras i termer av kanaler : en framtid är en singelkanal, och ett löfte är en process som skickar ett värde till en kanal genom att exekvera framtiden [27] . Så här implementeras terminer i samtidiga kanalaktiverade språk som CSP och Go . Framtiden de implementerar är explicita eftersom de nås genom att läsa från en kanal, inte genom normal uttrycksutvärdering.