I. Call by Reference (3.8, pp. 107-114) A. Informal overview 1. pictures and basic meaning ------------------------------------------ CALL BY REFERENCE let t = 5 u = 6 v = 7 w = 8 in (proc (a, b) (proc (x, y, z) % picture for here set y = 13 a b 6) 3 v) t u v w [ * | * | * | * ] | | |^ | v v v \ v 5 6 7 | 8 \ \ |\ | \ | \ a b | \ [ * | * ] | \ ^ | | | \ / v \---/ | / 3 | | | | x y z | | [ * | * | * ] | | | | | | ------/ | v | | 6 | \--------/ set y = 13 ------------------------------------------ 2. motivation ------------------------------------------ CALL-BY-REFERENCE MOTIVATION let swap = proc(x,y) let temp = 0 in begin set temp = x; set x = y; set y = temp end a = 3 b = 4 in begin (swap a b); list(a,b) end ------------------------------------------ What does this in C++? Can you write swap in Scheme? Java? ------------------------------------------ FOR YOU TO DO Draw a picture of what happens with the following with call by reference: let assign2 = proc(v1, v2, e1, e2) begin set v1 = e1; set v2 = e2 end in let swap4 = proc(x,y) (assign2 x y y x) a = 3 b = 4 in begin (swap4 a b); list(a, b) end; ------------------------------------------ Can you do make the above work in C++ or Pascal? How? 3. passing non-variables by reference ------------------------------------------ WHAT IF PASS A VALUE BY REFERENCE? let c = 3 p = proc (x) set x = 5 in begin (p add1(c)); c end ------------------------------------------ What are the choices? B. model (interpreter/language changes) for call-by-reference 1. what kinds of parameters What kinds of things can we pass as arguments? ------------------------------------------ TARGETS ;; in 3-8ref-reference.scm (define-datatype reference reference? (a-ref (position integer?) (vec (vector-of target?)))) (define-datatype target target? (direct-target (expval expval?)) (indirect-target (ref reference?))) ------------------------------------------ ------------------------------------------ (deftype deref (-> ((ref-of target)) Expressed-Value)) (define deref (lambda (ref) (cases target (primitive-deref ref) (direct-target (expval) expval) (indirect-target (ref1) (cases target (primitive-deref ref1) (direct-target (expval) expval) (indirect-target (p) (eopl:error 'deref "Illegal reference: ~s" ref1))))))) Can you write setref! ? (deftype setref! (-> ((ref-of target) Expressed-Value) void)) ------------------------------------------ 2. domains and data structures ------------------------------------------ DOMAINS FOR CALL BY REFERENCE WITH INDIRECT ARRAYS Domains: Denoted-Value = Ref(Target) Target = Expressed-Value = Number + ProcVal ------------------------------------------ 3. changes to interpreter Where in the interpreter do we change how parameters are evaluated? ------------------------------------------ CHANGES FOR CALL-BY-REFERENCE (deftype eval-rands (-> ((list-of expression) environment) (list-of target))) (define eval-rands (lambda (rands env) (map (lambda (x) (eval-rand x env)) rands))) ;;; from EOPL2e, p. 112 (deftype eval-rand (-> (expression environment) target)) (define eval-rand (lambda (rand env) (cases expression rand (var-exp (id) (indirect-target (let ((ref (apply-env-ref env id))) (cases target (primitive-deref ref) (direct-target (expval) ref) (indirect-target (ref1) ref1) )))) (else (direct-target (eval-expression rand env)))))) ------------------------------------------ 4. Changes to procval So what gets passed to apply-procval then? So does that mean we have to change the procval ADT? ------------------------------------------ CHANGES TO PROCVAL (deftype apply-procval (-> (procval (list-of target)) Expressed-Value)) (define apply-procval (lambda (proc targs) (cases procval proc (closure (ids body env) (eval-expression body (extend-env ids targs env)))))) ------------------------------------------ 5. Changes to environment and init-env Do environments have to change to deal with targets? ------------------------------------------ ENVIRONMENT MAPS NAMES TO TARGETS (deftype apply-env-ref (-> (environment symbol) (ref-of target))) (deftype extend-env (-> ((list-of symbol) (list-of target) environment) environment)) ------------------------------------------ Does anything else have to change because of this? ------------------------------------------ CHANGES TO INIT-ENV (deftype init-env (-> () environment)) (define init-env (lambda () (extend-env '(i v x) (map direct-target (map number->expressed '(1 5 10))) (empty-env)))) ------------------------------------------ 6. implications a. let expressions Why do we make direct targets for expressions other than variables? ------------------------------------------ WHAT SHOULD LET DO? let three = 3 in let x = three in begin set x = +(x, 1); three end ------------------------------------------ b. primitives What choices do we have for calls to primitives? ------------------------------------------ WHAT ABOUT PRIMITIVES? (deftype apply-primitive (-> (primitive (list-of Expressed-Value)) Expressed-Value)) Can we use eval-rands for arguments to apply-primitive? ------------------------------------------ C. set expressions with call by reference ------------------------------------------ FOR YOU TO DO DRAW PICTURE FOR THE FOLLOWING let a = 0 b = 7 in let g = proc(y, z) begin set y = z; %% draw picture for here 0 end in begin (g a b); list(a, b) end ------------------------------------------ D. aliasing ------------------------------------------ VARIABLE ALIASING def: variables x and y are aliases if they both denote the same location. Thus, changing x's value also changes y's ------------------------------------------ ------------------------------------------ VARIABLE ALIASING CAUSES REASONING PROBLEMS Does the following correctly add the values of a and b into c, storing the result in c? let addInTo = proc(c,a,b) begin set c = b; set c = +(c,a) end in ... ------------------------------------------ ------------------------------------------ ALIASES CAUSE NAIVE REASONING TO FAIL let addInTo = proc(c,a,b) begin set c = b; set c = +(c,a) end in let x = 3 y = 4 in begin (addInTo x x y); x end; ------------------------------------------ Can you draw pictures of how this executes with call by reference? What does the last expression return? E. call-by-value-result (exercise 3.55) Would this work for swap? What happens if you call a procedure and use the same thing for two result parameters? F. mixes of mechanisms (exercise 3.53) Can we have both call-by-value and call-by reference? How do you know what to pass by reference and what by value? Is this more expressive? G. arrays (exercise 3.54) 1. array models (see EOPL first edition, chapter 6) ------------------------------------------ ARRAY MODELS Indirect arrays (Scheme, Java): stack heap a [ *-]--------------->[ * | * | * ] | | | v v v 1 2 3 Direct arrays (C/C++, Pascal, Ada): stack heap a [1|2|3] ------------------------------------------ ------------------------------------------ EXAMPLE letarray a[2]; b[2] in let p = proc(x,y) begin set y = b; set x = 5 end in begin set a[0] = 1; set a[1] = 2; set b[0] = 4; set b[1] = 6; (p a[1] a); list(a[0],a[1],b[0],b[1]) end ------------------------------------------ What does this do under call-by-value in the indirect model? What does this do under call-by-reference in the indirect model? What does this do under call-by-value in the direct model? What does this do under call-by-reference in the direct model? ------------------------------------------ FOR YOU TO DO What does this return under call by reference in the: (i) indirect and (ii) direct models? letarray u[3]; v[2] in let p = proc (x) begin set x = v; set x[0] = 0 end in begin set u[0] = 5; set u[1] = 6; set u[2] = 4; set v[0] = 3; set v[1] = 8; (p u); list(v[0], u[0]) end ------------------------------------------ II. Call-by-Name and Call-by-Need (6.5) A. call-by-name 1. informal overview (using the indirect array model) a. motivation Does any parameter mechanism correspond to beta-reduction? ------------------------------------------ LEFTMOST-ORDER MECHANISM? % does this work? --> define while = proc(test, body) if equal(test, 1) then begin body; while(test,body) end else 0; --> define not = proc(b) if equal(b, 0) then 1 else 0; --> define prod = proc(ls) local result = 1 in begin while(not(null(ls)), begin result := *(result, car(ls)); ls := cdr(ls) end); result end; --> define myls = list(1,2,3); --> prod(myls); ------------------------------------------ What might some advantages of giving users the ability to define things like while? b. array subscripts as parameters ------------------------------------------ SUBSCRIPTED ARRAY PARAMETERS PASSED BY NAME --> local i = 0 in local p = proc(x) begin i := 1; x := 2 end in letarray a[2] in begin a[0] := 1; p(a[i]); writeln(a[0], a[1]) end; ------------------------------------------ c. careful! ------------------------------------------ CAN WE JUST PASS PARAMETER TEXTS? --> define constant = proc(x) proc(y) x; --> (constant(3))(4); 3 --> define ohno = proc(x) ohno(x); --> (constant(3))(ohno(4)); 3 --> define y = 3; --> (constant(y))(4); ------------------------------------------ How could we avoid the capture? 2. model (interpreter/language changes) for call-by-name, indirect arrays a. domains and data structures ------------------------------------------ DOMAINS FOR CALL BY NAME WITH INDIRECT ARRAYS Environment = -> Denoted-Value Denoted-Value = Expressed-Value = Number + Procedure + Array(Expressed-Value) Procedure = prim-proc + closure Array(T) = {Cell(T)}* L-Value = Thunk = New data structures: ------------------------------------------ b. changes to interpreter ------------------------------------------ CHANGES TO THE CALL-BY-VALUE INTERPRETER FOR CALL-BY-NAME (INDIRECT MODEL) ;;; *Modified* from Figure 6.5.1 (deftype eval-rand (-> (parsed-exp Environment) Denoted-Value)) (define eval-rand (lambda (rand env) (variant-case rand ------------------------------------------ How and when do we get the value? What kinds of parameters are there? Why don't we have a special case for array refs? ------------------------------------------ EXTRACTING VALUES ;;; (unchanged code from) Figure 6.5.2 (deftype denoted->expressed (-> (Denoted-Value) Expressed-Value)) (define denoted->expressed (lambda (den-val) (let ((l-val (denoted->L-value den-val))) (cond ((cell? l-val) (cell-ref l-val)) ((ae? l-val) (array-ref (ae->array l-val) (ae->index l-val))) (else (error "Can't deref: " l-val)))))) ;;; *Modified* from Figure 6.5.2, page 204 (deftype denoted->l-value (-> (Denoted-Value) L-value)) (define denoted->l-value (lambda (den-val) (if (thunk? den-val) ------------------------------------------ What should eval-thunk do? ------------------------------------------ EXTRACTING VALUES (CONTINUED) ;;; *Modified* from Figure 6.5.2 (deftype eval-thunk (-> (Thunk) L-value)) (define eval-thunk ;; new name/type (lambda (thnk) (variant-case thnk (thunk (exp env) (variant-case exp (else (error "Not a thunk: " thnk))))) ------------------------------------------ What has to be done to assign to a denoted value? What cases? ------------------------------------------ MORE CHANGES TO THE CALL-BY-VALUE INTERPRETER FOR CALL-BY-NAME (INDIRECT MODEL) (deftype denoted-value-assign! (-> (Denoted-Value Expressed-Value) void)) (define denoted-value-assign! (lambda (den-val exp-val) (let ((l-val (cond ((cell? den-val) (cell-set! den-val exp-val)) ((ae? l-val) (else (error "Can't assign to :" den-val))))) ------------------------------------------ What is the value of let x = 3 in begin x := 4; x end (remember that let is a syntactic sugar)? So do we have any variables? ------------------------------------------ LOCAL VARIABLES Concrete syntax: ::= local in Abstract Syntax: (define-record local (decls body)) ;; changes to base interpreter: (define eval-exp (lambda (exp env) (variant-case exp ; ... (local (decls body) (let ((vars (map decl->var decls)) (exps (map decl->exp decls)) ) (let ((new-env (extend-env vars (map (lambda (exp) ; following is new! (expressed->denoted (eval-exp exp env))) exps) env))) (eval-exp body new-env)))) (else ...)))) ------------------------------------------ B. call by need 1. motivation 2. model ------------------------------------------ DOMAINS FOR CALL-BY-NEED (LAZY EVALUATION) WITH INDIRECT ARRAYS Environment = -> Denoted-Value Denoted-Value = Expressed-Value = Number + Procedure + Array(Expressed-Value) Procedure = prim-proc + closure Array(T) = {Cell(T)}* L-value = Cell(Expressed-Value) + Array-Element(Expressed-Value) Thunk = () -> L-Value Memo(T) = ------------------------------------------ What's the information in a memo? How could you make a record? ------------------------------------------ A MEMO ADT ;;; Anonymous figure : page 207 (define-record memo-rep (cell)) (define memo? memo-rep?) (deftype memo-remember (-> ((-> () T)) (memo T))) (define memo-remember (lambda (thnk) (make-memo-rep (make-cell thnk)))) (deftype memo-retrieve (-> ((memo T)) T)) (define memo-retrieve (lambda (m) (variant-case m (memo-rep (cell) ------------------------------------------ ------------------------------------------ DENOTED VALUES FOR CALL-BY-NEED (load-quietly-from-lib "memo.scm") ;;; Anonymous figure : page 202 (define-record thunk (exp env)) (deftype memo-create (-> (parsed-exp Environment) Denoted-Value)) (define memo-create (lambda (exp env) ;; eval-thunk as before (deftype l-value->denoted (-> (L-Value) Denoted-Value)) (define l-value->denoted inject) (deftype denoted->l-value (-> (Denoted-Value) L-value)) (define denoted->l-value (lambda (den-val) (if (memo? den-val) (memo-retrieve den-val) den-val))) ------------------------------------------ a. model interpreter changes ------------------------------------------ CHANGES FOR CALL-BY-NEED INTERPRETER MAKING MEMOS ;;; *Modified* from Figure 6.5.3, page 208 (deftype eval-rand (-> (parsed-exp Environment) Denoted-Value)) (define eval-rand (lambda (rand env) (variant-case rand (varref (var) (let ((den-val (apply-env env var))) ------------------------------------------ ------------------------------------------ CHANGES FOR CALL-BY-NEED INTERPRETER EXTRACTING VALUES ;;; *Modified* from Figure 6.5.3, page 208 (deftype (-> (Denoted-Value) L-value)) (define denoted->l-value (lambda (den-val) ------------------------------------------