Kääntäjätekniikka

Luento 20 (30.5.2017)

Funktionaalinen lähdekieli

ML/Haskell/Lisp/...

  • tietorakenteet ovat rekursiivisia puita
    • atomidata (kokonaisluvut ym)
    • puukonstruktorit
      • Lispissä NIL ja CONS, ML:ssä ja Haskellissa ohjelmoijan määriteltävissä
      • kuin funktioita mutta vain säilyttävät argumenttinsa tekemättä niille mitään
  • rekursiivinen hahmonsovitus ja paloittainen määrittely (ei Lispissä)
    • jos hahmo ei sovitu, testataan seuraavaa
  • funktiot ovat käsiteltävissä datana
    • funktio voidaan tallentaa muuttujaan, antaa parametrina funktiolle tai palauttaa funktiosta paluuarvona
  • funktioita voidaan luoda toisten funktioiden sisällä ja ne voivat viitata ulompien funktioiden paikallisiin muuttujiin
  • muuttujiin ei voi sijoittaa (Haskell ja ML)
    • sen sijaan voidaan luoda muuttuvia tieto-olioita

Funktio-ohjelman kääntämisen vaiheet

  • sokerinpoisto
    • hahmonsovituksen yksinkertaistus (pattern match compilation)
    • konstruktorikutsujen normalisointi
    • funktiomäärittelyiden sisäkkäistyksen poisto (lambda lifting tai closure conversion)
  • funktionaaliselle välikielelle (esim. STG) kääntäminen
  • konventionaaliselle välikielelle (LLVM IR, C, kolmiosoitekoodi) kääntäminen
  • ... loppuosa kuten tavallisissa kääntäjissä ...

Hahmonsovituksen kääntäminen

Idea:

case E of
  C p1 p2 p3 -> E1
  C p4 p5 p6 -> E2
  D p7       -> E3
  D p8       -> E4
  _          -> E5

(olettaen että p1 ja p4 ovat erillisiä, samoin p7 ja p8) käännetään muotoon

case E of
  C x1 x2 x3 -> case x1 of
                  p1 -> case x2 of
                          p2 -> case x3 of
                                  p3 -> E1
                                  _  -> E5
                          _  -> E5
                  p4 -> case x2 of
                          p5 -> case x3 of
                                  p6 -> E1
                                  _  -> E5
                          _  -> E5
                  _ -> E5
  D x4 -> case x4 of
            p7 -> E3
            p8 -> E4
            _  -> E5
  _ -> E5

Hahmonsovituksen vaikeus

  • Algoritmi on suoraviivainen jos hahmot ovat erillisiä ja kattavia
    • hahmot ovat erillisiä jos mikään arvo ei sovi useampaan kuin yhteen hahmoon
    • hahmojoukko on kattava jos jokainen arvo sopii johonkin hahmoon
  • Erillisyydestä luopuminen tekee kääntämisestä haastavaa
  • Ks. tarkemmin Philip Wadler: Efficient Compilation of Pattern-Matching. Luku 5 (s. 78–103) kirjassa The Implementation of Functional Programming Languages (pääkirjoittaja Simon L. Peyton Jones); Prentice-Hall 1987. PDF saatavilla

Konstruktorikutsujen normalisointi

Jos on määritelty

data T = C U V W

niin jokainen C lähdekielisessä lausekkeessa pitää muuttaa muotoon, jossa sillä on kaikki tarvittavat argumentit (tehdään \(\eta\)-lavennus):

(\ x y z -> C x y z)

Näin konstruktorien osittaisapplikaatio muuttuu funktioiden osittaisapplikaatioksi.

Lambda lifting

  • Sisäkkäiset funktiomäärittelyt voidaan poistaa tekemällä ns. lambda lifting
    • toisen funktion sisällä määritelty funktio siirretään toplevel-määrittelyksi
    • funktion käyttämät ulompien funktioiden paikalliset muuttujat muutetaan sen parametreiksi
f x = let g y = x + y in g
==>
f_g x y = x + y
f x = f_g x

Sulkeumamuunnos

  • Vaihtoehtoisesti funktioarvo voidaan esittää sulkeumana (closure)
    • sulkeuma sisältää
      • kutsuosoitteen (entry point address) ja
      • kopiot funktion vapaiden muuttujien arvoista
    • funktiolle pitää kutsuttaessa välittää osoite sen sulkeumaan (ns. static link)

Jos paikallisiin muuttujiin voi sijoittaa

  • Jos paikallisen muuttujan arvo voi muuttuja alustuksen jälkeen, välitetään arvon sijasta osoite muuttujaan
    • tällaiset muuttujat tulee kääntäjän sijoittaa muistisiivouksen alaiseen kekoon
      • ns. escape analysis
    • koskee sekä lambda liftingiä että sulkeumamuunnosta

Lambda lifting ja sulkeumamuunnos ovat melko sama asia

Tarkastellaan esimerkkiä

f x = let g y = x + y in g

Lambda lift tuottaa muodon

f_g x y = x + y
f x = g x

Sulkeumamuunnos tuottaa muodon

f x = let g = \[x] y -> x + y in g

Lausekkeen f 3 tuloksena on kummassakin tapauksessa muistiolio, jossa on tallennettuna 3 ja g:n kutsuosoite

  • lambda liftin tapauksessa ns PAP, eli partial application
  • sulkeumamuunnoksen tapauksessa sulkeuma

