Computer Science 3675
Section 001
Fall 2006
Solutions to practice questions for quiz 4

1. What is the purpose of the static link in a frame in the run-time stack?

   The static link is used to find the frame where a function's nonlocal bindings are found.

2. What is the purpose of the dynamic link in a frame in the run-time stack?

   The dynamic link is used to find the frame below the current frame, which is necessary to pop the run-time stack.

3. What information is stored in a function closure?

   A function closure holds a function (given by the code that performs the function) and a pointer to the frame where the nonlocal bindings of that function can be found, and that will be installed as the static link when the function runs.

4. In C, you are not allowed to write a function inside another function. But C does allow you to treat a function as a value. Does C need to use function closures?

   Since a C function cannot be embedded in another function, it needs no static link, so there is no need for function closures.

5. What is one important motivation for including exception handling in a programming language?

   Here are some reasonable answers.

   1. Exception handling moves error handling code out of the way of the main program logic, making programs easier to read.
   2. Exception handling makes it possible to recover from errors that are made in parts of a program that do not perform careful error checking.
   3. Exception handling makes error checking easier, and requiring fewer lines of a program.

6. Are backtracking and exception handling the same thing? For example, can you use the exception handling mechanism of Java to do backtracking?

   Backtracking and exception handling are not the same thing. Exception handling can be done using a single run-time stack. Once a subprogram returns, any exception-handling control frames that it created are gone. Backtracking requires the run-time stack to be copied because a backtrack control frame can remain in effect even after the subprogram that created it has returned. That allows a subprogram to resume, and make an alternate choice, later, even after it has already given one answer.

7. Using backtracking, write a Cinnameg program fragment that will print all solutions (x,y) to equation xy - 2x² + y = 10, where x and y are both integers in the range 0,...,100. Do not use a loop or recursion. Your program fragment can fail when it is done.

       Let x = each [0,...,100].
       Let y = each [0,...,100].
       {x*y - 2*x^2 + y == 10}
       Writeln[$(x,y)].
       {false}  %% force to get next solution
     

8. True or false.

   1. When a variable occurs in a logic programming goal, the interpreter is being asked whether that goal holds for all values of the variable.

      False. The interpreter is being asked whether the goal holds for some values of the variables, and, if so, for which values?

   2. In logic programming, a variable in an axiom might be used as an input variable sometimes, and as an output variable at other times, when computation uses that axiom.

      True. The symmetry of unification makes it possible for a given parameter sometimes to represent information coming into a predicate, and sometimes to provide information coming out.

9. Unification is a form of pattern matching. Which of the following is not a characteristic of unification?

   1. Unification never changes the binding of a bound variable.
   2. Unification is symmetric; unifying A with B has exactly the same effect as unifying B with A.
   3. Unification is very slow, and is only used rarely during computations of logic programs.
   4. Unification can bind unbound variables.

   (Unification is a fundamental tool of logic programming, and is used at every step. It generally works very quickly. The more expensive aspect of logic programming is backtracking.)