2.6 Rudimentary Interpreter

You must complete this assignment by yourself.

You must submit this in an archive named "rinterp.zip".

You must complete this assignment in the PLAI Scheme language. You can do so by choosing it from the Language|Choose Language... menu in DrScheme or via the language chooser at the bottom-left. You can also choose the Module language and have the following as the first line of your program:

#lang planet plai/plai

2.6.1 WAE

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

2.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.

2.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 Scheme number and id is not '+, '-, or 'with.

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")

2.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)

2.6.2 W*AE

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

2.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.

2.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 Scheme 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 '-) -)

2.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:

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

Your parser must call lookup-op.

It is not a parse error for an identifier to appear multiple times:

(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)) (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")

2.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.

You will find calling your previous subst function 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)))

2.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.

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 →

1	Introduction
2	Assignments
3	Lectures
4	Help
5	Turn In Policy
6	Readings
7	Software
8	Exams
9	Grading
10	Your Final Grade
11	Team Work
12	Codewalks
13	Advice

2.1	Musical Notation
2.2	Survey
2.3	Basic Scheme
2.4	Lists and Trees
2.5	Higher-order Functions
2.6	Rudimentary Interpreter
2.7	Substitution
2.8	Extended Interpreter
2.9	Laziness and Infinite Data
2.10	Laziness
2.11	Raw Web Programming
2.12	Language Design
2.13	Continuations
2.14	PLT Web Programming
2.15	Garbage Collectors
2.16	Garbage Collection
2.17	Type Checking
2.18	Type Checker
2.19	Type Inferrer
2.20	Type Inference
2.21	Prolog
2.22	Final

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