Demo 6 - kommentit

Kuudennen ja tähän asti vähiten suositun (hiihtolomaviikko :) ) demokerran tehtävät löytyvät osoitteesta http://users.jyu.fi/~antkaij/opetus/okp/2009/demot/6.html . Tällä kertaa tein sekä ensimmäisen ja toisen tehtävän. Toisen tehtävän c-kohtaa "Funktio, joka luo parametrina annetun pituisen Fibonacci-lukujen listan (NumList)." lähdin ratkaisemaan turhan geneerisesti. Ajatuksena oli, että fibonaccin lukujen listaa ajateltaisiin generaattorina ja n-mittainen lista koostettaisiin toisen aliohjelman avulla, jolle annettaisiin syötteenä n:n lisäksi generaattorialiohjelma. Pythonilla ratkaisu menisi seuraavasti:

def fibo():
    n, m = 0, 1
   
    while True:
        yield n
        n, m = m, n + m

def list_factory(n, gen):
    return [gen.next() for i in range(n)]

assert list_factory(10, fibo()) == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Tuo varmaan kääntyy myös lambda-lausekkeiksi pienellä vaivalla. Yllä oleva ratkaisu toimii tässä tapauksessa. Kuitenkin yleisemmässä käytössä generaattori varmaan muuttuisi omaksi luokakseen, jonka voisi nollata. Toisaalta fibo generaattoria voisi ajatella myös aliohjelmana, joka laskee n:n arvon tilastaan riippumatta. Isoilla n:n arvoilla aliohjelmapohjaisen ratkaisun suorituskyky saattaisi tosin kärsiä.

Luento 14 - Parametripolymorfismi

Parametripolymorfismi on eräs Cardellin ja Wegnerin määritelmän kategorioista. Se on määritelty seuraavasti: "Parametric Polymorphism: a polymorphic function has an implicit or explicit type parameter which determines the type of the argument for each application of that function." Oleellista määritelmässä on tyyppiparametrin käsite. Sen avulla voidaan siis määritellä aliohjelman tyyppi. Huomaa, että dynaamisesti tyypitetyissä kielissä tämän voidaan ajatella tapahtuvan implisiittisesti. Staattisesti tyypitetyissä kielissä tyyppiparametri tulee määritellä eksplisiittisesti.

Parametrinen polymorfismi mahdollistaa geneerisemmän koodin kirjoittamisen. Tämä onkin eräs tapa, jolla staattisesti tyypitetyt kielet matkivat dynaamisesti tyypitettyjä. Geneerisen koodin ansiosta voidaan sitä voidaan ajatella abstraktimmalla tasolla.

Tyypitetyn lambda-kielen tapauksessa parametrista polymorfismia voidaan toteuttaa käyttäen ns. Systeemi F -laajennosta, joka luo tyypeille sopivan abstraktion. Käsittääkseni tässä on oleellisesti kyse siitä, että Systeemi F mahdollistaa tyyppien käsittelyn omassa avaruudessaan ja se toteuttaa rajapinnan, jonka avulla se liittyy vanhaan määritelmään.

Systeemi F ei toimi tyyppitoimituksilla (tyyppitasolla toimiva funktio, esim. lista), joten sitä on laajennettu edelleen. Tätä laajennosta kutsutaan nimellä Systeemi F (pikku omega). Tyyppitoimituksia varten tyypeille tulee määritellä tyypit eli luonteet (kinds). Tämä johtunee siitä, että Systeemi F:n tyypit ja tyyppitoimitukset voidaan samaistaa olevan samassa tyyppiavaruudessa.

Luennolla esiteltiin myös varsin mielenkiintoinen foldr (fold right) operaatio, joka tunnetaan myös reduce nimellä. Pythonissa operaatiota voidaan käyttää esim. seuraavasti: reduce(lambda x, y: x*y, [1, 2, 3, 4]). Tässä tapauksessa listan sisältämät luvut kerrotaan keskenään. Tarkemman kuvauksen löydät täältä.

Luento 13 - Subsumptioperiaate

Mitä subsumptio tarkoittaa? Merriam-Websterin mukaan seuraavaa: "to include or place within something larger or more comprehensive : encompass as a subordinate or component element subsumed under the term “color”". Eli vapaasti tulkittuna kysymys on sisältymissuhteesta. Subsumption avulla voidaan oleellisesti määritellä hierarkioita.

Tästä havainnosta, sisältymisestä, on johdettu subsumptioperiaate, joka vapaasti ilmaistuna sanoo, että tyyppiä voidaan käyttää ylityyppinsä sijalla. Eli esimerkiksi väriin voidaan sijoittaa sen konkreettinen ilmentymä vihreä. Toisaalta pätee myös, että voidaan ottaa alityypin alityyppi, esimerkiksi vihreän sävy jade, ja sijoittaa se ylityyppiinsä väriin. Eli sääntö pätee siis yleisellä tasolla.

