In Through the looking glass van Lewis Carroll, wil de Ridder voor Alice een lied zingen:
`You are sad,' the Knight said in an anxious tone: `let me sing you a song to comfort you.' ... `The name of the song is called "Haddock's Eyes."'.
`Oh, that's the name of the song, is it?' Alice said, trying to feel interested.
`No, you don't understand,' the Knight said, looking a little vexed. `That is what the name is called. The name really is "The Aged Aged Man."' `Then I ought to have said "That's what the song is called"?' Alice corrected herself.
`No, you oughtn't: That's quite another thing! The song is called "Ways and Means": but that is only what it is called, you know!'
`Well, what is the song then?' said Alice, who was by this time completely bewildered.
`I was coming to that,' the Knight said. `The song really is "A-sitting On A Gate": and the tune's my own invention.
In de natuurlijke taal moet meestal uit het verband en het gezond verstand van de toehoorders duidelijk worden welke woorden waar naar verwijzen.
De grammatica helpt soms een klein beetje: In "Hij ziet hem in de spiegel" vs. "Hij ziet zich in de spiegel" maakt de grammatica duidelijk dat in het eerste geval "hem" op een andere persoon slaat dan "hij". Erg uitvoerig is dit onderscheid niet: in "hij ziet zijn huis" kunnen we dat verschil niet makkelijk meer uitdrukken: we hebben wel "zijn eigen" maar geen korte manier om te laten zien dat "zijn" niet op dezelfde persoon slaat.
(Het Deens maakt nog verschil: "han ser hans hus" vs "han ser sit hus", net als het Latijn: "suus" slaat terug op het onderwerp, "eius" niet.)
Een ander bezwaar van de natuurlijke taal is dat geen duidelijk onderscheid gemaakt wordt tussen dingen en hun naam. In "Willem heeft drie dochters" en "Willem heeft zes letters" en "Willem staat cursief" wordt naar drie verschillende dingen verwezen: naar een persoon, naar de spelling van de naam van die persoon, naar de tekstuele representatie van één instantie van die naam.
Ik bezit serieuze grammatica's waarin gesteld wordt dat elke woordsoort onderwerp van een Nederlandse zin zijn kan. Om te laten zien dat een zin een voorzetsel als onderwerp kan hebben wordt het voorbeeld gegeven: "`Op' is een voorzetsel". Maar het onderwerp van die zin is helemaal geen voorzetsel. Het onderwerp is niet "Op" maar "`Op'", en de naam van iets is een zelfstandig naamwoord.
In een programmeertaal moet zorgvuldig rekenschap gegeven worden welke uitdrukkingen waar aan refereren.
Stel we hebben een programmeertaal en schrijven f(x) op. Wat gebeurt er? Bij het uitrekenen van f(x), welke x wordt er gebruikt, en wat wordt er precies met die x gedaan? Hier zijn talloze mechanismen. Oplettendheid is geboden. Vaak is de intuïtie die we uit de wiskunde hebben zeer misleidend.
Het meest primitief is de macroprocessor die gewoon x invult in de definitie van x. Na
#define f(x) x*x
denk je misschien dat f(x) het kwadraat van x uitrekent, maar helaas! Als ik f(a+1) aanroep krijg ik a+1*a+1 d.w.z. 2a+1. Bij gebruik van macroprocessoren moet je de definities altijd volledig van haakjes voorzien om niet gefopt te worden:
#define square(x) ((x)*(x))
Dat was de C preprocessor. Java heeft geen preprocessor, en vermijdt dus ook dit soort valkuilen.
In C heb je precies 1 parametermechanisme: call-by-value. Als ik f(E) opschrijf, met voor E een of andere uitdrukking, dan wordt eerst E uitgerekend, en daarna wordt f aangeroepen met de zo gevonden waarde. Eenvoudig en rechttoe rechtaan.
Meer in het bijzonder, als x de waarde 7 heeft dan is bij call-by-value de aanroep f(x) equivalent met de aanroep f(7), en zal bijvoorbeeld de waarde van x niet wijzigen.
Blijft de vraag waar x aan refereert. Het antwoord is dat elke naam een geldigheidsgebied (scope) heeft, en de kleinste scope waarin een variabele x gedefinieerd is geeft aan welke x bedoeld is.
Bijvoorbeeld: in
int x = 1;
out(int x) {
printf("%d\n", x);
}
main(){
int x = 2;
foo();
out(x);
if (x > 0) {
int x = 3;
out(x);
}
out(x);
foo();
}
foo() {
out(x);
}
komen vier variabelen x voor. Een globale (die 1 is), een locale in main()
(die 2 is), een locale binnen het if-statement in main() (die 3 is),
en een formele in out() waarvan de waarde bij aanroep bepaald
wordt. De x in printf("%d\n", x) is de formele parameter,
de x in de eerste en derde out(x) in main() is de locale,
de x in de tweede out(x) in main() is die binnen het
if-statement, en de x in out(x) in foo() is de globale
x.
Een scope kun je vinden door de eerste { voor de
declaratie te zoeken, en dan de bijbehorende }. Het stuk daartussen
is de scope van de gedeclareerde variabele;
Dit programma drukt dus 1 2 3 2 1 af.
In dit voorbeeld konden de verschillende incarnaties van de variabele x in de tekst aangewezen worden, maar als een procedure recursief is en een variabele x declareert, dan kunnen onbegrensd veel verschillende variabelen x tegelijk actief zijn.
Met Pascal is alles precies zo, maar dan met BEGIN en END in plaats van { en }. Ook Java volgt dit voorbeeld.
In ALGOL-60 heb je twee parameter mechanismen: call-by-name en call-by-value.
Call-by-name is het mechanisme dat je ook in de Lambda Calculus hebt: vervang in de tekst van de procedure overal de formele parameters door de actuele parameters, en voer de procedure dan uit.
Met call-by-name kun je opschrijven
PROCEDURE square(x); INTEGER x; BEGIN x := x * x END;
(met hoofdletters in plaats van flexowriter-onderstreepte kleine letters, en * in plaats van ×) waarbij een argument door de aanroep verandert.
Een grappige toepassing van call-by-name is `Jensen's device' (bedacht in 1960 door Jørn Jensen, werkzaam bij de Regnecentrale in Kopenhagen), waarbij één parameter van een andere afhankelijk is:
INTEGER PROCEDURE sum(i,n,x); VALUE n; INTEGER n;
BEGIN INTEGER s;
s := 0;
FOR i:=1 STEP 1 UNTIL n DO s := s+x;
sum := s;
END;
Nu berekent de aanroep sum(i,n,u[i]*v[i]) het inwendig product van de
vectoren u en v, terwijl de aanroep sum(i,n,sin(i)) waarden
van de sinusfunctie optelt.
Dit is natuurlijk zeer obscuur programmeren: de lezer van de functie sum
heeft nauwelijks een idee wat er gebeurt.
Hier de definitie van call-by-name in het Algol rapport:
From the Revised Report on the Algorithmic Language Algol 60:
4.7.3 Semantics
A procedure statement serves to invoke (call for) the
execution of a procedure body... Where the procedure body is
a statement written in Algol, the effect of this execution
will be equvalent to the effect of performing the following
operations on the program at the time of execution of the
procedure statement:
...
4.7.3.1. Value assignment (call by value)
...
4.7.3.2. Name replacement (call by name)
Any formal parameter not quoted in the value list is replaced,
throughout the procedure body, by the corresponding actual
parameter, after enclosing this latter in parentheses wherever
syntactically possible. Possible conflicts between identifiers
inserted through this process and other identifiers already
present within the procedure body will be avoided by suitable
systematic changes of the formal or local identifiers involved.
Dit klinkt weinig schokkend, maar is in feite ontzettend gecompliceerd doordat de variabelen bij de "Name replacement" hun identiteit moeten behouden. In één enkele expressie kunnen variabelen voorkomen die in geheel verschillende context gedefinieerd zijn, en zulke variabelen moeten dus een hele administratie meeslepen om bij te houden om welke recursieve incarnatie van welke textuele declaratie het gaat.
Knuth schreef het programma Man-or-Boy (Algol Bulletin 17.2.4, Juli 1964) dat een Algol-60 compiler test op het correct behandelen van niet-locale verwijzingen naar verschillende recursieve incarnaties van dezelfde variabele. Hij had zelf uitgerekend wat het resultaat zou moeten zijn (-121), maar in feite is het resultaat -67. (In Algol Bulletin 19.2.3.4 verontschuldigt Knuth zich door te zeggen dat hij zijn pols gebroken had, en dit foute antwoord met de linkerhand had uitgerekend.)
Bij een programmeertaal zoals Algol-60 die call-by-name toelaat
is het onmogelijk om statisch (tijdens het vertalen) te beslissen
of een programma syntactisch correct is: de aanroep square(7)
is incorrect - je kunt geen assignment 7 := 49 uitvoeren - maar
het is onbeslisbaar of tijdens de executie van een programma
de procedure square ooit met het constante argument 7
aangeroepen zal worden (want procedure identifiers en argumenten
kunnen op onnaspeurbare wijze doorgegeven worden).
[We gebruikten dan ook syntactisch incorrecte Algol programma's, met array identifiers die voorzien werden van het verkeerde aantal subscripts, om in te breken in het Algol systeem van het Mathematisch Centrum, en stukken machinetaal naar eigen keuze uit te voeren.]
Kijk nog eens naar Man-or-Boy. De procedure A wordt aangeroepen met zes parameters. De eerste is de gewenste recursiediepte k. Is die 0 dan wordt de som x4+x5 van de laatste twee parameters afgeleverd. Is k groter dan nul dan wordt de locale procedure B aangeroepen. Deze procedure B roept A weer aan, met een gewenste recursiediepte die 1 lager is, en verschoven argumenten, waarbij B zelf argument wordt. Een aantal recursiestappen later zijn verschillende incarnaties van B argumenten van A. Bij het evalueren van B (als B terechtkomt in x4 of x5 en dus om een waarde gevraagd wordt via A := x4+x5) spelen de variabelen x1, ..., x5 een rol, en wel die incarnaties van die variabelen die geldig waren op het moment dat B werd meegegeven in de aanroep A(k,B,x1,x2,x3,x4,x5).
Dit wordt deep binding genoemd: bij deep binding wordt bij het doorgeven van een procedureidentifier als parameter de hele omgeving van die procedureidentifier meegesleept, zodat als de procedure later aangeroepen wordt de variabelen in de proceduretekst de referentiewaarde hebben die ze op het moment van doorgeven hadden.
Ook LISP heeft call-by-name, maar gebruikte (in de oorspronkelijke versie) shallow binding: de namen in de tekst van de procedure refereren aan waarden zoals passend op het moment dat de procedure wordt aangeroepen. Dit betekent dat een identifier gewoon meegegeven kan worden bij een aanroep zonder begeleidende administratie over het recursieniveau waar hij van afkomstig is.
Is LISP (in de oorspronkelijke versie) in dit opzicht eenvoudiger, de definitie van scope in ingewikkelder dan die bij Algol. In een Algol programma, net als in een C programma, is uit de programmatekst duidelijk welke declaratie in de programmatekst hoort bij een voorkomen van een variabele. Dit heet statische scope. In een LISP programma heerste dynamische scope: nieuwe bindingen (identifier,waarde) werden bij een functieaanroep vooraan de lijst met associaties gezet, en als van een variabele de waarde nodig was werd de lijst van voor naar achter doorzocht, zodat de meest recente (diepst geneste) versie van de variabele gebruikt werd. Dit is een heel ongelukkig systeem, want bij het lezen van de tekst van een procedure is niet duidelijk wat de betekenis van de variabelen is. Met dynamische scope als geschetst zou het C programma hierboven 2 2 3 2 2 afdrukken.
Globaal genomen is call-by-name een mislukking, al te gecompliceerd. Maar call-by-value is te beperkt. Soms moet inderdaad een argument van de aanroep door de aanroep gewijzigd worden. Een standaard voorbeeld is de procedure verwissel:
PROCEDURE swap(x,y); INTEGER x, y; BEGIN INTEGER t; t:=x; x:=y; y:=t END;
Bij call-by-reference wordt niet de waarde maar de verwijzing naar de variabele doorgegeven, zodat de procedure werkt met dezelfde variabelen als de aanroepende omgeving (en niet met copieen).
We zeiden dat C strict call-by-value was. Maar aan de andere kant is dit effect moeiteloos te bereiken, want ook pointers (verwijzingen) zijn waarden, en ik kan schrijven
swap(int *x, int *y) { int t; t = *x; *x = *y; *y = t; }
Ons doel is om de werking van een procedure te doorgronden door de tekst van die procedure te lezen, zonder het hele omringende programma te hoeven kennen. Dat werkt voor call-by-value. Maar call-by-reference heeft problemen. Een routine als
translate(x,y,a,b) { x := x+a; y := y+b; }
in een call-by-reference omgeving, lijkt het punt (x,y) te verschuiven over de vector (a,b). Maar bij een aanroep
x := 5;
y := 0;
translate(x,y,x,x);
wordt niet (5,0)+(5,5)=(10,5) uitgerekend; we vinden als resultaat (10,10). Dit alias-probleem, dat verschillende namen in feite dezelfde variabele kunnen voorstellen, maakt procedures onleesbaar. Een manier om het te vermijden is een combinatie van call-by-value en call-by-reference die wel call-by-copy genoemd wordt: bij de aanroep van de procedure gaat alles als bij call-by-value; de procedure werkt met locale copieen van de variabelen, maar bij het verlaten van de procedure worden deze locale copieen weer teruggecopieerd naar de variabelen in de aanroep.
Een voordeel van call-by-name is dat als een argument bij een functieaanroep een ingewikkelde expressie is, en de functie gebruikt die waarde in het geheel niet, dan wordt die expressie ook niet geevalueerd. Aan de andere kant, als die waarde twee keer gebruikt wordt, dan wordt die expressie ook twee keer geevalueerd. Soms is dat juist de bedoeling, zoals bij Jensen's device, maar meestal is dat gewoon inefficient. Lazy evaluation is een vorm van call-by-value waarbij de waarde niet bij de aanroep wordt uitgerekend, maar pas als hij voor het eerst nodig is. (En als hij dan nodig is, en het is een samengestelde waarde, dan wordt precies genoeg uitgerekend om te voldoen aan wat nodig is.) Functionele programmeertalen zoals Miranda en Haskell volgen dit idee.
Bij een commandotaal als Algol of C zijn de variabelen eigenlijk geheugenadressen. Een opdracht x := 1 betekent dat de waarde 1 opgeborgen moet worden in het hokje dat x heet. In een functionele programmeertaal zijn de variabelen geen namen van geheugenplaatsen, met dynamisch varierende inhoud, maar namen van waarden die uitgerekend kunnen worden, en in principe constant zijn. Assignment komt niet voor, en functies hebben geen neveneffecten.
Hoe zit dit bij Mathematica en Maple en Macsyma?
Mathematica benadert het idee van een functionele taal een beetje, maar er zijn allerlei troebele details.
Mathematica evalueert in principe eerst de functienaam, en dan de argumenten van die functie, en roept tenslotte de functie aan.
Is de waarde van een variabele bekend, dan wordt die waarde voor de variabele gesubstitueerd, en we hebben een soort call-by-value idee. Toch is het mogelijk dat een functieaanroep een parameter wijzigt:
In[1]:= MaakNul[x_]:=(x:=0)
In[2]:= a
Out[2]= a
In[3]:= MaakNul[a]
In[4]:= a
Out[4]= 0
In[5]:= b:=a
In[6]:= MaakEen[x_]:=(x=1)
In[7]:= MaakEen[b]
Set::setraw: Cannot assign to raw object 0.
In[8]:= b=1
Out[8]= 1
In[9]:= c:=d
In[10]:= MaakNul[c]
In[11]:= d
Out[11]= 0
Waarschijnlijk is het het beste dit op te vatten als pure call-by-value, waarbij in het geval van een ongedefinieerde variabele zeg a, die a zichzelf als waarde heeft.
Er zijn allerlei manieren om dit eenvoudige model wat aan te passen.