Automata, Languages and Compilers 2019/20 spring

Puhas let-sidumistega keel Pullet

a – (10 – kala)
let x=5 in x-1
let a=10 in let b=20 in a-b
sum x=1 to 4 in x

Pullet on keel, mis koosneb ainult avaldistest, aga tal on natuke eriline konstruktsioon muutujate sidumiseks, nimelt let-avaldis. Mõned näited selle keele avaldistest on paremal. (Programm koosnebki ainult ühest avaldises, seega on paremal tegelikult neli erinevat programmi.)

Näiteks let-avaldise let x=5 in x-1 korral väärtustame avaldist x-1 keskkonnas, kus x-i väärtus on 5 ja selle avaldise tulemuseks on siis 4. Siin on ka natuke keerulisem summa konstruktsioon, mis on võib-olla tuttav matemaatikast. Näiteks avaldise sum x=1 to 4 in x tulemuseks on 1+2+3+4.

AST

AST moodustatakse PulletNode alamklassidest. Avaldiseks võib olla:

• PulletNum (täisarv).
• PulletVar (muutuja).
• PulletDiff (kahe avaldise vahe).
• PulletBinding (muutuja sidumisega avaldis). See koosneb seotava muutuja nimest, muutujale omistatavast avaldisest ning avaldise kehast.
• PulletSum (summeeriv avaldis). Avaldis koosneb muutuja nimest, muutuja algväärtusavaldisest, muutuja lõppväärtusavaldisest ning avaldise kehast.

AST moodustamisel võib kasutada PulletNode staatilisi meetodeid. Nende abil saab viimased kaks ülalolevatest näidetest järgmiselt luua:

let("a", num(10), let("b", num(20), diff(var("a"), var("b"))))
sum("x", num(1), num(4), var("x"))

Alusosa: PulletEvaluator

Lahenda soojenduseks eval meetod, mis tagastab etteantud ASTi täisarvulise väärtuse. Literaal, muutuja ja vahe on meil juba tuttavad. Edasi kehtivad järgmised tingimused:

1. Sidumisega avaldises esmalt arvutatakse välja muutuja väärtus ning seejärel kasutatakse saadud tulemust avaldise kehas.
2. Summeerimises leitakse muutuja väärtuse vahemik (kõik täisarvud, mis on vähemalt lo ning mitte rohkem kui hi), leitakse avaldise keha väärtus iga muutuja väärtuse jaoks ning summeeritakse need.
3. Kui kasutatakse muutujat, mis pole eelnevalt sidumise või summeerimise poolt defineeritud, tuleks visata erind.

Põhiosa: PulletAst

let x = 1; y = 2 in
let x = 666 in 
 (sum i = 0 to 3; 
      j = 0 to i 
  in i-j) - 1

Keele Pullet avaldiseks võib olla täisarv, muutuja nimi, lahutamine, sidumisega avaldis, summeerimine või sulgudega ümbritsetud avaldis.

• Muutuja nimi koosneb ühest või rohkemast ladina suur- ja/või väiketähest.
• Lahutamine koosneb kahest avaldisest, mille vahel on miinusmärk. Lahutamine on vasakassotsiatiivne ning suurema prioriteediga kui sidumine või summeerimine.
• Sidumisega avaldis algab võtmesõnaga let, millele järgneb muutuja nimi, seejärel võrdusmärk, millele järgneb avaldis (taolisi muutujale omistamisi võib järjestikku olla rohkem kui üks, sellisel juhul on nad üksteisest semikoolonitega eraldatud). Sidumine lõpeb võtmesõnaga in, mille järel tuleb avaldis.
• Summeerimine algab võtmesõnaga sum, millele järgneb muutuja nimi, võrdusmärk, avaldis, võtmesõna to, avaldis (jällegi võib taolisi omistamisi olla rohkem kui üks, sel juhul semikoolonitega eraldatud). Summeerimine lõpeb jällegi võtmesõnaga in ning sellele järgneva avaldisega.
• Avaldises võib olla suvalisel kohal tühikuid, tabulaatoreid ja reavahetusi. Avaldiste näidiste jaoks uuri teste.