Subsumptio pitänee nähdä polymorfismin, eli suomeksi jotakuinkin "monimuotoisuuden", yläkäsitteenä. Tähän liittyen luennolla esiteltiin Cardellin ja Wegnerin esittämä polymorfismin kategorisointi. On huomattava, että polymorfismi ei ole ainoastaan oliokielten ominaisuus vaikka käsite tuleekin oliokielistä puhuttaessa esille usein.

Tämä ilmeni esimerkissä, jossa tarkasteltiin lambda-kieltä ja tietueita. Jotta tietueita voidaan käsitellä lambda-lausekkeiden avulla, kuten intuitio ehkä opastaisi, tulee kielen määrittelyyn tehdä pieniä muutoksia. Osoittautui, että tietuiden käsittelyä voidaan helpottaa nimenomaan yllä esitetyn subsumptiolauseen avulla. Tässä tapauksessa subsumptiota sovelletaan tietueen tasolla. Toisin sanoen tietueesta voidaan karsia lambda-lausekkeen kannalta turha osa pois subsumption nojalla.

Oliokielten ja perinnän tapauksessa subsumptiolla osoittautui olevan kaksi varsin mielenkiintoista ominaisuutta. Olkoon luokat A ja B. B on A:n perillinen. Lisäksi B ylikirjoittaa A:n toteuttaman metodin foo. Voi olla mielekästä, että B saa muuttaa metodin palautusarvon tai parametrien tyyppejä. Kysymys kuuluukin, kuinka tämän tulisi tapahtua.

Subsumptioperiaatteen avulla havaitaan, että palautusarvon tulee olla vähintään alkuperäinen tyyppi tai sen alityyppi. Eli kyseessä on kovarianssi.

Parametrien tapauksessa perivä luokka ei voi rajoittaa vanhempansa määrittelemää tyyppiä, koska tämä sotisi subsumptioperiaatetta vastaan. Tässä tapauksessa tuleekin päteä, että perivän luokan ylikirjoittamien metodien tyyppien tulee olla vähintään alkuperäisiä tyyppejä ja niiden ylityyppejä. Tätä kutsutaan myös kontravarianssiksi.

Eiffelissä parametrien tyyppi on kenties hieman yllättäen toteutettu kovarianssia noudattaen (tekivät ehkä saman intuitiivisen virheen kuin minä alun perin :) ). Tästä seuraa, että tyyppejä joudutaan tarkastelemaan dynaamisesti ohjelman ajonaikana, koska ei voida taata, että parametrin tyyppi on korkeintaan metodin alkuperäisen määritelmän tyyppi. Eiffelin DbC (Design by Contract) on määritelty myös kovarianssin mukaisesti, mikä sinänsä tuntuu loogiselta.

Luennolla mainittiin myös Top ja Bot(tom) tyypeistä, jotka edustavat kaikkien tyyppien ylintä ja alinta tyyppiä. Usein Topin voidaan ajatella olevan ohjelmointikielen ns. Object-luokka. Bot edustaa pohjaa ja sitä voidaan ajatella myös noreturn tyyppinä, joka lopulta terminoi ohjelman suorituksen.

Demo 5 - kommentit

Viidennen demokerran tehtävät löytyvät osoitteesta http://users.jyu.fi/~antkaij/opetus/okp/2009/demot/d5.pdf . Demotehtävät olivat jälleen kerran lambda painotteisia. Teinkin ainoastaan bonustehtävien ensimmäisen osan, jossa tuli suunnitella yleistajuinen esitys aliohjelmien toteuttamiselle tyypitettyyn while-kieleen. Tehtävään pääsi mukavasti kiinni pohtimalla hieman, miten asia on hoidettu esimerkiksi C:ssä ja Javassa. Myös näkyvyysalueita (sulkeumat) sai miettiä hieman.

Luento 12 - Rekursiiviset tyypit

Tällä kertaa käsiteltiin rekursiivisia tyyppejä, jotka lienevät useille tuttuja esimerkiksi C:n linkitettyjen listojen toteutuksesta. Ajatuksena on, että tietue voi viitata itseensä. Täten voidaan luoda mitä mielenkiintoisimpia rakenteita. Toki ilman rekursiota pärjää ja on pärjättykin, mutta mikäli ohjelmointikieli sallii sen käytön, sitä voi kannattaa käyttää.

Luennon aluksi käsiteltiin myös tietuieiden samuutta. Helpoimmalla pääsee vertailemalla tietuiden nimiä (ns. nimisamuus). Toisaalta tässä tapauksessa kielen tasolla tulee huolehtia siitä, että nimet ovat uniikkeja tietuieita käytettäessä. Toinen tapa käsitellä samuutta on jättää nimen käsite omaan arvoonsa ja vertailla puhtaasti tietueiden sisältöä.

