Do the following problems. The vast majority of these are taken directly from the textbook, because a lot of students are comforted by the idea of textbook problems. Turn in a hardcopy pdf, on the day of the Final Exam.

Readings: [Scott], Chapters 7 and 8, and skim 9 and 10. Consider the "Check Your Understanding" questions as part of your reading assignment (that is, solve as many as you can but do not turn in any solutions).

1. Consider the following C declaration, compiled on a 32-bit Pentium machine:

       struct {
           int n;
           char c;
       } A[10][10];
   

   If the address of A[0][0] is 1000 (decimal), what is the address of A[3][7]?

2. Explain the meaning of the following C declarations:

       double *a[n];
       double (*b)[n];
       double (*c[n])();
       double (*d())[n];
   

3. Using your favorite language and compiler, write a program that determines the order in which subroutine parameters are evaluated.
4. Consider the following (erroneous) program in C:

       void foo() {
           int i;
           printf("%d ", i++);
       }
       int main() {
           int j;
           for (j = 1; j <= 10; j++) foo();
       }
   

   Local variable i in subroutine foo is never initialized. On many systems, however, the program will display repeatable behavior, printing 0 1 2 3 4 5 6 7 8 9. Suggest an explanation. Also explain why the behavior on other systems might be different, or nondeterministic.
5. Write (in the language of your choice) a procedure or function that will have four different effects, depending on whether arguments are passed by value, by reference, by value/result, or by name.
6. In some implementations of Fortran IV, the following code would print a 3. Can you suggest an explanation? How do you suppose more recent Fortran implementations get around the problem?

         call foo(2)
         print* 2
         stop
         end
         subroutine foo(x)
             x = x + 1
             return
         end
   

7. Consider the following declaration in C:

       double (*foo(double (*)(double, double[]), double)) (double, ...);
   

   Describe in English the type of foo.
8. What happens to the implementation of a class if we redefine a field? For example, suppose we have:

       class Foo {
           public int a;
           public String b;
       }
       ...
       class Bar extends Foo {
           public float c;
           public int b;
       }
   

   Does the representation of a Bar object contain one b field or two? If two, are both accessible, or only one? Under what circumstances? Answer for C++, Java, and Ruby. In the case of Ruby, show your translation of the above Java code into the closest possible Ruby code that maintains the spirit of the problem.
9. If Foo is an abstract class in a C++ program, why is it acceptable to declare variables of type Foo*, but not of type Foo? Does this problem even make sense to ask in Java or Ruby?
10. Some authors characterize functional programming as one form of declarative programming. Others characterize functional programming as a separate computational model, co-equal with imperative and declarative programming. Which characterization do you prefer? Why?
11. Consider the problem of determining whether two trees have the same fringe: the same set of leaves in the same order, regardless of internal structure. An obvious way to solve this problem is to write a function flatten that takes a tree as argument and returns an ordered list of its leaves. Then we can say

        fun same_fringe t1 t2 = flatten t1 = flatten t2
    

    Write a straightforward version of flatten in ML. How efficient is same_fringe when the trees differ in their first few leaves? How could you improve this, since, after all, ML is an eager, not a lazy, functional language.
12. Write the standard quicksort algorithm in ML, without using any imperative language features. Be careful to avoid the trivial update problem; your code should run in expected time Θ(n log n).