Control Flow

Prev: Target Machine Architecture Next: Type Systems

Prev: Target Machine Architecture Next: Type Systems

6.1.1-6.1.2 Check Your Understanding

1. Name eight major categories of control-flow mechanisms.
2. What distinguishes operators from other sorts of functions?
3. Explain the difference between prefix, infix, and postfix notation. What is Cambridge Polish notation? Name two programming languages that use postfix notation.
4. Why don’t issues of associativity and precedence arise in Postscript or Forth?
5. What does it mean for an expression to be referentially transparent?
6. What is the difference between a value model of variables and a reference model of variables? Why is the distinction important?
7. What is an l-value? An r-value?
8. Why is the distinction between mutable and immutable values important in the implementation of a language with a reference model of variables?
9. Define orthogonality in the context of programming language design.
10. What is the difference between a statement and an expression? What does it mean for a language to be expression-oriented?
11. What are the advantages of updating a variable with an assignment operator, rather than with a regular assignment in which the variable appears on both the left- and right-hand sides?

6.1.3-6.1.5 Check Your Understanding

12. Given the ability to assign a value into a variable, why is it useful to be able to specify an initial value?
13. What are aggregates? Why are they useful?
14. Explain the notion of definite assignment in Java and C#.
15. Why is it generally expensive to catch all uses of uninitialized variables at run time?
16. Why is it impossible to catch all uses of uninitialized variables at compile time?
17. Why do most languages leave unspecified the order in which the arguments of an operator or function are evaluated?
18. What is short-circuit Boolean evaluation? Why is it useful?

6.2-6.4 Check Your Understanding

19. List the principal uses of goto, and the structured alternatives to each.
20. Explain the distinction between exceptions and multilevel returns.
21. What are continuations? What other language features do they subsume?
22. Why is sequencing a comparatively unimportant form of control flow in Lisp?
23. Explain why it may sometimes be useful for a function to have side effects.
24. Describe the jump code implementation of short-circuit Boolean evaluation.
25. Why do imperative languages commonly provide a case or switch statement in addition to if ... then ... else?
26. Describe three different search strategies that might be employed in the implementation of a case statement, and the circumstances in which each would be desirable.
27. Explain the use of break to terminate the arms of a C switch statement, and the behavior that arises if a break is accidentally omitted.

6.5 Check Your Understanding

28. Describe three subtleties in the implementation of enumeration-controlled loops.
29. Why do most languages not allow the bounds or increment of an enumeration-controlled loop to be floating-point numbers?
30. Why do many languages require the step size of an enumeration-controlled loop to be a compile-time constant?
31. Describe the “iteration count” loop implementation. What problem(s) does it solve?
32. What are the advantages of making an index variable local to the loop it controls?
33. Does C have enumeration-controlled loops? Explain.
34. What is a collection, a container instance?
35. Explain the difference between true iterators and iterator objects.
36. Cite two advantages of iterator objects over the use of programming conventions in a language like C.
37. Describe the approach to iteration typically employed in languages with first-class functions.
38. Give an example in which a mid-test loop results in more elegant code than does a pretest or post-test loop.

6.6-6.7 Check Your Understanding

39. What is a tail-recursive function? Why is tail recursion important?
40. Explain the difference between applicative- and normal-order evaluation of expressions. Under what circumstances is each desirable?
41. What is lazy evaluation? What are promises? What is memoization?
42. Give two reasons why lazy evaluation may be desirable.
43. Name a language in which parameters are always evaluated lazily.
44. Give two reasons why a programmer might sometimes want control flow to be nondeterministic.

6.9 Exercises

1. We noted in Section 6.1.1 that most binary arithmetic operators are left-associative in most programming languages. In Section 6.1.4, however, we also noted that most compilers are free to evaluate the operands of a binary operator in either order. Are these statements contradictory? Why or why not?
2. As noted in Figure 6.1, Fortran and Pascal give unary and binary minus the same level of precedence. Is this likely to lead to nonintuitive evaluations of certain expressions? Why or why not?
3. In Example 6.9 we described a common error in Pascal programs caused by the fact that and and or have precedence comparable to that of the arithmetic operators. Show how a similar problem can arise in the stream-based I/O of C++.
4. Translate the following expression into postfix and prefix notation: [-b + sqrt(b * b - 4 * a * c)] / (2 * a). Do you need a special symbol for unary negation?
5. In Lisp, most arithmetic operators take two or more arguments, rather than strictly two. Show that parentheses are necessary to disambiguate arithmetic expressions in Lisp. Reword the claim that precedence and associativity do not arise with prefix or postfix notation to make explicit the hidden assumption.
6. Verify the claim from Example 6.33 that for certain values of x, (0.1 + x) * 10.0 and 1.0 + (x * 10.0) can differ by as much as 25%, even when 0.1 and x are of the same magnitude.
7. Is &(&i) ever valid in C? Explain.
8. Languages that employ a reference model of variables also tend to employ automatic garbage collection. Is this more than a coincidence? Explain.
9. C uses = for assignment and == for equality. The language designers argued that assignment is about twice as frequent, so the operator should be half as long. What do you think of this rationale?
10. Consider a language implementation in which we wish to catch every use of an uninitialized variable. Describe a plausible allocation strategy for initialization flags, and show the assembly-language sequences required for dynamic checks, with and without distinguished sentinel values.
11. Write an attribute grammar, based on the following CFG, that accumulates jump code for Boolean expressions with short-circuiting into a synthesized attribute code of condition, and then uses this attribute to generate code for if statements.

