Due: 5:59:59 PM Friday January 28, 2011
This project, and some later projects in this class, will be done in the C language. There are two reasons for this. First, some of the things we want to study (e.g., in lab 2 the implementation of threads) require low-level manipulation of registers, stacks, pointers that would be awkward (at best) in a safe language like java. Second, C/C++ are still widely used languages, and learning them is a useful thing to do in its own right.
If you are interested in why C looks like it does, we encourage you to look at Ritchie's history. Here, perhaps, is the key quote: "Despite some aspects mysterious to the beginner and occasionally even to the adept, C remains a simple and small language, translatable with simple and small compilers. Its types and operations are well-grounded in those provided by real machines, and for people used to how computers work, learning the idioms for generating time- and space-efficient programs is not difficult. At the same time the language is sufficiently abstracted from machine details that program portability can be achieved."
Java borrows heavily from C syntax, and it is relatively easy to learn one language if you know the other well. At a high level, there are three major differences
By unsafe, we mean that programs can manipulate pointers in arbitrary ways. e.g.,
/* Dangerous pointer manipulation will compile in C. Don't do this! */ int dangerous = 0x102481a0; int *pointer = (int *)dangerous; /* We can set a pointer to anything. Yikes! */ pointer = pointer + 39468; /* We can do arbitrary math with poiners. Yikes! */ int value = *pointer; /* Programs can read/write any address. Yikes! */
In the second line above, we cast the int dangerous into a new type, a pointer to an int (int *). This should make you nervous. We are telling the compiler to ignore the type information it has and to trust us. This type of thing can lead to ugly bugs that are difficult to find (especially since the programmer here has deliberately deactivated the compiler's type safety checks.)
or/* A horse is a horse of course of course unless the horse... */ Horse h; Cow *c = (cow *)&h; /* Set the pointer c to the address of h */
In C you must manually allocate and free objects on the heap:
#include <assert.h> #include <stdlib.h> ... Cow *cow = (Cow *)malloc(sizeof(Cow)); cow_init(cow); moo(cow); ... free(cow);
In the above snippet, we called malloc, which is part of the standard libaray stdlib.h, to allocate memory from the heap, and we called free, also part of stdlib, to free memory when we were done with it. If you fail to call free() for heap memory objects when you are finished with them, you will have a memory leak. Conversely, if you continue to use a pointer after freeing it, you will have a nasty bug:
#include <assert.h> #include <stdlib.h> ... Horse *horse = (Horse *)malloc(sizeof(Horse)); ... free(horse); ... neigh(horse); /* Using memory after it is freed = many nights suffering in lab */
Many bad things can happen if you continue to access memory once it has been freed. Calls that use horse may do strange things since the memory location being pointed at might be reallocated as another object and changed. Calls that use other objects may fail or do strange things, since the "horse" manipulations will likely corrupt other data structures using the same memory. Calls to malloc/free may fail or do strange things since the calls using (freed) horse may corrupt the heap data structures being stored at those locations. Etc. And to top it all of, these bugs will manifest at strange times and different ways depending on details of how the libary manages the heap, what calls to the library are made in what order by the program, etc.
Note that the above discussion focuses on the differences. Don't lose sight of the fact that the languages are much more similar than different. If you know Java well, you should be able to quickly pick up C.
This lab is to help you get up to speed on the language before we start using it for interesting things in the next lab. It has two parts. First, do some reading of a more extensive (and better!) discussion of the differences between the languages. Second, write a few simple programs to begin practicing a few of the mechanics.
Read the following discussion of C for Java programmers.
Here are some other useful resources. (You are not required to read them. We include them just for your convenience/reference if you want to learn more.) You can find more with some simple web searches.
To help you get familiar with C, in this lab you will write some extremely simple C programs.
We will grade this lab on the CS department public linux machines. Although most or all of this lab should "just work" in many other environments (cygwin, OSX, solaris, etc.), note that (1) the course staff will not be able to assist in setting up or debugging problems caused by differences in the environment and (2) statements like "it worked on my home machine" will not be considered in the grading process. If you choose to do development in an unsupported environment, it is your responsibility to leave adequate time to port your solution to the supported environment, test it there, and fix any problems that manifest.
Download the file http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/labs/labC.tar. Untar it. You should be able to make a test program that we have included called "hi".
> mkdir ~/cs372 > cd ~/cs372 > wget http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/labs/labC.tar > tar -xvf labC.tar > cd labC > which make > /usr/bin/make > which gcc > /lusr/bin/gcc > make hi gcc -g -Wall -Werror -c -o hi.o hi.c gcc -g -Wall -Werror -o hi hi.o > ./hi So far so good. >
> make hello ... > ./hello Hello world
The first grading test in grade.sh should now pass
> ./grade.sh ... Output passed: 1 Output failed: 9
Note that passing the automated grading script grade.sh is a necessary but not sufficient condition for getting credit for a problem:
> make words ... > ./words To be or not to be? That is the question. To be or not to be? That is the question.
The next test in grade.sh should pass (as should your own tests.)
> make fact > ./fact one Huh? > ./fact 5 120 > ./fact 5.1 Huh?
The next test in grade.sh should pass (as should your own tests.)
You can split your code across multiple source files. Typically, a header file (e.g., "foo.h") describes the procedures and variables exported by a source file (e.g., "foo.c"). To compile, each .c file is typically compiled into an object file (e.g., "foo.o" and "bar.o") and then all object files are linked together into one executable.
You can define a structure that groups together a number of fields of state. These are like state variables in a class.
Notice that you can adopt a basic object oriented style of programming in C (even without the syntactic sugar of C++) by defining a type and the methods that operate on it in a .h file and a corresponding .c file.
We have provided point.h, which defines a type and structure for storing a point's position in 2d space, and which defines the interface to a translate() function to move the point to a new location and to determine the distance() between points. Your job is to implement these functions in point.c so that the test program testPoint.c works.
grade.sh should now pass the TestPoint test.
Create a sortedPoints module that maintains a list of points sorted by their distance from the origin (0.0, 0.0) as defined by the interface sortedPoints.h
The simple test in testSortedPoints.c should now run. You probably should write additional tests.
Hint: You are allowed to add new functions or even fields to point.h and point.c. (You don't have to do this to solve this problem, but you may find it convenient to do so.)
Although most of the projects for this class will be done in small teams, this project is do be done individually. The normal class rules on collaboration apply.
Complete the project and turn it in using the turnin command. make handin will tar up the necessary files and turn thim in automatically for you. Inspect the output to verify that all files necessary to compile, run, and evaluate your work were included.
% make handin