Tentamenvoorbeeld II

Vraag 1

Welke van de volgende Scheme termen is in feite syntactic sugar:

a.

define

b.

let

c.

+

d.

lambda

Vraag 2

Gegeven onderstaand programma:

(define (proc x)
  (cond ((= x 0) 1)
        ((= x 1) 2)
        ((= x 2) 3)
        ((= x 3) 4)
        (else (proc (- x 3)))))

Hoe vaak wordt tijdens de evaluatie van (proc 5) de primitieve procedure '=' uitgevoerd?

a.

2

b.

7

c.

5

d.

8

Vraag 3

Welke van onderstaande termen zijn allen special forms:

a.

define, let, cond, >

b.

define, lambda, if, +

c.

define, set!, cons, cond

d.

set!, cond, if, lambda

Vraag 4

Gegeven de volgende Scheme procedure.

(define (proc x)
   (cond ((= x 1) 0)
         ((< x 1) (+ 1 (proc (+ x 1))))
         (else    (- 1 (proc (- x 1))))))

Wat is het resultaat van (proc 4)?

a.

0.

b.

1.

c.

-1.

d.

4.

Vraag 5

Als Scheme een combinatie behandelt als ``special form'', wat is dan karakteristiek voor de behandeling van de combinatie? (Kies het meest nauwkeurige antwoord.)

a.

De subexpressies van de combinatie worden direkt, zonder evaluatie, doorgegeven aan de procedure.

b.

Iedere ``special form'' heeft een eigen set evaluatieregels, die wordt toegepast op de combinatie.

c.

De evaluatie van de ``special form'' krijgt voorrang boven de evaluatie van andere combinaties.

d.

De ``special form'' wordt niet geëvalueerd.

Vraag 6

Gegeven de volgende procedure.

(define (a b c d)
   (if (= c 0)
       d
       (a b (- c 1) (+ d (b c)))))

Wat zal het resultaat zijn van de volgende combinatie?

(a (lambda (x) (+ x 1)) 3 0)

a.

0.

b.

3.

c.

6.

d.

9.

Vraag 7

Een programmeur schrijft onderstaand programma om uit te testen of de boolean procedure ``and'' wel of geen special form is:

(define counter 0)

