Teknillinen korkeakoulu T Tik-76.101 Ohjelmoinnin pitkä peruskurssi

Tietojenkasittelyopin laboratorio Tentti 214.1998 Saikkonen, Syrjänen, Tiusanen

Merkitse jokaisen vastauspaperisi vasempaan yläreunaan selvästi allekkain:

. Tik-76.101 Ohjelmoinnin pitkä peruskurssi ~ tentti 21.04.1998

. sukunimi, etunimet

. koulutusohjelma, opintokirjan numero

Tentissä saa käyttää apuna kurssikirjaa (Abelson & Sussman), mutta ei muuta materiaalia (esim. opetusmonisteita tai laskimia).

Käytä mahdollisimman selvää käsialaa, jätä riittävät marginaalit sivun laitoihin ja merkitse tehtävän numero näkyviin. Merkitse jokaiseen paperiin paperien kokonaismäärä. Tentin korjaamisen jouduttamiseksi vastaa eri tehtäviin eri papereilla alla olevien ohjeiden mukaan. Palauta paperit kukin omaan nippuunsa.

Paperille 1:

I. Pascalin kolmion:

1 1

1 2 1

1 3 3 1

1 4 6 4 1

n's rivi sisältää ns. "binomikertoimet", eli sen x:n ja y:n polynomin kertoimet, joka on saatu, kun binomi (x + y) on korotettu potenssiin n ja lavennettu. Tee Scheme proseduuri (bincoeff i j), joka laskee rivin i kertoimen j käyttäen rekursiivista prosessia. (6p)

2. On määritelty seuraavat proseduurit:

(define (cons x y)

(lambda (m) (m x y)))

(define (car z)

(z (lambda (p q) p)))

Osoita, että kaikille objekteille x ja y pätee, että (car (cons x y)) palauttaa arvon x. Käytä tarkasteluissa korvausmallin (substitution model) mukaista perustelua. Määrittele vastaava proseduuri cdr. (6p)

(6p)

Paperille 2:

Oletetaan, että olemme evaluoineet seuraavat Esp-

lausekkeet

(define (appena x y)

(if ((null? x)

(cons (car x) (appena (cdr x) y))))

(define (last x)

(if (nul]? (cdr x))

(last (cdr x))))

(define (appena! x y)

(set- cdr! (last x) y)

(define x '(a b c))

(define y '(al b1 cl))

(define z (appena y x))

(define s (appena! y x))

Piirrä "laatikko ja osoitin - kaavio", josta ilmenevät s:n, z:n, y:n ja x:n arvot.

(6p)

Paperille 3:

4. Toteuta luvun 4.1 metakirkulaariseen tulkkiin erikoismuoto (infix exp), jonka

argumentti exp on ns. täysin sulutettu infix- auseke, joka käyttää Scheme-

operaattoreita

ja muuttujia. Täysin sulutettu intix- muotoinen lauseke on jokin muodoista

(QUOTE <expr>)

(<tstot> <op> <tstot,> ... ) missä <number> on mikä tahansa luku, <variable> mikä tahansa muuttuja, <expr> mikä tahansa (prefix- muotoinen) Scheme- lauseke <op> mikä tahansa Schemeoperaattori, sekä <tstot>, <tstot,>, ... mitä tahansa, mahdollisesti erilaisia täysin sulutettuja inEx- lausekkeita. Viimeisen muodon on tarkoitus olla merkitykseltään sauna kain (<op> <tstot> <tstot ~ > . . . ) tavallisessa Schemessä. Tavoitteena on sallia mm. aritmeettisten lausekkeiden kirjoittaminen Scheme- ohjelmassa hivenen lähempinä näiden "tavallista" ulkoasua. Peru ratkaisusi! (6p)

5. Kuinka monta kertaa ja millä ensimmäisellä argumentilla kulloinkin luvun 4.1 mela

sirkulaarisen tulkin proseduuria eval kutsutaan, kun tulkilla evaluoidaan lauseke:

(begin (define (appena L1 L2)

(if (null? L1)

(cons (car L1) (appena (cdr L1) L2))))

(appena `(a) `()))