Com Sci 221/321 --- Programming Languages
Assignment #5 --- Autumn 1999
Due Monday, 1 November

Com Sci 221 and 321

1. Old FORTRAN had no records or structures. Sometimes we wanted to use a type of arrays of structures, such as the C type of the variable table below.

   
   table struct {
           A a;
           B b;
         }       [99];
   

   In such a case we had to use, instead, a separate array for each component of the structure:

   
   tableA A[99];
   tableB B[99];
   

   We called this the technique of ``parallel arrays.'' It worked partly because the two set-theoretic types [0..99]->(AxB) and ([0..99]->A)x([0..99]->B) are equivalent in some useful computational sense---they can be used to represent exactly the same information.

   Suppose that you are supporting a small telephone directory, containing names and telephone numbers as character strings, plus a mark on each entry to indicate whether it describes a residential or business phone. For prototyping purposes, you only need to support a directory of up to 10 entries. Telephone numbers are all 10 digits long, and names are at most 30 characters long. Use an array of structures/records to represent such a telephone directory. Rework your binary search program from Assignment #4 to look up the telephone number for any given name, or give a special error message if the name does not appear in the directory. Also provide a procedure to insert a new entry in the directory.




2. Perform the tasks from problem #1 for a telephone directory represented by three parallel arrays, instead of one array of structures.



3. Critique very briefly the difference between the datatypes in your programs in #1 vs. #2. In particular, describe a type of error that could easily be made in processing parallel arrays that is less likely to occur when processing an array of structures. Consider other operations on the datatype besides binary search: sorting is a particularly interesting one. Try to think of a context in which parallel arrays are preferable to an array of structures.



4. Consider the two set-theoretic types [0..99]->(A+B) and ([0..99]->A)+([0..99]->B). Do they represent the same information? Explain briefly.

Com Sci 321 only

1. Propose a sensible practical definition of equivalence between datatypes.