6.001 Recitation – April 18, 2003

RI: Konrad Tollmar

• Streams

• Concurrency

1. Create Infinite Streams

(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.

(define seq (stream-interval 1 10))

(define (integers-starting-from n)

(cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

(define ones (cons-streams 1 ones))

(define integers

(cons-stream 1

(add-streams ones integers))

(define (divisible? x y) (= (remainder x y) 0))

(define no-sevens

(stream-filter (lambda (x) (not (divisible? x 7)))

integers))

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

F(n) = F(n-2) + F(n-1)

(define fibs

(cons-stream

0

(cons-stream

1

(add-stream (stream-cdr fibs) fibs))))

3. Concurrency

(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)))

;;from footnote -- 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 "Unknown request -- MAKE-ACCOUNT"

m))))

dispatch))

(define (get-balance acct)

(acct ‘balance))

(define (deposit acct amount)

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

(d amount)))

(define a (make-account 100))

Make deposite safe by use serialize

(define (deposit acct amount)

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

(d (acct ‘deposite)))

((s d) amount)))

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

è No, because balance is always a reasonable value.

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)))

(define (serialized-exchange account1 account2)

(let ((serializer1 (account1 'serializer))

(serializer2 (account2 'serializer)))

((serializer1 (serializer2 exchange))

account1

account2)))

(define s (make-serializer))

(define t (make-serializer))

(s proc) -> serialized proc

(s ‘id) -> 1

(t ‘id) -> 2

(define (serialized-exchange account1 account2)

(let ((serializer1 (account1 'serializer))

(serializer2 (account2 'serializer)))

((if (< (serializer1 ‘id) (serializer2 ‘id))

(serializer1 (serializer2 exchange))

(serializer2 (serializer1 exchange))

account1 account2)

))