Tällä luennolla

• Pieni kertaus rekursiosta
• Abstraktio
• Muut funktionaaliset tietorakenteet
• Lisää esimerkkejä abstraktiosta

Pieni kertaus rekursiosta

• Tapa käsitellä mielivaltaisen suuria tietorakenteita
  • esim. luku voi olla kuinka suuri vain, lista kuinka pitkä vain, jne
• perustuu siihen, että tietorakenteen operaatio palautetaan sen osan samaan operaatioon
  • esim. luvun n tulo luvun m kanssa palautuu luvun n - 1 tuloon luvun m kanssa
  • listan summa palautuu listan loppuosan summaan
• rekursion päättyminen perustuu siihen, että tietyissä tapauksissa tulos ei määrity rekursiivisesti
  • nollan tapauksessa kahden luvun tulo on aina 0
  • tyhjän listan tapauksessa summa on aina 0

Abstraktio

• Mitä on konkretia?
• Abstraktio λ-kalkyylissa
• Esimerkki abstraktiosta: pinta-alan laskeminen
• Esimerkki abstraktiosta: listan muuntaminen
• Abstraktion huippu

Mitä on konkretia?

• lauseke, joka on täysin määritelty, on konkreettinen
  • esimerkiksi (plus (times 3 7) 3) => (plus 21 3) => 24
• konkreettisen lauseen arvon voi laskea
• abstraktiossa (eli λ-alkuisessa lauseessa) abstraktion runko ei ole täysin määritelty
  • esimerkiksi (λ c. plus (times c 7) c)
• abstraktio on ikään kuin lauseke, joka odottaa puuttuvaa osaa määrittelystään

Abstraktio λ-kalkyylissa

• λ-kalkyylissa lausekkeen puuttuva osa annetaan argumenttina
  • ((λ c. plus (times c 7) c) 3) =>
    (plus (times 3 7) 3) => 24
  • ((λ c. plus (times c 7) c) 1) =>
    (plus (times 1 7) 1) => 8
• abstrahoida voi monella tavoin
  • lähtökohta: (plus (times 3 7) 3)
  • (λ c. plus (times c 7) c)
  • (λ c. plus (times c 7) 3)
• operaation abstraktio
  • (λ c. plus (c 3 7) 3)
    • ((λ c. plus (c 3 7) 3) times) => 24
    • ((λ c. plus (c 3 7) 3) plus) => 13

Abstraktio λ-kalkyylissa (jatkoa)

• abstrahoida voi monta kertaa
  • (plus (times 3 7) 3)
  • (λ c. plus (times c 7) c)
  • (λ d. λ c. plus (times c d) c)
  • tai vaikka: (λ a b. a (b 3 7) 3)
• kaksi näkökulmaa siihen, mitä abstraktio on:
  • abstraktion sisäisestä näkökulmasta laskutoimitus, josta puuttuu konkreettisia osasia
  • abstraktion käyttäjän näkökulmasta määritelmä, joka kertoo, mitä sen argumenteille tehdään
  • eli argumentit konkretisoivat abstraktion, ja abstraktio konkretisoi, mitä argumenteilla tehdään (ovatpa ne kauniit yhdessä!)

Abstraktion merkitys

• λ-kalkyyli on abstraktin ja konkreettisen leikkiä
• kun kahdella laskennalla on mitä tahansa yhteistä, voidaan muodostaa λ-lauseke, jossa yhteinen toiminta on konkreettista ja eroava toiminta on abstrahoitu
• tällöin kyseessä on parametrinen laskenta, joka spesialisoidaan antamalla argumentiksi konkreettinen toimintaohje
• λ-kalkyylissa ei tarvita monta reduktiosääntöä, koska β-reduktio tekee λ-lausekkeesta 1. luokan reduktiosäännön

Esimerkki abstraktiosta: pinta-alan laskeminen

• Haluamme laskea monta ympyrän pinta-alaa:
  • (times (times 3 3) pi)
  • (times (times 8 8) pi)
  • (times (times 10 10) pi)