Tässä tapauksessa voidaan kiinnittää lisäksi huomiota tietueen sisäiseen järjestykseen tai jättää se huomiotta. Luennolla esitettiin edellä mainittuun tapaan bisimulaatioon pohjautuva ratkaisu, jossa vertailtavia tietueita askelletaan samanaikaisesti ja tutkitaan onko kunkin vertailtava tieto sama sen nimen ja tiedon suhteen. Tätä ehtoa voisi varmaan löyhentää keskittymällä vain tietotyyppiin ja jättämällä nimen huomiotta. Tosin mikäli nimi jätetään huomiotta voivat semanttisesti hyvinkin erilaiset tietueet tulla tulkituiksi samoiksi! Käsittääkseni jälkimmäisessä järjestyksen huomiotta jättävässä tapauksessa bisimulaatio voidaan toteuttaa käyttämällä toista tietuetta referenssinä ja toista tutkittavana. Huomaa, että kummankin tietueen tulee vuorollaan toimia referenssinä, jotta voidaan taata ettei toisessa tietueessa satu olemaan ylimääräisiä alkioita! Seuraavana algoritmi pseudokoodina:

struct1, struct2 = Struct(), Struct()

def structs_are_equal(struct1, struct2):
  for ref_node in struct1:
      found_node = False

      for node in struct2:
          if str(ref_node) == str(node)
             and type(ref_node) == type(node):
              found_node = True
              break

      if not found_node:
          return False

  return True # tietueet ovat samoja

Sinänsä algoritmissa ei ole mitään ihmeellistä (ellen sattunut tekemään jotain radikaalia virhettä). Luennolla esitettiin myös rekursiivisten tyyppien toteutusta lambda-kielessä. Koko touhun ytimessä on kiintopisteoperaattori, johon määritelty tyyppi voi viitata mahdollistaen rekursion. Toinen varsin mielenkiintoinen sivuttu asia oli laskostaminen (isorekursio), jossa kiintopiste irrotetaan erikseen kokonaisuudesta ja rekursio mahdollistuu erityisten laskostamisaliohjelmien (fold, unfold) avulla, joilla tietue käsittääkseni voidaan kääriä auki (unfold, rekursio pois) ja kääriä kiinni (fold, rekursio takaisin).

Myös tietueilla operoimista käytiin läpi. Tässä yhteydessä huomioni herätti erityisesti jo Pythonista tuttujen sum ja lambda aliohjelmien toteutus. "reduce" lienee menee hieman samaan tapaan. Ajatuksena näissä pienissä apureissa on, että annettua tietuetta (tässä tapauksessa rajoituttiin NumListiin (numeroiden lista)) voidaan manipuloida annetun aliohjelman avulla. Esimerkiksi map suorittaa annetun aliohjelman kaikille tietueen alkioille ja palauttaa muunnetun tietueen.

Myös virtojen (stream) käsite kiinnitti huomioni. Virralta voidaan kysyä arvoja, kuten generaattorilta ikään. Virta voi palauttaa yksinkertaisimmillaan jonkin luvun. Se voi myös säilyttää tilansa mahdollistaen matemaattisten funktioiden kuvaamisen virtana. Myös satunnaislukugeneraattorinkin luulisi syntyvän helposti tätä kautta.

Luento 11 - Tyyppijärjestelmän laajennoksia

Luento rakensi aiemmin esitetyn teorian luomalle pohjalle. Aluksi esitettiin mielenkiintoinen huomio siitä, kuinka C:stä tuttu void tyyppi on määritelty kielen spesifikaatiossa. Sen mukaan void on tyyppi, jolla ei ole yhtään arvoa. Aliohjelmakutsun tapauksessa tämä tarkoittaa intuitiivisesti hieman hämärää käyttäytymistä.

Olkoon void tee_jotain(int a, int b) { ... }. C käyttäytyy siten, että aliohjelmakutsu (tee_jotain(4, 6)) palaa kutsuvaan funktioon. Kuitenkin määritelmää tarkasti lukien voisi olettaa, että paluuta ei tapahdu. Luennoitsija esittikin, että tarkempi määritelmä olisikin, että void palauttaisi pohjan (pohja on käsittääkseni jotakuinkin sama asia kuin, että aliohjelman saavuttaessa loppunsa, se palaa kutsuvaan käyttäen paluuosoitetta). Edellä mainitun epäselvyyden vuoksi esitettiin erityistä "noreturn" tyyppiä, joka ei palaa kutsujaan.

En ole varma olisiko noreturn tyypistä käytännön hyötyä. Sinällään sen perusajatusta voi helposti emuloida esimerkiksi kutsumalla järjestelmätason poistukomentoa. Toisaalta se olisi hyvinkin eksplisiittinen tapa ilmaista, että aliohjelmakutsu ei palaa takaisin.

