Evalueringsstrategi - Evaluation strategy

Evalueringsstrategier

I et programmeringssprog er en evalueringsstrategi et sæt regler for evaluering af udtryk. Udtrykket bruges ofte til at henvise til den mere specifikke forestilling om en parameteroverførende strategi, der definerer, om parametrene for et funktionsopkald skal evalueres , og i givet fald i hvilken rækkefølge ( evalueringsordren ) og den slags værdi, der sendes til funktionen for hver parameter ( bindingsstrategien ). Begrebet reduktionsstrategi er tydelig, selvom nogle forfattere kombinerer de to udtryk, og definitionen af ​​hvert udtryk ikke er bred enighed om.

For at illustrere, kan en funktionsapplikation evaluere argumentet, før den evaluerer funktionens krop og videregive adressen, hvilket giver funktionen mulighed for at slå argumentets aktuelle værdi op og ændre det via tildeling .

Evalueringsstrategi er specificeret af programmeringssprogsdefinitionen og er ikke en funktion af nogen specifik implementering. Den kaldekonvention definerer implementering-specifik parameter passerer detaljer.

Bord

Dette er en tabel med evalueringsstrategier og repræsentative sprog efter år introduceret. De repræsentative sprog er angivet i kronologisk rækkefølge, startende med de sprog, der introducerede strategien (hvis nogen) og efterfulgt af fremtrædende sprog, der bruger strategien.

Evalueringsstrategi Repræsentative sprog År blev først introduceret
Ring efter reference FORTRAN II , PL/I 1958
Opkald efter værdi ALGOL , C , skema 1960
Ring efter navn ALGOL 60 , Simula 1960
Opkald ved kopi-gendannelse Fortran IV , Ada 1962
Ring efter behov Haskell , R. 1971
Opkald efter referenceparametre C ++ , PHP , C# , Visual Basic .NET ?
Ring med henvisning til konst C , C ++ ?
Ring ved at dele Java, Python, Ruby ?

Evalueringsordrer

Mens rækkefølgen af ​​operationer definerer udtrykets abstrakte syntakstræ , definerer evalueringsordren den rækkefølge, hvori udtryk evalueres. For eksempel Python -programmet 

def f(x):
    print(x)
    return x

f(1) + f(2)

output på 1 2grund af Pythons evalueringsordre fra venstre til højre, men et lignende program i OCaml: 

let f x =  print_string (string_of_int x); x ;;
f 1 + f 2

output på 2 1grund af OCamls evalueringsordre fra højre til venstre.

Evalueringsordren er hovedsageligt synlig i kode med bivirkninger , men den påvirker også kodens ydeevne, fordi en stiv ordre hæmmer instruktionsplanlægning . Af denne grund efterlod sprogstandarder som C ++ traditionelt ordren udefineret, selvom sprog som Java og C# definerer evalueringsrækkefølgen som venstre til højre, og C ++ 17- standarden har tilføjet begrænsninger for evalueringsordren.

Strenge evaluering

Anvendelig rækkefølge er en familie af evalueringsordrer, hvor en funktions argumenter evalueres fuldstændigt, før funktionen anvendes. Dette har den virkning, at funktionen bliver streng , dvs. funktionens resultat er udefineret, hvis et af argumenterne er udefineret, så applikativ rækkefølgeevaluering mere almindeligt kaldes streng evaluering . Desuden udføres et funktionsopkald, så snart det støder på i en procedure, så det kaldes også ivrig evaluering eller grådig evaluering . Nogle forfattere omtaler streng evaluering som "call by value" på grund af den call-by-value bindende strategi, der kræver streng evaluering.

Fælles Lisp, Eiffel og Java evaluerer funktionsargumenter fra venstre til højre. C efterlader ordren udefineret. Skema kræver, at eksekveringsordren er den sekventielle udførelse af en uspecificeret permutation af argumenterne. OCaml efterlader på samme måde ordren uspecificeret, men vurderer i praksis argumenter højre til venstre på grund af designet af sin abstrakte maskine . Alle disse er strenge evalueringer.

Ikke-streng evaluering

