Advanced Programming (CS3995) Spring 2002 -- Final Exam Solutions

This is a closed book, closed notes exam. However, you may use the slides for the bash, Tcl, and python chapters.

You have two hours and thirty minutes (150 minutes) to complete the exam. The exam questions are labeled with their points in ^[], adding up to 150. The number corresponds roughly to the amount of time it should take to finish each problem.

Your blue book must contain the problems in numerical order, with no more than one problem per page.

You must hand in your exam sheet with your blue book.

Statistics

Mean 73.1
Median 81.2
Std. Dev. 23.0

^[5] How can one use gdb to find out where a program has crashed?
```
$ gcc -g buggy.c
$ gdb a.out core
(gdb) where
```
Alternatively, you can run the program within the debugger and step through the program until the program crashes, or set breakpoints and let it run.
^[4] Name four locale properties.
Locale describes I18N properties of the current location, such as the language, default character set, the numeric decimal point, the currency symbol, the date format, the collation sequence for sorting, and "yes" and "no" in the local language.
^[5] How are a program and a process related and how are they different?
A program is the static executable ("text"), i.e., a sequence of machine instructions. It is generally stored as a file. A process is a program in execution. It runs on a processor and has a virtual memory space allocated to it for heap and stack. A program is passive, a process is active. A single program can be run in multiple processes. Note that a program does not fork processes - when running a program, the shell starts a process that then runs the instructions in the program text.
^[10] Write the world's most inefficient (well, close...) way to computing a factorial, recursively. Instead of invoking a function, create a Unix process that returns that result. You can choose the mechanism to return the result, but be sure that it works even if multiple copies of your program waste CPU cycles at the same time. The program is to be written in C.

n! = n * (n-1)! = n * (n-1) * (n-2) * ... * 1
The code here implements this; system() can also be used or one can simply fork. (Details such as WEXITSTATUS() or the precise arguments to exec() are not needed for full credit.) The solution here is limited by the method of returning values. Exit status values are limited to 8 bits for positive numbers. It is also possible to return the value as a file, but the file name must be unique, e.g., generated from the process identifier.
^[40] Multi-lingual programming: For each language, sketch two functions that implement a simple queue of strings, i.e., where one function adds a string to the end of the queue, and the other returns and removes the first element. The pseudo-code prototype might be
```
void AddToQueue(queue, string)
string RemoveFromQueue(queue)
```
You may also add a CreateQueue function where necessary.
1. C ^[10]
  queue.c
2. Python ^[10]
  queue.py
3. bash ^[10]
  
  Bash doesn't have lists, so arrays need to be used. Also, arguments in bash are by-reference only, so that global variables have to contain the results. This illustrates the difficulty of doing programming requiring anything but atomic types in bash. queue.bash
4. Tcl ^[10]
  queue.tcl
^[6] What are the three major differences between Java servlets and cgi scripts?
1. Java servlets are (surprise) written in Java, while cgi scripts can be written in any language.
2. Servlets maintain program state, just like a normal Java program, across requests, while each cgi script is a new process.
3. A servlet is a single process, while a new process is created for each cgi script.
4. In CGI, form variables are passed as environment variables, while servlets can extract them via defined classes.
^[8] Give an example of a data-driven ^[2] and of an event-driven ^[2] application. For each, sketch the basic program outline, using your example ^[2ea].
A sorting application is data driven: It reads data elements, sorts them in memory and then outputs the result.
```
main() {
  while (not end-of-file) {
    read line of data
  }
  sort()
  output data
}
```
A web server is event-driven: it waits for an external event (a web request) and processes it.
```
main() {
  while (1) {
    wait for request
    process request and return web page    
  }
}
```
Similarly, a GUI-based application such as a game or text editor is event-driven, with an event loop:
```
main() {
  while (1) {
    wait for keyboard or mouse event
    act on event
  }
}
```
or, in a callback-based architecture:
```
main() {
  callback(keyboard, keyboard_handler)
  callback(left_mouse, mouse_handler, left)
  callback(right_mouse, mouse_handler, right)
  while (1) {
    call functions on events
  }
}
```
^[6] Using Tcl/Tk, give an example of a synchronous and asynchronous operation. (Describe the operation ^[3] and show a code fragment ^[3].)
Any of the operating system functions are synchronous, i.e., they block until the operation succeeds. For example,
```
  set f [open test.dat]
  read $f
```
Many of the Tk widgets support asynchronous operations, i.e., they install a callback function that gets called when the event, such as a keypress, occurs.
```
  button .b -command buttonpressed
```
^[4] Why are signals needed in Unix? Could you achieve the same effect by just returning an appropriate status code for system calls?

