--- C311 script4.txt -- 9/24/96 --- Add local binding (the LET form): --> ( let ( * ) ) --> --> ( ) Example: (let ((x 3) (y (* 1 2))) (+ x y)) --- We start with a distilation of our previous interpreter-support code. --- > (begin (define apply-env (lambda (env symbol) (record-case env (empty-env () (error 'empty-env "no association for symbol: ~s" symbol)) (extended-env (sym-list val-vector env) (let ((x (memq symbol sym-list))) (if x (vector-ref val-vector (- (length sym-list) (length x))) (apply-env env symbol)))) (else (error 'apply-env "Invalid finite function: ~s" env))))) (define the-empty-env (list 'empty-env)) (define extend-env (lambda (sym-list val-list env) (list 'extended-env sym-list (list->vector val-list) env))) (define variable? symbol?) (define literal? number?) (define app->rator car) (define app->rands cdr) (define *prim-op-names* '(+ - * add1 sub1)) (define apply-prim-op (lambda (prim-op args) (case prim-op ((+) (+ (car args) (cadr args))) ((-) (- (car args) (cadr args))) ((*) (* (car args) (cadr args))) ((add1) (+ (car args) 1)) ((sub1) (- (car args) 1)) (else (error 'apply-prim-op "Invalid prim-op name: ~s" prim-op))))) (define make-prim-proc (lambda (prim-op-name) (list 'prim-proc prim-op-name))) (define init-env (extend-env *prim-op-names* (map make-prim-proc *prim-op-names*) the-empty-env)) (define apply-proc (lambda (proc args) (if (pair? proc) (record-case proc (prim-proc (prim-op) (apply-prim-op prim-op args)) (else (error 'apply-proc "Invalid procedure: ~s" proc))) (error 'apply-proc "Invalid procedure: ~s" proc))))) --- Now to add let we need a little syntax support and and a version of eval-exp that takes an environment argument. --- > (define decl->var car) > (define decl->exp cadr) > (define eval-exp (lambda (exp env) (cond ((literal? exp) exp) ((variable? exp) (apply-env env exp)) ; CHANGE (else (record-case exp (let (decls body) ; NEW (let ((vars (map decl->var decls)) (exps (map decl->exp decls))) (let ((new-env (extend-env vars (eval-rands exps env) env))) (eval-exp body new-env)))) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args)))))))) > (define eval-rands (lambda (rands env) (map (lambda (exp) (eval-exp exp env)) rands))) > (define run (lambda (exp) (eval-exp exp init-env))) > (run '(let ((x (+ 1 2)) (y (add1 3))) (* x y))) 12 --- PROCEDURES What happens when we evaluate a lambda expression? +++ NOT MUCH: we make a CLOSURE that "closes over", or captures the values of the variables that appear FREE in the lambda expression. --- We extend the procedure ADT. It is easier for us (but not necessarily a compiler) to capture the whole environment. --- > (define make-closure (lambda (formals body env) (list 'closure formals body env))) --- What happens when we invoke a closure? +++ In what environment do we evaluate the body? --- > (define apply-proc (lambda (proc args) (record-case proc (prim-proc (prim-op) (apply-prim-op prim-op args)) (closure (formals body env) ; NEW (eval-exp body (extend-env formals args env))) (else (error 'apply-proc "Invalid procedure: ~s" proc))))) > (define eval-exp (lambda (exp env) (cond ((literal? exp) exp) ((variable? exp) (apply-env env exp)) (else (record-case exp (lambda (formals body) (make-closure formals body env)) (let (decls body) (let ((vars (map decl->var decls)) (exps (map decl->exp decls))) (let ((new-env (extend-env vars (eval-rands exps env) env))) (eval-exp body new-env)))) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args)))))))) > (run '((lambda (a b) (+ a (* b 3))) 3 4)) > (run '(lambda (x) y)) --- What would the interpreter look like if we represented procedures as Scheme closures? --- Let expressions can be implemented in terms of the syntactic transformation: (let ((var exp) ...) body) ==> ((lambda (var ...) body) exp ...) --- > (define eval-exp (lambda (exp env) (cond ((literal? exp) exp) ((variable? exp) (apply-env env exp)) (else (record-case exp (let (decls body) (let ((vars (map decl->var decls)) (exps (map decl->exp decls))) (eval-exp (cons (list 'lambda vars body) exps) ; CHANGED env))) ; CHANGED (lambda (formals body) (make-closure formals body env)) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args)))))))) > (run '(let ((x 3) (y 4)) (+ x y))) 7 --- If we expand let expressions into applications before entering the interpreter, this work only is done once. > (define run (lambda (exp) (eval-exp (expand exp) init-env))) > (define expand (lambda (exp) (cond ((literal? exp) exp) ((variable? exp) exp) (else (record-case exp (let (decls body) (let ((vars (map decl->var decls)) (exps (map decl->exp decls))) (expand (cons (list 'lambda vars body) exps)))) (lambda (formals body) (list 'lambda formals (expand body))) (else (map expand exp))))))) > (define eval-exp (lambda (exp env) (cond ((literal? exp) exp) ((variable? exp) (apply-env env exp)) (else (record-case exp ; LET CLAUSE IS GONE NOW (lambda (formals body) (make-closure formals body env)) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args)))))))) > (run '(let ((x 3) (y 4)) (+ x y))) 7 --- Let's add QUOTE to the interpreter. > (define eval-exp (lambda (exp env) (cond ((literal? exp) exp) ((variable? exp) (apply-env env exp)) (else (record-case exp (quote (datum) datum) ; NEW (lambda (formals body) (make-closure formals body env)) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args)))))))) > (run '(+ '3 '5)) 8 > (run ''a) a --- We can implement all literals as quotations via the syntactic transformation literal ==> (quote literal) > (define expand (lambda (exp) (cond ((literal? exp) (list 'quote exp)) ; CHANGE ((variable? exp) exp) (else (record-case exp (quote (datum) exp) (let (decls body) (let ((vars (map decl->var decls)) (exps (map decl->exp decls))) (expand (cons (list 'lambda vars body)) exps))) (lambda (formals body) (list 'lambda formals (expand body))) (else (map expand exp))))))) > (define eval-exp (lambda (exp env) ; NO LITERAL CLAUSE (if (variable? exp) (apply-env env exp) (record-case exp (quote (datum) datum) (lambda (formals body) (make-closure formals body env)) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args))))))) > (run '(+ 1 '2)) 3 --- ASSIGNMENT --> ( set! ) Our environment ADT does not support assignment. It could be extended to support assignment, but we choose not to do so in order to emphasize the following: Abstractly, environments map variables to "denoted values", which do not change. Expressions, on the other hand, return "expressed values". So far, the denoted and expressed values have been the same: Denoted Value = Expressed Value +++ But in most languages (such as Scheme, C, Pascal, and Ada), they are not the same because variables denote mutable (assignable) locations (or cells) that cannot be the value of an expression. Denoted Value = cell(Expressed Value) --- We create a cell ADT: make-cell, cell-ref, cell-set! +++ Let's represent cells as pairs with the symbol CELL in the car and the value in the cdr: > (define make-cell (lambda (value) (cons 'cell value))) > (define cell-ref (lambda (cell) (cdr cell))) > (define cell-ref cdr) > (define cell-set! (lambda (cell value) (set-cdr! cell value))) > (define cell-set! set-cdr!) --- In the interpreter we have to change how variables are referenced and how environments are extended, as well as adding a SET! clause. > (define apply-proc (lambda (proc args) (record-case proc (prim-proc (prim-op) (apply-prim-op prim-op args)) (closure (formals body env) (eval-exp body (extend-env formals (map make-cell args) ; CHANGED env))) (else (error 'apply-proc "Invalid procedure: ~s" proc))))) > (define eval-exp (lambda (exp env) (if (variable? exp) (cell-ref (apply-env env exp)) ; CHANGED (record-case exp (set! (var exp) ; NEW (cell-set! (apply-env env var) (eval-exp exp env))) (quote (datum) datum) (lambda (formals body) (make-closure formals body env)) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args))))))) > (run '(let ((x 3)) (let ((y (set! x 4))) x))) > (run '(+ 1 2)) > (define init-env (extend-env *prim-op-names* (map (lambda (prim-op) (make-cell (make-prim-proc prim-op))) *prim-op-names*) the-empty-env)) > (define compose (lambda (f g) (lambda (x) (f (g x))))) > (define init-env (extend-env *prim-op-names* (map (compose make-cell make-prim-proc) *prim-op-names*) the-empty-env)) > (run '(+ 1 2)) --- Exercise 5.5.3: What if apply-proc were redefined as follows: > (define denoted->expressed cell-ref) > (define apply-proc (lambda (proc args) (record-case proc (prim-proc (prim-op) (apply-prim-op prim-op (map denoted->expressed args))) (closure (formals body env) (eval-exp body (extend-env formals (map make-cell args) env))) (else (error 'apply-proc "Invalid procedure: ~s" proc))))) --- Redefine eval-rands so this works. Can you suggest a further change so that set! can be a primitive? Is this a good idea? > (define expressed->denoted make-cell) > (define eval-rands (lambda (rands env) (map (lambda (exp) (if (variable? exp) (apply-env env exp) (expressed->denoted (eval-exp exp env)))) rands))) > (define eval-exp (lambda (exp env) (if (variable? exp) (cell-ref (apply-env env exp)) (record-case exp ; NO SET! CLAUSE (quote (datum) datum) (lambda (formals body) (make-closure formals body env)) (else (let ((proc (eval-exp (app->rator exp) env)) (args (eval-rands (app->rands exp) env))) (apply-proc proc args))))))) > (define apply-proc (lambda (proc args) (record-case proc (set-proc () (cell-set! (car args) (prim-proc (prim-op) (apply-prim-op prim-op (map denoted->expressed args))) (closure (formals body env) (eval-exp body (extend-env formals (map make-cell args) env))) (else (error 'apply-proc "Invalid procedure: ~s" proc))))))) > (define init-env (extend-env (cons 'set! *prim-op-names*) (cons (list 'set-proc) (map (compose make-cell make-prim-proc) *prim-op-names*)) the-empty-env)) > (run '(let ((x 3)) (let ((y (set! x 4))) x))) > (run '(+ 1 2)) --- Class discussion of * EOPL Exercise 5.5.3 * rib-structured environments and closures * display (flat) closures * engineering trade-offs of display closures - more expensive closure creation - less expensive variable reference (at least if variables not assigned) - less likely to prevent collection of garbage * set! elimination necessitated by display closures * uses for variable and data mutation: primarily - modeling real-world objects with changing state - memoizing * inefficiencies of variable assignment and mutation - extra indirection - more difficult for --- END ---