stmt -> if condition then stmt else stmt
      -> other_stmt
condition -> c_term | condition or c_term
c_term -> c_factor | c_term and c_factor
c_factor -> ident relation ident | ( condition ) | not ( condition )
relation -> < | <= | = | <> | > | >=

12. Describe a plausible scenario in which a programmer might wish to avoid short-circuit evaluation of a Boolean expression.
13. Neither Algol 60 nor Algol 68 employs short-circuit evaluation for Boolean expressions, but both allow if ... then ... else as an expression. Show how to use that construct to achieve the effect of short-circuit evaluation.
14. Consider the following expression in C: a/b > 0 && b/a > 0. What happens when a is zero? When b is zero? Would it make sense to design a language in which this expression is guaranteed to evaluate to false when either a or b, but not both, is zero? Explain.
15. Compare the alternatives used for missing values in case statements: do nothing, raise a run-time error, or require full coverage statically. Which do you prefer, and why?
16. The equivalence of for and while loops is not precise. Give an example in which it breaks down. Hint: think about continue.
17. Write the equivalent of Figure 6.5 in C#, Python, or Ruby. Write a second version that performs an in-order enumeration rather than preorder.
18. Revise the algorithm of Figure 6.6 so that it performs an in-order enumeration rather than preorder.
19. Write a C++ preorder iterator to supply tree nodes to the loop in Example 6.69. You may assume the data in a tree node is always an int.
20. Write code for the tree_iter type and the ti_create, ti_done, ti_next, ti_val, and ti_delete functions employed in Example 6.73.
21. Write, in C#, Python, or Ruby, an iterator that yields:

• all permutations of the integers 1..n
• all combinations of k integers from the range 1..n, where 0 <= k <= n

22. Use iterators to construct a program that outputs all structurally distinct binary trees of n nodes. The five structurally distinct trees of three nodes should be representable in dotted parenthesized form such as (((.).).) and (.(.(.))).
23. Build true iterators in Java using threads. Hide as much of the implementation as possible behind a reasonable interface. Compare the cost to standard Java iterator objects.
24. In an expression-oriented language such as Algol 68 or Lisp, a while or do loop has a value as an expression. How should this value be determined? Is it useful? What should happen if the body never executes?
25. Show how to rewrite a mid-test loop that looks for blank lines using only while or do/repeat, if mid-test loops were not available. Compare the result.
26. Rubin used the following C code to argue in favor of goto:

int first_zero_row = -1;
int i, j;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (A[i][j]) goto next;
    }
    first_zero_row = i;
    break;
next: ;
}

Do you find the example convincing? Is there a good structured alternative in C? In any language? 27. Write code for binary search in your favorite imperative language. What loop construct(s) did you find most useful? 28. Show the loop invariant(s) for your solution to the previous exercise. 29. If you know automata theory or recursive function theory, explain why while loops are strictly more powerful than Ada-style for loops. 30. Show how to calculate the number of iterations of a general Fortran 90-style do loop in assembler-like notation. Your code should work for all valid bounds and step sizes and avoid overflow. 31. Write a tail-recursive function in Scheme or ML to compute n!. 32. Is it possible to write a tail-recursive version of classic quicksort? Why or why not? 33. Give an example in C in which an in-line subroutine may be significantly faster than a functionally equivalent macro. Give another in which the macro is likely to be faster. 34. Use lazy evaluation, delay and force, to implement iterator objects in Scheme. Provide uptoby and for-iter so that expressions such as the following work in O(1) intrinsic space:

(for-iter (lambda (e) (display e) (newline)) (uptoby 10 50 3))

35. Use call-with-current-continuation, call/cc, to implement:

• multilevel returns, in the style of Common Lisp catch and throw
• true iterators in Scheme, with an iterator macro and a yield function

36. 6.36-6.40 In More Depth.