Luennolla mainittiin myös, että joissain kielissä aliohjelmista voidaan erottaa erityiset proseduurit. Näistä olen kuullut aiemminkin (erityisesti Delphin yhteydessä), mutta merkitys oli päässyt hieman unohtumaan. Ajatuksena on, että proseduurilla ei ole lainkaan palautusarvoja missään tapauksessa. Proseduureja käytetään sivuvaikutuksien avulla ohjelmointiin. Proseduuri voi manipuloida esimerkiksi jotain globaalia tilaa.

Periaatteessa olisi mahdollista luopua aliohjelman käsitteestä ja käyttää ainoastaan proseduureja. Kuitenkin pelkästään sivuvaikutusten avulla ohjelmointi tuntuu jotenkin vieraalta ajatukselta. Miten tässä tapauksessa kannattaisi hoitaa esimerkiksi hypot(a, b) (hypotenuusa) tulos? Tuloksen voisi tallentaa johonkin globaalisti saatavilla olevaan paikkaan, vaikkapa globaaliin result muuttujaan. Tämän ratkaisumallin ongelmat tulevat esiin, kun pitää suorittaa useita samanaikaisia proseduureja, jotka manipuloivat samaa globaalia dataa. Ei ole taetta siitä, että tulos on oikea. Toisessa ratkaisumallissa voitaisiin palautusosoite antaa parametrina.

Mielestäni aliohjelmien käyttäminen pelkkien proseduurien sijasta on varsin perusteltua. Toisaalta proseduuri sinällään sisältyy aliohjelman määritelmään, mikäli aiemmin mainittu void tai vastaava konstruktio on käytössä. Tässä mielessä on varsin luontevaa, ettei kieli satu sisältämään erillistä proseduurin käsitettä.

Mikäli kieleen haluaisi tarkan jaon aliohjelmien ja proseduurien välille, tämän voisi tehdä siten, että ainoastaan proseduureilla voi olla sivuvaikutuksia. Toisin sanoen voitaisiin eksplisiittisesti kieltää aliohjelmien sivuvaikutukset. Ohjelmoijan kannalta tästä saattaisi olla enemmän haittaa kuin hyötyä joustavuuden suhteen. Kuitenkin semantiikka säilyisi erittäin selvänä.

Aliohjelmista puhuttaessa eräs mielenkiintoinen ja luennolla sivuttu seikka on se, kuinka ne voivat palauttaa monia arvoja. Aina ei ole mielekästä palauttaa vain yhtä arvoa. Toisaalta, jos aliohjelma voi palauttaa monia arvoja kerralla, kuinka se tulisi määritellä staattisesti tyypitetyssä kielessä? Eräs luonteva tapa tehdä tämä on palauttaa monikko (tuple) tai tietue (structure).

Sekä monikot ja tietueet olivat jo ennalta tuttuja. Monikoita olen käyttänyt varsinkin Pythonissa. Sen toteutuksessa monikon sisältämiä viitteitä olioihin ei voi enää muokata luonnin jälkeen. Huomaa, ettei tämä tarkoita etteikö olioiden sisältöä voisi muokata! Ainoastaan viitteet on "lukittu".

Tietue on varsin tuttu käsite C:stä. Tietuehan on pohjimmiltaan vain monikko, jossa sisältöön voidaan viitata konkreettisten nimien avulla pelkkien indeksien sijasta. Tietueisiin liittyy myös varianttien käsite, jossa tietueen tiettyä osaa voidaan varioida. Voidaan siis matkia yksinkertaista perintää noin tietueen tasolla.

Tietue muistuttaa hyvin paljon assosiatiivista listaa (dictionary) rakenteeltaan. Dynaamisesti tyypitetyissä kielissä assosiatiivisen listan avulla voidaankin emuloida tietueita. Esimerkiksi Luassa tässä mennään varsin pitkälle erityisesti syntaksin suhteen (syntaksi muistuttaa C:n tietuesyntaksia mutta operoi assosiatiivista listaa).

Luennon lopussa käytiin läpi vielä viitetyyppien käsitettä. Joskus voi olla hyvinkin hyödyllistä, että voidaan operoida muistiosoitteiden tarkkuudella, kuten C:ssä ikään. Korkeamman tason kielet abstrahoivat tämän käyttäytymisen syntaksinsa alle. Tässä tapauksessa joudutaan tekemään automaattia käännöksiä osoitteiden ja arvojen välillä.

Demo 4 - kommentit

