►Programming Language Design (Fall 2010)
▼3 Assignments
►3.6 Rudimentary Interpreter
On this page:
3.6.1 WAE
3.6.1.1 Datatypes
3.6.1.2 Parser
parse
3.6.1.3 Interpreter
calc
3.6.2 W*AE
3.6.2.1 Datatypes
3.6.2.2 Operator Table
op-table
lookup-op
3.6.2.3 Parser
parse
3.6.2.4 Multiple Substitution
subst*
3.6.2.5 Interpreter
calc
  ← prev  up  next → 

3.6 Rudimentary Interpreter

You must complete this assignment by yourself.

You must submit this in an archive named "rinterp.zip". This archive must contain a folder named "rinterp". This folder must contain all the files specified below. You must attach "rinterp.zip" to an email whose subject is "BYU - Fall 2010 - CS 330 - rinterp" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 9/21. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.

You must complete this assignment using a specific language. Choose Determine language from source in the DrRacket menu, then write
  #lang plai
as the first line of your program, overwritting the default #lang at the top of the file.

3.6.1 WAE

You must submit this in a file named "wae1.rkt".

3.6.1.1 Datatypes

Define the following datatypes:
  (define-type Binding
    [binding (name symbol?) (named-expr WAE?)])
  
  (define-type WAE
    [num (n number?)]
    [add (lhs WAE?) (rhs WAE?)]
    [sub (lhs WAE?) (rhs WAE?)]
    [with (b Binding?) (body WAE?)]
    [id (name symbol?)])

This part requires no test cases.

3.6.1.2 Parser

Write the following function:

(parse s-exp) → WAE?
  s-exp : s-expression?
Parses s-exp into a WAE according to this grammar:

  WAE = number
  | (+ WAE WAE)
  | (- WAE WAE)
  | (with ([id WAE]) WAE)
  | id

where number is a Racket number and id is not '+, '-, or 'with.

Remember, this grammar is for the quoted S-expressions. The Racket data structures will look like:
  WAE = number
  | (list '+ WAE WAE)
  | (list '- WAE WAE)
  | (list 'with (list (list id WAE)) WAE)
  | id

The textbook provides a basic version for you.

You should write test cases for all legal and illegal types of expressions. Here are some examples:
  (test (parse '5) (num 5))
  (test/exn (parse true) "Illegal syntax")
  (test (parse '(+ 1 2)) (add (num 1) (num 2)))
  (test/exn (parse '(+ 1 2 3)) "More than two arguments")
  (test/exn (parse '(with [x 1] x)) "Not a list of bindings")

3.6.1.3 Interpreter

Write the following function:

(calc e) → number?
  e : WAE?
Consumes a WAE representation of an expression and computes the corresponding numerical result.

The textbook provides a basic version for you.

You should write test cases for all legal parse tests and more to demonstrate that substitution works correctly. Here are some examples:
  (test (calc (parse '5)) 5)
  (test (calc (parse '(+ 4 1))) 5)
  (test (calc (parse '(with ([x 5]) x))) 5)

3.6.2 W*AE

You must submit this in a file named "wae2.rkt".

3.6.2.1 Datatypes

Define the following datatypes:
  (define-type Binding
    [binding (name symbol?) (named-expr WAE?)])
  
  (define-type WAE
    [num (n number?)]
    [binop (op procedure?)
           (lhs WAE?)
           (rhs WAE?)]
    [with (lob (listof Binding?)) (body WAE?)]
    [id (name symbol?)])

This part requires no test cases.

3.6.2.2 Operator Table

Define a data-structure to contain a mapping from operator symbols to their definitions.

op-table : (listof (list/c symbol? (number? number? . -> . number?)))

For example,
  (define op-table
    (list (list '+ +)))

Populate it with mappings for '+, '-, '*, and '/.

Define a function that extracts the definition of an operator or false:

(lookup-op op) → (or/c procedure? false/c)
  op : symbol?

You will find the Racket function assoc useful.

You should write tests for each of the operators listed above and a few to check other symbols. For example:
  (test (lookup-op '+) +)
  (test (lookup-op '-) -)

3.6.2.3 Parser

Write the following function:

(parse s-exp) → WAE?
  s-exp : s-expression?
Parses s-exp into a WAE according to this grammar:

  WAE = number
  | (+ WAE WAE)
  | (- WAE WAE)
  | (* WAE WAE)
  | (/ WAE WAE)
  | (with ([id WAE] ...) WAE)
  | id

where number is a Racket number and id is not '+, '-, '*, '/, or 'with.

Remember, this grammar is for the quoted S-expressions. The Racket data structures will look like:
  WAE = number
  | (list '+ WAE WAE)
  | (list '- WAE WAE)
  | (list '* WAE WAE)
  | (list '/ WAE WAE)
  | (list 'with (list (list id WAE) ...) WAE)
  | id

Your parser must call lookup-op.

You will find the Racket functions length, andmap, symbol?, list?, symbol=?, and map useful.

It is not a parse error for an identifier to appear multiple times in a with:
  (test (parse '(with ([x 1] [x 2]) (+ x x)))
        (with (list (binding 'x (num 1))
                    (binding 'x (num 2)))
              (binop + (id 'x) (id 'x))))

You should write test cases for all legal and illegal types of expressions. Here are some examples:
  (test (parse '5) (num 5))
  (test/exn (parse true) "Illegal syntax")
  (test (parse '(+ 1 2)) (binop + (num 1) (num 2)))
  (test/exn (parse '(+ 1 2 3)) "Illegal syntax")
  (test/exn (parse '(with [x 1] x)) "Illegal syntax")

3.6.2.4 Multiple Substitution

Write the following function:

(subst* lob body) → WAE?
  lob : (listof Binding?)
  body : WAE?
Substitutes for all of the bindings in lob inside body simultaneously.

You will find looking at your previous subst function useful.

You will find the Racket functions andmap, filter, and map useful.

You should write test cases for this function. Here are some examples:
  (test (subst* (list (binding 'x (num 1))) (id 'x))
        (num 1))
  (test (subst* (list (binding 'x (num 1))
                      (binding 'y (id 'x)))
                (binop + (id 'x) (id 'y)))
        (binop + (num 1) (id 'x)))

3.6.2.5 Interpreter

Write the following function:

(calc e) → number?
  e : WAE?
Consumes a WAE representation of an expression and computes the corresponding numerical result.

You will find the Racket functions map useful.

It is an interpretation error for an identifier to appear multiple times:
  (test/exn (calc (parse '(with ([x 1] [x 2]) (+ x x))))
            "Multiple bindings")

You will find the functions ormap and symbol=? to detect errors like this.

You should write test cases for all legal parse tests and more to demonstrate that substitution works correctly. Here are some examples:
  (test (calc (parse '5)) 5)
  (test (calc (parse '(+ 4 1))) 5)
  (test (calc (parse '(with ([x 5]) x))) 5)

  ← prev  up  next →