I. Adding Arrays (6.1) A. context What's missing from our defined langauge so far? ------------------------------------------ AGGREGATE DATA STRUCTURES def: an *aggregate* data structure is How is aggregate data passed to procedures? ------------------------------------------ B. syntax ------------------------------------------ ARRAYS Concrete syntax:
::= definearray [] | ::= letarray in | [] | [] := ::= | () ::= {; }* ::= [] Examples: Abstract Syntax: (define-record definearray (var len-exp)) (define-record letarray (arraydecls body)) (define-record arrayref (array index)) (define-record arrayassign (array index exp)) (define-record decl (var exp)) ------------------------------------------ C. array ADT What should the first index of an array be? ------------------------------------------ ARRAY ADT Array ADT signature: make-array: (-> (number) (Array T)) array?: (-> (datum) boolean) array-ref: (-> ((Array T) natural) ) array-set! : (-> ((Array T) number T) void) array-whole-set!: : (-> ((Array T) (Array T)) void) array-copy: (-> ((Array T)) (Array T)) array-length : (-> ((Array T)) number) Behavior: (array? (make-array n)) = (array? (array-copy a)) = (array? (vector 3 4)) = (let ((a (make-array 2)) (b (make-array 2))) (array-set! a 0 227) (array-set! a 1 228) (array-set! a 0 342) (array-whole-set! b a) (list "a[0]" (array-ref a 0) "b[1]" (array-ref b 1) "eq?" (eq? a b))) = (array-length (make-array n)) = ------------------------------------------ D. base interpreter with arrays ------------------------------------------ CH 6 BASE INTERPRETER ;;; Figure 6.1.2 : page 182 (define eval-exp ;; TYPE: (-> (parsed-exp Environment) ;; Expressed-Value) (lambda (exp env) (variant-case exp (varref (var) (denoted->expressed (apply-env env var))) (varassign (var exp) (void->expressed (denoted-value-assign! (apply-env env var) (eval-exp exp env)))) (letarray (arraydecls body) ------------------------------------------ ------------------------------------------ ;; Figure 6.1.2 continued (arrayref (array index) (arrayassign (array index exp) (array-element-assign! ;; new! (else ...)))) ------------------------------------------ ------------------------------------------ EVALUATION OF OPERANDS (define eval-rands ;; TYPE: (-> ((list parsed-exp) ;; Environment) ;; (list Denoted-Value)) (lambda (rands env) (map (lambda (rand) (eval-rand rand env)) rands))) (define eval-rand ;; TYPE: (-> (parsed-exp Environment) ;; Denoted-Value) (lambda (exp env) (expressed->denoted (eval-exp exp env)))) (define apply-proc ------------------------------------------ What else do we need to write? ------------------------------------------ ROLES OF THE HOOKS array-element-assign! denoted->expressed denoted-value-assign! do-letarray eval-array-exp expressed->denoted ------------------------------------------ E. call by value with indirect arrays 1. example ------------------------------------------ INDIRECT ARRAY MODEL EXAMPLE letarray u[3]; v[2] in let p = proc (x) begin x := v; x[0] := 0 end in begin u[0] := 5; u[1] := 6; u[2] := 4; v[0] := 3; v[1] := 8; p(u); print(v[0]) end ------------------------------------------ ------------------------------------------ ANOTHER INDIRECT ARRAY MODEL EXAMPLE letarray a[3] in let suma = proc (x) begin x[1] := 10; +(x[0],+(a[1],x[0])) end in begin a[0] := 7; a[1] := 5; a[2] := 3; suma(a) end ------------------------------------------ 2. domains ------------------------------------------ DOMAINS FOR INDIRECT ARRAYS (CALL BY VALUE) Domains: Environment = -> Denoted-Value Denoted-Value = Expressed-Value = Number + Procedure + Procedure = prim-proc + closure Array(T) = Some of the helping procedures: array->expressed : (-> ((Array Expressed-Value)) Expressed-Value) expressed->array : (-> (Expressed-Value) (list Expressed-Value)) ------------------------------------------ What were those hooks (helping procedures we still need to write)? What are the types of these free variables? ------------------------------------------ EXPRESSED <-> DENOTED FOR THE INDIRECT MODEL ;;; Figure 6.1.3 : page 183 (define denoted->expressed ;; TYPE: (-> (Denoted-Value) ;; Expressed-Value) (define expressed->denoted ;; TYPE: (-> (Expressed-Value) ;; Denoted-Value) ------------------------------------------ ------------------------------------------ AUXILIARY FUNCTIONS FOR THE INDIRECT MODEL ;;; Figure 6.1.3 : page 183 (define denoted-value-assign! (define do-letarray ------------------------------------------ ------------------------------------------ MORE AUXILIARY FUNCTIONS FOR THE INDIRECT MODEL (define eval-array-exp ;; addition to figure 6.1.3 (define array-element-assign! ------------------------------------------ How does that make it call by value for parameters? F. call by value with direct arrays 1. example ------------------------------------------ DIRECT ARRAY MODEL EXAMPLE letarray u[3]; v[2] in let p = proc (x) begin x := v; x[0] := 0 end in begin u[0] := 5; u[1] := 6; u[2] := 4; v[0] := 3; v[1] := 8; p(u); print(v[0]) end ------------------------------------------ ------------------------------------------ ANOTHER DIRECT ARRAY MODEL EXAMPLE letarray a[3] in let suma = proc (x) begin x[1] := 10; +(x[0],+(a[1],x[0])) end in begin a[0] := 7; a[1] := 5; a[2] := 3; suma(a) end ------------------------------------------ Can two array names name the same array in the direct model? 2. domains ------------------------------------------ DOMAINS FOR DIRECT ARRAYS (CALL BY VALUE) Domains: Environment = -> Denoted-Value Denoted-Value = Expressed-Value = Number + Procedure + Void + Array(Storable-Value) Procedure = prim-proc + closure Array(T) = {Cell(T)}* Storable-Value = ------------------------------------------ Can you have multi-dimensional arrays with the direct model? ------------------------------------------ STORABLE-VALUE DOMAIN FOR THE DIRECT MODEL number->storable : (-> (number) Storable-Value) storable->number : (-> (Storable-Value) number) procedure->storable : (-> (Procedure) Storable-Value) storable->procedure : (-> (Storable-Value) Procedure) storable->denoted : (-> (Storable-Value) Denoted-Value) expressed->storable : (-> (Expressed-Value) Storable-Value) storable->expressed : (-> (Storable-Value) Expressed-Value) ------------------------------------------ ------------------------------------------ DENOTABLE-VALUE DOMAIN FOR THE DIRECT MODEL make-cell : (-> (Storable-Value) Denoted-Value) cell-ref : (-> (Denoted-Value) Storable-Value) cell-set! : (-> (Denoted-Value Storable-Value) void) cell-swap! : (-> (Denoted-Value Denoted-Value) void) array->denoted : (-> ((Array Storable-Value)) Denoted-Value) denoted->array : (-> (Denoted-Value) (Array Storable-Value)) ------------------------------------------ ------------------------------------------ EXPRESSED <-> DENOTED FOR THE DIRECT MODEL ;;; Figure 6.1.4 : page 184 (revised) (define denoted->expressed ;; TYPE: (-> (Denoted-Value) ;; Expressed-Value) (lambda (den-val) (define expressed->denoted ;; TYPE: (-> (Expressed-Value) ;; Denoted-Value) (lambda (exp-val) ------------------------------------------ ------------------------------------------ AUXILIARY FUNCTIONS FOR THE DIRECT MODEL ;;; Figure 6.1.4 : page 184 (revised) (define denoted-value-assign! ;; TYPE: (-> (Denoted-Value ;; Expressed-Value) ;; void) (lambda (den-val exp-val) (cond ((and (not (array? den-val)) (not (array? exp-val))) ; new (cell-set! den-val (expressed->storable exp-val))) ((and (array? den-val) (array? exp-val)) ; new (array-whole-set! (denoted->array den-val) (expressed->array exp-val))) ((and (not (array? den-val)) (array? exp-val)) ; new ... (error (else (error ------------------------------------------ ------------------------------------------ AUXILIARY FUNCTIONS FOR THE DIRECT MODEL CONTINUED (define do-letarray ;; TYPE: (-> (number) Denoted-Value) (lambda (n) (if (not (<= 0 n)) ; added check (error "do-letarray: bad index") (array->denoted (make-array n))))) (define eval-array-exp ;; TYPE: (-> (parsed-exp Environment) ;; Expressed-Value) (lambda (exp env) (eval-exp exp env))) ------------------------------------------ ------------------------------------------ FOR YOU TO DO (define array-element-assign! ;; TYPE: (-> ((Array Storable-Value) ;; number ;; Expressed-Value) ;; void) (lambda (array index value) (if (array? value) (error ------------------------------------------ II. Call by Reference (6.2) A. informal overview (using the indirect array model) 1. motivation ------------------------------------------ CALL-BY-REFERENCE (WITH INDIRECT ARRAYS) MOTIVATION define swap = proc(x,y) let temp = 0 in begin temp := x; x := y; y := temp end; let a = 3; b = 4 in begin swap(a,b); print(a); print(b) end; ------------------------------------------ What does this in C++? ------------------------------------------ FOR YOU TO DO Draw a picture of what happens with the following with call by reference, (using the indirect array model): define assign2 = proc(v1, v2, e1, e2) begin v1 := e1; v2 := e2 end; define swap4 = proc(x,y) assign2(x,y,y,x); let a = 3; b = 4 in begin swap4(a,b); print(a); print(b) end; ------------------------------------------ Can you do make the above work in C++ or Pascal? How? 2. aliasing ------------------------------------------ VARIABLE ALIASING define addInTo = proc(c,a,b) begin c := b; c := +(c,a) end; 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? 3. passing array elements Can we use swap to swap array elements? ------------------------------------------ CALL BY REFERENCE FOR ARRAY ELEMENTS define init = proc(v) v := 0; letarray a[3] in begin init(a[0]); init(a[1]); init(a[2]); print(a[0]) end; ------------------------------------------ 4. passing non-variables by reference ------------------------------------------ WHAT IF PASS A VALUE BY REFERENCE? define c = 3; define p = proc (x) x := 5; begin p(add1(c)); c end; ------------------------------------------ What are the choices? B. model (interpreter/language changes) for call-by-reference, indirect arrays 1. what kinds of parameters What kinds of things can we pass by reference? 2. domains and data structures ------------------------------------------ DOMAINS FOR CALL BY REFERENCE WITH INDIRECT ARRAYS Domains: Environment = -> Denoted-Value Denoted-Value = Expressed-Value = Number + Procedure + Array(Expressed-Value) Procedure = prim-proc + closure Array(T) = {Cell(T)}* New data structure: ------------------------------------------ How would we represent an array element L-value? 3. changes to interpreter ------------------------------------------ CHANGES TO THE CALL-BY-VALUE INTERPRETER FOR CALL-BY-REFERENCE (INDIRECT MODEL) ;;; Figure 6.2.1 : page 191 (revised) (define eval-rand ;; TYPE: (-> (parsed-exp Environment) ;; Denoted-Value) (lambda (rand env) (variant-case rand (varref (var) (arrayref (array index) (define denoted->expressed ;; TYPE: (-> (Denoted-Value) ;; Expressed-Value) (lambda (den-val) (cond ((cell? den-val) (cell-ref den-val)) ((ae? den-val) (else (error "Can't dereference: " den-val))))) ------------------------------------------ How does eval-rand treat array names? Is that different from how it treats expressions returning arrays? can the error ever happen? ------------------------------------------ OTHER AUXILIARY FUNCTIONS FOR CALL-BY-REFERENCE (INDIRECT MODEL) (define denoted-value-assign! ;; TYPE: (-> (Denoted-Value ;; Expressed-Value) void) (lambda (den-val val) (cond ((cell? den-val) (cell-set! den-val val)) ((ae? den-val) (else (error "Can't assign to :" den-val))))) (define array-element-assign! ;; TYPE: (-> ((Array Expressed-Value) ;; number ;; Expressed-Value) ;; void) array-set!) ------------------------------------------ What about do-letarray, does it change from 6.1.3's interpreter? How about eval-array-exp? ------------------------------------------ INDIRECT MODEL EXAMPLE letarray a[3]; b[2] in let p = proc(x,y) begin y := b; x := 5 end in begin a[0] := 1; a[1] := 2; a[2] := 3; b[0] := 4; b[1] := 6; p(a[1], a); list(a[0],a[1],b[0],b[1]) end ------------------------------------------ C. model with direct arrays 1. motivation (differences) ------------------------------------------ DIRECT MODEL EXAMPLE letarray a[3]; b[2] in let p = proc(x,y) begin y := b; x := 5 end in begin a[0] := 1; a[1] := 2; a[2] := 3; b[0] := 4; b[1] := 6; p(a[1], a); list(a[0],a[1],b[0],b[1]) end ------------------------------------------ ------------------------------------------ INDIRECT VS. DIRECT MODEL letarray u[3]; v[2] in let p = proc (x) begin x := v; x[0] := 0 end in begin u[0] := 5; u[1] := 6; u[2] := 4; v[0] := 3; v[1] := 8; p(u); print(v[0]) end ------------------------------------------ What would print(u[0]) print at the end? 2. model interpreter changes What is meant by passing an array element by reference? What would have to change in the interpreter? ------------------------------------------ CALL-BY-REFERENCE WITH DIRECT ARRAYS Domains: Environment = -> Denoted-Value Denoted-Value = Expressed-Value = Number + Procedure + Array(Storable-Value) Procedure = prim-proc + closure Storable-Value = Number + Procedure Array(T) = {Cell(T)}* ------------------------------------------ III. Call by Value-Result and call-by-result (6.3) A. informal overview 1. motivation ------------------------------------------ MOTIVATION FOR CALL BY VALUE-RESULT How would a compiler access a formal using: - call by value? - call by reference? Which is more efficient? Which works over a network? What can be done with call-by-reference that can't be with call-by-value? ------------------------------------------ 2. examples ------------------------------------------ CALL BY REFERENCE VS. CALL BY VALUE-RESULT EXAMPLE define swap2 = proc (x, y) begin x := +(x, y); y := -(x, y); x := -(x, y) end; let b = 5; c = 7 in begin swap2(b, c); print(b); print(c) end; ------------------------------------------ What does this do in call by reference? value-result? What if we execute swap(b,b)? ------------------------------------------ PASSING AN ARRAY BY VALUE-RESULT let one = 1 in let p = proc(b,x) begin x := 2; b[x] := one end in letarray a[3] in begin a[0] := 7; a[1] := 8; a[2] := 9; p(a, one); list(a,one) end ------------------------------------------ Is there any complication for passing an array element? ------------------------------------------ PASSING ARRAY ELEMENTS BY VALUE-RESULT let swap = proc(x,y) let temp = 0 in begin temp := x; x := y; y := temp end in letarray a[3] in begin a[0] := 3; a[1] := 4; a[2] := 2; let i = 0 in begin swap(i, a[i]); list(i, a[0], a[1], a[2]) end ------------------------------------------ What about in the direct model? How would you implement call by value-result? How does call by value-result relate to call-by-value? What do you think call-by-result should mean? B. summary ------------------------------------------ LANGUAGES AND MECHANISMS array language model mechanism(s) C direct value C++ direct value (default) reference (&) Pascal direct value (default) reference (var) MS Visual direct reference (default) Basic 6.0 value (ByVal) Ada direct value (in) result (out) value-result (in out) Java indirect value Scheme Smalltalk ------------------------------------------ ------------------------------------------ SUMMARY OF CALLING MECHANISMS action at call at return mechanism value copy value - reference copy address - value-result result name/need make closure - pass address of closure variable reference is direct to local for call-by: variable reference is indirect in: ------------------------------------------ IV. 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 (define eval-rand ;; TYPE: (-> (parsed-exp Environment) ;; Denoted-Value) (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 (define denoted->expressed ;; TYPE: (-> (Denoted-Value) ;; Expressed-Value) (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 (define denoted->l-value ; TYPE: (-> (Denoted-Value) L-value) (lambda (den-val) (if (thunk? den-val) ------------------------------------------ What should eval-thunk do? ------------------------------------------ EXTRACTING VALUES (CONTINUED) ;;; *Modified* from Figure 6.5.2 (define eval-thunk ;; new name/type ;; TYPE: (-> (Thunk) L-value) (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) (define denoted-value-assign! ;; TYPE: (-> (Denoted-Value ;; Expressed-Value) void) (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 ; TYPE: (-> (parsed-exp Environment) ; Expressed-Value) (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?) (define memo-remember ;; TYPE: (-> ((-> () T)) (memo T)) (lambda (thnk) (make-memo-rep (make-cell thnk)))) (define memo-retrieve ;; TYPE: (-> ((memo T)) T) (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)) (define memo-create ;; TYPE: (-> (parsed-exp Environment) ;; Denoted-Value) (lambda (exp env) ;; eval-thunk as before (define l-value->denoted ;; TYPE: (-> (L-Value) Denoted-Value) inject) (define denoted->l-value ;; TYPE: (-> (Denoted-Value) 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 (define eval-rand ; TYPE: (-> (parsed-exp Environment) ; Denoted-Value) (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 (define denoted->l-value ; TYPE: (-> (Denoted-Value) L-value) (lambda (den-val) ------------------------------------------