Cpt S 355 Homework Assignment 4

Assigned: April 11, 2005

Due: April 25, 2005 in class

All answers except drawings must be typed!

The textbook problem sets for the later chapters in the book are terrific review for the course. This assignment covers some of the most important topics discussed in the course, but the other problems are well worth your attention. You should consider each of the problems in Chapters 8-14 that touch in any way on things we have covered and try to frame for yourself the issues that are raised. If you can do this you will have a very solid understanding of these topics.

Chapter 8

1. Consider the following python code:

   def twice(f,x):
      try:
         return f(f(x))
      except "oops", v: 
         return v
   def pred(x):
      if x==0:
         raise "oops", x
      else:
         return x-1
   def dumb(x):
      raise "oops", x
   def smart(x):
      try:
         return 1+pred(x)
      except "oops", v:
         return 1

• twice(pred(1))
• twice(dumb(1))
• twice(smart(0))
For each case explain what exception(s) is/are raised and where it/they are handled. (Note: you can easily copy the code into a file and execute it; this, of course, is not the object of the exercise. Do it mentally first then check by executing it.)

2. Consider the following python code:

   def hd(l):
      if null(l): raise "hd"
      return l[0]
   def tl(l):
      if null(l): raise "tl"
      return l[1:]
   def g(l):
      try:
         return hd(l)+tl(l)
      except "hd":
         return []

3. Problem 8.3 from the textbook.

Chapter 9

4. Consider the following ML structure that defines a polymorphic abstract type for stacks:

   structure Stack = struct
      datatype 'a stack = Empty | Push of 'a * 'a stack
      exception EmptyStack
      fun top Empty = raise EmptyStack
        | top (Push(x,s)) = x
      fun pop Empty = raise EmptyStack
        | pop (Push(x,s)) = s
      fun push (x,s) = Push (x,s)
   end (* Stack *)

   functor StackF(S: sig type t end) = struct
      datatype stack = Empty | Push of S.t * stack
      exception EmptyStack
      fun top Empty = raise EmptyStack
        | top (Push(x,s)) = x
      fun pop Empty = raise EmptyStack
        | pop (Push(x,s)) = s
      fun push (x,s) = Push (x,s)
   end (* Stack *)

   structure IntStack = StackF(struct type t = int end)

Chapter 12

5. Problem 12.1 -- objects on the stack, and review of object implementation issues.

6. Problem 12.7 parts (a) and (b) -- You may want to do the experiment to confirm your understanding of the language. If you do, please say what compiler you used as well as stating the results you obtained.

7. Problem 12.11 -- Use Figure 12.3 as a model for how to draw the diagrams for part (a).

8. Note that the parenthetical remark in the third-to-last paragraph on p. 380 is not correct. I know of one class of counterexamples: (float) 1 will produce the floating point representation of the value 1, not treat the integer representation representation of 1 as a float. What would you have to do if you wanted to treat the bit pattern of an int as a float?

Chapter 13

9. Problem 13.2 (b) and (c)

10. Problem 13.6 (c) - Hint: this not really a Java question at all; refer to Chapter 2.

11. Problem 13.7 (a) and (b)

Chapter 14

12. Problem 14.1. Example 14.2 referred to by the problem is on pp. 438-439, but to understand it you must also read example 14.1 on pp. 436-437.