Answer key for final exam in COM 1358, spring 2000.

17 students took the test.  The low score was 42, the median was 76, and
the high was 100.  The arithmetic mean was 77, and the sample deviation
was 15.9.

For each question, the percentage of credit that was earned by students
is shown in square brackets following the question.

                           Name_______________________________________

Final exam.
COM 1358.  Analysis of Programming Languages.
Spring 2000.

Each multiple choice question is worth 4 points.  Other questions are
worth the number of points shown within brackets.

Unless otherwise specified, all code is written in the language of
Section 3.9 (at the end of Chapter 3), extended with comparisons,
print(_) expressions, and begin/end expressions.


 1.  Aliasing occurs when 

     ____  A.  more than one computer is on a network.

     ____  B.  a class has more than one method.

     ____  C.  a computer can support more than one user.

     ____  D.  two programmers share the same office.

     _XX_  E.  two variables denote the same location.                   [100%]


 2.  What sequence of integers is printed by this C++ program?

          #include <iostream>

          int f (int& x, int& y) {
              x = x + x;
              y = y + y;
              return x;
          }

          main() {
              int a = 2;
              int b = 3;
              cout << f (a, b) << ", ";
              cout << f (a, a) << endl;
          }

     ____  A.  4, 8

     ____  B.  6, 8

     ____  C.  4, 6

     ____  D.  6, 4

     _XX_  E.  4, 16                                                      [65%]


 3.  Which of the following grammars generates the string

          $ $

     ____  A.  X  ::=  $  |  X $ $  |  $ $ X

     ____  B.  X  ::=  $  |  $ $ X  |  X X $

     _XX_  C.  X  ::=  $  |  $ $ $  |  X X                               [100%]

     ____  D.  X  ::=  $  |  $ $ X  |  X $ X

     ____  E.  X  ::=  $  |  $ X $  |  $ $ X


 4.  Which of the following strings is generated by the grammar

          Y  ::=  $  |  Y * Y  |  Y - Y

     ____  A.  - * - * - * - * - * -

     ____  B.  * $ * $ * $ * $ * $ -

     ____  C.  $ - $ - * * * - $ - $

     ____  D.  $ * $ $ - $ $ * $ $ *

     _XX_  E.  $ - $ * $ * $ * $ - $                                     [100%]


 5.  Which of the following expressions goes into an infinite loop
     under call-by-value, but not under call-by-name?

     ____  A.  let f = proc (f) (f f)
                   g = proc (g) (g g)
               in (g (f f))

     ____  B.  let f = proc (f) proc (f) 17
                   g = proc (g) (g g)
               in (g (f f))

     _XX_  C.  let f = proc (f) (f f)                                     [59%]
                   g = proc (g) 17
               in (g (f f))

     ____  D.  let f = proc (f) 17
                   g = proc (g) (g g)
               in (f g)

     ____  E.  let f = proc (f) proc (f) 17
                   g = proc (g) (g g)
               in (g g)


 6.  Which set is the set of variables that occur free within

          proc (m, n)
            let f = proc (x, y, z) (g m x)
                g = proc (a, b) (f g n b)
                i = (g n m)
            in (i f g)

     _XX_  A.  { f, g }                                                   [76%]

     ____  B.  { i, m, n }

     ____  C.  { m, n, x }

     ____  D.  { a, b, f, g, m, n, x, y, z }

     ____  E.  { b, m, n, x }


 7.  With single inheritance and 1-way dynamic method dispatch,
     a dynamic call to a zero-argument method m for an object o
     is typically implemented by

     _XX_  A.  fetching the class of o, fetching the method table         [88%]
               out of the class of o, fetching the code pointer at
               the lexical address of m, and jumping to that code.

     ____  B.  using the rlwinm (Rotate Left Word Immediate then aNd
               with Mask) instruction to combine the address of o
               with the name of m (represented as a Unicode string),
               and jumping to the resulting address.

     ____  C.  jumping to the code for m, using instanceof to
               determine the class of o, loading the code for that
               class from a source file, and interpreting any code
               for a method named m that appears within that file.

     ____  D.  searching the runtime environment to find the class
               hierarchy, searching the class hierarchy to locate
               all classes that have o as an instance, choosing one
               of those classes at random, searching for a method
               named m within the chosen class, and jumping to its
               code.

     ____  E.  dynamiting the root of the class hierarchy, exclusive
               ORing any loose code fragments with the address of o,
               and jumping off a cliff.


 8.  Among other things, the halting problem shows that

     ____  A.  separators are better than terminators.

     ____  B.  the parsing problem for context-free languages is
               undecidable.

     ____  C.  Turing machines are equivalent to finite automata.

     ____  D.  object-oriented languages are more powerful than
               procedural languages.

     _XX_  E.  some problems have no solutions.                           [94%]


 9.  All general purpose programming languages are Turing equivalent
     because, for all general purpose programming languages A and B,

     _XX_  A.  we can write a program in language A that interprets      [100%]
               programs written in language B.

     ____  B.  the control structures of A are a subset of the
               control structures of B.

     ____  C.  identifiers are spelled the same in A as in B.

     ____  D.  the syntax of A is a minor variation of the syntax
               of B.

     ____  E.  A runs on every computer system that B runs on.


