Automaadid, keeled ja translaatorid - Kursused

Skoobid

Taust

Nii programmide interpreteerimise kui ka sageli muu semantilise analüüsimise juures on väga oluline järgida muutujaid ja nende väärtusi. Selle muudavad keeruliseks muutujate skoobid, mis määravad ära selle, milliseid muutujaid ja milliste väärtustega igas programmi punktis kasutada on võimalik.

Näited huvipakkuvatest olukordadest

Sama nimega erinevad muutujad

var x = inputInt();

if x % 2 == 0 then {
    printInt(x)
} else {
    var x = 1;
    printInt(x)
};

printInt(x)

Defineerimata muutuja kasutamine

var x = inputInt();

if x % 2 == 0 then {
    var y = 0;
    printInt(x)
} else {
    var y = 1;
    printInt(y)
};

printInt(y)

Mõisted

Muutuja (variable)

Sõna 'muutuja' kasutatakse kahes tähenduses:

programmi tekstist rääkides mõeldakse selle all tavaliselt ühte süntaktilist konstruktsiooni, mis koosneb mingist nimest ja on harilikult avaldise alamliik, nt. x. Kui tahetakse seda tähendust rõhutada, siis öeldakse muutuja viide või viide muutujale;
programmi jooksutamisest rääkides mõeldakse selle all tavaliselt mingit nimega väärtust või mälukohta.

Need tähendused on seotud: muutuja esimeses tähenduses (e. muutuja viide) tähistab mingit muutujat teises tähenduses (e. nimega väärtust või mälukohta).

NB! Muutuja ei pea olema tingimata muudetav (SML, Haskell, matemaatika), tähtis on see, et muutuja kasutamisel me (harilikult) ei tea, millise konkreetse väärtusega see programmi käivitamisel seotud on.

Vabad vs. seotud muutujad (free vs. bound variables)

Informaatikas

Termineid vaba vs. seotud muutuja kasutatakse harilikult koodilõikude kohta. Muutuja on vaba, kui näidatud koodis ei ole muutuja definitsiooni või olemuse kohta mingit infot, vastasel juhul on muutuja seotud. Näiteks avaldises print(x + 1) on muutuja x vaba, aga programmilõigus var x = 10; print(x + 1) on seotud.

Kui vaadelda terviklikku programmi, mitte ainult selle lõiku, siis vaba muutuja on selles programmis deklareerimata muutuja.

Matemaatikas

Sama terminoloogiat kasutatakse ka matemaatikas. Vaatame järgmist predikaatarvutuse valemit:

 ∀x.∀y.x&y∨z

Siin on muutujad x ja y seotud, aga muutuja z on vaba.