Neljännen, ja tähän asti vähiten suosituimman, demokerran tehtävät löytyvät osoitteesta http://users.jyu.fi/~antkaij/opetus/okp/2009/demot/4.html . Tehtävät olivat haastavia erityisesti mikäli lambda-laskento oli vielä hieman hakusessa. Itse sain tehtyä ensimmäinen tehtävän, josta sain jopa osan oikein.

Tehtävät olivat varmasti helppoja jos tiesi mitä on tekemässä. Ehkä suurin ongelma näin lambda-noobin kannalta on se, että en ole yksinkertaisesti nähnyt tarpeeksi lambda-lausekkeita. Mielestäni koodia tulisi lukea, kuten kirjallisuutta ikään (Milloin yliopistolle tulee tarjolle koodin lukukurssi?). Tällä tavoin saattaa oppia erilaisia tapoja ratkaista erinäisiä ongelmia ja samalla saattaa oppia erottamaan hyvän koodin huonosta. Tiedä sitten voiko "huonoa" lambda-koodia edes kirjoittaa, kunhan se toimii oikein?

Demokerran lopulla käytiin läpi pieni bonustehtävä. Ajatuksena oli luoda binäärilaskuri (0 -> 10 -> 11 -> 100 -> 101, ...) käyttäen lambda-laskentoa. Laskurille vietiin binäärinen arvo listana ja se palautti sitä seuraavan arvon listana kuitenkin siten, että siihen oli lisätty yksi (siis kymmenjärjestelmässä, ei concat-operaationa).

Sinänsä tehtävän formulointi algoritmiksi on varsin helppoa. Haastavuus piilikin algoritmin muuttamisessa lambda-muotoon, mikä loppujen lopuksi osoittautui melko yksinkertaiseksi.

Luento 10 - Lisää tyyppiteoriaa

Tällä kertaa pidettiin erittäin matemaattisesti orientoinut luento. Olennaisesti esitettiin staattisten tyyppijärjestelmien teoreettista perustaa. Tässä yhteydessä en aio käydä todistuksia läpi ja tästä tulleekin lyhin postaus tähän asti kirjoitetuista.

Olennaisin kysymys tämän postauksen kannalta lieneekin mitä opin luennolla, onhan kyseessä oppimispäiväkirja. Intuitiivisesti voi tuntua selvältä, että vahvasti tyypitetty kieli ei tuota ajonaikaisia (dynaamisia) virheitä vaan kaikki tyyppivirheet saadaan kiinni käännösvaiheessa. Kuitenkin asian todistaminen ei ole aivan vaivatonta, kuten luennolla näin.

Kenties tähän asti mystisin esitetty asia oli Hindleyn ja Milnerin tyyppipäättely. Tässä tapauksessa tyypit nimenomaan päätellään niiden käyttökontekstin perusteella.

Luennolla mainittiin myös Curry-Howard vastaavuudesta (Curry-Howard correspondence), jonka ajatuksena on, että ohjelmoinnista tuttuja tyyppejä ja ohjelmia vastaavat matematiikan puolella väittämät ja todistukset. Ohjelmointi on jossain mielessä matematiikkaa ja todistaminen taas ohjelmointia. Tästä varmaan seuraa myös, että matematiikkaa voidaan muuntaa ohjelmiksi ja toisinpäin. Toisin sanoen koodin toimivuus voidaan todistaa, mikä sinällään on ihan järkeenkäypää. Vaikeampi kysymys onkin onko mahdollista kirjoittaa kääntäjä, joka muuttaisi todistuksia haluttuun kieleen ja toisinpäin.

Todistuksista voisin mainita vielä sen verran, että äkkiseltään katsottuna ne näyttävät erittäin vaikeaselkoisilta. Tämä kuitenkin johtuu vain niiden korkeasta abstraktiotasosta. Matemaattinen notaatio on erittäin tiivistä. Luentojen välisellä tauolla kävinkin keskustelua notaation kääntämisestä konkreettiseksi suomeksi, mikä sinällään madalti todistusten ymmärtämisen kynnystä. Asiat ymmärtäisi ehkä kenties vielä paremmin, jos oikeasti joutuisi rakentamaan niihin pohjautuvia kieliä.

Luento 9 - Tyyppiteorian alkeet

Yhdeksännen luennon aiheena oli tyyppiteoria. Kaikissa ohjelmointikielissä on tyyppejä. Tyyppi kertoo oleellisesti, mitä tietyllä oliolla voi tehdä. Jossain ohjelmointikielessä voi olla esimerkiksi sallittua yhdistää lukuja tyyliin "5 . 2 . 342", josta seuraisi luku "52342". Toisaalta tämän tyylinen operaatio voi aiheuttaa virheen. Virhe voidaan havaita joko käännösvaiheessa tai ajonaikana. Tässä palataan jälleen aiemmin mainittuun jakoon, dynaamisesti ja staattisesti tyypitettyihin kieliin.

