Here are nine fun problems. As with the previous assignment, generate a hardcopy pdf to turn in — Wednesday, November 19, for grads and Thursday, November 20 for undergrads.

Readings: [Scott], Chapters 3 and 6. Consider the "Check Your Understanding" questions as part of your reading assignment (that is, solve as many as you can but do not turn in any solutions).

1. Give an example of a program in C that would not work correctly if local variables were allocated in static storage as opposed to the stack.
2. Give three examples from C which a variable is live but not in scope.
3. Consider the following pseudocode:

       var x = 100;
       function set_x(n) {x = n}
       function print_x {write_integer(x);}
       function first {set_x(1); print_x();}
       function second {var x; set_x(2); print_x();}
       set_x(0);
       first();
       print_x();
       second();
       print_x();
   

   What does this program print if the language uses static scoping? What does it print with dynamic scoping? Why?
4. Consider the following pseudocode:

       var x = 100;
       function set_x(n) {x = n}
       function print_x {write_integer(x);}
       function foo(S, P, n) {
           var x;
           if (n == 1 or n == 3) {set_x(n);} else {S(n);}
           if (n == 1 or n == 2) {print_x();} else {P();}
       }
       set_x(0); foo(set_x, print_x, 1); print_x();
       set_x(0); foo(set_x, print_x, 2); print_x();
       set_x(0); foo(set_x, print_x, 3); print_x();
       set_x(0); foo(set_x, print_x, 4); print_x();
   

   Assume that the language uses dynamic scoping. What does the program print if the language uses shallow binding? What does it print with deep binding? Why?
5. Translate the following expression into postfix and prefix notation:

       (-b + sqrt(4 × a × c)) / (2 × a)
   

   Do you need a special symbol for unary negation?
6. In Lisp, most of the arithmetic operators are defined to take two or more arguments, rather than strictly two. Thus (* 2 3 4 5) evaluates to 120, and (– 16 9 4) evaluates to 3. Show that parentheses are necessary to disambiguate arithmetic expressions in Lisp (in other words, give an example of an expression whose meaning is unclear when parentheses are removed). Why then, on page 236 of [Scott], does it say "Issues of precedence and associativity do not arise with prefix or postfix notation"? Reword this claim to make explicit the hidden assumption.
7. Recall the "blank line" example from Chapter 6 in [Scott]. here written in Modula-2:

       LOOP
           line := ReadLine;
           IF AllBlanks(line) THEN EXIT END;
           ConsumeLine(line)
       END;
   

   Show how you might accomplish the same task using a while or repeat loop, if midtest loops were not available. (Hint: one alternative duplicates part of the code; another introduces a Boolean flag variable.) How do these alternatives compare to the midtest version?
8. Rubin used the following example (rewritten here in C) to argue in favor of a goto statement:

       int first_zero_row = -1; /* none */
       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: ;
       }
   

   The intent of the code is to find the first all-zero row, if any, of an n × n matrix. Do you find the example convincing? Is there a good structured alternative in C? In any language? Undergraduates only: Give answers in the form of a three page paper. Include a brief abstract, a good introductory section, a background section describing views on the goto statement throughout history, a beefy section analyzing alternatives to Rubin's problem, and a good concluding section.
9. Write a tail-recursive function to compute the factorial of an integer in ML, JavaScript, and Ruby.