Assignment 4, Solutions

Part of the homework for 22C:112, Spring 2009
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Consider a large project where you have the following sourcel files:
    - a text file
    - a C program that, given list as standard input, produces list.c as standard output
    - a C package used by main.c
    - included by list.c, crunchlist.c and main.c
    - a C package used by main.c
    - included by main.c and by output.c
    - the C source of the main program of the application
    - the executable application program

    a) Several files have been omitted from the above, most notably the object files. List the intermediate files that are omitted above that would be of interest to a C programmer. Do not list transient intermediate files that you hypothesize exist during compilation, only list the files you would expect to find in your directory as you develop this program. (0.5 points)

    - the executable version of crunchlist.c
    - the object code from list.c
    - the object code from output.c
    - the object code from main.c

    b) Give a well documented (but not overdocumented) makefile appropriate for this project. It should automatically make application when the user types the make command. (1.0 points)

            # Makefile
            # make, with no arguments, builds application
            # Build application from its components
            application: main.o output.o list.o
                    cc -o application main.o output.o list.o
            # Build the components
            main.o: main.c output.h list.h
                    cc -c main.c
            output.o: output.c output.h
                    cc -c output.c
            list.o: list.c list.h
                    cc -c list.c
            # Construct list.c from list using crunchlist
            list.c: list crunchlist
                    crunchlist < list
            # Build crunchlist, if needed
            crunchlist: crunchlist.c list.h
                    cc -o crunchlist crunchlist.c

  2. Background: Christopher Strachey's implementation of objects involved placing pointers to the subroutine implementing each method of the class in each object, so that a call to object.method(p) was translated to object->method(object,p) (which means the same thing as (*object).method(object,p)). That is, use the method field of the object as a pointer to a subroutine, then call that subroutine, passing the pointer to the object itself as the first parameter.

    For classes with large numbers of methods, Strachey's implementation leads to a large number of pointers to subroutines cluttering up the representation of each object.

    A Question: An alternative is to have the method table of each class stored just once, with a pointer in each object in the class pointing to the method table for that class. In this case, each object would contain a field called myclass pointing to the method table for the class of that object. Write out, in C, the code that would correspond to this implementation of the method call object.method(p) (0.5 points)

            ((*(* object).methodtable).method)(object,p);
            (object->methodtable>method)(object,p); /* equivalent */

  3. Background: With block-structured devices, the natural unit of reading or writing is one block of data, such as a disk sector, and we would implement character sequential access to such a device with a layer of software that sits above the block-level I/O routines. With character structured devices, the natural unit or reading or writing is one character, and we would implement block access to such a device using a layer of softwaare that sits above the character sequential I/O routines.

    A Question: How does this challenge the concept of an object hierarchy as used in languages such as Java, C++ and C# (not to mention Simula 67, where the idea originated). (0.5 points)

    For a block structured device, the general class adds stream operations to the block operations it inherits from the base class. For a sequential device, the general class adds block operations to the stream operations it inherits from the base class. This suggests that the programming environment will need to support some kind of multiple inheritance.

  4. Background: The Unix file abstraction supports three basic operations, read(), write() and lseek(). Use the man command to read up on these (they're system calls, so use man 2 write to avoid being distracted by shell commands with the same name).

    C programmers usually use a stream abstraction where the basic operations are fputc(), fgetc() and fseek() -- in terms of which the other routines in stdio.h can be written. Note that fputc() is implemented using read().

    It is quite possible to substitute read(0,&ch,1) instead of ch=fgetc(stdin). Both get a single character from the standard input stream.

    A Question: Obviously, using the C stream interface makes the code more portable, but there is also a performance reason to use the C interface instead of the system call. Explain this. (0.5 points)

    Calls to stream operations are lightweight calls (only a few simple parameters). Calls to read() and write() are expensive, both because they involve more parameters, but also because the file descriptor parameter is an array index into an array of pointers to device descriptions, and then read() or write() must dispatch to the appropriate method of the underlying device driver. Doing this for each character is inefficient, while the C stream operations can be implemented with a large buffer so that most calls to the stream operators just use the buffer and only occasionally do the stream operations call read() or write() to move the buffer to or from the device.