Kielet eivät välttämättä ole selvästi ainoastaan staattisia tai vain dynaamisia vaan ne voivat sisältää myös molempia piirteitä. Esimerkiksi Javassa käännösaikana saadaan kiinni melko paljon erilaisia tyyppivirheitä. Toisaalta myös ajonaikana niitä voidaan havaita. Pythonin tapauksessa staattista, käännösaikana tapahtuvaa tyyppitarkistusta ei tehdä lainkaan. Tarkistukset tehdään dynaamisesti ajonaikana.

Tässä yhteydessä lienee tarpeen mainita vahvuuden käsitteestä. Javan staattista ja dynaamista tyyppitarkistusta kumpaakin voidaan pitää melko vahvana. Pythonin staattista tarkistusta voidaan pitää erittäin heikkona, koska sillä ei ole sitä lainkaan, mutta toisaalta sen dynaaminen tarkistus on erittäin vahva.

Itselleni Pythonin lähestymistapa on Javaa luontevampi. Tyyppejä voi halutessaan välillä tarkistaa (esim. assert toimii mukavasti), mutta itse kieli ei pakota määrittelemään eksplisiittisiä tyyppejä. Tyypit määräytyvät sijoituksen perusteella. Esimerkiksi jos sijoitan muuttujaan kokonaisluvun, on sen tyyppi sen jälkeen kokonaisluku. Toisaalta myös kaikki muuttujat viittaavat olioihin (primitiivityyppejä ei ole lainkaan, kuten Javassa), mikä sinällään on ihan mielenkiintoista. Tietenkin myös aliohjelmia voi sijoittaa ovathan ne olioita.

Javan tapauksessa tyyppejä joutuu miettimään tarkemmin. Toisaalta myös geneerisen koodin kirjoittaminen on hankalampaa, mutta tätä varten Javassa onkin omat vippaskonstinsa. Dynaamisesta ympäristöstä tuttua tapaa ajatella on ikäänkuin liimattu Javan päälle, mikä ei välttämättä ole aivan huono asia, geneerisyys kun sattuu olemaan varsin kätevä apuväline.

Näen tyypit osana testausta. Koska dynaamisesti tyypitettyjen kielten tapauksessa tyyppejä ei kirjoiteta eksplisiittisesti itse ohjelmakoodiin, kannattaa esimerkiksi aliohjelmien ja luokkien rajapinta dokumentoida hyvin esimerkiksi testien ja docstringien avulla. Toki näin kannattaa tehdä myös Javan tapauksessa tyypeistä huolimatta.

Luennolla mainittiin, että staattisesti tyypitetyt kielet tulevat ennemmin tai myöhemmin kehittäjän tielle. Kielten rajoituksia voi kiertää mutta pitemmän päälle näin saa aikaan vain sotkua. Kielen kehittäjän näkökulmasta onkin haaste luoda staattisesti tyypitetty kieli, joka hyppii mahdollisimman vähän kehittäjän silmille.

Nähdäkseni staattisesti tyypitetyt kielet voivat toimia hyvin matalamman tason kielinä (vrt. C). Dynaaminen tyypitys sen sijaan toimii paremmin korkeamman abstraktiotason sisältävissä kielissä. Staattisen tyypityksen tapauksessa teknisiä, matalamman tason asioita tulee pohdittua jo luonnostaan enemmän. Dynaamisen tyypityksen tapauksessa teknisen tason jättää mielellään vähemmälle huomiolle.

Kielessä tulee olla tyyppejä joka tapauksessa. Hyvä kysymys onkin, kuinka monta tyyppiä kielessä tulee olla. Tämä riippuu suoraan kielen käyttötarkoituksesta. Mikäli ollaan tekemisissä matalamman tason kielen kanssa, voi olla hyvinkin suotavaa, että kielen tyypit on tarkasti mietitty nimenomaan suorituskyvyn kannalta. Korkeamman tason kielessä abstraktiota voidaan viedä suorituskyvyn kustannuksella korkeammalle tasolle. Ääriesimerkkinä Lua sisältää vain yhden lukutyypin, joka on toteutettu doublena. Perinteistä kokonaislukutyyppiä kielessä ei ole siis lainkaan. Toisaalta esimerkiksi C sisältää laajan kokoelman eri lukutyyppejä.

Luennolla esitettiin myös formaaleja tapoja esittää tyypillinen (siis kieli, joka sisältää tyyppejä) kieli. Oleellista määritelmissä on se, että niiden avulla muodostaa helposti ohjelmakoodiksi muuttuva rajoittimien joukko, jonka avulla tyyppeihin liittyvät tarkistukset voidaan tehdä. Rajoittimet voidaan esittää loogisina päättelylauseina, jotka olivatkin jo tuttuja aiemmalta luennolta. Ajatuksena on, että tietyllä ehdolla voidaan tehdä jotain. Karkeasti yksinkertaistettuna summa 5+8 voidaan esittää sääntönä, joka tarkistaa, että summa muodostuu tekijöistä, joiden kummankin tyyppi on luku.

