Chapter 7 Recursive Data Types182
according to the Environment Model and the Substitution Model, indicating where
the rule for each case of the recursive definitions of eval.;/andŒWD] or substitution
is first used. Compare the number of arithmetic operations and variable lookups.
(b)Describe an example along the lines of part (a) where the Environment Model
would perform 6 fewer multiplications than the Substitution model. You neednot
carry out the evaluations.
(c)Describe an example along the lines of part (a) where the Substitution Model
would perform 6 fewer multiplications than the Environment model. You neednot
carry out the evaluations.
Homework Problems
Problem 7.14. (a)Give a recursive definition of a function erase.e/that erases all
the symbols ine 2 Aexp but the brackets. For example
erase.[ [ 3 [xx] ]C[ [ 2 x]C 1 ] ]/D[ [ [ ] ] [ [ 2 x]C 1 ] ]:(b)Prove that erase.e/ 2 RecMatch for alle 2 Aexp.(c)Give an example of a small strings 2 RecMatch such that[s]¤erase.e/for
anye 2 Aexp.