DD2456 - Laboratory Exercise 3.

An Type Checker for the Typed Object Calculus with Subtypes

This exercise is designed to deepen your understanding of the object calculus. It will give you the chance to analyse the structure of Typed OC programs

1. Getting Started

You can develop an OC type checker 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 Type Checker Requirements

The requirements on the OC type checker are as follows:

  1. The interpreter shall be able to read in a typed 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 typed OC term as a type free term. If the input term is syntactically well-formed as a type free term the interpreter shall construct a parse tree representation. If the input term is not syntactically 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 type checker should automatically begin to analyse the type structure of the input term to check that it is well typed according to the typing rules of the OC with subtypes.

  4. If the input term has a well defined type then the type checker will return both the term and its type as strings, either to the screen or to a named file. If the input term is not well typed, the type checker will return an appropriate error message. It may give an indication the location of the typing error in the input term.

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

  6. The type checker may support the use of typed lambda terms, either directly or else by translating them into OC terms. Note these two approaches are quite different, so think carefully about which you choose from the start.

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


1.2. Evaluating your OC type checker

While you are constructing the OC type checker you should test it using some simple test cases of OC programs that you have type checked by hand. You should use positive examples (correctly typed) and negative examples (incorrectly typed). When you are finished you should develop one more extended OC program yourself to study OC type checking.


1.3. Lab Demonstration

When you are happy with your work, and you have finished and type checked at least one extended 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!