----------------------------------------- Tutorial notes #11 for 5/7 or 5/8/2007 TA: Stephen McCamant Email: smcc@mit.edu Location: 36-113A or 36-115 http://people.csail.mit.edu/smcc/6.001-sp07/ ----------------------------------------- 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 extensions. 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 problem. 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 code. Questions about project 5? ----------------------------------------- Extending m-eval: "eval" "eval" is sort of like the opposite of quote: it causes an additional level of evaluation: (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 primitive: (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) (eval-sequence (macro-body macro) (extend-environment (macro-parameters macro) args (macro-environment macro))))Could you use macros and/or eval to make streams?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 too?;; 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) (stream-append (map-streams (lambda (a) (list (stream-car s1) a)) s2) (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)) (interleave (map-streams (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 million.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) (else (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)))) (else (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)))))