Tutorial Preparation

The following exercises should be prepared for discussion in tutorial.

Tutorial Exercise 1

Define, in Scheme, two different procedures that compute the minimum of the absolute values of a non-empty list of numbers. For example, (minabs (list 5 2 -3)) evaluates to 2; (minabs (list -1 0 -3 -7)) evaluates to 0. You should make sure you define everything in terms of the available primitives. For each of your procedures, say what order of growth in time (number of machine operations) and space (stack depth) you expect them to use. Pick your two procedures to have different orders of growth in space (i.e. iterative vs. recursive).

Check the 6.001 discussion forum for tutorial-ex-01

Look here for information about the forum.

Tutorial exercise 2

Implement each of your procedures from exercise 1 as a register machine, and show both the data paths and controllers for each machine. For the data paths, a diagram is needed; for the controllers, a textual description in the manner of Chapter 5 is adequate.

When implementing register machines, you should observe the following caveats:

• Every instruction is one of the following types: assign, branch, goto, save, restore. You should not need to use perform.
• The only values that can be assigned to registers or tested in branches are constants, fetches from registers, or primitive operations applied to fetches from registers. No nested operations are permitted.

Check the 6.001 discussion forum for tutorial-ex-02

Look here for information about the forum.