(interleave-stream stream1 stream2)
> (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 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:
<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 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.
(constant-optimize abstract-syntax-tree)
that performs this transformation (it returns a new abstract-syntax-tree).
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.
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) ...)