` CSE 341 Assignment 4 (Autumn 2003)  

CSE 341 -- Programming Languages

Autumn 2003

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 4

Version 1.02 (a minor correction involving == was made on Nov 3 to version 1.01 of 23 October

Building an Interpreter 

Due dates and times: Part I: Monday, November 3, as hardcopy, in class. Part II: Web-based turn-in on Wednesday, Nov. 5, at 11:59 PM. .

 

Title: Building an Interpreter.

Purposes: Pre-Part I: Gain a perspective on functional programming and, specifically, on lazy evaluation, that will help with implementing the Part II interpreter. Part I: Begin to learn the ML language.
Part II: Implement an evaluator for a new language to gain a deeper understanding of the core of an interpretive language.

Instructions: 
 

Pre-Part I (Reading Only)

Read sections 0 through 2 of the tutorial paper by David Wise, entitled "Interpreters for Functional Programming." His guest lecture on October 31 will focus on sections 1.5, 1.6, 2.1, and 2.3. Read this material prior to class on October 31.
 

Part I (Individual Work)

Read Elements of ML Programming by Jeffrey D. Ullman, pages iii-v, 1-100, 143-179, 193-204. Do the following exercises in that book: Evaluation: This part is worth approximately 30 points, with an actual point breakdown to be determined later.

 

Part II (Group Work)

Groupings for this assignment have been made by the INFACT group-formation algorithm, using any preference information you have entered in INFACT for who you want to work with. (You'll have another opportunity to express your preferences before the next group assignment.)
Each group should create and turn in one solution to the problem.
 
Implement an interpreter in Lisp for the TAGL language that is described below. 
1. A TAGL expression is either
 a. an integer in the range 0 to 63.
 b. a TAGL symbol (representing a variable or an operator)
 c. a TAGL list, consisting of an even number of
     top-level elements separated by spaces and
     surrounded by parentheses.  The elements in
     even positions are special tokens called TAGs.
     The elements in odd-numbered positions are
     TAGL expressions.  Additional restrictions on
     TAGL lists are described below.

2. The possible TAGs are:
    OP, ARG1, ARG2, CONDITION, THEN, ELSE,
    VAR1, VAL1, VAR2, VAL2, FORM1, FORM2.

3. A TAGL list always contains OP as one of its tags,
   and the element immediately following OP must be
   one of the following TAGL symbols that represent
   operators:
     +, *, -, ==  (which represent TAGL functions)
     IF, PROG2, BIND  (which represent control structures).
     OUTPUT (a way to print out a value)
TAGL stands for "TAGged Language". The idea of TAGL is that you never have to remember the order for arguments in TAGL's function calls or special forms, because you simply put a tag in front of each expression in the calling form to tell which role it plays. Here is a sample program in Lisp: 
(let ((x 5)(y 15))
  (if (= x 5)
    (mod (* x y) 64)
    (mod (+ x y) 64)
 ) )
Here are two equivalent programs in TAGL: In the first, the various elements are in a traditional order. 
(op bind var1 x val1 5 var2 y val2 15
  form1 (op if condition (op == arg1 x arg2 y)
               then (op * arg1 x arg2 y)
               else (op + arg1 x arg2 y)))
And here is the second program. In this one, the order of elements within lists has been reversed, except that tags must always stay in front of the elements that they identify. 
(form1 (else (arg2 y arg1 x op +)
        then (arg2 y arg1 x op *)
        condition (arg2 y arg1 x op ==)
        op if)
  val2 15
  var2 y
  val1 5
  var1 x
  op bind)
Notice also that we don't need to specify the MOD 64 part of the arithmetic. To make things interesting, TAGL always does its arithmetic MOD 64.

Here is how to handle the operators: The functions +, *, ==, and - should be considered to be binary operators. The *,+, and - functions return their results modulo 64. For example 

(arg2 10 arg1 7 op *)
evaluates to 6, because 7 times 10 is 70, but 70 mod 64 is 6.

The == function returns 1 if its arguments are equal and 0 otherwise.

The special form BIND is like a limited version of Lisp's LET form. It can bind at most two local variables, and it can have at most two top-level forms in its body. For example, a call in the normal order might be: 

(OP BIND
  VAR1 X
  VAL1 5
  VAR2 Y
  VAL2 10
  FORM1 (OP * ARG1 X ARG2 Y))
If there is only one variable, then the tags for it and its value must be VAR1 and VAL1.

The special form PROG2 is like a limited version of Lisp's PROGN. It takes exactly two forms as arguments, tagged with FORM1 and FORM2. For example: 

(OP PROG2
   FORM1 (OP + ARG1 X ARG2 1)
   FORM2 (OP * ARG1 X ARG2 2))

To evaluate an IF form, we first evaluate the condition if the result is nonzero, then the THEN expression is evaluated and returned; otherwise the ELSE expression is evaluated and returned.

To evaluate an OUTPUT form, we evaluate one argument (tagged with ARG1) and print out the word OUTPUT followed by the value.

TAGL is like Lisp in that you can build programs by nesting expressions within expressions.

The rules of evaluation in TAGL are: 

1. If the expression is a number, then the number is returned.
2. If the expression is a variable, then the binding of that variable
 is returned, and if there are multiple bindings, the lexically closest
 binding that is in scope is returned.  If there is no binding for
 the variable, then an error message should be printed: "YOU DID NOT
 BIND VARIABLE X HERE" (assuming X is the variable that is not bound).
3. If the expression is a TAGL list, but there is no operator, then
 an error message "IMPROPER TAGL LIST" should be printed.
4. If the operator in the expression is a function, then the
 arguments are recursively evaluated in the order ARG1 first, then ARG2,
 and then the function is applied to the results.
5. If the operator is one of the special forms IF, BIND, PROG2,
 then execution works as described above for each case.
6. If there are two few or two many arguments, variables, values or
 forms to any operator, an error message should be printed:
 "WRONG NUMBER OF ARGUMENTS TO OPERATOR op" Where op is the operator.
Limitations: TAGL is a small language. There are no facilities in it for defining callable functions, no looping, no list processing, no closures, no QUOTE, no input, and no assignment.
 
Here are some of the test cases we will use to evaluate your programs. We may use others, too. 
(defun test1 () (tagl-eval '
 (op + arg1 63 arg2 62)) )

(defun test2 () (tagl-eval '
  (op bind var1 x val1 5 var2 y val2 15
    form1 (op if condition (op == arg1 x arg2 y)
              then (op * arg1 x arg2 y)
              else (op + arg1 x arg2 y)))
) )

(defun test3 () (tagl-eval '
  (form1 (else (arg2 y arg1 x op +)
          then (arg2 y arg1 x op *)
          condition (arg2 y arg1 x op ==)
          op if)
    val2 15
    var2 y
    val1 5
    var1 x
    op bind)
) )

(defun test4 () (tagl-eval '
  (op bind var1 x 
    val1 25
    form1 (op * arg1 x arg2 x) 
    form2 (op bind var1 x val1 10 form1 (op * arg1 x arg2 x)))
) )

(defun test5 () (tagl-eval '
  (op prog2 form1 (op output arg1 5)
            form2 (op + arg1 5 arg2 7))))

(defun test6 () (tagl-eval '
  (op bind var1 x var2 y
    form1
    (op bind var1 x var2 y
        form1
        (op prog2
          form1 (op output arg1 x)
          form2 (op output arg1 y) )
        form2
         (op + arg1 x arg2 y)
        val1 (op * arg1 x arg2 x)
        val2 (op * arg1 y arg2 y) )
    val1 20
    val2 21)
) )

;(test1)
; 61
;(test2)
; 20
;(test3)
; 20
;(test4)
; 36
;(test5)
; OUTPUT: 5
; 12
;(test6)
; OUTPUT: 16
; OUTPUT: 57
; 9
Requirements: Your main evaluation function should be called TAGL-EVAL and take one argument: a TAGL expression to be evaluated. All your functions for the evaluator should be in a file named a4p2.lsp.

Evaluation: Part II is worth approximately 30 points, with 25 for a working program that handles all the test cases and 5 points for style: clear design and implementation, and good comments and/or documentation strings.