2 of 42

Announcements

Midterm 2 is (mostly) graded

You will receive scores through email tonight

Homework 9 due today, 8/3
Homework 10 due Friday, 8/7
Maps composition revision due today, 8/3
Project 4 due next Monday, 8/10

New extra credit (Q23). Requires downloading some new files
Office hours next Monday (8/10) from 4 - 7PM in Wozniak Lounge

Project 4 contest due Tuesday, 8/11 (optional)

Scheme art contest (see galleries from previous semesters)

No love for slower-paced section

Yulin's discussion will return to being normal-paced
This week's topics are tough; go to lab and discussion!

Missing items: please email Albert or Robert

A black jacket and a black notebook (left at the midterm)
An adapter that says "Tanium" (left at the potluck)
Amazon mouse (in lab, a long time ago)

3 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

Today is about making modifications to our interpreter

Also, how to do extra credit on the project

4 of 42

Number of call frames: Python

def factorial(n):

if n == 0:

return 1

else:

return n*factorial(n-1)

Global

factorial

func factorial(x)

f1: factorial

return value

f1: factorial

return value

f1: factorial

return value

O(n) frames

What if n is 1000? 2000? 10,000?

Maximum recursion depth exceeded

5 of 42

Number of call frames: Python

def factorial(n):

total = 1

while n > 0:

n, total = n - 1, n * total

return total

Global

factorial

func factorial(x)

f1: factorial

return value

total

O(1) frames

What if n is 1000? 2000? 10,000?

No problem!

6 of 42

Number of call frames: Scheme

def factorial(n):

total = 1

while n > 0:

n, total = n - 1, n * total

return total

(define (factorial n)

(if (= n 0)

(* n (factorial (- n 1)))))

def factorial(n):

if n == 0:

return 1

else:

return n*factorial(n-1)

Python

Scheme

Python

Scheme

What kind of language doesn't have a while loop?!?!?!?!?!

7 of 42

An aside: Converting iteration to recursion (review)

(define (factorial n)

(define (helper n total)

(if (= n 0)

total

(helper (- n 1) (* n total))))

(helper n 1)

)

def factorial(n):

total = 1

while n > 0:

n, total = n - 1, n * total

return total

Stopping condition

Updated variables

Updated values

Initial values

8 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

9 of 42

Tail recursion

(define (factorial n)

(if (= n 0)

(* n (factorial (- n 1)) ) ))

(define (helper n total)

(if (= n 0)

total

(helper (- n 1) (* n total) ) ))

Tail recursion: a function whose recursive call is a tail call

Tail call: a function call that is the last expression evaluated in a function (i.e. in a tail context)

Tail recursive: last evaluated expression is the recursive call

Not tail recursive: the last function call is *, not the recursive call

10 of 42

Number of call frames: Regular recursion

Global

factorial

func factorial(x)

f1: factorial

return value

f1: factorial

return value

f1: factorial

return value

O(n) frames

(define (factorial n)

(if (= n 0)

(* n (factorial (- n 1)))))

11 of 42

Number of call frames: Tail recursion

(define (helper n total)

(if (= n 0)

total

(helper (- n 1)

(* n total))))

(helper 2 1)

Global

helper

func helper(x)

f1: helper

return value

total

O(1) frames

f2: helper

return value

total

f3: helper

return value

total

Tail call optimization

12 of 42

Tail recursion: Is it iteration or recursion?

(define (helper n total)

(if (= n 0)

total

(helper (- n 1) (* n total))))

Recursive syntax

The code is written using recursive calls

Iterative procedure

The computation described is the same as iterative factorial in Python

13 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

14 of 42

Example: Length of a list

Implement (length lst):

lst is a well-formed list

Returns the number of elements in lst
Make it tail recursive!

(define (length lst)

'YOUR-CODE-HERE

)

15 of 42

Example: Length of a list

How would you write this iteratively in Python?

Keep a running total (start at 0)
Move one link at a time, incrementing total
When we run out of links, return total

def length(lst):

total = 0

while lst is not Link.empty:

total = total + 1

lst = lst.rest

return total

16 of 42

Example: Length of a list