En ikke-streng evalueringsordre er en evalueringsordre, der ikke er streng, det vil sige, at en funktion kan returnere et resultat, før alle dens argumenter er fuldt ud evalueret. Det prototypiske eksempel er normal ordreevaluering , som ikke evaluerer nogen af ​​argumenterne, før de er nødvendige i funktionens krop. Normal ordreevaluering har den egenskab, at den afsluttes uden fejl, når enhver anden evalueringsordre afsluttes uden fejl. Bemærk, at doven evaluering i denne artikel er klassificeret som en bindende teknik frem for en evalueringsordre. Men denne sondring følges ikke altid, og nogle forfattere definerer doven evaluering som normal ordreevaluering eller omvendt eller forveksler ikke-strenghed med doven evaluering.

Boolske udtryk på mange sprog bruger en form for ikke-streng evaluering kaldet kortslutningsevaluering , hvor evaluering vender tilbage, så snart det kan fastslås, at en entydig boolsk vil resultere-for eksempel i et disjunktivt udtryk (OR), hvor trueman støder på, eller i et konjunktivt udtryk (AND), hvor falseman støder på og så videre. Betingede udtryk bruger på samme måde ikke -streng evaluering - kun en af ​​grenene evalueres.

Sammenligning af gældende rækkefølge og normal ordreevaluering

Ved normal ordreevaluering vil udtryk, der indeholder en dyr beregning, en fejl eller en uendelig sløjfe, blive ignoreret, hvis det ikke er nødvendigt, hvilket tillader specifikation af brugerdefinerede kontrolflowkonstruktioner, en facilitet, der ikke er tilgængelig med applikativ ordreevaluering. Normal ordreevaluering bruger komplekse strukturer, f.eks. Thunks til uvurderede udtryk, sammenlignet med opkaldsstakken, der blev anvendt i applikativ ordreevaluering . Normal ordreevaluering har historisk set manglet brugbare fejlfindingsværktøjer på grund af dens kompleksitet.

Strenge bindingsstrategier

Opkald efter værdi

I opkald efter værdi er den evaluerede værdi af argumentudtrykket bundet til den tilsvarende variabel i funktionen (ofte ved at kopiere værdien til et nyt hukommelsesområde). Hvis funktionen eller proceduren er i stand til at tildele værdier til sine parametre, tildeles kun den lokale variabel - det vil sige, at alt, der sendes til et funktionsopkald, er uændret i opkalders omfang, når funktionen vender tilbage.

Implicitte begrænsninger

I nogle tilfælde er udtrykket "opkald efter værdi" problematisk, da værdien, der overføres, ikke er variabelens værdi som forstået af den almindelige betydning af værdi, men en implementeringsspecifik henvisning til værdien. Effekten er, at det, der syntaktisk ligner opkald efter værdi, kan ende med at opføre sig som opkald ved reference eller opkald ved at dele , ofte afhængigt af meget subtile aspekter af sprogsemantikken.

Grunden til at videregive en reference er ofte, at sproget teknisk set ikke giver en værdirepræsentation af komplicerede data, men i stedet repræsenterer dem som en datastruktur, samtidig med at der bevares en vis form for værdienes udseende i kildekoden. Præcis hvor grænsen er trukket mellem korrekte værdier og datastrukturer, der udgør sig som sådan, er ofte svært at forudsige. I C er en matrix (hvoraf strenge er specielle sager) en datastruktur, men navnet på en matrix behandles som (har som værdi) henvisningen til matrixens første element, mens en strukturvariabels navn refererer til en værdi selvom den har felter, der er vektorer. I Maple er en vektor et specielt tilfælde af en tabel og derfor en datastruktur, men en liste (som bliver gengivet og kan indekseres på nøjagtig samme måde) er en værdi. I Tcl er værdier "dobbeltportede", således at værdirepræsentationen bruges på scriptniveau, og sproget selv administrerer den tilsvarende datastruktur, hvis en er påkrævet. Ændringer foretaget via datastrukturen reflekteres tilbage til værdirepræsentationen og omvendt.

Beskrivelsen "opkald efter værdi, hvor værdien er en reference", er almindelig (men skal ikke forstås som opkald ved reference); et andet udtryk er opkald ved deling . Således er opkaldet efter værdi Java eller Visual Basic og opkald efter værdi C eller Pascal væsentligt forskelligt: ​​i C eller Pascal vil opkald til en funktion med en stor struktur som et argument få hele strukturen til at blive kopieret (undtagen hvis det faktisk er en henvisning til en struktur), der potentielt kan forårsage alvorlig ydelsesforringelse og mutationer i strukturen er usynlige for den, der ringer. I Java eller Visual Basic kopieres imidlertid kun referencen til strukturen, hvilket er hurtigt, og mutationer til strukturen er synlige for den, der ringer.

