TIES448 Kääntäjätekniikka

Luento 1 (14.3.2017)

Opettajat

• Antti-Juhani Kaijanaho
  • yliopistonopettaja, FT
  • päävastuussa kurssista tänä vuonna
• Ville Tirronen
  • yliopistonlehtori, dosentti
  • isyysvapaalla tällä hetkellä
  • saattaa osallistua kurssin opetukseen myöhemmin

Viestintä

• Kurssin TIM-sivusto
• Slack
• yleinen postilista ties448_2017@korppi.jyu.fi
  • julkinen arkisto

Lähiopetus

• luennot 14.3.–1.6. ti ja to klo 10 (pääosin Ag C233)
  • pääsiäistauon 10.–17.4. aikana ei ole luentoja
  • helatorstaina 25.5. ei ole luentoa
• ohjauksia 20.3.–19.6. ma klo 16 (Ag C233)
• tarvittaessa myös ohjauksia pe klo 10
  • ei tällä viikolla
• ei läsnäolopakkoa, mutta luentoja EI TALTIOIDA

Kirjallisuutta

Luentojen pohjana

• Andrew W. Appel: Modern Compiler Implementation in Java. 2nd ed. Cambridge University Press, 2002.
• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: Principles, Techniques, & Tools. 2nd ed. Pearson Addison-Wesley, 2007.

Tarvittaessa viitataan myös tutkimuskirjallisuuteen ja muuhun lisämateriaaliin.

Etäopiskelijoille suosittelen vahvasti jomman kumman hankkimista. Myös muille ovat hyödyllistä lisäluettavaa.

Tentti

• tentillä 2 op, tällöin ei tehdä harjoitustyötä
• tentissä testataan, että opiskelija "tuntee kääntäjätekniikan perusteet lukuunottamatta varsinaisen optimoinnin tekniikoita"
  • ei algoritmien yksityiskohtia
• joko luentotentti tai kirjallisuustentti
• e-tentti avataan kesäkuussa
  • paperitentti voidaan laatia perustellusta syystä

Harjoitustyö

• 3-6 op, ei tehdä tenttiä
• deadline 19.6.2016
• tehdään 1–3 hengen ryhmissä
  • suositellaan vähintään 2 hengen ryhmiä työmäärän vuoksi

Harjoitustyön opintopistemäärän muodostuminen

• perusopintopistemäärä vähintään 3 op
  • lasketaan puolen opintopisteen tarkkuudella
• rekisteriin merkintää varten pyöristetään alaspäin lähimpään kokonaislukuun (max 6)
• mahdollinen ylijäämä korottaa arvosanaa:
  • 0,5 op:n ylijäämä +1
  • 1 op:n ylijäämä +2
  • ei isompia korotuksia

Akateeminen rehellisyys

• Kun käytät jonkun muun laatimaa koodia, tee tämä selväksi.
• Tee selväksi, miten olet muiden laatimaa koodia muuttanut.
• Puutteet estävät kurssisuorituksen hyväksymisen
  • varteenotettavat vilppiepäilyt viedään dekaanin tutkittavaksi
  • sanktio vakavimmillaan määräaikainen erottaminen yliopistosta
• Tarkemmin ks. aiempien kurssieni ohjesivu

Miksi opiskella kääntäjätekniikkaa?

Kääntäjätekniikka on haasteellista

• Kääntäjäprojektin tekeminen kehittää ohjelmointi- ja projektinhallintataitoja.
• Onnistunut kääntäjäprojekti voi olla vahva näyttö osaamisesta.

Teoria ja käytäntö yhdistyvät

• Kääntäjä on käytännönläheinen ja hyödyllinen ohjelma.
• Kääntäjän sisällä jylläävät algoritmit ja tietorakenteeet ovat epätriviaaleja ja pitkän tutkimustyön huipentumia.
  • Kääntäjätekniikka oli tietojenkäsittelytieteen merkittävä tutkimusalue 1960- ja 1970-luvuilla.
• Nykyisin tutkimus keskittyy aiheisiin, jotka eivät kuulu tämän kurssin ydinsisältöön.

Näkemystä kääntäjien toimintaan

• Kääntäjätekniikan tuntemus auttaa ymmärtämään teollisten kääntäjien aivoituksia.
• Olemassaolevia kääntäjiä ja kieliä oppii siten käyttämään paremmin.

Tietokonekielet

Määritelmä: Tietokonekieli on kieli, joka on tarkoitettu tietokoneen ymmärrettäväksi.

Esimerkkejä:

• monet dokumenttitiedostomuodot (.docx, .xml, .html, .odt, ...)
• useimmat sovellustason verkkoprotokollat (HTTP, ESMTP, NNTP, XMPP, ...)
• konfiguraatiotiedostot
• määrittelykielet (B, Z, VDM, ...)
• ohjelmointikielet

Konekielet

Määritelmä. Konekieli on tietokonekieli, jota tietokoneen keskusyksikkö ymmärtää sellaisenaan.

Huomautus. Käytännössä konekieltä ei ymmärrä suoraan rauta, vaan keskusyksikön sisällä on ns. mikrokoodilla kirjoitettu tulkki tai JIT-kääntäjä. Tämä ei kuitenkaan näy ohjelmoijalle.

Määritelmä. Yleensä konekielestä on olemassa ainakin yksi ihmisen luettavissa oleva versio, ns. symbolinen konekieli eli assembly, joka käännetään eri ohjelmalla (ns. assembler) konekieleksi.

Instruction Set Architecture

Konekieliä on erilaisia, ja tietokoneet jaetaan eri luokkiin (instruction set architecture eli ISA, suomeksi yleensä käskykanta-arkkitehtuuri) sen mukaan, mitä konekieltä kukin hallitsee:

• PC:issä nykyään yleensä x86-64 eli AMD64.
• Pitkään PC-koneissa oli x86(-32) eli IA32.
• Mobiililaitteissa yleisin on ARM.
• Aiemmin yleisiä mm. PowerPC, Sparc, 68000, 6502, Z80
• Teollisessa käytössä on kuitenkin useita kymmeniä erilaisia ISA:ita.

Välikielet

Määritelmä. Välikieli (engl. intermediate language) on ohjelmien kuvaamiseen tarkoitettu tietokonekieli, jota tuotetaan ohjelmallisesti ja joka suoritetaan joko tulkkaamalla tai edelleen kääntämällä.

Esimerkkejä.

• monilla kääntäjillä oma sisäinen välikielensä
• 1970- ja 1980-lukujen Pascalin P-code
• Java bytecode
• .NET:n CIL
• LLVM

Kääntäjien peruskäsitteitä

Määritelmä. Kääntäjä (engl. compiler) on tietokoneohjelma, joka ottaa yhdellä kielellä (lähdekieli, engl. source language) kirjoitetun tietokoneohjelman syötteenään ja tuottaa ulos saman tietokoneohjelman kirjoitettuna jollakin toisella kielellä (kohdekieli, engl. target language).

Huomautus. Usein kohdekieli on jokin konekieli, mutta ei aina.

Huomautus. Tavallisesti kohdekieli on lähdekieltä yksinkertaisempi. Jos tilanne on päinvastainen ja kääntäjä pyrkii idiomaattiseen kohdekoodiin, puhutaan takaisinkääntäjästä (engl. decompiler). Jos kielet ovat suunnilleen yhtä monimutkaisia, englannin kielessä käytetään yleisemmin sanaa translator.

Isäntäkieli

Määritelmä. Kieli, jolla kääntäjä itse on kirjoitettu, on sen isäntäkieli (engl. host language).

Huomautus. Toisinaan kääntäjän isäntäkieli ja lähdekieli ovat (olennaisilta osin) sama kieli. Tällöin kääntäjän odotetaan kykenevän kääntämään itsensä; tällainen kääntäjä on itsensä isännöivä (engl. self-hosting)

Isäntäarkkitehtuuri

Määritelmä. ISA, jossa kääntäjä on suoritettavissa, on sen isäntäarkkitehtuuri (engl. host architecture).

Huomautus. Tavallisimmin isäntäarkkitehtuuri on sama kuin kohdekieli. Jos näin ei ole, kääntäjä on ristiinkääntäjä (engl. cross-compiler).

Bootstrapping

Määritelmä. Prosessi, jolla itsensä isännöivä kääntäjä saadaan käännetyksi suoritettavaan muotoon, on nimeltään bootstrapping.

Luentotehtävä. Olet suunnitellut uuden ohjelmointikielen, ja haluat kirjoittaa sille itsensä isännöivän kääntäjän. Kuinka bootstrapping voisi onnistua?

Tulkki

Määritelmä. Tulkki (engl. interpreter) on tietokoneohjelma, joka ottaa syötteenään lähdekielisen tietokoneohjelman ja käyttäytyy sen jälkeen kuten kyseinen tietokoneohjelma. Tulkkia kutsutaan joskus myös virtuaalikoneeksi (virtual machine) tai simulaattoriksi.

Tulkkeja on kolmea päälajia:

• Klassinen tulkki suorittaa ohjelmaa sitä mukaa kuin lukee sitä.
• Moderni tulkki kääntää ohjelman ensin välikielelle ja luovuttaa tuloksen edelleen välikielen tulkille.
• JIT-kääntäjä (engl. just-in-time compiler) kääntää ohjelman tai sen osan konekielelle juuri, kun se tulee suorittaa, ja luovuttaa suorituksen välittömästi tämän jälkeen käännöksen tulokselle.

Kääntäjän rakenne

Selaaja

• ..., lekseri, selain, palastelija, tokenisoija, ...
• syötteenä lähdeohjelmaa esittävä merkkijono
• tulosteena jono sanasia (engl. token), pienimpiä merkityksellisiä osia, vrt. sanat suomen kielessä; tyypillisesti:
  • kokonaislukuvakio 521
  • merkkijonovakio "kissa"
  • välimerkki ;
  • luokan nimi Window
  • muuttujan nimi it
  • avainsana while
  • Välilyönnit ym. eivät yleensä ole sanasia.
• tuottaa virheilmoituksia ja varoituksia
• voi hylätä ohjelman virheellisenä.

Jäsentäjä

• ..., parseri, parsija, syntaktinen analysaattori, ...
• syötteenä selaajan tuottama sanasjono
• tulosteena rakennepuu eli abstrakti jäsennyspuu
  • engl. abstract syntax tree (AST)
  • tietorakenne, joka kuvaa ohjelman (staattisen) loogisen rakenteen
  • kukin sisäsolmu edustaa operaatiota ja sen lapsisolmut sen operandeja
• tuottaa virheilmoituksia ja varoituksia
• voi hylätä ohjelman virheellisenä.

Tarkastaja

• ..., semanttinen analysoija, staattinen tarkastaja, ...
• syötteenä jäsentäjän tai sokerinpilkkojan tuottama rakennepuu
• tulosteena (ehkä muokattu) rakennepuu
• tarkastaa, että ohjelmassa ei ole mitään sellaisia virheitä, joiden takia kääntäminen tulisi keskeyttää, esimerkiksi:
  • muuttujaa käytetään ennen määrittelyä
  • funktiolle annetaan väärä määrä parametreja
  • tyyppimäärittelyt ovat keskenään ristiriitaisia
  • myös usein lisää rakennepuuhun muistiinpanoja, esimerkiksi tyyppi-informaatiota
• Tarkastaja on viimeinen osa, joka voi hylätä ohjelman virheellisenä. Myöhemmät osat olettavat koodin olevan virheetöntä

Sokerinpilkkoja

• engl. desugarer
• ei ole kaikissa kääntäjissä
• syötteenä jäsentäjän tai tarkastajan tuottama rakennepuu
  • Valinta riippuu kääntäjästä.
  • Sokerinpilkkojan sijoittaminen tarkastajan jälkeen on käyttäjäystävällistä mutta monimutkaistaa tarkastajaa.
• tulosteena rakennepuu
• Pilkkoo käyttömukavuutta lisääviä rakenteita (eli syntaktista sokeria) yksinkertaisempiin osiin; esimerkiksi:

for (int i = 0; i < n; i++) { s(i); }
⇓
{ int i = 0; while (i < n) { s(i); i++; } }

Välikoodin generoija

• engl. intermediate code generator
• syötteenä tarkastajan ja sokerinpilkkojan läpikäymä rakennepuu
• tulosteena ohjelma välikielellä esitettynä
• Jotkut kääntäjät lopettavat kääntämisen tähän ja luovuttavat välikoodin tulkattavaksi virtuaalikoneelle.
  • mahdollista myös antaa toisen kääntäjän edelleen käännettäväksi

Optimoija

• syö ja tulostaa välikoodia tai
• syö ja tulostaa kohdekoodia
• koostuu tavallisesti monesta erillisestä osasta
• Analyysiosat tutkivat koodia ja tekevät siitä päätelmiä, joista sitten tehdään muistiinpanoja koodiin jatkokäyttöä varten.
• Muokkausosat muuttavat koodia analyysiosien tekemien havaintojen perusteella.
• monesti iteroidaan useita kertoja
• sivuutetaan tällä kurssilla

Kohdekoodin generoija

• engl. (target) code generator
• syö välikoodia
• tulostaa kohdekoodia
• jos kovin naiivi, tarvitsee usein kohdekoodin optimoijan (tyypillisesti ovisilmäoptimoija, engl. peephole optimizer) kaverikseen

Kääntäjän päät