Veel üks näide (http://en.wikipedia.org/wiki/Free_variables_and_bound_variables):

Siin on muutuja n vaba ja muutuja k on seotud.

Skoop (scope)

Ka sõna 'skoop' kasutatakse mitmes pisut erinevas tähenduses:

skoop võib tähendada mingit koodi piirkonda; näiteks globaalseks skoobiks nimetatakse harilikult tervet programmi (või moodulit), funktsiooni keha nimetatakse lokaalseks skoobiks, siit on ka näha, et mingi osa programmist võib korraga kuuluda mitmesse skoopi;
muutuja skoop on see osa programmi koodist, kus konkreetne muutuja (kui nimega väärtus või mälukoht) on nähtav/viidatav;
kui muutuja on mingis programmi kohas nähtav, siis öeldakse, et see muutuja on antud kohas skoobis.

Näide Pythonis

x = 123

def blah(y):
    x = 10
    print(y*x)

z = "tere"
print(z)

Proovime selle näite põhjal kasutada sõna 'skoop' kolmel viisil:

globaalne skoop on read 1-8, funktsiooni blah lokaalne skoop on read 4-5;
globaalse muutuja x skoop on read 2,3,6,7,8, globaalse z skoop on rida 8, lokaalse x skoop on rida 5 ja lokaalse muutuja y skoop on read 4 ja 5;
real 5 on lokaalne muutuja y skoobis, aga real 8 ei ole.

Nimede sidumine (name binding)

Muutujate kasutamise teeb keerulisemaks see, et enamik programmeerimiskeeli lubab kasutada sama nime erinevate muutujate tähistamiseks. Protsessi, mis paneb nimede esinemised vastavusse õigete muutujatega, nimetatakse nimede sidumiseks. Erinevates keeltes on selle jaoks erinevad reeglid. Iga programmeerija peab pidevalt seda protsessi enda peas käivitama, et programmist õigesti aru saada.

Väärtuskeskkond (environment)

Kui skoop on programmi koodi kohta käiv termin, siis väärtuskeskkond on programmi käivitamise kohta käiv termin.

Väärtuskeskkond on kujutus, mis seab mingile muutujale vastavusse tema väärtuse, seega Javas mingi keele interpretaatorit kirjutades võiks lihtsat väärtuskeskkonda esitada objektiga, mille tüüp on üldiselt Map<Muutuja, Väärtus> või konkreetsemalt näiteks Map<String, Integer>.

Klassikaliselt on programmi käivitamisel kõigepealt globaalne skoop, milles hoitakse globaalseid muutujaid ja mis eksisteerib programmi sulgemiseni. Iga funktsiooni väljakutsel luuakse ajutine lokaalne skoop, mis hoiab lokaalseid muutujaid ja mis kaob funktsiooni töö lõppemisel.

Mõnedes keeltes (nagu näiteks C, Java või AKTK) on iga plokk samuti eraldi lokaalne skoop:

void blah() {
     if (...) {
          int x = 1;
          ...
     } else {
          int x = 2;
          ...
     }
}

Konkreetse programmeerimiskeele reeglid määravad, millisest skoopidest tuleb väärtust otsida, kui interpretaator peab väärtustama mingi muutujaviite. Enamasti korraldatakse asi nii, et iga programmipunkti jaoks on teada järjestatud skoopide ahel (nt. sisemise ploki, välise ploki, funktsiooni ja lõpuks globaalne skoop), kust muutuja väärtust otsitakse.

Kui samanimelist muutujat on programmeerimiskeeles lubatud deklareerida korraga mitmes skoobis, siis väärtuskeskkonna hoidmiseks ei piisa enam nii lihtsast Map andmestruktuurist, sest sama muutuja jaoks võib olla vaja hoida kahte erinevat väärtust ning seejuures muutujateviidete väärtustamisel kuidagi teada, millist kasutada.

Väärtuskeskkonna harjutus (IntegerEnvironment)

Kodutöö interpretaator peab hakkama saama erinevates skoopides deklareeritud muutujatega, mida on kõige parem hallata spetsiaalse väärtuskeskkonna andmestruktuuriga, mis on teadlik ka skoopidest. Kuna skoobitud muutujatega kaasnevad mitmed erijuhud, siis harjutamise mõttes implementeerime väärtuskeskkonna andmestruktuuri IntegerEnvironment, kus muutujateks on sõned ja nende väärtusteks täisarvud.

Täpsemad nõuded on järgmised:

Meetod declare deklareerib praeguses skoobis uue muutuja.
Meetod assign omistab muutujale uue väärtuse kõige sisemises skoobis, kus see muutuja deklareeritud on.
Meetod get tagastab muutuja praeguse väärtuse kõige sisemises skoobis, kus see muutuja deklareeritud on.
Deklareerimata või väärtustamata muutujate korral peaks tagastama null.
Meetod enterBlock tähistab uude skoopi (plokki) sisenemist.
Uues skoobis võib üle deklareerida välimiste välimise skoobi muutujaid.
Meetod exitBlock tähistab praegusest skoobist (plokist) väljumist.
Unustama peaks kõik sisemises skoobis deklareeritud muutujad.
Esialgu peaks olemas olema globaalne skoop, kuhu saab muutujaid deklareerida enne ühtegi skoopi (plokki) sisenemist.

Seda andmestruktuuri kontrollib IntegerEnvironmentTest, mille teste tasub samuti uurida.

Automaadid, keeled ja translaatorid 2018/19 kevad