Spineless Tagless G-machine (STG)

  • Simon L. Peyton Jones and Jon Salkild: The spineless tagless G-machine. In FPCA '89 Proceedings of the fourth international conference on Functional programming languages and computer architecture, 184-201, 1989. doi:10.1145/99370.99385
  • Simon L. Peyton Jones: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine. Journal of Functional Programming 2 (2), 127–202, 1992. doi:10.1017/S0956796800000319
  • Simon Marlow and Simon Peyton Jones: Making a fast curry: push/enter vs. eval/apply for higher-order languages. Journal of Functional Programming 16 (4–5), 415–449, 2006. doi:10.1017/S0956796806005995 JYU access
  • Simon Marlow, Alexey Rodriguez Yakushev, and Simon Peyton Jones: Faster Laziness Using Dynamic Pointer Tagging. In ICFP '07 Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, 277–288, 2007. doi:10.1145/1291151.1291194
  • Alberto de la Encina and Ricardo Peña: From natural semantics to C: A formal derivation of two STG machines. Journal of Fuctional Programmming 19 (1), 47–94, 2009. doi:10.1017/S0956796808006746 JYU access

STG:n peruskieli

  • Lausekkeita ovat
    • muuttuja
    • vakio
    • funktiokutsu, jossa funktio ja argumentit ovat muuttujia tai vakioita
    • primitiivioperaatiot (esim. yhteenlasku)
    • rekursiivinen let, joka luo paikallisia muuttujia
    • case, jolla tehdään (ei-rekursiivinen) hahmonsovitus
  • Let-lausekkeessa ja toplevelissä muuttuja voidaan alustaa seuraavilla konstruktioilla:
    • funktiomäärittely
    • konstruktorikutsu, jossa on annettu oikea määrä parametreja
    • lauseke
  • Olennaisesti siis kuten kolmiosoitekoodi, mutta sisäkkäisellä lohkorakenteella
    • muistivaraus tapahtuu aina let-lausekkeessa (tai toplevelissä)

Laiska laskenta vs innokas laskenta

Laiskassa laskennassa (lazy evaluation) on kaksi olennaista komponenttia:

  • kun lauseke sidotaan muuttujaan, sitä ei vielä tässä vaiheessa lasketa
    • muuttujaan sidotaan ns. thunk, joka on olennaisesti parametriton funktiosulkeuma
    • kun muuttujan arvo halutaan selvittää, pitää tarkistaa, onko muuttujassa valmiiksi laskettu arvo vai thunk
  • kun thunk on laskettu, se korvataan laskennan tuloksella
    • hyödyllistä korvata thunk laskennan ajaksi erillisellä väliaikaisarvolla (blackhole)
      • jos muuttujasta löydetään blackhole, tarkoittaa se ikuista silmukkaa

Innokkaassa laskennassa (eager evaluation) lausekkeen arvo lasketaan loppuun ennen muuttujaan sijoittamista

Miksi STG oli tagless mutta ei enää

  • Jos ohjelmassa voi esiintyä laiskaa laskentaa, pitää joka kerta muuttujan arvoa selvittäessä varmistaa, onko muuttujassa thunk ja jos näin on, pitää sen arvo laskea
    • perusidea tallettaa joka arvo-olioon tagi, joka kertoo onko se thunk vai ei
    • jos on, kutsutaan thunkin laskentakoodia
  • Alkuperäisessä STG:ssä tagi ja sen testaus korvattiin seuraavasti:
    • joka arvolla on entry point
    • jos arvo on laskettu, sen koodi vain palauttaa arvon
    • joka muuttujan haku aiheuttaa epäsuoran kutsun
  • Nykyprosessoreilla tagin tarkistus on nopeampaa kuin epäsuora kutsu, joten STG ei ole enää tagless

Push/enter vs eval/apply

Tarkastellaan seuraavaa kutsua:

f a b c

Nyt f voi olla määritelty esimerkiksi

f x y = g
g z = z

jolloin kutsu tulee kääntää t1 := CALL f (a,b); CALL t1 (c). Tai f voi olla määritelty

f x y z = z

jolloin oikea kutsu on CALL f (a,b,c). Jos kääntäjä ei tiedä, miten f on määritelty, sen tulee varautua molempiin (ja lisäksi myös tapauksiin, joissa f ottaa yhden tai enemmän kuin kolme parametria).

Push/enter

f a b c

käännetään

PUSH c
PUSH b
PUSH a
CALL f

Määrittely

f x y = g
g z = z

puolestaan käännetään

f: IF not enough args GOTO f0
   POP    # x
   IF not enough args GOTO f1
   POP    # y
   CALL g
   RET
f0: Create closure for f, put to RAX
    RET
f1: Create a PAP for f(x), put to RAX
    RET
g: If not enough args GOTO g0
   POP rax # z
   RET
g0: create a closure for g, put to RAX
    RET

Eval/apply

f a b c

käännetään

CALL apply_3 (f,a,b,c)

missä apply_3 on kirjastofunktio, joka tekee suunnilleen näin:

VALUE *apply_3(VALUE *f, VALUE *a1, VALUE *a2, VALUE *a3)
{
    VALUE * tmp;
    switch (f->args) {
    case 0:
        return apply_3(f->entrypoint(), a1, a2, a3);
    case 1:
         tmp = f->entrypoint(a1);
         return apply_2(tmp, a2, a3);
    case 2:
         tmp = f->entrypoint(a1, a2);
         return apply_1(tmp, a3);
    case 3:
         return f->entrypoint(a1, a2, a3);
    default:
        return make_PAP(f, a1, a2, a3);
    }
}

Kumpi parempi?

Push/enter tuntuu yksinkertaisemmalta, mutta eval/apply on empiirisesti parempi.

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.