Computer Science & Engineering 505 Midterm - Answer Key November 1992 1. What does it mean for a program to be type correct? What does it mean for a program to be statically type correct? What is the difference? A type correct program is one in which all functions and operations are applied only to objects of the correct type. A statically type correct program is a type correct program, and further one in which all the type checking can be done statically (at compile time), with no runtime checks needed. "Statically type correct" implies "type correct" but not vice versa. The difference is that a program that is just type correct might need to have some runtime checks in it. Name a language (if one exists) in which: (a) every program that compiles without errors is both type correct and statically type correct Ada. (b) every program that compiles without errors is type correct, but not necessarily statically type correct Smalltalk (or Lisp) (c) every program that compiles without errors is statically type correct, but not necessarily type correct None (can't exist, by the above definition). (d) some programs that compile without errors are not statically type correct Smalltalk, Lisp, Fortran, C, Pascal (e) some programs that compile without errors are not type correct Fortran, C, Pascal. [You only need to name one language for each of these subquestions, of course.] 2. Consider the following program in an Algol-like language. ... What is the output if j and k are both passed by: (a) call by value 1,2 1,2 /* for call by value, the assignment to barnacle doesn't affect the value of j or k in the procedure (b) call by name 1,2 4,8 /* here the values of the actual parameters are re-evaluated each time the formal parameter is used */. (c) call by reference 1,2 4,2 /* for the actual parameter that is a variable, the second call finds the updated value. for the actual parameter that is an expression, the compiler makes a temporary, and passes that by reference, so that the change to the value of barnacle isn't seen. (Some languages, for example Pascal, don't allow expressions for call-by-reference parameters; but others, for example Fortran, do.) HOWEVER ... I didn't explain this well in class, so I'm going to count any reasonable answer to the call-by-reference question as correct. */ 3. Compare how multiple inheritance is handled in Extended Smalltalk and CLOS. The key problem in multiple inheritance is how to handle conflicts. Suppose we have a class D that is a subclass of both B and C. B and C in turn are both subclasses of A. A / \ / \ B C \ / \ / D Extended Smalltalk takes a conservative approach to conflicts. If B and C both define a method clam, but D doesn't, then trying to send an instance of D the clam message would give a conflicting inheritance error. Similarly, if A and B both define a message squid, sending an instance of D the squid message would also give an error (since C inherits squid from A). However, if only A defines the mollusc message, instances of D could happily mollusc away without generating an error. The standard approach in CLOS is to form a linear ordering of the superclasses. For D the order would be B,C,A (with B first). If B and C both define a method clam, but D doesn't, then the version in B would be used, since it is first in the list. If A and B both define a message squid, again the version in B would be used. The above is all I need for a correct answer. Here is some additional information that some students might have included: Another source of conflicts is instance variables with the same name. In Extended Smalltalk, if B and C both defined an instance variable x, an error would occur. In CLOS, instances of D would have two different x's. In addition to the linearization discussed above, CLOS also has a powerful and complicated set of method combination constructs. In addition to the primary method, programmers can define before and after methods, and wrappers. In CLOS all of the above can be changed using the meta-object protocol. 4. What is the output from the following program in an Algol-like language? ... in procedure oak -- n=4 k=5 in procedure oak -- n=5 k=5 in procedure oak -- n=3 k=4 in procedure oak -- n=4 k=4 in procedure oak -- n=2 k=3 in procedure oak -- n=3 k=3 in procedure oak -- n=1 k=2 in procedure oak -- n=2 k=2 in procedure nettle in procedure oak -- n=1 k=1 Note that in the body of procedure pine, the call oak(n) calls the procedure oak, with the static link set to the current invocation of pine. However, the call p(n) calls the procedure that was passed as a parameter. For n>1 this will call oak again, but the static link will point to the previous call to pine (hence the different values printed for n=). For n=1 it calls nettle. 5. Consider the following class hierarchy in Smalltalk: ... If we send pressConference to an instance of Politician, the system will look in the class Politician, find the method for pressConference, and execute it. When the statement "self soundBite" is executed, self will be an instance of Politician, and the method for soundBite in Politician will be found, and will return 'more apple pie'. So the whole method will return 'If elected, I promise that there will be more apple pie'. If we send pressConference to an instance of Democrat, the system will look in the class Democrat. There isn't a method for pressConference there, so it will go to its superclass Politician, and find the method for pressConference there. When the statement "self soundBite" is executed, self will be an instance of Democrat, and so the soundBite method in Democrat will be found, returning 'more jobs'. So the whole method will return 'If elected, I promise that there will be more jobs'. If we send pressConference to an instance of Republican, the system will look in the class Republican. There isn't a method for pressConference there, so it will go to the superclass Politician, and find the method for pressConference there. When the statement "self soundBite" is executed, self will be an instance of Republican. The soundBite method in Republican will be found. The body of this method is ^ 'no new taxes' , ' and ' , super soundBite Executing super soundBite causes the method lookup to start in Politician, so that this expression returns 'more apple pie'. Thus the soundBite method for Republican returns 'no new taxes and more apple pie'. Finally, pressConference returns 'If elected, I promise that there will be no new taxes and more apple pie'. [You don't need quite this much detail in your answer on the exam.] 6. Suppose one re-implemented the political example in Question 5 in a prototype-based object-oriented language, but otherwise following the original Smalltalk code as closely as possible. (a) Suppose delegation were being used. Explain what happens when a Democrat is sent the pressConference message. The Democrat object would have a reference to a parent object, the Politician. The Democrat would get the pressConference message. It wouldn't find a method for pressConference, so it would delegate the message to its parent. Politician would find a method for pressConference and run it. When the statement "self soundBite" is executed, since the Politician is executing the code on behalf of the Democrat, the message soundBite is sent to the Democrat. The soundBite method in Democrat will be found, returning 'more jobs'. So the whole method will return 'If elected, I promise that there will be more jobs'. (b) Suppose that one tried to handle this situation by having a Democrat object, with a Politician object as one of its instance variables. Suppose rather than using delegation, when the Democrat received the pressConference message, it just sent it to the Politician object. What would happen? The Democrat would get the pressConference message. It wouldn't find a method for pressConference, so it would send the pressConference message to the Politican object stored in one of its instance variables. Politician would find a method for pressConference and run it. When the statement "self soundBite" is executed, it would find its own soundBite method, and return 'more apple pie'. So the whole method will return 'If elected, I promise that there will be more apple pie'. 7. True or false? [I put a reason down for some of these, but all you needed to answer was T or F.] (a) In Smalltalk-80, while loops are defined using the whileTrue: message, which is sent to a block. True. (b) In Smalltalk-80, every object is an instance of some class. Classes are themselves objects, and each class is an instance of a different metaclass. Each metaclass is an instance of a different meta-metaclass, and so forth. However, to stop the infinite regress, the system only stores 100 levels of meta-meta-meta ... metaclasses, and creates the remaining levels on demand. False. It's almost this bad, but not quite. (c) A "thunk" is an implementation technique for passing parameters by value in Algol-60. False. It's an implementation technique for passing parameters by name. (d) Blocks in Smalltalk-80, like procedures in Algol-60, are not first-class citizens. They can only be passed as parameters, but can't be returned from a method or assigned to a global variable, since if this were done the Smalltalk implementor wouldn't be able to allocate activation records on a stack. False. They are first-class citizens. (e) A FORTRAN loop DO 100 I=1,N will execute zero times if N=0. False. It executes one time! (f) Recursive subroutines aren't supported in standard FORTRAN-IV. True. (g) It is possible for users to define their own kinds of iterators in Smalltalk-80, for example, to traverse a data structure in a given order. True. (h) In Ada, a handler for an exception can optionally retry execution of the code that raised the exception. False. (i) In Ada, if the handler for the ZORK exception re-raised the ZORK exception, the program would get into an infinite loop, since the same handler would get invoked again for ZORK, and so forth. False. If ZORK re-raises the exception, Ada looks for the next handler on the stack; it skips the current one and so there isn't a loop. (j) It would be possible to define the basic control structures (conditionals and loops) in Smalltalk -- they don't need to be primitives. True. (k) COMMON blocks in FORTRAN allow data to be shared among subroutines and the main program, without passing the information as parameters to the subroutines. True. (l) Double-dispatching is a technique for simulating multiple dispatch in a language such as Smalltalk that only supports single dispatch. True. (m) When executing a rendezvous in Ada, the calling task suspends while the called tasks executes the sequence of statements in the accept statement. Thereafter, the two tasks can continue their execution in parallel. True. (n) Ada allows parameters to be passed using both positional and keyword notation; however, in a given call, the notations can't be mixed. False. They can be mixed. (o) True/false questions have no place on an examination in a graduate course; the only time they are given is when instructors are too lazy to grade penetrating page-long answers to essay questions. No comment.