Automaadid, keeled ja translaatorid

Paralleelkomponeerimise mikrokeel Parm

Kala <- X + 5
1 ; 2
X <- Y | Y <- X
3 + 3 ; (X <- 4) + 1

Keel koosneb ainult avaldistest, kuid nende avaldiste seas on ka omistamine ja kaks võimalust avaldiste komponeerimiseks. Paremal on mõned näited Parm programmidest. NB! Selles keeles me ei kirjuta käske eraldi ridadel, vaid seal on neli erinevat programmi. Oluline on siin just komponeerimine, mis võib binaarse operatsioonina natuke veider tunduda, kui oled harjunud programme vaatama käskude jadana.

Kahte avaldist võib komponeerida ja tulemuseks on teise avaldise väärtustamise tulemus, aga kuna omistamisel seisund muutub, siis on kahte liiki komponeerimist: järjestikune komponeerimine ja paralleelne komponeerimine. Nende peamine erinevus selgub, kui võrrelda järgmisi programme:

• X <- Y | Y <- X paralleelselt vahetame omavahel muutujate väärtusi.
• X <- Y ; Y <- X järjestikuselt saavad mõlemad muutujad Y-i väärtuse.

Seega paralleelselt arvutades ei mõjuta operatsioonid teineteist. Me eeldame, et paralleelsed programmid kunagi ei ürita samasse muutujasse kirjutada.

AST

AST moodustatakse ParmNode alamklassidest, mis asuvad paketis toylangs.parm.ast. Lisaks meie tuttavatele ParmLit (arvliteraal), ParmVar (muutuja) ja ParmPlus (liitmine), on selle keele esitamiseks olemas kaks klassi:

• ParmUpdate (omistamine). See uuendab muutuja väärtuse täpselt ja tagastab vastava väärtuse nagu Javas.
• ParmCompose (avaldiste komponeerimine). Selle tipu konstruktor võtab siis ühe tõeväärtustüüpi argument parallel, mis on tõene siis, kui tahame paralleelselt komponeerida.

Lisaks on klassis ParmNode staatilised loomismeetodid, mis võimaldavad kompaktsemalt puud üles ehitada. Seal kasutame kompositsiooniks meetodid seq ja par vastavalt järjestikuse ja paralleelse kompositsiooni jaoks. Ülalolevate näidete saab vastavaid ASTe luua järgmiselt:

up("Kala", plus(var("X"), lit(5)))
seq(lit(1), lit(2))
par(up("X", var("Y")), up("Y", var("X")))
seq(plus(lit(3), lit(3)), plus(up("X", lit(4)), lit(1)))

Alusosa: ParmEvaluator

Klassis ParmEvaluator on vaja avaldise väärtustajat implementeerida. Puhtad avaldised (muutujad, literaalid ja liitmine) väärtustatakse nagu aritmeetikas tavaks. Omistamisel ja kompositsioonil on järgmised nõuded:

1. Omistamine käitub täpselt nagu Java: parempoolset avaldist väärtustatakse, uuendatakse muutuja ja kogu omistusavaldise väärtuseks on seesama väärtus, mis muutujale omistati.
2. Kui omistamine toimub liitmisavaldises, siis seda tuleks tõlgendada täpselt nagu Javas, näiteks (x = x + 1) + x tulemuseks on (x + 1) + (x + 1), aga x + (x = x + 1) tulemuseks on x + (x + 1).
3. Avaldiste p ja q järjestikune kompositsioon tähendab, et kõigepealt väärtustame avaldist p, mille käigus muutujate väärtused võivad muutuda. Me väärtustame avaldist q uuendatud keskkonnas ning kompositsiooni tulemusena tagastame q väärtustamise tulemuse.
4. Avaldiste p ja q paralleelne kompositsioon tähendab, et käivitame neid sisuliselt samaaegselt ehk avaldist q tuleb samuti väärtustada esialgses keskkonnas.
5. Me eeldame, et paralleelselt komponeeritavad avaldised kunagi ei ürita ühistesse muutujatesse kirjutada. Kui selline olukord (andmejooks) peaks tekkima, võib programm tagastada misiganes ta tahab. Meie testides need olukorrad ei esine.

