Tällä luennolla

• terminologista selvennystä
• evaluaatiojärjestykset
• sivuvaikutukset ja sivuvaikutuksettomuus
• abstraktio

Terminologiasta

• termien sievennys (evaluation) ja reduktio (reduction) käyttö ei ole täysin vakiintunut
  • kurssilla syntyi vähän ad hoc -terminologia: reduktio = uudelleenkirjoitussäännön suorittaminen termille kokonaisuudessaan, sievennys = uudelleenkirjoitussäännön suorittaminen jollekin termin osalle
• nyt otetaan käyttöön vähemmän monitulkintainen terminologia
  • suorittaminen termillä kokonaisuudessaan = säännön suorittaminen
  • suorittaminen termin mille tahansa osalle = sievennys säännöllä

Erottelu: suorittaminen - sievennys

• lausekkeella voi olla normaalimuoto β-reduktion suorittamisen suhteen, vaikka sen jollain osalausekkeella ei olisikaan:
  • (λ a. a ((λ b. b b) (λ c. c c)))
• tätä erottelua ei kohta enää tarvita niin paljon, kun evaluaatiojärjestykset on käyty…
• käytännön kannalta on olemassa kolmenlaisia lausekkeita:
  • niitä, joilla on normaalimuoto, johon päätyy aina äärellisellä määrällä sievennysaskelia: (λ a. a a) (λ a. a)
  • niitä, joilla on normaalimuoto, johon päätyy sieventämällä oikeasta kohtaa: (λ a b. b) ((λ a. a a) (λ a. a a))
  • niitä, joilla ei ole normaalimuotoa: (λ a. (λ a. a a) (λ a. a a))

Evaluaatiojärjestykset

• Evaluaatiojärjestysten merkitys
• Normaalijärjestys ja sovellusjärjestys
• Normaalijärjestyksen ja sovellusjärjestyksen vertailua
• Äärettömät tietorakenteet
• Evaluaatiojärjestykset: yhteenveto

Evaluaatiojärjestysten merkitys

• epädeterministisen sievennyssäännön voi muuttaa deterministiseksi määrittämällä, missä järjestyksessä sievennetään
• enimmäkseen ei ole väliä, mistä kohtaa lausekkeen sieventää
  • tietty applikaatio (sovellus) edustaa lopputulostaan
  • koska suoritussäännön tulos ei riipu siitä, missä ympäristössä se suoritetaan, tulos on aina sama
  • joten lausekkeen voi sieventää missä vaiheessa vain, se ei vaikuta lopputulokseen
• mitä väliä siis on sillä, missä järjestyksessä sievennetään?
• kuten edellä nähtiin, joidenkin lauseiden normaalimuotoa ei voi saavuttaa sieventämällä tietyssä järjestyksessä.

Normaalijärjestys ja sovellusjärjestys

• käytännössä kaksi selkeää vaihtoehtoa:
  1. sievennetään aina sisin mahdollinen lauseke (sovellusjärjestys)
  2. sievennetään aina uloin mahdollinen lauseke (normaalijärjestys)
• kaikkein ulointa lauseketta ei pysty aina sieventämään
  • ((λ a b. a b) c d) = (((λ a (λ b. a b)) c) d)
  • uloimman lausekkeen vasen haara ei ole lambdalauseke, siispä sitä pitää sieventää ensin, kunnes saadaan lambdalauseke
  • normaalijärjestyksen sääntö: vasemmanpuoleisin uloin ensin

Normaalijärjestyksen ja sovellusjärjestyksen vertailua

• sovellusjärjestys
  • toteutettavissa suhteellisen yksinkertaisella pinokoneella
  • nopea (?)
  • jumiutuu aina, kun mahdollista
• normaalijärjestys
  • toteuttaminen vaatii sisäisen esitystavan lausekkeille, jotka odottavat sievennystä
  • lausekkeista tulee käsittämättömän kokoisia varsin nopeasti
    • hidas (?)
    • mutta optimointi: laiska evaluaatio
  • tuottaa tuloksen (eli normaalimuodon) aina, kun mahdollista

Äärettömät tietorakenteet

• normaalijärjestys avaa oven äärettömiin tietorakenteisiin (tietorakenteisiin, joissa on äärettömän paljon tietoa)
  • jos ääretöntä lauseketta käsitellään tavalla, joka käyttää lausekkeen esittämästä tietorakenteesta vain äärellistä osaa lopputuloksen laskemiseen, tulos saadaan
• äärettömiä tietorakenteita ei tietenkään voi luetella, ne määritetään säännöillä
  • esim. ääretön lista luonnollisista luvuista kasvavassa järjestyksessä: ((λ i. i i) (λ i n. (cons n (i i (+ n 1)))) 0)
  • cons, + ja 1 määritellään myöhemmin kurssilla

Äärettömät tietorakenteet (jatkoa)

• oikeastaan funktiolla ja tietorakenteella ei ole eroa edes semanttisessa mielessä
  • argumentin antaminen funktiolle ja tietorakenteen osan valitseminen on sama asia
• useimmat potentiaalisesti äärettömät prosessit (optimointi, päättely, …) voi mallintaa äärettöminä tietorakenteina
  • eri vaiheet listan eri kohtia, eri päättelysuunnat puun eri haaroja, jne…
  • tyypillisesti yhdistelmä, jossa tehdään monta muunnosta äärettömästä tietorakenteesta toiseksi äärettömäksi tietorakenteeksi
  • lopuksi valitaan tietorakenteesta halutulla perusteella jokin osa

Evaluaatiojärjestykset: yhteenveto

