Kääntäjätekniikka

Luento 6 (14.4.2016)

Luennon aiheena tarkastaja

Staattinen semantiikka

• semantiikka eli merkitysoppi: yleensä ohjelmointikielten tapauksessa kaikki se, mikä ei ole (kontekstittomalla) kieliopilla (helposti) kuvattavissa
• staattinen: käännösaikana tiedossa oleva
• staattinen semantiikka: mm. käännösaikaiset oikeellisuustarkastukset
  • joissakin kielissä puhutaan rajoitteista (constraints)

Lohkorakenne ja symbolitaulut

Mitä seuraava ohjelma tulostaa?

Lohkorakenne

• Useimmissa kielissä on lohkorakenne.
  • Ohjelmateksti jaetaan lohkoihin.
  • Kaksi lohkoa ovat kokonaan erilliset tai sitten toinen on toisen sisällä.
  • Aktiiviset lohkot muodostavat siten pinorakenteen.
• Lohkoja:
  • Koko ohjelma on lohko (ns. globaali lohko).
  • Moduli (käännösyksikkö tms.) on lohko.
  • Luokka on lohko.
  • Funktio (sisältäen myös parametrilistan) on lohko.
  • Silmukkalause on (joissakin kielissä) lohko.

Lohkorakenteisen kielen nimisäännöt

• Nimen määritelmän lohkolla tarkoitetaan sisintä lohkoa määritelmän kohdalla.
• Nimi saadaan määritellä useampaan kertaan vain, jos joka määritelmällä on eri sisin lohko.
• Toisin sanoen jos saman sisimmän lohkon alueella määritellään sama nimi kahdesti, on virhe diagnosoitava.
• Kullakin hetkellä näkyy vain sisin määritelmä; muut määritelmät ovat piilossa.

Symbolitaulu

• Kääntäjässä nimen ja sen merkityksen yhdistää symbolitaulu.
  • merkkijonoilla indeksoitu taulu, jonka alkioita ovat määritelmät (tai niistä tehdyt muistiinpanot).
• Symbolitaulun tulee ottaa huomioon ohjelman käsittelyn edetessä sen lohkorakenne.
• Symbolitaulun tulee hallita nimen piilotus oikein.

Symbolitaulu, vaihtoehto I

• Luodaan joka lohkolle oma symbolitaulunsa.
• Symbolitaululla voi olla viite ympäröivän lohkon (engl. enclosing scope) symbolitauluun.
• Jos symbolitaulu ei tiedä nimestä mitään, se kysyy ympäröivän lohkon symbolitaululta.
• Tietorakennevalinta?
  • Hajautustaulu erinomainen jos nimiä on paljon (esim. globaali ja modulin symbolitaulu) mutta muuten tilasyöppö.
• Lineaarinen haku (linkitty lista tai taulukko) kilpailukykyinen jos nimiä vähän (esim. silmukkalohko).
• Esim. AJK-2009

Symbolitaulu, vaihtoehto II

• Yksi iso hajautustaulu, jota päivitetään määritelmien sekä lohkojen alun ja lopun osuessa kohdalle.
• Apuna pino, johon pistetään muistiin nimen vanha määritelmä.
• Lohkoon tultaessa pinoon pistetään merkki.
• Lohkosta poistuttaessa perutaan pinon avulla kaikki määritelmät lähimpään merkkiin asti.
• Lohkot numeroitava jotta duplikaattimääritelmä voidaan diagnosoida.
• esim. AJK-2016

Symbolitaulu, vaihtoehto III

• Perusidea sama kuin vaihtoehdossa I: joka lohkolla oma symbolitaulunsa.
• Tehdään Copy-On-Write (COW) -kopio ympäröivän lohkon symbolitaulusta.
• Tietyillä tietorakenteilla (esim. binääriset hakupuut) on tämä kopiointikin mahdollista rajata koskemaan vain osaa symbolitaulusta.
• esim. VT-2016

Symbolitaulun (osittainen) vaihtoehto

• Tavallisesti jonkinlaista symbolitaulua tarvitaan koko käännöksen aikana.
• Tätä voidaan rajoittaa linkittämällä rakennepuussa viittaus nimeen siihen määritelmään, johon ko. nimiviittaus viittaa.
• Linkityksessä tarvitaan symbolitaulua, sen jälkeen ei.

Mitä seuraava ohjelma tulostaa?

Staattinen vs dynaaminen lohkotus

• Vaihtoehdot:
  • staattinen lohkotus: aliohjelma näkee (vain) ne muuttujat, jotka ovat sen määrittelykohdassa näkyvissä (ohjelma tulostaa 4)
  • dynaaminen lohkotus: aliohjelma näkee kutsupaikalla näkyvissä olevat muuttujat (ohjelma tulostaaa 6)
• Tulkkaava toteutus toteuttaa dynaamisen lohkotuksen luonnostaan, staattinen lohkotus on tulkille työläämpi.
• Kääntäjälle staattinen lohkotus olennaisesti helpompi.
• Useimmiten dynaaminen lohkotus on bugi.
  • ... paitsi Lispissä jossa se muuttui bugista featureksi