Siin ülesandes tuleb teisendada ANTLRi abil moodustatud parse-puu abstraktseks süntaksipuuks. Pane tähele, et sidumise ja summerimise klassides on ainult üks muutuja nimi, aga grammatikas on lubatud semikoolonitega omistada mitmele muutujale. Siinkohal tuleks tõlgendada selliselt, et let x=1; y=2 in x-y on samaväärne avaldisega let x=1 in (let y=2 in x-y). Mõtle, mis järjekorras oleks siin kõige mõttekam omistamisi läbi käia.

Lõviosa: PulletCompiler

Nüüd võib implementeerida compile meetod, et transleerida let-avaldisi CMa programmideks. Meil on defineeritud vabad muutujad (x, y, z), mis asuvad kohe magasini põhjas (pesades 0, 1, 2 vastavalt). Õige indeksi saab kätte VARS.indexof abil. Teeme siin aga olulise lihtsustuse, et let ja sum ei esine teiste avaldiste alamavaldistena, vaid meil on ainult järjest let-sidumiste jada, nagu näiteks:

let a = 5 in
let b = x - a in
let c = sum 3 to y in 10 - b in
let d = a - c in
  d - (z - 1)

See garanteerib, et magasini tegelikult ainult kasvab ja iga let-seotud muutuja asukoht on kompileerimise ajal lihtne paika panna. Testides on näha, mis avaldistega peab hakkama saama.

Lisaülesanne: PulletMaster

Let-avaldise puu võib sisaldada erinevaid muutujad. Defineeri meetod isLive, mis etteantud muutuja ja puu kohta kontrollib, kas selle muutuja väärtust on avaldise väärtustamisel vaja või mitte. Need muutujad, mis on avaldise väärtustamiseks vaja, nimetame elusateks muutujateks. Kõigepealt tasub vaadata meie teste ning nende põhjal järjest implementeerida. Näiteks avaldise x-kala väärtustamisel on muutuja kala kasutusel, aga avaldise x-y puhul mitte.

Oluline on aga see, et tuleb eristada lokaalselt defineeritud muutujad nendest muutujatest, mis peavad olema väärtustamise keskkonnas defineeritud. Kui mõni muutuja on kohalikult defineeritud (let x=5 in x), siis ei sõltu selle väärtus keskkonnast ja tuleb tagastada, et muutuja x ei ole siin elus. Järgneva kahe avaldise väärtustamiseks aga on vaja, et keskkonnas oleks muutuja x defineeritud:

let y = x-1 in y
(let x=5 in x) – x

Siin võib tekkida küsimus, kas avaldises let y=x in 5 on muutuja x väärtus vaja või mitte. Avaldise tavapärasel väärtustamisel tekiks viga, kui muutuja on defineerimata, aga tulemus samas ei sõltu muutuja väärtusest. Sellistel avaldistel on meil käitumine spetsifitseerimata ehk me otseselt ei testi seda ja võid tagastada misiganes aitab Sul järgmist optimeerijat mugavamalt implementeerida.

Nüüd võime kirjutada meetod optimize, mis eemaldab surnuid let-sidumisi. Need on sellised let-sidumised, mis väärtustamisel vaja ei lähe ehk seotakse väärtus muutujale, mis ei ole sidumise kehas elus. Jällegi tasub vaadata testis olevaid näited ning nende põhjal üldistada. Siin on mõned neist välja kirjutatud:

let x=5 in y
let x=5 in x
let x=5 in let y=10 in let z=x in z
let x=10 in let y=x in z

y
let x=5 in x
let x=5 in let z=x in z
z

NB! Me ei soovi siin saada avaldise lihtsutajat, vaid ainult üleliigsete let-sidumiste eemaldajat. Seega, teise näide korral ei ole tulemuseks lihtsalt 5, vaid terve esialgne let-avaldis. Tuleb aga nii palju let-avaldisi eemaldada kui võimalik. Näiteks ei ole viimases näites muutuja x väärtust vaja, sest selle põhjal arvutatakse muutuja y väärtus, mida lõpuks ei kasutata. Me jätsime üleval isLive käitumist sellistel juhtudel lõpuni spetsifitseerimata, sest tema vajalik käitumine sõltub sellest, kuidas seda meetodit siin rakendada.