C311 script10.txt -- 3/24/97

---

PARAMATER PASSING

> (begin
    (define cell-ref cdr)
    (define make-cell
      (lambda (x)
	(cons 'cell x)))
    (define cell-set! set-cdr!)
    (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 decl->var car)
    (define decl->exp cadr)
    (define make-closure
      (lambda (formals body env)
	(list 'closure formals body env)))
    (load "~/w/grammar.ss")
    (define run
      (lambda (exp)
	(if (exp? exp) (eval-exp (expand exp) init-env)))))

---

SEMANTIC DOMAINS used throughout

procedure = closure + prim-proc

expressed-value = number + procedure

L-value = cell(expressed-value)

closure = (denoted-value*) -> expressed-value

prim-proc = (denoted-value*) -> expressed-value

+++

SYNTAX

We add the LOCAL form, which is like our old let.

We also allow sequences in the bodies of let, local, and lambda.

> (define exp?
    (grammar expression
      (variable
	(predicate
	  (lambda (x)
	    (and (symbol? x)
	      (not (memq x '(quote local lambda let set!)))))))
      (literal (predicate number?))
      (datum (predicate (lambda (x) #t)))
      (declaration (lst variable expression))
      (procedure-call
	(predicate    ;; this could have been (lst (plus expression))
	  (lambda (x) ;; but then a spurious bad keyword is reported
	    (and (pair? x)	    
	      (not (and (symbol? (car x)) (not (variable x))))
	      ((seq (plus expression))
	       x)))))
      (expression
	(report-if-bad 'expression
	  (alt variable literal procedure-call
	    (lst 'quote datum)
	    (lst 'lambda (lst (star variable)) (plus expression))
	    (lst 'set! variable expression)
	    (lst 'let (lst (star declaration)) (plus expression))
	    (lst 'local (lst (star declaration)) (plus expression)))))))

---

Sequencing is handled in lambda bodies.

> (define expand
    (lambda (exp)
      (cond
	((literal? exp) (list 'quote exp))
	((variable? exp) exp)
	(else 
	  (record-case exp
	    (quote (datum) exp)
	    (set! (var exp) (list 'set! var (expand exp)))
	    (let (decls . body)
	      (let ((vars (map decl->var decls))
		    (exps (map decl->exp decls)))
		(expand (cons (cons 'lambda (cons vars body))
			  exps))))
	    (local (decls . body)
	      (let ((vars (map decl->var decls))
		    (exps (map decl->exp decls)))
		(list 'local (map (lambda (decl)
				    (list (decl->var decl)
				      (expand (decl->exp decl))))
			       decls)
		  (expand (cons 'let (cons '() body))))))
	    (lambda (formals . body)
	      (cons 'lambda (cons formals (map expand body))))
	    (else (map expand exp)))))))

> (define L-value->expressed cell-ref)

> (define denoted->L-value 'ignored) ; assigned by the call-by- procedures

> (define denoted->expressed
    (lambda (denval)
      (L-value->expressed (denoted->L-value denval))))

> (define expressed->L-value make-cell)

> (define L-value->denoted (lambda (lval) lval))

> (define expressed->denoted
    (lambda (val)
      (L-value->denoted (expressed->L-value val))))

> (define apply-proc
    (lambda (proc args)
      (if (pair? proc)
	(record-case proc
	  (prim-proc (prim-op)
	    (apply-prim-op prim-op (map denoted->expressed args)))
	  (closure (formals body env)
	    (eval-body body (extend-env formals args env)))
	  (else (error 'apply-proc "Invalid procedure: ~s" proc)))
	(error 'apply-proc "Invalid procedure: ~s" proc))))

> (define eval-body
    (lambda (body env)
      (let ((answer (eval-exp (car body) env)))
	(if (null? (cdr body))
	  answer
	  (eval-body (cdr body) env)))))

---

Denoted values will always be primative procedures in prim-env, and we
assume primitive names cannot be shadowed.

> (define prim-env init-env)

> (define init-env the-empty-env)

> (define eval-exp
    (lambda (exp env)
      (if (variable? exp)
	(if (memq exp *prim-op-names*)
	  (apply-env prim-env exp)
	  (denoted->expressed (apply-env env exp)))
	(record-case exp
	  (quote (datum) datum)
	  (lambda (formals . body) (make-closure formals body env))
	  (set! (var exp)
	    (cell-set! (denoted->L-value (apply-env env var))
	      (eval-exp exp env)))
	  (local (decls body)
	    (let ((vars (map decl->var decls))
		  (exps (map decl->exp decls)))
	      (eval-exp body
		(extend-env vars
		  (map (lambda (exp) (expressed->denoted (eval-exp exp env)))
		    exps)
		  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-rand exp env))
	rands)))

---

eval-rand will be assigned by the call-by- procedures

> (define eval-rand 'ignored) 

---

Now we are set up to define the call-by variations.

+++

For call-by-value and call-by-reference

  denoted-value = L-value

> (define call-by-value
    (lambda ()
      (set! denoted->L-value (lambda (denval) denval))
      (set! eval-rand
	(lambda (rand env)
	  (expressed->denoted (eval-exp rand env))))))

> (define call-by-reference
    (lambda ()
      (set! denoted->L-value (lambda (denval) denval))
      (set! eval-rand
	(lambda (rand env)
	  (if (variable? rand)
	    (apply-env env rand)
	    (expressed->denoted (eval-exp rand env)))))))

+++

For call-by-name, 

  denoted-value = L-value + thunk 

  thunk = () -> L-value

First we need a thunk ADT.

> (define make-thunk
    (lambda (exp env)
      (list 'thunk exp env)))

> (define thunk?
    (lambda (x)
      (and (pair? x) (eq? (car x) 'thunk))))

> (define thunk->exp cadr)
> (define thunk->env caddr)

> (define thaw-thunk
    (lambda (thunk)
      (let ((exp (thunk->exp thunk))
	    (env (thunk->env thunk)))
	(if (variable? exp)
	  (denoted->L-value (apply-env env exp))
	  (expressed->L-value (eval-exp exp env))))))

---

Call-by-name makes thunks out of operands and thaws them at the last
possible moment.

> (define call-by-name
    (lambda ()
      (set! denoted->L-value
	(lambda (denval)
	  (if (thunk? denval)
	    (thaw-thunk denval)
	    denval)))
      (set! eval-rand
	(lambda (rand env)
	  (make-thunk rand env)))))

---

Testing...

> (define test
    (lambda (exp)
      (call-by-value)
      (printf "By-value: ~s~n" (run exp))
      (call-by-reference)
      (printf "By-reference: ~s~n" (run exp))
      (call-by-name)
      (printf "By-name: ~s~n" (run exp))))

> (define exp
    '(local ((a 1))
       (let ((x a)
	     (y (+ a 1)))
	 (set! x (+ a 1))
	 (set! x y)
	 a)))

> (test exp)

---

		      Discussion of parameter passing

call-by-name
 - allows use of the copy rule (beta-reduction)
 - a.k.a. lazy evaluation
 - memoized version: call-by-need
 - particularly powerful if constructors (e.g. cons) are lazy
 - makes it very difficult to reason about side effects
 - one famous use of call-by-name with side effects
    * Jensen's device for integration
 - default parameter passing mechanism in Algol

call-by-value-result
 - used in Fortran
 - Ada in out declaration may mean call-by-reference or call-by-value-result
 - Ada out declaration is call-by-result

swap procedure as application of call-by-reference

aliasing of data structures and L-values

locatives (first-class L-values)

pointers to L-values possible in C/C++

difference between call-by-reference and passing references to objects by value

reasoning about variable assignment
 - look for assignments in scope with call-by-value
 - must also look for & in C/C++
 - must examine all procedures that are passed a variable by-reference

---

		     Discussion of stack architecture

putting environments on the stack
 - not possible in general with first-class procedures
   * use display closures
   * display closures may take more room than linked environment
     but linked environments may prevent garbage collection
 - static links and dynamic links
   * dynamic links only necessary if stack frame size not know to compiler
     because arrays or other objects of size unknown at compile time are on
     the stack   
 - tail-recursion problem with JSR

---

END

---