Please answer all questions or none at all. Thank you in advance.

8.1 Suppose we are compiling for a machine with 1-byte characters, 2-byte shorts, 4-byte integers, and 8-byte reals, and with alignment rules that require the address of every primitive data element to be an even multiple of the element's size. Suppose further that the compiler is not permitted to reorder fields. How much space will be consumed by the following array? Explain.

A : array [0..9] of record

s : short

c : char

t : short

d : char

r : real

i : integer

8.2 In Example 8.10 we suggested the possibility of sorting record fields by their alignment requirement, to minimize holes. In the example, we sorted smallest-alignment-first. What would happen if we sorted longest-alignment-first? Do you see any advantages to this scheme? Any disadvantages? If the record as a whole must be an even multiple of the longest alignment, do the two approaches ever differ in total space required?

8.3 Give C code to map from lowercase to uppercase letters, using (a) an array (b) a function Note the similarity of syntax: in both cases upper('a') is 'A'.

8.6 Explain how to obtain the effect of Fortran 90's allocate statement for one-dimensional arrays using pointers in C. You will probably find that your solution does not generalize to multidimensional arrays. Why not? If you are familiar with C++, show how to use its class facilities to solve the problem.

8.7 Example 8.24, which considered the layout of a two-dimensional array of characters, counted only the space devoted to characters and pointers. This is appropriate if the space is allocated statically, as a global array of days or keywords known at compile time. Supposed instead that space is allocated in the heap, with 4 or 8 bytes of overhead for each contiguous block of storage. How does this change the tradeoffs in space efficiency?

8.12 Consider the following C declaration, compiled on a 64-bit x86 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]?

8.16 Explain the meaning of the following C declarations:

double *a[n];

double (*b)[n];

double (*c[n])();

double (*d())[n];

8.20 (a) Occasionally one encounters the suggestion that a garbage-collected language should provide a delete operation as an optimization: by explicitly delete-ing objects that will never be used again, the programmer might save the garbage collector the trouble of finding and reclaiming those objects automatically, thereby improving performance. What do you think of this suggestion? Explain.

(b) Alternatively, one might allow the programmer to tenure an object, so that it will never be a candidate for reclamation. Is this a good idea?

8.22 Here is a skeleton for the standard quicksort algorithm in Haskell:

quicksort [] = []

quicksort (a : l) = quicksort [] ++ [a] ++ quicksort []

The ++ operator denotes list concatenation (similar to @ in ML). The : operator is equivalent to ML's :: or Lisp's cons. Show how to express the two elided expressions as list comprehensions.