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: Using the natural semantics for Language One,
show how the conclusion
plus(const(2),times(const(3),const(4)))→14 would be
derived. That is, what are the immediately preceding premises from
which a rule allows this conclusion to be derived? And for any of
those immediately preceding premises that is itself a consequence of
applying some rule to earlier premises, what are those? (You can
structure this as a tree, as demonstrated in class.)
Exercise 23.x2: Using the natural semantics for Language Two,
show how the conclusion
⟨let(x,const(2),times(var(x),const(4))), [ ]⟩→8 would be
derived. That is, what are the immediately preceding premises from
which a rule allows this conclusion to be derived? And for any of
those immediately preceding premises that is itself a consequence of
applying some rule to earlier premises, what are those? (You can
structure this as a tree, as demonstrated in class.)
Exercise 23.x3: The natural semantics rules for Language Two
make use of an auxilliary function lookup. This can be
eliminated if two different rules are used for var
expressions. One of these rules is
⟨var(x), bind(x,v)::C⟩→v.
What is the other rule? (Hint 1: Look at the Prolog rules for the
lookup predicate. Hint 2: The premises listed above
the line in a natural semantics rule do not all need to contain the
→ symbol.)