Princeton University
Computer Science Dept.

Computer Science 441
Programming Languages
Fall 1998

Assignment 5
Due Tuesday, 10/27/98
  1. In early FORTRANs (i.e., I to 77) there was usually no checking of code for recursive calls. Instead at execution time the recursive call was made, but the program later fell into an infinite loop. Based on your knowledge of the implementation of subroutine calls in FORTRAN, explain why this happens. Design a mechanism which would allow the program to detect such recursive calls and abort. Your mechanism should also detect mutually recursive or indirectly recursive calls. (It is sufficient to have a run-time rather than compile-time mechanism.)

  2. Do problem 23 on page 244 of Louden.

  3. A block is like a procedure body which occurs in-line in a program. That is, it is composed of a series of declarations followed by some executable code. However it may not be called like a procedure, it is only executed when the program counter enters the first statement of the block. Please explain why the static and dynamic links have the same values for blocks.

  4. Please do problem 26 on page 246 of the text.

  5. In class we discussed the use of a run-time stack of activation records for procedure calls in block-structured languages. In the interpreter you wrote last week there was no explicit use of a run-time stack. Your (recursive) interpreter for PCF provides similar support for activation records (though PCF is simpler than block-structured languages because there are no local variables and only one parameter for each function call). Explain how your interpreter provides a stack-like support for activation records by explaining how the environment changes during the evaluation of the following expression:

    	((if is_zero(((fn y => pred y)1)) then succ else pred)
		((fn y => (pred(pred y)))8))
  6. Write an ML function which converts a string of digits into an integer. The conversion should interpret the digits as being in base b, where b is the smallest base less than or equal to 10 such that a conversion is possible. Your function should use exceptions to "restart" the onversion with the next higher base if the current conversion encounters an "illegal" digit. If the string is not convertible to an integer for any base less than or equal to 10 then your function should raise an exception. For example: 
    - convert "301";
val it = 49 : int
-convert "89";
val it = 89: int
-convert "1234";
val it = 194 : int
- convert "11111111";
val it = 255 : int
-convert "90A3";

uncaught exception exception Range
    Note that the conversion bases were 4, 10, 5, and 2, respectively.

    b. Compare this function with a similar function written without using exceptions. (You don't have to write it - just talk about it's general structure!) Comment on clarity and efficiency at least.