CSE 505 Midterm

November 4, 1994

50 minutes, open notes, 110 points total
  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..] my_map double :: my_map (my_const False) [] :: my_const :: I 3 :: Anything 3 :: [I 3, B False, Anything [3], Nothing, Anything 4] :: tree_map double :: tree_map double (Node 10 (Node 20 EmptyTree EmptyTree) EmptyTree) my_const (Node 10 (Node True EmptyTree EmptyTree)) :: my_const 3 (1/0) my_const (1/0) 3

  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?

  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.

  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?

  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.

  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.)

  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)

  8. (26 points) Tacky but easy-to-grade true/false questions!

    1. Every piece of data in Simula is an object.
    2. Every piece of data in Smalltalk-80 is an object.
    3. Smalltalk-80 is statically typed.
    4. Smalltalk-80 is type safe.
    5. Ada is statically typed.
    6. Ada is type safe.
    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.
    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.
    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.
    10. Algol-60 is statically typed.
    11. In Smalltalk-80, control structures are implemented using ordinary message sending, often with blocks as arguments.
    12. Assignment in Smalltalk is written as the infix operator := and is a message to class Variable.
    13. Since there are no reserved words in Fortran, IF=5 is a legal assignment statement.

  9. Which do you think is the most appropriate name for the temporary building next to Sieg?