realloc users: there was a bug in the memory tracking code for realloc. Please update your i_memory.c file.
isNumber. It was originally meant to be part of the project, but since it causes some bad expressions not to error we have revised the code in microscheme.c. The first if in isNumber should check if (ch == '-' && strlen(str) > 1), otherwise the '-' alone will be recognized as a number, as in (+ - 2). Note that such an expression is not valid Scheme (so it won't be tested).
free_thing(a,0); free_thing(b,0); above the "Non-numeric arg to plus" call to printf in microscheme.c. The microscheme.c file has been fixed.
make_num(int num). You can make a new implementation like make_big_num(...) and call that instead.
int to index or count digits. You should aim not to build any unnececssary sizing limits into your code. Don't focus on the 231-1 number, but instead think of the limit as somewhere in the hundreds, thousands, or millions of digits.
i_memory.c file
Does anyone else miss Scheme and CS61A? Ah, the good ol' days, when we didn't worry about low-level number representation with its imprecisions and limitations. We could call expt without worrying about overflow, or take fractional parts in stride:
STk> (expt 2 100) 1267650600228229401496703205376 STk> (/ 1 5) 0.2As Scheme programmers, we only cared about numbers, not fixed-bit-length
ints, chars, and unsigned shorts. Well, grab your parentheses, because we want you to implement "bignums" (a datatype and some arithmetic operations) in a very small and simple Scheme interpreter called microscheme! (without using any C bignum libraries, of course...)
We want the provided microscheme interpreter to be able to input, output, and do arithmetic on decimal positional notation numbers that can have sign and both whole and fractional parts (each arbitrarily sized). There should be no hard-coded limit to number length. We also want to implement the following arithmetic operations on bignums: + (addition), - (subtraction), * (multiplication), and expt (exponentiation), though you only have to be able to raise a bignum to a non-negative integer power.
Note that we do want you to implement "bignum fractions" that can handle any size fractional part. This implementation will be even better than STk's bignums, because STk can't handle really big fractions:
STk> .9999999999999999999999999999999999999 1.0We don't want any rounding in our microscheme interpreter, so it should respond like this:
> .9999999999999999999999999999999999999 0.9999999999999999999999999999999999999The project can be broken down into the following steps.
int data type, but that just won't do. You must extend it to be able to internally represent numbers of arbitrary size, possibly with fractional parts: enter the bignum.You will have to create a bignum data type for the interpreter to use internally by modifying the struct thing definition in thing.h. It must keep track of sign, whole, and fractional parts, but you are free to choose the internal representation. You can use a binary representation like those in ints, or you can simply store decimal digits (like a binary-coded decimal). Don't forget the principles of data abstraction! See the Suggestions section below.
bignum bignum_add(bignum a, bignum b), but should include addition, subtraction, multiplication, and exponentiation via non-negative integer powers. They will be called by the microscheme interpreter to manipulate bignums. You will add these new functions in microscheme.c.
Numbers should be parsed from and printed to the decimal form [-]Y.Z, where Y and Z are decimal digit strings of any length and [-] indicates an optional '-'. If Z has zero length then the decimal point should not be printed, but if Y has zero length a "0" should be printed in its place. For details on valid numbers at the input and the output, see below:
A valid number for input is defined as follows:
Your arithmetic operators should act similarly to the STk ones. That is, they should take arbitrary-sized arguments, where each argument can be any valid number, except for expt, which takes only two arguments, the second of which must be a non-negative integer. If + or * is called with no arguments, 0 or 1 should be returned, respectively. If - is called with one argument, the argument should be negated. Multi-argument calls to - should behave similarly to STk, namely all but the first argument should subtract from the first. Add these functions into microscheme.c.
The car and cdr operations are already implemented in the microscheme interpreter, and you should stick to the "Thing" data abstraction for evaluated Scheme expressions.
malloc() and free(). You must #include microscheme.h in any .c file you add to the project so that memory tracking will work!
(+ 9999999999 99999999999999999999) shouldn't have to perform 9999999999 (or 99999999999999999999) additions.
(+ 'hi 'matt) are legal Scheme from a syntax perspective, and such things shouldn't crash microscheme. Instead, print some error and continue the read-eval-print loop. It doesn't matter what you print on such erroneous input, but make your errors descriptive like "non-numeric argument to +". Never segfault from any input!
Copy the contents of ~cs61c/proj/01 to your home directory.
$ mkdir ~/proj $ cp -r ~cs61c/proj/01 ~/proj1The directory contains several files:
thing.h, contains the definition of thing, the structure used to represent all objects in microscheme. You can edit this file.
core.c, a file to setup the microscheme interpreter environment. Do not edit this file.
microscheme.c, which is the file you will work from to enhance microscheme. You can edit this file as long as it maintains compatability with microscheme.h (don't violate any function prototypes, but you don't have to call any of the provided functions and instead replace them with your own).
microscheme.h, the header file for microscheme. Do not edit, but #include in any C files for which you want to track memory management.
microscheme.h and core.c.
Makefile, which is a file that will tell us how to compile your submission (see the Compiling section). The directory also contains several text files of sample interactions with a bignum-enabled microscheme interpreter.
% gmake proj1 % ./microscheme
gmake is a program that makes the compiling process easier when you have many files. It knows how to compile your submission based on the contents of the Makefile in the same directory.
submit proj1 command from your proj1 folder. The submission process will ask you to submit the Makefile, microscheme.c, thing.h, any additional .c and .h (C header files) needed to compile your project, and a README, information you want to tell the reader about how your code is organized as well as what does and doesn't work. Please do not submit addtional files such as your executable, the code we already gave you, and the sample files we gave you. To reduce the number of files that submit will go through, it will help to run the command "gmake clean".
0.99999999999999999999999999999. It should also produce the same output as the examples.
$ cat example0.in | ./microscheme > example0.myout $ diff example0.myout example0.outUPDATE: You should test numbers with many digits using this pipe technique, as the Solaris machines have a fixed-length buffer for typed terminal inputs.
> (+ 1 2) 3 > (+ 0 0.0) 0 > (+ 1.0 5) 6 > (+ 000200.0000 050) 250 > (+ 99999999999999999999 99999999999999999999) 199999999999999999998 > (+ -100 100) 0 > (+ 123980234983 -2) 123980234981 > (+ -49283 200.999999999999999999999999999 300) -48782.000000000000000000000000001 > (+ -50000000000 -50000000000 -50000000000 -50000000000) -200000000000
> (- 10 5) 5 > (- 10000) -10000 > (- 20 5 5 5 5) 0 > (- 0) 0 > (- 2390840928309.12093894892389 90082389.9999999999999999999999999999) 2390750845919.1209389489238900000000000001 > (- -500 23895) -24395
> (* 100 0) 0 > (* 1 .99999999999999999999) 0.99999999999999999999 > (* 1000000 1000000) 1000000000000 > (* 1 -1 1 -1 1 -1 1 -1) 1 > (* 2.5 2 2) 10 > (* -6 5 2.25) -67.5
> (expt 238 0) 1 > (expt -1 100) 1 > (expt 111.2 5) 17002936630.96832
> (+ (- 1 1) 10) 10 > (+ (- 452 4.52) (* 42 52) (- (+ 3 (- 4 2)) 4.24)) 2632.24 > (* (- 1) (+ 100 50 2) (expt 2 4)) -2432
microscheme.c, but rather creating separate C and header files. A good way to organize is by data abstraction, so you'll probably at least want a bignum.c and bignum.h
bignum new_bignum(void) that would call malloc and set up a bignum type for use. The keys to abstraction in C are structs, typedefs, and appropriate getters, setters, and other operations on data.
ddd, which is only accessible through cory server (ssh cory.eecs.berkeley.edu).
microscheme.c code that you don't understand (like the union keyword in the struct), ask! Okay, you should probably check K&R and try to figure it out for yourself first. If you still do not understand, then make a newsgroup post and/or go to office hours of a TA!
After making a backup copy of your primary proj1 submission, do the following:
(/ 1 3)). For these cases it's up to you what to do (looping forever is fine); we will not test with any numbers that have infinite decimal (or other radix) representations.
> (base 2 10) 0b1010 > (base 10 0b100000) 32 > (base 0b1010 0b100000) 32 > (base 16 0b100000) 0x20 > (base 0x10 0b100000) 0x20 > (base 10 0b1000000000000000000000000000000000000000000000000000000000000) 1152921504606846976 > (base 2 70643625237641) 0b10000000100000000000000001100000001110010001001 > (base 2 -10.5) -0b1010.1 > (base 10 -0b1010.1) -10.5
(base x y) where x must be 2, 10, or 16.
To submit the extra credit, you will submit it to "submit proj1_xc". Do NOT submit the extra credit version using "submit proj1" unless you are confident your changes will not effect the primary requirements of this project. Note, unless you submit using "submit proj1_xc", we will not know whether you tried the extra credit or not.