Environment Passing Interpreters III Local Binding, Procedures
Include tests, such as above, to verify that your interpreter and primitive procedures are working properly.
- interp3-3.scm extends interp3-1.scm (Fig 3.1: A simple interpreter) to support
ifexpressions and boolean valuestrueandfalse.The language interpreted has BNF
Expressed values are those that can be values of expressions.[program] ::= [expression] [expression] ::= [number] | [symbol] | [primitive]() | [primitive]([expression]{, [expression]}*) | if [expression] then [expression] else [expression] | [bool] [primitive] ::= + | - | * | add1 | sub1 | equal? [bool] ::= true | false
Denoted values are those that can be values of variables.Expressed Values = Number + BoolTo obtain inter3-3.scm from interp3-1.scm, we
Denoted Values = Number + Bool
- added
if-expandbool-expto theexpressiondatatype(bool-exp (bval bool?)) (if-exp (test-exp expression?) (true-exp expression?) (false-exp expression?))- added a
booldatatype --(define-datatype bool bool? (true-value) (false-value))- added
equal-primto theprimitivedatatype- added cases clauses to
eval-expressionfor interpretingif-expandbool-exp, gettingmaking use of(define eval-expression (lambda (exp env) (cases expression exp (lit-exp (datum) datum) (bool-exp (bval) bval) (var-exp (id) (apply-env env id)) (primapp-exp (prim rands) (let ((args (eval-rands rands env))) (apply-primitive prim args))) (if-exp (test-exp true-exp false-exp) (if (true-value? (eval-expression test-exp env)) (eval-expression true-exp env) (eval-expression false-exp env))) (else (error 'eval-expression "bad exp ~s" exp)))))(define true-value? (lambda (x) (cases bool x (true-value () #t) (false-value () #f) (else (error 'bool "not a bool" x)))))- added code to
apply-primitiveto interpretequal-prim. This is simplified usingThen the clause interpreting(define bool-value (lambda (x) (if x (true-value) (false-value))))equal-primis just(equal-prim () (bool-value (= (car args) (cadr args))))- added code to parse
#t,#fandiftoparse-expression
- added code to unparse
bool-expandif-exptounparse-expression
- added code to parse
if,truefalsetogrammar-3-1to getgrammar-3-3(expression ("if" expression "then" expression "else" expression) if-exp) (expression (bool) bool-exp) (bool ("true") true-value) (bool ("false") false-value)We can test everything with
For example,(define run-test-all (lambda (string) (let ((parsed (scan&parse string))) (let ((datum (unparse-program parsed))) (newline) (pretty-print string) (display " or")(newline) (pretty-print datum) (display " or")(newline) (pretty-print parsed) (display " => ") (eval-program (parse-program datum))))))has output, in the environment(run-test-all "+(if equal?(x, 10) then v else i, x)")[i = 1, v = 5, x = 10](empty-env),"+(if equal?(x, 10) then v else i, x)" or (+ (if (= x 10) v i) x) or (a-program (primapp-exp (add-prim) ((if-exp (primapp-exp (equal-prim) ((var-exp x) (lit-exp 10))) (var-exp v) (var-exp i)) (var-exp x)))) => 15- Local Variables
The defined language is extended to include BNF
which entails[expression] ::= let {[symbol] = [expression]}+ in expressionExamples of local binding:
- adding
let-expto the grammar --(expression ("let" (arbno id "=" expression) "in" expression) let-exp)- adding
let-exptoexpression(let-exp (ids (list-of symbol?)) (exps (list-of expression?)) (body expression?))- adding to
eval-expression-- to implement lexical scopeThe variables which are both free in body and in ids have values given by the values of the corresponding exps. Lexical addresses, rather than variable names could be used to look up values in the environment.(let-exp (ids exps body) (let ((args (eval-rands exps env))) (eval-expression body (extend-env ids args env))))
- adding to
parse-expression- adding to
unparse-expressionhas output, in the environment(run-test-all "let a = 2 b = 3 in +(*(a, v), *(b, x))")[i = 1, v = 5, x = 10](empty-env),and"let a = 2 b = 3 in +(*(a, v), *(b, x))" or (let ([a 2] [b 3]) (+ (* a v) (* b x))) or (a-program (let-exp (a b) ((lit-exp 2) (lit-exp 3)) (primapp-exp (add-prim) ((primapp-exp (mult-prim) ((var-exp a) (var-exp v))) (primapp-exp (mult-prim) ((var-exp b) (var-exp x))))))) => 40has output,(run-test-all "let x = 2 in print(list(i, v, x, emptylist))")"let x = 2 in print(list(i, v, x, emptylist))" or (let ([x 2]) (print (list i v x emptylist))) or (a-program (let-exp (x) ((lit-exp 2)) (primapp-exp (print-prim) ((primapp-exp (list-prim) ((var-exp i) (var-exp v) (var-exp x) (var-exp emptylist))))))) => (1 5 2 ()) 1- Procedures
The defined language is extended to include BNF for procedure definition and procedure application.
The expressed and denoted values become[expression] ::= proc() [expression] | proc([id]{, [id]}*) [expression] | ([expression] {[expression]}*)Expressed Values = Number + Bool + ProcedureDefined procedure, unlike primitive procedures (whose application has a different character syntax) are first class objects.
Denoted Values = Number + Bool + ProcedureImplementing procedure definition and application entails
Example of procedure definition and application:
- adding
proc-expandapp-expto the grammar(expression ("proc" "(" (separated-list id ",") ")" expression) proc-exp) (expression ("(" expression (arbno expression) ")") app-exp)- adding
proc-expandapp-expto theexpressiondatatype(proc-exp (ids (list-of symbol?)) (body expression?)) (app-exp (rator expression?) (rands (list-of expression?)))- adding
proc-expandapp-exptoeval-expression
The value of a procedure will be aclosure, a data structure which stores the procedure's ids and body, and the environment in which the procedure is evaluated. This will enable implementing lexical scoping semantics.(proc-exp (ids body) (closure ids body env)) (app-exp (rator rands) (let ((proc (eval-expression rator env)) (args (eval-rands rands env))) (apply-procval proc args)))- adding a
procvaldatatype with aclosurevariant and a procedureapply-procvalwhich implements the application of a closure on its arguments.A closure is a run-time data structure that exists when the abstract syntax tree of an expression containing the procedure is being evaluated.(define-datatype procval procval? (closure (ids (list-of symbol?)) (body expression?) (env environment?))) (define apply-procval (lambda (proc args) (cases procval proc (closure (ids body env) (eval-expression body (extend-env ids args env))) (else (error 'procval "Not a procedure ~s" proc)))))
- adding to
parse-expression- adding to
unparse-expressionhas output, in the environment(run-test-all "let sqr = proc(x) *(x, x) in let cub = proc(x) *(x, (sqr x)) in +((sqr v), (cub x))")[i = 1, v = 5, x = 10](empty-env),Here's another example that uses lists."let sqr = proc(x) *(x, x) in let cub = proc(x) *(x, (sqr x)) in +((sqr v), (cub x))" or (let ([sqr (lambda (x) (* x x))]) (let ([cub (lambda (x) (* x (sqr x)))]) (+ (sqr v) (cub x)))) or (a-program (let-exp (sqr) ((proc-exp (x) (primapp-exp (mult-prim) ((var-exp x) (var-exp x))))) (let-exp (cub) ((proc-exp (x) (primapp-exp (mult-prim) ((var-exp x) (app-exp (var-exp sqr) ((var-exp x))))))) (primapp-exp (add-prim) ((app-exp (var-exp sqr) ((var-exp v))) (app-exp (var-exp cub) ((var-exp x)))))))) => 1025has output, in the environment(run-test-all "let sqr= proc(x) *(x, x) a = list(1, 2, 3) in let b = list(car(a), cdr(a)) in cons(b, list(x, (sqr x), (sqr (sqr x))))")[i = 1, v = 5, x = 10](empty-env),"let sqr= proc(x) *(x, x) a = list(1, 2, 3) in let b = list(car(a), cdr(a)) in cons(b, list(x, (sqr x), (sqr (sqr x))))" or (let ([sqr (lambda (x) (* x x))] [a (list 1 2 3)]) (let ([b (list (car a) (cdr a))]) (cons b (list x (sqr x) (sqr (sqr x)))))) or (a-program (let-exp (sqr a) ((proc-exp (x) (primapp-exp (mult-prim) ((var-exp x) (var-exp x)))) (primapp-exp (list-prim) ((lit-exp 1) (lit-exp 2) (lit-exp 3)))) (let-exp (b) ((primapp-exp (list-prim) ((primapp-exp (car-prim) ((var-exp a))) (primapp-exp (cdr-prim) ((var-exp a)))))) (primapp-exp (cons-prim) ((var-exp b) (primapp-exp (list-prim) ((var-exp x) (app-exp (var-exp sqr) ((var-exp x))) (app-exp (var-exp sqr) ((app-exp (var-exp sqr) ((var-exp x)))))))))))) => ((1 (2 3)) 10 100 10000)