Teoriasta käytäntöön: Lambdakalkyylitulkin suunnittelu ja toteutus Haskellilla

Abstract

Tässä kandidaatintutkielmassa suunnitellaan ja toteutetaan tyypittömän lambdakalkyylin tulkki puhtaasti funktionaalisella Haskell-ohjelmointikielellä. Lisäksi tutkielmassa perehdytään erityisesti lambdakalkyylin ja evaluoinnin teoriaan. Työn tavoitteena on tarkastella, miten Alonzo Churchin 1930-luvulla kehittämä formaalin laskennan malli voidaan siirtää teoriasta konkreettiseksi, toimivaksi ohjelmistoksi. Tutkimuskysymys kuuluu: ”Miten tyypitön lambdakalkyyli voidaan toteuttaa modernissa puhtaasti funktionaalisessa ohjelmointikielessä?” Toteutettu tulkki koostuu syntaksi-, jäsennys- ja evaluointikomponenteista sekä pääohjelmasta, joka mahdollistaa lambdakalkyylilausekkeiden interaktiivisen evaluoinnin komentorivillä.

Työ alkaa kirjallisuuskatsauksesta toteutuksen kannalta kriittisiin aiheisiin. Teoriaosuudessa käsitellään muun muassa lambdakalkyylin teoriaa, erilaisia evaluointistrategioita ja syntaksin määrittelyä. Tämän jälkeen työn painopiste siirtyy toteutuksen suunnitteluun ja implementointiin koodi-esimerkkeineen. Lopuksi reflektoidaan suunnittelupäätösten ja teknisten valintojen vaikutuksia tulkin toteutukseen ja toimintaan sekä käsitellään jatkokehitysideoita.