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. :)