MCS-287 Lab Project 1: Lexical Addressing (Spring 2000)

Due: February 24, 2000

In this lab, you will basically do Exercise 2.3.10 (page 62) with some variations. Some of these are slight changes I recommend in the basic problem specification and approach. Others are extensions to the language. Your project report should reflect your final product, with all the extensions in place, rather than showing each incremental step along the way. However, I recommend that you start simple (without the extra language features) and add them in once you have the basics working. Your project report should explain the overall functionality your lexical-address procedure provides and the program design that allows it to provide this functionality. Don't go into the details in English: your audience can read Scheme. However, don't assume the audience knows what you are trying to accomplish or how you have gone about accomplishing it.

Change to basic problem specification

EOPL's authors say to give any free variable reference a lexical address as though it was bound by an imaginary lambda that was wrapped around the entire expression. (Presumably this lambda would list the free variables in the order of their first occurrence in the expression.)

Instead of doing this, I would like you to leave any free variable reference alone: don't assign it a lexical address at all. Only bound variable references should be given lexical addresses.

Suggested approach and hints

Rather than doing this exercise via list processing (as in chapter 2), I would suggest you use records and variant-case, as explained in section 3.4. That is, I am suggesting you do Exercise 3.4.6 (page 87). The idea here is that lexical-address would first use parse to translate the expression into an abstract syntax tree (AST) built out of records. Then it would invoke some "core" lexical-address-conversion procedure that operates on the AST, replacing some varref records with lex-info records. Finally, your top-level lexical-address procedure would use unparse to translate the expression back into list form. (The parse and unparse procedures on page 85 are for a slightly different language, so you'll need to modify them.)

There is no need for you to wait until we reach section 3.4 in class in order to start work on this project. Not only could you peek ahead at that section, but also the first problem you face is deciding on a general design or strategy for lexical addressing, not writing specific code. The general strategy is independent of whether your procedure operates on list structures or records.

In designing your strategy, you should give some thought to efficiency. In particular, it would be best not to make repeated passes over the expression. Remember that you are free to write as many procedures as you find useful, including ones that generalize the original problem or serve as helpers.

Assuming you take my suggestion to use define-record and variant-case, you will need to load these features into Scheme, since they are non-standard. If you use DrScheme on one of the department's Linux machines, you can just put the following line at the top of your program file:

(load "~max/www-docs/courses/S2000/MCS-287/code/")
If you are using DrScheme on another machine (e.g., your own), you can download that file from the course web page. If you are using some other Scheme system than DrScheme, you will need a different definition of these facilities. You might find them in the book's FTP site, which is also linked from the course web page.

Another issue with using the record facilities is getting DrScheme to indent them appropriately. You can find a web page on this topic linked from the course page.

Language extensions

You should extend your lexical addresser's language to include cond, let, and letrec. Use a different approach for cond than for the other two, as described below.

For cond, you should just change parse to produce the same AST records as if the expression had been written using if. (Or at any rate, had been written without using cond. Some unusually simple cond expressions may be translatable without using if.) This very roughly corresponds to Exercise 3.3.1, page 71.

For let and letrec, on the other hand, you should introduce new AST record types, and change all three phases of your program: parse, the core lexical address conversion code, and unparse. Keep in mind the difference between let and letrec. This extension corresponds approximately to Exercise 3.1.5, page 74.

Instructor: Max Hailperin