Principles of Programming Languages — Homework 18

Fun with Streams

Due by class time Tuesday, December 3

Review the Ruse definitions that we wrote today in class for creating infinite lists (streams).

Download interpreter-with-zcons-macro.scm and new-environment-representation.scm, which is our Ruse interpreter with support for infinite streams (infinite lazy lists), and assign18.txt, which is written in Ruse (hence the .txt file extension), and use them as your starting point for these exercises. You do not need to modify the interpreter at all, just add your new Ruse definitions to assign18.txt. To execute the code in assign18.txt, open interpreter-with-zcons-macro.scm in DrRacket and click Run, then type (start) to start the Ruse interpreter, and then (load "assign18.txt") to load in your stream definitions: 

  > (start)
  Welcome to the SLC Ruse Interpreter

  ==> (load "assign18.txt")
  ==>

  1. Define the Ruse function (scale factor s), which takes a number factor and an infinite stream of numbers s and returns a new stream with all values multiplied by factor. For example:

    ==> (get-first 15 (scale 10 nats))
(0 10 20 30 40 50 60 70 80 90 100 110 120 130 140)

  2. Define the following five infinite streams in Ruse:

    evens: The stream of even numbers beginning with 0
    ==> (get-first 15 evens)
    (0 2 4 6 8 10 12 14 16 18 20 22 24 26 28)

    odds: The stream of odd numbers beginning with 1
    ==> (get-first 15 odds)
    (1 3 5 7 9 11 13 15 17 19 21 23 25 27 29)

    odd-reciprocals: The stream of odd reciprocals
    ==> (get-first 15 odd-reciprocals)
    (1 1/3 1/5 1/7 1/9 1/11 1/13 1/15 1/17 1/19 1/21 1/23 1/25 1/27 1/29)

    alternating-signs: The stream with alternating values of 1 and -1
    ==> (get-first 15 alternating-signs)
    (1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1)

    terms: The stream of odd reciprocals with alternating signs
    ==> (get-first 15 terms)
    (1 -1/3 1/5 -1/7 1/9 -1/11 1/13 -1/15 1/17 -1/19 1/21 -1/23 1/25 -1/27 1/29)

  3. Define the Ruse function (remove-multiples n s), which takes an infinite stream of numbers s and returns a new stream with all multiples of n removed. Hint: if x is a multiple of n, then the remainder (x % n) will be zero. For example:

    ==> (get-first 20 (remove-multiples 3 nats))
(1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29)

==> (get-first 20 (remove-multiples 5 nats))
(1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19 21 22 23 24)

    What happens if you remove all multiples of 1 from nats?

  4. Define the Ruse function (partial-sums s), which takes an infinite stream s of numbers (n0  n1  n2  n3  n4 ...) and returns a stream of their partial sums: (n0  n0+n1  n0+n1+n2  n0+n1+n2+n3 ...). For example, the partial sums of nats would be (0  0+1  0+1+2  0+1+2+3 ...)

    Hint: the partial sums of the stream (zcdr s) would be (n1  n1+n2  n1+n2+n3  n1+n2+n3+n4 ...). If you then add n0 to each element of this stream using zmap, you will get almost the right answer — just missing the initial n0 element at the front, which can be attached using zcons.

    ==> (get-first 15 (partial-sums nats))
(0 1 3 6 10 15 21 28 36 45 55 66 78 91 105)

==> (get-first 15 (partial-sums odds))
(1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)

==> (get-first 8 (partial-sums terms))
(1 2/3 13/15 76/105 263/315 2578/3465 36979/45045 33976/45045)

Turning in Your Homework