A tiny Scheme-subset interpreter written in C is available in the file microscheme.c. Your job is to extend the interpreter. Part of the object of this project is for you to be sure to learn any C details needed for the project that you haven't learned already, so ask questions if necessary.

One of the niftiest features of Scheme is the way numbers are dealt with. Instead of having various number types such as int, unsigned, long, double, etc., numbers are just plain numbers. There is no need to worry about limits to the size or precision of the data; Scheme numbers can handle everything. Unfortunately, the code in microscheme.c can only handle signed 32 bit integers. The goal of this project will be to extend it to deal with arbitrarily large integers and rational numbers.

You will be required to do the following:

1) Modify the I/O of the interpreter to handle bigints: The current interpreter merely assumes that a number can be represented by a signed 32-bit integer. Extend this such that it can handle arbitrarily large integers, i.e. 1234567890123456789. "Arbitrary" has its limits: our test numbers will not exceed 2^32-1 decimal digits. You will also need to modify the output functions to recognize this representation. The output text is described below. You are advised to make a new number representation in the interpreter to hold the larger values/rationals.

2) Implement math functions for big integers: The current addition function takes in what it expects to be signed 32 bit integers, except that is clearly no longer the case. Modify it to accept big integers. Also implement subtraction, multiplication, and division, which do not exist in the framework code that we have provided you.

3) Add I/O for rationals: Now that big integers can be stored, add in rationals of the form "numerator/denominator" where numerator and denominator can be big integers themselves. For example, the following will be valid inputs:

12345678901234567890 1/3720 -2/400000000000000000000000000000000000The second number represents the odds of successfully navigating an asteroid field.

4) Add math for rationals: Just like for bignums, implement addition, subtraction, multiplication, and division for rationals.

5) Variable argument math functions: To make things a bit more like real Scheme, we'll let the math operators take in a variable number of arguments- as opposed to just two. Once this is all complete, the interpreter should be able to evaluate

(+ 858101931 1/3 (* 7858282/812 9999999999999999999999999999999999999) 42)6) Have reasonable running time: You should do your computations in a logical fashion that takes into account the fact that numbers can be very large. In general, we don't want to see your program take half a minute to compute the above example. An example of a poor algorithm would be to add two numbers together by repeatedly adding 1 over and over again, i.e.

(+ 99999999999 9999999999999999999999999999999999999999999)shouldn't have to perform 9999999999999999999999999999999999999999999 additions.

7) Good file organization: You should organize the code into multiple files to prevent microscheme.c from growing large and unwieldy. Write header file(s) to facilitate this. At the very minimum, much of your work with math functions and the new number representations should be in seperate file(s).

8) Follow restrictions: You may only use libraries specified in the appendix of K&R.

You will NOT be required to do the following (but read this, since there are subsets of them that need to be done)

1) All out memory management: The framework code we provide does not call free(), and we will not require you to fix this (very leaky!) code. However, you should use good memory management skills and ensure that any intermediate memory that you malloc() is free()'ed before your functions complete. In other words, you do not have to free() the arguments or return values of your math operators.

2) Input error checking: We guarantee that input will be valid Scheme syntax according to Dr. Scheme. Your program will only need to handle a subset of the inputs that Dr. Scheme does. Of course, the inputs can be extremely large nasty numbers. Your computation should gracefully error if an invalid math operation occurs, i.e. division by zero, or the number itself has a denominator of zero.

In particular, legal numbers will only be of the form /-?[0-9]+(/[0-9])?/ (perl). To translate- there is a possible leading negative sign (only before numerator) and some digits. An optional slash may follow in conjunction with more digits representing the numerator.

Dr. Scheme chooses to display produced rationals as numbers with decimal points, so ignore its immediate output. However, if you use the display function on the output, it will show a reduced rational that you can check against, i.e.

(display 2/4)will show 1/2 on the screen.

(display -7/3)will show -2 and 1/3 in Dr. Scheme. Your code should print

-7/3Note that there is no whole part like Dr. Scheme prints.

Helpful files:

example0.in

example0.out

Using these, you can run

cat example0.in | ./microscheme > example0.myout diff example0.myout example0.outThe first command will print outputs to the file named example0.myout. After that, the second command compares example0.myout to example0.out. If there are differences they will be printed out, otherwise, nothing will be shown on the screen.

Add user-defined procedures and symbol tables so variables can be defined. This will require several steps and knowledge from 61A:

1) Implement symbol tables (make sure that there can be more than 1 of these). Given a symbol, it should return the associated value. You should also create some means off adding symbol/value pairs into a table.

2) Create the global envrionment and the define special form. An environment is just a list of symbol tables. The global enviroment is a 1-element list. Calling the define special form should add a symbol/value pair to the correct symbol table.

3) Modify EVAL so that the operator (first) subexpression of a compound expression is evaluated recursively, as the argument subexpressions already are. Invent a primitive-procedure data type; put the primitives in the global environment. [The interpreter as it exists now doesn't look up the primitives in the symbol table; it has their names built in, as if they were special forms. But you'll change this, so that procedures are first-class values, as in Scheme.]

4) Add user-defined procedures. Create a new USERPROC type that includes the procedure's text and its defining environment. Add a LAMBDA special form to create user procedures. The text of the procedure is just the LAMBDA expression (or its cdr, if you prefer, leaving out the word LAMBDA itself). Modify the symbol lookup routine to handle a list of symbol tables. Then you have to write APPLY so that for user-defined procedures it extends the procedure's defining environment with a new frame in which the procedure's formal parameters are bound to the calling expression's actual argument values, and you have to write EVAL-SEQUENCE that evaluates the procedure's body. (Actually, since we have no primitives with side effects --- no mutation, for example --- you could get away with only allowing one expression in the body.) Basically you are redoing the metacircular evaluator from chapter 4 of SICP, but writing in C instead of in Scheme. This really isn't hard if you remember 61A!