HW Assignment 2 - Spring 2001 - Michael Elhadad

- Streams
- Interpreter with Store and Constant Optimization
- Interpreter in Java or C++
- Tailform predicate

`interleave-stream`

and
`merge-streams`

.
`(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 () (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 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:

- S begins with 1
- The elements of (scale-stream 2 S) are also elements of S
- The elements of (scale-stream 3 S) are also elements of S
- The elements of (scale-stream 5 S) are also elements of S
- These are all the elements of S

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

`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?`

.

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

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 indicates how the explicit handling of the store must start
for the case of `eval-rands`

.

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

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; }In your design, all instances of variant-case in the Scheme implementation will be replaced with virtual functions.

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)