În informaticăfuture , constructele promiseși delayîn unele limbaje de programare formează strategia de evaluare utilizată pentru calculul paralel . Cu ajutorul lor, este descris un obiect care poate fi accesat pentru un rezultat, al cărui calcul este posibil să nu fie finalizat momentan.
Termenul de promisiune a fost inventat în 1976 de Daniel Friedman și David Wise [1] și Peter Hibbard l-a numit eventual . [2] Un concept similar numit viitor a fost propus într-o lucrare din 1977 de Henry Baker și Carl Hewitt. [3]
Termenii viitor , promisiune și întârziere sunt adesea folosiți în mod interschimbabil, dar diferența dintre viitor și promisiune este descrisă mai jos . Viitorul este de obicei o reprezentare numai în citire a unei variabile, în timp ce promisiunea este un container cu o singură atribuire mutabil care trece valoarea viitorului . [4] Un viitor poate fi definit fără a specifica din ce promisiune va veni valoarea. De asemenea , mai multe promisiuni pot fi asociate unui singur viitor , dar o singură promisiune poate atribui o valoare unui viitor. În caz contrar, viitorul și promisiunea sunt create împreună și legate unul de celălalt: viitorul este o valoare, iar promisiunea este o funcție care atribuie o valoare. În practică, viitorul este valoarea de returnare a unei funcții de promisiune asincrone . Procesul de atribuire a unei valori viitoare se numește rezolvare , îndeplinire sau legare .
Unele surse în limba rusă folosesc următoarele traduceri ale termenilor: pentru viitor - rezultate viitoare [5] , futures [6] [7] [8] ; pentru promisiune, o promisiune [9] [5] ; pentru întârziere — întârziere.
Trebuie remarcat faptul că traducerile nenumărate (" viitor ") și cu două cuvinte (" valoare viitoare ") au o aplicabilitate foarte limitată (vezi discuția ). În special, limbajul Alice ML oferă futuresproprietăți de primă clasă, inclusiv furnizarea de module ML futures de primă clasă - și [10] - și toți acești termeni se dovedesc a fi intraductibili folosind aceste variante. O posibilă traducere a termenului în acest caz se dovedește a fi „ viitor ” - respectiv, dând un grup de termeni „ future de primă clasă ” , „future la nivel de modul ”, „ structuri viitoare ” și „ semnături viitoare ”. Este posibilă o traducere gratuită a „ perspectivă ”, cu gama terminologică corespunzătoare. future modulesfuture type modules
Utilizarea viitorului poate fi implicită (orice referire la viitor returnează o referință la valoare) sau explicită (utilizatorul trebuie să apeleze o funcție pentru a obține valoarea). Un exemplu este metoda get a unei clase java.util.concurrent.Futureîn limbajul Java . Obținerea unei valori dintr-un viitor explicit se numește ustură sau forțare . Viitoarele explicite pot fi implementate ca o bibliotecă, în timp ce futures implicite sunt de obicei implementate ca parte a limbajului.
Articolul lui Baker și Hewitt descrie viitoarele implicite, care sunt susținute în mod natural în modelul de calcul al actorului și în limbaje pur orientate pe obiecte , cum ar fi Smalltalk . Articolul lui Friedman și Wise descrie doar futures explicite, cel mai probabil din cauza dificultății de a implementa futures implicite pe computerele convenționale. Dificultatea constă în faptul că la nivel hardware nu se va putea lucra cu viitorul ca tip de date primitive precum numerele întregi. De exemplu, utilizarea instrucțiunii append nu va putea procesa 3 + factorul viitor (100000) . În limbaje pur obiect și în limbaje care acceptă modelul actor, această problemă poate fi rezolvată prin trimiterea viitorului mesaj factorial(100000) +[3] , în care viitorului i se va spune să adauge 3 și să returneze rezultatul. Este demn de remarcat faptul că abordarea de transmitere a mesajelor funcționează indiferent de cât timp durează calculul factorial(100000) și nu necesită stingere sau forțare.
Când se utilizează viitor, întârzierile în sistemele distribuite sunt reduse semnificativ . De exemplu, folosind futures, puteți crea o conductă din promise [11] [12] , care este implementată în limbaje precum E și Joule , precum și în Argus numit call-stream .
Luați în considerare o expresie care utilizează apeluri tradiționale de procedură la distanță :
t3 := ( xa() ).c( yb() )care poate fi dezvăluit ca
t1 := xa(); t2 := yb(); t3 := t1.c(t2);În fiecare declarație, trebuie mai întâi să trimiteți un mesaj și să primiți un răspuns la acesta înainte de a continua cu următorul. Să presupunem că x , y , t1 și t2 sunt pe aceeași mașină la distanță. În acest caz, pentru a finaliza a treia afirmație, mai întâi trebuie să efectuați două transferuri de date prin rețea. Apoi, a treia declarație va efectua un alt transfer de date către aceeași mașină la distanță.
Această expresie poate fi rescrisă folosind viitor
t3 := (x <- a()) <- c(y <- b())și dezvăluite ca
t1 := x <- a(); t2 := y <- b(); t3 := t1 <- c(t2);Aceasta folosește sintaxa din limbajul E, unde x <- a() înseamnă „redirecționează asincron mesajul a() către x ”. Toate cele trei variabile devin viitoare, iar execuția programului continuă. Mai târziu, când încercați să obțineți valoarea lui t3 , ar putea exista o întârziere; cu toate acestea, utilizarea unei conducte poate reduce acest lucru. Dacă, ca în exemplul anterior, x , y , t1 și t2 sunt situate pe aceeași mașină la distanță, atunci este posibil să se implementeze calculul lui t3 folosind o conductă și un transfer de date prin rețea. Deoarece toate cele trei mesaje sunt pentru variabile situate pe aceeași mașină la distanță, trebuie să executați o singură cerere și să obțineți un răspuns pentru a obține rezultatul. Rețineți că transferul t1 <- c(t2) nu se va bloca chiar dacă t1 și t2 au fost pe mașini diferite unul de celălalt sau de la x și y .
Utilizarea unei conducte dintr-o promisiune ar trebui să fie distinsă de transmiterea unui mesaj în paralel în mod asincron. Pe sistemele care acceptă transmiterea paralelă a mesajelor, dar nu acceptă conducte, trimiterea mesajelor x <- a() și y <- b() din exemplu se poate face în paralel, dar trimiterea t1 <- c(t2) va trebui să așteptați până când t1 este primit și t2 , chiar dacă x , y , t1 și t2 sunt pe aceeași mașină la distanță. Avantajul latenței de utilizare a unei conducte devine mai semnificativ în situațiile complexe în care trebuie trimise mai multe mesaje.
Este important să nu confundați canalul de promisiuni cu canalul de mesaje în sistemele actor, unde este posibil ca un actor să specifice și să înceapă să execute comportamentul pentru următorul mesaj înainte ca cel anterior să se termine procesarea.
În unele limbaje de programare, cum ar fi Oz , E și AmbientTalk , este posibil să obțineți o reprezentare imuabilă a viitorului care vă permite să obțineți valoarea acestuia după rezolvare, dar nu vă permite să rezolvați:
Suportul pentru reprezentările imuabile este în concordanță cu principiul cel mai mic privilegiu , deoarece accesul la o valoare poate fi acordat doar acelor obiecte care au nevoie de ea. În sistemele care acceptă conducte, expeditorul unui mesaj asincron (cu un rezultat) primește o promisiune imuabilă a rezultatului, iar receptorul mesajului este un resolver.
În unele limbi, cum ar fi Alice ML , futures sunt legate de un anumit fir care evaluează o valoare. Evaluarea poate începe imediat când viitorul este creat, sau leneș , adică după cum este necesar. Un viitor „leneș” este ca un thunk (în termeni de evaluare leneșă).
Alice ML acceptă, de asemenea, futures, care pot fi rezolvate prin orice fir și se mai numește și o promisiune acolo . [14] Este demn de remarcat faptul că, în acest context, promisiunea nu înseamnă același lucru ca exemplul E de mai sus : promisiunea lui Alice nu este o reprezentare imuabilă, iar Alice nu acceptă pipingul din promisiuni. Dar conductele funcționează în mod natural cu futures (inclusiv cele legate de promisiuni).
Dacă o valoare viitoare este accesată asincron, cum ar fi transmiterea unui mesaj către aceasta sau așteptarea folosind un construct whenîn E, atunci nu este dificil să așteptați ca viitorul să se rezolve înainte de a primi mesajul. Acesta este singurul lucru de luat în considerare în sistemele pur asincrone, cum ar fi limbile cu model de actor.
Cu toate acestea, pe unele sisteme este posibil să accesați valoarea viitoare imediat și sincron . Acest lucru poate fi realizat în următoarele moduri:
Prima modalitate, de exemplu, este implementată în C++11 , unde firul în care doriți să obțineți valoarea viitoare se poate bloca până când membrul funcționează wait()sau get(). Folosind wait_for()sau wait_until(), puteți specifica în mod explicit un timeout pentru a evita blocarea veșnică. Dacă viitorul este obținut ca urmare a executării std::async, atunci cu o așteptare de blocare (fără timeout) pe firul de execuție, rezultatul executării funcției poate fi primit sincron.
O variabilă I (în limbajul Id ) este un viitor cu semantica de blocare descrisă mai sus. I-structura este o structură de date constând din I-variabile. O construcție similară utilizată pentru sincronizare, în care o valoare poate fi atribuită de mai multe ori, se numește variabilă M. Variabilele M suportă operații atomice de obținere și scriere a valorii unei variabile, unde obținerea valorii returnează variabila M într-o stare goală . [17]
Variabila booleană paralelă este similară cu viitorul, dar este actualizată în timpul unificării în același mod ca variabilele booleene din programarea logică . Prin urmare, poate fi asociat cu mai mult de o valoare uniformă (dar nu poate reveni la o stare goală sau nerezolvată). Variabilele thread din Oz funcționează ca variabile booleene concurente cu semantica de blocare descrisă mai sus.
Variabila paralelă constrânsă este o generalizare a variabilelor booleene paralele cu suport pentru programarea logică constrânsă : o constrângere poate restrânge setul de valori permise de câteva ori. De obicei, există o modalitate de a specifica un thunk care va fi executat la fiecare îngustare; acest lucru este necesar pentru a sprijini propagarea constrângerii .
Futururile foarte calculate specifice firului de execuție pot fi implementate direct în termeni de futures nespecifice firului de execuție prin crearea unui fir pentru a evalua valoarea în momentul creării viitorului. În acest caz, este de dorit să returnați clientului o vizualizare numai în citire, astfel încât numai firul creat să poată executa viitorul.
Implementarea futures implicite lazy-specific (cum ar fi în Alice ML) în termeni de futures non-thread-specific necesită un mecanism pentru a determina primul punct de utilizare al unei valori viitoare (cum ar fi constructul WaitNeeded în Oz [18] ). Dacă toate valorile sunt obiecte, atunci este suficient să implementați obiecte transparente pentru a redirecționa valoarea, deoarece primul mesaj către obiectul de redirecționare va indica faptul că valoarea viitorului trebuie evaluată.
Futururile non-specifice pentru fire pot fi implementate prin futures specifice pentru fire, presupunând că sistemul acceptă transmiterea mesajelor. Un fir care necesită o valoare viitoare poate trimite un mesaj către firul viitor. Cu toate acestea, această abordare introduce o complexitate redundantă. În limbajele de programare bazate pe fire, cea mai expresivă abordare este, probabil, o combinație de viitor non-specific, vizualizări numai pentru citire și fie constructul „WaitNeeded” sau suport pentru redirecționare transparentă.
Strategia de evaluare „ apel după viitor ” este nedeterministă: valoarea viitorului va fi evaluată la un moment dat după creare, dar înainte de utilizare. Evaluarea poate începe imediat după crearea viitorului (" eager evaluation "), sau numai în momentul în care este nevoie de valoare ( evaluare leneșă , evaluare amânată). Odată ce rezultatul viitorului a fost evaluat, apelurile ulterioare nu se recalculează. Astfel, viitorul oferă atât apelul după nevoie , cât și memorarea .
Conceptul de viitor leneș oferă o semantică deterministă a evaluării leneșe: evaluarea valorii viitoare începe prima dată când valoarea este utilizată, ca în metoda „apel după nevoie”. Lazy futures sunt utile în limbaje de programare care nu oferă o evaluare leneșă. De exemplu, în C++11 , o construcție similară poate fi creată prin specificarea unei politici std::launch::syncde lansare std::asyncși transmiterea unei funcții care evaluează valoarea.
În modelul Actor, o expresie a formei ''future'' <Expression>este definită ca răspuns la un mesaj Eval în mediul E pentru consumatorul C , după cum urmează: O expresie viitoare răspunde la un mesaj Eval trimițând consumatorului C actorul nou creat F (un proxy pentru răspunsul cu evaluare <Expression>) ca valoare returnată, în același timp cu trimiterea expresiei <Expression>mesaje Eval în mediul E pentru consumatorul C . Comportamentul lui F este definit astfel:
Unele implementări ale viitorului pot gestiona cererile diferit pentru a crește gradul de paralelism. De exemplu, expresia 1 + factorial(n) viitor poate crea un viitor nou care se comportă ca numărul 1+factorial(n) .
Construcțiile viitor și promisiuni au fost implementate pentru prima dată în limbajele de programare MultiLisp și Act 1 . Utilizarea variabilelor booleene pentru interacțiune în limbaje de programare logică concomitentă este destul de similară cu viitorul. Printre acestea se numără Prolog cu Freeze și IC Prolog , o primitivă competitivă cu drepturi depline a fost implementată de Relational Language , Concurrent Prolog , Guarded Horn Clauses (GHC), Parlog , Strand , Vulcan , Janus , Mozart / Oz , Flow Java și Alice ML . Atribuțiile unice I-var din limbaje de programare pentru flux de date , introduse inițial în Id și incluse în Reppy Concurrent ML , sunt similare cu variabilele booleene concurente.
O tehnică de promisiune care folosește futures pentru a depăși întârzierile a fost propusă de Barbara Liskov și Liuba Shrira în 1988 [19] , și independent de Mark S. Miller , Dean Tribble și Rob Jellinghaus ca parte a Proiectului Xanadu în jurul anului 1989 [20] .
Termenul de promisiune a fost inventat de Liskov și Shrira, deși au numit mecanismul conductei call-stream (folosit acum rar).
În ambele lucrări și în implementarea de către Xanadu a conductei de promisiuni, promisiunile nu erau obiecte de primă clasă : argumentele funcției și valorile returnate nu puteau fi promisiuni în mod direct (ceea ce complică implementarea conductei, de exemplu în Xanadu). promise și call-stream nu au fost implementate în versiunile publice ale lui Argus [21] (limbajul de programare folosit în lucrarea lui Liskov și Shrira); Argus și-a încetat dezvoltarea în 1988. [22] Implementarea conductei în Xanadu a devenit disponibilă doar odată cu lansarea Udanax Gold [23] în 1999 și nu este explicată în documentația publicată. [24]
Implementările Promise în Joule și E le susțin ca obiecte de primă clasă.
Câteva limbi Actor timpurii, inclusiv limbile Act, [25] [26] au acceptat transmiterea paralelă a mesajelor și canalizarea mesajelor, dar nu și pipeline-ul promisiunii. (În ciuda posibilității de a implementa pipeline-ul promis prin intermediul constructelor acceptate, nu există dovezi ale unor astfel de implementări în limbile Act.)
Conceptul de viitor poate fi implementat în termeni de canale : un viitor este un canal singleton, iar o promisiune este un proces care trimite o valoare unui canal prin executarea viitorului [27] . Acesta este modul în care viitoarele sunt implementate în limbaje simultane activate pentru canal, cum ar fi CSP și Go . Viitoarele pe care le implementează sunt explicite deoarece sunt accesate prin citirea de pe un canal, nu prin evaluarea expresiei normale.