Tietojenkäsittelyopin laboratorio Tentti 17.08.1995

Peltonen, Saikkonen, Syrjänen, Tiusanen 1

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

* Tik-76.101 Ohjelmoinnin pitkä peruskurssi

* tentti 17.08.1995

* sukunimi, etunimet

* koulutusohjelma, opintokidan numero

1 . Tutkitaan kahden kokonaislukuargumentin, x:n ja y:n kokonaislukuarvoisia funktioita, jotka kasvavat aidon monotonisesti x:n suhteen, kun y säilyy vakiona ja vähenevät aidon monotonisesti y:n suhteen, kun x säilyy vakiona. Ohjelmoi yleinen proseduuri "level", joka annetulle funktiolle f laskee neliömäiseltä alueelta 0..N, 0..N, niiden kokonaislukupisteiden lukumäärän, joilla f saa annetun kokonaislukuarvon v. Tehtävä tulee ratkaista vain proseduuri-abstraktiota käyttäen. Ratkaisusi tulisi olla vaativuudeltaan 0(N).

2 . Oletetaan, että eräitä geometrisia olioita esitetään Lisp-olioina, joilla on

tarkoituksenmukaiset ominaisuudet. Esim.

Olio Ominaisuus Arvo

y tyyppi ympyra

sade 4

N tyyppi nelio

sivu(npituus) 2

K tyyppi kolmio

kanta 3

korkeus 2

Määrittele kullekin ym. tyypille (ympyra, nelio, kolmio) konstruktori ja tarvittavat

selektorit sekä geneerinen funktion pinta-ala, joka sovellettuna olioon, joka on

jotain yo. tyypeistä (esim. Y, K tai N), palauttaa ko. olion pinta-alan. Voit olettaa, että

tarvitsemasi apuproseduurit (attach-type, type, contents, ... ) ovat käytettävissä.

3 . Kirjoita proseduuri

(make-moving-average n)

joka palauttaa olion, joka laskee liukuvaa keskiarvoa. Oliolle on käytettävissä seuraavat toiminnot:

reset

Nollaa olion tilan. Palauttaa arvon NIL.

add <luku>

Lisää uuden luvun liukuvaan keskiarvoon. Palauttaa sarnan kuin "average" (ks. alla). average

Palauttaa keskiarvon viimeisistä n:stä luvusta (n proseduurin "make-moving-average" parametri), jotka on lisätty add-proseduurilla. Jos yhtään lukua ei ole lisätty, palauttaa NIL. Jos on lisätty alle n lukua, palauttaa niiden keskiarvon.

Esimerkki:

(define x (make-moving-average )))

(x 'average)

--> NIL

((x 'add) 1 0)

--> 10

(x 'average)

--> 10

(( x 'add) 12)

-->11 ;(10+12)/2

(x 'add) 5)

--> 9 ; (10+12+5)13

(x 'add) 1)

--> 6 ; (12+5+1)13

(x 'add) 15)

--> 7 ; (5+1+15)13

(x 'reset)

-->NIL

((x 'add) 7)

-->7

4 . (a) Piirrä selkeä kuva siitä, mikä on tutkittujen proseduurien ympäristöjen muodostama rakenne lausekkeen (sum 3) suorituksen jälkeen kirjassa annetussa Schemen metasirkulaarisessa evaluaattorissa, kun sum on määritelty evaluaattorille lausekkeilla

(define (sum-aux i result)

(cond ((= 0 i) result)

(else (sum-aux (- i 1) (+ result 1)))))

(define (sum n) (sum-aux n 0))

Selitä kuvaasi! (Oleta, että roskan kerääjä ei ole ollut aktiivinen.) (4p)

(b) Anna perusteita dynaamisen sidonnan käytöstä (vastakohtana staattiselle), puolesta

ja vastaan. (2p)

5. Anna ja perustele lyhyesti (ei-rekursiivinen) rekisterikonetoteutus seuraavalle funktiolle

(sivu 98 kirjassa): (Sp)

(define (countatoms x)

(cond ((null? x) 0)

((atom? x) 1)

(else (+ (countatoms (car x))

(countatoms (cdr x))))))