Subroutines and Control Abstraction

Prev: Composite Types Next: Data Abstraction and Object Orientation

Prev: Composite Types Next: Data Abstraction and Object Orientation

9.2 Check Your Understanding

1. What is a subroutine calling sequence? What does it do? What is meant by the subroutine prologue and epilogue?
2. How do calling sequences typically differ in older CISC and newer RISC instruction sets?
3. Describe how to maintain the static chain during a subroutine call.
4. What is a display? How does it differ from a static chain?
5. What are the purposes of the stack pointer and frame pointer registers? Why does a subroutine often need both?
6. Why do modern machines typically pass subroutine parameters in registers rather than on the stack?
7. Why do subroutine calling conventions often give the caller responsibility for saving half the registers and the callee responsibility for saving the other half?
8. If work can be done in either the caller or the callee, why do we typically prefer to do it in the callee?
9. Why do compilers typically allocate space for arguments in the stack, even when they pass them in registers?
10. List the optimizations that can be made to the subroutine calling sequence in important special cases, for example leaf routines.
11. How does an in-line subroutine differ from a macro?
12. Under what circumstances is it desirable to expand a subroutine in-line?

9.3 Check Your Understanding

13. What is the difference between formal and actual parameters?
14. Describe four common parameter-passing modes. How does a programmer choose which one to use when?
15. Explain the rationale for READONLY parameters in Modula-3.
16. What parameter mode is typically used in languages with a reference model of variables?
17. Describe the parameter modes of Ada. How do they differ from the modes of other modern languages?
18. Give an example in which it is useful to return a reference from a function in C++.
19. What is an r-value reference? Why might it be useful?
20. List three reasons why a language implementation might implement a parameter as a closure.
21. What is a conformant open array?
22. What are default parameters? How are they implemented?
23. What are named keyword parameters? Why are they useful?
24. Explain the value of variable-length argument lists. What distinguishes such lists in Java and C# from their counterparts in C and C++?
25. Describe three common mechanisms for specifying the return value of a function. What are their relative strengths and drawbacks?

9.4 Check Your Understanding

26. Describe three ways in which a language may allow programmers to declare new kinds of exceptions.
27. Explain why it is useful to define exceptions as classes in C++, Java, and C#.
28. Explain the behavior and purpose of a try ... finally construct.
29. Describe the algorithm used to identify an appropriate handler when an exception is thrown.
30. Explain how to implement exceptions in a way that incurs no cost in the common no-exception case.
31. How do the exception handlers of a functional language like ML differ from those of more conventional imperative languages?
32. Describe the operations that must be performed by the implicit handler for a subroutine when an exception propagates out of it.
33. Summarize the shortcomings of the setjmp and longjmp library routines in C.
34. What is a volatile variable in C? Under what circumstances is it useful?

9.5-9.6 Check Your Understanding

35. What was the first high-level programming language to provide coroutines?
36. What is the difference between a coroutine and a thread?
37. Why doesn’t the transfer library routine need to change the program counter when switching between coroutines?
38. Describe three alternative means of allocating coroutine stacks. What are their relative strengths and weaknesses?
39. What is a cactus stack? What is its purpose?
40. What is discrete event simulation? What is its connection with coroutines?
41. What is an event in the programming-language sense of the word?
42. Summarize the two main implementation strategies for events.
43. Explain the appeal of anonymous delegates in C# and anonymous inner classes in Java for handling events.

9.8 Exercises

1. Describe as many ways as you can in which functions in imperative programming languages differ from functions in mathematics.
2. Consider the following code in C++:

class string_map {
    string cached_key;
    string cached_val;
    const string complex_lookup(const string key);
        // body specified elsewhere
public:
    const string operator[](const string key) {
        if (key == cached_key) return cached_val;
        string rtn_val = complex_lookup(key);
        cached_key = key;
        cached_val = rtn_val;
        return rtn_val;
    }
};

Suppose that string_map::operator[] contains the only call to complex_lookup anywhere in the program. Explain why it would be unwise for the programmer to expand that call textually in-line and eliminate the separate function. 3. Using your favorite language and compiler, write a program that can tell the order in which certain subroutine parameters are evaluated. 4. Consider the following erroneous program in C:

void foo() {
    int i;
    printf("%d ", i++);
}
 
int main() {
    int j;
    for (j = 1; j <= 10; j++) foo();
}

Local variable i in subroutine foo is never initialized. On many systems, however, the program will display repeatable behavior, printing 0 1 2 3 4 5 6 7 8 9. Suggest an explanation. Also explain why the behavior on other systems might be different, or nondeterministic. 5. The standard calling sequence for the c. 1980 Digital VAX instruction set employed not only a stack pointer and frame pointer, but a separate arguments pointer as well. Under what circumstances might this separate pointer be useful? In other words, when might it be handy not to have to place arguments at statically known offsets from the frame pointer? 6. Write, in the language of your choice, a procedure or function that will have four different effects depending on whether arguments are passed by value, by reference, by value/result, or by name. 7. Consider an expression like a + b that is passed to a subroutine in Fortran. Is there any semantically meaningful difference between passing this expression as a reference to an unnamed temporary, as Fortran does, and passing it by value, as one might in Pascal? That is, can the programmer tell the difference between a parameter that is a value and a parameter that is a reference to a temporary? 8. Consider the following subroutine in Fortran 77:

