Guided Practice 7.2

Consider the computation of

(free-vars
  (make-app
    (make-lam
      'x
      (make-app
        'x
        (make-lam
          'y
          (make-app
            'x
            (make-app 'y 'z)))))
    (make-lam
      'y
      (make-app
        'u
        (make-lam
          'z
          (make-app
            'x
            (make-app 'y 'z)))))))

Which of the following will appear as calls to free-vars-in-subexp during this computation?

1. (free-vars-in-subexp (list 'z 'y) (make-app 'y 'z))
2. (free-vars-in-subexp (list 'x 'y) (make-app 'y 'z))
3. (free-vars-in-subexp (list 'y 'x) (make-app 'y 'z))
4. (free-vars-in-subexp (list 'x 'z) (make-app 'y 'z))

ANSWER

(make-app 'y 'z)

in this fredexp. The first is inside

(make-lam 'x
   ...  
  (make-lam 'y 
    ...)) 

(make-lam 'y  
  ... 
  (make-lam 'z 
    ...)) 

If we look at the code for free-vars-in-subexp, we see that the innermost lambda variable always occurs first. So the right answers are 1 (corresponding to the first occurrence with the lambda variables listed inside out) and 3 (corresponding to the second occurrence with the lambda variables listed inside out).