Staattiset tyyppijärjestelmät vaikuttavat varsin yksinkertaisilta näin äkkiseltään. Kompleksisuus lienee syntyykin siinä vaiheessa, kun pitää määritellä useita eri tyyppejä ja miettiä mahdollisia eri operaatioita, joiden avulla tyypitettyjä muuttujia sallitaan käsiteltävän.

Demo 3 - kommentit

Väki vähenee ja pidot paranee. Kolmannen demokerran tehtävät löytyvät osoitteesta http://users.jyu.fi/~antkaij/opetus/okp/2009/demot/3.html . Ensimmäinen tehtävä seuraili jo edellisistä demoista tuttua sanaselityskonseptia. Noista kiinnostunut kaivaa määritelmät pikaisesti vaikka Wikipediasta. :)

Toisessa tehtävässä päästiin pohtimaan Jensenin vekotinta. Jonkinmoisena johtopäätöksenä tehtävään liittyen todettakoon, että moderneissa ohjelmointikielissä samaan ja semanttisesti selkeämpään lopputulokseen pääsee esimerkiksi lambdoja käyttäen (lambda kuvaa matemaattisen funktion, mikä Jensenin versiossa seuraa tuota call-by-name ajatusta). Merkitsin sekä ensimmäisen ja toisen tehtävän tehdyiksi. Kolmannen ja neljännen jätin väliin ja niiden sijaan teinkin bonustehtävän.

Yllättäen kolmannen tehtävän oli tehnyt vain yksi demojen osanottaja. Toistaalta "tarkasti laskeminen" on teknistä puuhaa, kuten osoittautui. Neljättä tehtävää ei ollut tehnyt kukaan, joten se jäi ikäänkuin laiskanläksyksi. Toisaalta tehtävänannon pyytämän for-silmukan johtanee jossain määrin whilen määrittelystä. Suurin haaste tuossa lienee iteraatiologiikan sisällyttäminen itse lausekkeeseen jotenkin järkevällä tavalla.

Bonustehtävänä oli tällä kertaa while-kielen denotationaaliseen määritelmään pohjautuvan tulkin kirjoittaminen. Valitettavasti olin ainut, joka oli kyseisen tehtävän tekemään, joten en saanut kyhäelmälleni vertailukohtaa (tosin hieman kuuklaamalla noita varmaan löytyy). Esittämäni versio löytyy osoitteesta http://users.jyu.fi/~jutuveps/interpreter.py .

Kyseessä oli ensimmäinen kirjoittamani tulkki. Siihen nähden tuo meni ihan mukavasti. Toteutin sen interaktiiviseen tyyliin, joten käyttäjä näkee reaaliajassa mitä tulkki oikein puuhailee.

Toisaalta tuossa versiossa on muutamia kohtia joita voisi huomattavasti hioa. Näin jälkikäteen ajatellen olisi kannattanut muutama viikko sitten kirjoittamani AST (Abstract Syntax Tree) luokka naftaliinista ja hoitaa sijoitusoperaatio sen kautta. Mutta meneehän se raa'alla voimallakin. :)

Vertailuoperaattorin kohdalla itse perusajatus on nähdäkseni ihan hyvä. Tosin check_condition funktion toteutusta voisi tiivistää aavistuksen muuttamalla sen taulukkopohjaiseksi ja tekemällä vertailufunktioista lambdoja. Tuo nyt on vain pieni kauneusvirhe mutta jotain mitä tekisin toisin.

Puolipisteen käsittely on jossain määrin karmealla tavalla toteutettu. Tällä hetkellä se toimii vain yksinkertaisimmassa tapauksessaan (esim. a = 5; b = 8). Tuotakin voisi hieman miettiä uudelleen.

Tulkin kirjoittaminen ei ollut läheskään yhtä vaikeaa kuin ennalta odotin. Se sopii mukavaksi ohjelmointiharjoitukseksi, jos sattuu tylsyys yllättämään. Jos oikein aikaa riittää, voi kenties saada aikaan jotain LOLPythonin tapaista.

KTHXBYE

Luento 8 - Aliohjelmien formalisointia - lambda-kieli

Kahdeksannen luennon aiheena oli käsitteen tasolla jo jossain määrin tuttu lambda-kieli. Lambdoja, anonyymeja funktioita, onkin aina silloin tällöin tullut käytettyä. Perusajatuksena on, että lambdalle annetaan syötearvoja, joiden avulla operoidaan ja lopulta palautetaan jotain järkevää. Esimerkiksi Pythonin syntaksia mukaillen "hypot = lambda x, y: (x*x + y*y)**0.5" toimisi hypotenuusan laskemiseen (hypot(3, 4) palauttaa 5 jne.). Lambdat ovat erityisen päteviä template method suunnittelumallin kanssa hyödynnettyinä.

