DD2456 - Laboratory Exercise 2.

An Object Calculus (OC) Interpreter.

This exercise is designed to deepen your understanding of the object calculus. It will give you the chance to write and execute simple object calculus programs.

1. Getting Started

You can develop an OC interpreter on any platform you wish, but consider that you will have to demonstrate your interpreter to me personally. In the past I have found that either a NADA Unix terminal or your own laptop in my office are the two easiest methods to use.


1.1. The Interpreter Requirements

The requirements on the OC interpreter are as follows:

  1. The interpreter shall be able to read in an OC program (i.e. an OC term) as a string either from the keyboard or from a named file.

  2. The interpreter shall be able to parse the OC term. If the input term is syntactically well-formed the interpreter shall construct a parse tree representation. If the input term is not syntatically well-formed, the interpreter should return an appropriate error message (such as "unmatched bracket"). The interpreter may return a pointer to where the error lies in the term.

  3. If a parse tree can be successfully constructed for the input term, the user shall be informed of this. Then the user shall be able to execute the OC term by the method of "weak reduction". (See course notes). An OC program may get into an infinite loop, and no method is practically possible to prevent this. Otherwise the OC program will terminate under weak reduction.

  4. If the OC program terminates under weak reduction, the interpreter will print out the resulting parse tree in the form of a string. The output shall be printable either to a named file, or to the screen. The interpreter will keep track of how many individual reductions were made on the input term parse tree. On request, the interpreter will display how many reductions were made.

  5. It shall be possible for the end user to single-step through the reduction of an OC term, applying just one weak reduction at each step. In this case the interpreter will display the new form of the parse tree as a string on the screen, after each individual reduction. This is to make debugging of OC programs easier.

  6. The interpreter shall have an appropriate graphical user interface that makes the various user activities easy to carry out.

  7. The interpreter shall support the execution of type free lambda terms, either directly using beta reduction, or else by translating them into OC terms and executing them with OC weak reduction.

  8. The interpreter shall support the integer data type together with the successor and addition, subtraction, and multiplication operations.


1.2. Evaluating your OC interpreter

While you are constructing the OC interpreter you should test it using the OC program examples developed in class. When you are finished you shold develop one OC program yourself to study OC reduction. One suggestion here is to extend the desktop calculator program, but you can develop something similar. Try to add some simple extra function, like a memory key (hint: consider object backup in the course notes), or a new mathematical function.


1.3. Lab Demonstration

When you are happy with your work, and you have finished and debugged at least one demo OC program, you should make an appointment with me for a demonstration. You can e-mail me for this. It is not necessary for the whole lab team to attend, but you must inform me of all team members if I am to assign them marks. The demo will not take more than about 10-15 minutes. To pass the demo, your program must:
(a) not crash, even on bad input,
(b) show that it satisfies all of the above "shall" requirements.

There is no deadline for this lab, but be aware of the deadlines for LADOK points. Please do not wait until the last week of term and expect that I will have time to see you then!