Homoikonisuus

Esivaroitus

Tässä käsitelty aihe on vaikea ja teoreettinen. Siihen ei välttämättä kannata tutustua, ellei ole pakko. Pakko saattaisi olla esim. siinä vaiheessa, kun symbolien ja listojen erilaiset syntaksit alkavat kummastuttaa. Esimerkiksi listan voi kirjoittaa molemmilla seuraavista tavoista:

'(1 3 #\r)
(list 1 3 #\r)

Tämän dokumentin on tarkoitus selittää syy tähän ja muutamaan muuhunkin asiaan.

Mitä homoikonisuus tarkoittaa?

Itse asiassa homoikonisuus tarkoittaa useampiakin asioita, mutta Lisp-perheen kielten yhteydessä sillä on vakiintunut merkitys. Se tarkoittaa, että ohjelmilla (lausekkeilla, funktioilla jne.) on (yksiselitteinen) esitystapa tietorakenteina. Toisaalta tietorakenteilla on (yksiselitteinen) esitystapa tekstinä eli merkkijonoina.

Mitä tämä tarkoittaa? Tarkastellaan ilmausta (+ 3 5). Kun se on ohjelmatiedostossa tai käyttäjä kirjoittaa sen, se on merkkijono (+ 3 5) ja siinä on seitsemän merkkiä (kaksi välilyöntiä ja viisi muuta merkkiä). Mutta se sattuu olemaan myös kolmielementtisen listan esitysmuoto tekstinä. Schemen sisäänrakennettu funktio (read) osaa lukea näitä ulkoisia esitysmuotoja ja palauttaa niitä vastaavan tietorakenteen; tässä tapauksessa listan, jossa on kolme elementtiä (symboli +, luku 3 ja luku 5).

Se, onko ilmaus (+ 3 5) tietorakenne vai pätkä ohjelmaa, riippuu siitä, mitä sillä tehdään. Jos haluamme kohdella sitä tietorakenteena, voimme tehdä sille listaoperaatioita — esimerkiksi car palauttaa siitä symbolin +. Jos taas haluamme kohdella sitä ohjelmana, annamme sen tyypillisesti funktiolle eval, joka suorittaa sen ohjelmana ja palauttaa, mitä suorituksesta on tuloksena — esimerkkitapauksessamme luku 8.

Tarkastellaan jotain vielä yksinkertaisempaa ilmausta, esimerkiksi symbolia foo. Sekin voidaan nähdä tietorakenteena tai ohjelmana. Tietorakenteena sitä voi esim. verrata muihin symboleihin eqv?-predikaatilla. Mutta, jos se suoritetaan ohjelmana, se onkin muuttuja, ja eval palauttaa tällöin muuttujan foo arvon.

Miksi homoikonisuus on vaikea juttu?

Homoikonisuus aiheuttaa jonkin verran väärinkäsityksiä. Yksi ongelma on se, että tietyt asiat tuottavat saman tuloksen suoritettuina kuin mitä ne ovat tietorakenteina. Esimerkiksi luku 3 on tietorakenne, mutta toisaalta sen suorittaminen ohjelmana tuottaa myös luvun 3. Samoin merkkijono väsyttää on toisaalta tietorakenne, mutta toisaalta ohjelma, joka eval:lle annettuna tuottaa tismalleen saman tuloksen, nimittäin merkkijonon väsyttää. Tällaisista rakenteista sanotaan, että ne evaluoituvat itsekseen, ja niihin kuuluvat lukujen ja merkkijonojen lisäksi totuusarvot ja merkit.

Sen sijaan esimerkkejä rakenteista, jotka eivät evaluoidu itsekseen ovat juuri listat (jotka tulkitaan funktiokutsuina), symbolit (jotka tulkitaan muuttujiin viittaamisena) sekä hiukan yllättäen taulukot (joille ei ole mitään evaluointitulkintaa).

Operaatio quote, jolla on lyhennemerkintänä heittomerkki, estää argumenttinsa evaluoimisen. Esimerkiksi:

(define x y)
(define x 'y)

Näistä lausekkeista ensimmäinen antaa muuttujan x arvoksi saman kuin y:n arvo. Toinen sen sijaan antaa muuttujan x arvoksi symbolin y. Tämä johtuu siitä, että quote esti ilmauksen y tulkinnan muuttujana ja jätti sen sen sijaan symboliksi. Samaan tapaan:

(define x (+ 3 5))
(define x '(+ 3 5))

Ensimmäinen lauseke sijoittaa x-muuttujaan luvun 8, sillä se on ilmauksen (+ 3 5) evaluoinnin tulos. Sen sijaan toisessa quote estää listan evaluoinnin, jolloin x-muuttujaan päätyykin kolmielementtinen lista (jonka elementit ovat symboli + sekä luvut 3 ja 5).

Sen sijaan esimerkiksi näillä ei ole mitään eroa:

(define x "foo")
(define x '"foo")

Ensimmäisessä tapauksessa foo evaluoidaan, ja tuloksena on foo, joka sitten sijoitetaan x-muuttujaan. Toisessa tapauksessa foo:a ei evaluoida, vaan quote palauttaa sen sellaisenaan, ja se sijoitetaan x-muuttujaan. Vaikutus on tismalleen sama.

Toinen, mikä usein aiheuttaa käsittämisvaikeuksia ihmisille, on se, kuinka ohjelmia suoritetaan eli kuinka eval toimii. Esimerkiksi ilmauksen (* 2 x) suorittaakseen eval tekee monta asiaa:

1. se tulkitsee symbolin * muuttujana, eli hakee sen arvon (joka on kertolaskufunktio);
2. se toteaa luvun 2 itse-evaluoituvaksi;
3. se tulkitsee symbolin x muuttujana, eli hakee sen arvon (joka on oletettavasti jokin luku);
4. se soveltaa kertolaskufunktiota lukuun 2 ja lukuun, joka oli muuttujan x arvona.
5. se palauttaa kertolaskun tuloksen.

Jos eval kohtaa listan sisällä toisen listan, tämä alalista evaluoidaan ensin; esimerkiksi ilmauksen (car (cdr mylist)) suoritus etenee näin:

1. eval hakee symbolin car arvon (joka on funktio);
2. eval alkaa suorittaa ilmausta (cdr mylist);
3. eval hakee symbolin cdr arvon (joka on funktio);
4. eval hakee symbolin mylist arvon (joka on toivottavasti lista);
5. eval soveltaa cdr-funktiota kyseiseen listaan;
6. eval soveltaa car-funktiota tästä tuloksena olleeseen listaan;
7. eval palauttaa tästä tuloksena olevan arvon.

Homoikonisuuden seurauksia

Homoikonisuudesta seuraa suoraan se, että listat ja symbolit ovat erityisiä. Niitä ei voi kirjoittaa sellaisinaan lähdekoodiin, kuten lukuja, totuusarvoja yms., vaan ne pitää suojata quote:lla (tai sen lyhennemerkinnällä heittomerkillä). quote suojaa evaluoinnilta koko argumenttinsa. Esimerkiksi ilmauksesta (quote (x y z)) on suoritettaessa tuloksena lista, jossa on kolme symbolia (x, y ja z); ei lista, jossa on muuttujien x, y ja z arvot. Tämän vuoksi, jos halutaan perustaa lista, jossa jokin elementti on laskettu tai tulee muuttujasta, tarvitaan operaatiota list (tai cons). Seuraavat ilmaukset tuottavat suoritettuina saman tuloksen:

'("foo" bar 3)
(list "foo" 'bar 3)
(cons "foo" (cons 'bar (cons 3 '())))

Jos listoja on paljon sisäkkäin, tilanne voi tulla varsin monimutkaiseksi. Seuraavat ilmaukset tuottavat myös keskenään saman tuloksen:

'(vp (n "poika") (v "juoksee"))
(list 'vp (list 'n "poika") (list 'v "juoksee"))
(cons 'vp
 (cons (cons 'n (cons "poika" '()))
  (cons (cons 'v (cons "juoksee" '()))
   '()))

Myös taulukot on suojattava evaluaatiolta quote:lla. Niiden evaluoimisella ei ole määritettyä arvoa, vaan se on virhe:

(define x #(1 4 5 6))   ; VIRHE
(define x '#(1 4 5 6))  ; sijoittaa taulukon muuttujaan x

Homoikonisuudella on myös mielenkiintoisia käytännön seurauksia. Yksi on se, että ohjelmia voi tarkastella tietorakenteina:

(if (eqv? '+ (car ilmaus)) (error "En suostu tekemään yhteenlaskua")
    (eval ilmaus))

Yksi ensimmäisiä ohjelmia, joka Lisp:lla aikoinaan kirjoitettiin, oli Lisp-kielen toteutus. Se on vain muutamia kymmeniä rivejä pitkä. Lisäksi on verrattain helppoa kirjoittaa yksinkertaisia kieliä, joissa on samanlainen (read) (eli merkit tulkitaan samalla tavalla tietorakenteeksi) mutta erilainen (eval) (eli tietorakennetta suoritetaan eri tavalla). Esimerkiksi tekoälyohjelmissa on joskus sisäinen kyselykieli, joka saattaa näyttää esim. tältä:

; hae yli 50-vuotiaat ihmiset, joiden äiti asuu Helsingissä
(and (ikä x ikä)
     (> 50 ikä)
     (äippä x y)
     (asuu-kaupungissa y "Helsinki"))

; voitaisiin käyttää esim. näin (huom! fetch-tuples on siis se, jossa
; koko kyselykieli on varsinaisesti toteutettu)
(fetch-tuples '(and (ikä x ikä) (> 50 ikä)))
; tulos voi olla esim. lista erilaisista x:n ja ikä:n arvoista...

Quasiquote: näppärä tapa kirjoittaa tietorakenteita

Schemessä on myös operaatio quasiquote, jonka voi lyhentää käänteisheittomerkillä (`). Se toimii muuten niin kuin quote, paitsi että sekaan voi livauttaa pilkulla merkittynä kohtia, jotka sittenkin evaluoidaan. Esimerkiksi nämä ilmaukset tuottavat saman suoritettuina:

'(x y 4 (+ 2 1))
(list 'x 'y (+ 2 2) '(+ 2 1))
w_bq (x y ,(+ 2 2) (+ 2 1))

quasiquote on ehdottoman hyödyllinen, jos listan tai taulukon osana on jotain, minkä arvo ei ole vakio. Esimerkiksi seuraava funktio tuottaa lausetta punainen x laulaa villisti vastaavan syntaksipuun (jossa x on vaihtuva osio):

(define (make-syntax-example x)
  w_bq (vp (np (adj "punainen") (n ,x)) (vp (adv "villisti") (v "laulaa"))))

Tällaisen tekeminen list-operaatiolla on lähinnä itsensä turhaa kiduttamista… Toinen hyvä esimerkki voisi olla henkilötietorakenteen muodostava funktio:

(define (make-person name age city)
  w_bq (:person #(,name ,age ,city)))