Streams

interleave-stream

> (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 () (filter-stream pred? (stream-cdr
s)))))
           (else (filter-stream pred? (stream-cdr s)))))
> (define (display-head s n) 
     (if (> n 0) 
        (let ((head (stream-car s)))
          (display head) (display " ")
          (display-head (stream-cdr s) (- n 1)))))

> (define i1 (filter-stream even? (integers 0)))
> (display-head (interleave-stream 
               (filter-stream even? (integers 0))
               (filter-stream (lambda (n) (>= n 10)) 
                              (integers 0)))
              6)
0 10 2 11 4 12 

merge-stream

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

Interpreter with Store and Constant Optimization

<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)
<decls> ::= ({<decl>}*)
<decl>  ::= (<var> <exp>)                   decl (var exp)

Denoted value = Cell(Expressed Value) + Expressed Value

Parser

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

Write a function: (constant-optimize abstract-syntax-tree) that performs this transformation (it returns a new abstract-syntax-tree).

Interpreter with Explicit Store

Write the function: (eval-exp exp env store) and the supporting function (apply-proc proc rands store).

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 store) 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 rewrite this function so that it does not use the accumulator ans 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)))

Interpreter in Java or C++

We are not interested in parsing issues, therefore we will only define constructors for expressions and use the following style to enter expressions to be evaluated (at compile-time only):

C++ example:

Interp.h:
class Expression ....;
class VarrefExpression : Expression ....;
class LitExpression : Expression ...;
...

Test.C:

main() {
  LitExpression e1(1), e2(2);      // Expressions: 1, 2.
  AppExpression a1("+", e1, e2);   // Expression: (+ 1 2)
  AppExpression a2("*", a1, e2);   // Expression: (* (+ 1 2) 2)

  cout << e1.eval() << nl;
  cout << e2.eval() << nl;
  cout << a2.eval() << nl;
}

Implement the interpreter for the language defined by the following BNF using the same evaluation rules as defined in class:

<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)