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) 5 6 7 8 ^ ^ ^ ^ | | | | [ * | * | * | * ] t u v ^ w \ |\ 3 | \ ^ / | \ / | [ * | * ] | a ^ b | | | 6 \ / ^ \ / / [ * | * | * ] x y z 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 ------------------------------------------ CHANGES FOR CALL-BY-REFERENCE ;;; 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. implications and variations 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. aliasing ------------------------------------------ VARIABLE ALIASING 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? d. 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? e. 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? C. 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 ------------------------------------------