Tyyppitarkastus

Huomautus tyyppitarkastuksesta

• Tällä luennolla käsitellään vain staattista tyyppitarkastusta.
• Tarkoituksena on diagnosoida tyyppivirheet käännösaikana.
• Jos kieli onkin dynaamisesti tyypitetty, ei tämän osan tekniikoita tarvita.

Tyyppi

• Tyyppi on ohjelmatekstin osaa liitettävä tunnus, joka kertoo, minkälaisten arvojen tai olioiden kanssa kyseinen ohjelmatekstin osa on tekemisissä.
  • Lausekkeen tyyppi luokittelee sen laskemisen tuloksena syntyvät arvot.
  • Funktion tyyppi kertoo, minkätyyppisiä arvoja ja kuinka monta se ottaa parametriksi ja mitä se palauttaa.
  • Lauseella ei yleensä ole tyyppiä, mutta se voi sisältää diagnosoitavia tyyppivirheitä.
  • Määrittelyllä ei yleensä ole tyyppiä, mutta se määrittelee uuden nimen ja sille tyypin, ja saattaa sisältää diagnosoitavia tyyppivirheitä.

Yksinkertaiset tyypit

• Ohjelmointikieli määrittelee joukon perustyyppejä:
  • Perustyypit edustavat yleensä matemaattisia joukkoja kuten kokonaislukuja modulo \(2^{64}\) tai totuusarvoja.
  • Perustyypillä ei ole lainkaan ohjelman manipuolitavissa olevaa sisäistä rakennetta, joten
  • perustyypin arvoja ja olioita käsitellään vain perusoperaatioiden (esimerkiksi +, ∗) ja niistä johdettujen aliohjelmien avulla.
• Lisäksi ohjelmointikieli määrittelee joukon tyyppikonstruktoreja, mm.
  • funktiot
  • tietueet eli struktuurit
  • variantit
  • taulukot
• Luokat eivät ole yksinkertaisia tyyppejä.

Lausekkeen tyyppitarkastus

• Tarkastus etenee rakennepuussa alhaalta ylös, lehtisolmuista juureen.
  • läpikäynti jälkijärjestyksessä
  • kunkin solmun käsittelyssä tiedossa sen lapsisolmujen tyyppi; solmun tehtävä selvittää oma tyyppinsä
  • tyyppi on siten synteettinen attribuutti
• Lehtisolmuja ovat vakiot ja muuttujat:
  • Vakion tyyppi on yleensä trivialiteetti.
  • Muuttujan tyyppi haetaan symbolitaulusta ko. muuttujan nimellä.
• Sisäsolmut ovat operaatioita. Pääsääntö:
  1. Tarkastetaan ensin, onko lapsisolmuilla operaation vaatimat tyypit.
  2. Solmun oma tyyppi riippuu operaatiosta (ja joskus lapsisolmujen tyypeistä).
• Lause tyyppitarkastetaan kuten lauseke, mutta lausesolmuilla ei ole tyyppiä.

Sijoituslauseen tarkastus

• Usein sijoituslause on muotoa \(E = E\), missä \(E\) on lauseke.
• Vasen lauseke kertoo muistipaikan, johon oikean arvo tallennetaan.
  • Left value eli lvalue tarkoittaa lausekkeen tulkintaa sijoituslauseen vasemmalla puolella, ja
  • Right value eli rvalue tarkoittaa lausekkeen tulkintaa sijoituslauseen oikealla puolella.
• Vain osa lausekkeista kelpaa vasemmalle puolelle (eli vain osalla lausekkeista on lvalue).
  • Esimerkiksi a[i] on lvalue mutta x + y ei (yleensä) ole.
• Sijoituslauseen tarkastus:
  • Tee tyyppitarkastus molemmille lausekkeille.
  • Tarkista, että molemmilla on sama tyyppi.
  • Tarkista vielä, että vasemmalla lausekkeella on lvalue.

Aliohjelman määrittely

• Aliohjelman määrittelystä on tarkastettava että
  • sen nimeä ei ole jo määritelty samassa sisimmässä lohkossa,
  • sen parametrien nimissä ei esiinny toistoa,
  • sen parametreille on annettu hyväksyttävät tyypit,
  • että sen runko on hyvin tyypitetty silloin kun parametrinimeillä on ne tyypit, jotka niille on määrittelyssä annettu, ja
  • sen rungossa palautetaan määrittelyn vaatimaa tyyppiä oleva arvo (mikäli määritelmä sen vaatii) silloin kun parametrinimillä on ne tyypit, jotka niille on määrittelyssä annettu.

Aliohjelmakutsu

