Automata, Languages and Compilers 2019/20 spring

Beebiprolog ehk Bolog

X kui A, B, C ja D
X <> P kui A ja B
!X && P kui R && JAH ja EI
(AB kui Z) && KALA
JAH || EI kui JAH

Bolog on kolmanda põlvkonna loogilise programmeerimise keel. Programm koosneb eraldi ridades kirjutatud loogilistest väidetest. Selle keele konkreetse süntaksi kohta räägime täpsemalt põhiosa kirjelduses. Sisuliselt on meil siis lausearvutuse valmid, aga implikatsiooni jaoks on natuke mugavam esitus, sest implikatsioon on loogilises programmeerimises väga oluline!

Loogiliste programmide "täitmisel" tahatakse üldiselt leida selline muutujate väärtustus, mis rahuldaks kõiki implikatsioone. Kuna see on natuke keerulisem, siis alusosas väärtustame ainult ühte avaldist ja lõviosas vaatame tervet programmi. Keele süntaks on veidi segane (tähendab väljendusrikkas), aga abstraktne süntaks on lihtne ja loogiline.

AST

AST moodustatakse BologNode alamklassidest, mis asuvad paketis bolog. Loogilises programmeerimises ei ole järjekord oluline, mistõttu programm on meil lihtsalt hulk BologNode tüüpi avaldisi, milleks on lausarvutuse valmid. Selle esitamiseks klassid on järgmised:

• BologLit (tõeväärtusliteraal)
• BologVar (muutuja),
• BologNand (konjunktsiooni eitus)
• BologImp (implikatsioon). See koosneb kahest osast, järeldusest (conclusion) ja eelduste listist (assumptions). Näiteks "P kui A ja B" korral on järelduseks "P" ja eelduste list koosneb elementidest "A" ja "B".

Klassis BologNode on staatilised mugavusmeetodid, millega abstraktset süntaksipuud saab ise ehitada. Implikatsiooni saab ka nii ehitada, et argumendid on kõik lamedalt järjest. Lisaks on meetodid konjunktsiooni (and), disjunktsiooni (or), välistava disjunktsiooni (xor) ja eituse (not) väljendamiseks BologNand kaudu. Meie näites kaks esimest avaldist saab ehitada järgmiselt:

imp(var("X"), var("A"), var("B"), var("C"), var("D"))
imp(and(var("X"), var("P")), var("A"), var("B"))

Viimane aga loob järgmist esitust: imp(nand(tv(true), nand(var("X"), var("P"))), var("A"), var("B")). Seega väärtustamisel peame ainult Nand juhtumit implementeerima.

Alusosa: BologEvaluator

Programm koosneb avaldiste hulgast, aga meie eval meetod peab lihtsalt ühe loogilise avaldise väärtustama. See peaks muidu olema (Interneti abiga) selge, aga implikatsioon on natuke keerulisem, kuna meil on siin eelduste list. Matemaatilises loogikas piisab implikatsiooni tõesuseks järgmine tingimus: kui kõik eeldused on tõesed, siis peab ka järeldus olema tõene. Implikatsioon on seega tõene, kui järeldus on tõene või kasvõi üks eeldus on väär. Kui ei ole ühtegi eeldust, siis peab järeldus olema tõene.

Põhiosa: BologAst.java

X kui P ja Q
X && P kui P, P||Q ja (P kui Q ja R)
(AB kui Z) && KALA
!X && P kui R <> JAH || EI
JAH

Paremal on taaskord näide selles keeles kirjutatud programmist. Ta koosneb eraldi ridadel kirjutatud loogilistest avaldistest. Süntaksile kehtivad järgmised nõuded:

1. Tõeväärtusliteraalideks on suurte tähtedega sõned JAH ja EI tähistamaks vastavalt true ja false.
2. Muutujad on ühest või rohkemast ladina suurtähest koosnevad sõned.
3. Lubatud operatsioonid on eitus (!) ja järgmised vaskassotsiatiivsed binaarsed operatsioonid, alustades kõige kõrgemast prioriteedist: konjunktsioon (&&), disjunktsioon (||) ja välistav disjunktsioon (<>).
4. AST tuleb luua kasutades BologNode klassis defineeritud staatilised meetodid, et saada täpselt sama puu nagu testidel.
5. Implikatsioon algab nüüd reegli järeldusega, mis võib olla suvaline avaldis, millele järgneb märksõna kui ning siis eelduste list. See on lihtsalt avaldiste loetelu eesti keele tavapärase komakasutusega, s.t. viimase avaldise ees on märksõna ja, aga kui loetelus on rohkem kui kolm, siis kasutatakse koma. Eeldusi võib ka üldse mitte olla (A kui).
6. Iga avaldise ümber võib panna sulud, et muuta süntakspuu struktuuri.
7. Tühisümboleid (tühikuid ja tabulaatoreid) võib ignoreerida, aga reavahetused on olulised.
8. Avaldiste vahel peab olema vähemalt üks reavahetus. Programmi algul ja lõpul võiks neid ignoreerida.

Grammatika tuleb implementeerida faili Bolog.g4 ja implementeerida klassis BologAst meetod parseTreeToAst, mis teisendab parsepuu abstraktseks süntaksipuuks.

Lõviosa: BologCompiler

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. Tõeväärtusmuutujate argumente teisendame täisarvudeks CMaUtils.bool2int abil.

Lisaülesanne: BologMaster

Tuleb implementeerida meetod leastModel. See peab leidma need muutujad, mis peavad olema tõesed selleks, et etteantud valemid kõik kehtiksid. Me eeldame, et valmiteks on ainult implikatsioonid, mille järelduseks on ainult aatomid (muutuja või literaal). Selles ülesandes võib muutujate arv olla väga suur, seega ära vaata kõik võimalikud tõeväärtused läbi, vaid alusta tühjast hulgast ja lisa järjest muutujaid juurde kuni rohkem ei pea lisama, et kõik valemid oleksid tõesed.