define-record and
variant-case in SCM, evaluate: (require 'struct).
NOTE: The code in interp.scm provides a working interpreters with all necessary code. You should only modify this code in your solution.
Questions:We can do this by modeling the store not as a collection of cells but as a finite function. The domain of the finite function is some arbitrary set of addresses (say the nonnegative integers) thatr represents locations or cells, and its range is the set of expressed values.
Mutation of a location in the store is then modeled by extending this finite function to associate the location with the new value. This new association supersedes any earlier associations for the same cell.
In order for the new store to be used in subsequent evaluations, it is passed as an additional argument to all interpreter procedured that might need it (eval-exp, eval-rands, apply-proc etc). For example:
(define (eval-exp exp env store)
(variant-case exp
(varref (var) (apply-store store (apply-env env var)))
...))
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. The trickiest
interpreter procedure to modify is eval-rands. It can no longer just use
map. Instead, it must evaluate the operands in some specific order, with
the store resulting from each evaluation being used in the next
evaluation. We can evaluate the operands from left to right and accumulate
the partial answers in reverse order.
(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-result (eval-exp (car rands) env store)))
(loop (cdr rands)
(cons (interp-result->value first-result) ans)
(interp-result->store first-result)))))))
(loop rands '() store)))
Finish modifying the interpreter. Be sure to define the store ADT. Then
rewrite eval-rands so that it does not use the accumulator variable ans.
var
specification in Pascal to specify parameters passed by reference). The
following syntax is to be used to this end:
<exp> ::= <varref> varref (var)
| <number> lit (datum)
| (if <exp> <exp> <exp>) if (test-exp then-exp else-exp)
| (proc ({<par-decl>}*) <exp>) proc (formals body)
| (<exp> {<exp>}*) app (rator rands)
| (:= <var> <exp>) varassign (var exp)
| (begin {<exp>}+) begin (exps)
| (let <decls> <exp>) let (decls body)
| (letrec <decls> <exp>) letrec (decls body)
<decls> ::= ({<decl>}*)
<decl> ::= (<var> <exp>) decl (var exp)
<par-decl> ::= <var> val-param (var)
| (:ref <var>) ref-param (var)
| (:need <var>) need-param (var)
The following is an example of how a procedure can be defined and called:
(let ((a 1) (b 2))
(begin
((proc (x (:ref y) (:need z))
(begin (:= x 1) (:= y 2) (:= z 3)))
a b (+ a b))
(write a b)))
For this language, we define the following value structure:
Expressed Value = Number + Procedure L-value = Cell(Expressed Value) Denoted value = Expressed Value + L-value + Memo Memo = Cell(Thunk + L-value) Thunk = () -> L-valueImplement the interpreter and write two programs in this language that demonstrate:
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.