(toiminnot)

hwechtla-tl: Evaluointijärjestykset

Kierre.png

Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset


Funktionaalisissa kielissä ja järjestelmissä: säännöt siitä, missä järjestyksessä kaavan osia suoritetaan.

http://sange.fi/~atehwa/lambda-kurssi/luento3.html

Tarkastellaan esimerkiksi seuraavanlaisten funktiomääritysten redusoimista kaavassa:

map f []     = []
map f (x:xs) = f x : map f xs

hd []     = error "empty"
hd (x:xs) = x

hd (map (\x -> 3 * x) [1..10])

Jos evaluointi on laiskaa, yritetään ensin laajentaa hd (toivossa ettei map:a tarvitsisi laajentaa ollenkaan). Kuitenkin hd:n pitää lukea argumenttinsa rakennetta toimiakseen, joten map joudutaan laajentamaan. map:kin joutuu laajentamaan argumenttiaan [1..10] yhden kierroksen pystyäkseen tekemään hommansa. Yksi laajennus kuitenkin riittää, sitten hd jo pystyy tekemään hommansa:

hd (map (\x -> 3 * x) (1:[2..10]))   ==>
hd ((\x -> 3 * x) 1 : map (\x -> 3 * x) [2..10])  ==>
(\x -> 3 * x) 1  ==>
4

Kiivaassa evaluaatiossa kuitenkin funktion argumentit laajennetaan ennen funktion itsensä laajentamista. Se merkitsee, että koko lista [1..10] laajennetaan ensin muotoon 1:(2:(3:...(10:[])...)), sitten map laajennetaan niin monta kertaa kuin mahdollista, jolloin tuloksena on lista 4:(5:(6:...)). Vasta sitten siitä otetaan ensimmäinen kohta hd:lla.

Laiska evaluaatio tarjoaa todella voimakkaita abstraktiovälineitä. Sen seurauksena tietorakenteista tuleekin yhtäkkiä funktioiden keinoja lähettää viestejä toisilleen, kontrollirakenteet tulevat erottumattomiksi muista kaavoista, ja potentiaalisesti loputtomat tietorakenteet tulevat mahdollisiksi. Huonoja puolia on suuri muistinkulutus (monimutkaisia kaavoja saatetaan pitää pitkäänkin redusoimatta ihan vain siinä toivossa, ettei niitä koskaan tarvitsisi), hankaluus hallita funktioiden sivuvaikutuksia ja se, että evaluaatiota odottaville laskutoimituksille täytyy keksiä jokin representaatio.

Todennäköisesti viimeinen näistä on suurin syy siihen, miksi käytännölliset kielet ovat paljolti suosineet kiivasta evaluaatiota. Erityisesti C:n kaltaisissa kielissä, joissa ajonaikaisesti muodostettavia funktioita ei ole ollenkaan, tämä sallii jättää kaikenlaiset representaatiot komputaatiolle pois ja käsitellä yksinkertaisesti vain kutsupinoa ja tavallisia arvoja kuten osoittimia ja numeroita.

kategoria: ohjelmointi


kommentoi (viimeksi muutettu 15.02.2011 21:28)