T3 in het wild While ‘ ’ Juni 2004 Tom de Valk Tom Evers Sjors Meekels
0115665 0115525 0138630
INHOUDSOPGAVE Inleiding ............................................................................................................................. 2 1.
WHILE ‘OO’............................................................................................................. 3 1.1 Afbakening.......................................................................................................... 3 1.2 Uitbreidingen...................................................................................................... 3 2. Syntax ......................................................................................................................... 4 3.
Semantiek................................................................................................................... 5 3.1 States en environment ......................................................................................... 5 3.1.1 State............................................................................................................. 5 3.1.2 Envp ............................................................................................................. 6 3.1.3 Envdo ............................................................................................................ 6 3.1.4 Heap ............................................................................................................ 7 3.1.5 Envthis .......................................................................................................... 8 3.2 Uitbreiding van de Semantiek van A & B .......................................................... 8 3.3 State transitie....................................................................................................... 9 3.4 Update object declaratie ...................................................................................... 9 3.5 State transitie bij object initialisatie .................................................................. 10 3.6 NS Semantiek .................................................................................................... 12 3.7 Voorbeeld .......................................................................................................... 13
4.
Inheritance ............................................................................................................... 14 4.1 Syntax................................................................................................................ 14 4.2 Semantiek.......................................................................................................... 15 4.2.1 Envdo uitbreiden ........................................................................................ 15 4.2.2 Update functie ........................................................................................... 15 4.3 Object Initialisatie............................................................................................. 17 4.4 Semantiekregels ................................................................................................ 18 4.5 Voorbeeld .......................................................................................................... 19
5.
Keywords Public & Private .................................................................................... 20 5.1 Syntax uitbreiding............................................................................................. 20 5.2 Semantiek.......................................................................................................... 21 5.3 Semantiekregels ................................................................................................ 23
6.
Geneste objecten...................................................................................................... 24 6.1 Syntax................................................................................................................ 24 6.2 States en environment ....................................................................................... 24 6.3 Semantiek.......................................................................................................... 25
Conclusie .......................................................................................................................... 26
T3 in het Wild
While
1
Inleiding De bedoeling van dit werkstuk is dat we semantische technieken kunnen ontwikkelen en toepassen “in het wild”. Het onderwerp dat we gekozen hebben, is het uitbreiden van de taal While met een aantal typische Object Oriented (OO) onderwerpen. Deze nieuwe taal hebben we de naam While ‘OO’ gegeven. While ‘OO’ is geen OO-taal in zuivere zin, maar meer de taal While met OO aspecten. We leggen de syntax en ns-semantiek van objecten en klassen vast. In de syntax wordt het declareren van objecten al sterk aan banden gelegd, dit is namelijk alleen mogelijk aan het begin van het programma. Bovendien is het niet toegestaan klassen in klassen te declareren, om het niet meteen te moeilijk te maken. Vervolgens gaan we de ns-semantiek vastleggen. Dit houdt onder andere in dat de state wordt uitgebreid, er update functies worden toegevoegd en de ns -semantiek regels worden aangepast. Nadat we deze implementatie van While ‘OO’ hebben gerealiseerd, wordt er ingegaan op een ander typisch OO onderwerp, namelijk inheritance. Deze uitbreiding van While ‘OO’ wordt in een apart hoofdstuk gedaan, omdat het anders te onoverzichtelijk wordt. Andere typische OO onderwerpen zoals klassen declareren in klassen (nesting van klassen) en de keywords ‘public’ en ‘private’ zullen we minder uitgebreid behandelen. Dit houdt in dat we de syntax en ns-semantiek niet exact zullen vastleggen, maar wel globaal bespreken hoe deze onderwerpen in While ‘OO’ verwerkt kunnen worden. Concreet gezegd gaan we dus onderzoek doen naar de uitbreiding van de syntax en semantiek van de taal While met OO aspecten, te weten object declaraties en object instantiaties en we beschrijve n de benodigdheden voor inheritance en geneste klassen.
T3 in het Wild
While
2
1.
WHILE ‘OO’
1.1
Afbakening
Het uitbreiden van While kan op meerdere wijzen geïmplementeerd worden. Om het overzichtelijk te houden tijdens de beginfase, hebben wij ervoor gekozen om het declareren van objecten alleen toe te staan in het begin van het programma. Een ander belangrijk gevolg van deze keuze is de onmogelijkheid om objecten in objecten te declareren. Beide gevolgen zijn een inbreuk op de zuivere OO gedachte, echter er blijft voldoende expressieve kracht over om van een OO taal te spreken. Andere mogelijke uitgangspunten voor implementaties zouden kunnen zijn: Alles in objecten te zetten, dit impliceert dat alle variabelen en procedures dus ook in een object zitten. Verder houdt dit in dat elke programma dus een object is en er ergens een start (soort main () functie ) aanwezig dient te zijn. We hebben ervoor gekozen om hier niet voor te kiezen maar de taal While ‘OO’ (backwards)compatible te maken met While.
1.2
Uitbreidingen
Op de eerste plaats hebben wij de aritmetische expressie uitgebreid met de velden van een object. Zodoende kan een veld gebruikt worden als zijnde een ‘normale’ aritmetische expressie. Dit is nodig om bijvoorbeeld de waarde van een veld aan een variabele toe te kennen of om de waarde van een veld aan te passen. Omdat wij een onderscheid maken tussen gedeclareerde en geïnstantieerde objecten is het ook nodig om dit verschil te kunnen maken bij het gebruik van velden. Hiervoor hebben wij de object.veldnaam en this.veldnaam geïntroduceerd. Deze gebruiken we respectievelijk bij een geïnstantieerd en een gedeclareerd object. In de syntax worden ze beschreven met o.v en this.v. De this.veldnaam constructie is een speciaal geval van object.veldnaam en heeft alleen betekenis binnen de declaratie van een object. (in Do ). Hierdoor is het mogelijk om naar procedures en velden te verwijzen in het huidige object voordat deze daadwerkelijk geïnstantieerd is. Het afdwingen van de declaratie van objecten aan het begin van een programma hebben wij geïmplementeerd met een apart statement R die vooraf gaat aan de originele S. In deze R kunnen vervolgens objecten worden gedeclareerd, dit is echter niet noodzakelijk, het laatste onderdeel van R is de normale S. Hierdoor zijn alle mogelijkheden van traditioneel While direct overgenomen. Objecten worden op een gelijke wijze gedeclareerd als bijvoorbeeld procedures. Het is een eindige rij met object declaraties, zie de definitie van Do .
T3 in het Wild
While
3
2.
Syntax
De syntax met de besproken uitbreidingen komt er nu zo uit te zien: a::=
n | x | a1 + a2 | a1 * a2 | a1 – a2 | o.v | this.v
R::=
begin Dv Dp Do Dd S end
S::=
x:= a | skip | S1 ; S2 | if b then S1 else S2 | while b do S | begin Dv Dp Dd S end | call p | call o.p | call this.p | o.v := a | this.v := a
Dv ::= var x := a ; Dv | e Dp ::= proc p is S ; Dp | e Do ::= class O is Dv Dp ; Do | e Dd ::= object o : = new O ; Dd | e De O is een metavariabele die de type van objecten beschrijft. (O type) o is een metavariabele die de namen van objecten beschrijft. (Oname ) Do is een metavariabele die de declaratie van objecten beschrijft. De v in o.v en this.v is een metavariabele die de namen van velden van objecten beschrijft. Dd is eveneens een metavariabele die de instantiatie van objecten beschrijft binnen een Begin – End block. De aparte metavariabele voor instanties is noodzakelijk om de instanties te kunnen ‘opruimen’ bij het verlaten van de scope. (zie definities van Block)
T3 in het Wild
While
4
3.
Semantiek
Het is nuttig eerst een functie te definiëren die uit een tupel (of een rij) een zeker element haalt. In de volgende paragrafen zal blijken dat deze functie bestaansrecht heeft. Projectiefunctie: pi (x0 ,x1..xn ) = xi
3.1
States en environment
Zoals gezegd en gezien is de syntax aangepast, dit heeft natuurlijk ook invloed op de benadering van state en environment. Wij maken onderscheid tussen een vijftal onderdelen. § De ‘normale’ State, met hierin de globale variabelen § De ‘normale’ Envp , met hierin de globale procedures § Een speciaal environment envdo , hierin worden alle gedeclareerde objecten opgeslagen, inclusief de procedures en velden. § Een heap waarin de geïnstantieerde objecten worden opgeslagen. Van deze objecten hebben wij alleen de naam nodig en de velden. § Een speciaal environment (veld) envthis, waarin we de objectnaam opslaan waar we op dat moment in bezig zijn. We zullen de bovenstaande aanpassingen stuk voor stuk bespreken en nader toelichten met voorbeelden.
3.1.1 State De standaard State zullen we gewoon blijven gebruiken. Deze kan zowel in R als in S uitgebreid worden met nieuwe variabelen. Semantisch is er geen verschil tussen gebruik in R en S, echter bij gebruik in R kunnen de variabelen ook al gebruikt worden in de object declaraties in R. Zo kunnen objecten ook gebruik maken van globale variabelen. Formeel gezien geldt nog steeds de volgende formule met een schets van het geheugen gebruik: State : Vname à Z
X
3
Y
5
..
..
De totale functie State levert dus altijd een waarde uit het bereik van Z op.
T3 in het Wild
While
5
3.1.2 Envp Ook de Envp zal niet worden gewijzigd, ook hier geldt dat hij in zowel R als in S kan worden uitgebreid. Hierin worden alle procedures opgeslagen die niet voorkomen in een object (dit wordt later behandeld). Formeel levert dit wederom de volgende functie en schets op: Envp : Pname à Stm
P
P body
Q
Q body
..
..
De partiële functie envp levert niet altijd een resultaat op, omdat deze een Statement op moet leveren. Indien de Pname niet voorkomt in envp is de kans groot bij een concrete implementatie dat er naar een waarde wordt gewezen die niet is te interpreteren als zijnde een geldig Statement.
3.1.3 Envdo We houden een extra (static) environment bij waarin we alle gedeclareerde objecten opslaan, Envdo (Declared Objectes). Deze kunnen alleen in R worden gedeclareerd. Na de declaratie van de objecten zal dit environment niet meer veranderen. Hierin worden de initialisatie waarden voor de velden en body’s van de procedures opgeslagen. Formeel gezien: Envdo : Otype à (State x Envp )
O1
O2
X 3
P
body
Y 5
q
body
X
P
body
1
Voorbeeld 3.1: … class O n is var x:= 3; var y:= this.x + 1; proc p is q:= 3; … Door de bovenstaande klasse declaratie wordt de envdo uitgebreid met het volgende tupel: De y wordt eerst geëvalueerd en vervolgens in het environment opgeslagen, dit wordt nader besproken in 3.4. On
x 3
p
q:= 3;
y 4
T3 in het Wild
While
6
3.1.4 Heap Alle instantiaties van gedeclareerde objecten slaan we op in een heap h. Het instantiëren van objecten gebeurt alleen in S. Het verschil met de Envdo is dat de velden van de objecten kunnen veranderen naar aanleiding van Statements die worden uitgevoerd op deze velden. In tegenstelling tot de Envdo waar de waardes van de velden niet meer veranderen na declaratie. Verder onderscheid is het ontbreken van de body’s van de procedures in de heap. Deze kunnen worden opgezocht in de Envdo, wanneer er een call wordt aangeroepen. Door middel van de O name kan worden beoordeeld van welk type het object is en welke procedures dit type heeft. Dit levert een besparing op van het geheugengebruik omdat alle procedures maar op één plek worden opgeslagen. Formeel gezien: h : Oname à (Otype x State) o1
O2
X 1
o2
O1
Y 6 X 3
Omdat de heap kan worden gezien als een resultaat van het programma hebben we besloten de heap te besc houwen als een state in plaats van een environment. Voorbeeld 3.2 : .. class O n is var x:= 3; var y:= this.x + 1; proc p is q:= 3; object o:= new O n; .. Bovenstaande toevoeging levert de volgende heap op: o
T3 in het Wild
On
x 3 y 4
While
7
3.1.5 Envthis Tot slot slaan we het huidige object waarin gewerkt wordt op in Envthis. Zodoende kunnen we na elke call op een object procedure precies terugvinden in welke object we werken. Bij het uitvoeren van een Statement van een object procedure kunnen we nu de this.veldnaam en of this.procedurenaam evalueren. Na het uitvoeren van een call staat de envthis weer op de waarde voorafgaand aan de call. (zie ook updthis) Envthis : Oname Voorbeeld 3.3: .. class O n is var x:= 3; var y:= 4; proc p is this.y := 1; object o:= new O n; call o.p; .. Bij de aanroep van o.p is bekend dat o het huidige object is en zodoende kan dus de procedure p worden uitgevoerd en de y-waarde van de instantie o in de heap op 1 worden gezet.
3.2
Uitbreiding van de Semantiek van A & B
Het is noodzakelijk dat we de semantiek van aritmetische expressies (A) aanpassen aan de uitbreiding van de syntax van a. De heap en envthis zijn namelijk nodig voor het evalueren van de expressies o.v en this.v. Signatuur: A: Aexp à ( State x heap x envthis à Z ) We schrijven één regel van de bestaande regels uit, de overige laten we aan de verbeelding van de lezer over. A [n] s h envthis = N [n] De volgende regels hebben we toegevoegd: A [o.v] s h envthis = p1 (h o ) v A [this.v] s h envthis = p1 (h envthis ) v
T3 in het Wild
While
8
Nu rest ons nog de aanpassing van de booleaanse expressies (B), die natuurlijk verandert aangezien de signatuur van A is veranderd en deze afhankelijk is van A. Signatuur: B: Bexp à ( State x heap x envthis à T ) We schrijven wederom één bestaande regel uit. B [ a1 = a2 ] s h envthis
3.3
{ {
tt if A [ a1 ] s h envthis = A [ a2 ] s h envthis ff if A [ a1 ] s h envthis ? A [ a2 ] s h envthis
State transitie
Aangezien de toegevoegde environments en de heap ook dienen te worden verwerkt in de state overgangen hebben wij de oude state transitie gemodificeerd. De aangepaste state transitie ziet er als volgt uit: envthis, envdo , envp + < S , s, h > à ( s’, h’)
3.4
Update object declaratie
In deze paragraaf zullen we de update functies behandelen die ervoor zorgen dat de environments ook daadwerkelijk worden aangepast bij object declaraties. Update van de envdo , bij het declareren van objecten (in Do in R): upddo ( class O is Dv Dp ; Do, envdo , stateg 1 ) = upddo (Do , envdo [ O ( updv ( Dv , lege state,stateg, O) , updp ( Dp, lege envp ) ) ], state g ) upddo (e, envdo ,stateg ) = envdo In bovenstaand gedeelte maken we gebruik van de functie updv die de velden van het gedeclareerde object instelt op de begin waarde en de functie upd p die de procedures in de environment opslaat. Updp heeft de “vertrouwde” vorm zoals bekend is van While. Update van de initiële waarden van de velden in envdo : updv (var x:= a; Dv , state ,stateg, Ocur ) = updv (Dv , state [x envthisleeg],stateg, O cur ) where t = a [ this.v p0 (envdo O cur ) v ] 1
A[t ]stateg hleeg
stateg = de globaal bekende state (s)
T3 in het Wild
While
9
updv (e, state,stateg, O cur ) = state Opmerking: t is de Aexp a met daarin alle voorkomens van this.v’s vervangen door de numerieke waarde van v in het huidige object (O cur) dat nu in de declaratie fase is. Update van de procedures in envdo : updp (proc p is S; Dp , envp ) à updp (Dp , envp ) updp (e, envp ) = envp Tenslotte moeten we de envthis kunnen aanpassen. Hiervoor introduceren we de triviale functie updthis . Update van envthis: updthis ( Oname, envthis) = envthis
3.5
Oname
State transitie bij object initialisatie
Doordat de objectinstantiaties bijdragen tot een verandering van de heap en niet tot een verandering in een environment moeten deze beschreven worden door middel van state transities. Dd ::= object o : = new O ; Dd | e
[objectns]
envdo + < Dd, s, h [ o
( O, t) ] > à d (s, h’) where t = p0 (envdo O)
envdo + < object o := new O ; D d, s, h > à d (s , h’)
[noneobjc ns ]
< e , s , h > à d ( s,h) envdo dwingt af dat er geen objecten geïnstantieerd kunne n worden die niet gedeclareerd zijn. Dit komt doordat het een partiële functie is. Alle objecten die geïnstantieerd worden moeten dus voorkomen in envdo . Nu moet er nog een nieuwe functie worden geïntroduceerd die de geïnstantieerde objecten opruimt. De functie DD(Dd):
T3 in het Wild
While
10
DD( object o := new O; D d) = { o } U DD(Dd ) DD( e ) = ø Deze functie draagt zorg voor het terugzetten van object instantiaties naar oude waarde bij het verlaten van de huidige scope (block). Zie ook de definitie van blockns en R blockns. We hebben in paragraaf 3.2 de semantiek van A aangepast. Dit leidt ertoe dat we de transitie van D v ook iets dienen aan te passen. Transitie van Dv in state g : [varns]
< Dv , s [x
A [a] s h ], h > à v (s’, h)
< var x := a ; Dv, s, h > à v (s’ , h)
[nonevarns ]
< e , s , h > à v ( s,h) Aangezien de state s wordt aangepast bij het verwerken van Dv hebben we besloten om hier ook een state transitie te gebruiken in plaats van een update functie, zoals updv waarbij de env do wordt aangepast. De functie DV(Dv) zullen we niet uitschrijven, aangezien er niks veranderd is.
T3 in het Wild
While
11
3.6
NS Semantiek
Hieronder volgen de toegevoegde semantiekregels, de regel [skip ns] hebben we uitgeschreven om aan te geven hoe de overige regels eruit komen te zien. Behalve de signatuur verandert daar verder niks wezenlijks aan. [R blockns ]
< Dv , s, h> àv (s’,h) , updp (Dp , envp ) , upddo (Do , envdo , s) + < D d , s’ , h > àd ( s’ , h’ ), envthis , envp , envdo + < S , s’, h’ > à ( s’’, h’’) envthis, envp , envdo + < Begin Dv D p Do D d S End, s , h > à (s’’ [DV(Dv )às] , h’’[DD(Dd)àh] )
[S blockns ]
< D v , s, h> à v (s’,h) , updp (Dp , envp ) ,envdo + < D d , s’ , h > à d ( s’ , h’ ), envthis, envp , envdo + < S , s’, h’ > à ( s’’, h’’) envthis, envp, envdo + < Begin Dv Dp Dd S End, s , h > à (s’’ [DV(Dv )às] , h’’[DD(Dd )àh] )
[call o.p ns]
envdo ,updthis (o, envthis), envp envdo , envthis, envp
+ < S, s, h> à ( s’, h‘ )
+ < call o.p, s , h > à ( s’, h’ )
envdo , envthis, envp + < S, s, h> à ( s’, h‘ ) [call this.pns]
where S = p1 (env do p0 (h o ) ) p
where S =
p1 (env do p0 (h envthis ) ) p
envdo , envthis, envp + < call this.p, s , envdo , envthis, envp h > à ( s’, h’ )
[ass this.vns]
envdo , envthis, envp + < this.v := a, s, h > à ( s, h[p1 (h envthis ) v à A[a] s h envthis] )
[ass o.vns]
envdo , envthis, envp + < o.v := a, s , h > à ( s, h[p1 (h o) v à A[a] s h envthis] )
[skip ns]
envdo , envthis, envp + < skip, s, h > à ( s, h )
T3 in het Wild
While
12
3.7
Voorbeeld
begin 1 class O is var y:=1 ; proc p is this.y:= this.y + 2; 2
object o1 = new O;
3
call o1.p ;
4
x := o1.y;
5
end
Het resultaat hiervan is dat x de waarde 3 krijgt/ heeft. Ad regel 1: Class O wordt gedeclareerd en toegevoegd aan de envdo . envdo [ O ( y 1, p this.y:= this.y + 2; ) ] Ad regel 2: Object o1 wordt geïnstantieerd met de velden van O en wordt toegevoegd aan de heap. h [ o1 (O , y 1) ] Ad regel 3: De body wordt uitgevoerd met this vervangen door de update waarde van envthis: o1.y := o1.y +2 ; Resultaat van dit statement is dat het veld o1.y ingesteld wordt op 3, in de heap. envthis h [ o1
o1 (O , y
3) ]
Ad regel 4: De waarde van het veld o1.y wordt toegekend aan x. s [x
3]
Ad regel 5: Alle geïnstantieerde objecten (o1) worden teruggezet op hun oorspronkelijke waarde.
T3 in het Wild
While
13
4.
Inheritance
Er zijn ve rschillende manieren om inheritance (overerving) van klassen te implementeren. Een manier is om in een subklassen alle velden en procedures (methoden) van de superklasse(n) te kopiëren, zodat er precies kan worden gezien welke velden en procedures er gebruikt kunnen worden. Gedeclareerde velden en procedures in de subklassen worden hier dan ook toegevoegd en als er dan velden en/of procedures opnieuw worden gedeclareerd (door middel van dezelfde naam als in de superklasse), wordt het veld of procedure van de superklasse overschreven. Het nadeel van deze implementatie is dat het nogal veel geheugengebruik heeft. Een andere manier van implementatie is dat er geen informatie van superklasse(n) in een subklasse wordt gekopieerd. Wanneer er dan een veld op procedure wordt aangeroepen, wordt eerst gekeken of dit voorkomt in de subklasse. Als dit niet het geval is, wordt er teruggezocht in de superklasse en dit patroon kan zich dus herhalen als er meer superklassen zijn. Hier is er geen sprake van overhead in het geheugengebruik. Hierbij is het eleganter dat de velden van de superklasse(n) in de subklasse gekopieerd worden (al dan niet overschreven), omdat dan de object initialisatie hetzelfde blijft. Deze tweede implementatie is mooier dan de eerste en we proberen dus ook deze implementatie te realiseren in het vervolg van dit hoofdstuk.
4.1
Syntax
Als eerste zal de syntax van While ‘OO’ moeten worden uitgebreid. Dit kan eenvoudig door alleen Do aan te passen: Do ::= class O is Dv Dp ; Do | class O is subclass Osuper Dv Dp ; Do | e Waar Osuper de superklasse is, waarvan overgeërfd wordt.
T3 in het Wild
While
14
4.2
Semantiek
In de semantiek zal meer aangepast moeten worden, de Envdo wordt namelijk uitgebreid. Dit heeft het gevolg dat de grootste veranderingen in de update functie van Envdo zullen zitten.
4.2.1 Envdo uitbreiden Bij elk gedeclareerde object moet nu ook een eventueel Otype van de superklasse bijgehouden worden, zodat bij een procedure aanroep er ‘omhoog’ gezocht kan worden in de klassenstructuur naar deze procedure. Formeel gezien: Envdo : Otype à (Otype x State x Envp )
O type O1
O2
Voorbeeld 4.1: .. class O 1 is
class O2 is subclass O1
O type e O1
State
Envp
X 3
P
body
Y 5
q
body
X
1
P
body
Y
5
var x = 3; var y = 5; proc p is this.x = 5; proc q is this.y = 3; var x = 1; proc p is this.x = 3;
object o2 := new O2; call o2.q; .. Deze aanroep is dus correct en zal de procedure q uit klasse O1 uitvoeren en zal dus de waarde van y in klasse O2 op 3 zetten..
4.2.2 Update functie Als eerste zal een klasse, die geen subklasse is, worden herschreven: upddo ( class O is Dv Dp ; Do, envdo , stateg) = upddo ( class O is subclass e Dv Dp ; Do , envdo , stateg)
T3 in het Wild
While
15
Hierdoor kan de echte update in de onderstaande regel worden gedaan. Hier worden ook twee hulpfuncties geïntroduceerd, namelijk updp en updv . De functie updp verandert niet, maar het opzoeken van procedures zal later nog behandeld worden. upddo ( class O is subclass Osuper Dv Dp ; Do, envdo , stateg) = upddo (Do , envdo [ O ( O super , updv ( Dv , lege state, stateg, O, O super) , updp ( Dp , lege envp ) )], stateg ) Als Do leeg is, wordt de geupdate envdo opgeleverd: upddo (e, envdo ,stateg ) = envdo De functie updv: Omdat de velden van alle superklassen overgeërfd moeten worden, gaan we alle velden van de superklassen kopiëren. Om ervoor te zorgen dat overschrijving van velden wel mogelijk is, zullen we recursief naar de top/root/pater familias-klasse zoeken en vervolgens op de ‘terugweg’ alle velden kopiëren naar de nieuw te declareren klasse. Op deze wijze worden velden die door een superklasse zijn aangemaakt, indien nodig overschreven door de declaratie waarden van subklassen. Schematisch:
T3 in het Wild
While
16
Het algoritme voor de updv functie in pseudo-code: functie update (O cur, O super) { if (O super = = leeg) //root is leeg voegtoe_Dv (O cur ) else //root is niet leeg update (O super , O super’) //recursie voegtoe_Dv (O cur) //backtracking } functie voegtoe_Dv (Ocur ) { if (Dv van O cur = = leeg) return //Dv leeg, dan stoppen else voeg eerste element van Dv van Ocur toe aan de nieuwe state voegtoe_Dv (Dv van Ocur zonder eerste element) }
Ten slotte de aangepaste upd v functie: updv (var x:=a; Dv, state, stateg, Ocur , e) = updv (Dv, state [x A[t]state g hleeg envthisleeg], state g, Ocur, e ) where t = a [ this.v p1 (envdo O cur ) v ]
//root is leeg //voegtoe_D v
updv (var x:=a; Dv, state, stateg, Ocur , Osuper) = merge (updv (var x:=a; Dv , state, stateg, O super, p0 (envdo O cur)), updv (var x:=a; Dv , state, stateg, O cur , e ) )
//root is niet leeg //recursie //backtracking
updv (e, state, stateg, O cur, e) = state
//Dv leeg, dan stoppen
NB: De functie merge doet het volgende: State1 x State2 à State[ voeg alle variabelen uit State1 samen met alle variabelen uit State2, waarbij indien de variabelenaam in State1 al bestaat deze overschreven wordt door de waarde in State2]
4.3
Object Initialisatie
De object initialisatie verandert niet, omdat we alle velden weer overnemen vanuit de gedeclareerde klasse en we de procedures gaan opzoeken indien er een aanroep (call) wordt uitgevoerd.
T3 in het Wild
While
17
4.4
Semantiekregels
Alle semantiekregels blijven hetzelfde, behalve de [call o.pns] en [call this.pns]. Merk op dat de upd do functie bij de regel [R blockns] de aangepaste functie uit hoofdstuk 5.2.2 is. envdo ,updthis (o, envthis), envp [call o.pns] envdo , envthis, envp
+ < S, s, h> à ( s’, h‘ )
lookUp(p0 (h o), p)
where S =
lookUp(p0 (h envthis), p)
+ < call o.p, s , h > à ( s’, h’ )
envdo , envthis, envp + < S, s, h> à ( s’, h‘ ) [call this.pns]
where S =
envdo , envthis, envp + < call this.p, s , envdo , envthis, envp h > à ( s’, h’ )
De functie lookUp: lookUp: (O type x Pname) à Statement lookUp ( o, p) = If ( ! Exists (p2 (envdo o), p) ) Then lookUp ( p0 (envdo o ) , p) Else p2 (envdo o ) p De functie Exists: Exists: (Envp x Pname ) à Boolean Exists geeft true terug als de Pname in Envp voorkomt en false als Pname niet in Envp voorkomt. NB: Merk op dat p2 (envdo o )p een p kan proberen op te zoeken die niet bestaat. Het is dan niet duidelijk wat de partiële functie Envp gaat opleveren en daarom hebben we de functie Exists geïntroduceerd. Deze functie werken we niet verder uit.
T3 in het Wild
While
18
4.5
Voorbeeld
begin 1 class O1 is var y:=1 ; proc p is this.y:= this.y + 2; 2
class O2 is subclass O1 var x:=2;
3
object o2 = new O2;
4
call o2.p ;
5
y := o2.x;
6
z := o2.y;
7
end
Ad regel 2: class O2 wordt gedeclareerd en toegevoegd aan de envdo . envdo [O2 à (O1, (y à 1 , x à 2), e )] Ad regel 3: Object o2 wordt geinstantieerd met de velden van O1 en O2 en wordt toegevoegd aan de heap: h[ o2 à (O1, (y à 1, x à 2))] Ad regel 4: De body van p wordt opgezocht met de lookUp functie. Deze wordt uit de superklasse O1 gehaald. Resultaat van het statement is dat het veld o2.y ingesteld wordt op 3 in de heap. Ad regel 5: De waarde van o2.x wordt aan y toegekend. Ad regel 6: De waarde van o2.y wordt aan z toegekend.
T3 in het Wild
While
19
5.
Keywords Public & Private
In het kader van dit werkstuk definiëren we de verschillende types velden en procedures als volgt: (conform de definities zoals gebruikt in Java). Public methoden & velden: - mogen buiten het object aangeroepen worden - mogen worden aangeroepen in subclasses van het object Private methoden & velden - mogen alleen worden aangeroepen binnen het huidige object - mogen niet worden aangeroepen binnen subclasses van het object De overige keywords aangaande methoden en velden zullen we buiten beschouwing laten (final, static, friend en dergelijke).
5.1
Syntax uitbreiding
Om de syntax zo overzichtelijk mogelijk te houden en niet te veel af te wijken van het While ‘OO’ hebben we de syntactische uitbreidingen tot een minimum beperkt. Bij het declareren van velden en methoden in klassen geven we enkel een extra indicator mee u (public) of i (private). Deze indicator kan alleen meegegeven worden bij velden en procedures in klassen. Voor reguliere velden en procedures heeft het geen zin deze indicator mee te geven, syntactisch wordt dit afgedwongen door een aangepaste Dv1 en Dp1 voor Do . ind::= u | i Do ::= class O is Dv1 Dp1 ; Do | e Dv1 ::= var ind x := a ; Dv1 | e Dp1 ::= proc ind p is S ; Dp1 | e
T3 in het Wild
While
20
5.2
Semantiek
De State in envdo zal aangepast moeten worden zodat deze een tupel oplevert met de Z waarde en een indicator. Ook de envp zal van een dergelijke constructie worden voorzien: Formeel gezien: State’ : Vname à ( Ind x Z ) Envp ’ : Pname à ( Ind x Stm ) Envdo : Otype à (State’ x Envp ’) Schematisch: O
..
x
u
3
P
i
body
y
i
4
Q
u
body
.
..
..
..
..
..
Voorbeeld 5.1: .. class O n is var i x:= 3; var u y:= this.x + 1; proc u p is q:= 3; … In het bovenstaande voorbeeld maken we een class O aan in envdo met private veld x , public veld y en public methode p. Bij een call o.p zal er alleen nog maar worden gezocht naar de public procedures ( welke dus een u indicator hebben). Zodoende kunnen er dus geen private procedures worden aangeroepen buiten de class. Voor de o.v geldt hetzelfde natuurlijk hetzelfde. Bij een this.v of een this.p is dit niet nodig omdat hier sprake is van een aanroep vanuit de class en dan mogen zowel private als public methoden / velden gebruikt worden. Overerving & public, private Indien er sprake is van overerving van classes zullen we een extra probleem moeten tackelen: subclasses erven geen private velden en methoden over. De oplossing voor de velden is eenvoudig, de nieuw geïntroduceerde updv zal alleen nog maar de public velden van alle superclasses moeten kopiëren naar de State van een nieuwe subclass in envdo , bij een object declaratie. Bij de initialisatie kunnen vervolgens weer alle velden in de heap worden gezet, dit zijn immers toch alle public velden.
T3 in het Wild
While
21
Bij de aanroep van procedures wordt het complexer, de lookUp functie zal bij een call o.p de gevraagde procedure opzoeken. Er mag alleen gekeken worden naar public procedures, private procedures mogen alleen in de class worden aangeroepen. De functie lookUp2 : lookUp2 : (Otype x Pname) à Statement lookUp2 ( o, p) = If ( ! Exists (p2 (envdo o), p)) Then lookUp 2 ( p0 (env do o ) , p) Else If ( isPublic (p2 ( envdo o), p )) p1 (p2 (envdo o ) p) De functie isPublic: isPublic: (Envp x Pname ) à Boolean isPublic geeft true terug als de Procedure p in Envp public is (de u indicator heeft) en false indien deze private is (i indicator). Indien call this.p wordt gebruikt zal eveneens de functie moeten worden opgezocht. Hier moet echter onderscheid gemaakt worden tussen een aanroep in een subclass of de originele class. Bij een subclass mogen geen private functies van de superclass worden aangeroepen. Om dit op te lossen kan een aparte lookUp3 gedefinieerd worden. Deze maakt geen onderscheid maakt tussen private en public procedures indien er niet gezocht hoeft te worden. Dit houdt in dat de functie in de eigen class is gedeclareerd en deze dus altijd aangeroepen mag worden. Indien de functie opgezocht moet worden in superclasses moet wel weer gecontroleerd worden, hiervoor kan de oude lookUp 2 voor gebruikt worden. De functie lookUp3 : lookUp3 : (Otype x Pname) à Statement lookUp3 ( o, p) = If ( ! Exists (p2 (envdo o), p)) Then lookUp 2 ( p0 (env do o ) , p) Else p1 ( p2 (envdo o ) p)
T3 in het Wild
While
22
5.3
Semantiekregels
Het enige dat verandert aan de semantiekregels is de wijze waarop de procedurebody wordt opgezocht. envdo ,updthis (o, envthis), envp [call o.p ns ]
envdo , envthis , env p
+ < S, s, h> à ( s’, h‘ ) where S = lookUp 2 ( p 0 (h o ) p)
+ < call o.p, s , h > à ( s’, h’ )
envdo , envthis , env p + < S, s, h> à ( s’, h‘ ) [call this.p ns ]
where S= lookUp 3 ( p0 (h env this ) p)
envdo , envthis , env p + < call this.p, s , env do , envthis , env p h > à ( s’, h’ )
T3 in het Wild
While
23
6.
Geneste objecten
In onze eerste implementatie hebben we ervoor gekozen om alleen aan het begin van het programma object declaraties toe te staan. Dit leidde ertoe dat er geen objecten gedeclareerd konden worden in een object. Dit is iets wat in een gangbare OO taal wel kan. Vandaar dat we in dit hoofdstuk de extra moeilijkheden zullen beschrijven die deze uitbreiding met zich mee brengt. We zullen tevens een aanzet geven tot een concrete uitwerking ervan. Hetzelfde zullen we doen voor het instantiëren van objecten in objecten. Denk hierbij aan een Java klasse waarin als veld een andere klasse zit.
6.1
Syntax
De R regel in de syntax die we in hoofdstuk 2 hebben toegevoegd kan uit de syntax verdwijnen. De S verandert iets: S::=
… | begin D v Dp Do Dd S end | …
We hebben ervoor gezorgd dat er in een Statement nu dus ook objecten kunnen worden gedeclareerd. Dit heeft echter enkele verdere gevolgen voor de syntax. Je wilt deze geneste objecten ook kunnen benaderen. Er moet dus bijvoorbeeld een call o.o.o.p mogelijk worden gemaakt. Maar ook een call this.o.o.p Hiervoor introduceren we een semantische regel O* . Deze regel produceert een reeks van nul of meer o. ‘s: O* ::= o.O* | e De regel kunnen we als het volgt in de andere syntax regels verwerken: a::=
….. | o.O*v | this.O*v
S::= …. | call o. O*p | call this. O*p | o. O*v := a | this. O*v := a Voor het instatiëren van objecten in objecten moeten we ervoor zorge n dat de regel Do worden aangepast zodat hierin ook object instantiaties kunnen voorkomen: Do ::= class O is Dv Dd Dp ; Do | e
6.2
States en environment
We hebben er nu voor gezorgd dat syntactisch objecten in objecten kunnen worden gedeclareerd en geinstantieerd. We zullen hiervoor extra informatie moeten bijhouden in de states en evironments.
T3 in het Wild
While
24
Allereerst zal voor het bijhouden van geneste object declaraties de envdo worden veranderd. Elk gedeclareerd object heeft nu een eigen lokale env do van objecten die in hem zijn gedeclareerd. De signatuur verandert dus als volgt: Envdo : Otype à (State x Envp x Envdo ) Een soortgelijke aanpassing is nodig voor de heap. Er moet in de heap nu bij elk geïnstantieerd object ook een lokale heap worden toegevoegd. In de geneste heap worden de geïnstantieerde objecten in dit object opgeslagen. De signatuur van de heap verandert als volgt: h : Oname à (Otype x State x h) De update functies zullen nu vanzelfsprekend ook veranderen en worden uitgebreid, maar daar zullen we geen aandacht aan schenken. Het updaten wordt ingewikkelder, maar er verandert niks wezenlijks aan de vorige hoofdstukken. Het zou meer van het zelfde worden.
6.3
Semantiek
We zullen ons wat betreft het uitbreiden van de semantiek vooral richten op het correct afhandelen van de punt operator. Dit aangezien de andere veranderingen vooral gebaseerd zullen zijn op het juist aanroepen van de update functies. Het probleem zit hem in het elegant afhandelen van de O* regel. Deze moet er voor zorgen dat je door de geneste structuur in de heap en de envdo kunt zoeken. Hiervoor zien wij twee mogelijkheden: 1. We kunnen een functie definiëren die onder andere de gehele O* regel als argument mee krijgt. De finesse van het opzoeken verschuiven we op deze manier naar deze functie. Dit werkt in principe natuurlijk prima, maar vinden we niet elegant. 2. Een ander alternatief is dat we een nieuwe environment introduceren die een Oname oplevert. Vergelijkbaar met de envthis. Het idee is dat we deze environment als een soort pointer door de geneste structuur laten lopen bij het van vooraf aan uitlezen van o’s van de O*’s. Uiteindelijk hoef je alleen maar een “functie” te maken die een naam en een pointer naar de geneste structuur meekrijgt en dat wat je zoekt oplevert. Dit laatste vinden we een beter alternatief, omdat je zo tijdens het lezen van de o’s al actie onderneemt. Iets wat je in het echt ook zou doen. Een nadeel is de nieuwe environment, wat op zich geen probleem is, maar die maakt de semantische regels wel een stuk minder leesbaar.
T3 in het Wild
While
25
Conclusie We hebben onderzoek gedaan naar de uitbreiding van de syntax en semantiek van de taal While met OO aspecten, te weten object declaraties en object instantiaties en we hebben de benodigdheden beschreven voor inheritance en geneste klassen. Het blijkt dat het niet eenvoudig is om OO te beschrijven in NS. Dat komt doordat er bij OO een heel samenhangend geheel van concepten komt kijken, zoals inheritence, keywords en geneste klassen. We hebben er eerst voor gekozen om het voor een eenvoudig geval te beschrijven, dat is vrij elegant gelukt. De uitbreidingen zijn echter ingewikkelder. Het blijkt dat er al gauw kunstgrepen worden toegepast zoals het uitbreiden van de e nvironment of extra velden in state. Dat is op zich geen probleem, maar wanneer je alle concepten tegelijk wilt vangen in de semantiek, dan wordt het een onoverzichtelijk geheel. Wanneer we het “puur ” OO zouden hebben gemaakt, dan was het waarschijnlijk eleganter geworden. Echter de kans bestaat dat we dan tegen andere problemen zouden aanlopen, die we nu nog niet overzien. Denk hierbij bijvoorbeeld aan een beginpunt van het uitvoeren (main functie).
T3 in het Wild
While
26