subroutine shift(a, b, c)
integer a, b, c
a = b
b = c
end

Suppose we want to call shift(x, y, 0) but we do not want to change the value of y. Knowing that built-up expressions are passed as temporaries, we decide to call shift(x, y+0, 0). Our code works fine at first, but then, with some compilers, fails when we enable optimization. What is going on? What might we do instead? 9. In some implementations of Fortran IV, the following code would print a 3. Can you suggest an explanation? How do you suppose more recent Fortran implementations get around the problem?

c    main program
     call foo(2)
     print*, 2
     stop
     end
     subroutine foo(x)
          x = x + 1
          return
     end

10. Suppose you are writing a program in which all parameters must be passed by name. Can you write a subroutine that will swap the values of its actual parameters? Explain. Hint: consider mutually dependent parameters like i and A[i].
11. Can you write a swap routine in Java, or in any other language with only call-by-sharing parameters? What exactly should swap do in such a language? Hint: think about the distinction between the object to which a variable refers and the value contents of that object.
12. As noted in Section 9.3.1, out parameters in Ada 83 can be written by the callee but not read. In Ada 95 they can be both read and written, but they begin their life uninitialized. Why do you think the designers of Ada 95 made this change? Does it have any drawbacks?
13. Taking a cue from Ada, Swift provides an inout parameter mode. The language manual does not specify whether inout parameters are to be passed by reference or value-result. Write a program that determines the implementation used by your local Swift compiler.
14. Fields of packed records cannot be passed by reference in Pascal. Likewise, when passing a subrange variable by reference, Pascal requires that all possible values of the corresponding formal parameter be valid for the subrange:

type small = 1..100;
     R = record x, y : small; end;
     S = packed record x, y : small; end;
var a : 1..10;
     b : 1..1000;
     c : R;
     d : S;
procedure foo(var n : small);
begin
     n := 100;
     writeln(a);
end;
...
a := 2;
foo(b);       (* ok *)
foo(a);       (* static semantic error *)
foo(c.x);     (* ok *)
foo(d.x);     (* static semantic error *)

Using what you have learned about parameter-passing modes, explain these language restrictions. 15. Consider the following declaration in C:

double(*foo(double (*)(double, double[]), double)) (double, ...);

Describe in English the type of foo. 16. Does a program run faster when the programmer leaves optional parameters out of a subroutine call? Why or why not? 17. Why do you suppose that variable-length argument lists are so seldom supported by high-level programming languages? 18. Building on Exercise 6.35, show how to implement exceptions using call-with-current-continuation in Scheme. Model your syntax after the handler-case of Common Lisp. As in Exercise 6.35, you will probably need define-syntax and dynamic-wind. 19. Given what you have learned about the implementation of structured exceptions, describe how you might implement the nonlocal gotos of Pascal or the label parameters of Algol 60. Do you need to place any restrictions on how these features can be used? 20. Describe a plausible implementation of C++ destructors or Java try ... finally blocks. What code must the compiler generate, at what points in the program, to ensure that cleanup always occurs when leaving a scope? 21. Use threads to build support for true iterators in Java. Try to hide as much of the implementation as possible behind a reasonable interface. In particular, hide any uses of new Thread, thread.start, thread.join, wait, and notify inside implementations of routines named yield, to be called by an iterator, and in the standard Java Iterator interface routines, to be called in the body of a loop. Compare the performance of your iterators to that of the built-in iterator objects. It probably will not be good. Discuss any weaknesses you encounter in the abstraction facilities of the language. 22. In Common Lisp, multilevel returns use catch and throw; exception handling in the style of most other modern languages uses handler-case and error. Show that the distinction between these is mainly a matter of style rather than expressive power. In other words, show that each facility can be used to emulate the other. 23. Compile and run the program in Figure 9.6. Explain its behavior. Create a new version that behaves more predictably.

#include <signal.h>
#include <stdio.h>
#include <string.h>
 
char* days[7] = {"Sunday", "Monday", "Tuesday",
                "Wednesday", "Thursday", "Friday", "Saturday"};
char today[10];
 
void handler(int n) {
    printf(" %s\n", today);
}
 
int main() {
    signal(SIGTSTP, handler);                // ^Z at keyboard
    for (int n = 0; ; n++) {
        strcpy(today, days[n%7]);
    }
}

24. In C#, Java, or some other language with thread-based event handling, build a simple program around the pause button of Examples 9.51-9.54. Your program should open a small window containing a text field and two buttons, one labeled pause, the other labeled resume. It should then display an integer in the text field, starting with zero and counting up once per second. If the pause button is pressed, the count should suspend; if the resume button is pressed, it should continue.