It is possible to have system calls return status values indicating internal errors or external events ("control-c pressed"). However, this relies on the program to handle these events properly. It would also be much more tedious since each system call would need such code.
Signals are needed to indicate asynchronous events in a program. Events that trigger signals can occur at any time, not just in system calls. For example, segmentation faults, bus errors or divide-by-zero errors can occur in normal user code. One could poll for these events, but this would be far less efficient.
Signals can also be used to synchronize two processes.
^[12] Add to the C function below code that exits the loop if there is an error in the 'fp' function that causes a signal. (You can pick any signal; real applications would handle several different ones.) The loop() calls a user-provided function for a range of numbers and prints the results. The core code fragment is:
```
void loop(int (*fp)(int))
{
  int i;
  for (i = 1; i < 1000; i++) {
    printf("%d = %d\n", i, (*fp)(i));
  }
}
```
Also, write a simple main() to complete the program.
Any signal can be used; for simplicity, the program below triggers the SIGFPE (floating-point fault) signal when the function divides by zero. loop.c As an alternative that avoids the use of longjmp(), the signal handler can set a global variable that causes the loop to exit when a signal (here, SIGUSR1) is received. However, this does not work if the error is a system error, as this will cause the code after the error condition to be executed, with the system in an undefined state. For SIGFPE, the program coredumps.
^[4] What is a re-entrant function? Give an example of a function that is not re-entrant and describe why.
A re-entrant function is defined as follows: "A function whose effect, when called by two or more threads, is guaranteed to be as if the threads each executed the function one after another in an undefined order, even if the actual execution is interleaved." In particular, a re-entrant function cannot use global or static variables or call malloc. An example of a non-reentrant function could be
```
char *gettime(void) {
  static char timebuf[80];
  ... fill in time ...
  return timebuf;
}
```
^[6]
1. What is serialization?
  Serialization converts structured data, such as trees, linked lists or arrays, to a linear sequence of bytes that can be stored in files or transmitted across a network.
2. How is serialization done in Python?
  Using 'pickle'.
3. Give a brief XML example of serialization, using the C struct
```
struct {
  char *date;
  int available_time;
  struct {
    char *text;
    char points;
  } problem[20];
} exam;
```
  There are many possible variations, depending on whether elements are written as tags or parameters. example
^[6] What are three important drawbacks of pure XML? Are there mechanisms to address these drawbacks?
- XML is verbose. Compression (gzip and similar) can help.
- XML only has textual (untyped) data. XML schema can identify the type of data needed.
- XML does not deal well with binary data. Base64 encoding is possible, but not efficient. Depending on the context, minimal escaping may be sufficient.
^[4] "Scripting languages are interpreted and C/C++ is compiled." True, true-but or false? Explain.
False or at best true-but. Most modern scripting languages (Tcl, Perl and Python) are compiled into byte code, which is then interpreted. There is no user-visible compilation step.
^[4] What is awk particularly suited for?
Awk is particularly well suited for processing line-oriented text files, applying operations based on the content of each line.
^[4] Name two limitations of bash, compared to Tcl and Python.
- Bash has far fewer data structures, being basically limited to arrays with numerical indices. For example, it does not have lists, associative arrays or structures.
- Bash functions can only return small integers.
- There is no pass-by-reference mechanism.
- Function arguments are positional only ($1, $2).
- Bash has no namespaces and no modules.
- Bash has no object-oriented capabilities.
- Bash cannot be embedded or easily extended.
- Bash has no GUI functionality equivalent to Tk.
^[8] Given only a Python function that sums and the sum of the first and the square of the second number and returns the result (as a sequence), write a function that takes a sequence and returns the average and variance. Your part of the code should not do any arithmetic except scaling the result.
The reduce() function "returns a single value constructed by calling the binary function func on the first two items of the sequence, then on the result and the next item, and so on". stats.py
^[4] Give at least two examples of namespaces that we have seen. What is the primary function of a namespace?
Python, Tcl and XML have namespaces. They allow modules to assign globally visible names without having to worry about collision with other modules.
^[6] Suggest three ways that a web (cgi) programmer can maintain per-client state when building a web application. Briefly compare their advantages and disadvantages.
State can be either the full state (e.g., all the user's preferences) or a reference to state on the server (a "handle"). State can be maintained by

Cookies:
Persist across sessions, but are sometimes disabled by users. Also, may have privacy implications.
Hidden form elements:
Only work within a single session. Cannot be book-marked. Are least likely to get disabled or lost.
Data in URLs:
Only work within a single session. Unlike hidden form elements, they can be bookmarked. If passed around from user to user, they can confuse the system.
^[4] What is the 3-tier model and what are its advantages?
The 3-tier model is commonly used for web-based applications. The client-tier provides the user interface and renders data. The most common example is the web browser. The application-server tier performs the actual data processing. In a web environment, the web script or servlet performs this function. The data-server tier provides data storage, typically implemented as a relational database. The advantage of the 3-tier model is that it allows to separate concerns into different elements and change them independently. For example, it allows the business logic to be implemented without having to worry about the details of data storage or the capabilities of the user interface.

Last updated by Henning Schulzrinne