CSE 505 Midterm -- Answer Key

1. (24 points) Suppose the following Miranda script has been filed in. weird * ::= Nothing | I num | B bool | Anything * tree * ::= EmptyTree | Node * (tree *) (tree *) my_const k x = k my_map f [] = [] my_map f (x:xs) = f x : my_map f xs double x = 2*x tree_map f EmptyTree = EmptyTree tree_map f (Node x left right) = Node (f x) (tree_map f left) (tree_map f right) What is the result of evaluting the following Miranda expressions? If there is a compile-time type error, or a non-terminating computation, say so. If the result is an infinite data structure, give some initial parts of it. If the expression is followed by ::, then give the type instead of the value. my_map double [1..] [2,4,6,8, ...] my_map double :: [num] -> [num] my_map (my_const False) [] :: [bool] my_const :: * -> ** -> * I 3 :: weird * Anything 3 :: weird num [I 3, B False, Anything [3], Nothing, Anything 4] :: type error tree_map double :: tree num -> tree num tree_map double (Node 10 (Node 20 EmptyTree EmptyTree) EmptyTree) Node 20 (Node 40 EmptyTree EmptyTree) EmptyTree my_const (Node 10 (Node True EmptyTree EmptyTree)) :: type error my_const 3 (1/0) 3 my_const (1/0) 3 numeric error: divide by 0

2. (10 points) Consider the following code in an Ada-like language. type aa is array(1..10) of integer; type bb is array(1..10) of integer; w: aa; x,y: bb; z: array(1..10) of integer; ... x := w; y := x; z := w; Which of the assignments would be legal if the language determined type equivalence using pure name equivalence? Which would be legal if the language determined type equivalence using structual equivalence?

   Under pure name equivalence:

   x := w; -- illegal y := x; -- legal z := w; -- illegal

   Under structural equivalence:

   x := w; -- legal y := x; -- legal z := w; -- legal

3. (10 points) The combinators S, K, and I are defined as follows: S f g x = f x (g x) K x y = x I x = x In fact we only need S and K, since SKK=I. Prove this equivalence. S K K x = K x (K x) (by the definition of S) = x (by the definition of K) I x = x (by the definition of I) hence by the principle of extensionality SKK = I

4. (10 points) Consider the following program in an Algol-like language. begin integer n; procedure p(j: integer); begin print(j,n); n := n+j; print(j,n); n := n+j; print(j,n); end procedure p; n := 5; p(n+2); print(n); end; What is the output when j is:
   1. passed by name?
   2. passed by value?

   passed by name:

   7 5 14 12 28 26 26 passed by value: 7 5 7 12 7 19 19

5. (10 points) Consider the following program in an Algol-like language. begin integer n; procedure p(j, k: integer); begin n := n+j+k; print(j,k,n); end procedure p; n := 2; p(n,n); end; What is the output when j and k are both:
   1. passed by value?
   2. passed by value result?
   3. passed by reference?
   In each case, if any variables are aliased, say so.

   passed by value:

   2 2 6 No aliasing in this case.

   passed by value result:

   2 2 6 No aliasing in this case.

   passed by reference

   6 6 6 Within p, j, k, and n are all aliased.

6. (10 points) Consider the following Simula program: begin class a; begin end a; a class b; begin end b; b class c; begin end c; ref(a) va; ref(b) vb; ref(c) vc; va :- new a; vb :- va; vc :- new c; vb :- vc; vc :- va qua c; In other words, class b is a subclass of a, and class c is a subclass of b. Which of the assignments will pass the compiler's type check, and which will fail? (Just write "yes" or "no" next to each assignment.)
   va :- new a; YES vb :- va; NO vc :- new c; YES vb :- vc; YES vc :- va qua c; YES

7. (10 points) Suppose that B1 and B2 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. | x y | x := 5. y := 6. B1 := [:temp | y := temp. x+y]. x := 0. Subsequently, one selects the following code and says "print it". What is printed? Explain your reasoning. | x y | x := 12. y := 15. B2 := [:temp | y := temp. x+y]. (B1 value: 3) + (B2 value: 4)

   19 is printed. When we evaluate the first chunk of code, a block is created as assigned to B1. This block is a closure, and captures the temporary variables x and y. At this point x is 0 (after the final assignment), and y is 6. Note in particular that we don't simply copy the current value of x (namely 12) at the time the block is created; rather, we capture the binding of x, so that the subsequent assignment of 0 affects the block. When we evaluate the second chunk of code, another block is created and assigned to B2. This captures the temporary variables for that code, also named x and y, but which refer to different storage locations. Here x is 12 and y is 15. When we evaluate (B1 value: 3), this assigns 3 to the y in the first block, and returns 0+3 which is 3. When we evaluate (B2 value: 4), this assigns 4 to the y in the second block, and returns 12+4 which is 16. So the final result is 19.

8. (26 points) Tacky but easy-to-grade true/false questions!
   1. Every piece of data in Simula is an object. False
   2. Every piece of data in Smalltalk-80 is an object. True
   3. Smalltalk-80 is statically typed. False
   4. Smalltalk-80 is type safe. True
   5. Ada is statically typed. True
   6. Ada is type safe. True
   7. Although Simula was a major inspiration for later languages that support abstract data types, classes in Simula don't hide their internal representations from outside clients. True
   8. The combinator graph reduction implementation used in Miranda has certain self-optimizing properties. For example, given a function definition such as f x = (4+5)*x when the function is first invoked, 4+5 will be evaluated, and thereafter the function will just compute 9*x when it is invoked. True
   9. Fortran is weakly typed. As an example of a type loophole, one can use the equivalence statement to direct the compiler to store a real and an integer in the same storage location, so that the real number can be accessed incorrectly as an integer and vice versa. True
   10. Algol-60 is statically typed. False (Procedures as parameters in Algol-60 don't contain any information about their arguments, so this must either be checked at runtime, or not checked.)
   11. In Smalltalk-80, control structures are implemented using ordinary message sending, often with blocks as arguments. True
   12. Assignment in Smalltalk is written as the infix operator := and is a message to class Variable. False (although it's not a bad idea)
   13. Since there are no reserved words in Fortran, IF=5 is a legal assignment statement. True

9. Which do you think is the most appropriate name for the temporary building next to Sieg?
   • The Chateau
   • The Trailer Court
   • The Projects
   • Lazowskaville
   • Other [what?]

   The results:

   • The Chateau = 8
   • The Trailer Court = 2
   • The Projects = 2
   • Lazowskaville = 6
   • Others = 10
   Write ins:
   • Trailer park
   • Recycled Beer Cans
   • ?
   • Sieg Annex
   • Bungalow
   • CS Homeless Shelter
   • TMA-2
   • Le Chateau
   • Da Ghetto
   • Weaverville