• normaalijärjestyksessä toteutusongelmia, mutta teoriassa parempi
  • esim. (λ a. a a) (λ f p. if p (f f (not p)) p)
• toteutus vapaa valitsemaan evaluaatiojärjestyksen pystyessään todistamaan, että tulos sievenee joka tapauksessa
• nykyaikaiset normaalijärjestyksessä sieventävät ohjelmointikielet (esim. Haskell) käyttävät laiskaa evaluaatiota ja vaikka mitä temppuja
• normaalijärjestyksessä sieventäminen mahdollistaa äärettömät tietorakenteet

Sivuvaikutukset ja sivuvaikutuksettomuus

• Laskennan mallien kaksi tyyliä
• Mitä ovat sivuvaikutukset?
• Miten pystyy laskemaan sivuvaikutuksettomasti?
• Entäs yhteydet ulkomaailmaan?
• Sivuvaikutuksettomuuden hyötyjä
• Sivuvaikutukset: yhteenveto

Laskennan mallien kaksi tyyliä

• Aika usein laskenta mielletään joksikin, jossa jokin (toimija) tekee jotain jollekin (aineistolle) jonkin ohjeen mukaan
• λ-kalkyylissa kuitenkin lausekkeet vain korvautuvat toisilla (suoritussääntöjen mukaan), indeterministisesti eli haluamassaan järjestyksessä
• pohjimmiltaan nämä kaksi eivät kuitenkaan ole eri asia: Church-Turing-isomorfismi
• tarkastellaan siis näiden kahden laskennanhahmotustavan suhdetta.

Mitä ovat sivuvaikutukset?

• sivuvaikutuksellisessa mallissa laskennalla on jokin ympäristö, jolla on jokin tila
  • esim. Turingin koneessa nauha, jonka tila koostuu nauhalla olevista symboleista sekä siitä, mihin kohtaa nauha on kelattu
• sivuvaikutuksiksi sanotaan sitä, kun:
  • laskennan tulos riippuu ympäristön tilasta
  • tai laskenta muuttaa ympäristön tilaa
  • tai molempia, siten että laskenta kommunikoi itsensä kanssa ympäristön kautta
• sivuvaikutusten puute on syy siihen, miksi λ-kalkyylissa evaluaatiojärjestyksellä ei ole kovin paljon väliä.

Miten pystyy laskemaan sivuvaikutuksettomasti?

• sen sijaan, että muutellaan maailmassa olevia tietoja, tuotetaan uusia tietoja
  • esim. + 33 51 => 86 ei muuta kumpaakaan lukua 86:ksi, vaan tuottaa uuden luvun 86
• isommissa tietorakenteissa sama juttu: listan (taulukon) muuntelun sijaan tuotetaan uusi lista
  • esim. alkioiden tuplaaminen: (map (λ a. + a a) (cons 3 (cons 5 null))) => (cons 6 (cons 10 null))
  • ei muuta vanhaa listaa eikä sen sisältöä, vaan tuottaa uuden listan uudella sisällöllä
  • funktiot map, +, cons ja null sekä numerot määritellään kurssilla myöhemmin

Entäs yhteydet ulkomaailmaan?

• helppoa: muunnetaan koko ulkomaailma tietorakenteeksi, josta ohjelmat tuottavat uusia ulkomaailmoita
  • esim. tulosta jipii on funktio, joka ottaa argumentikseen maailman ja tuottaa siitä uuden maailman, joka on muuten samanlainen paitsi että näytöllä on teksti jipii.
  • kaikista näistä virtuaalimaailmoista aktuaalinen on se, joka on ohjelman tulos
• Unix-tyylinen vuorovaikutus, jossa ohjelmalle tulee tekstiä ja ohjelma tuottaa tekstiä, voidaan myös mallintaa funktiona, joka ottaa syötteeksi merkkilistan ja palauttaa merkkilistan
• miten tahansa syöte ja tuloste määritelläänkin, pystyy aina muodostamaan funktiot, joilla saa sen näyttämään ymmärrettävältä

Sivuvaikutuksettomuuden hyötyjä

• ohjelman ominaisuuksien todistettavuus
  • vapaa evaluaatiojärjestys
  • idempotenssi: lausekkeen sieventäminen kahteen kertaan ei muuta lopputulosta
• jokainen lauseke edustaa lopputulostaan, joten esim. ääretöntä listaa ei tarvitse kirjoittaa auki vaan voi kirjoittaa lausekkeen, joka tuottaa äärettömän listan, ja tulos on sama
• laiska evaluaatio tekee tosi vaikeaksi hahmottaa, missä vaiheessa sivuvaikutukset tapahtuvat, jos ne ovat sallittuja
  • mutta laiska evaluaatio on välttämätön normaalijärjestyksessä sieventämisen tehokkaaseen toteuttamiseen

Sivuvaikutukset: yhteenveto

• laskennan voi mallintaa kahdella tyylillä (tai asenteella)
• sivuvaikutuksissa vaikutettava on ympäristö
• sivuvaikutuksettomassa laskennassa vaikutettava asia annetaan eksplisiittisesti syötteeksi ja siitä tuotetaan jotain uutta
• mille tahansa sivuvaikutukselle on olemassa vastaava funktio, jolle annetaan ympäristö (jollain tavoin tietorakenteeksi koodattuna) ja joka tuottaa uuden ympäristön
  • ympäristö-tietorakenne voi tietysti olla läpinäkymätön
• normaalijärjestyksessä sieventäminen lähes edellyttää sivuvaikutusten kieltämistä