Guided Practice 7.3: Solution

Consider the computation of

(program-all-defined?
    (list
     (make-def 'f1 (list 'x) (make-appexp 'f2 (list (make-varexp 'x))))
     (make-def 'f2 (list 'x 'y) (make-appexp 'f2
                                             (list (make-varexp 'z)
                                                   (make-varexp 'y))))
     (make-def 'f3 (list 'x 'y 'z)
               (make-appexp 'f1 (list (make-appexp 'f2
                                                   (list (make-varexp 'z)
                                                         (make-varexp 'y)))
                                   (make-varexp 'x))))))

Which of the following will appear as calls during this computation?

  1. (exp-all-defined? (make-varexp 'z) (list 'f1 'x))
  2. (exp-all-defined? (make-varexp 'z) (list 'f3 'x 'y 'z 'f2 'f1))
  3. (exp-all-defined? (make-varexp 'z) (list 'f2 'x 'y 'z 'f1))
  4. (exp-all-defined? (make-varexp 'z) (list 'f3 'x 'y 'f1 'f2 'z))

ANSWER

Answer: There are two occurrences of (make-varexp 'z) in this program-- one in the definition of f2 and one in the definition of definition of f3.

According to the definition of defs-all-defined?, the variables appear in vars in the following order:

  1. the name of the function being defined
  2. the arguments of the function being defined
  3. the functions defined above the current one, in reverse order.
However, the invariant does not require that the variables appear in this order.

Answer (1) does not occur and does not satisfy the invariant, because z does not occur in the definition of f1.

Answer (2) occurs for the use of z in f3. It satisfies the invariant.

Answer (3) does not occur and does not satisfy the invariant. There is no occurrence of z for which these are the available variables.

Answer (4) does not occur, but it does satisfy the invariant. These are exactly the variables that are available for the occurrence of z in f3, but this is not the order in which the variables are listed in the algorithm (compare with answer (2)).

Last modified: Mon Oct 2 12:40:51 Eastern Daylight Time 2017