Machine Problem 3: First Interpreter

Out: Wednesday, 30 January 2008

Due: 5 PM Friday, 8 February 2008

Submission: Partners

This assignment is to be done in pairs. If you cannot find a partner, please contact your instructor.

Purpose

The main goal of this assignment is to give you a simple introduction to environments, abstract syntax trees, and interpreters.

Tasks

1. [12pts] EoPL exercises 2.5, 2.9, and 2.10. (Note that exercise 2.5 starts on page 37 and continues on page 39.)
2. [6pts] Write a procedure named calculate that takes one argument exp, which belongs to the arithmetic-exp datatype (see below) but contains no variable references, and calculates and returns the numerical value of exp.
3. [6pts] Write a procedure named value-of that takes two arguments exp and env, where
   1. exp is an element of the arithmetic-exp datatype (see below)
   2. env is an environment as implemented for EoPL exercise 2.5, with the further restrictions that env maps every identifier that occurs within exp to a Scheme number
   and returns the numerical value of exp evaluated in the environment env.
4. [6pts] EoPL exercise 2.31 (which starts on the bottom of page 54 and continues on page 55). Your parser should be a one-argument procedure named parse-prefix-list. Its one argument is a Prefix-list as defined in exercise 2.31, and its result is a prefix-exp as defined in exercise 2.31 and in mp3-data-structures.scm (see below).

   Hint: Observe that every Prefix-list is a Listof[Prefix-exp], but not every Listof[Prefix-exp] is a Prefix-list. Use a help procedure that takes a nonempty Listof[Prefix-exp] as its one argument input and returns two results: (1) the prefix-exp t obtained by parsing the first Prefix-exp in the input, and (2) the Listof[Prefix-exp] that is left over after that first Prefix-exp has been removed from the input.

Infrastructure

You are given the following files:

• mp3-test.scm is a woefully incomplete prototype of the mp3-test.scm you will modify and submit as your second deliverable.
• mp3-data-structures.scm defines and provides the prefix-exp and arithmetic-exp datatypes you will use for tasks 2, 3, and 4 above. It also defines and provides a parser that translates a concrete syntax for arithmetic expressions into the arithmetic-exp representation of abstract syntax trees. You should not modify mp3-data-structures.scm.
• drscheme-init.scm is the usual initialization file required by mp3-test.scm. You should not modify drscheme-init.scm.

Deliverables

1. A PLT Scheme module mp3.scm. This module should be written in the language (lib "eopl.ss" "eopl"), and should provide the 8 procedures you wrote for tasks 1 through 4. (You may define help procedures as well, but they should not be provided.)
2. A PLT Scheme module mp3-test.scm. The module should be written in the language (lib "eopl.ss" "eopl"), require the modules drscheme-init.scm, mp3.scm, and mp3-data-structures.scm, and should test all 8 procedures provided by mp3.scm. Your mp3-test.scm file should be derived from the one given you by the course staff (see above). You will need to add more tests to that file, of course.
3. The output obtained by running your mp3-test module, in a plain text file named mp3-test-output.txt.
4. A Development Diary

Back to Machine Problems

Last modified: 3 February 2008