Etupää, engl. front end. Kääntäjän etupää on se osa kääntäjästä, joka on tekemisissä lähdekielen erityispiirteiden kanssa – selaaja, jäsentäjä, tarkastaja, sokerinpilkkoja sekä välikoodin generoija.

Välipää, engl. middle end. Kääntäjän välipää on se osa kääntäjästä, joka ei ole sen paremmin lähdekielen kuin kohdekielenkään kanssa tekemisissä – suuri osa välikoodin optimoijasta.

Takapää, engl. back end. Kääntäjän takapää on se osa kääntäjästä, joka on tekemisissä kohdekielen erityispiirteiden kassa – kohdekoodin generoija, kohdekoodin optimoja sekä mahdollisesti osa välikoodin optimoijasta.

Kääntäjäkokoelmat

Taitavasti laadittu välipää mahdollistaa etupäiden ja takapäiden vaihtamisen tarvittaessa. Tyypillinen esimerkki on GNU Compiler Collection (GCC).

Kääntäjä, jonka takapää on vaihdettavissa, on tähdättävä kääntäjä, engl. retargetable compiler.

Moniosaiset kääntäjät

• Muinoin (ennen 1990-lukua) tietokoneiden työmuistit olivat niin pieniä, etteivät kääntäjä ja koko käännettävä ohjelma mahtuneet yhtä aikaa muistiin.
• Yksiosainen kääntäjä (one-pass compiler) käänsi ohjelmaa rivi tai aliohjelma kerrallaan sitä mukaa kuin sitä luki.
• Moniosainen kääntäjä (multi-pass compiler) koostui monesta eri ohjelmasta, jotka kommunikoivat aputiedostojen avulla.
  • esim. jäsentäjä oma ohjelmansa
• Nykyään aika lailla kuollut ongelma. Ohjelma ja kääntäjä mahtuvat muistiin ongelmitta, eikä tarvetta kikkailuun ole enää.
  • sana pass esiintyy edelleen, mutta saisi kuolla tarpeettomana

Kääntäjä osana käännöstyökalustoa

Nykyaikana kääntäjät tuottavat harvoin suoraan ajettavaa ohjelmaa. Tulos on yleensä joko symbolista konekieltä tai linkittämätön konekielinen ohjelmayksikkö.

Kääntäjän ajuri

• lyhyt ohjelma, joka yhdistää kääntäjän eri osat sekä kääntäjän ulkopuoliset välineet (assembleri, linkkeri)
• helpottaa kääntäjän käyttämistä
• esim. komento gcc ei ole kääntäjä, vaan ajuri

Harjoitustyö

• vaatimukset
• Muodostetaan 1–3 hengen ryhmiä.
• Kukin ryhmä laatii 19.6. mennessä toimivan kääntäjän. (deadline siirretty 1.6.2017: uusi deadline 28.8.2017)
• Työ jakaantuu seitsemään inkrementtiin.
• Työtä ohjataan ja seurataan ohjauksissa.
• Inkrementtien aikataulussa pysyminen vaikuttaa arvosanaan.

Inkrementit

(deadlineja päivitetty 1.6.2017)

Alustava deadline sulkeissa (klo 16 kyseisenä päivänä ellei muuta ilmoitettu)

1. Suunnittelu ja ryhmien muodostaminen (20.3.)
2. Jäsentäjä valmis (perjantai 7.4. klo 10)
3. Tarkastaja valmis (perjantai 5.5. klo 10)
4. Välikielen generointi valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (15.5.)
5. Kohdekielen generointi (naivi rekisteriallokaatio) valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (19.6.)
6. Fiksu rekisteriallokaatio valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (14.8. klo 12)
7. Koko työ viimeistelty ja valmis tarkastettavaksi (28.8. klo 12)

Inkrementtien palautus

• Tehkää yhteinen Git-varasto Yousourceen tai Githubiin
• Jos ette halua julkiseksi, käyttäkää Yousourcea
  • Antakaa tarkasteluoikeus käyttäjille antkaij ja aleator.
• Inkrementti on palautettu, kun se on pushattu ja tagattu ko. repossa

Suunnitelmassa oltava

• kääntäjän työnimi
• ryhmäläisten nimet ja yhteystiedot (vähintään sähköpostiosoite)
• lähdekielen alustava määrittely (myös alustavia esimerkkiohjelmia)
• kohdekielen alustava määrittely
• isäntäkielen valinta
• mahdollisesti vaatimusten prioriteettijärjestys
• ryhmän alustava vastuualuejako
• alustava testaussuunnitelma

Lähdekieli

