C311 script5.txt -- 9/30/96 

---

RECURSION

It is simplest to understand recursion in terms of the expansion of letrec:

(letrec ((var_1 exp_1) ... (var_n exp_n)) body) ==>

(let ((var_1 'ignored) ... (var_n 'ignored))
  (set! var_1 exp_1)
  ...
  (set! var_n exp_n)
  body)

+++

or as in the book:

(letrec ((var_1 exp_1) ... (var_n exp_n)) body) ==>

(let ((var_1 'ignored) ... (var_n 'ignored))
  (let ((v_1 exp_1) ... (v_n exp_n))
    (set! var_1 v_1)
    ...
    (set! var_n v_n)I'm quite happy declaring all types wherever necessary. The expressive
power of a type system shouldn't be limited by what is inferable. 

    body))

This version does not allow any references to var_1, ..., var_n while
evaluating exp_1, ..., exp_n, while the first version allows reference
to var_i in exp_j when i < j.

---

Remember, variables occurring free in a lambda expression can only be
referenced when the resulting closure is invoked, not when the lambda
expression is evaluated.

+++

Letrec builds a circular data structure (picture on board).

---

Read the letrecproc material in section 5.6 for the general idea (not
responsible for the details).  This shows it is possible to implement
recursion without using assignment.  It requires that the declaration
expressions be procedures, and delays formation of the closure until its
variable is referenced in the environment.  

+++

Does recursion require the support of some special purpose mechanism, such
as LETREC or DEFINE?  Is recursion possible in the lambda calculus?

---

RECURSION IN THE LAMBDA CALCULUS

(define g
  (lambda (n) 
    (if (zero? n) 1 (* n (g (- n 1))))))

g = (lambda (n) (if (zero? n) 1 (* n (g (- n 1)))))
 
g itself must be lambda-bound

f = (lambda (g)
      (lambda (n) 
        (if (zero? n) 1 (* n (g (- n 1))))))

Can we define a function Y such that (Y f) is the desired 
procedure g, or must Y be primitive?  Must have

(Y f) = g = (f g) = (f (Y f)), so we must have (Y f) = (f (Y f))

Y can be expressed as

(lambda (f)
  ((lambda (x) (f (x x)))
   (lambda (x) (f (x x)))))

This works in the lambda calculus with "normal-order reduction" (basically
call-by-name, introduced in Chapter 6).  It does not work with
"applicative-order reduction", as in most languages, including Scheme. An
applicative-order Y combinator is obtained by eta-converting (x x) terms:

> (define Y 
    (lambda (f)
      ((lambda (x) (f (lambda (y) ((x x) y))))
       (lambda (x) (f (lambda (y) ((x x) y)))))))
> (define f
    (lambda (g)
      (lambda (n) 
        (if (zero? n) 1 (* n (g (- n 1)))))))
