CSE 505 Final

Your name:


December 13, 1994
110 minutes, open notes, 10 points per question, 140 points total
  1. Compare the notion of a variable in Miranda, Algol-60, Smalltalk, and Prolog.

  2. Consider a typical Algol-60 implementation. Give an example of code where the static link and the dynamic link for an activation record both point to the same activation record; and another example in which where they point to different activation records.

  3. Suppose we have classes A, B, and C in Smalltalk. B is a subclass of A, and C is a subclass of B. Each contains a method clam, and another method mollusc, as follows: class A clam Transcript show: 'clam here in class A'. self mollusc. mollusc Transcript show: 'mollusc here in class A'. class B clam Transcript show: 'clam here in class B'. super clam. mollusc Transcript show: 'mollusc here in class B'. class C clam Transcript show: 'clam here in class C'. super clam. mollusc Transcript show: 'mollusc here in class C' What happens when you send the clam message to an instance of A? To an instance of B? To an instance of C?

  4. Consider the task of simulating a Lisp list in Smalltalk-80. Give the definition for a class ConsCell. Cons cells should understand the following messages:

    How are you representing the empty list? Say why you chose that representation, and compare it with alternative possibilities. Give code that constructs the list (1 2 3), and show how to print each element in the list to the Transcript using do:.

  5. Suppose ConsCell were implemented in Bracha and Griswold's Strongtalk system. Show the generic protocol for ConsCell.

  6. Regarding the Strongtalk implementation of ConsCell, is "list of integer" a subtype of "list of number"? Is "list of number" a subtype of "list of integer"? Why?

    What would the relation be if Strongtalk used the covariant rule instead of the contravariant rule?

  7. Suppose you were defining cons cells in SELF instead, following the usual SELF conventions. Describe the objects you would define. Describe the process of making a new list, and of sending it the car message. (In particular describe what messages are delegated to what).

  8. Suppose that B1, B2, and B3 have been declared as global variables in Smalltalk-80. One has the following code in a workspace in Smalltalk-80, and selects it all and then "do it" from the menu. | p1 p2 p3 | B1 := [p1 := Point x: 1 y: 1]. B2 := [p1 := Point x: 100 y: 100]. p1 := Point x: 3 y: 3. p2 := Point x: 10 y: 10. p3 := Point x: 33 y: 33. B3 := [p1+p2]. Subsequently, one selects the following code and says "print it". What is printed? Explain your reasoning. | p1 | p1 := B3 value. B1 value. p1 + B3 value

  9. There is code in the previous example to create points with values (x=1,y=1), (x=3,y=3), (x=10,y=10). (x=33,y=33). and (x=100,y=100). Exactly when, if ever, in the execution of the code are these points created? Exactly when, if ever, do they become no longer accessible and hence subject to being garbage collected? Again, explain your reasoning.

  10. Suppose that one were writing a denotational semantics for Smalltalk, following the semantics given in Cardelli's paper "A Semantics of Multiple Inheritance". When would the meaning of a Smalltalk expression be 'bottom', and when would it be 'wrong'?

  11. Consider the CLOS rules for multiple inheritance, given the following class hierarchy. A / \ B C \ / D In other words, B is a subclass of A, C is a subclass of A, and D is a subclass of B and C (where B is listed before C in the DEFCLASS).

    Describe how the search for a method is performed given a message sent to an instance of D.

  12. Consider the following Prolog definition of append in Prolog. append([],Ys,Ys). append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs). What answers are produced by Prolog for the following queries? Give all of the answers if there is more than one (unless there is an infinite number of answers). ?- append([1,2],[5,6,7],C). ?- append([1,2],B,C). ?- append([1],[5,6],W). ?- append([1,A],B,[1,2,3]). ?- append([1|A],B,[1,2,3]).

  13. Briefly, what are the differences between Constraint Logic Programming and Prolog?

  14. More tacky but easy-to-grade true/false questions!

    1. The binding of an exception to an exception handler is done using lexical scoping rules in both Ada and Smalltalk-80.
    2. Miranda is a higher-order language, since functions can take other functions as arguments, or return them as results.
    3. The "cut" operator in Prolog is used to prune off branches of the seach tree.
    4. The search order in Prolog is breadth first.
    5. The CLP(R) implementation of Jaffar et al. uses several constraint solvers that work in combination. When possible the implementation uses a faster and less general solver rather than a general and slower one.