• suositeltavaa ottaa olemassaoleva ohjelmointikieli pohjaksi
• suunnitelmassa hahmoteltava poikkeamat pohjaksi otetusta kielestä
• Kurssin aikana keretään todennäköisesti toteuttaa vain osa kielestä, joten halutut ominaisuudet on hyvä priorisoida.

Hyviä kohdekieliä

• Oikea konekieli (lähinnä AMD64 ja ARM)
  • sallittua on tuottaa symbolista konekieltä,
  • suositeltavaa, että tällöin kääntäjä kutsuu assembleria automaattisesti
  • kiinnitä myös käyttöjärjestelmä (esim. Linux tai Windows)
• Standardoitu välikieli (LLVM, Java bytecode, .NET CIL)
  • huomaa vaikutus opintopistemäärään

Isäntäkielen valinnasta

• mikä tahansa ohjelmointikieli, jonka tulkkaaminen tai kääntäminen onnistuu luentosalissa (viimeistään omalla läppärillä)
• kiinnitä huomiota:
  • Kuinka hyvin kieli tukee laajojen ohjelmien tekemistä?
  • Kuinka helppoa sillä on käsitellä puu- ja graafitietorakenteita?
  • Onko sille olemassa kielioppityökaluja (vrt. yacc, CUP)?
  • Kuinka hyvin osaat kieltä jo valmiiksi?
• Suosittelen Haskellia ja muita ML-suvun kieliä (SML, OCaml),
  • vain jos osaat niitä jo valmiiksi.

Vastuun jako

Ryhmässä on hyvä jakaa seuraavat vastuut:

• ryhmänjohtaja, joka huolehtii siitä, että tekeminen etenee ja ratkaisee kiistat siitä, kuka tekee mitäkin
• (lähde)kielitsaari, joka ratkaisee kiistat lähdekielen ominaisuuksista
• testi-inkvisiittori, joka vastaa testauksen kattavuudesta
• kohdekieliguru, joka tutustuu kohdekielen saloihin ja selvittää tarvittaessa vastaukset kohdekieltä koskeviin kysymyksiin
• työkaluguru, joka tutustuu valittuihin työkaluihin ja selvittää tarvittaesa vastaukset työkaluja koskeviin kysymyksiin

Luonnollisesti samalla henkilöllä voi olla useita rooleja. Jokainen tietenkin osallistuu itse tekemiseen!

Harjoitustyöstä selviälminen

• aloita heti
• älä pysähdy
• ajattele mitä teet
• pyydä apua ajoissa
• pidä tuntikirjanpitoa
  • jos op-määrät ylittyvät perustellusti, voidaan harkita ylimääräisten opintopisteiden antamista toisella koodilla (esim. ohjelmointityö tai erikoistyö)

Opettajien esimerkkikääntäjät

AJK 2009

• Lähdekieli on C-kielestä mallia ottava kieli, joka tukee yksinkertaista olio-ohjelmointia ja yksinkertaista innokasta funktio-ohjelmointia.
• Kohdekielenä on AMD64:n symbolinen konekieli (nasm) Linuxissa.
• Isäntäkielenä on Java...
  • ...koska se on kaikille toivottavasti tuttu.
  • En varsinaisesti suosittele.
• YouSourcessa

AJK 2016 (laskin-py)

• puolivahingossa kääntäjäksi levinnyt luentoesimerkki
• C-sukuinen kieli
• kohdekielenä AMD64 (nasm, Linux)
• isäntäkielenä Python3
• Yousourcessa

VT 2016

Villen tarkoitus oli tehdä:

• Lähdekieli
  • Proseduraalinen
  • Sisennyspohjainen
  • Tyypinpäättely
  • Vedetty hatusta
• Kohdekieli on LLVM (ja ehkä AMD64)
• Isäntäkieli Haskell

Löytyy Yousourcesta

AJK 2017

Saa nähdä.

Luentojen sisällöt karkeasti

Voi muuttua ilman etukäteisilmoitusta

• Johdanto (1 luento)
• Konekielinen ohjelmointi (2 luentoa)
• Selaajat, jäsentäjät ja rakennepuut (3 luentoa)
• Staattinen analyysi (3 luentoa)
• Välikielen generointi (3 luentoa)
• Käskyjen valinta (3 luentoa)
• Rekisterien valinta (3 luentoa)
• Erityiskysymyksiä (4 luentoa) tilanteen mukaan, esimerkiksi
  • laiska laskenta
  • tyyppipäättely
  • roskienkeruu
  • perintä ja myöhäinen sidonta oliokielissä