►Programming Language Design (Fall 2012)
▼3 Assignments
►3.4 Rudimentary Interpreter
On this page:
3.4.1 WAE
3.4.1.1 Datatypes
3.4.1.2 Parser
parse
3.4.1.3 Interpreter
calc
3.4.2 W*AE
3.4.2.1 Datatypes
3.4.2.2 Operator Table
op-table
lookup-op
3.4.2.3 Parser
parse
3.4.2.4 Multiple Substitution
subst*
3.4.2.5 Interpreter
calc
    ← prev  up  next → 

3.4 Rudimentary Interpreter

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.4.1 WAE
3.4.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.4.1.2 Parser

Write the following function:

procedure

(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.4.1.3 Interpreter

Write the following function:

procedure

(calc e) → number?

  e : WAE?
Consumes a WAE representation of an expression and computes the corresponding numerical result, eagerly.

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.4.2 W*AE
3.4.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.4.2.2 Operator Table

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

value

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:

procedure

(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.4.2.3 Parser

Write the following function:

procedure

(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.4.2.4 Multiple Substitution

Write the following function:

procedure

(subst* lob body) → WAE?

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

You may assume that lob (the argument to subst*) only contains bindings to num objects. (This assumption must be obeyed by the other code you write.)

You will find using your previous subst function useful.

You will find the Racket function foldr 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 (num 2)))
              (binop + (id 'x) (id 'y)))
      (binop + (num 1) (num 2)))

3.4.2.5 Interpreter

Write the following function:

procedure

(calc e) → number?

  e : WAE?
Consumes a WAE representation of an expression and computes the corresponding numerical result, eagerly.

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 →