CS217 Day 10 Monday, April 17, 2000

Environment Passing Interpreters I

An interpreter is a program that performs some action on a data structure that depends upon its structure. We will begin by developing interpreters for a series of simple languages that have the semantics of Scheme, a lexically scoped language in which procedures are first class objects and which supports recursion and assignment. We will then consider alternative semantics for the meaning of variables and parameter passing.

Our interpreters will act on abstract syntax obtained either by parsing list syntax expressions or character syntax expressions. In order to emphasize the distinction between Scheme and defined languages, we will generally write defined language programs in character syntax and parse to abstract syntax using SLLGEN, although for convenience, we will maintain a parser of list syntax into abstract syntax.

• As a simplest example, consider a language of primitive numerical expressions and no variables. Expressions are numbers or applications of primitive procedures +, -, *, add1, and sub1. Our interpreter will evaluate programs, which are just expressions in this language. BNF for the language:

  [program] ::= [expression]
  
  [expression] ::= [number]
         | [primitive]([expression]{, [expression]}*)
  
  [primitive] ::= + | - | * | add1 | sub1
  

  E.g., 5, +(2, 3) and *(+(2, add1(3)), sub1(4)) are in the language. The values of these expressions should be 5, 5 and 18.

  Abstract syntax for this language can be defined by

  (define-datatype program program?
    (a-program
      (exp expression?)))
  
  (define-datatype expression expression?
    (lit-exp
      (datum number?))
    (primapp-exp
      (prim primitive?)
      (rands (list-of expression?))))
  
  (define-datatype primitive primitive?
    (add-prim)
    (subtract-prim)
    (mult-prim)
    (incr-prim)
    (decr-prim))
  

  SLLGEN, developed by Mitch Wand at Northeastern University, will scan and parse our simplest language into the list representaton of this abstract syntax with the following definitions.

  (define lex-spec
    '((white-sp (whitespace)
        skip)
      (comment ("%" (arbno (not #\newline)))
        skip)
      (id (letter (arbno (or letter digit "?")))
        make-symbol)
      (number (digit (arbno digit))
        make-number)))
  
  (define grammar-3-0
    '((program (expression)
        a-program)
      (expression (number)
        lit-exp)
      (expression
        (primitive "(" (separated-list expression ",") ")")
        primapp-exp)
      (primitive ("+") add-prim)
      (primitive ("-") subtract-prim)
      (primitive ("*") mult-prim)
      (primitive ("add1") incr-prim)
      (primitive ("sub1") decr-prim)))
  
  (define scan&parse
    (sllgen:make-string-parser lex-spec grammar-3-0))
  
  (sllgen:make-define-datatypes lex-spec grammar-3-0)
  
  (define run
    (lambda (string)
      (eval-program (scan&parse string))))
  

  Our interpreter almost writes itself.

  (define eval-program
    (lambda (pgm)
      (cases program pgm
        (a-program (exp)
  	(eval-expression exp)))))
  
  (define eval-expression
    (lambda (exp)
      (cases expression exp
        (lit-exp (datum) datum)
        (primapp-exp (prim rands)
  	(let ((args (map eval-expression rands)))
  	  (cases primitive prim
  	    (add-exp ()
  	      (+ (car args) (cadr args)))
  	    (subtract-exp ()
  	      (- (car args) (cadr args)))
  	    (mult-exp ()
  	      (* (car args) (cadr args)))
  	    (incr-exp ()
  	      (+ (car args) 1))
  	    (decr-exp ()
  	      (- (car args) 1))))))))
  

• cs217d10.scm tests these definitions.

• interp3-1.scm implements the simplest environment passing interpreter, using code in 3-1 and 3-2. The language has variables as well as numbers and primitive applications.

  An environment, in which to look up values of variables, is passed, along with an expression, to eval-expression. Programs are evaluated in an initial environment.

  (define eval-program
    (lambda (pgm)
      (cases program pgm
        (a-program (exp)
  	(eval-expression exp (make-init-env))))))
  

  Assignment 4 is to extend this interpreter by adding more primitive procedures and by implementing and testing if, let and proc.

Start working on Assignment 4, adding primitive procedues.