6.001 Recitation – April 18, 2003

RI: Konrad Tollmar

• Streams

• Concurrency

1. Create Infinite Streams

From lecture:

(define (cons-stream x (y lazy-memo))

(cons x y))

(define stream-car car)

(define stream-cdr cdr)

(define (stream-interval a b)

(if (> a b)

the-empty-stream

(cons-stream a (stream-interval (+ a 1) b))))

(define (stream-ref s n)

(if (= n 0)

(stream-car s)

(stream-ref (stream-cdr s) (- n 1))))

(define (stream-filter pred stream)

(cond ((stream-null? stream) the-empty-stream)

((pred (stream-car stream))

(cons-stream (stream-car stream)

(stream-filter pred

(stream-cdr stream))))

(else (stream-filter pred (stream-cdr stream)))))

(define (add-streams s1 s2)

(cons-stream (+ (stream-car s1) (stream-car s2))

(add-streams (stream-cdr s1) (stream-cdr s2)))))

Show how we could create a stream of integers in an alternative way,
given the stream ones (1 1 1 1 ….) and the procedure add-streams.

2. Define Fibonacci numbers with stream.

Write a procedure, (fibs), that returns a stream of Fibonacci numbers. The Fibonacci series goes

(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...)

It starts with two 1's, then each successive value is the sum of the previous two.

Hint: use add-streams and F(n) = F(n-2) + F(n-1)

3. Concurrency

From lecture:

(define (make-serializer)

(let ((mutex (make-mutex)))

(lambda (p)

(define (serialized-p . args)

(mutex 'acquire)

(let ((val (apply p args)))

(mutex 'release)

val))

serialized-p)))

(define (make-mutex)

(let ((cell (list false)))

(define (the-mutex m)

(cond ((eq? m 'acquire)

(if (test-and-set! cell)

(the-mutex 'acquire)))

((eq? m 'release) (clear! cell))))

the-mutex))

(define (clear! cell)

(set-car! cell false))

(define (test-and-set! cell)

(if (car cell)

true

(begin (set-car! cell true)

false)))

;; MIT Scheme

(define (test-and-set! cell)

(without-interrupts

(lambda ()

(if (car cell)

true

(begin (set-car! cell true)

false)))))

Give all possible values of x that can result from execution the following:

(define x 10)

(define p (lambda () (set! x (* x x))))

(define q (lambda () (set! x (* x x x))))

(parallel-execute p q)

And if we instead use serialized procedures:

(define x 10)

(define s (make-serializer))

(define p (s (lambda () (set! x (* x x)))))

(define q (s (lambda () (set! x (* x x x)))))

(parallel-execute p q)

2. Bank Accounts

(define (make-account-and-serializer balance)

(define (deposit amount)

(set! balance (+ balance amount))

balance)

(let ((balance-serializer (make-serializer)))

(define (dispatch m)

(cond ((eq? m 'deposit) (balance-serializer deposit))

((eq? m 'balance) balance)

((eq? m 'serializer) balance-serializer)

(else (error "Don’t know how to do: " m))))

dispatch))

(define (get-balance acct)

(acct ‘balance))

(define (deposit acct amount)

(let ((d (acct ‘deposite)))

(d amount)))

(define a (make-account 100))

A/ Make deposite safe by use serialize

(define (deposit acct amount)

(let ((s (acct ‘serialize)))

(d (acct ‘deposite)))

<< insert some code here >>

))

B/ Do we need to redefine get-balance in the same way?

3. Exchange Accounts

(define a (make-account 100))

(define b (make-account 50))

(exchange a b)

(get-balance a) -> 50

(get-balance b) -> 100

(define (exchange a1 a2)

(let ((diff (- (a1 ‘balance) (a2 ‘balance)))

((a1 ‘deposite (- diff))

((a2 ‘deposite) diff)))

A/ Create a serialized exchange

(define (serialized-exchange account1 account2)

(let ((serializer1 (account1 'serializer))

(serializer2 (account2 'serializer)))

<< insert your code here >>

))

This could however create deadlocks, lets instead mark each serialized procedure with an id so we know in which order to execute them.

(define s (make-serializer))

(define t (make-serializer))

(s proc) -> serialized proc

(s ‘id) -> 1

(t ‘id) -> 2

B/ Used labeled serializer to implement a “safer” exchange

(define (serialized-exchange account1 account2)

(let ((serializer1 (account1 'serializer))

(serializer2 (account2 'serializer)))

<< insert your code here >>

))