• View
• Edit
• History
• Print

PS8

Home Assignments Lecture Blog Resources Project Discussion Group

91.301 Organization of Programming Languages
Prof. F. Martin

Out: April 8, 2009
Due: April 15, 2009

Problem Set 8: Streams and Final Project Exploration

Overview

This problem set introduces streams, which are like lists but where the cdr of a stream is a “promise of delayed evaluation.”

Also, you will explore the PLT Scheme world and look for some interesting libraries you may wish to use in your final project.

Reading

Before doing this problem set, read the following material:

• SICP 3.5, Streams

Implementation

Use Module language in Dr. Scheme 4.x for this problem set.

• Use this streams starter code for completing the work.
• This starter code has even more useful stuff in it: Attach:stream-examples.ss

Problems

First, some problems on the environment model and mutation. Read Section 3, 3.1, and 3.2.

Problem 1: Exercise 3.1 on pp. 224. After writing and testing the code, draw the environment diagram that would result from evaluating the three statements in the exercise.

Problem 2: Exercise 3.2 on pp. 224-225. After writing and testing the code, draw the environment diagram that would result from evaluating the three statements in the exercise.

Problem 3: Exercise 3.3 on pp. 225, creating a password-protected bank account.

Problem 4: Exercise 3.4 on pp. 225, modifying it to keep track of incorrect password accesses.

Now, the streams stuff.

Problem 5: Use stream-map (pp. 320 of textbook) to define a procedure called convert-temps that takes a stream of temperatures in Fahrenheit and returns a stream of converted temperatures in Celsius. Recall that to convert Fahrenheit to Celsius, the equation is C = 5/9 * (F-32).

Problem 6: Use stream-filter (pp. 322 of textbook) to define the stream of all integers that are evenly divisible by 2, 3, or 5.

Problem 7: Complete the following alternative definition of the integers stream:

 (define integers (cons-stream 1 (stream-map <??> integers)))

Problem 8: Exercise 3.51 on pp. 325, examining the delayed evaluation by printing results as they are computed.

Problem 9: Exercise 3.52 on pp. 325–326, delayed evaluation while state is changing.

Problem 10: Exercise 3.53 on pp. 330, thinking about how streams defined in terms of themselves operate.

Problem 11: Exercise 3.54 on pp. 331, implementing factorial with mul-streams, analogous to how Fibonacci is done in the text.

Problem 12: Exercise 3.57 on pp. 332, understanding memo-ization as it applies to the Fibonacci computation.

Final Project Exploration

In this exercise, you will play with one more library provided by the PLT Scheme developers.

Start off at the PLT Scheme home page, http://plt-scheme.org/

Then there are two places you can go for library code:

• the Documentation link, taking you here: http://docs.plt-scheme.org/
• the PLaneT link, taking you here: http://planet.plt-scheme.org/ (this is user-contributed code)

To turn in: 2 to 4 pages of interspersed code and narrative explaining what you did.