CS217 Day 14 Wednesday, April 26, 2000

Recursion II

• We introduced letrec expressions to define recursive or mutually recursive functions in our defined language. BNF for the character syntax is:

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

  Potentially mutually recursive functions f1,... with parameter lists (x1,...),... and bodies E1,... are defined in E1,... and E by

  letrec f1(x1,...) = E1
         ...
  in E
  

  Free occurrences of f1,... in E1,... and in E are bound to proc (x1,...) E1,....

  The application

  (f1 a1...)
  

  is evaluated by evaluating E1 in the environment of the letrec extended by f1,..., with free occurrences of x1,... bound to the values of a1,....
  The grammar for the concrete syntax is:

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

  and the define-datatype for expression contains the clause

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

• For example, 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)
  

  And

  letrec f(x) = if zero?(x) then 1 else *(2, (f sub1(x)))
         g(x, y) = if zero?(x) then y else (g sub1(x) *(2, y))
         h(x) = (g x 1)
  in
    list((f 5), (g 5 1), (h 5))
  

  defines recursive functions f and g, and h is terms of g, and uses them in the body of the letrec.

  What do these functions compute?
  What is the value of the expression?
  Compare the concrete, list and abstract syntax for these functions:

  letrec f(x) = if zero?(x) then 1 else *(2, (f sub1(x)))
         g(x, y) = if zero?(x) then y else (g sub1(x) *(2, y))
         h(x) = (g x 1)
  in list((f 5), (g 5 1), (h 5))
  
    or
  
  (letrec ([f
            (lambda (x) (if (zero? x) 1 (* 2 (f (sub1 x)))))]
           [g (lambda (x y) (if (zero? x) y (g (sub1 x) (* 2 y))))]
           [h (lambda (x) (g x 1))])
    (list (f 5) (g 5 1) (h 5)))
  
    or
  
  (a-program
    (letrec-exp
      (f g h)
      ((x) (x y) (x))
      ((if-exp
         (primapp-exp (zero-prim) ((var-exp x)))
         (lit-exp 1)
         (primapp-exp
           (mult-prim)
           ((lit-exp 2)
            (app-exp
              (var-exp f)
              ((primapp-exp (decr-prim) ((var-exp x))))))))
       (if-exp
         (primapp-exp (zero-prim) ((var-exp x)))
         (var-exp y)
         (app-exp
           (var-exp g)
           ((primapp-exp (decr-prim) ((var-exp x)))
            (primapp-exp (mult-prim) ((lit-exp 2) (var-exp y))))))
       (app-exp (var-exp g) ((var-exp x) (lit-exp 1))))
      (primapp-exp
        (list-prim)
        ((app-exp (var-exp f) ((lit-exp 5)))
         (app-exp (var-exp g) ((lit-exp 5) (lit-exp 1)))
         (app-exp (var-exp h) ((lit-exp 5)))))))
  
    => (32 32 32)
  