10.  The partial recursive functions are the same as the

     ____  A.  total recursive functions.

     _XX_  B.  functions that are computable by some Turing machine.      [47%]

     ____  C.  finite functions.

     ____  D.  primitive recursive functions.

     ____  E.  projection functions.

[Note:  None of the alternatives are actually correct.  Alternative B
should have said "partial functions that are...", but was still the
best of the five choices.]


11.  Which parameter-passing mechanism is likely to make the following
     program run the fastest?  [Hint: (fib 10) evaluates to 55, and
     (fib 30) evaluates to 832040.]

          print (letrec fib (n) = if less? (n, 2)
                                      then n
                                      else let n1 = -(n, 1)
                                               n2 = -(n, 2)
                                           in + ((fib n1), (fib n2))
                        loop (n, m, ignored) =
                            if less? (n, m)
                                then m
                                else let n = add1 (n)
                                     in (loop n m ignored)
                 in let one = 1
                        ten = 10
                        thirty = 30
                    in (loop one (fib ten) (fib thirty)))

     ____  A.  call-by-value-result

     ____  B.  call-by-name

     ____  C.  call-by-reference

     _XX_  D.  call-by-need                                               [59%]

     ____  E.  call-by-value


12.  Java classes and methods provide

     ____  A.  multiple inheritance, 1-way static method dispatch
               (overloading), and n-way dynamic method dispatch

     _XX_  B.  single inheritance, n-way static method dispatch           [47%]
               (overloading), and 1-way dynamic method dispatch

     ____  C.  multiple inheritance, n-way static method dispatch
               (overloading), and 1-way dynamic method dispatch

     ____  D.  single inheritance, 1-way static method dispatch
               (overloading), and n-way dynamic method dispatch

     ____  E.  all of the above


13.  Which of the following programming languages uses call-by-name
     as its default parameter passing mechanism?

     _XX_  A.  Algol 60                                                   [71%]

     ____  B.  C++

     ____  C.  Scheme

     ____  D.  Ada

     ____  E.  Java


14.  Which of the following programming languages may use
     call-by-value-result for certain parameters?

     ____  A.  Algol 60

     ____  B.  C++

     ____  C.  Scheme

     _XX_  D.  Ada                                                        [47%]

     ____  E.  Java


