Question 1

[10 marks] Given the following code:

01| (define (foo n)

02| (define (iter a b c)

03| (cond ((> a b) c)

04| ((= a b) (iter a (+ b 1) c))

05| (else (iter (+ a (- b c))(- b a) (- c 1)))))

06| (if (< n 3)

07| n

08| (iter n (* n n)(* n 2))))

09|

10| (foo 3)

[5 marks] Draw a contour diagram during the evaluation of foo at the beginning of line 8, (before executing the first call to iter).

[5 marks] Draw a contour diagram at the start of line 03 during the second evaluation of iter (ie. before the call to (iter 6 7 5)).

Question 2

[10 marks] Given the following code:

01| (define (f L)

02| (cond ((null? L) '())

03| ((< (car L) 0)(cons (* (g (cdr L)) (car L)) (f (cdr L))))

04| (else (cons (car L)(f (cdr L))))))

05|

06| (define (g L)

07| (cond ((null? L) 0)

08| (else (+ (car L)(- (g (cdr L)))))))

09|

10| (f '(3 -7 4 2))

[5 marks] Draw a contour diagram during the evaluation of g at the beginning of line 8 (before g recurses on itself) using lexical (static) scoping rules.

[5 marks] Draw a contour diagram during the evaluation of g at the beginning of line 8 (before g recurses on itself) using dynamic scoping rules.

Question 3

[10 marks] Given the following code:

01|(define (outer z)

02| (define x 2)

03| (define (in1)

04| (define z (+ 20 x))

05| (in2))

06| (define (in2)

07| (set! z (* z 10))

08| z)

09| in1)

10|

11|(define closure (outer 30))

12|(closure)

[/6 marks] Draw a contour diagram at the start of line 5 (after calling the closure function on line 12, before calling in2 on line 5).

[/1 mark] What is the output of this code? (Using lexical scoping)

[/3 marks] Would this code work using dynamic scope as taught in lecture? If yes, provide the output. If no, explain why not.

Question 4

[20 marks] Define a procedure called make-map that implements an Associative Array (Map ADT) using an object oriented design in Scheme. The make-map procedure should return an object that supports the following operations:

(put! k v) - adds a given key-value pair to the map. Duplicate keys should be replaced.

(get k) â†’ v - returns the value associated with a given key if it is in the map.

(remove! k) - removes a given key (and its associated value) from the map.

(contains? k) â†’ bool - returns true if a given key is in the map, false otherwise.

(empty?) â†’ bool - returns true if there are no elements in the map, false otherwise.

(print) - displays the contents of the map to the user in the format: ((k1 . v1)(k2 . v2)(k3 . v3)...(kn . vn))

Your map object should use lists and/or pairs as the backing data structure.

Return #f for any operation that should return a value but fails.

Documentation & Testing [10 marks]

Documentation

Ensure that your name and student number are in comments at the top of all files.

Document the purpose of each function including its expected inputs (parameters) and output (return).

Testing

You are required to include testing runs of every function in your submission.

The specific tests required depend on the question at hand, but should cover all valid inputs and all possible branches of your code.

The example runs provided in the guidelines above may not be sufficient.

Unless otherwise specified, you may assume inputs supplied are of the correct type.

Fabricated test outputs will result in 0 marks for a question.

For best practices: Comment your testing as to what you are testing and why, giving expected output as well as observed output and explanations for any differences.

Any code files that are not runnable (in DrRacket using R5RS) will result in a mark of 0 for that question.

Ensure that your code is well-formatted and easily readable; a happy TA is a generous TA.

An example submission including documentation and testing can be found here: [login to view URL]

Kemahiran: Scheme

Tentang Majikan:
( 1 ulasan ) ottawa, Canada

ID Projek: #22385707