UNM Computer Science

Programming Languages and Systems
Comprehensive Exam
In-Class Version

August 18, 1997
Computer Science Department
University of New Mexico

The test monitor will answer some parts of these questions for you if you are unsure of what some of these terms mean. The only penalty is that you will not get any points for the part that was answered for you. You can still answer the other parts of the question. This can get you started on a question even if you are not sure of the definitions.

You can do any questions you want. You do not have to do all the parts of a single question. Instead you can pick the parts you want to answer. Be sure that is is absolutely clear which questions you are answering.

Do enough questions to total at least 100 points. It is okay to go over 100 points and you can answer as many questions as you wish but all the questions you answer will be counted in your grade and the total will be normalized to 100 points. We will not take the best 100 points

1. Translator Architectures
   1. (9 points) Describe the architecture of a typical compiler, that is, what are the major modules in a compiler and what do they do. Draw a block diagram showing the modules and the data flows between them. Hint: each modules does one step in the processing and the modules are arranged in a pipeline where the output of one is the input to the next one.

      Describe the input and output of each module. Also show any other data structures that are used by a compiler, that is, data that does not flow between modules directly put persists over two or more stages of processing.

      Give a C struct (or C++ class) definition of the type of the data items that are passed between modules in a compiler and for the items in any other data structures you identified.

   2. (3 points) Indicate the differences (if there are any) in the description of a compiler (that you did for part (a)) if you were talking about a byte-code compiler, that is, a compiler that generates byte code for a virtual machine (such as is used in Emacs Lisp and Java).

   3. (4 points) Indicate the differences (if there are any) in the description of a compiler (that you did for part (a)) if you were talking about a ``just-in-time'' compiler that compiles byte codes to machine language as the byte codes are being executed.

   4. (4 points) Do the same thing for an interpreter as you did for a compiler in part (a) above.

2. Objects hierarchies
   1. (4 points) Some object-oriented languages require all objects to be subclasses of a single root object (often called ``Object''), that is, the inheritance graph is a tree. Give an example of such a language. Some languages do not require this. Give an example of such a language.

   2. (5 points) A language with a single object hierarchy can implement container objects (that is, objects like stack, queue, list, map, etc. that contain other objects) more easily than languages without a single object hierarchy. Explain why this is. (Hint: The answer we want is related to strong typing.) Does the single object hierarchy solve all the problems with typing and container objects? If not, explain what other problems it fails to solve.

   3. (3 points) How does this relate to the template facility in C++?

   4. (4 points) The C++ template facility is a parameterized type facility, sometimes called generic types. Similar facilities are provided in other languages such as Ada and Eiffel. Explain how this facility is related to inheritance. How is it the same and how is it different?

   5. (4 points) Give another advantage of a single object hierarchy.

3. Inheritance
   1. (4 points) Explain the distinction between interface inheritance and implementation inheritance.

   2. (5 points) Is this the same distinction as between public and private inheritance in C++? Explain how they are the same and how they are different.

   3. (6 points) In object-oriented programming languages, we talk about the is-a relation defined by inheritance (if A inherits from B then A is-a B) and the has-a relation (if A includes a B as a data member then A has-a B). Is this the same distinction as that between interface and implementation inheritance? Explain how they are the same and how they are different and how they are related.

4. Declarations
   1. (6 points) Give two reasons for requiring variables to be declared in a language. One should have to do with program correctness and one should have to do with program efficiency (in time or space or both).

   2. (4 points) There is a class of languages called scripting languages which typically do not require variable to be declared. Some examples are shell languages, Tcl, and Perl. What is the advantage of not requiring variables to be declared?

   3. (4 points) If a language does not require variables to be declared, how does it know what type they are?

   4. (6 points) Some functional languages (principally ML) do not require type declarations but are still strongly typed. They use type inferencing to determine the type of variables. Explain what type inferencing is and give a simple example.

5. First class objects

   A first class object in a programming language is a language object that can be created dynamically, stored in a variable, passed as a parameter to a function and returned as a result by a function. Consider the following list of language objects:

   1. integer variable
   2. string
   3. array
   4. structure or record
   5. procedure
   6. object (in the object-oriented programming sense)
   7. class
   8. label

   For up to four of the following languages go through each of the above objects and say whether or not they are first class objects. If there is any ambiguity please explain that. If it is not a first class object in the language explain how it fails to be a first class object.

   1. C
   2. C++
   3. Smalltalk
   4. Ada83 or Ada95
   5. Common Lisp with CLOS
   6. SML (Standard ML)
   7. Prolog

   You can do up to four languages and each language counts 5 points. You can do another language with the approval of the computer science test monitor.

6. Shallow and deep copy
   1. (4 points) Explain the difference between a shallow and a deep copy. Give examples of each.

   2. (5 points) In a pure functional language, the difference between a shallow and a deep copy is much less important. Explain why this is. It is important (in a pure functional language) in equality testing. Explain why.

   3. (6 points) What mechanisms in C++ affect the implementation of shallow and deep copy? How are they used?

7. Names and Namespaces
   1. Name resolution is the process by which a name is mapped to the object it refers to. Sometimes name resolution requires you to look at more than one namespace. Describe how name resolution works in some of the languages mentioned below.

      Many programming languages use qualified and/or compound names. For some of the languages mentioned below describe the ways in which names can be combined to form compound names and ways in which names can be qualified to change or disambiguate their meaning.

      You can choose up to four languages and each language counts for 4 points.

      1. C
      2. C++
      3. Smalltalk
      4. Ada83 or Ada95
      5. Common Lisp with CLOS
      6. SML (Standard ML)
      7. Prolog

   2. (4 points) In some languages, objects of different types can have the same name at a point in a program, that is, you could have a variable named f and a function named f both visible at a point in a program. Give an example of a language where that is possible. What are the advantages and disadvantages of this feature?

8. Computation in biological systems (20 points)

   The analogy between various biological systems and computation is explored in a number of CS Dept. courses. Choose one candidate biological mechanism (e.g., one aspect of a neural system, population genetics, DNA as a computer program, affinity maturation in the immune system, etc.) and analyze its behavior computationally. Your answer should review earlier such analyses, assess their strengths and weaknesses, and extend the analogies as you see fit.