CMPUT 325 Schedule and Outcomes - 5. Week 3 - Jan 20

CMPUT 325 Schedule and Outcomes

5. Week 3 - Jan 20

5.1 Topics

prefix computation revisted, generalized reduce via foldl and foldr.
special forms like if revisted, procedural truth, and define-syntax-rule
exploring lazy evaluation further, m-delay and m-force
diversion - using state inside closures to implement objects
lazy data structures: streams

5.2 Flipped Work

Use the state encapsulation trick to implment a caching version of delay and force, call them c-delay and c-force. The idea is that the first time c-force is involed it evaluates the expression and caches it's value so that the next time the force just does the lookup. Why is this this call by value?
The object-based example of using a closure to implement an object does not have inheritance. How would you add inheritance to this technique? How about just adding additional methods, since you have complete control over method dispatch?
What would foldl and foldr look like on streams? What is a reasonable interpretation of these operations.
Implement s-prefix, the stream version of prefix-list.
In the sqrt-stream implementation, replace the 1.0 by 1 to cause rational arithmetic to be used. What happens?
Implement streams using the non-caching versions m-delay and m-force and assess how the time and space complexity differs from the caching versions.

Composing streams code/Week03/streams-1.rkt

; here is a function that interleaves two streams and produces a new stream

(define (s-interleave s1 s2)

(if (s-null? s1)

s2

(s-cons (s-first s1)

(s-interleave s2 (s-rest s1)))))

; here we enumerate the integers by interleaving the positive and negative ones

(define integers-bad

(s-interleave naturals (s-map (lambda(x) (- x)) naturals)))

; when you display the first 12 terms of the stream you see it is not quite correct

; fix it

(s-interval-to-list integers 0 11)

Enumerate all the pairs of natural numbers in the following order (0 0) (0 1) (1 0) (0 2) (1 1) (2 0) (0 3) (1 2) (2 1) (3 0) ...

5.3 Sample Solutions to Flipped Work

code/Week03/solutions-1.rkt

#lang racket

(require "stream-base.rkt")

(define (s-prefix op s)

(s-cons (s-first s) (s-map (lambda (e) (op (s-first s) e))

(s-prefix op (s-rest s)))) )

(define (s-foldl op init s)

(if (s-null? s) '()

(let ( [ t (op init (s-first s)) ] )

(s-cons t (s-foldl op t (s-rest s) ) ) ) ) )

5.4 Formative Quiz

Change in plan, the formative quiz will be after the first bit of material from the next week.

5. Week 3 - Jan 20
CMPUT 325 Schedule / Version 2.31 2014-04-04