南京大学：《计算机程序的构造和解释 Structure and Interpretation of Computer Programs》课程教学资源（PPT课件讲稿）22-Streams

Lecture 22-Streams

Lecture 22 - Streams

Streams

Streams

Lazy Evaluation in Scheme

Lazy Evaluation in Scheme

Lazy evaluation In Python,iterators and def ints(first): while True: generators allowed for lazy yield first evaluation first +=1 >>>s ints(1) Can represent large or >>next(s) infinite sequences 1 >>next(s) 2 Scheme doesn't have iterators. (define (ints first) (cons first (ints (first 1))) How about a list? Second argument to cons scm>(ints 1) is always evaluated maximum recursion depth exceeded

scm> (ints 1) maximum recursion depth exceeded Lazy evaluation ● In Python, iterators and generators allowed for lazy evaluation def ints(first): while True: yield first first += 1 (define (ints first) (cons first (ints (+ first 1))) >>> s = ints(1) >>> next(s) 1 >>> next(s) 2 ● Scheme doesn't have iterators. How about a list? Second argument to cons is always evaluated Can represent large or infinite sequences

Streams Instead of iterators, Scheme uses streams (define (ints first) (define (ints first) (cons first (cons-stream first (ints (first 1))) (ints (first 1))) scm>(ints 1) scm>(ints 1) maximum recursion depth exceeded (1.#[promise (not forced)]) Lazy evaluation,just like iterators in Python

Streams Instead of iterators, Scheme uses streams (define (ints first) (cons first (ints (+ first 1))) scm> (ints 1) maximum recursion depth exceeded (define (ints first) (cons-stream first (ints (+ first 1))) scm> (ints 1) (1 . #[promise (not forced)]) Lazy evaluation, just like iterators in Python

Streams scm>(define s (cons-stream 1 (cons-stream 2 nil))) s scm>s Stream:(linked)list whose rest (1.#[promise (not forced)]) is lazily evaluated scm>(car s) 1 O A promise to compute I don't need the rest of this list right now.Can you Sure,I promise to compute it compute it for me later? right after I finish watching Stranger Things. scm>

scm> (define s (cons-stream 1 (cons-stream 2 nil))) s scm> s (1 . #[promise (not forced)]) scm> (car s) 1 Streams ● Stream: (linked) list whose rest is lazily evaluated ○ A promise to compute I don't need the rest of this list right now. Can you compute it for me later? scm> Sure, I promise to compute it right after I finish watching Stranger Things

Streams scm>(define s (cons-stream 1 (cons-stream 2 nil))) s scm>s cdr returns the rest of a list (1.#[promise (not forced)]) O For normal lists,the rest is scm>(cdr s) #[promise (not forced)] another list O The rest of a stream is a promise to compute the list I want the cdr of the list now. Just one more episode.I'm almost done with season 3. scm>

scm> (define s (cons-stream 1 (cons-stream 2 nil))) s scm> s (1 . #[promise (not forced)]) scm> (cdr s) #[promise (not forced)] Streams ● cdr returns the rest of a list ○ For normal lists, the rest is another list ○ The rest of a stream is a promise to compute the list I want the cdr of the list now. scm> Just one more episode. I'm almost done with season 3

Streams scm>(define s (cons-stream 1 (cons-stream 2 nil))) s scm>s (1.#[promise (not forced)]) cdr-stream forces Scheme to scm>(cdr-stream s) compute the rest (2.#[promise (not forced)]) scm>(cdr-stream (cdr-stream s)) () cdr-stream！ Fine!Here's your stupid list. scm>

scm> (define s (cons-stream 1 (cons-stream 2 nil))) s scm> s (1 . #[promise (not forced)]) scm> (cdr-stream s) (2 . #[promise (not forced)]) scm> (cdr-stream (cdr-stream s)) () Streams ● cdr-stream forces Scheme to compute the rest cdr-stream ! scm> Fine! Here's your stupid list

Streams Remember,a stream is just a regular Scheme pair whose second element is a promise scm>(define s (cons-stream 1 (cons-stream 2 nil))) scm>(cdr s) #[promise (not forced)] scm>(cdr-stream s) (2 #[promise (not forced)]) scm>(cdr-stream (cdr-stream s)) IF A PROMISE CONTAINS () AN EMPTY LIST Promise: Promise: (cons-stream 2 nil) nil 1 2 IS IT AN EMPTY PROMISE?

scm> (cdr-stream s) (2 . #[promise (not forced)]) scm> (define s (cons-stream 1 (cons-stream 2 nil))) s scm> (cdr s) #[promise (not forced)] Streams Remember, a stream is just a regular Scheme pair whose second element is a promise 1 Promise: (cons-stream 2 nil) scm> (cdr-stream (cdr-stream s)) () 2 Promise: nil

Streams ● Streams O Promises O Examples O Streams Exam Problems

Streams ● Streams ○ Promises ○ Examples ○ Streams Exam Problems