• aika helppo nähdä, mikä näille on yhteistä…
  • circarea =_def (λ n. (times (times n n) pi))
  • esim. (times (times 3 3) pi) = circarea 3
• voidaanko abstraktiota jatkaa?

Esimerkki abstraktiosta: pinta-alan laskeminen (jatkoa)

• mitä yhteistä on näillä:
  • circarea =_def (λ n. (times (times n n) pi))
  • sqarea =_def (λ n. (times (times n n) 1))
  • voidaan abstrahoida:
    • area-by-length =_def (λ k n. (times (times n n) k))
    • circarea = area-by-length pi
    • sqarea = area-by-length 1
• milloin olisi järkeä määritellä xxx =_def (λ t k n. (t (t n n) k))?
  • esimerkiksi, jos lukujen esitystapaa ei ole määritelty eli kertolasku ei ole vielä konkreettinen…

Esimerkki abstraktiosta: listan muuntaminen

• Tapaukset: listan elementtien kasvattaminen
  • add-three = Y (λ i l. l nil (λ e r. cell (plus e 3) (i r)))
  • add-six = Y (λ i l. l nil (λ e r. cell (plus e 6) (i r)))
• Helppo nähdä, mitä voisi abstrahoida
  • add-any = λ n. Y (λ i l. l nil (λ e r. cell (plus e n) (i r)))
  • add-three = add-any 3
  • add-six = add-any 6

Esimerkki abstraktiosta: listan muuntaminen (jatkoa)

• Vieläkin yleispätevämpi abstraktio olisi saatavissa
  • map = λ f. Y (λ i l. l nil (λ e r. cell (f e) (i r)))
  • tämä siis tekee minkä tahansa muunnoksen kaikille listan elementeille
  • doubles = map (λ e. plus e e)
  • add-any = λ n. map (plus n)
• On olemassa vieläkin yleispätevämpi abstraktio
  • fold = λ f n. Y (λ i l. l n (λ e r. f e (i r)))
  • map = λ f. fold (λ e a. cell (f e) a) nil
  • kaikki listaoperaatiot voi määrittää fold:lla!

Abstraktion huippu

• Mutta miksi pysähtyä tähän?
• Onko olemassa funktio, jolla voi tehdä mille tietotyypille tahansa mitä tahansa?
  • toki, se on (λ f a. f a)
  • tässä a kuvaa tietotyyppiä ja f tehtävää operaatiota
  • toimii, koska minkä tahansa operaation voi määrittää λ-lausekkeena f
• äärimmäisen yleispätevä ohjelma on hyödytön
  • ohjelmat määritetään tarkentuvana hierarkiana

Funktionaaliset tietorakenteet

• Yleistä funktionaalisista tietorakenteista
• Puut
• Esimerkkejä puiden käsittelystä
• Rekursiiviset tietorakenteet
• Esimerkki abstraktiosta: puu ja lista

Yleistä funktionaalisista tietorakenteista

• sivuvaikutuksettomuus
  • kun tietorakenne kerran on tuotettu, se (tai mikään sen osa) ei muutu
  • muutokset tehdään tuottamalla uusia tietorakenteita
  • uusi tehdään vanhan perusteella ja usein jakaa osia vanhan kanssa
• rakenteisuus
  • induktiiviset tietotyypit ovat syviä
  • tietotyyppi koostuu äärellisestä määrästä pienempiä osasia
  • myös lista ja luku ovat tällaisia

Puut

• Tarkastellaan yksinkertaisimpana tapauksena binääripuita
  • puu on joko tyhjä, tai se sisältää mielivaltaisen elementin ja kaksi haaraa
  • oikeastaan lista on unaaripuu
  • muodollisesti: tree ::= emptytree | branch element tree tree
• puun järjestelystä voidaan tietysti sopia jotain
  • esimerkiksi hakupuu on järjestetty jollain relaatiolla <
  • tällöin vasemmassa haarassa kaikki elementit ovat tätä pienempiä ja oikeassa haarassa suurempia

Esimerkkejä puiden käsittelystä

