Viies kodutöö -- Virtuaalmasin
Kuna hindame ka koodi struktureerimist ja stiili (3 punkti 10st), siis soovitame esitada vahetähtajaks. Siis saate oma koodi veel parandada.
Ülesanne
Implementeerida alljärgnev virtuaalne masin. Interpretaator võtab argumendiks baitkoodi teksti faili nime ja käivitab selle. Andes programmile käsurealt võtme "-v" (nt. "./Bc -v ex1.bc") trükitakse iga instruktsiooni eel virtuaalmasina seisund.
> ./Bc -v ex1.bc stack: [] fp: 0 pc: 1 instr: loadc 1 stack: [1] fp: 0 pc: 2 instr: loadc 2 stack: [2,1] fp: 0 pc: 3 instr: eq stack: [0] fp: 0 pc: 4 instr: loadc 9 ...
Virtuaalmasin
- Virtuaalmasina programm on instruktsioonide list.
- Virtuaalmasina seisundiks on täsiarvude stack (implementatsioonis võiks kasutada listi andmestruktuuri), täisarvuline register fp ja täisarvuline register pc.
- Algseisus on stack tühi (s.t. []), pc = 0 ja fp = 0.
- Täidetav instruktsioon on programmi pc-s instruktsioon. Aga enne instruktsiooni täitmist suurendatakse pc-d ühe võrra. (S.t kui instruktsioon pc-d ei muuda, täidetakse järgmisena vaikimisi järgnev instruktsioon)
- Iga instruktsioon a) teisendab seisundit all defineeritud viisil, b) trükib midagi välja (instruktsioon printint) või c) paneb masina seisma (instruktsioon halt).
- Masin seiskub, kui jõutakse halt instruktsioonini või kui jõutakse faili lõppu.
Instruktsioonid
Igal instruktsioonil on kas null või üks täisarvuline argument. Alustame lihtsamatest instruktsioonidest.
halt
Masin seiskub.
loadc
laeb konstandi stacki peale
stack= xs loadc c stack= c:xs fp = y --------------> fp = y pc = z pc = z
s.t. fp ja pc jäävad samaks
dup
duplitseerib stacki pealmist väärtust
stack= x:xs dup stack= x:x:xs fp = y --------------> fp = y pc = z pc = z
add, sub, div, mul
aritmeetilised operatsioonid: liitmine, lahutamine, korrutamine ja jagamine.
stack= x:y:xs add stack= (y+x):xs fp = y --------------> fp = y pc = z pc = z stack= x:y:xs sub stack= (y-x):xs fp = y --------------> fp = y pc = z pc = z stack= x:y:xs mul stack= (y*x):xs fp = y --------------> fp = y pc = z pc = z stack= x:y:xs div stack= (y`div`x):xs fp = y --------------> fp = y pc = z pc = z
eq, leq, not
operatsioonid: võrdus, väiksem-võrdne ja eitus (tõene on 1 ja väär 0)
stack= x:y:xs eq stack= (if y==x then 1 else 0):xs fp = y --------------> fp = y pc = z pc = z stack= x:y:xs leq stack= (if y<=x then 1 else 0):xs fp = y --------------> fp = y pc = z pc = z stack= x:xs not stack= (if x==0 then 1 else 0):xs fp = y --------------> fp = y pc = z pc = z
printint
trükib välja stacki pealmise väärtuse (+reavahetus) NB! järelikult implementatsioon peab kasutama IO monaadi
stack= x:xs printint stack= xs fp = y --------------> fp = y pc = z pc = z
pop
stacki pealt elementide eemaldamin
stack= x:xs pop stack= xs fp = y --------------> fp = y pc = z pc = z stack= xs pop n stack= drop n xs fp = y --------------> fp = y pc = z pc = z
jump
hüpe stacki peal olevale instruktsiooni numbrile
stack= x:xs jump stack= xs fp = y --------------> fp = y pc = z pc = x
jumpz
valikuline hüpe (kui stacki peal on null)
stack= x:0:xs jumpz stack= xs fp = y --------------> fp = y pc = z pc = x stack= x:1:xs jumpz stack= xs fp = y --------------> fp = y pc = z pc = z
load
stackis sügavamal sees oleva väärtuse kopeerimine stacki peale
stack= xs load n stack= xs!!n : xs fp = y --------------> fp = y pc = z pc = z
store
stackis sügavamal sees oleva väärtuse ülekirjutamine stacki peal olnud väärtusega
stack= x1:x2:..:xm:[] store n stack= x2:..:xn-1:x1:xn+1:..:xm:[] fp = y -----------> fp = y pc = z pc = z
Järgnevaid instruktsioone on tarvis funktsioonikutsete implementeerimiseks. (näide ex3, ex4)
slide
stacki pealmise elemendi alt elementide eemaldamine
stack= x:xs slide n stack= x:drop n xs fp = y --------------> fp = y pc = z pc = z
loadsp
stacki viimase elemendi indeksi asetamine stacki peale
stack= xs loadsp stack= length xs - 1 : xs fp = y --------------> fp = y pc = z pc = z
loadfp
fp panemine stacki peale
stack= xs loadfp stack= y : xs fp = y --------------> fp = y pc = z pc = z
storefp
fp võtmine stacki pealt
stack= x:xs storefp stack= xs fp = y --------------> fp = x pc = z pc = z
loadr ja storer
load ja store instruktsioonid, mis töötavad relatiivselt fp registriga. (load ja store indekseerivad stacki pealt) Näiteks:
stack= xs loadr n stack= xs!!(length xs-1-y-n):xs fp = y --------------> fp = y pc = z pc = z stack= x1:x2:..:xm:[] storer q stack= x2:..:xn-1:x1:xn+1:..:xm:[] fp = y -----------> fp = y pc = z pc = z n = length xs-1-y-q
Baitkoodi faili laadimine
- Rea-kommentaarid algavad sümboliga '#'. Kommentaar võib tulla ka peale instruktsiooni. Parsimisel tuleks sisutühjad read (sh. kommentaarid) eemaldada.
- Iga instruktsioon paikneb omal real ja argumendid on eraldatud tühiku(te) ga. Parsimiseks saab kasutada funktsioone lines ja words.
- Koodis kasutatakse viitamiseks silte, mille kasutus tuleb parsimisel asendada konstantidega. Sildid algavad sümboliga ':'. (Enamasti kasutatakse silte instruktsiooni loadc argumendina.)
- Iga silt paikneb eraldi real ja viitab järgmisele päris instruktsioonile. (s.t kaks järjestikkust silti viitavad mõlemad samale instruktsioonile, mis tuleb peale silte.) Näiteks, silt mis on vahetult enne viiendat instruktsiooni (lugedes alates faili algusest nullist), vahetatakse välja konstandiga viis.
Näiteprogrammid
NB! Näiteväljundid on toodud masina töö näitamiseks s.t. teie ei pea taastootma täpselt sama väljundit.