Implementing Scheme

This lab is designed to show you how the techniques that we've been learning to implement application-specific languages also apply to implementing large, mainstream languages. To demonstrate this, over the next two labs we will implement a subset of Scheme.

At first, this assignment seems strange: why would we write a Scheme program to implement Scheme? The goal is to show you that our techniques for writing data definitions and interpreters let you implement ANY large language; on those grounds, we could in theory (but won't) write a Scheme program to implement Java. Similarly, you could write the interpreter in any language you choose. So the skills you practice here would let you implement Perl in Java, or Python in Scheme, or Java in COBOL (assuming you could find a reason to do the latter ...).

The way to think about this lab is to recall the set of concerns we've asked about with each new language design: what's the data, what are the operators? How do we create data definitions for each? How do we implement an interpreter that evaluates the operators? Think about these same questions as you work through the exercises.

**NOTE:** You may continue with this lab next week or do a lab
on newer material. Make sure you have uploaded your lab for this week
to turnin so you can download it again next week.

Work through the exercises on Evaluating Scheme in HTDP.

Everyone should be able to finish up through exercise 14.4.3 by the end of lab 5.

If you are doing well, you will be able to finish up through exercise 14.4.4 by the end of lab 5.

Work through the exercises on Evaluating Scheme, Part 2 in HTDP.

Everyone should be able to finish up through exercise 17.7.2 by the end of lab 6.

If you are doing well, you will be able to finish up through 17.7.3 by the end of lab 6.

If you are extremely well, you will be able to finish up through 17.7.4 by the end of lab 6.

Most of you won't get this far in the two weeks. If you do, however, here are some extensions you can consider making to your interpreter.

Add an

`if-zero`

construct. This construct is a simplified form of an if-statement. The test must evaluate to a number. If that number evaluates to true, evaluate the then-part, otherwise evaluate the else-part. For example:(if-zero (+ 4 3) 2 6) returns 6 (if-zero (+ 4 -4) (* 2 1) 6) returns 3

Given if-zero, you can now write factorial in your subset of Scheme. Send factorial as one of the definitions and evaluate a call to factorial with your interpreter. Do you get the right answer?

From here, you can do all sorts of fun things like add functions with multiple arguments, local, begin, and your other favorite operators to your implementation ...