CSE 526
Spring 2005
Stony Brook
Principles of Programming Languages
Annie Liu
Homework 2
Handout H2
Feb. 1, 2005
Due Feb. 8

Implementing an Operational Semantics

This assignment has two parts, each worth 50% of the grade. It is due before class on Tuesday Feb. 8. For this assignment, please hand in all your files (or directories) by including them in an email to cse526ATcsDOTsunysbDOTedu (You may use any format for the email, but give instructions for decoding if this is not clear from the message itself). More automated handin methods will be provided later.

Part 1. Implementation.

Implement the operational semantics for IMP in Chapter 2 of Winskel's book in a programming language of your choice.

Note that this combines Exercises 2.1, 2.2, and 2.6, except that you are not required to implement it in ML or Prolog.

Whatever your language of choice is, you should write your program as clear, simple, and efficient as you can.

Part 2. Related requirements.

Document your program as clearly and succinctly as you can. Your comments should include all issues related to the programming task. For this particular homework, you are asked to explain:

a.Language of choice: why do you choose the implementation language you use in Part 1 as opposed to any other languages?

b.Using C: if your language of choice is not C, describe how you would implement in C, and compare it with your implementation; if it is C, can you think of another way of implementing it (if yes, compare with your implementation, and if not, why not)?

c.Trade-offs: often it is not possible to make programs clear, simple, and efficient at the same time. Describe trade-offs and your decision when you feel them.

d.Usage: how can anyone take your file(s) and compile and run your program for tests? You should make this as simple as possible (e.g., by supplying tests or testing scripts if you feel necessary).

For issues not related to particular point in the code, put your descriptions/instructions in a separate section, typically before the code, or in a separate file if necessary.