Uskumatu hulgatöötluskeel Hulk
A := {x}
B := A + {y, z}
C := B | A subset {x,y}
B := A & {}
C := C - {y}
Programmeerimiskeel Hulk võimaldab hulkadega uskumatult mugavalt töötada. Selles keeles on ainsaks tüübiks tähtedest koosnevad hulgad, näiteks {x, y, z}, mida saab hoida (suurte tähtedega) hulkmuutujatesse. Oluline on keele juures see, et ei tagastata ühtegi väärtust, vaid keel koosneb lausetest, mis uuendavad muutujate väärtusi. Lause juures võib olla püstkriipsuga eraldatud tingimus, mille korral täidetakse lause ainult siis, kui tingimus kehtib.
Siinses näites toimitakse järgmiselt. Hulgale A omistatakse väärtust {x}, hulga B väärtuseks saab A ja {y, z} ühend ehk {x, y, z} ning hulk C pannakse A-ga võrduma, sest B on {x,y,z} alamhulk. Eelmviimasel real tühjendatakse hulka B, sest võetakse ühisosa tühja hulgaga. Lõpuks eemaldatakse hulgast C elementi y. Koodi tulemusena on muutujate väärtused järgmised: A = {x}, B = {} ja C = {x, z}.
AST
Hulk keele AST klassid asuvad paketis toylangs.hulk.ast. Nad on kõik HulkNode alamklassid. Selles keeles (nagu ka AKT kodutöös) on avaldiste jaoks vahepealne abstraktne klass. See asub koos tema alamklassidega alampaketis expressions. Kokkuvõtvalt on meil järgmised klassid:
- HulkExpr esitab erinevad avaldise liike, milleks on
- HulkVar — hulkmuutuja, mida tähistame suure tähega;
- HulkLit — elementide list;
- HulkOp — binaarsed tehted hulkadega (ühend, ühisosa, vahe).
- HulkCond — tingimus, mis koosneb alamavaldisest (subset expression) ja ülemavaldisest (superset expression).
- HulkStmt — lause esindab omistamist, koosneb hulgamuutuja nimest (millele omistatakse), avaldisest (mida omistatakse) ning tingimusest (kas omistatakse).
- HulkProg — tervikprogram, mis sisaldab listi HulkStmt tippudega.
Nagu ikka on meil HulkNode klassis mugavusmeetodid ASTi loomiseks. Nende abil saab ülaloleva koodinäide järgmiselt kirja panna (enamasti on stmt viimaseks argumendiks null, sest tal puudub tingimus):
prog(
stmt('A', lit('x'), null),
stmt('B', binop('+', var('A'), lit('y', 'z')), null),
stmt('C', var('B'), cond(var('A'), lit('x', 'y'))),
stmt('B', binop('&', var('A'), lit()), null),
stmt('C', binop('-', var('C'), lit('y')), null)
)
Alusosa: HulkEvaluator
Väärtustaja tuleb implementeerida klassi HulkEvaluator, mis asub selle nädala eval paketis. Seal on vaja implementeerida meetod eval! See on aga natuke teistsugune kui meie tavalised eval meetodid: see võtab lisaks ASTi argumendiks keskkonna (Map<Character, Set<Character>>, mis näitab missugused elemendid kuuluvad hulkadesse) ning peab muutma etteantud keskkonna sisu nii, et see vastaks ASTile vastava programmi jooksutamisele.
- Avaldistes on lisaks literaalile ja hulgamuutujale ka binaarsed operatsioon (binop). Nende väärtustamise tulemus sõltub esimesest argumendist, mis võib olla vastavalt
+(ühend),&(ühisosa) ja-(vahe). Nende operatsioonide definitsioonid on näiteks Eesti Wikipedias. - Hulgamuutujaid saab avaldises kasutada ainult siis, kui neile on eelnevalt omistatud midagi või nad on etteantud keskkonnas juba defineeritud. Muidu tuleks visata erind.
- Programmi tuleb täita ülevalt alla ja lause täidetakse ainult siis, kui vastav tingimus on tõene või tingimus puudub.
- Tingimus on koosneb alamavaldisest ja ülemavaldisest. Tingimus on tõene siis, kui iga alamavaldise element on ka ülemavaldise element.
Vihje: pead tegema, kas erinevate visitoritega või kusutad Set<Character>, mis on avaldiste tulemus, ja lausete puhul tagastad "null". Tingimuste tulemus saab ka hulgana kodeerida. Muidu saab alati tagastada Object ja igal pool tüüpe teisendada.
Lahendamise video: Hulk alusosa.
Põhiosa: HulkAst
A := {x, y, z} + A
B := A & (B - C) & {}
A := A + {x, y} | x in A + B
A <- x | {x} + {y} subset A
A -> a, b, c
Grammatika tuleb implementeerida faili Hulk.g4 ja implementeerida klassis HulkAst meetod parseTreeToAst, mis teisendab parsepuu abstraktseks süntaksipuuks.
Programm koosneb lausetest, mis paiknevad kõik omaette real. Tühje ridu ei ole. Lause võib olla kas omistamine või hulga muutmine. Iga lause lõpus võib olla püstkriipsuga eraldatud tingimus.
- Omistamislause algab hulgamuutujaga, järgneb
:=, millele omakorda järgneb avaldis. - Hulga muutmise lause algab hulgamuutujaga, järgneb kas
<-(elementide lisamine hulka) või->(elementide eemaldamine), millele järgneb üks või mitu komaga eraldatud elementi. - Hulgamuutuja tähistatakse ühe ladina suurtähega, elementi ühe ladina väiketähega.
- Avaldiseks võib olla hulgamuutuja, hulgaliteraal, hulgatehe või sulgudega ümbritsetud avaldis.
- Hulgaliteraal koosneb loogeliste sulgude vahel asuvast komaga eraldatud elementidest (võib olla tühi), näiteks
{a,b,c}. - Hulgatehe koosneb kahest avaldisest, mille vahel on operaator. Operaatoriteks võivad olla
+(ühend),&(ühisosa),-(vahe). Operaatorite prioriteedid on samad ning kõik on vasakassotsiatiivsed. - Tingimus võib olla:
- Elemendi sisaldumine hulgas, koosneb elemendist ja avaldisest, mille vahel on võtmesõna
in. - Alamhulgaks olemine, koosneb kahest avaldisest, mille vahel on võtmesõna
subset.
- Elemendi sisaldumine hulgas, koosneb elemendist ja avaldisest, mille vahel on võtmesõna
- Kõikide leeksemide ümber võib olla suvaline arv tühikuid ja tabulaatoreid.
AST moodustamisel tuleks kasutada HulkNode.java staatilisi meetodeid. Pane tähele, et elementide lisamise/eemaldamise jaoks eraldi lauseliiki ei ole, mõtle kuidas teisendada see tavaliseks omistamiseks nii, et hulga sisu oleks siiski sama. Samuti pole eraldi tippe mõlema tingimusliigi jaoks, mõtle kuidas elemendi sisalduvust esitleda alamhulgaks olemise kaudu.
Lahendamise video: Hulk põhiosa.
Lõviosa: HulkCompiler
Lõpuks on jäänud meetod compile, kus tuleb hulkprogramme CMa peal käivitada. Hulkmuutujate keskkond on fikseeritud ja nende mälupesad saab kätte SET_VARIABLES.indexOf kaudu. Kuna CMa arvutab ainult täisarvudega, siis on hulga sisu ka fikseeritud ja meetod set2int, teisendab hulka bitvektoriks. See muidugi tähendab, et pead ise nuputama, kuidas hulga operatsioone bitoperatsioonidena teostada. Ühe vihje anname siiski, sest NOT ei tööta CMa-s bithaaval: selle asemel võib teha miinus ühega XOR.
Lahendamise video: Hulk lõviosa.
Lisaülesanded: HulkMaster
Meetod isValidHulkNode peab kontrollima, kas kõik muutujad, mida avaldistes ning tingimustes kasutatakse, on eelnevalt defineeritud. Kui leidub mõni mitte-defineeritud muutuja kasutus, tuleb tagastada false, vastasel juhul tagastada true. Kui muutuja on omistatud avaldisega, mis sisaldab tingimust, ei loe me muutujat defineerituks (olenemata tingimuse tõeväärtusest – siin me nende väärtusi ei arvesta). Ükski muutuja pole enne programmi analüüsi defineeritud.
- Järgneva näite korral peab meetod tagastama false, sest muutuja A pole enne selle kasutamist defineeritud:
A := A | {a} subset {b, c} - Järgneva näite korral peab meetod tagastama false, sest muutuja B omistamisel kasutatakse muutujat A, mida loeme mitte-defineerituks tingimusega omistamise tõttu:
A := {b} | {a} subset {a, b, c} B := (A-{a}) - Järgneva näite korral peab meetod tagastama true, sest muutuja A on enne selle kasutamist eelnevalt defineeritud:
A := {a, b, c} B := (A+{a})
Meetod processEmptyLiterals tagastab uue puu, kus on eemaldatud kõik tühjad literaalid, mis esinevad tehetes. Lisaks on vaja omistuslausest eemaldada ka tingimus, kui tingimuses kasutatav alamhulk on tühi literaal. Uus puu peab olema esialgsega samaväärne ning tehetest tühjade literaalide eemaldamisel kasutatakse järgmisi reegleid:
- Kui ühisosa (
&) vasak või parem pool on tühi literaal, tuleb tehe asendada tühja literaaliga.A := {} & B => A := {} - Kui ühendi (
+) vasak või parem pool on tühi literaal, tuleb tehe asendada poolega, mis polnud tühi literaal.A := {a, b, c} + {} => A := {a, b, c} - Kui vahe (
-) vasak pool on tühi literaal, tuleb tehe asendada tühja literaaliga.A := {} - B => A := {} - Kui vahe (
-) parem pool on tühi literaal, tuleb tehe asendada vasaku poolega.A := {a, b} - {} => A := {a, b}