CS217 Day 13 Monday, April 24, 2000

Lexical vs Dynamic Binding, Recursion I

Lexical vs Dynamic Binding

• The value of a proc-exp is a closure.

        (proc-exp (ids body)
  	(closure ids body env))
  

  where we have defined closure as a kind of procval by

  (define-datatype procval procval?
    (closure
      (ids (list-of symbol?))
      (body expression?)
      (env environment?)))
  

  To implement lexical binding in procedure applications, we evaluate the body of the procedure in its environment of definition, extended by binding its formals to the values of the operands.

        (app-exp (rator rands)
  	(let ((proc (eval-expression rator env))
  	      (args (eval-rands rands env)))
  	  (apply-procval proc args)))
  

  where

  (define apply-procval
    (lambda (proc args)
      (cases procval proc
        (closure (ids body env)
  	(eval-expression body (extend-env ids args env)))
        (else
  	(error 'procval "Not a procedure ~s" proc)))))
  

• Dynamic binding is a binding mechanism for procedure calls in which free variables in the body are evaluated in the environment of the procedure call.

  Dynamic binding can be implemented by passing the current environment to apply-procval and evaluating the body in the environment obtained by extending that environment rather than the environment of definition. I.e.,

        (app-exp (rator rands)
  	(let ((proc (eval-expression rator env))
  	      (args (eval-rands rands env)))
  	  (apply-procval proc args env)))
  

  and

  (define apply-procval
    (lambda (proc args env)
      (cases procval proc
        (closure (ids body env0)
  	(eval-expression body (extend-env ids args env)))
        (else
  	(error 'procval "Not a procedure ~s" proc)))))
  

• Examples of lexical vs dynamic binding (Cf Ex 3.5.11,13, p82)

  Cf Ex 3.5.11

  let a = 1
  in let a = 3
     in let p = proc (x) +(x, a)
            a = 5
        in *(a, (p 2))
  
    => ? (lexical binding)
    => ? (dynamic binding)
  

  Ex 3.5.13 -- illustrates difficulty in understanding behavior with dynamic binding.

  let a = 1 in
    let a = 3
        p = proc () a
    in let f = proc (x) (p)
           a = 5
       in (f 2)
  
    => ? (lexical binding)
    => ? (dynamic binding)
  

  Replacing formal parameter x with a

  let a = 1 in
    let a = 3
        p = proc () a
    in let f = proc (a) (p)
           a = 5
       in (f 2)
  
    => ? (lexical binding)
    => ? (dynamic binding)
  

• Recursion is easy with dynamic binding -- recursive procedures can be bound with let. (Early Lisps used dynamic binding. Scheme was first Lisp with lexical binding, followed by Common Lisp.)

  What is behavior (Cf Ex 3.5.12, p 82) with lexical, dynamic binding of the following?

  let fact = proc (n) add1(n)
  in
    let fact = proc (n)
                 if zero?(n)
                 then 1
                 else *(n, (fact sub1(n)))
    in
      (fact 5)
  
    => ? (lexical binding)
    => ? (dynamic binding)
  

• Recursion can be simulated with lexical binding and first class functions by including an extra parameter to pass the "recursive" function.

  Consider the example from p80.

  let makemult = proc (maker, x)
                  if zero?(x)
                  then 0
                  else +(4, (maker maker sub1(x)))
  in
    let times4 = proc (x) (makemult makemult x)
    in
      (times4 3)
  

  What is the value of this program?

  A recursive function f has a definition of the form

  f = proc(x) (e f x)
  

  E.g.

  times4 = proc (x)
             if zero?(x)
             then 0
             else +(4, (times4 x))
  

  We can abstract the body and rewrite the above definition of times4 as

  let
    e = proc (f, x)
          if zero?(x)
          then 0
          else +(4, (f sub1(x)))
  in
    let
      fm = proc (m, x)
            (e 
              proc(x) (m m x)
              x)
    in
      let times4 = proc (x) (fm fm x)
      in
        (times4 3)
  

  Ex 3.5.3, p 80 -- Write a procedure for factorial using this idea

• cs217d13.dl

Recursion I

• We introduce a letrec syntax to define recursive functions.

  [expression] ::= letrec {[letrec-decl]}* in [expression]
  
  [letrec-decl] ::= [symbol]() = [expression]
                  | [symbol]([symbol] {, [symbol]}*) = [expression]
  

  will be represented in abstract syntax by the grammar

      (expression
        ("letrec"
         (arbno id "(" (separated-list id ",") ")"
  	 "=" expression)
         "in" expression)
        letrec-exp)
  

  or expression datatype

  (letrec-exp
    (proc-names (list-of symbol?))
    (idss (list-of (list-of symbol?)))
    (bodies (list-of expression?))
    (letrec-body expression?))
  

  E.g, a recursive definition and application of times4 could be expressed

  letrec times4(x) = if zero?(x)
                     then 0
                     else +(4, (times4 sub1(x)))
  in
    (times4 3)
  

• A letrec-exp can be evaluated with

  (letrec-exp (proc-names idss bodies letrec-body)
    (eval-expression letrec-body
      (extend-env-recursively proc-names idss bodies env)))
  

  We just need to define extend-env-recursively to get the desired semantics.

Continued on Wednesday