Exercises and Assignments

This course is a pass/fail course, and in order to pass you must deliver solutions to the programming exercises which will be described on this page, each one accompanied by a small report describing your approach and results.

NB: Solutions to the mandatory assignments except the last one should be delivered during the first half of the course, and all of them have been delivered at the latest by Easter. The solution to the last assignment should be delivered at the last lectures or by email sometime before that.

Assignment 1 (mandatory)

Implement the SECD machine in Standard ML, as defined in [ICVM.1].

Assignment 2 (optional)

Find a trivial program that satisfies the boot-strapping construction, as shown in [ICVM.2].

Assignment 3 (mandatory)

Extend Dejlisp to make it meta-circular, i.e., write a Scheme self-interpreter.

Go to the following UNIX directory:

and look at the following files:

• dejlisp.scm
• dejlisp.session
• dejlisp.txt

Assignment 4 (mandatory)

This assignment was described in the news group message "Last ICVM assignment" sent to the daimi.icvm news group on May 8th, 2003.

Please deliver your solution at the last lectures of the course, or by email some time before that.

Here comes the description as it appeared on the news group (with a slightly adjusted wording because the source code is given as links here, not inlined):

Please take a look at the mini-OO-language interpreter given below and add one of the following extensions to the language:

1. Whereas the language as given accepts exactly one argument in message send expressions, you should make it possible to give an arbitrary number of arguments (such that each method expects exactly N arguments for some number N). This means that methods should be redefined such that they specify a _number_ of formal arguments, and message send expressions should be modified such that they contain a _list_ of actual argument expressions. Arguments should then be accessed in the body of methods using 'Syn.ARG i' for the i'th argument. You could also use named arguments, but in the spirit of the language design decisions taken so far it seems most consistent to use numbered arguments (moreover, it allows you to simplify environment and error handling a bit).
2. Whereas the language as given has no notion of inheritance, you should add some inheritance mechanism to it, such that each class specifies the name of its superclass (you may want to add a special "Object" class to use when no (other) superclass is needed), and such that relevant semantics is achieved (instance variable declarations are accumulated, giving an error for duplicated names, and method declarations are accumulated, choosing the most specific one in case of duplicated names).

Please consider relevant language design issues, e.g.,

• how to handle a message send expression giving another number of arguments than the method expects (consider: how/when do you even know which method is being called?)
• how to handle method overriding when the number of arguments are different in a class and its superclass
• whether there is really a need to specify the number of arguments in the method declaration
• whether the semantics of multiple method arguments or inheritance should indeed be as described above---if you prefer something else then please describe it, describe why you think your design is better, and do it!
• perhaps, if you have time and ideas about it, explain briefly how the constructs could be extended, e.g., from single inheritance to multiple inheritance

Then please write a report of up to 3 pages about your language design and implementation, with information about where we can find your source code files. Here is the interpreter source code: ms2.sml.

Note that this interpreter is a significantly simpler expression of the semantics of the tiny object-oriented language than the st.sml you have seen at the lectures. The trick is that Olivier applied some short-cuts which are appropriate for the overall process, and in particular this interpreter does not represent the heap and stack explicitly, it uses the built-in heap and stack of SML.

The purest version of this interpreter is produced by deleting the lines containing comments on the form (*- ... -*). If you keep these lines in the interpreter it is extended with the ability to execute the 'pred' method on an integer and to create an instance of "True"/"False" conditionally, as well as the ability to print out messages during program execution (look for 'PRT'), which is convenient during debugging.

To get started, you may wish to experiment with the following small example programs: ex2.sml.

Exercise 1 (optional)

Based on the evaluator, write a function fv of type

    Expr.expr -> Expr.ide list

that computes the list of free variables in an expression.

Exercise 2 (optional)

Based on the evaluator, write a function that compiles an expression into another expression where all the identifiers have been replaced by their lexical offset:

structure Expr'
= struct
    datatype expr = LIT of int
                  | VAR of int
                  | LAM of expr
                  | APP of expr * expr
    type program = expr
  end;

Adapt Eval_cbv and Eval_cbn to work on this new abstract syntax.

Exercise 3 (optional)

Exercise 4 (optional)

Exercise 5 (optional)

Exercise 6 (optional)

Exercise 7 (optional)

Exercise 8 (optional)

Exercise 9 (optional)