Vezérlés Strategoban
A Stratego nyelvet úgy alakították ki, hogy alapvető műveletei a termátírás alapvető műveletei legyenek: mintaillesztés, résztermek cseréje, termbejárások. Ennek megfelelően hagyományos értelemben vett vezérlési szerkezetekről nem beszélhetünk; a program futása során min dig egy aktív termen végzünk transzformációkat.
A nyelv "tiszta": teljesül a hivatkozási helyfüggetlenség elve - ha csak a Stratego nyelvet használjuk és nem támaszkodunk olyan külső könyvtárakra, melyek mellékhatásos függvényeket importálnak. Az átírási lépések során nem állapotváltozás történik, hanem új term jön létre, amit a következő művelet esetén aktívnak tekintünk. Ha egy termet névhez kötünk, a név értéke hatókörén belül nem változhat.
Mintaillesztés (vagy tetszőleges művelet) lehet sikertelen (fail). Ha egy sikertelen művelet eredményére kísérlünk meg újabb műveletet alkalmazni, az mindenképp sikertelen.
Elemi műveletek
Új aktív term
Az aktív term a ! prefix operátorral cserélhető le új termre. A term tartalmazhat kötött változókat; ez úgy fog viselkedni, mintha az adott változóhoz kötött termet a jelölt ponton behelyettesítettük volna. Például a !Var("a",4,f) végrehajtása után az aktív term Var("a",4,f) lesz.
Identitás
A id művelet helyben hagyja az aktív termet.
Sikertelenség
A fail művelet mindig sikertelen.
Mintaillesztés
Az aktív term illeszthető megadott mintához, a ? prefix jelölésű művelettel. A minta abban különbözik termektől, hogy tartalmazhat szabad változókat és a "_" jelet (bármit illesztő jel, wildcard). Ha az aktív term megfelel a mintának, úgy a szabad változók kötötté válnak; értékük az aktív term adott pozíción szereplő résztermje lesz.
Például ha az aktív term Var("a",Int(4),f) (és n,x szabad változók), akkor a ?Var(n,Int(x),_) utasítás után az aktív term változatlan, de a hatókör hátralevő részében n = "a" és x = 4.
Ha a megadott minta nem illeszkedik az aktív termre, a művelet sikertelen (fail).
Szabályok
A termátírás központi eleme a "szabályalkalmazás": ekkor az aktív termre illesztünk egy mintát (ez a szabály baloldala) majd a minta által kötött változók felhasználásával azt egy új termre cseréljük. Ennek megfelelően a legegyszerűbb elnevezhető program a szabály, ami egy mintának megfelelő termet cserél le kizárólag a minta alapján egy új termre. Ez azt jelenti, hogy csak a minta szabad változói szerepelhetnek a term változói között. A szabály alkalmazása
Általános formája: minta -> term. A modulban az elnevezett szabályokat egy külön "rules" blokkban soroljuk fel és nevüket név : prefixszerl jelöljük. Például:
module eval-bool
rules
EvalNT : Not(True()) -> False()
EvalNF : Not(False()) -> True()
EvalO1 : Or(True(), _) -> True()
EvalO2 : Or(False(), a) -> a
Egy névhez több szabály is tartozhat; ekkor a rendszer kiválasztja az illeszkedő mintát és az ahhoz tartozó szabályt használja. Ha több minta is illeszkedik, nem definiált, hogy melyik szabály kerül alkalmazásra, ezért figyeljünk arra, hogy egy lehetséges termre azonos nevű szabályok közül legfeljebb egy baloldala illeszkedjen. Több illeszkedése esetén is működőképes programot kapunk, de viselkedése nehezen állapítható meg előre. Ennek megfelelően az előbbiekben megadott szabályrendszer egyszerűsítve:
Eval : Not(True()) -> False()
Eval : Not(False()) -> True()
Eval : Or(True(), _) -> True()
Eval : Or(False(), a) -> a
A szabályra nevével hivatkozunk; azt s Ha egyik baloldal sem egyezik, úgy az eredmény fail; ha legalább egyik egyezik, akkor a minta esetleges változóival behelyettesített jobboldal lesz az új aktív term. Például az előbb megadott Eval szabály többek között a következő módosításokat teszi:
| Kiindulási term | Új term |
|---|---|
Not(True()) | False() |
Or(True(), True()) | True() |
Or(False(), True()) | True() |
Or(False(), Not(True()) | Not(True()) |
Or(Not(True()),False()) | fail |
Stratégiák
A Strategoban a végrehajtható utasítások alapvető egysége a stratégia; művelet, ami vagy lecseréli az aktív termet, vagy fail üzenettel tér vissza az átírás sikertelenségét jelezve. Stratégiának tekintjük az elemi utasításokat, a szabályokat, felhasználói stratégia alkalmazását és stratégiák egy kombinációját.
Stratégiák alkalmazása
Stratégia lehet névtelen vagy elnevezett. Egy s nevű stratégiát az aktív termre a következőképp alkalmazunk:
s
Ha a programban egy t term s stratégiával való transzformáltjára szeretnénk hivatkozni, azt a következőképp tehetjük meg:
<s> t
Ez alkalmazza s stratégiát t termre és az aktív termet az így kapott termre cseréli.
Az alábbi kódrészlet startégia-alkalmazásra mutat példát. Ehhez a standard könyvtárban található add stratégiát használjuk. Ez egy egészekből álló rendezett pár két koordinátáját összeadja.
stratego> !(2,3)
(2,3)
stratego> add
5
stratego> <add> (7,8)
17
Ha egy <s> formájú stratégiahívás esetén nem adunk meg átírandó termet, akkor az aktív termre alkalmazzuk.
stratego> !5
5
stratego> !<id>
5
stratego> !Int(<id>)
Int(5)
Stratégia-kombinátorok
Ahhoz, hogy új stratégiákat hozhassunk létre korábbiak alapján, stratégia-kombinátorokat alkalmazunk. Ezek olyan műveletek, melyek két stratégiából egy újat hoznak létre.
Szekvenciális kompozíció
Az s1 és s2 stratégiák szekvenciális kombinációja az a stratégia, mely az aktív termre először alkalmazza s1-et, és ha az sikeres, s2-t is. Ha bármely stratégia végrehajtása sikertelen, a kompozíció végrehajtása is sikertelen.
Vegyük figyelembe, hogy ha s1 sikeres, de s2 sikertelen, kompozíciójuk sikertelen, nem változik az aktív term, de az esetleges mellékhatások nem visszavonhatóak.
Például tekintsük az előzőekben megadott EvalO1 és EvalNT szabályokat. Az Or(False(),Not(True()) termre ezt a két szabályt egymás után alkalmazva a False() termet kapjuk.
stratego> EvalO1 : Or(False(),a) -> a
stratego> EvalNT : Not(True()) -> False()
stratego> !Or(False(),Not(True())
Or(False(),Not(True())
stratego> EvalO1; EvalNT
False()
stratego> EvalO1; EvalNT
command failed
A szekvenciális kompozíció segítségével elemi műveletekből kifejezhető a "szabály". Megkísérlünk mintát ileszteni; ha az sikeres, a változók értékeit behelyettesítjük az eredmény-termbe; ha sikertelen, akkor az egész szabályalkalmazás sikertelen. Például az EvalO1 : Or(False(),a) -> a szabály a ?Or(False(),a); !a kompozícióval képzett stratégiaként adható meg.
Beáltható, hogy a szekvenciális kompozíció asszociatív; (s1; s2); s3) ekvivalens s1; (s2; s3) stratégiával. Ennek megfelelően zárójelezése elhanyagolható.
Determinisztikus választás
Az s1 és s2 stratégiákból képzett s1 <+ s2 determinisztikus választás megkísérli s1 alkalmazását, és ha az sikertelen, s2-t alkalmazza. s2 sikertelensége esetén a kombináció is sikertelen.
stratego> EvalO1 : Or(False(),a) -> a
stratego> EvalNT : Not(True()) -> False()
stratego> !Or(False(),Not(True())
Or(False(),Not(True())
stratego> EvalNT <+ EvalO1
Not(True())
stratego> EvalNT <+ EvalO1
False()
stratego> EvalNT <+ EvalO1
command failed
A determinisztikus választás kombinátort jellemzően arra használjuk, hogy sok szabály közül úgy válasszunk ki egy illeszkedő baloldalút, hogy a próbálkozások sorrendje ismert legyen.
Őrzött választás
Az "őrzött választás" három stratégia kombinációjaként hoz létre újat: egy "feltétel"-stratégiát megkísérel végrehajtani az aktív termen, majd ennek sikeressége alapján választ a másik két stratégia közül rákövetkezőt. Az sp, s1, s2 stratégiákból képezett őrzött választás formája:
sp < s1 + s2
Ha sp végrehajtása sikeres, az eredményül kapott term válik aktív termmé és azon elvégezzük s1-et és az így kapott term lesz aktív. Ha sp sikertelen, úgy az eredeti termen hajtja végre s2-t és az így kapott term lesz az aktív.
Az őrzött választás általánosítása a determinisztikus választás műveletének. s1<+s2 balválasztással ekvivalens a s1<id+s2 őrzött választással.
A szekvenciális kompozíció is kifejezhető az őrzött választás segítségével. s1;s2 ekvivalens s1<s1+fail őrzött választással.
Nemdeterminisztikus választás
A determinisztikus választáshoz hasonlóan a nemdeterminisztikus választás is két szabály közül választ ki egy végrehajthatót - ha van ilyen. A különbség abban áll, hogy amennyiben mindkét szabály végrehajtható, bármely stratégiát választhatja a program. Nincs biztosítékunk arra vonatkozóan, hogy a futtató rendszer mely stratégiának ad elsőbbséget. Formája:
s1 + s2
Ha több szabályt látunk el azonos névvel, a fordító a szabályokat ezen operátor segítségével kombinálja egy stratégiává. Tehát például a következő két kódrészlet ekvivalens:
Eval : Or(False(), a) -> a
Eval : Or(a, True()) -> a
Eval = (Or(False(), a) -> a) + (Or(a, True()) -> a)
Bejárások
Az eddigi műveletekkel csak olyan transzformációkat tudunk végrehajtani, ahol a term szerkezetét előre pontosan megadtuk. Azonban legtöbb esetben e megszorítás felesleges; a szintaxisfa-bejárások nagy része csak bizonyos fajta résztermeken operál, azok szülőitől függetlenül. Például: a változónevek összegyűjtése attól független, hogy pontosan milyen csomópontok szerepelnek a program absztrakt szintaxisfájában; kizárólag a "Var" konstruktorú résztermek érdekesek.
Összes részterm meglátogatása
Információk összegyűjtéséhez a szintaxisfa összes csúcsát / a term összes résztermjét meg kell látogatni. Erre szolgál az all(s) stratégia, ami az s stratégiával transzformálja az összes közvetlen résztermet. Például:
stratego> unwrap : Int(x) -> x
stratego> !Add(Int(1),Int(2))
Add(Int(1),Int(2))
stratego> all(unwrap)
Add(1,2)
Ha a stratégi alkalmazása minden résztermre sikeres, az új termet a közvetlen résztermek transzformálásával kapjuk. Ha akár egyetlen résztermre is sikertelen az alkalmazás, a teljes transzformáció sikertelen.
stratego> unwrap : Int(x) -> x
stratego> !Add(Int(1),Var("x")
Add(Int(1),Var("x"))
stratego> all(unwrap)
command failed
Néhány részterm meglátogatása
Az all(s) stratégiához hasonló a some(s). Megkísérli s-t alkalmazni az összes közvetlen résztermre. Azonban - az all-lal ellentétben - ha van olyan közvetlen részterm, amelyre sikeres az alkalmazás, de nem mindegyikre, a some(s) sikeres. Ebben az esetben azon résztermek, melyekre s nem alkalmazható, változatlanul marad. Viszont ha egyik közvetlen résztermre sem sikeres s, az egész művelet sikertelen. Használatára példa:
stratego> !Add(Int(1),Var("x"),Int(2))
Add(Int(1),Var("x"),Int(2))
stratego> some(unwrap)
Add(1,Var("x"),2)
stratego> some(unwrap)
command failed
Egy részterm meglátogatása
Ha csak arra van szükség, hogy egyetlen megfelelő résztermre alkalmazzuk s-t, akkor a one(s) stratégiát használjuk. Balról indulva megkísérli alkalmazni s-t a közvetlen résztermekre. Az első ilyet lecseréli az s-sel transzformáltjára. Ha nincs ilyen, akkor a one(s) sikertelen.
stratego> unwrap : Int(x) -> x
stratego> !Add(Int(5),Int(6))
Add(Int(5),Int(6))
stratego> one(unwrap)
Add(5,Int(6))
stratego> one(unwrap)
Add(5,6)
stratego> one(unwrap)
command failed
Term-dekonstrukció
Ezekkel a műveletekkel már be tudunk járni ismert struktúrájú fákat illetve tudjuk azukat redukálni; mindazonáltal ismeretlen struktúrájúakat továbbra sem. A problémát leginkább a különböző nevű illetve aritású konstruktorok jelentik. Listákat viszonylag könnyen tudunk dekonstruálni; minden nemüres lista felbontható egy fejelemre és egy maradékrészre. Így például egy számokból álló lista tagjait a következő sum szabállyal összegezhetjük (az add a standard könyvtár-beli):
sum : [] -> 0
sum : [x|xs] -> <add> (x, <sum> xs)
Ez azonban konstruktoros termekre és rendezett n-esekre nem használható. Ennek érdekében bevezetjük a termdekonstrukció # operátorát. t#(l) minta minden termre illeszkedik, t-hez a term nevét (konstruktornevet sztringként, rendezett n-esre az üres sztringet, listára az üres listát), l-hez a term összes közvetlen résztermjének listáját rendeli. Például:
stratego> !Add(1,2)
Add(1,2)
stratego> ?t#(l)
stratego> !(t,l)
("Add", [1,2])
Így már például a résztermek összegzését le tudjuk írni:
sumterm : _#(l) -> <sum> l
Term-rekonstrukció
A # operátor fordított irányban is használható, mint termkonstrukciós operátor. Adott t névre és l közvetlen részterm-listára t#(l) megkonstruálja azt a termet, melynek dekonstruáltjára t#(l) minta illeszkedik. Például:
stratego> !"Add"#([Int(1),Var("b")])
Add(Int(1),Var("b"))