Ring efter reference

Opkald ved reference (eller pass ved reference) er en evalueringsstrategi, hvor en parameter er bundet til en implicit henvisning til variablen, der bruges som argument, frem for en kopi af dens værdi.

Dette betyder typisk, at funktionen kan ændre (dvs. tildele ) variablen, der bruges som argument - noget, der vil blive set af den, der ringer. Opkald ved reference kan derfor bruges til at tilvejebringe en yderligere kommunikationskanal mellem den kaldte funktion og den kaldende funktion. Et opkald-til-reference-sprog gør det vanskeligere for en programmør at spore virkningerne af et funktionsopkald og kan indføre subtile fejl. En simpel lakmus-test for, om et sprog understøtter call-by-reference semantik, er, om det er muligt at skrive en traditionel swap(a, b)funktion på sproget.

Opkald ved reference kan simuleres på sprog, der bruger opkald efter værdi og ikke ligefrem understøtter opkald ved reference, ved at gøre brug af referencer (objekter, der henviser til andre objekter), såsom pointer (objekter, der repræsenterer hukommelsesadresser for andre objekter) . Sprog som C , ML og Rust bruger denne teknik. Det er ikke en separat evalueringsstrategi - sproget kalder efter værdi - men nogle gange kaldes det "opkald efter adresse" eller "forbi adresse". I ML er referencer type- og hukommelsessikre , svarende til Rust.

På rent funktionelle sprog er der typisk ingen semantisk forskel mellem de to strategier (da deres datastrukturer er uforanderlige, så der ikke er nogen mulighed for en funktion at ændre nogen af ​​dens argumenter), så de beskrives typisk som opkald efter værdi, selvom implementeringer brug ofte opkald ved reference internt for effektivitetsfordelene.

Følgende er et eksempel, der demonstrerer opkald ved reference i programmeringssproget E : 

def modify(var p, &q) {
    p := 27 # passed by value: only the local parameter is modified
    q := 27 # passed by reference: variable used in call is modified
}

? var a := 1
# value: 1
? var b := 2
# value: 2
? modify(a, &b)
? a
# value: 1
? b
# value: 27

Følgende er et eksempel på opkald efter adresse, der simulerer opkald ved reference i C : 

void modify(int p, int* q, int* r) {
    p = 27; // passed by value: only the local parameter is modified
    *q = 27; // passed by value or reference, check call site to determine which
    *r = 27; // passed by value or reference, check call site to determine which
}

int main() {
    int a = 1;
    int b = 1;
    int x = 1;
    int* c = &x;
    modify(a, &b, c); // a is passed by value, b is passed by reference by creating a pointer (call by value),
                    // c is a pointer passed by value
                    // b and x are changed
    return 0;
}

Ring ved at dele

Call by sharing (også kendt som "call by object" eller "call by object-sharing") er en evalueringsstrategi, der først blev noteret af Barbara Liskov i 1974 for CLU- sproget. Det bruges af sprog som Python , Java (til objektreferencer), Ruby , JavaScript , Scheme, OCaml, AppleScript og mange andre. Udtrykket "opkald ved deling" er imidlertid ikke almindeligt anvendt; terminologien er inkonsekvent på tværs af forskellige kilder. For eksempel siger de i Java -fællesskabet, at Java er opkald efter værdi. Opkald ved deling indebærer, at værdier i sproget er baseret på objekter frem for primitive typer , dvs. at alle værdier er " bokset ". Fordi de er i boks, kan de siges at passere ved kopi af reference (hvor primitiver er bokset før de passeres og udpakket med kaldet funktion).

