Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 3 - Spring 2000 - Michael Elhadad

Streams & Interpreters

Problems for Tue 18 Apr 2000


Two functions related to streams: 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
           (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)))
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:

  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.

Interpreter with Store and Constant Optimization

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


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

Write an interpreter with an explicit model of the store, that does not use assignment in the meta-language and that supports continuations.

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)))
In the CPS transformation, you can assume that reverse, cons, all record access functions and all store and env members are primitives.

Interpreter in Java or C++

The meta-language we use to describe languages influences our way of thinking about them. Just to get out of the Scheme mood imposed since the beginning of the semester, and to demonstrate the generality of the constructs studied so far, we will now construct the same interpreter as demonstrated in class but using an Object-oriented language instead of Scheme. You can use Java (probably the easiest because it provides garbage collection) 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:

class Expression ....;
class VarrefExpression : Expression ....;
class LitExpression : Expression ...;


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)