Kääntäjätekniikka

Luento 19 (23.5.2017)

Mikä on funktiokieli?

• funktioiden määrittelyitä
  • funktio määritellään parametreilta lausekkeelle
• ei lauseita, ei olioita, (ei muuttuvaa tilaa)
• funktiot ovat arvoja
  • "tuntemattoman" funktion kutsu pitää hoitaa kunnolla
• funktioita voidaan määritellä toistensa sisällä
• joissakin kielissä laiskuus

Funktiokielten kääntämisen erityishaasteita

• idiomaattinen funktio-ohjelmointi soveltuu huonosti sellaisenaan von Neumannin koneen suoritettavaksi
  • kääntäjäoptimoinnit ovat olennaisempia kuin perinteisissä kielissä
• funktiot ovat lyhyitä ja koostuvat pääosin funktiokutsuista
  • funktiokutsu pitää tehdä erittäin nopeaksi
• silmukkarakenteita ei ole tai niitä ei juuri käytetä jos on:
  • pääosin käytetään mapin ja filterin kaltaisia funktionaaleja
    • funktion välittämisen parametrina pitää toimia
  • lisäksi käytetään (häntä)rekursiota
    • häntäkutsun poisto ei ole optimointi vaan olennainen osa kielen semantiikkaa
• muistia varataan keosta todella usein ja suurin osa muuttuu roskaksi lähes välittömästi
  • muistinvaraus pitää tehdä erittäin nopeaksi
  • roskienkeruun pitää olla tehokasta ja mielellään välttää ohjelman pysäyttämistä pitkäksi aikaa
• joidenkin kielten laiskuus tuo lisähaastetta

Funktiot funktiokielissä

• funktio voidaan määritellä toisen funktion sisällä, ja sisempi funktio voi käyttää ulomman paikallisia muuttujia
  • ns. funarg-ongelma
• funktio voidaan välittää parametrina toiselle funktiolle

Haasteellisia kohtia

• tyyppitarkastus
  • tyypinpäättely! Hindley-Milner
• "lähdekielen tason" optimointi, erityisesti inlining
• sokerinpoistaja, erityisesti pattern matching
• laiskuus!
  • strictness analysis
  • graafinsievennys? G-kone? STG?
• ensiluokkaisten funktioiden käsittely

Tyyppitarkastus (Hindley-Milner)

ks esimerkki

Perusidea:

• arvataan kullekin muuttujan- ja funktionnimille tyypiksi jokin tyyppimuuttuja
• käydään koodi läpi ja kirjataan ylös tyyppien välisiä yhtälöitä
  • esim jos f :: a, x :: Int ja f x :: b, niin täytyy olla a ~ Int -> b
• ratkaistaan syntynyt yhtälöryhmä nimille arvattujen tyyppimuuttujien suhteen
  • jos yhtälöryhmä on inkonsistentti, tehdään tyyppivirheistä diagnoosit

Etuja:

• ei vaadi muuttujien ja funktioiden tyyppien esittelemistä lähdekoodissa
• jos koodi menee Hindley-Milneristä läpi, siinä ei ole tyyppivirheitä, ja takapää voi jättää tyyppitarkastukset generoimatta
• geneerisyys tulee puoli-ilmaiseksi

Tyyppivirhetyypit Hindley-Milnerissä

• type mismatch: yhtälö T ~ U, missä T ja U ovat eri konkreetteja tyyppejä (esim Int ja String)
• occurs check failure: yhtälö a ~ ... a ..., ts. tyyppimuuttujan ratkaisu sisältää kyseisen tyyppimuuttujan itsensä