Semantikken ved opkald ved deling adskiller sig fra opkald ved reference: "Især er det ikke opkald efter værdi, fordi mutationer af argumenter udført af den kaldte rutine vil være synlige for den, der ringer. Og det er ikke opkald ved reference, fordi der ikke gives adgang til den opkaldendes variabler, men kun til bestemte objekter ". Så for eksempel, hvis en variabel blev bestået, er det ikke muligt at simulere en tildeling på denne variabel i callees omfang. Da funktionen imidlertid har adgang til det samme objekt som den, der ringer op (ingen kopi foretages), er mutationer til disse objekter, hvis objekterne kan ændres , synlige inden for funktionen for den, der ringer op, hvilket kan se ud til at variere fra opkald efter værdi semantik. Mutationer af et objekt, der kan ændres i funktionen, er synlige for den, der ringer op, fordi objektet ikke kopieres eller klones - det deles.

I Python kan lister for eksempel ændres, så: 

def f(a_list):
    a_list.append(1)

m = []
f(m)
print(m)

output, [1]fordi appendmetoden ændrer objektet, som det kaldes på.

Tildelinger inden for en funktion er ikke synlige for den, der ringer, fordi passering af variablen på disse sprog kun betyder, at man sender (adgang til) det faktiske objekt, som variablen refererer til, ikke adgang til den originale (opkalders) variabel. Da rebound -variablen kun findes inden for funktionsomfanget, bevarer modparten i opkalderen sin oprindelige binding.

Sammenlign Python -mutationen ovenfor med koden herunder, som binder det formelle argument til et nyt objekt: 

def f(a_list):
    a_list = [1]

m = []
f(m)
print(m)

output [], fordi udsagnet a_list = [1]tildeler en ny liste til variablen frem for den placering, den refererer til.

For uforanderlige objekter er der ingen reel forskel mellem opkald ved deling og opkald efter værdi, undtagen hvis objektidentitet er synlig på sproget. Anvendelse af opkald ved at dele med objektiver, der kan ændres, er et alternativ til input/output -parametre : parameteren tildeles ikke (argumentet overskrives ikke, og objektidentiteten ændres ikke), men objektet (argumentet) er muteret.

Opkald ved kopi-gendannelse

Opkald ved kopi-gendannelse-også kendt som "kopi-ind kopi-ud", "opkald efter værdiresultat", "opkald efter værdiretur" (som betegnet i Fortran- fællesskabet)-er et specielt tilfælde af opkald som reference, hvor den angivne reference er unik for den, der ringer op. Denne variant har fået opmærksomhed i multiprocesseringskontekster og fjernprocedurekald : Hvis en parameter til et funktionsopkald er en reference, der kan være tilgængelig for en anden udførelsestråd, kan dens indhold blive kopieret til en ny reference, der ikke er; når funktionsopkaldet vender tilbage, kopieres det opdaterede indhold i denne nye reference tilbage til den originale reference ("gendannet").

Semantikken ved opkald ved kopirestaurering adskiller sig også fra opkald ved reference, hvor to eller flere funktionsargumenter alias hinanden (dvs. peger på den samme variabel i den, der ringer op). Under opkald som reference vil skrivning til den ene påvirke den anden; opkald ved kopi-gendannelse undgår dette ved at give funktionen forskellige kopier, men efterlader resultatet i opkaldsmiljøet udefineret afhængigt af hvilket af de alias-argumenter, der først kopieres tilbage-vil kopierne blive foretaget i venstre-til-højre rækkefølge både ved indtastning og ved retur?

Når referencen uinitialiseres til calleen, kan denne evalueringsstrategi kaldes "call by result".

Ikke-strenge bindingsstrategier

Ring efter navn

Opkald ved navn er en evalueringsstrategi, hvor argumenterne til en funktion ikke evalueres, før funktionen kaldes-de erstattes snarere direkte i funktionskroppen (ved hjælp af fangstundgående substitution ) og derefter overlades til at blive evalueret, hver gang de vises i fungere. Hvis et argument ikke bruges i funktionsdelen, evalueres argumentet aldrig; hvis det bruges flere gange, vurderes det igen, hver gang det vises. (Se Jensens enhed .)

Evaluering af opkald efter navn foretrækkes lejlighedsvis frem for evaluering efter værdi. Hvis en funktions argument ikke bruges i funktionen, vil opkald ved navn spare tid ved ikke at evaluere argumentet, mens opkald efter værdi vil evaluere det uanset. Hvis argumentet er en ikke-afsluttende beregning, er fordelen enorm. Men når funktionsargumentet bruges, er opkald ved navn ofte langsommere, hvilket kræver en mekanisme som f.eks. En tunk .

