Do exercise 21.1 on page 472. Don't worry about cases where the
given riddle predicate would go into infinite loops:
your more efficient predicate can do something different in those
cases.
Do exercise 21.2 on page 472.
Exercise 23.x1: The natural semantics for Language One has the property that for any AST of the language, let's say T, there exists some numerical value, v, such that one can prove T->v using the semantic rules. Not all collections of rules would have that property. Give an example of a simple modification to Language One's semantic rules that would eliminate this property (keeping the syntax unchanged), and give an example AST for which no value is provable using your modified rules. Your new semantics don't need to be useful.
Exercise 23.x2: The natural semantics for Language One has the property that for any AST of the language, let's say T, there never exist two different numerical values, v1 and v2, such that one can prove both T->v1 and T->v2 using the semantic rules. Not all collections of rules would have that property. Give an example of a simple modification to Language One's semantic rules that would eliminate this property (keeping the syntax unchanged), and give an example AST for which two different values are provable using your modified rules. Your new semantics don't need to be useful.
Exercise 23.x3: Prove that the natural semantics rules for Language One have the property that for any AST of the language, let's say T, there exists exactly one numerical value, v, such that one can prove T->v using the semantic rules.