• It is instructive to evaluate

  letrec f(x) = if zero?(x) then 1 else *(2, (f sub1(x)))
         g(x, y) = if zero?(x) then y else (g sub1(x) *(2, y))
         h(x) = (g x 1)
  in (g 0 1)
  

  with tracing of eval-rands turned on.

  eval-rands is called to evaluate the operands of

  • (g 0 1) in the init env extended by the recursive env, and of
  • zero?(x) in the recursive env extended by [x = 0, y = 1]
  There is no recursive call -- the value of y is returned.
  Here is the trace:

  |(eval-rands
     ((lit-exp 0) (lit-exp 1))
     (extended-env-recursively-record
       (f g h)
       #3((x) (x y) (x))
       #3((if-exp
            (primapp-exp (zero-prim) ((var-exp x)))
            (lit-exp 1)
            (primapp-exp
              (mult-prim)
              ((lit-exp 2)
               (app-exp (var-exp f) ((primapp-exp (decr-prim) ((var-exp x))))))))
          (if-exp
            (primapp-exp (zero-prim) ((var-exp x)))
            (var-exp y)
            (app-exp
              (var-exp g)
              ((primapp-exp (decr-prim) ((var-exp x)))
               (primapp-exp (mult-prim) ((lit-exp 2) (var-exp y))))))
          (app-exp (var-exp g) ((var-exp x) (lit-exp 1))))
       (extended-env-record (i v x emptylist) #4(1 5 10 ()) (empty-env-record))))
  |(0 1)
  |(eval-rands
     ((var-exp x))
     (extended-env-record
       (x y)
       #2(0 1)
       (extended-env-recursively-record
         (f g h)
         #3((x) (x y) (x))
         #3((if-exp
              (primapp-exp (zero-prim) ((var-exp x)))
              (lit-exp 1)
              (primapp-exp
                (mult-prim)
                ((lit-exp 2)
                 (app-exp
                   (var-exp f)
                   ((primapp-exp (decr-prim) ((var-exp x))))))))
            (if-exp
              (primapp-exp (zero-prim) ((var-exp x)))
              (var-exp y)
              (app-exp
                (var-exp g)
                ((primapp-exp (decr-prim) ((var-exp x)))
                 (primapp-exp (mult-prim) ((lit-exp 2) (var-exp y))))))
            (app-exp (var-exp g) ((var-exp x) (lit-exp 1))))
         (extended-env-record
           (i v x emptylist)
           #4(1 5 10 ())
           (empty-env-record)))))
  |(0)
  1
  

  We have used an extended-env-recursively-record to represent a recursive environment.

• How is a letrec-exp evaluated?
  • The clause in eval-expression can be just

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

    The magic is in the definition of extend-env-recursively.

  • We choose to extend the environment data type.

    (define-datatype environment environment?
      (empty-env-record)
      (extended-env-record
        (syms (list-of symbol?))
        (vec vector?)
        (env environment?))
      (extended-env-recursively-record
        (proc-names (list-of symbol?))
        (ids-vec vector?)
        (body-vec vector?)
        (env environment?)))
    

  • extend-env-recursively creates an extended-env-recursively-record.

    The value of a recursively defined procedure will be a closure, but we choose to create the closure when the value of the function is requested in apply-exp.

    (define extend-env-recursively
      (lambda (proc-names idss bodies env)
        (extended-env-recursively-record
          proc-names
          (list->vector idss)
          (list->vector bodies)
          env)))
    

  • The semantics is encapsulated in apply-env.

    A recursive function is evaluated by creating a closure whose environment is its environment of definition extended by the recursive environment containing the function.

    A variable which is not one of the recursively defined functions is looked up in the environment of the letrec.

    (define apply-env
      (lambda (env sym)
        (cases environment env
          (empty-env-record ()
    	(error 'empty-env "no association for symbol ~s" sym))
          (extended-env-record (syms vec env)
    	(let ((position (list-find-position sym syms)))
    	  (if (number? position)
    	      (vector-ref vec position)
    	      (apply-env env sym))))
          (extended-env-recursively-record (proc-names ids-vec body-vec env0)
    	(let ((position (list-find-position sym proc-names)))
    	  (if (number? position)
    	      (closure
    		(vector-ref ids-vec position)
    		(vector-ref body-vec position)
    		env)
    	      (apply-env env0 sym)))))))
    

• interp3-6sol.scm

Midterm on Friday
There will be an in-class part and a take-home part due next Wednesday.

Be able to
• compute lexical addresses.
• write/use BNF for char/list syntax of our defined language
• write/use grammar for char syntax
• parse/unparse (convert between char, list, abstract syntax)
• draw abstract syntax trees
• write and evaluate programs in the defined language using either lexical or dynamic binding
• evaluate lit-exp, var-exp, bool-exp, primapp-exp, if-exp, let-exp, letrec-exp, proc-exp and app-exp expressions