Streams & Interpreters

Problems for Wed 17 Feb 1999

Streams

Two functions related to streams: interleave-stream and merge-streams.

interleave-stream

(interleave-stream stream1 stream2)
The procedure must return one stream that returns alternatively one element of stream1 and then one element of stream2. For example:
> (define (integers n) (make-stream n (lambda () (integers (+ n 1)))))
> (define (filter-stream pred? s) 
     (cond ((stream-null? s) the-null-stream)
           ((pred? (stream-car s))
            (make-stream (stream-car s)
                         (lambda () (stream-filter pred? (stream-cdr s)))))
           (else (stream-filter pred? (stream-cdr s)))))
> (define (display-head s n) 
     (if (> n 0) 
        (let ((head (stream-car s)))
          (display head) (display " ")
          (display-head s (- n 1)))))
> (display-head (interleave-stream (filter-stream even? (integers 0))
                                   (filter-stream (lambda () (> n 10)) 
                                                  (integers 0)))
                6)
0 10 2 11 4 12 

merge-stream

(merge-stream stream1 stream2) The procedure combines two ordered streams into one ordered stream eliminating repetitions. Use this procedure to generate in an efficient way, in ascending order and with no repetitions, all positive integers with no prime factors other than 2, 3 and 5. If you call this stream S, note that S is defined by the following facts:
  1. S begins with 1
  2. The elements of (scale-stream 2 S) are also elements of S
  3. The elements of (scale-stream 3 S) are also elements of S
  4. The elements of (scale-stream 5 S) are also elements of S
  5. These are all the elements of S
where (scale-stream n S) is a procedure which returns the stream of elements n*i for each i generated by S.

The Complete Interpreter

Consider the language defined by the following BNF:
<exp>         ::= <varref>                  varref (var)
               |  <number>                  lit (datum)
               |  (if <exp> <exp> <exp>)    if (test-exp then-exp else-exp)
               |  (proc ({<var>}*) <exp>)   proc (formals body)
               |  (<prim-op> {<exp>}*)      prim-app (prim-rator rands)
               |  (<exp> {<exp>}*)          app (rator rands)
               |  (:= <var> <exp>)          varassign (var exp)
               |  (begin {<exp>}+)          begin (exps)
               |  (let <decls> <exp>)       let (decls body)
               |  (letmutable <decls> <exp>)    letmutable (decls body)
               |  (letrec <decls> <exp>)    letrec (decls body)
               |  (letcont <var> <exp>)    letcont (var body)
<decls> ::= ({<decl>}*)
<decl>  ::= (<var> <exp>)                   decl (var exp)
In this language, we allow both mutable and immutable (that is, variable and constant) variable bindings in the interpreter:
Denoted value = Cell(Expressed Value) + Expressed Value
Letmutable defines bindings that can be modified. All the other bindings are defined as constant bindings. It is a runtime error to perform an assignment on a constant binding.

Parser

Write a complete parser for this BNF. The function must be called parse and receive a Scheme expression as input and return the abstract syntax tree of the expression according to the BNF or raise an error if the expression is not acceptable. Note that primitives are recognized by the parser and a primitive application is syntactically different from a non-primitive application. The following list of primitives is to be recognized: +, -, *, /, car, cdr, cons, null?.

Constant Optimization

Process the output of the parser to identify when each binding needs to be mutable and when it can be immutable. That is, replace all occurrences of letmutable to let when it can be proved that the binding does not need to be mutable.
Write a function: (constant-optimize abstract-syntax-tree) that performs this transformation (it returns a new abstract-syntax-tree).

Interpreter with Explicit Store and Continuation

Write an interpreter with an explicit model of the store, that does not use assignment in the meta-language and that supports continuations. The interpreter must be written in CPS style and not use first-class functions. That is, it must use the "concrete style" for continuations with an appropriate definition of the continuation ADT.

Write the function: (eval-exp exp env store k) and the supporting functions (apply-continuation k v), (apply-proc proc rands store k).

To support the store explicitly, you must define a store ADT: (make-empty-store), (apply-store store address) and (extend-store store address value). You may need to define as well (new-address) to return a new unused address when needed.

Every procedure that might modify the store will return not just its usual value, but a pair consisting of the value and a new store. Note that you cannot use map anymore. Operands must be evaluated in a fixed order (use left-to-right).

The following code which is not in CPS indicates how the explicit handling of the store must start for the case of eval-rands. You must adapt this to a CPS style and integrate it in your code:

(define-record interp-result (value store))

(define (eval-rands rands env store)
  (letrec ((loop (lambda (rands ans store)
                   (if (null? rands)
                       (make-interp-result (reverse ans) store)
                       (let ((first (eval-exp (car rands) env store)))
                         (loop (cdr rands)
                               (cons (interp-result->value first) ans)
                               (interp-result->store first)))))))
    (loop rands '() store)))
In the CPS transformation, you can assume that reverse, cons, all record access functions and all store and env members are primitives.

Coroutines in Scheme

Write the function makecoroutine in Scheme using call-with-current-continuation.

(define (makecoroutine proc) ...)

(define resume ...)
(define co1 (makecoroutine (lambda (v) ...))
(define co2 (makecoroutine (lambda (v) ...))

(resume co1 1)
Use this definition to implement the samefringe example in Scheme as discussed in class:
(define (samefringe tree1 tree2) ...)