Referenstransparens

Den här artikeln handlar om referenstransparens i programmeringsspråksteori. För dess användning i lingvistik och filosofi, se Opaque context .

Inom datavetenskap är referenstransparens och referensopacitet egenskaper hos delar av datorprogram . Ett uttryck kallas referenstransparent om det kan ersättas med dess motsvarande värde (och vice versa) utan att ändra programmets beteende. Detta kräver att uttrycket är rent – ​​dess värde måste vara detsamma för samma indata och dess utvärdering får inte ha några biverkningar . Ett uttryck som inte är referensmässigt transparent kallas referensiellt ogenomskinligt .

I matematik är alla funktionstillämpningar referenstransparenta, enligt definitionen av vad som utgör en matematisk funktion . Detta är dock inte alltid fallet i programmering, där termerna procedur och metod används för att undvika missvisande konnotationer. En utmärkande egenskap hos funktionell programmering är att den endast tillåter referenstransparenta funktioner. Andra programmeringsspråk kan tillhandahålla medel för att selektivt garantera referenstransparens. Vissa funktionella programmeringsspråk tvingar fram referenstransparens för alla funktioner.

Vikten av referenstransparens är att den tillåter programmeraren och kompilatorn att resonera om programbeteende som ett omskrivningssystem . Detta kan hjälpa till att bevisa korrekthet , förenkla en algoritm , hjälpa till att modifiera kod utan att bryta den eller optimera koden med hjälp av memoisering , eliminering av vanliga underuttryck , lat utvärdering eller parallellisering .

Historia

Begreppet verkar ha sitt ursprung i Alfred North Whitehead och Bertrand Russells Principia Mathematica (1910–13). Det antogs i analytisk filosofi av Willard Van Orman Quine . I §30 i Word and Object (1960) ger Quine denna definition:

Ett inneslutningssätt φ är referensmässigt transparent om, närhelst en förekomst av en singulär term t är rent referens i en term eller mening ψ(t), den är rent referensmässig även i den innehållande termen eller meningen φ(ψ(t)).

Termen dök upp i dess samtida datavetenskapliga användning, i diskussionen om variabler i programmeringsspråk , i Christopher Stracheys framstående uppsättning föreläsningsanteckningar Fundamental Concepts in Programming Languages ​​(1967). Föreläsningsanteckningarna refererade till Quines ord och objekt i bibliografin.

Exempel och motexempel

Om alla funktioner som är involverade i uttrycket är rena funktioner är uttrycket referenstransparent.

Tänk på en funktion som returnerar indata från någon källa. I pseudokod kan ett anrop till den här funktionen vara GetInput(Source) där Source kan identifiera en viss diskfil, tangentbordet etc. Även med identiska värden för Source kommer de successiva returvärdena att vara olika. Därför är funktionen GetInput() varken deterministisk eller referenstransparent.

Ett mer subtilt exempel är det på en funktion som har en fri variabel , dvs. beror på någon indata som inte uttryckligen skickas som en parameter. Detta löses sedan enligt namnbindningsregler till en icke-lokal variabel , till exempel en global variabel , en variabel i den aktuella exekveringsmiljön (för dynamisk bindning ) eller en variabel i en stängning (för statisk bindning). Eftersom denna variabel kan ändras utan att ändra värdena som skickas som parameter, kan resultatet av efterföljande anrop till funktionen skilja sig åt även om parametrarna är identiska. Men i ren funktionell programmering är destruktiv tilldelning inte tillåten, och om den fria variabeln är statiskt bunden till ett värde är funktionen fortfarande referenstransparent, eftersom varken den icke-lokala variabeln eller dess värde kan ändras, på grund av statisk bindning och oföränderlighet , respektive.

Aritmetiska operationer är referenstransparenta: 5 * 5 kan till exempel ersättas med 25 . Faktum är att alla funktioner i matematisk mening är referenstransparenta: sin(x) är transparent, eftersom den alltid ger samma resultat för varje enskilt x .

Omtilldelningar är inte transparenta. Till exempel C -uttrycket x = x + 1 värdet som tilldelats variabeln x . Om man antar att x initialt har värdet 10 ger två på varandra följande utvärderingar av uttrycksutbytet 11 respektive 12 . Att ersätta x = x + 1 med antingen 11 eller 12 ger uppenbarligen ett program med annan innebörd, så uttrycket är inte referenstransparent. Men att anropa en funktion som int plusone ( int x ) { return x + 1 ; } är transparent, eftersom den inte implicit kommer att ändra ingången x och har därför inga sådana bieffekter .

today() är inte transparent, som om du utvärderar den och ersätter den med dess värde (säg "1 jan 2001" ), får du inte samma resultat som du får om du kör den imorgon. Detta beror på ett tillstånd (datumet).

