CS212 CS212Problem Sets
Problem Set 6 - Fall 1999
Interpretation and Compilation: Part 1

Issued: Thursday, November 11
Due: Thursday, December 2, 4PM

I. Introduction

In this problem set, you will turn the Tiny Scheme implementation, discussed in class, into a Medium Scheme implementation. In doing so, you will learn about the structure of interpreters, compilers and optimizers.

The Tiny Scheme language is a small subset of Scheme. The semantics of this subset is the same as for Scheme. This will also hold for the extensions you will make. So, if you are not sure how something should behave, try it out in DrSwindle, read the documentation for Scheme and refer to the notes on the environment model. For all the questions, you need to provide output. Make sure your answers are well-commented. Otherwise, you will lose points.

The source code you are given has a read-eval-print loop. It writes a prompt on the screen, reads in expressions, compiles them through the function ts:compile (compilation phase), then evaluates them using the environment model through ts:eval (interpretation phase). You should understand how ts:eval and ts:compile work very well in order to answer the questions in part 2 and 3.

After loading the source code, enter in the prompt line (tiny-scheme). You will enter the Tiny Scheme environment. You can enter expressions and watch them evaluate. When you want to leave the Tiny Scheme environment, enter (exit).

II. Extending the Interpreter

In this section, you will add to the Tiny Scheme interpreter the ability to process some additional constructs.

Problem 1:

Currently, Tiny Scheme does not fully support the boolean operators. Add to the interpreter the ability to handle <, <=, >, >=, equal? .

Problem 2:

(define x e) and (set! x e)

Using the environment model, add the constructs define and set! You need to handle only the most basic case, where the first argument is a variable, the second is an expression. For define you can assume it is always global.

Problem 3:

(set-car! e1 e2) and (set-cdr! e1 e2)

Assume the operations are always applied to two expressions. First, these expressions are evaluated. If the value of the first expression is not a pair, an error signal should be given. Otherwise, set the car (resp. cdr) field of the value of the first expression to the value of the second expression.

Problem 4:

(begin e1 e2 ... en)

You may assume there is at least one operand.

Problem 5:

(letrec ((x1 e1) (x2 e2) ... (xn en)) e)

You can assume x1,...,xn are all variables, n > 0 and the body e is one expression. This can be tricky. Make sure you know what the environment model does in this case and check your answer with the results Scheme gives.

III. Extending the Compiler

Rudimentary compilation is achieved by the function ts:compile, which calls the function ts:reduce. Currently, it reduces let-expressions into function applications. In this section, you will extend the compiler so that it can handle more complicated constructs. In all of the problems in this section, make sure that you check that the expressions are well-formed and if they are not, give an error message.

Problem 1:

(define (f x1 ... xn) e1 ... en)

If you have successfully finished the first part, your interpreter can handle simple define constructs of the form (define x e). Extend ts:reduce so that (define (f x1 ... xn) e1 ... en) can be handled by the interpreter.

Problem 2:

(let* ((x1 e1) (x2 e2) ... (xn en)) exp1 ... expm)

The semantics of let* is different from let. Currently, Tiny Scheme doesn't handle it. Extend ts:reduce so that a let* is reduced to a construct that can be handled.

Problem 3:

(lambda (x1 ... xn) e1 ... em)

Add to the compiler the ability to handle lambda expressions with multiple expressions in their body. Do the same for (letrec ...).

Hint: Consider compiling these constructs to equivalent ones using begin-expressions.

Problem 4:

(and e1 ... en) and (or e1 ... en)

Compile these into equivalent expressions that can be handled by the interpreter. Note that n can be 0 or 1.

Problem 5:

(cond (test1 e1) ...(testn en) (else e)) and (case e ((v1) e1) ... (else en))

Compile cond-expressions to something the interpreter can handle. You can assume that n > 0 and there is always an else part. The same remark applies to case-expressions. See the Scheme Quick Reference for the semantics of case-expressions. You may assume that value lists will contain only one element. You can further assume the values are just integers