=> Tehtävä 1 <= mapcar ja maplist analysoivaan tulkkiin --------------------------------------- Toteuta kirjan kohdan 4.1.7 analysoivaan metasirkulaariseen Scheme-tulkkiin mapcar- ja maplist-proseduurit primitiiveinä. Proseduuri mapcar toimii kuten tavallinen Scheme-kielen map. Proseduuri maplist on muuten samanlainen kuin mapcar paitsi, että se antaa funktiolleen argumentiksi kaikkien loppulistojen ensimmäisten alkioiden sijaan koko loppulistat. Esimerkki: > (mapcar + '(1 2 3) '(3 2 1)) (4 4 4) > (maplist list '(1 2 3) '(3 2 1)) (((1 2 3) (3 2 1)) ((2 3) (2 1)) ((3) (1))) Tee siis proseduurit primitive-mapcar ja primitive-maplist täydentämällä seuraavia runkoja: (define (primitive-mapcar proc . lists) ) (define (primitive-maplist proc . lists) ) Tällaisen proseduurin voi lisätä metasirkulaariseen tulkkiin lisäämällä tulkin primitive-procedures-listaan alkiot (list 'mapcar primitive-mapcar) ja (list 'maplist primitive-maplist) (define primitive-procedures (list (list 'car car) (list 'cdr cdr) (list 'cons cons) (list 'null? null?) (list '+ +) (list '- -) (list '* *) (list '/ /) (list '= =) (list 'list list) ; em. esimerkkiä varten (list 'mapcar primitive-mapcar) (list 'maplist primitive-maplist) ;; more primitives )) Näin toteutettuna primitive-mapcar ja primitive-maplist saavat siis proc-argumenteikseen metasirkulaarisen tulkin proseduuriolion. Lists-argumenttiin tulee loput metasirkulaarisen tulkin esim. mapcarille annetut, evaluoidut, argumentit listana. Tekemäsi map-proseduurien siis tulee toimia useammalla argumentilla, esimerkiksi lausekkeen (mapcar + '(1 2) '(3 4)) tulee palauttaa lista (4 6). (Jos et ymmärrä (primitive-map proc . lists)-notaatiota, katso kirjan tehtävää 2.20.) Voit kopioida kirjassa olevan analysoivan metasirkulaarisen tulkin koodin itsellesi muokattavaksi evaluoimalla (copy-course-extension "a-eval" "a-eval.scm"), joka kopioi koodin Scheme-tulkin nykyiseen hakemistoon tiedostoon a-eval.scm (ks. johdantotehtävä 3). Tulkin voi käynnistää evaluoimalla tiedoston lopussa olevat kaksi kommentoitua riviä. Palauta vastauksena vain tekemäsi primitive-mapcar ja primitive-maplist -proseduurit. => Tehtävä 2 <= Listat laiskaan tulkkiin ------------------------ Kirjan kohdassa 4.2.3 laiskaan Scheme-tulkkiin lisätään laiskat listat tekemällä cons-, car- ja cdr-proseduurit, jotka käyttäytyvät halutulla tavalla, mutta eivät käsittele "oikeita" listoja, josta syystä mm. (car '(a b c)) ei kirjan toteutuksessa toimi. Tässä tehtävässä lisätään laiskaan Scheme-tulkkiin laiskat listat primitiiveinä. Car- ja cdr-primitiivit voidaan lisätä suoraan primitive-procedures-listaan, mutta consin tapauksessa tämä ei suoraan onnistu, koska laiska Scheme-tulkki evaluoi kaikki primitiiviensä argumentit ennen niiden kutsua, jolloin suoraan primitiivien joukkoon lisätty cons ei tee laiskoja listoja. Toteuta cons-, car-, cdr- ja null?-primiivit laiskaan tulkkiin niin että cons toimii laiskasti. Vihje: Laiskat primitiivit, kuten tällainen cons, täytyy käsitellä applyssä erikseen. Voit kopioida kirjassa olevan laiskan tulkin koodin itsellesi muokattavaksi evaluoimalla (copy-course-extension "l-eval" "l-eval.scm"), joka kopioi koodin Scheme-tulkin nykyiseen hakemistoon tiedostoon l-eval.scm. Tulkin voi käynnistää evaluoimalla (driver-loop). Palauta vastauksena tekemäsi uusien proseduurien ja muuttamiesi proseduurien määrittelyt (eli kaikki mitä muutit kopioidusta koodista). => Tehtävä 3 <= permutation ----------- Määrittele amb-tulkilla epädeterministinen Scheme-ohjelma permutation, joka palauttaa lukujoukon [1,n] permutaatiot. Esimerkki: ;;; Amb-Eval input: (permutation 0) ;;; Starting a new problem ;;; Amb-Eval value: () ;;; Amb-Eval input: (permutation 1) ;;; Starting a new problem ;;; Amb-Eval value: (1) ;;; Amb-Eval input: (permutation 2) ;;; Starting a new problem ;;; Amb-Eval value: (1 2) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (2 1) ;;; Amb-Eval input: try-again ;;; There are no more values of (permutation 2) Siis (permutation 0) palauttaa tyhjän listan. (permutation 1) listan (1) ja (permutation 2) listat (1 2) ja (2 1). Palauta vastauksena tekemäsi (permutation n) proseduurin määrittely. => Tehtävä 4 <= Amb-tulkki ja succeed-kutsut ---------------------------- Kirjan kohdan 4.3 amb-tulkki kutsuu evaluoinnin yhteydessä monia eri succeed- ja fail-kontinuaatioita. Esimerkki 1: Evaluoidaan lauseke 1 (pelkkä luku 1, joka siis evaluoituu luvuksi 1) amb-tulkissa. Kun tämä lauseke annetaan driver-loopille, se tekee kutsun (ambeval 1 the-global-environment succeed fail), missä succeed on kontinuaatio, joka näyttää saamansa arvon, ja fail on kontinuaatio, joka kertoo käyttäjälle, että lausekkeella ei ole arvoja (ks. driver-loopin koodia sivulta 435). Ambeval kutsuu (analyze 1):tä, joka tutkii lauseketta ja tekee kutsun (analyze-self-evaluating 1). Tämä palauttaa proseduurin (lambda (env succeed fail) (succeed 1 fail))), jota ambeval kutsuu antaen sille argumenteiksi driver-loopilta saamansa env-, succeed- ja fail-argumentit. Palautettu proseduuri kutsuu siis driver-loopin luomaa succeed-kontinaatiota argumenteilla 1 ja fail (driver-loopin luoma fail-kontinuaatio). Driver-loopin luoma succeed-kontinuaatio näyttää arvon 1 käyttäjälle. Tässä esimerkissä succeed-kontinuaatioita kutsuttiin siis vain kerran, ja tässä ainoassa kutsussa ensimmäisenä argumenttina oli tulos 1. Esimerkki 2: Evaluoidaan lauseke (if true 2 3), joka palauttaa luvun 2. Driver-loop kutsuu taas ambevalia ja antaa sille tekemänsä succeed- ja fail-kontinuaatiot. Ambeval kutsuu analyzeä, joka kutsuu analyze-ifiä antaen sille argumentiksi koko lausekkeen. Analyze-if analysoi lausekkeen osat (true, 2 ja 3) ja palauttaa proseduurin, jota ambeval kutsuu driver-loopin sille antamilla env-, succeed- ja fail-argumenteilla. Analyze-ifin luomassa proseduurissa kutsutaan ehdon (true) analysoinnin palauttamaa proseduuria. Tämä on analyze-variablen palauttama proseduuri, joka katsoo true-muuttujan arvon ympäristöstä (sen arvona on totuusarvo #t). Nyt se kutsuu succeed-kontinuaatiotaan tällä arvolla; analyze-ifissä luotua succeed-kontinuaatiota siis kutsutaan argumenteilla #t ja fail. Tämä kontinuaatio tarkistaa, onko arvo tosi (kutsu (true? #t)); se on, joten nyt kutsutaan if-lausekkeen tosi-haaraa eli lausekkeen 2 analysoinnin palauttamaa proseduuria. Tämä toimii kuten esimerkissä 1, eli kutsuu sille annettua succeed-kontinuaatiota argumenteilla 2 ja fail. Tämä succeed-kontinuaatio on se, jonka ambeval antoi analyze-ifin palauttamalle proseduurille, eli se näyttää arvon 2 käyttäjälle. Tässä esimerkissä siis kutsuttiin kahta succeed-kontinuaatiota niin että kutsujen ensimmäiset argumentit olivat #t ja 2. Tehtävä: Mitkä ovat kaikkien succeed-kontinuaatioiden kutsujen ensimmäiset argumentit, kun amb-tulkille annetaan (driver-loopissa) seuraava lauseke (jonka evaluointi antaa arvon 4; arvo 5 annettaisiin seuraavaksi, jos driver-loopille kirjoitettaisiin myös try-again): (if (= 1 2) 3 (amb 4 5)) Vihje: Kutsuja on 8 kpl. Palauta vastauksena vain kaikki ensimmäiset argumentit, kukin omalla rivillään. Palauttamiesi rivien järjestyksellä ei ole väliä. Jos kyseessä olisi esimerkki 2:n lauseke, palauttaisit siis seuraavat kaksi riviä: #t 2 Kuvaa totuusarvoja #t:llä ja #f:llä, =-proseduuria =-merkillä ja listoja normaalisti (esim. (4 5); tyhjä lista on '()). Voit kopioida kirjassa olevan amb-tulkin koodin itsellesi tutkittavaksi tai kokeiltavaksi evaluoimalla (copy-course-extension "amb-eval" "amb-eval.scm"), joka kopioi koodin Scheme-tulkin nykyiseen hakemistoon tiedostoon amb-eval.scm. Tulkin voi käynnistää evaluoimalla (driver-loop). => Tehtävä 5 <= permanent-set! -------------- Tee kirjan tehtävä 4.51 (s. 436). Palauta vastauksenasi kaikki ne amb-tulkin osat, joita muutit. Voit kopioida amb-tulkin itsellesi evaluoimalla (copy-course-extension "amb-eval" "amb-eval.scm") Niksulan Scheme-tulkissa. => Tehtävä 6 <= length ------ Luonnolliset luvut {0,1,2,...} voidaan määritellä seuraavasti seuraajafunktion ja luvun nolla avulla: 0 = 0 1 = s(0) 2 = s(s(0)) . . . Tämän määritelmän avulla voidaan määritellä SICP:n logiikka- ohjelmointikielellä plus-sääntö, joka laskee luonnollisten lukujen yhteenlaskuja: (assert! (rule (plus 0 ?x ?x))) (assert! (rule (plus (s ?x) ?y (s ?z)) (plus ?x ?y ?z))) Esimerkkejä plus-säännön käytöstä: ;;; Query input: (plus (s 0) (s 0) ?x) ; 1 + 1 = ? ;;; Query results: (plus (s 0) (s 0) (s (s 0))) ; 1 + 1 = 2 ;;; Query input: (plus (s 0) (s 0) (s 0)) ; 1 + 1 = 1 ;;; Query results: ; ei vastausta, koska 1 + 1 != 1. Huomaa, että plus-sääntöä voidaan käyttää myös näin: ;;; Query input: (plus (s 0) ?x (s (s 0))) ; 1 + ? = 2 ;;; Query results: (plus (s 0) (s 0) (s (s 0))) ; 1 + 1 = 2 Tai jopa näin: ;;; Query input: (plus ?x ?y (s (s 0))) ; ? + ? = 2 ;;; Query results: (plus (s (s 0)) 0 (s (s 0))) ; 2 + 0 = 2 (plus 0 (s (s 0)) (s (s 0))) ; 0 + 2 = 2 (plus (s 0) (s 0) (s (s 0))) ; 1 + 1 = 2 Toteuta kirjan logiikkatulkkiin length-sääntö, joka laskee listan pituuden. Length-sääntö ilmoittaa listan pituuden seuraajafunktion avulla esitetyillä numeroilla. Esimerkki: ;;; Query input: (length () ?x) ;;; Query results: (length () 0) ;;; Query input: (length (1) ?x) ;;; Query results: (length (1) (s 0)) ;;; Query input: (length (1 2 3) ?x) ;;; Query results: (length (1 2 3) (s (s (s 0)))) Palauta tekemäsi length-säännön määrittelyt assert!-komentojen sisällä. => Tehtävä 7 <= Yhdistetyt kyselyt ------------------ Tee kirjan tehtävä 4.57 kirjan sivulta 450. Anna korvaavuussäännölle nimeksi replaces. Syntaksi on (replaces ), missä ja on Microshaft-tietokannan henkilöiden nimiä. Tee myös tehtävän a-kohta. Logiikkatulkkiin voi lisätä omia sääntöjä assert!-komennolla. Esimerkiksi näin: ;;; Query input: (assert! (rule (replaces ...) ...)) Assertion added to data base. Palauta vastauksenasi replaces-säännön määritelly assert!-komennon sisällä ja vastaus a-kohtaan tässä järjestyksessä. => Tehtävä 8 <= unique logiikkatulkkiin ----------------------- Tee kirjan tehtävä 4.75 sivulta 488. Voit kopioida kirjan logiikkatulkin koodin itsellesi muokattavaksi evaluoimalla (copy-course-extension "q-eval" "q-eval.scm"), joka kopioi koodin Scheme-tulkin nykyiseen hakemistoon tiedostoon q-eval.scm. Palauta vastauksenasi vain tekemäsi uniquely-asserted-proseduurin määritelmä. HUOM! Älä muuta Microshaft-tietokantaa, koska tarkistin olettaa kyselyjen tulosten tulevan samassa järjestyksessä kuin copy-course-extensionilla kopioidussa q-eval-logiikkatulkissa. => Tehtävä 9 <= expmod rekisterikoneella ------------------------ Kirjan sivulla 51 on seuraava määritelmä expmod-proseduurille: (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) Tee tätä määritelmää vastaava rekisterikone, jossa =, even?, remainder, square, /, * ja - ovat primitiivioperaatioita. Koneen tulee ottaa argumentit rekistereissä base, exp ja m ja palauttaa tulos rekisterissä result. Tee rekursiiviset kutsut koneessa continue-rekisteriä ja pinoa käyttäen, samoin kuin esim. kirjan sivun 511 esimerkissä. Voit ladata rekisterikoneen tulkkiin evaluoimalla (load-course-extension "regsim") tai kopioida simulaattorin itsellesi evaluoimalla (copy-course-extension "regsim" "regsim.scm"). Tee kone täydentäen seuraavaa runkoa (täydennä sitä siis <...>:n kohdalta): (define expmod-machine (make-machine '(base exp m result continue <...>) (list (list '= =) (list 'even? even?) (list 'remainder remainder) (list 'square (lambda (x) (* x x))) (list '/ /) (list '* *) (list '- -)) '(<...>))) => Tehtävä 10 <= deep-reverse rekisterikoneella ------------------------------ Deep-reverse on reversen kaltainen listojen käsittelyoperaatio. Reverse kääntää listan alkiot ympäri eli (reverse '(1 2 3)) => (3 2 1), mutta (reverse '((1 2) 3)) => (3 (1 2)). Eli listan "sisällä" olevia listoja ei käännetä. Deep-reverse kääntää myös listan sisällä olevat listat: (deep-reverse '((1 2) 3)) => (3 (2 1)) Deep-reversen voi toteuttaa Schemellä esimerkiksi näin: (define (deep-reverse lst) (if (pair? lst) (append (deep-reverse (cdr lst)) (list (deep-reverse (car lst)))) lst)) Toteuta deep-reverse-operaation suorittava rekisterikone täydentämällä alla olevaa runkoa <...> merkityllä kohdalla: (define deep-reverse-machine (make-machine '(lst continue val) (list (list 'car car) (list 'cdr cdr) (list 'pair? pair?) (list 'append append) (list 'list list)) '(<...>))) Palauta vastauksenasi tekemäsi deep-reverse-machinen määrittely. Voit ladata rekisterikoneen tulkkiin evaluoimalla (load-course-extension "regsim") tai kopioida simulaattorin itsellesi evaluoimalla (copy-course-extension "regsim" "regsim.scm").