Tutorial notes #11 for 5/7 or 5/8/2007

TA:       Stephen McCamant
Email:    smcc@mit.edu
Location: 36-113A or 36-115
Project 4 turn back

Though this project was a lot of work,
most people who finished it did pretty
well. I also saw a number of inventive
and technically sophisticated

Questions about the project?

Project 5

The final project is closer in length to
some of the earlier projects, but it's
pretty conceptually difficult, so don't
get too complacent. Think carefully
about the right way to approach each

We're asking you to submit one file,
which should be a modified version of
eval.scm. Be sure to clearly mark all
the places where you changed or added

Questions about project 5?

Extending m-eval: "eval"

"eval" is sort of like the opposite of
quote: it causes an additional level of

(let ((x 7))
  (let ((code (list 'list 'x 'x)))
    (eval code)))
-> (7 7)

(Note this is slightly different from
the one in DrScheme). Can eval be a
primitive procedure, or does it need to
be a special form?

The DrScheme version that always uses the global environment can be a

(list 'eval (lambda (exp) (m-eval exp the-global-environment)))

For my version, though, you need to know that the current environment
is, which isn't passed to primitives. So you need a special form with an
implementation like

(define (eval-eval exp env)
   (m-eval (m-eval (eval-arg exp) env) env))

Note that in either case, there are two levels of m-eval going on.
Extending m-eval: macros

"Macros" are like functions that operate
before their arguments are evaluated.
How could you create a macro constructor
"mu" similar to "lambda"?

The data abstraction is mainly the same, the only thing different
is the way it will be called.

(define (mu? exp) (tagged-list? exp 'mu))
(define (mu-parameters exp) (cadr exp))
(define (mu-body exp) (cddr exp))
(define (make-mu parms body) (cons 'mu (cons parms body)))

(define (make-macro parameters body env)
  (list 'macro parameters body env))
(define (macro? proc)
  (tagged-list? proc 'macro))
(define (macro-parameters proc) (second proc))
(define (macro-body proc) (third proc))
(define (macro-environment proc) (fourth proc))

;; in m-eval:
        ((application? exp)
         (let ((operator-val (m-eval (operator exp) env)))
           (if (macro? operator-val)
               (m-eval (macro-apply operator-val (operands exp)) env)
               (m-apply operator-val (list-of-values (operands exp) env)))))

(define (macro-apply macro args)
   (macro-body macro)
   (extend-environment (macro-parameters macro)
                       (macro-environment macro))))

Could you use macros and/or eval to make

Yes, this kind of macro is enough, just like what we did to make
macros in DrScheme. The simplest implementation:

(define cons-stream
        (mu (ar dr)
            (list 'cons ar (list 'lambda '() dr))))
(define stream-car car)
(define (stream-cdr str) ((cdr str)))

You could improve the above by adding memoization or by implementing
stream pairs as message-interpreting procedures to be defensive about
mistakes from mixing lists and streams.

Stream operations: integers, pairs

The "integers" stream we defined in
class is actually only the positive
integers. How would you make a stream
that included negative integers and zero

;; Most straightforward:
(define (interleave s1 s2)
  (cons-stream (stream-car s1)
               (cons-stream (stream-car s2)
                            (interleave (stream-cdr s1)
                                        (stream-cdr s2)))))
(define all-integers
  (cons-stream 0 (interleave integers (scale-stream -1 integers))))

;; Similar to the way we did "integers":
(define (repeating-stream lst)
  (define (helper tail)
    (if (null? tail)
        (helper lst)
        (cons-stream (car tail) (helper (cdr tail)))))
  (helper lst))
(define all-integers2
  (cons-stream 0
     (cons-stream 1
        (add-streams all-integers2
                     (repeating-stream '(-1 1))))))

;; Algebraic style:
(define (repeat-stream n)
  (cons-stream n (repeat-stream n)))
(define (power-stream n)
  (cons-stream 1 (map-streams * (power-stream n) (repeat-stream n))))
(define (sums-stream str)
  (define (helper sum str)
    (cons-stream sum
                 (helper (+ sum (stream-car str))
                         (stream-cdr str))))
  (helper 0 str))
(define all-integers3
  (sums-stream (map-streams * (power-stream -1) integers)))

Now, suppose we want to a stream of
all the two-element lists of positive
integers, or more generally, pairs from
any infinite stream.

Louis suggests the following definition:

(define (louis-pairs s1 s2)
    (lambda (a) (list (stream-car s1) a))
   (louis-pairs (stream-cdr s1) s2)))

Unfortunately, there are a couple of
problems with this.

Problem 1: it generates the stream (1 1) (1 2) (1 3) (1 4) ... and never
gets to pairs whose first element is larger than 1. This can be fixed by
replacing the stream-append with "interleave" defined above.

Problem 2: actually, it causes an infinite loop. The recursive call to
louis-pairs isn't inside a cons-stream, so it recurses immediately and
never terminates. To fix this, you need to add a call to cons-stream and
adjust the map accordingly to avoid duplicates:

(define (louis-pairs s1 s2)
  (cons-stream (list (stream-car s1) (stream-car s2))
                 (lambda (a) (list (stream-car s1) a))
                 (stream-cdr s2))
                (louis-pairs (stream-cdr s1) s2))))
Stream operations: 2-3-5

Let's construct a stream of all the
positive integers whose only prime
factors are 2, 3, and 5.

First, there's an straightforward way to
do it with stream-filter.

(define (remove-factors f n)
  (cond ((= (remainder n f) 0)
         (remove-factors f (/ n f)))
        (else n)))

(define (is-235 n)
  (= (remove-factors 2 (remove-factors 3 (remove-factors 5 n))) 1))

(define str235-1
  (stream-filter is-235 integers))

Analyze the efficiency of the filtering
approach in big-Omega terms.

Not so good. The number of such numbers less than n is only about
O(log^3(n)), but the filtering approach needs to test all n numbers.
For instance, there are only about 500 such numbers less than a

For another approach, consider a
recursive definition of the set of
integers we're interested in.

1 is such a number. If k is such a number, so are 2k, 3k, and 5k; and
all such numbers are formed in this way. That means that the set of
numbers is the same if we replace it with a union of 1 and copies of
itself scaled by 2, 3, and 5. To apply this insight to get a stream of
the numbers in the right order, we need to implement a merging operation
on streams, and always keep our intermediate streams ordered.

(define (merge s1 s2)
  (cond ((null-stream? s1) s2)
        ((null-stream? s2) s1)
         (let ((s1car (stream-car s1)) (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                  (cons-stream s1car (merge (stream-cdr s1)
                                            (stream-cdr s2)))))))))

(define str235-2
  (cons-stream 1 (merge (scale-stream 2 str235-2)
                        (merge (scale-stream 3 str235-2)
                               (scale-stream 5 str235-2)))))