(define (length lst)

(define (helper total lst)

)

def length(lst):

total = 0

while lst is not Link.empty:

total = total + 1

lst = lst.rest

return total

What variables are we updating in the loop?

total and lst

17 of 42

Example: Length of a list

(define (length lst)

(define (helper total lst)

(if (null? lst)

total

)

def length(lst):

total = 0

while lst is not Link.empty:

total = total + 1

lst = lst.rest

return total

When do we stop the loop?

When lst is empty
We return total

18 of 42

Example: Length of a list

(define (length lst)

(define (helper total lst)

(if (null? lst)

total

(helper (+ total 1) (cdr lst))

)

def length(lst):

total = 0

while lst is not Link.empty:

total = total + 1

lst = lst.rest

return total

In the loop, how do we update the variables?

total is incremented
move to the rest of the lst

Make a recursive call

19 of 42

Example: Length of a list

(define (length lst)

(define (helper total lst)

(if (null? lst)

total

(helper (+ total 1) (cdr lst))

)

(helper 0 lst)

)

def length(lst):

total = 0

while lst is not Link.empty:

total = total + 1

lst = lst.rest

return total

What are the initial values?

lst is just lst
total is 0

20 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

21 of 42

Naive scheme_eval

def scheme_eval(exp, env):

...

return scheme_apply(procedure, args, env)

def scheme_apply(procedure, args, env):

...

new_env = make_call_frame(procedure, env)

return eval_all(procedure.body, new_env)

f1: factorial

(define (helper n total)

(if (= n 0)

total

(factorial (- n 1) (* total n))))

scheme_eval

scheme_apply

scheme_eval

scheme_apply

f2: factorial

scheme_eval

...

22 of 42

Implementing tail call optimization

def scheme_optimized_eval(exp, env, tail):

if tail:

# Return Evaluating. Don't call scheme_apply

else:

result = Evaluating(exp, env)

while exp isinstance(result, Evaluating):

...

result = scheme_apply(procedure, args, env)

env = result.env

def scheme_apply(procedure, args, env):

...

new_env = make_call_frame(procedure, env)

return eval_all(procedure.body, new_env)

f1: factorial

scheme_eval

scheme_apply

scheme_eval

f2: factorial

23 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

24 of 42

Lazy evaluation

scm> (ints 1)

maximum recursion depth exceeded

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)

Scheme doesn't have iterators. How about a list?

Second argument to cons is always evaluated

Can represent large or infinite sequences

25 of 42

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

26 of 42

Streams

scm> (define s (cons-stream 1 (cons-stream 2 nil)))

scm> s

(1 . #[promise (not forced)])

scm> (car s)

Stream: (linked) list whose rest is lazily evaluated

A promise to compute

scm>

I don't need the rest of this list right now. Can you compute it for me later?

Sure, I promise to compute it right after I finish watching House of Cards.

27 of 42

Streams

scm> (define s (cons-stream 1 (cons-stream 2 nil)))

scm> s

(1 . #[promise (not forced)])

scm> (cdr s)

#[promise (not forced)]

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

scm>

I want the cdr of the list now.

Just one more episode. I'm almost done with season 2.

28 of 42

Streams

scm> (define s (cons-stream 1 (cons-stream 2 nil)))

scm> s

(1 . #[promise (not forced)])

scm> (stream-cdr s)

(2 . #[promise (not forced)])

scm> (stream-cdr (stream-cdr s))

()

stream-cdr forces Scheme to compute the rest

scm>

stream-cdr !

Fine! Here's your stupid list.

29 of 42

Streams

scm> (stream-cdr s)

(2 . #[promise (not forced)])

scm> (define s (cons-stream 1 (cons-stream 2 nil)))

scm> (cdr s)

#[promise (not forced)]

Remember, a stream is just a regular Scheme pair whose second element is a promise

scm> (stream-cdr (stream-cdr s))

()

Promise:

(cons-stream 2 nil)

Promise:

(cons-stream 2 nil)

Promise:

nil

Promise:

nil

30 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

31 of 42

Promises: delay

scm> (print 5)

scm> (delay (print 5))

#[promise (not forced)]

Promise: an object that delays evaluation of an expression

The delay special form creates promises

(print 5) is not evaluated yet

(print 5) is immediately evaluated

Promise:

(print 5)

32 of 42

Promises: force

scm> (define x (delay (print 5)))

scm> x

#[promise (not forced)]

The delay special form creates promises
The force procedure evaluates the expression inside the promise

scm> (force x)

okay

scm> x

#[promise (forced)]

Promise:

(print 5)

Promise:

(print 5)

okay

Evaluates (print 5)

(print 5) is not evaluated yet

33 of 42

Promises

scm> (define s (cons 1 (delay nil))))

scm> s

(1 . #[promise (not forced)])

scm> (define s (cons-stream 1 nil)))

scm> s

(1 . #[promise (not forced)])

scm> (stream-cdr s)

()

scm> (force (cdr s))

()

Promise:

nil

Promise:

nil

cons-stream and stream-cdr are syntactic sugar. Achieve the same effect with delay and force

34 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

35 of 42

Examples: map-stream

Implement (map-stream fn s):

fn is a one-argument function
s is a stream

Returns a new stream with fn applied to elements of s

(define (map-stream fn s)

'YOUR-CODE-HERE

)

36 of 42

Examples: map-stream

How would you implement map-list?

(define (map-list fn s)

(if (null? s)

nil

(cons (fn (car s))

(map-list fn (cdr s)))))

How about map-stream?

(define (map-stream fn s)

(if (null? s)

nil

(cons-stream (fn (car s))

(map-list fn (stream-cdr s)))))

What happens if you change this to cons?

37 of 42

Examples: stream-to-list

Implement (stream-to-list s num-elements):

s is a stream
num-elements is a non-negative integer

Returns a Scheme list containing the first num-elements elements of s

(define (stream-to-list s num-elements)

'YOUR-CODE-HERE

)

scm> (stream-to-list (ints 1) 10)

(1 2 3 4 5 6 7 8 9 10)

38 of 42

Examples: stream-to-list

Step 1: Base case(s).
Simplest input for s:

If s is nil: no elements, so return nil

Simplest input for num-elements

If num-elements is 0: return nil (a list containing 0 elements)

(define (stream-to-list s num-elements)

(if (or (null? s) (= num-elements 0))

nil

)

39 of 42

Examples: stream-to-list

Step 2: Recursive call
How to reduce inputs?

(stream-cdr s) computes the rest of the stream
(- num-elements 1) reduces the number of desired elements

What does (stream-to-list (stream-cdr s) (- num-elements 1)) do?

Gets the first (- num-elements 1) elements of the rest of s

(define (stream-to-list s num-elements)

(if (or (null? s) (= num-elements 0))

nil

)

40 of 42

Examples: stream-to-list

Step 3: Use the recursive call
Add (car s) to the front of the list returned by the recursive call

How do you create a list in Scheme? cons

(define (stream-to-list s num-elements)

(if (or (null? s) (= num-elements 0))

nil

(cons (car s)

(stream-to-list (stream-cdr s)

(- num-elements 1))))

)

41 of 42

Tail Recursion and Streams

Tail recursion

Recursion vs. iteration
Tail recursive functions
Example
Implementing tail call optimization

Streams

Promises
Examples
Implementing streams and promises

42 of 42

Implementing streams and promises

Extra credit question 23 in Project 4
Implement a Promise class
Implement do_delay_form

Handles the delay special form
Just returns a Promise

Implement do_cons_stream_form

Syntactic sugar
(cons first (delay second))

class Promise:

...

def do_delay_form(exp, env):

...

def do_cons_stream_form(exp, env):

...

>>> str( Promise( Pair('+', Pair(4, Pair(3, nil))) , env) )

#[promise (not forced)]

>>> do_delay_form( Pair(Pair('+', Pair(4, Pair(3, nil))), nil) , env)

Promise(Pair('+', Pair(4, Pair(3, nil))), env)

>>> do_cons_stream_form( Pair(1, Pair(2, nil)) , env)

Pair(1, Promise(Pair(2, nil), env))