• Aliohjelmatyypin arvoa voi käyttää aliohjelmakutsun vasemmalla puolella.
• Aliohjelmakutsusta f(a1, ... , an) on tarkastettava, että
  • f:n tyyppi on n-parametrisen aliohjelman tyyppi,
  • f:n tyypissä on paluutyyppi, jos kutsu esiintyy lausekkeessa, tai että f:n tyypissä ei ole paluutyyppiä, jos kutsu esiintyy lauseena, ja
  • kunkin ai:n tyyppi kelpaa f:n tyypin i:nnen parametrin tyypiksi.
• Kutsun tyyppi on f:n paluutyyppi (jos sellainen on).
• Onko aliohjelmakutsulla lvalue?

Tietueet

• Tietuemääritelmä määrittelee uuden tyyppinimen ja koostuu tietueen sisällä näkyvistä muuttujamäärittelyistä (ilman alustusta) eli kentistä.
• Tietuemäärittelystä on tarkastettava, että
  • samaa kenttää ei määritellä useasti,
  • kenttien tyypit ovat sellaiset, että ne kelpaavat tähän käyttöön.
• Tietuetta käytetään projektio-operaattorilla e.l; siitä on tarkastettava, että
  • e:llä on tietuetyyppi ja
  • l on e:n tyypissä määritelty kenttä.
  • Tällaisen lausekkeen tyyppi on l:lle e:n tyypissä määritelty tyyppi.
  • Tällaisella lausekkeella on lvalue, jos e:llä on lvalue.

Varianttityyppi

• Varianttityyppi on kuin tietue, mutta sen kentät ovat muistissa päällekkäin, ei peräkkäin.
• Vain yksi variantin kentistä on aktiivinen kulloinkin. Varianttiin sisältyy lisäksi tieto siitä, mikä kentistä on aktiivinen.
  • ns. tagged union (toisin kuin C:n union)
• Tyyppitarkastus kuten tietueelle.
• Lisäksi variantti tarjoaa jonkin tavan selvittää, mikä kenttä on kulloinkin aktiivinen, esim. sopivasti muokattu switch–case-lause

Tyyppien yhtäläisyys

• Tyyppitarkastuksessa olennainen kysymys on, milloin kaksi tyyppiä ovat yhtäläiset.
• Pääsääntö:
  • Perustyypit ovat yhtäläisiä vain itsensä kanssa.
  • Rakenteiset tyypit (funktiot ym.) ovat yhtäläisiä jos niiden rakennepuut ovat samanlaiset sen jälkeen, kun tyyppinimet on korvattu niiden määritelmillä
  • Tätä sanotaan rakenneyhtäläisyydeksi.
• Rakenneyhtäläisyys on epätriviaalia jos rekursiiviset tyyppimäärittelyt ovat sallittuja.
• Yksinkertainen ratkaisu on nimiyhtäläisyys:
  • Kaksi tyyppinimeä ovat samat jos ne viittaavat samaan tietuetyypin määrittelyyn.

Luokat

• Luokat ei enää sisälly yksinkertaiset tyypit -järjestelmään.
• Yksinkertaisimmillaan luokka on tietue, jossa on lisäksi mahdollisuus määritellä yläluokka.
• Tarkastuksen huomattava yläluokan nimien overriding ja siihen liittyvät virheet.
• Lisäksi mahdollisesti näkyvyysaluetarkastukset (private jne).
• Tavanomaisessa mallissa luokka määrittelee tyypin; jos sillä on yläluokka, niin luokan ja yläluokan välille muodostuu alityypityssuhde.

Alityypitys

• Alityypitys on tyyppien välinen osittaisrelaatio.
• Sen pohjana on monissa kielissä luokkien väliset perintäsuhteet.
• Kaksi tyyppiä ovat ekvivalentit, jos ne ovat toistensa alityyppejä.

Alityypityksen laajentaminen

• Tietue ei voi alityypittyä, jos sen kenttiin voi sijoittaa.
• Aliohjelmatyyppi on kovariantti paluutyyppinsä suhteen mutta kontravariantti parametrityyppinsä suhteen.
  • Epäintuitiivista!
• Kovarianssi tarkoittaa, että jos f:n tyyppi on g:n tyypin alityyppi, niin f:n paluuarvon tyyppi on g:n paluuarvon tyypin alityyppi.
• Kontravarianssi tarkoittaa, että jos f:n tyyppi on g:n tyypin alityyppi, niin g:n argumentin tyypin tulee olla f:n argumentin tyypin alityyppi.

Varianssin muistisäänöt

• Arvon lähde alityypittyy kovariantisti.
  • Esimerkiksi tietue, jonka kenttiin ei saa sijoittaa.
  • Myös: aliohjelman paluuarvo.
• Arvon kohde alityypittyy kontravariantisti.
  • Tyypillinen esimerkki on aliohjelman parametri.
• Arvon yhdistetty lähde–kohde ei alityypity (eli on invariantti).
  • Tyypillisiä esimerkkejä ovat osoitintyyppi, taulukkotyyppi ja tietuetyyppi.
• Moni kieli rikkoo invarianssisääntöjä. Tästä seuraa velvoite dynaamiseen tarkastukseen.