Higher-Order Programming » Lab Sessions

Session 7 (Solutions)

Assistant: Steven Keuchel (steven.keuchel@vub.be)

Section 2: Scheme Objects

Exercise 1: The Flip Procedure

Part 1:

(define state 0) (define (flip) (set! state (modulo (+ state 1) 2)) state)

Part 2:

(define (make-flip) (define state 0) (define (flip) (set! state (modulo (+ state 1) 2)) state) flip)

Part 3:

Every call of make-flip produces a new lexical scope where a new state variable exists. Applying the flip procedure from this scope will result in it only modifying the state variable in that scope.

Exercise 5: A Turnstile

(define (make-turnstile) (define counter 0) (define (increment how-many) (set! counter (+ counter how-many))) (define (query) counter) (define (dispatch m) (cond ((eq? m 'query) query) ((eq? m 'increment) increment))) dispatch) (define a (make-turnstile)) (define b (make-turnstile)) ((a 'increment) 1) ((b 'increment) 5) (display ((a 'query))) (newline) (display ((b 'query))) (newline)

The turnstile is similar to that of the previous exercise. However, in this solution, there are multiple procedures that are created in the scope created by applying make-turnstile. It has 4 fields: counter, increment (a procedure object with scope), query (also a procedure object with scope), and dispatch (and also a procedure object with scope). All these procedures refer to the same lexical environment: thus the dispatch procedure has access to the the other closures.

Exercise 6: Function Profiling

(define (make-monitored f) (define counter 0) (lambda (x) (cond ((eq? x 'how-many-calls?) counter) ((eq? x 'reset-count!) (set! counter 0)) (else (set! counter (+ counter 1)) (f x)))))

Fibonacci:

(define (fib n) (cond ((= n 0) 1) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) (define m-fib (make-monitored fib)) (m-fib 5) (m-fib 'how-many-calls?)

(m-fib 'how-many-calls?) returns 1. However, we would expect more since the fib procedure is called multiple times recursively. A solution is to overwrite the definition of fib...

(set! fib (make-monitored fib)) (fib 5) (fib 'how-many-calls?)

(m-fib 'how-many-calls?) now returns 15, which is the expected result.

An alternative solution is to turn an open recursive generator into a monitored function

(define (open-fib rec n) (cond ((= n 0) 1) ((= n 1) 1) (else (+ (rec (- n 1)) (rec (- n 2)))))) (define (make-monitored-fixpoint g) (define counter 0) (define (fun x) (cond ((eq? x 'how-many-calls?) counter) ((eq? x 'reset-count!) (set! counter 0)) (else (set! counter (+ counter 1)) (g fun x)))) fun) (define fib (make-monitored-fixpoint open-fib)) (fib 5) (fib 'how-many-calls?)