25 Points
Due: 11/1 at the start of class

Note: The following instructions are repeated from the Homework Dates/Guidelines page:

Your solutions for each homework assignment must be prepared with a word processor (e.g., LaTeX or Word), and are due at the beginning of class on the due date specified unless otherwise noted on the assignment itself.

Note that all homework problems taken from the text are in the Problem Sets. Do not turn in solutions to Review Questions by mistake!

Complete each of the following problems:

1. From Chapter 7 (pp. 306-307 of 5E text, in 4E, Chapter 6, p. 285):
   1. Problem 12
   2. Draw the parse tree for the expression in 10.c according to your grammar. Annotate your parse tree by including numbers (and circling them) by each operator in the tree indicating the order of evaluation. There is no need to number the parentheses in the expression.

   3. Chapter 7, Problem 14 (p. 307 of 5E text, in 4E: Chapter 6, Problem 14 on p. 285)

   4. In homework assignment 4, you wrote a Scheme function that removed all occurences of an atom from a list, no matter where or how deeply within the list.

      1. Write an equivalent Prolog predicate called remove_everwhere that takes three arguments:

             remove_everywhere( Value, The_List, List_Without_Value ) :-
                 /* Your implementation should ensure that List_Without_Value
                    is the same as The_List, with all occurrences of Value removed, no
                    matter how deeply nested. */
                 .
         

      2. Try out your predicate to ensure it works correctly. Then try it out with this goal and place the result in your homework solution:

             ?- remove_everywhere(99, List, [a,[b,[c]],d]), fail.
         

         Describe what result your predicate produces and explain its behavior in this case.