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 ch3-8ref.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 (3.8, pp. 115ff) A. eager (strict) vs. lazy evaluation ------------------------------------------ EAGER (strict) vs. LAZY def: a parameter passing mechanism is eager (or strict) if it evaluates actual parameters before calling the procedure --> define constant(x) = proc(y) x --> define loop() = (loop) --> ((constant 3) (loop)) ... loops forever ... def: a parameter passing mechanism is lazy if --> define constant(x) = proc(y) x --> define loop() = (loop) --> ((constant 3) (loop)) ------------------------------------------ B. motivation Why can't "if" be a procedure in a normal language? Could "if" be a procedure in a language with lazy evaluation? Does eager evaluation ever waste effort? C. implementation overview How could we avoid evaluating an expression in Scheme? ------------------------------------------ DELAYING EVALUATION IN SCHEME (define loop (lambda () (loop))) (define expensive (lambda () ...)) def: a *thunk* is a procedure with def: creation of a thunk is called *freezing* an expression e.g., to freeze (foo x 3) use (lambda () (foo x 3)) def: use of a thunk is called *thawing* it e.g., (define thaw (lambda (p) (p))) ------------------------------------------ D. call-by-name vs. call-by-need ------------------------------------------ CALL BY NAME vs. CALL BY NEED General idea: bind formals to thunks Call by name: evaluate thunk each time the corresponding formal parameter is referenced Call by need: evaluate the thunk only the first time it is used, save the value, return that stated value for other uses Example: let g = let count = 0 in proc () begin set count = add1(count); count end in (proc (x) +(x,x) (g)) ------------------------------------------ What are the advantages and disadvantages of these two strategies? E. implementation 1. domains ------------------------------------------ DOMAINS (for both) Expressed-Value = Number + ProcVal Denoted-Value = Ref(Target) Target = Direct-Target(Expressed-Value) + Indirect-Target(Ref(Target)) + Thunk-Target(expression x environment) ------------------------------------------ How does this differ from call by reference? 2. thunks as targets If we wanted to represent the information in (lambda () exp) without using a Scheme closure, how would we do that? ------------------------------------------ THUNKS AS TARGETS (for both) (define-datatype target target? (direct-target (expval expval?)) (indirect-target (ref ref-to-direct-target?)) (thunk-target ------------------------------------------ What do targets do in the interpreter? What should ref-to-direct-target? do? What about thunks? Why? 3. eval-rand ------------------------------------------ EVAL-RAND (deftype eval-rand (-> (expression environment) target)) (define eval-rand (lambda (rand env) (cases expression rand ------------------------------------------ 4. manipulating references What else in the interpreter is involved with targets? a. deref i. for call by name ------------------------------------------ DEREF FOR CALL BY NAME (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)) ------------------------------------------ ii. for call by need ------------------------------------------ DEREF FOR CALL BY NEED (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)) ------------------------------------------ ------------------------------------------ EVAL-THUNK FOR CALL BY NEED (deftype eval-thunk (-> ((ref-of target) expression environment) expressed-value)) (define eval-thunk (lambda (ref exp env) ------------------------------------------ b. setref! F. summary 1. memoization 2. language design 3. language user ------------------------------------------ SUMMARY CHART action mechanism | at call at return ===========|============================= value copy value - reference copy address - value-result copy address copy result copy value result copy address copy result name copy address - of thunk need copy address - of thunk ------------------------------------------