Assignment 1
Due Thursday, March 8



This assignment has two aspects:

Here are the steps you should perform:

Part 1 of the Assignment

Step 1
Install the GCC/G++ compiler on your computer, if it is not already installed. To do so, follow the instructions for your system on the course web page.

Step 2
Read the code C++ discussed in class on February 6 and 27, on the course web page.

Step 3
Write in C++ a program that has the following:

A very simple program that satisifies the above criteria can be found in the following files:

Your program, of course, should not look like this one. Try to come up with a more realistic program that has somewhat more complicated code. Be sure to work on the program by yourself. Your code should not look like any other student's code.

To compile your code using GCC/G++, type the following into a shell (using your file names, of course).

g++ file1.cc fileN.cc
To run the resulting executable, on a Mac or on Linux, type
./a.out
or using Cygwin on Windows, type
./a.exe


Part 2 of the Assignment

Step 4
Review how to use function pointers in C. A brief description of function pointers in C can be found here here. Any C reference book or online tutorial will also contain information about function pointers.

Step 5
Review your notes from class on the implementation of dynamic dispatch in C++ using vtables. For more detail, you may want to read the Wikipedia page on vtables. Be sure you understand completely how vtables work for both single and multiple inheritance. Be sure follow the link for "thunks" from the above Wikipedia page (you can also click here).

To summarize, note that a C++ object instantiated from a a base class can be represented in C by a record (struct) containing the following fields:

The vtable is itself a record containing a field for each virtual function in the class. Each field of the vtable is a pointer to the code for the virtual function, where the first parameter of the virtual function must be a pointer to the object. For example, here is some C code for declaring the type of an object (A_OBJECT) and the type of its vtable (A_VTABLE).

struct A_vtable;

typedef struct A_object {
  struct A_vtable *vt;
  int x;
  int y;
} A_OBJECT;

typedef struct A_vtable {
  void (*g)(A_OBJECT *);
} A_VTABLE;

Thus, for a call a virtual function for an object there's a level of indirection through the vtable for the object. There is no such indirection for non-virtual functions, since there is no entry for a non-virtual function in the vtable.

To implement inheritance, the struct representing an object of the child class will have all the fields of the struct for the parent class, plus any additional fields for the new data members of the child class. The vtable for the child class will have all the fields of the vtable for the parent class, plus a new field for each new virtual function of the child class. If the child class redefines any virtual functions of the parent class, then the corresponding fields of the child's vtable will point to the new definitions of those virtual functions.

Note that it is not necessary to create a new vtable every time a new object is created. A single vtable can be shared (i.e. pointed to) by all objects of the same class.

In the case of multiple inheritance, an object of the child class will contain all the fields -- including the vtables -- of the parent classes. Thus, the objects of a class that inherits from two parent classes will have two vtables. Read the description in the Wikipedia page concerning the implementation of vtables in the presence of multiple inheritance closely, along with the Wikipedia page on thunks (see above).

I have written some skeleton C code implementing vtables. This code is similar to what I discussed in class, so I recommend taking a look.

Step 6
Translate the C++ program you wrote for Part 1 into C (or into the subset of C++ is essentially C -- so no classes, methods, etc.). That is, each class in your C++ program should be translated into struct declarations in C (like the ones above) and each member function of the classes in your C++ program should be written by hand in C. If you are writing in C, you can use printf() to print and malloc() to allocate structures and can invoke the C compiler by typing "gcc ...". If you are writing in the non-object oriented subset of C++, you can use cout for output and new to allocate structures, and type "g++ ..." to run the compiler.

Step 7
Email your code for both parts of the assignment to Prof. Goldberg (goldberg@cs.nyu.edu) in a zip file. Please put "OOP Assignment 1" in the subject field of your message. If you have questions, you should email me or come to my office hours on Monday at 3:30pm - 5:30pm in room 401 WWH.