• puun koko
  • halutaan noudattavan seuraavia yhtälöitä:
    • tree-size emptytree = 0
    • tree-size (branch e l r) = succ (plus (tree-size l) (tree-size r))
  • määrittely: tree-size =_def Y (λ i t.
    t 0 (λ e l r. succ (plus (i l) (i r))))
• mielivaltaisen elementin etsiminen
  • halutaan noudattavan seuraavia yhtälöitä:
    • tree-find e emptytree = false
    • tree-find e (branch e l r) = true
    • tree-find e (branch d l r) = tree-find e (if (< e d) l r)
  • määrittely: tree-find =_def Y (λ i e t.
    t false (λ d l r. compare e d (i e l) true (i e r)))

Rekursiiviset tietorakenteet

• myös tietorakenteet voivat olla rekursiivisia, ts. sisältää itsensä osanaan.
  • varoitus: induktiivisia tietorakenteita kutsutaan joskus rekursiivisiksi
• esimerkiksi ääretön lista ykkösiä:
  • Toteuttaa yhtälön: ones = cell 1 ones
  • määrittely: ones =_def Y (λ i. cell 1 i)
• tai ääretön lista listaa itseään (ei kovin hyödyllistä?):
  • selfs =_def Y (λ i. cell i i)

Rekursiiviset tietorakenteet (jatkoa)

• Lättänä puu eli kaksisuuntainen lista
  • jokaisesta haarasta pystyy palaamaan takaisin vastakkaisella haaralla
  • esim. a = branch 1 emptytree b, b = branch 2 a c, c = branch 3 b emptytree
• voidaan muodostaa listasta kaksoisrekursiivisella määrittelyllä
  • Määritelty noudattamaan seuraavia yhtälöitä:
    • dlink prev nil = emptytree
    • dlink prev (cell e r) = me, jossa me = branch e prev (dlink me r)
  • määrittely: dlink =_def Y (λ i p l.
    l emptytree (λ e r. Y (λ m. branch e p (i m r))))

Esimerkki abstraktiosta: puu ja lista

• Äsken tutkittiin abstraktiota, jossa tietotyyppi pysyy ja sille tehtävä operaatio vaihtuu
• Entä toisin päin, voisiko esimerkiksi määrittää, että lasketaan summa, mutta abstrahoida, mistä tietotyypistä?
• toki, määrittämällä tietotyypeille operaation, jolla summan voi aina määritellä (gather)
• gatherille annetaan neljä syötettä: mitä tehdään tyhjälle muodostimelle; millä yhdistetään keräelmä ja elementti; ja millä yhdistetään kaksi keräelmää

Esimerkki abstraktiosta: puu ja lista (jatkoa)

• ilman abstraktiota
  • sum-list = Y (λ i l. l 0 (λ e r. plus e (i r)))
  • sum-tree = Y (λ i t. t 0 (λ e l r. plus e (plus (i l) (i r))))
• abstraktion kanssa
  • gensum = λ g. g 0 plus plus
  • gather-list = λ z c a. Y (λ i l. l z (λ e r. c e (i r)))
  • gather-tree = λ z c a. Y (λ i t. t z (λ e l r. c e (a (i l) (i r))))
  • sum-list = gensum gather-list
  • sum-tree = gensum gather-tree

Esimerkki abstraktiosta: puu ja lista (jatkoa)

• gather:a voi käyttää muuhunkin:
  • genflatten =_def λ g. g nil cell append
  • flatten-list = genflatten gather-list
    • ei hyödyllinen, listat valmiiksi lättäniä
  • flatten-tree = genflatten gather-tree
• ja vieläkin muuhun: gensize =_def λ g. g 0 (λ e. succ) plus
• yleinen ajatus: tietorakenteen osista haetaan tietoa, joka yhdistellään tietyin funktioin

Kikkoja XXX

• CPS:n käyttöä kuvaamisen rikastuttamiseen
  • Useamman arvon palauttaminen
    • annetaan argumentiksi funktio, jolle tulos palautetaan
  • Erilaiset palautustavat
    • annetaan argumentiksi useampia, vaihtoehtoisia jatkeita
  • Rajoitettu rekursio
    • käytetään Y:n sijaan jotain muuta
• Jatkolistat