Computer Science 3675
Fall 2014
Practice Questions for Quiz 6

1. True or false?

   1. Programs written in an object-oriented style tend to be organized significantly differently from programs written in a functional or procedural style. Answer

   2. All object-oriented programming languages are statically typed. Answer

   3. In object-oriented programming, an object is represented as a structure holding variables and all of the methods that the object can perform. Answer

2. In a single-inheritance object-oriented language, is there a limit on the number of base classes that a class can have? Answer

3. In a single-inheritance object-oriented language, is there a limit on the number of subclasses that a class can have? Answer

4. In object-oriented programming, you imagine that objects carry methods with them. Yet, the methods are not really stored with the objects. How does an object locate its methods? How does it know which methods to select? What is the name of the system support that is responsible for locating methods? Answer

5. How does the mechanism for inheriting variables work in single-inheritance object-oriented languages? Is there a separate implementation of each selector for each class, or does one implementation of each selector work for all classes? How do the selector(s) work? Answer

6. What are the characteristics of a virtual method? What makes it virtual? Answer

7. What is an abstract class? Answer

8. What is the significance of λ-calculus to the semantics of programming languages? Answer

9. If you perform a single beta reduction on expression (λx.λy.x x y)(λz.z z), what do you get?

   1. λy.λz.z z (λz.z z) y
   2. (λx.λy.x x y) (λx.λy.x x y)
   3. λx.λy.(x x y) (x x y)
   4. λy.(λz.z z) (λz.z z) y
   Answer

10. For this problem, the following λ-calculus functions are assumed to be predefined, where x and y are Church-numerals and true and false are the standard boolean values.

    • if is the conditional function (if A B C = B when A = true and C when A = false),
    • isZero(x) yields true if x = 0 and false if x ≠ 0,
    • times x y is the product of x and y,
    • pred x is x − 1, for x > 0 and pred 0 = 0,
    • fix is a fixed-point finding function.

    Suppose that function k is defined in λ-calculus by k = λf.λx.if (isZero(x)) (1) (times (2) (f (pred x))).

    If function g is defined by g = fix k, then which of the following is true of g?
    1. g(0) = 0, g(1) = 1, g(2) = 2.
    2. g(0) = 1, g(1) = 2, g(2) = 4.
    3. g(0) = 1, g(1) = 1, g(2) = 1.
    4. g(x) has no normal form for every Church-numeral x.

    Answer