Dagens .NET -sprog kan simulere opkald ved navn ved hjælp af delegerede eller Expression<T>parametre. Sidstnævnte resulterer i, at et abstrakt syntakstræ gives til funktionen. Eiffel leverer agenter, der repræsenterer en operation, der skal evalueres, når det er nødvendigt. Seed7 giver opkald efter navn med funktionsparametre. Java -programmer kan udføre lignende dovne evalueringer ved hjælp af lambda -udtryk og java.util.function.Supplier<T>grænsefladen.

Ring efter behov

Hovedartikel: Lazy evaluering

Opkald efter behov er en memoiseret variant af opkald ved navn, hvor værdien gemmes til senere brug, hvis funktionsargumentet evalueres. Hvis argumentet er rent (dvs. fri for bivirkninger), giver dette de samme resultater som opkald ved navn, hvilket sparer omkostninger ved at genberegne argumentet.

Haskell er et velkendt sprog, der bruger evaluering efter behov. Fordi evaluering af udtryk kan ske vilkårligt langt ind i en beregning, understøtter Haskell kun bivirkninger (såsom mutation ) via brug af monader . Dette eliminerer enhver uventet adfærd fra variabler, hvis værdier ændres før deres forsinkede evaluering.

Ved R 's implementering af opkald efter behov bliver alle argumenter passeret, hvilket betyder, at R tillader vilkårlige bivirkninger.

Lazy evaluering er den mest almindelige implementering af call-by-need semantik, men der findes variationer som optimistisk evaluering . .NET -sprog implementerer opkald efter behov ved hjælp af typen Lazy<T>.

Grafreduktion er en effektiv implementering af doven evaluering.

Opkald ved makroudvidelse

Opkald ved makroudvidelse ligner opkald ved navn, men bruger tekstlig substitution frem for indfangning og undgår derved substitution. Men makrosubstitution kan forårsage fejl, hvilket resulterer i variabel optagelse , hvilket fører til uønsket adfærd. Hygiejniske makroer undgår dette problem ved at kontrollere og udskifte skyggefulde variabler , der ikke er parametre.

Ring fremover

Se også: Fremtider og løfter

"Call by future", også kendt som "parallel call by name", er en samtidig evalueringsstrategi, hvor værdien af ​​et fremtidigt udtryk beregnes samtidigt med flowet i resten af ​​programmet med løfter, også kendt som futures. Når løfteværdien er nødvendig, blokerer hovedprogrammet, indtil løftet har en værdi (løftet eller et af løfterne afslutter computing, hvis det ikke allerede er afsluttet inden da).

Denne strategi er ikke-deterministisk, da evalueringen kan forekomme når som helst mellem fremtidens oprettelse (dvs. når udtrykket er givet) og brug af fremtidens værdi. Det ligner at kalde efter behov, idet værdien kun beregnes én gang, og beregning kan udskydes, indtil værdien er nødvendig, men den kan startes før. Hvis værdien af ​​en fremtid ikke er nødvendig, f.eks. Hvis det er en lokal variabel i en funktion, der vender tilbage, kan beregningen endvidere afsluttes halvvejs.

Hvis det implementeres med processer eller tråde, skaber en fremtid en eller flere nye processer eller tråde (for løfterne), adgang til værdien synkroniserer disse med hovedtråden, og afslutning af fremtidens beregning svarer til at dræbe løfterne, der beregner dens værdi.

Hvis det implementeres med en coroutine , som i .NET async/afventer , opretter en fremtid et opkald til en coroutine (en asynkroniseringsfunktion), som kan give efter for den, der ringer op, og igen kan returneres til, når værdien bruges, i samarbejde multitasking.

Optimistisk evaluering

Optimistisk evaluering er en anden call-by-need-variant, hvor funktionens argument delvist evalueres i et stykke tid (som kan justeres ved runtime ). Efter at den tid er gået, afbrydes evalueringen, og funktionen anvendes ved hjælp af opkald efter behov. Denne fremgangsmåde undgår nogle call-by-need-strategiens driftsudgifter, samtidig med at de ønskede afslutningsegenskaber bevares.

Se også

Referencer


Yderligere læsning

eksterne links