(and (sequence (set! counter (+ counter 2))
               #f )
     (sequence (set! counter (+ counter 3))
               #t))

Na evaluatie van dit programma observeert de programmeur de uitkomst van de ``and expressie'' en de waarde van de counter. Welke van onderstaande uitspraken is het meest nauwkeurig:

a.

De uitkomst van de ``and expressie'' is #f dus, is ``and'' geen special form.

b.

Dit programma is niet geschikt om te testen of ``and'' een special form is.

c.

De waarde van counter is 2 dus is ``and'' een special form.

d.

Omdat zowel de uitkomst van de ``and expressie'' #f is en de waarde van counter 2 is ``and'' een special form.

Vraag 8

Gegeven de volgende Scheme expressie:

(sequence 3 (set! counter 4))

Welke van onderstaande uitspraken is het meest nauwkeurig:

a.

De expressie heeft als resultaat 3 en de counter wordt 4.

b.

De expressie heeft als resultaat 4 en de counter wordt 4.

c.

De counter wordt 4 en het resultaat van de expressie is niet goed gedefinieerd.

d.

De counter wordt 4 en het resultaat van de expressie is #t.

Vraag 9

Theo beweert dat ``if'' als primitive niet in Scheme behoeft te worden opgenomen, immers ``if'' kan als volgt geimplementeerd worden:

(define (if a b c)
  (cond (a b)
        (else c)))

Hij test dit als volgt:

==> (if (= 1 1) 3 4)
3
==> (if (= 1 2) 3 4)
4

en concludeert vervolgens uit de antwoorden dat de gegeven definitie van if correct is.

Alyssa vermoedt dat ``if'' niet op bovenstaande wijze kan worden hergedefiniëerd; volgens haar kan wel in ieder programma, en voor willekeurige expressies ``a'' ``b'' en ``c'' de expressie (if a b c) vervangen worden door
(cond (a b) (else c)) zonder dat de semantiek van het programma wijzigt.

Welke van onderstaande uitspraken is het meest nauwkeurig:

a.

De beweringen van Theo en Alyssa zijn beide correct.

b.

De bewering van Theo is niet correct, die van Alyssa wel.

c.

Beide beweringen zijn niet correct

d.

De bewering van Theo is correct, die van Alyssa niet.

Vraag 10

Gegeven de volgende twee definities:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

Na invoer van deze definities evalueren we (test 0 (p)). Welke van de volgende uitspraken is het meest correct:

a.

De evaluator retourneert als resultaat 0.

b.

De evaluator blijft constant bezig met evaluatie, indien normal order evaluation gebruikt wordt.

c.

De evaluator retourneert als resultaat 0, indien normal order evaluation gebruikt wordt.

d.

De evaluator retourneert met een foutmelding.

Vraag 11

Gegeven de volgende Scheme procedure:

(define proc
  (lambda (x y)
     (cond ((= x y) x)
           ((< x y) (proc (+ x 1) y))
           (else (proc x (+ y 1))))))

Welke van de volgende namen correspondeert het beste met de definitie van proc?

a.

min

b.

max

c.

abs

d.

add

Vraag 12

Gegeven de volgende Scheme procedure:

(define (proc a b)
  (if (= a 0)
      b
      (proc (- a 1) (* a b))))

Geef aan wat de ruimte en tijd complexiteiten zijn wanneer we (proc n m) evalueren; n en m zijn positieve gehele getallen.

ruimte tijd

complexiteit complexiteit

a. 0(1) 0(n)

b. 0(n) 0(n)

c. 0(m) 0(n)

d. 0(1) 0(m)

Vraag 13

Gegeven 3 Scheme procedures, ``mapcar'' ``odd?'' en ``sum-list'' die als volgt gebruikt kunnen worden:

==> (mapcar (lambda (x) (* x x)) '(1 2 3 4))
(1 4 9 16)

==> (odd? 1)
#t

==> (sum-list '(1 2 3 4))
10

Welke expressie berekent m.b.v. deze procedures de som van de oneven elementen van een lijst l1 ?

a.

(sum-list (mapcar odd? l1))

b.

(mapcar odd? (sum-list l1))

c.

(sum-list (mapcar 'odd? l1))

d.

Geen van de vorige antwoorden a, b, of c.

Vraag 14

Gegeven de volgende lijst definities:

(define lijst-1 '(1 (2 (3)) 4 (5)))
(define lijst-2 (cddr lijst-1))
(define lijst-3 (cadr lijst-1))

Wat zal na invoer van deze definities de waarden van lijst-2 en lijst-3 zijn?

lijst-2 lijst-3

a. (4 (5)) (2 (3))

b. (4 (5)) 2

c. ((3)) (2 (3))

d. ((3)) 2

Vraag 15

Gegeven de volgende Scheme code:

(define lijst-1 '(1 (2 (3)) 4 (5)))
(define lijst-2 (cddr lijst-1))
(set-cdr! lijst-2 '(4 5))

Wat zal na evaluatie van deze code de waarden van lijst-1 en lijst-2 zijn:

lijst-1 lijst-2

a. (1 (2 (3)) 4 4 5) (4 4 5)

b. (1 (2 (3)) 4 (5)) (4 4 5)

c. (1 (2 (3)) 4 4 5) ((4 5))

d. (1 (2 (3)) 4 (5)) ((4 5))

Vraag 16

Gegeven de volgende twee stukjes Scheme code, A en B:

A: (let ((x c1)
         (y c2))
     c3)

B: ((lambda (x y) c3) c1 c2)

Welke van de volgende uitspraken over A en B is het meest nauwkeurig?

a.

A en B zijn even efficiënt, en resulteren in gelijk resultaten.

b.

B is minder efficiënt dan A, maar de resultaten zijn altijd gelijk.

c.

A en B zijn even efficiënt, doch geven niet altijd dezelfde resultaten.

d.

B is minder efficiënt dan A; bovendien geven A en B niet altijd dezelfde resultaten.

Vraag 17

Gegeven de volgende 3 Scheme expressies, A, B en C:

A: '(1 2 3 4)
B: (quote 1 2 3 4)
C: (list 1 2 3 4)

Welke van de volgende uitspraken omtrent de evaluatie en het resultaat van A, B en C is het meest correct:

a.

A, B en C zijn even efficiënt, en resulteren in gelijk resultaten.

b.

A en B zijn even efficiënt; verder resulteren A, B en C in gelijk resultaten.

c.

A, B en C resulteren in gelijk resultaten, doch C is efficiënter dan A en B, daar C direct een lijst genereert.

d.

A, B, en C zijn niet gelijk daar één van de drie in een foutmelding resulteert.

Vraag 18

In een environment waarin x is gekoppeld (bound) aan 10, wat is dan het resultaat van de volgende Scheme expressie?

(let ((x 1) (y x))
     (let ((z (+ x y)))
          (+ z z)))

a.

20

b.

22

c.

4

d.

geen van antwoorden a, b, en c.

Vraag 19

Gegeven de volgende Scheme code:

(define (cube x) (* x x x))

(define (cube-list x)
  (if (null? x)
      '()
      .........I............. ))

Wat moet er op I worden ingevuld zodat de procedure ``cube-list'' toegepast op een lijst van getallen een lijst met de 3-e macht van deze getallen retourneert.

a.

(cons (cube (car x)) (cube-list (cdr x)))

b.

(cons (cube x) (cube-list (cdr x)))

c.

(list (cube (car x)) (cube-list (cdr x)))

d.

(list (cube x) (cube-list (cdr x)))

Vraag 20

Wat is het resultaat van de volgende Scheme expressie:

(cons (cons 1 2) (cons 3 4))

a.

((1.2) 3.4)

b.

(1 2 3.4)

c.

(1.2 3.4)

d.

((1.2) (3.4))

Vraag 21

Gegeven een procedure ``reverse-list'' welke toegepast op een lijst een nieuwe lijst retourneert waarin de elementen achterstevoren staan, dus

==> (reverse-list '(1 (2 3) 4))
(4 (2 3) 1)

Onderstaande definitie van reverse is nog niet compleet; geef aan wat er voor ``I'' moet worden ingevuld.

(define (reverse-list x)
  (if (null? x)
      '()
      .............I............... ))

a.

(append (reverse-list (cdr x)) (list (car x)))

b.

(cons (reverse-list (cdr x)) (list (car x)))

c.

(append (reverse-list (cdr x)) (car x))

d.

(cons (reverse-list (cdr x)) (car x))

Vraag 22

Een programmeur schrijft de volgende Scheme code:

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

(define (proc f x)
  (define (proc-iter lst answer)
    (if (null? lst)
        answer
        (proc-iter (cdr lst)
              (cons (f (car lst))
                    answer))))
  (proc-iter x '()))

Wat zal de uitvoer zijn bij evaluatie van (proc square '(1 2 3 4)) ?

a.

(1 4 9 16)

b.

(1 2 4 8)

c.

(1 4 9.16)

d.

(16 9 4 1)

Vraag 23

Gegeven de volgende Scheme procedures:

(define mycons
   (lambda (x y)
      (lambda (msg)
         (cond ((eq? msg 'mycar) x)
               ((eq? msg 'mycdr) y)
               (else (error "unknown method -- MYCONS" msg))))))

(define mycar
   (lambda (pair-proc)
      (pair-proc 'mycar)))

(define mycdr
   (lambda (pair-proc)
      (pair-proc 'mycdr)))

(define c (mycons 1 2))

Welke van de volgende uitspraken is het meest correct:

a.

c is een data pair

b.

(mycar c) evalueert tot 2

c.

(c mycar) evalueert tot 1

d.

(c 'mycdr) evalueert tot 2

Vraag 24

Gegeven de volgende Scheme procedures:

(define mycons
   (lambda (x y)
      (lambda (msg)
         (cond ((eq? msg 'mycar) x)
               ((eq? msg 'mycdr) y)
               (else (error "unknown method -- MYCONS" msg))))))

(define mycar
   (lambda (pair-proc)
      (pair-proc 'mycar)))

(define mycdr
   (lambda (pair-proc)
      (pair-proc 'mycdr)))

(define c (mycons 1 2))

Hoe wordt deze stijl van programmeren genoemd?

a.

Data-directed programming

b.

Message-passing programming

c.

Manifest-type programming

d.

Geen van de antwoorden a, b, en c.

Vraag 25

Welke van de volgende uitspraken over data directed programming is het meest correct?

a.

Data directed programming voorkomt dat ieder object type informatie nodig heeft.

b.

Data directed programming is een directe afgeleide van message passing.

c.

Data directed programming zorgt ervoor dat de implementatie van de generic interface procedures type onafhankelijk wordt.

d.

Data directed programming is nodig om objecten op meerdere manieren te kunnen representeren.

Vraag 26

Gegeven een Scheme procedure replace welke in een lijst van symbolen voorkomens van een bepaald symbool kan vervangen door een andere set symbolen; bijvoorbeeld in de lijst (a (a b) a b) kunnen we alle voorkomens van ``a'' vervangen door ``1 2 3'' door middel van:

==> (replace 'a '(1 2 3) '(a (a b) a b))
(1 2 3 (1 2 3 b) 1 2 3 b)

De implementatie van replace is hieronder gedeeltelijk gegeven:

(define (replace old new longlist)
  (cond ((atom? longlist) longlist)
        ((eq? (car longlist) old) (append new (replace old new (cdr longlist))))
        (else ....................I...................... )))

Wat moet er voor I worden ingevuld:

a.

(append (replace old new (car longlist)) (replace old new (cdr longlist)))

b.

(append (car longlist) (replace old new (cdr longlist)))

c.

(cons (replace old new (car longlist)) (replace old new (cdr longlist)))

d.

(cons (car longlist) (replace old new (cdr longlist)))

Vraag 27

Gegeven de definitie van een object obj:

(define obj
  (let ((a '()))
    (lambda (b) (sequence
                  (set! a (cons b a))
                  a))))

Wat is het resultaat van evaluatie van de volgende expressie:

(list (obj 1) (obj 2) (obj 3))

Gegeven is dat de Scheme evaluator de operanden van rechts naar links evalueert (dus de meeste rechtse operand eerst; de meeste Scheme evaluatoren doen het andersom!):

a.

((1) (2 1) (3 2 1))

b.

(1 2 3)

c.

((1 2 3) (2 3) (3))

d.

(1 2 3 2 3 3)

Vraag 28

Gegeven de volgende Scheme code:

(define (obj-create a)
  (define (hulp b)
    (set! a (+ a b))
    a)
   hulp)

(define obj1 (obj-create 0))
(define obj2 (obj-create 0))

De environment die ontstaat na evaluatie van de code is voor een deel getekend in onderstaande figuur:

Welke van onderstaande uitspraken over pointers a, b, c, I en II, is het meest correct:

a.

a wijst naar de body van hulp; I en II wijzen naar E2.

b.

b wijst naar de body van hulp; I en II wijzen naar E2.

c.

c wijst naar de body van hulp; I wijst naar E2; II wijst naar E3.

d.

a wijst naar de body van hulp; I wijst naar E2; II wijst naar E3.

Vraag 29

Gegeven de volgende Scheme code:

(define lst1 '(1 2 3))
(define lst2 '(1 2 3))
(define lst3 lst2)
(set-cdr! lst2 lst1)

Wat zijn de waarden van lst1, lst2 en lst3 na evaluatie van deze code:

lst1 lst2 lst3

a. (1 2 3) (1 1 2 3) (1 1 2 3)

b. (1 1 2 3) (1 1 2 3) (1 1 2 3)

c. (1 2 3) (1 1 2 3) (1 2 3)

d. (1 2 3) (1 (1 2 3)) (1 (1 2 3))

Vraag 30

Gegeven de volgende Scheme code:

(define (obj-create a)
  (define (hulp b)
    (set! a (+ a b))
    a)
   hulp)

(define obj1 (obj-create 0))

(obj1 5)

De environment die ontstaat tijdens evaluatie van de laatste expressie, (obj1 5), is voor een deel getekend in onderstaande figuur:

Waarheen wijzen pointers I en II:

a.

I wijst naar E2; II wijst naar E1.

b.

I wijst naar E1; II wijst naar E2.

c.

I wijst naar E2; II wijst naar E2.

d.

I wijst naar E1; II wijst naar E1.