EECS 662

Programming Languages

Index
Blog

Project 0 - A First Interpreter

Mini Project 0 - Implementing our First Interpreter
EECS 662 - Programming Languages

The objective of this miniproject is to develop your first rudimentary interpreter and extend that interpreter to include two additional language features. You will start with the AE language presented in class to get up-to-speed with Haskell, Parsec, and QuickCheck. You will first extend AE to allow multiplication and division and then a simple conditional operator.

Exercise 1

Write a parser and interpreter for the AE language discussed in class and presented in our text. Extend AE to include multiplication and division. (Yes, I know much of the code is in the book, so don’t snicker.)

AE ::= number
        AE + AE |
        AE - AE |
        AE * AE |
        AE / AE
  1. Write an type for representing the abstract syntax of the extended AE language using data.

  2. Using Parsec, write a function, parseAE, that accepts the concrete syntax of AE and generates an AE data structure representing it.

  3. Write a function, eval::AE -> AE, that takes a AE data structure and interprets it and returns a value. If your interpreter fails, it should throw an error using the error function discussed in class.

  4. Write a function, interp that combines your parser and evaluator into a single operation that parses and then evaluates a WAE expression. Note that eval should not be called if the parser fails. The error function should help you out with this.

Exercise 2

Modify the abstract syntax, parser and interpreter for AE to define a new language, AEE (AE Extended) to include the following new features in addition to your original WAE features:

AEE ::= number |
        AEE + AEE |
        AEE - AEE |
        AEE * AEE |
        AEE / AEE |
        if0 AEE then AEE else AEE

The new construct here is if0, an expression that evaluates its first argument and if it is 0 evaluates its second. If not, it evaluates its third.

  1. Write a type for representing the abstract syntax of the AEE language using data. Use your AE abstract syntax definition as a starting point and add a new constructor If0.

  2. Using Parsec, write a function, parseAEE, that accepts the concrete syntax of AEE and generates an AEE data structure representing it. The easiest way to do this is extend parseAE with the syntax for if0.

  3. Write a function, eval::AEE -> AEE, that takes an AEE data structure, evaluates it, and returns a value. If your interpreter fails, it should throw an error using the error function discussed in class.

  4. Write a function, interp that combines your parser and interpreter into a single operation that parses and then interprets an AEE expression. Note that your interpreter should not be called if the parser fails. The error function should help you out with this.

Extending the AE data type to handle AEE expressions is reasonably simple. You will need to add a constructor for if0 that takes three AEE arguments.

Super Cool Optional Exercise 3

Reimplement the AEE interpreter using a Maybe monad. Specifically, reimplement eval with the type eval::AEE->Maybe AEE. This is not particularly difficult and you should be able to find plenty of examples both in the class text and online.

Notes

Most if not all the code for the AE interpreter can be found in our text. I would encourage you to try to write as much of it as possible without referring to the textbook examples. Much of the code for AEE can be adapted from the WAE interpreter. If you’re not familiar with these functions, ask in class or go online.

To give you an idea of the effort required for this miniproject, my code is about 100 lines long and took me rougly an hour to write and debug. I view this as a moderately difficult project at this point in the semester. Do not put it off as most of you haven’t used Haskell in some time. Additionally, you’ll need to figure out how to use the Haskell tools installed on EECS machines or install them on your own.

Download source for the parser utilities.