CS217 Day 12 Friday, April 21, 2000

Environment Passing Interpreters III Local Binding, Procedures

• interp3-3.scm extends interp3-1.scm (Fig 3.1: A simple interpreter) to support if expressions and boolean values true and false.

  The language interpreted has BNF

  [program] ::= [expression]
  [expression] ::= [number]
         | [symbol]
         | [primitive]()
         | [primitive]([expression]{, [expression]}*)
         | if [expression] then [expression] else [expression]
         | [bool]
  [primitive] ::= + | - | * | add1 | sub1 | equal?
  [bool] ::= true | false
  

  Expressed values are those that can be values of expressions.
  Denoted values are those that can be values of variables.

  Expressed Values = Number + Bool
  Denoted Values = Number + Bool

  To obtain inter3-3.scm from interp3-1.scm, we
  • added if-exp and bool-exp to the expression datatype

      (bool-exp
        (bval bool?))
      (if-exp
        (test-exp expression?)
        (true-exp expression?)
        (false-exp expression?))
    

  • added a bool datatype --

    (define-datatype bool bool?
      (true-value)
      (false-value))
    

  • added equal-prim to the primitive datatype
  • added cases clauses to eval-expression for interpreting if-exp and bool-exp, getting

    (define eval-expression
      (lambda (exp env)
        (cases expression exp
          (lit-exp (datum) datum)
          (bool-exp (bval) bval)
          (var-exp (id) (apply-env env id))
          (primapp-exp (prim rands)
    	(let ((args (eval-rands rands env)))
    	  (apply-primitive prim args)))
          (if-exp (test-exp true-exp false-exp)
    	(if (true-value? (eval-expression test-exp env))
    	    (eval-expression true-exp env)
    	    (eval-expression false-exp env)))
          (else
    	(error 'eval-expression "bad exp ~s" exp)))))
    

    making use of

    (define true-value?
      (lambda (x)
        (cases bool x
          (true-value () #t)
          (false-value () #f)
          (else
    	(error 'bool "not a bool" x)))))
    

  • added code to apply-primitive to interpret equal-prim. This is simplified using

    (define bool-value
      (lambda (x)
        (if x (true-value) (false-value))))
    

    Then the clause interpreting equal-prim is just

    (equal-prim () (bool-value (= (car args) (cadr args))))
    

  • added code to parse #t, #f and if to parse-expression

  • added code to unparse bool-exp and if-exp to unparse-expression

  • added code to parse if, true false to grammar-3-1 to get grammar-3-3

        (expression
          ("if" expression "then" expression "else" expression)
          if-exp)
        (expression
          (bool)
          bool-exp)
        (bool ("true") true-value)
        (bool ("false") false-value)
    

  We can test everything with

  (define run-test-all
    (lambda (string)
      (let ((parsed (scan&parse string)))
        (let ((datum (unparse-program parsed)))
  	(newline)
  	(pretty-print string)
  	(display "  or")(newline)
  	(pretty-print datum)
  	(display "  or")(newline)
  	(pretty-print parsed)
  	(display "  => ")
  	(eval-program (parse-program datum))))))
  

  For example,

  (run-test-all "+(if equal?(x, 10) then v else i, x)")
  

  has output, in the environment [i = 1, v = 5, x = 10](empty-env),

  "+(if equal?(x, 10) then v else i, x)"
    or
  (+ (if (= x 10) v i) x)
    or
  (a-program
    (primapp-exp
      (add-prim)
      ((if-exp
         (primapp-exp (equal-prim) ((var-exp x) (lit-exp 10)))
         (var-exp v)
         (var-exp i))
       (var-exp x))))
    => 15
  

• Local Variables

  The defined language is extended to include BNF

  [expression] ::= let {[symbol] = [expression]}+ in expression
  

  which entails
  • adding let-exp to the grammar --

        (expression
          ("let" (arbno id "=" expression) "in" expression)
          let-exp)
    

  • adding let-exp to expression

      (let-exp
        (ids (list-of symbol?))
        (exps (list-of expression?))
        (body expression?))
    

  • adding to eval-expression -- to implement lexical scope

          (let-exp (ids exps body)
    	(let ((args (eval-rands exps env)))
    	  (eval-expression body (extend-env ids args env))))
    

    The variables which are both free in body and in ids have values given by the values of the corresponding exps. Lexical addresses, rather than variable names could be used to look up values in the environment.

  • adding to parse-expression

  • adding to unparse-expression

  Examples of local binding:

  (run-test-all "let a = 2 b = 3 in +(*(a, v), *(b, x))")
  

  has output, in the environment [i = 1, v = 5, x = 10](empty-env),

  "let a = 2 b = 3 in +(*(a, v), *(b, x))"
    or
  (let ([a 2] [b 3]) (+ (* a v) (* b x)))
    or
  (a-program
    (let-exp
      (a b)
      ((lit-exp 2) (lit-exp 3))
      (primapp-exp
        (add-prim)
        ((primapp-exp (mult-prim) ((var-exp a) (var-exp v)))
         (primapp-exp (mult-prim) ((var-exp b) (var-exp x)))))))
    => 40
  

  and

  (run-test-all "let x = 2 in print(list(i, v, x, emptylist))")
  

  has output,

  "let x = 2 in print(list(i, v, x, emptylist))"
    or
  (let ([x 2]) (print (list i v x emptylist)))
    or
  (a-program
    (let-exp
      (x)
      ((lit-exp 2))
      (primapp-exp
        (print-prim)
        ((primapp-exp
           (list-prim)
           ((var-exp i)
            (var-exp v)
            (var-exp x)
            (var-exp emptylist)))))))
    => (1 5 2 ())
  1
  

• Procedures

  The defined language is extended to include BNF for procedure definition and procedure application.

  [expression] ::= proc() [expression]
                 | proc([id]{, [id]}*) [expression]
                 | ([expression] {[expression]}*)
  

  The expressed and denoted values become

  Expressed Values = Number + Bool + Procedure
  Denoted Values = Number + Bool + Procedure

  Defined procedure, unlike primitive procedures (whose application has a different character syntax) are first class objects.

  Implementing procedure definition and application entails

  • adding proc-exp and app-exp to the grammar

        (expression
          ("proc" "(" (separated-list id ",") ")" expression)
          proc-exp)
        (expression
          ("(" expression (arbno expression) ")")
          app-exp)
    

  • adding proc-exp and app-exp to the expression datatype

      (proc-exp
        (ids (list-of symbol?))
        (body expression?))
      (app-exp
        (rator expression?)
        (rands (list-of expression?)))
    

  • adding proc-exp and app-exp to eval-expression
    The value of a procedure will be a closure, a data structure which stores the procedure's ids and body, and the environment in which the procedure is evaluated. This will enable implementing lexical scoping semantics.

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

  • adding a procval datatype with a closure variant and a procedure apply-procval which implements the application of a closure on its arguments.

    (define-datatype procval procval?
      (closure
        (ids (list-of symbol?))
        (body expression?)
        (env environment?)))
    
    (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)))))
    

    A closure is a run-time data structure that exists when the abstract syntax tree of an expression containing the procedure is being evaluated.

  • adding to parse-expression

  • adding to unparse-expression

  Example of procedure definition and application:

  (run-test-all
    "let sqr = proc(x) *(x, x)
     in let cub = proc(x) *(x, (sqr x))
        in +((sqr v), (cub x))")
  

  has output, in the environment [i = 1, v = 5, x = 10](empty-env),

  "let sqr = proc(x) *(x, x)
     in let cub = proc(x) *(x, (sqr x))
        in +((sqr v), (cub x))"
    or
  (let ([sqr (lambda (x) (* x x))])
    (let ([cub (lambda (x) (* x (sqr x)))])
      (+ (sqr v) (cub x))))
    or
  (a-program
    (let-exp
      (sqr)
      ((proc-exp
         (x)
         (primapp-exp (mult-prim) ((var-exp x) (var-exp x)))))
      (let-exp
        (cub)
        ((proc-exp
           (x)
           (primapp-exp
             (mult-prim)
             ((var-exp x) (app-exp (var-exp sqr) ((var-exp x)))))))
        (primapp-exp
          (add-prim)
          ((app-exp (var-exp sqr) ((var-exp v)))
           (app-exp (var-exp cub) ((var-exp x))))))))
    => 1025
  

  Here's another example that uses lists.

  (run-test-all
    "let sqr= proc(x) *(x, x)
         a = list(1, 2, 3)
     in let b = list(car(a), cdr(a))
        in cons(b, list(x, (sqr x), (sqr (sqr x))))")
  

  has output, in the environment [i = 1, v = 5, x = 10](empty-env),

  "let sqr= proc(x) *(x, x)
         a = list(1, 2, 3)
     in let b = list(car(a), cdr(a))
        in cons(b, list(x, (sqr x), (sqr (sqr x))))"
    or
  (let ([sqr (lambda (x) (* x x))] [a (list 1 2 3)])
    (let ([b (list (car a) (cdr a))])
      (cons b (list x (sqr x) (sqr (sqr x))))))
    or
  (a-program
    (let-exp
      (sqr a)
      ((proc-exp
         (x)
         (primapp-exp (mult-prim) ((var-exp x) (var-exp x))))
       (primapp-exp
         (list-prim)
         ((lit-exp 1) (lit-exp 2) (lit-exp 3))))
      (let-exp
        (b)
        ((primapp-exp
           (list-prim)
           ((primapp-exp (car-prim) ((var-exp a)))
            (primapp-exp (cdr-prim) ((var-exp a))))))
        (primapp-exp
          (cons-prim)
          ((var-exp b)
           (primapp-exp
             (list-prim)
             ((var-exp x)
              (app-exp (var-exp sqr) ((var-exp x)))
              (app-exp
                (var-exp sqr)
                ((app-exp (var-exp sqr) ((var-exp x))))))))))))
    => ((1 (2 3)) 10 100 10000)
  

Include tests, such as above, to verify that your interpreter and primitive procedures are working properly.
Place tests at the end or in a separate file.