15.  [5 points]  Write code for a Scheme procedure named tree-contains?
     that takes two arguments, a symbol x and a bintree t, and returns #t
     if x occurs as the label of some interior node of t, and returns #f
     otherwise.  The definition of a bintree appears below.

          (define-datatype bintree bintree?
            (leaf-node
              (datum number?))
            (interior-node
              (key symbol?)
              (left bintree?)
              (right bintree?)))

          ;  A question like this has infinitely many correct answers.
          ;  This code is untested.

          (define tree-contains?                                          [84%]
            (lambda (x t)
              (cases bintree t
                (interior-node (k t1 t2)
                  (or (eq? x k)
                      (tree-contains? x t1)
                      (tree-conttains? x t2)))
                (else #f))))


16.  What sequence of letters is printed by this Java program?

          public class A {
              public static void main (String[] args) {
                  A a = new A();
                  B b = new B();
                  C c = new C();
                  c.m (a, b, c);
              }
              void m (A x, A y, A z) {
                  System.out.print (x.id());
              }
              String id () { return "A "; }
          }

          class AA extends A {
              void m (A x, A y, A z) {
                  System.out.print (x.id());
                  y.m (y, z, x);
              }
          }
          
          class B extends AA {
              String id () { return "B "; }
          }
          
          class C extends AA {
              String id () { return "C "; }
          }

     ____  A.  C B A A

     ____  B.  C B C A

     _XX_  C.  A B C A                                                    [88%]

     ____  D.  C B A

     ____  E.  A A A A


17.  The Java code shown in the preceding question illustrates

     ____  A.  abstract methods

     _XX_  B.  subclass polymorphism                                      [94%]

     ____  C.  holographic rutabagas

     ____  D.  call-by-value-result

     ____  E.  final methods


18.  The variant records of Pascal and the unions of C/C++
     correspond most closely to which feature of Java?

     ____  A.  synchronized methods

     ____  B.  garbage collection

     _XX_  C.  abstract classes                                           [94%]

     ____  D.  exceptions

     ____  E.  static methods


19.  [15 points]  For each assignment to or use of a variable that        [85%]
     appears within the following program, draw an arrow from the
     assignment or use to the corresponding declaration of that
     variable.  You should draw 15 arrows.

          var a, b, c;
          var x, y, z;
          var b, c;
          {
              a = 1;
              c = 3;
              x = + (7, let f = proc (c) -(c, a)
                        in (f add1(c)));
              z = proc (c) greater? (c, a);
              while (z x) do x = -(c, 3);
              print (x)
          }

     [Note:  About half of the students got this completely right.
     The most common errors were:
         *  drawing arrows whose tail began at a binding occurrence
         *  failing to see the declarations of b and c on line 3
         *  failing to see the declarations of c in the proc expressions
         *  drawing use-def arrows from uses to assignments
     ]


Questions 20 through 21 ask about the consequences of changing the
semantics of our source language's let expressions from

     (define eval-expression
       (lambda (exp env)
         (cases expression exp
           ...
           (let-exp (ids rands body)
             (let ((args (eval-rands rands env)))
               (eval-expression body (extend-env ids args env))))
           ...
           )))

to

     (define eval-expression
       (lambda (exp env)
         (cases expression exp
           ...
           (let-exp (ids rands body)
             (let ((newenv (eval-let-rands ids rands env)))
               (eval-expression body newenv)))
           ...
           )))

where eval-let-rands is defined by

     (define eval-let-rands
       (lambda (ids rands env)
         (if (null? ids)
             env
             (let ((value (eval-expression (car rands) env)))
               (let ((newenv (extend-env (list (car ids))
                                         (list value)
                                         env)))
                 (eval-let-rands (cdr ids)
                                 (cdr rands)
                                 newenv))))))


20.  [5 points]  With the change shown above, what integer would          [87%]
     be printed by the following program?

          var x, y, z;
          {
              x = 1; y = 22; z = 333;
              print (let x = add1(x)
                         y = add1(x)
                         z = add1(y)
                         g = proc () z
                     in (g))
          }

     Answer: 4


21.  [7 points]  The change shown above would change the free             [42%]
     variables of a let expression.  On the midterm, these free
     variables were calculated as follows.

     (define free-variables
       (lambda (exp)
         (cases expression exp
           ...
           (let-exp (ids rands body)
             (set-union
              (reduce-left set-union
                           (empty-set)
                           (map free-variables rands))
              (set-difference (free-variables body)
                              (reduce-left set-union
                                           (empty-set)
                                           (map singleton ids)))))
           ...
           )))

     Show how the free variables of a let expression should be
     calculated for the changed semantics of let expressions.

     (define free-variables
       (lambda (exp)
         (cases expression exp
           ...
           (let-exp (ids rands body)
             
             ; Questions like this have infinitely many correct answers.
             ; This code is untested.
             
             (letrec ((free-in-rands
                       (lambda (ids rands)
                         (if (null? rands)
                             (empty-set)
                             (set-union (free-variables (car rands))
                                        (set-difference
                                         (free-in-rands (cdr ids) (cdr rands))
                                         (singleton (car ids))))))))
               (set-union (free-in-rands ids rands)
                          (set-difference
                           (free-variables body)
                           (reduce-left set-union
                                        (empty-set)
                                        (map singleton ids))))))
           ...
           )))