Homework 10

Template

You can copy the template for this homework by typing in your terminal:

cp ~cs61as/autograder/templates/hw10.scm .

You can also download it by clicking here.

Exercise 1

Read SICP 3.5.1, then answer the following:

  1. What is the type of the value of (delay (+ 1 27))?
  2. What is the type of the value of (force (delay (+ 1 27)))?

Exercise 2

Evaluating this expression produces an error:

(stream-cdr (stream-cdr (cons-stream 1 '(2 3))))

Explain why.

Exercise 3

Consider the following:

(define (enumerate-interval low high) 
  (if (> low high) 
      '() 
      (cons low (enumerate-interval (+ low 1) high)) ) )

(define (stream-enumerate-interval low high) 
  (if (> low high) 
      the-empty-stream 
      (cons-stream low (stream-enumerate-interval (+ low 1) high)) ) )

What's the difference between the following two expressions?

(delay (enumerate-interval 1 3))
(stream-enumerate-interval 1 3)

Exercise 4

An unsolved problem in number theory concerns the following algorithm for creating a sequence of positive integers [mathjaxinline]s_1, s_2, \ldots[/mathjaxinline] where [mathjaxinline]s_1[/mathjaxinline] is some positive integer and, for all [mathjaxinline]n > 1[/mathjaxinline],

  • if [mathjaxinline]s_n[/mathjaxinline] is odd, then [mathjaxinline]s_{n+1} = 3s_n+1[/mathjaxinline];
  • if [mathjaxinline]s_n[/mathjaxinline] is even, then [mathjaxinline]s_{n+1} = s_n \div 2[/mathjaxinline].

No matter what starting value [mathjaxinline]s_1[/mathjaxinline] is chosen, the sequence (called a hailstone sequence) always seems to end with the repeating values 1, 4, 2, 1, 4, 2, 1, .... However, it is not known if this is always the case.

  1. Write a procedure num-seq that, given a positive integer n as argument, returns the hailstone sequence for n. For example, (num-seq 7) should return the stream representing the sequence 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

  2. Write a procedure seq-length that, given a stream produced by num-seq, returns the number of values that occur in the sequence up to and including the first 1. For example, (seq-length (num-seq 7)) should return 17. You should assume that there is a 1 somewhere in the sequence.

Exercise 5

It's that time of the homework—SICP!

Complete the following: 3.50, 3.51, 3.52, 3.53, 3.54, 3.55, 3.56, 3.64, 3.66, 3.68.

Exercise 6

Write and test two functions to manipulate nonnegative proper fractions.

The first function, fract-stream, will take as its argument a list of two nonnegative integers, the numerator and the denominator, in which the numerator is less than the denominator. It will return an infinite stream of decimal digits representing the decimal expansion of the fraction.

The second function, approximation, will take two arguments: a fraction stream and a nonnegative integer numdigits. It will return a list (not a stream) containing the first numdigits digits of the decimal expansion.

Some guidelines:

  • (fract-stream '(1 7)) should return the stream representing the decimal
  • expansion of 1/7, which is 0.142857142857142857...
  • (stream-car (fract-stream '(1 7))) should return 1.
  • (stream-car (stream-cdr (stream-cdr (fract-stream '(1 7))))) should return
  • 2.
  • (approximation (fract-stream '(1 7)) 4) should return (1 4 2 8).
  • (approximation (fract-stream '(1 2)) 4) should return (5 0 0 0).

Submit Your Homework!

For instructions, see this guide. It covers basic terminal commands and assignment submission.

If you have any trouble submitting, do not hesitate to ask a TA!