I språk utan biverkningar, som Haskell , kan vi ersätta lika med lika: dvs om x == y så f(x) == f(y) . Detta är en egenskap som även kallas omöjliga identiska . Sådana egenskaper behöver inte gälla i allmänhet för språk med biverkningar. Trots det är det viktigt att begränsa sådana påståenden till så kallad bedömningslikhet, det vill säga likheten mellan termerna som testats av systemet, inte inklusive användardefinierad likvärdighet för typer. Till exempel, om B f(A x) och typen A har åsidosatt begreppet likhet, t.ex. gör alla termer lika, då är det möjligt att ha x == y och ändå hitta f(x) != f(y) . Detta beror på att system som Haskell inte verifierar att funktioner definierade på typer med användardefinierade ekvivalensrelationer är väldefinierade med avseende på den ekvivalensen. Således är referenstransparensen begränsad till typer utan ekvivalensrelationer. Att utöka referenstransparensen till användardefinierade ekvivalensrelationer kan göras till exempel med en Martin-Lof-identitetstyp, men kräver ett beroendetypat system som i Agda , Coq eller Idris .

Kontrast till imperativ programmering

Om ersättningen av ett uttryck med dess värde endast är giltigt vid en viss punkt i programmets körning, är uttrycket inte referenstransparent. Definitionen och ordningen av dessa sekvenspunkter är den teoretiska grunden för imperativ programmering och en del av semantiken i ett imperativt programmeringsspråk.

Men eftersom ett referenstransparent uttryck kan utvärderas när som helst, är det inte nödvändigt att definiera sekvenspunkter eller någon garanti för utvärderingsordningen alls. Programmering som görs utan dessa överväganden kallas rent funktionell programmering .

En fördel med att skriva kod i en referenstransparent stil är att med en intelligent kompilator är statisk kodanalys enklare och bättre kodförbättrande transformationer är möjliga automatiskt. Till exempel, vid programmering i C, kommer det att bli en prestationsstraff för att inkludera ett anrop till en dyr funktion i en loop, även om funktionsanropet skulle kunna flyttas utanför slingan utan att ändra programmets resultat. Programmeraren skulle tvingas utföra manuell kodrörelse av samtalet, möjligen på bekostnad av källkodens läsbarhet. Men om kompilatorn kan fastställa att funktionsanropet är referenstransparent, kan den utföra denna transformation automatiskt.

Den främsta nackdelen med språk som upprätthåller referenstransparens är att de gör uttrycket för operationer som naturligt passar in i en imperativ programmeringsstil mer besvärlig och mindre koncis. Sådana språk innehåller ofta mekanismer för att göra dessa uppgifter lättare samtidigt som de behåller den rent funktionella kvaliteten på språket, såsom bestämda satsgrammatiker och monader .

Ett annat exempel

Som ett exempel, låt oss använda två funktioner, en som är referenstransparent och den andra som är referensmässigt ogenomskinlig:

   0

   
     


   
  
     
 int  g  =  ;  int  rt  (  int  x  )  {  retur  x  +  1  ;  }  int  ro  (  int  x  )  {  g  ++  ;  returnera  x  +  g  ;  }

Funktionen rt är referenstransparent, vilket betyder att om x == y så är rt(x) == rt(y) . Till exempel, rt(6) = 7 . Vi kan dock inte säga något sådant för ro eftersom den använder en global variabel som den modifierar.

Den refererande opaciteten hos ro gör resonemang om program svårare. Säg till exempel att vi vill resonera kring följande påstående: 

          int  i  =  ro  (  x  )  +  ro  (  y  )  *  (  ro  (  x  )  -  ro  (  x  ));

Man kan vara frestad att förenkla detta uttalande till:

       0
     0
    int  i  =  ro  (  x  )  +  ro  (  y  )  *  ;  int  i  =  ro  (  x  )  +  ;  int  i  =  ro  (  x  );

Detta kommer dock inte att fungera för ro eftersom varje förekomst av ro(x) utvärderas till ett annat värde. Kom ihåg att returvärdet för ro är baserat på ett globalt värde som inte skickas in och som ändras vid varje anrop till ro . Det betyder att matematiska identiteter som x − x = 0 inte längre håller.

Sådana matematiska identiteter kommer att gälla för referenstransparenta funktioner som rt .

En mer sofistikerad analys kan dock användas för att förenkla uttalandet till:

                                  
                                  
                        
                      
             int  tmp  =  g  ;  int  i  =  x  +  tmp  +  1  +  (  y  +  tmp  +  2  )  *  (  x  +  tmp  +  3  -  (  x  +  tmp  +  4  ));  g  =  g  +  4  ;  int  tmp  =  g  ;  int  i  =  x  +  tmp  +  1  +  (  y  +  tmp  +  2  )  *  (  x  +  tmp  +  3  -  x  -  tmp  -  4  ));  g  =  g  +  4  ;  int  tmp  =  g  ;  int  i  =  x  +  tmp  +  1  +  (  y  +  tmp  +  2  )  *  (  -1  );  g  =  g  +  4  ;  int  tmp  =  g  ;  int  i  =  x  +  tmp  +  1  -  y  -  tmp  -  2  ;  g  =  g  +  4  ;  int  i  =  x  -  y  -  1  ;  g  =  g  +  4  ;

Detta tar fler steg och kräver en grad av insikt i koden som är omöjlig för kompilatoroptimering.

Därför tillåter referenstransparens oss att resonera kring vår kod som kommer att leda till mer robusta program, möjligheten att hitta buggar som vi inte kunde hoppas att hitta genom att testa, och möjligheten att se möjligheter till optimering .

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Referential_transparency&oldid=1117250292 "