Paralleelne komponeerimine kasutab sama seisundit mõlema alamavaldise jaoks, aga siis peab tulemusi kokku panema. Kuna me eeldame, et nad samu muutujaid ei näpi, siis ei ole see idee poolest liiga keeruline, aga Java imperatiivses stiilis on see paras nuhtlus. Selleks võib kasutada vihjena järgmist abimeetodit:

        new ParmAstVisitor<Integer>() {
            Map<String, Integer> env = new HashMap<>();

            /**
             * Abimeetod paralleelse komponeerimise jaoks.
             * Väärtustab avaldist ja taastab keskkonda.
             * Tagastab ainult muutujad, mille väärtus on muutunud.
             */
            private Map<String, Integer> computeUpdatesAndRestoreEnv(ParmNode expr) {
                Map<String, Integer> backup = new HashMap<>(env);
                visit(expr);

                // updates = env - backup
                env.entrySet().removeAll(backup.entrySet());
                Map<String, Integer> updates = env;

                env = backup;
                return updates;
            }
        }

Lahendamise video: Parm alusosa.

Põhiosa: ParmAst

Kala <- X + 5;
1 ; 2; A <- B <- 30;
(X <- Y | Y <- X);
3 + 3 ; (X <- -4) + 1

Paremal on näide selles keeles kirjutatud programmist. Üleval olid eraldi ridadel programmid, aga siin oleme avaldised üheks suureks Parm programmiks kokku pannud. Parm programm ongi ainult üks avaldis. Süntaksile kehtivad järgmised nõuded:

1. Täisarvliteraalid koosnevad ühest või enamast numbrist, millele võib eelneda üks miinusmärk. NB! See on lekseemi osa, mitte unaarne miinus, seega - 4 ja --4 ei sobi.
2. Muutujad algavad suure ladina tähega ja edasi võib järgneda kuitahes palju väikseid ladina tähti.
3. Ainsaks aritmeetiliseks operatsiooniks on liitmine (+), mida tuleks vasakassotsiatiivsena realiseerida.
4. Omistamise (<-) vasakul pool on muutuja nimi ja paremal suvaline avaldis.
5. Komponeerimise operatsioonid on semikoolon (;) ja püstkriips (|). Nad on vasakassotsiatiivsed ja samal prioriteedil.
6. Me kirjeldame operatsiooni (alati) prioriteedi järjekorras, st. kõige kõrgem on liitmine, siis omistamine ja lõpuks komponeerimisoperaatorid. Iga avaldise ümber võib panna sulud, mis mõjutavad puu struktuuri nagu aritmeetiliste avaldiste puhul.
7. Tühisümboleid (tühikuid, reavahetusi ja tabulaatoreid) võib ignoreerida.

Grammatika on vaja defineerida failis Parm.g4 ja implementeerida klassis ParmAst meetod parseTreeToAst, mis teisendab parsepuu abstraktseks süntaksipuuks.

Lahendamise video: Parm põhiosa.

Lõviosa: ParmCompiler

Selles osas on vaja genereerida masinkood (meetod compile). Muutujate nimed ja järjekord on fikseeritud massiivis VARS. Nende väärtused antakse magasinis ette samas järjekorras ja võib eeldada, et nad on alati algväärtustatud. Kompileerimisel ei pea paralleelset kompositsiooni käsitleda, seega võib eeldada, et kompositsioon on alati seq abil.

Lahendamise video: Parm lõviosa ja meistriosa.

Lisaülesanne: ParmMaster

Paralleelse komponeerimise käsitlus on üsna keeruline, aga eeldusel, et muutujate arv on fikseeritud ja eraldi harudes samale muutujale ei omistata, siis on see võimalik. Sellesse tuleb aga suhtuda kui meistriosa ülesanne, mis on eksami piiratud ajal lahendamiseks natuke liiga keeruline.

Lahendamise video: Parm lõviosa ja meistriosa.