Repetitio

Käsitteet

Ohjelmointikielten ehdottomasti tärkeimmät rakenteet ovat toistorakenteet. Ne sallivat tehdä ohjelmia, jotka käsittelevät suuren, mahdollisesti ennalta määräämättömän määrän tietoa. Toistorakenteiden käyttöä kutsutaan yleisesti repetitioksi. Repetitio jakautuu (joskaan ei tyhjentyvästi) kahteen päätyyppiin: iteraatioon ja rekursioon.

Iteraatio on yleisesti käytössä ns. imperatiivisissa ohjelmointikielissä, joita ovat kaikki yleisimmässä käytössä olevat kielet, kuten C, Java, C++ ja skriptikielet. Iteraatiossa tiettyjä ohjeita/toimia toistetaan, kunnes jokin ehto täyttyy. Esimerkiksi taulukon sisällön voi tulostaa käyttämällä indeksimuuttujaa, joka osoittaa vuorotellen kuhunkin taulukon jäseneen ja jonka kasvaessa taulukon koon yli lopetetaan:

(define (display-vector v)
  (do ((index 0 (+ index 1)))
      ((>= index (vector-length v)))
      (display (vector-ref v index))
      (newline)))

Funktionaalisissa kielissä, joihin Lisp-perheet kielet jokseenkin kuuluvat, käytetään kuitenkin usein rekursiota. Rekursiiviset algoritmit (= funktiot) ovat erityisen luonnollinen ratkaisu rekursiivisten tietorakenteiden käsittelyyn. Funktion rekursiivisuus tarkoittaa, että funktion x määrittelyssä käytetään apuna funktiota x itseään. Tietorakenteen rekursiivisuus taas tarkoittaa, että tietorakenne voi sisältää osanaan samanlaisia tietorakenteita. Seuraavassa pyrin antamaan esimerkkejä näistä.

Rekursiivisen tietorakenteen käsittely

Varmaankin yksinkertaisin esimerkki rekursiivisesta tietorakenteesta on Lisp-perheen kielten omin tietorakenne, lista. Lista on joko tyhjä, tai sitten se koostuu kahdesta asiasta, nimittäin ensimmäisestä elementistään ja toisesta listasta, jossa ovat loput elementit. Koska listan määrittelyyn kuuluu tällä tavoin, että siihen sisältyy toinen lista, on lista tietorakenteena rekursiivinen. Koska lista on rekursiivinen, myös sen läpikäynti on helpointa määrittää rekursiivisella algoritmilla:

(define (display-list ls)
  (cond ((null? ls) #f)
        (else (display (car ls))
	      (newline)
	      (display-list (cdr ls)))))

(cond on yleistetty if: siinä voi olla mielin määrin ehtoja, joita testataan ensimmäisestä viimeiseen, kunnes jokin ehto täyttyy, ja ehdon täyttyessä voi suorittaa useampia komentoja. Tässä käytetään cond:a, koska else-lausekkeessa on kolme komentoa.)

Rekursiivinen määrittely seuraa luonnostaan tietorakenteen määrittelystä. Tietorakenteen eri "muotoja"[1] — joita listalla on kaksi: se on joko tyhjä tai sitten koostuu ensimmäisestä elementistä ja lopuista — vastaavat ehtolausekkeen (esim. if tai cond) eri haarat. Perusmuotoja eli niitä muotoja, jotka eivät sisällä rekursiivisia osia — listojen tapauksessa tyhjiä listoja — vastaa jokin yksinkertainen operaatio, esim. yllä vain palautetaan #f. Yhdistelmämuotoja eli muotoja, joissa on rekursiivisia osia, vastaa jokin prosessointi, jonka osana käytetään rekursiivista kutsua tietorakenteen rekursiivisen osan käsittelemiseksi; esim. yllä display-list tulostaa listan ensimmäisen elementin sekä rivinvaihdon ja kutsuu itseään rekursiivisesti loppulistan käsittelemiseksi.

[1] näitä kutsutaan asianharrastajien keskuudessa tietomuodostimiksi

Toinen tyypillinen esimerkki rekursiivisesta tietorakenteesta on syntaksipuu. Käytämme esimerkkinä syntaksipuuta, jolla on kaksi muodostinta: joko puussa on vain yksi sana (perusmuoto) tai sitten se koostuu kahdesta puusta, joista toinen toimii määreenä toiselle (yhdistelmämuoto). Lisäksi jokaisessa puun solmussa (= haarauma tai lehti) on tagi, joka kertoo, onko kyseinen solmu verbilauseke, nominilauseke, adverbi tms.

Yksisanaisen puun voi esittää listana, jossa on ensin tagi ja sitten kyseinen sana (merkkijonona), esimerkiksi (v juoksee). Yhdistelmäpuun voi esittää listana, jossa on ensin tagi, sitten määrepuu ja viimeisenä pääpuu, esimerkiksi (vp (n poika) (v juoksee)). Määritämme myös kasan apufunktioita näiden puiden käsittelemiseen:

(Tässä käytetään uutta tietotyyppiä, symbolia, tagina. Symbolivakion voi kirjoittaa panemalla symbolin eteen heittomerkin. Oikeastaan ainoa, mitä symboleilla voi tehdä, on verrata niitä toisiinsa. Siksi ne ovat loistavia tageja. Symboleille on myös taattua, että eq? ja eqv? toimivat (toisin kuin merkkijonoille). Lisäksi yllä käytetään rakennetta let, jolla voi määrittää väliaikaismuuttujia, sekä funktiota (cadr s) = (car (cdr s)) ja funktiota (caddr s) = (car (cdr (cdr s))).)

(define (make-word tag word) (list tag word))
(define (make-noun word) (make-word 'n word))
(define (make-verb word) (make-word 'v word))
(define (make-adverb word) (make-word 'adv word))
(define (make-adjective word) (make-word 'adj word))

(define (make-phrase tag modif head) (list tag modif head))
(define (make-noun-phrase modif head) (make-phrase 'np modif head))
(define (make-verb-phrase modif head) (make-phrase 'vp modif head))

(define (syntax-tag s) (car s))
(define (syntax-phrase? s)
  (let ((tag (syntax-tag s)))
       (or (eqv? tag 'np) (eqv? tag 'vp))))
(define (syntax-word? s) (not (syntax-phrase? s)))
(define (syntax-modif s)
  (if (syntax-phrase? s) (cadr s) #f))
(define (syntax-head s)
  (if (syntax-phrase? s) (caddr s) #f))
(define (syntax-word s)
  (if (syntax-word? s) (cadr s) #f))

Katsokaamme nyt, miltä näyttää rekursiivinen funktio esim. syntaksipuun substantiivien (noun) laskemiseen:

(define (syntax-count-nouns s)
  (if (syntax-word? s)
      (if (eqv? (syntax-tag s) 'n) 1 0)
      (+ (syntax-count-nouns (syntax-modif s))
         (syntax-count-nouns (syntax-head s)))))

Yllä jälleen rekursiivinen määrittely lähtee siitä, että testataan, onko kyseessä perustapaus eli onko syntaksipuu yksisanainen. Jos on, lasketaan sen substantiivit hyvin yksinkertaisella operaatiolla: jos sana oli substantiivi ('n), siinä on yksi substantiivi; jos sana oli jokin muu, siinä on nolla substantiivia. Yhdistelmäpuulle taas lasketaan määrepuun ja pääpuun substantiivimäärät yhteen. Aika helppoa, eikö? Kokeillaanpa jotain muuta. Miten puusta saisi aikaiseksi merkkijonon, jossa ovat kaikki puun sanat?

(define (syntax->string s)
  (if (syntax-word? s)
      (syntax-word s)
      (string-append (syntax->string (syntax-modif s)) " "
                     (syntax->string (syntax-head s)))))

Kovasti samanlaiselta näyttää. Perustapauksessa, yksisanaisessa puussa, vain nostetaan kyseinen sana esiin. Yhdistelmätapauksessa liitetään yhteen määrepuuta vastaava merkkijono, välilyönti, ja pääpuuta vastaava merkkijono.

Ehkä olisi aika tehdä jotain vaikeampaa. Miten saisimme aikaan funktion, joka korvaa syntaksipuusta verbin jollain toisella sanalla? Katsotaanpa.

(define (syntax-replace-verb s new-verb)
  (case (syntax-tag s)
    ((n adj adv np) s)
    ((v) (make-verb new-verb))
    ((vp) (make-verb-phrase
            (syntax-modif s)
	    (syntax-replace-verb (syntax-head s) new-verb)))))

(case on myös tietynlainen ehtolauseke. Se vertaa ensimmäistä argumenttiaan (yllä (syntax-tag s)) erilaisiin arvoihin.)

Tällä kertaa perustapauksia on kaksi. Substantiivit, adjektiivit, adverbit ja nominilausekkeet eivät voi sisältää verbejä, joten niille on turha tehdä mitään. Ohjelma palauttaakin syntaksipuun sellaisenaan tässä tapauksessa. Sen sijaan verbi nimenomaan piti korvata toisella, ja sen tähden palautetaan uusi (yksisanainen) puu, jossa on uusi verbi. Rekursiotapaus syntyy vain verbilausekkeesta. Tällöin muodostetaan uusi verbilauseke, jossa määre on sama kuin entisessäkin mutta pääpuusta on verbi korvattu uudella (rekursiivinen kutsu).

Tarkastellaan vielä yhtä samanlaista operaatiota, nimittäin sanan x korvaamista y:llä syntaksipuusta. Se käy näin:

(define (syntax-replace-words s old-word new-word)
  (if (syntax-word? s)
      (if (string=? (syntax-word s) old-word)
          (make-word (syntax-tag s) new-word)
	  s)
      (make-phrase (syntax-tag s)
                   (syntax-replace-words (syntax-modif s) old-word new-word)
                   (syntax-replace-words (syntax-head s) old-word new-word))))

Tässäkin on kaksi perustapausta: yksisanainen puu joko on tai ei ole se sana, jonka haluamme korvata. Jos se on, palautamme uuden yksisanaisen puun (tagi tulee entisen perusteella). Jos ei, palautamme puun muutoksitta. Rekursiotapauksessa muodostamme uuden puun entisen tagista sekä entisen määre- ja pääpuista siten, että niistä on rekursiivisesti korvattu sanat toisilla.

Rekursiivisissa määrittelyissä on se (erinomainen) puoli, että ne ovat ns. applikatiivisia operaatioita eli ne eivät muuta argumentiksi saamiaan tietorakenteita vaan palauttavat vain uusia.[2]

[2] Tästä syystä on turvallista käyttää yhtä syntaksipuuta usean muun osana — on taattua, että kyseinen puu pysyy aina sisällöltään samana.

Palatkaamme vielä hetkeksi listoihin. Yllä muodostettiin syntaksipuista uusia puita siten, että rekursiivisten puunkäsittelykutsujen tulokset koottiin uudeksi puuksi make-verb-phrase:lla ja make-phrase:lla. Sama onnistuu tietenkin listojenkin suhteen. Listoja kootaan muodostimella cons. Esimerkiksi, jos haluaisimme kertoa kaikki listan luvut kahdella, voisimme kirjoittaa tällaisen määrittelyn:

(define (list-double ls)
  (if (null? ls) '()
      (cons (* 2 (car ls)) (list-double (cdr ls)))))

Perustapaus on jälleen tyhjä lista. Tyhjän listan luvut kerrottuna kahdella on uusi tyhjä lista; ei-tyhjän listan luvut kerrottuna kahdella on uusi lista, jossa on ensin vanhan listan ensimmäinen luku kerrottuna kahdella ja sitten loppulistan luvut kerrottuina kahdella (rekursiivinen kutsu). Tämä rutiini on sen verran yksinkertainen, että voisimme katsoa, kuinka se toimii. Alla esitetään rivi riviltä, kuinka laskenta etenee.

(list-double '(1 3 5)) ->
(cons (* 2 1) (list-double '(3 5))) ->
(cons 2 (list-double '(3 5))) ->
(cons 2 (cons (* 2 3) (list-double '(5)))) ->
(cons 2 (cons 6 (list-double '(5)))) ->
(cons 2 (cons 6 (cons (* 2 5) (list-double '())))) ->
(cons 2 (cons 6 (cons 10 (list-double '())))) ->
(cons 2 (cons 6 (cons 10 '()))) ->
(cons 2 (cons 6 '(10))) ->
(cons 2 '(6 10)) ->
'(2 6 10)

Listojen läpikäymiseen esitellään tuonnempana muutamia apukeinoja, jotka ovat joskus (esim. tässä tapauksessa) näppärämpiä kuin rekursiivisen rutiinin kirjoittaminen.

Generatiivinen rekursio

Edellisessä paneuduttiin ensisijaisesti ns. strukturaaliseen rekursioon eli tietorakenteen rakenteeseen perustuvaan rekursioon. Rekursio on kuitenkin erittäin yleispätevä tekniikka, jolla pystyy helposti kuvaamaan minkä tahansa iteratiivisen menetelmän. Rekursiota, joka ei perustu niinkään tietorakenteen ominaisuuksiin vaan johonkin sopivasti valittuihin lopetusehtoihin ja argumenttien vaihdoksiin, sanotaan generatiiviseksi. Ottakaamme esimerkiksi alussa käsitelty taulukon (iteratiivinen) läpikäynti indeksimuuttujalla. Jos haluamme olla oikein perusteellisia, sen toistoon perustuva versio näyttää tältä:

(define (display-vector v)
  (let ((index 0))
       (do () ((>= index (vector-length v)))
           (display (vector-ref v index))
	   (newline)
	   (set! index (+ index 1)))))

Yleinen tyyli näissä toistoissa on seuraava: toistetaan, kunnes tietty ehto täyttyy; joka toistolla tehdään tiettyjä asioita ja päivitetään muutamia tilamuuttujia, jotka kertovat, missä mennään (kuten index yllä); sitten testataan ehtoa taas. Jokaisen tällaisen toiston voi muuttaa rekursiiviseksi määrittelyksi helposti ja suoraviivaisesti muuttamalla toistorakenteen funktioksi, tilamuuttujat funktion argumenteiksi ja tilamuuttujien päivittämisen uusien argumenttiarvojen laskemiseksi. Esimerkiksi näin:

(define (display-vector-from v index)
  (cond ((>= index (vector-length v)) #f)
        (else (display (vector-ref v index))
	      (newline)
	      (display-vector-from v (+ index 1)))))
(define (display-vector v)
  (display-vector-from v 0))

Toisena esimerkkinä voisi toimia taulukon summa. Tyypillinen iteratiivinen ratkaisu näyttää tältä:

(define (vector-sum v)
  (let ((index 0) (sum 0))
       (do () ((>= index (vector-length v)))
           (set! sum (+ sum (vector-ref v index)))
	   (set! index (+ index 1)))
       sum))

Rekursiivisessa ratkaisussa sekä sum että index muuttuvat argumenteiksi, koska niiden arvoa päivitetään joka toistolla:

(define (vector-sum-helper v index sum)
  (cond ((>= index (vector-length v)) sum)
        (else (vector-sum-helper v (+ index 1) (+ sum (vector-ref v index))))))
(define (vector-sum v)
  (vector-sum-helper v 0 0))

Huomaa, että toisin kuin display-vector, vector-sum palauttaa jotain: taulukon summan. Iteratiivisessa versiossa palautettava arvo on funktion lopussa, kun do-silmukka on suoritettu loppuun. Rekursiivisessa versiossa se on perustapauksen (index suurempi kuin taulukon pituus) arvo.

Tällaisella tekniikalla voi helposti määrittää myös listan kääntävän funktion (siis ensimmäinen elementti viimeiseksi ja päin vastoin):

(define (list-reverse-helper ls result)
  (cond ((null? ls) result)
        (else (list-reverse-helper (cdr ls) (cons (car ls) result)))))
(define (list-reverse ls)
  (list-reverse-helper ls '()))

list-reverse-helper liittää listan ls elementtejä yksi kerrallaan result-listaan, kunnes ei ole enää mitään liitettävää. Tällöin result palautetaan lopputuloksena.

Jokikinen tässä jaksossa esimerkkinä ollut rekursiivinen määrittely koostuu kahdesta funktiosta: varsinaisen rekursion tekevästä apufunktiosta ja wrapper-funktiosta, joka antaa varsinaisen työn tekevän funktion argumenteille oikeat alkuarvot. Koska tällainen rakenne on erittäin yleinen, schemessä on tyylikäs nimetty let-rakenne. Se sallii määrittää apufunktion ja samalla määrittää sen argumenttien alkuarvot. Esimerkiksi yllä olevat rekursiiviset määrittelyt näyttäisivät sen avulla seuraavilta:

(define (display-vector v)
  (let loop ((index 0))
       (cond ((>= index (vector-length v)) #f)
             (else (display (vector-ref v index))
	           (newline)
		   (loop (+ index 1))))))

(define (vector-sum v)
  (let loop ((index 0) (sum 0))
       (if (>= index (vector-length v)) sum
           (loop (+ index 1) (+ sum (vector-ref v index))))))

(define (list-reverse ls)
  (let loop ((remaining ls) (result '()))
       (if (null? remaining) result
           (loop (cdr remaining) (cons (car remaining) result)))))

Jokaisessa yllä olevista esimerkeistä apufunktion nimi on loop, mutta se voi olla aivan hyvin jotain muutakin, mahdollisesti kuvaavampaa. Tällä tavoin tehdyt määritelmät ovat usein hyvin ytimekkäitä, jopa pelottavan tiiviitä. Huolellisella lukemisella ne kumminkin selviävät.

Yhtenä esimerkkinä generatiivisesta rekursiosta voisi ottaa funktion iota, joka palauttaa kaikki numerot nollasta n:ään. Tässä yhdistämme nimetyn let:n käytön ja listojen rakentamisen rekursiivisesti. Annan ensin kahta funktiota käyttävän määritelmän, sitten vastaavan nimettyä let:a käyttävän määritelmän:

(define (numbers from to)
  (if (>= from to) '()
      (cons from (numbers (+ from 1) to))))
(define (iota n)
  (numbers 0 n))

(define (iota n)
  (let numbers ((current 0))
       (if (>= current n) '()
           (cons current (numbers (+ current 1))))))

Vielä yksi esimerkki generatiivisesta rekursiosta voisi olla puhtaasti numeeriset algoritmit. Näissä perustapaus on usein nolla tai jokin muu perusnumero, joita rekursiiviset kutsut lähestyvät. Esimerkistä käyköön Fibonaccin sarjan n. luku. Ensin kahden funktion määritelmä, sitten let-pohjainen:

(define (fibonacci-helper n x1 x2)
  (if (= n 0) x1
      (fibonacci-helper (- n 1) (+ x1 x2) x1)))
(define (fibonacci n)
  (fibonacci-helper n 1 0))

(define (fibonacci n)
  (let loop ((iterations n) (x1 1) (x2 0))
       (if (= iterations 0) x1
           (loop (- iterations 1) (+ x1 x2) x1))))

Iteraattorit: siistimpi keino yleisiin tarpeisiin

Tietyt tavat käsitellä tietorakenteita ovat yleisempiä kuin toiset. Esimerkiksi listoille on erittäin tyypillistä käydä se läpi, tehdä jotain jokaiselle sen elementille, ja palauttaa uusi lista näiden operaatioiden tuloksista. Alkupuolella käsittelemämme lukulistan elementtien tuplaaminen on esimerkki tällaisesta operaatiosta.

Funktionaalisissa ohjelmointikielissä on mahdollista määritellä funktioita, jotka auttavat tällaisissa yleisissä tietorakenteiden käsittelytavoissa. Näitä kutsutaan tuttavallisesti iteraattoreiksi, ja perinteinen esimerkki niistä on map, joka nimenomaan käy listan läpi, tekee jonkin operaation sen elementeille ja palauttaa uuden listan tuloksista. Iteraattoreita on helpompi ymmärtää käytännön esimerkkien kuin määrittelyn kautta. Esimerkiksi listantuplausfunktion voisi määrittää näin:

(define (double x) (* 2 x))
(define (list-double ls) (map double ls))

map ottaa siis kaksi argumenttia: ensinnäkin funktion, jota sovelletaan kuhunkin listan elementtiin vuorollaan; toisekseen listan, jonka elementteihin sitä sovelletaan. map palauttaa listan, joka koostuu argumenttifunktion palauttamista arvoista.

Otetaan toiseksi esimerkiksi hyvin samanlainen toimenpide: listan jokaisen luvun korottaminen toiseen potenssiin. Annan ensin rekursiivisen määritelmän ja sitten iteraattorimääritelmän:

(define (square x) (* x x))

(define (list-square ls)
  (if (null? ls) '()
      (cons (square (car ls)) (list-square (cdr ls)))))

(define (list-square ls)
  (map square ls))

Jos taas annan map:lle funktion even?, saan listan siitä, mikä numero oli parillinen ja mikä ei:

(map even? '(1 2 3 5 8))  =>
'(#f #t #f #f #t)

Toinen, vähän käytännönläheisempi esimerkki on merkkijonon muuttaminen pieniksi kirjaimiksi. Schemessä on sisäänrakennettu funktio char-downcase, joka toimii vain merkeille. Mutta jos merkkijonon muuttaa merkkien listaksi, voimme käyttää map:a, ja tuloslistan voi muuttaa takaisin merkkijonoksi:

(define (string-downcase str)
  (list->string (map char-downcase (string->list str))))

(string-downcase "HeLL!o")  =>
"hell!o"

Map-funktiossa muuten ei ole mitään maagista. Sen pystyy helposti määrittelemään itsekin. Tätä määritelmää ei tarvitse ymmärtää, mutta sen huolellinen pohdiskelu saattaa nostaa korkeammalle tietoisuuden tasolle (tai sitten ei):

(define (map operation ls)
  (if (null? ls) '()
      (cons (operation (car ls)) (map operation (cdr ls)))))

Toinen tyypillinen iteraattori on filter. Se ottaa kaksi argumenttia: funktion, joka palauttaa totuusarvon, ja listan. Se käy listan läpi ja muodostaa uuden listan, jossa ovat alkuperäisestä listasta vain ne elementit, joille argumenttifunktio palauttaa toden. Esimerkiksi:

(filter even? '(1 2 3 5 8))  =>
'(2 8)

(filter string? '(1 3 "foo" #\o "bar"))  =>
'("foo" "bar")

Kaikissa Schemeissä ei ole filter-funktiota sisäänrakennettuna. Se on toki helppo määritellä. Tämänkin määritelmän tuijottaminen saattaa nostaa tietoisuuden tasoa:

(define (filter take? ls)
  (if (null? ls) '()
      (if (take? (car ls))
          (cons (car ls) (filter take? (cdr ls)))
	  (filter take? (cdr ls)))))

Joskus on mahdollista määritellä jossain mielessä allegorisia iteraattoreita muillekin tietorakenteille kuin listoille. Esimerkiksi syntaksipuille voisimme määrittää syntax-map-funktion, joka ottaa funktion ja syntaksipuun ja palauttaa uuden syntaksipuun, jossa jokainen sana on prosessoitu argumenttifunktion läpi. Tämän avulla voisimme tehdä esim. samaa kuin syntax-replace-words-funktiolla:

(define (syntax-map op s)
  (if (syntax-word? s)
      (make-word (syntax-tag s) (op (syntax-word s)))
      (make-phrase (syntax-tag s)
                   (syntax-map op (syntax-modif s))
		   (syntax-map op (syntax-head s)))))

(define (replace-foo-with-bar word)
  (if (string=? word "foo") "bar" word))
(define (syntax-replace-foo-with-bar s)
  (syntax-map replace-foo-with-bar s))

Voisimme helposti myös jatkaa pieniksi kirjaimiksi muuntamisen vimmaamme:

(define (syntax-downcase s)
  (syntax-map string-downcase s))

Yllä list-double- ja list-square-esimerkeissä määritimme apufunktiot double ja square, koska iteraattoreille pitää antaa funktio argumenttina. Samoin syntax-replace-foo-with-bar käyttää (typerää) apufunktiota replace-foo-with-bar. Iteraattorien kanssa tulee usein tarve muodostaa pieniä apufunktioita lennossa. Onneksi Schemessä on keino muodostaa nimettömiä funktioita. lambda-operaatio (nimi on historiallinen jäänne) palauttaa funktion, joka ottaa tietyt argumentit ja palauttaa tietyn arvon. Esimerkiksi:

(define (list-double ls)
  (map (lambda (x) (* 2 x)) ls))
(define (list-square ls)
  (map (lambda (x) (* x x)) ls))
(define (syntax-replace-words s old new)
  (syntax-map
    (lambda (word)
      (if (string=? word old) new word))
   s))

lambda näyttää siis samalta kuin define, paitsi että mitään nimeä funktiolle ei sanota. lambda:n perässä olevissa sulkeissa luetellaan funktion saamat argumentit ja niiden jälkeen kerrotaan, mitä funktio tekee (palauttaa). Itse asiassa Schemessä funktioiden define on määritelty lambda:n perusteella, ja seuraavat määritelmät ovat keskenään yhtäpitäviä:

(define (square x) (* x x)    <->  (define square (lambda (x) (* x x)))
(define (distance x y)        <->  (define distance (lambda (x y)
 (sqrt (+ (square x) (square y))))  (sqrt (+ (square x) (square y))))

Tämänkin pohdiskelu saattaa tuottaa korkeamman tietoisuuden tason tai olla tuottamatta.