> (define fact (Y f))
> (fact 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

---

Mutual recursion by having f represent a record with the procedures in 
its fields. 

---

DYNAMIC SCOPE

> (begin
    (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 apply-proc
      (lambda (proc args)
	(if (pair? proc)
	  (record-case proc
	    (prim-proc (prim-op) (apply-prim-op prim-op args))
	    (else (error 'apply-proc "Invalid procedure: ~s" proc)))
	  (error 'apply-proc "Invalid procedure: ~s" proc))))
    (define decl->var car)
    (define decl->exp cadr)
    (define expand
      (lambda (exp)
	(cond
	  ((literal? exp) (list 'quote exp))
	  ((variable? exp) exp)
	  (else
	    (record-case exp
	      (quote (datum) datum)
	      (let (decls body)
		(let ((vars (map decl->var decls))
		      (exps (map decl->exp decls)))
		  (expand (cons (list 'lambda vars body) exps))))
	      (lambda (formals body)
		(list 'lambda formals (expand body)))
	      (else (map expand exp)))))))
    (define make-closure
      (lambda (formals body env)
	(list 'closure formals body env)))
    (define eval-rands
      (lambda (rands env)
	(map (lambda (exp) (eval-exp exp env))
	  rands)))
    (define run
      (lambda (exp)
	(eval-exp (expand exp) init-env))))

> (define eval-exp
    (lambda (exp env)
      (if (variable? exp) (apply-env env exp)
	(record-case exp
	  (quote (datum) datum)
	  (lambda (formals body) (make-closure formals body env))
	  (else
	    (let ((proc (eval-exp (app->rator exp) env))
		  (args (eval-rands (app->rands exp) env)))
	      (apply-proc proc args env))))))) ; CHANGE

> (define apply-proc
    (lambda (proc args env^) ; CHANGE
      (record-case proc
	(prim-proc (prim-op) (apply-prim-op prim-op args))
	(closure (formals body env)
	  (eval-exp body (extend-env formals args env)))
	(else (error 'apply-proc "Invalid procedure: ~s" proc)))))

> (run '(let ((x 3))
	  (let ((f (lambda () x)))
	    (let ((x 4))
	      (f)))))
3
> (define apply-proc
    (lambda (proc args env^) ; CHANGE
      (record-case proc
	(prim-proc (prim-op) (apply-prim-op prim-op args))
	(closure (formals body env)
	  (eval-exp body (extend-env formals args env^)))
	(else (error 'apply-proc "Invalid procedure: ~s" proc)))))

> (run '(let ((x 3))
	  (let ((f (lambda () x)))
	    (let ((x 4))
	      (f)))))
4
> (define eval-exp
    (lambda (exp env)
      (if (variable? exp) (apply-env env exp)
	(record-case exp
	  (quote (datum) datum)
	  (lambda (formals body) exp)  ; CHANGE
	  (else
	    (let ((proc (eval-exp (app->rator exp) env))
		  (args (eval-rands (app->rands exp) env)))
	      (apply-proc proc args env)))))))

> (define apply-proc
    (lambda (proc args env^)
      (record-case proc
	(prim-proc (prim-op) (apply-prim-op prim-op args))
	(lambda (formals body) ; CHANGE
	  (eval-exp body (extend-env formals args env^)))
	(else (error 'apply-proc "Invalid procedure: ~s" proc)))))

> (run '(let ((x 3))
	  (let ((f (lambda () x)))
	    (let ((x 4))
	      (f)))))
4

---

What variable binding do we get with dynamic scope?

+++

As we've seen, not always the same as lexical scope.

Not always the most recently made binding of the variable: e.g.

> (run '(let ((x 3))
	  (let ((f (lambda () x)))
	    (let ((y (let ((x 4)) 5)))
	      (f)))))
3

---

Not always the binding that is in the lexical scope of the most recent
point of call, e.g.

> (run '(let ((x 3))
	  (let ((f (lambda () x)))
	    (let ((g (lambda () (f))))
	      (let ((x 4))
		(g))))))
4

---

With dynamic scope you get most recent EXTANT binding of the variable,
where binding is extant during evaluation of the body (including the
declarations in the case of letrec) of the body of the form that introduced
the binding.

One way of thinking about, and implementing, dynamic scope is with the
environment represented by a stack.

---

TOWARDS A STACK-BASED ENVIRONMENT

> (define contract-env cadddr)

> (define env init-env)

> (define eval-exp
    (lambda (exp)
      (if (variable? exp) (apply-env env exp)	
	(record-case exp
	  (quote (datum) datum)
	  (lambda (formals body) exp)
	  (else
	    (let ((proc (eval-exp (app->rator exp)))
		  (args (map eval-exp (app->rands exp))))
	      (apply-proc proc args)))))))

> (define apply-proc
    (lambda (proc args)
      (record-case proc
	(prim-proc (prim-op) (apply-prim-op prim-op args))
	(lambda (formals body)
	  (set! env (extend-env formals args env)) ; PUSH
	  (let ((answer (eval-exp body)))
	    (set! env (contract-env env)) ; POP
	    answer))	
	(else (error 'apply-proc "Invalid procedure: ~s" proc)))))

> (define run
    (lambda (exp)
      (eval-exp (expand exp))))

> (run '(let ((x 3))
	  (let ((f (lambda () x)))
	    (let ((x 4))
	      (f)))))
4

---

What about efficiency?

+++

Variable lookup is linear in the depth of the binding.

This sort of implementation is called DEEP BINDING.

Another appoach, called SHALLOW BINDING, uses DYNAMIC (OR "FLUID")
ASSIGNMENT.

+++

In Chez Scheme:

(fluid-let ((var_0 exp_0) ... (var_n exp_n)) body) ==>

(let ((v_0 var_0) ... (v_n var_n))
  (set! var_0 exp_0)
  ...
  (set! var_n exp_n)
  (let ((answer body))
    (set! var_0 v_0)
    ...
    (set! var_n v_n)
    answer))

> (let ((x 3))
    (let ((f (lambda () x)))
      (fluid-let ((x 4))
	(f))))
4

---

Compare the efficiency of procedure calls under shallow and deep binding.

+++

Shallow is more expensive, but procedure calls are generally less common
than variable references.

Shallow binding also has the serious problem that it blows tail recursion
(to be discussed later).

---

What is dynamic binding good for?

+++

Binding exception handlers and I/O parameters (such as standard ports, line
length, and print depth).

In general, dynamic scope is much harder to reason with than static scope.

But it sometimes avoids the need to pass thees paramters around through
procedures that may not even need to use them directly, which may increase
program modularity and clarity.

---

What languages use dynamic binding?

+++

Java dynamically binds exception handlers (more on that later). 

Lisp uses dynamic binding (though Common Lisp allows statically scoped
procedures to be created and invoked using special sytnax).

The TeX typsetting language uses dynamic binding extensively.

Some Basic systems use dynamic scope, as does APL.

---

END

---