Koko lambda-laskento perustuu sisäkkäisten funktioiden periaatteeseen. Sinänsä lambda-kielessä ei ole kokonaislukuja, liukulukuja ja muita vastaavia mukavuuksia! Ne tulee määritellä kielen itsensä avulla. Tämä sinällään tuntuu oudolta hieman erilaiseen määrittelyyn tottuneelta. Funktioiden sisäkkäisyydestä seuraa myös luonnostaan ohjelmoinnissa tuiki oleellisten näkyvyysalueiden käsite.

Lambda-lausekkeita voidaan käsitellä erityisten muunnosten avulla. Käsittely on oleellista erityisesti lausekkeiden arvioinnin kannalta. Täysin normalisoitu lambda-lauseke edustaa vastausta. Normalisoinnissa ajatuksena näyttää olevan oleellisestikin juuri lausekkeen pienten osien arviointi kerrallaan.

Alkeellisena esimerkkinä voisi ajatella kahden positiivisen kokonaisluvun n ja m summausta. Käsittääkseni tässä tapauksessa luentomonisteen lyhennysmerkintöjä lainaten saatettaisiin päätyä kenties seuraavanlaiseen normalisoituun muotoon: add(succ(succ(...(succ(zero)))), (näitä on n-kappaletta), succ(succ(...(succ(zero)))) (näitä on m-kappaletta)). Kokonaisluvut koostetaan summaamalla nollaan (zero) luvun arvo kertaa yksi ja lopuksi nämä luvut lasketaan yhteen.

Kertolaskulyhennyksen voisi mielestäni johtaa add:stä rekursiivisesti kenties seuraavasti (kerrotaan luvut n ja m, molemmat positiivisia kokonaislukuja): Olkoon positiviinen kokonaisluku int(n) = succ(succ(...(succ(zero))), jossa succ toistuu n kertaa (int on helpompi lukea :) ). Nyt saadaan add(int(n), add(int(n), add(int(n), ...*))), jossa * tarkoittaa, että sisäkkäisiä n operaatioita suoritetaan m kertaa (kertolaskun tarvitsema määrä). Veikkaisin, että tämä on jokseenkin sama kuin luentomonisteessa esitetty versio (pitää vielä tajuta, miten noita lambdoja lukea kunnolla :) ).

Liukulukujen (esim. 1.4235) esittäminen lambda-muodossa lienee haasteellista. Erittäin alkeellinen ja kenties harhaoppinen tapa olisi hahmottaa se kokonaislukuna siten, että desimaalierottimen sijainti suhteessa luvun vasemmanpuoleisimpaan tekijään tiedetään jotenkin erikseen. Toisaalta voisi kysyä myös, miten esittää esim. sqrt(2) lambda-notaation avulla. Tämä lienee tarvitsee jonkinmoisen pätevän määritelmän neliöjuurelle ja tätä kautta pääsisi ainakin rajattuun joukkoon liukulukuja käsiksi.

Tällä hetkellä suurin haaste lienee lukutaidon oppiminen. Pitänee vilkaista jotain funktionaalista kieltä ja katsoa miltä asiat näyttävät sen kannalta. Asia ei ole mahdotonta mutta tarvitsee hieman sulattelua. :)

Luento 7 - Lyhytaskelsemantiikka

Seitsemännen luennon aiheena oli lyhytaskelsemantiikka. Aiemmin esitellyssä denotationaalisessa semantiikassa päädyttiin pieniin vaikeuksiin jo while-lauseketta määriteltäessä. Kehittyneempiä käsitteitä on huomattavasti vaativampaa määritellä.

Lyhytaskelsemantiikan ajatuksena on luoda koneläheisempi tapa määritellä semantiikkaa. Denotationaalisen lähestymistavan perusajatushan oli olla täysin koneesta riippumaton, yleinen tapa. Lyhytaskelsemantiikka ottaa askelen lähemmäksi tietokonetta ja luopuu yleisyyden vaatimuksesta. Se sisältää tietokoneen abstraktion ja sen avulla määritellään omaa konekieltä, jolla sen tilaa manipuloidaan. Tämä katsantokannan muutos mahdollistaa helpommin hallittavan semantiikan hahmottamisen. Kääntöpuolena mainittiin todistamisen hankaloituminen.

Denotationaaliseen semantiikkaan verrattuna lyhytaskelsemantiikka on huomattavasti tiiviimpää ja siten myös mielestäni luettavampaa. Myös tapa, jolla ohjelmia voi tulkata lyhytaskelsemantiikan avulla annetun määritelmän avulla vaikutti varsin pätevältä.