Homework Three
Evaluation and Binary Numbers

These exercises should be done on Owlnet using Donkey and Scheme.

1. During the evaluation of Scheme expressions, the Law of Function Application states that the expression (E1 E2 ... En) reduces to the expression (V1 V2 ... Vn) where Vi is the value of the expression Ei. (The Law of Function Application also describes how to substitute V2, ..., Vn into V1 as the next step of evaluation.)

DrScheme and Donkey evaluate the expressions Ei in left to right order, E1, E2, ..., En. Your task is to step through the evaluation of the following expressions using the reduction rules described in class (and used by Donkey). However, you should reverse the order of evaluation for the law of function application. You should evaluate the expressions Ei in the right to left order, En, ..., E2, E1. Your answers should resemble the sequence of expressions produced by Donkey during stepping.

1. (+ (* (+ 2 4) (+ 3 -4)) (+ (+ 4 7) (- 6 7)))

2. (if (> 3 4) (/ 4 0) (if #t (+ 8 9) (/ 22 2)))

3. (define fib
       (lambda (n)
           (if (< n 2)
               1
               (+ (fib (- n 1)) (fib (- n 2))))))
   (fib 3)

2. Write the program remove-duplicates, which accepts a list of symbols with possible duplicates and returns a list without duplicate entrees. For example, (remove-duplicates (list 'a 'b 'c 'a)) = (list 'a 'b 'c). (the exact order of the result isn't important). As always, follow the program-design recipe from class.

   Hint: First write a helper function

   ;; remove: symbol, list-of-symbols --> list-of-symbols
   ;; (remove victim los) returns a list like los,
   ;;   but with all occurrences of victim are removed.
   ;;
   

3. Write a Scheme function that, given two non-negative natural numbers, n and m, computes n to the power m. As usual, include your data definition, program template, completed program and test data. Your function should not use the equivalent Scheme built-in function expt. However, you may use the multiplication (*) operation.
4. The following exercises are based on exercises from the book's chapter 5. To get the already-defined structure posn into Dr.Scheme, find the "Languages" menu and select "Select Library...", and request the library ~comp210/lib/teach/pingp-lib.ss. (The name pingp-lib.ss should appear next to the Check Syntax button, indicating success.)
   1. Exercise 5.16: define posn+ and posn*.
   2. Exercise 5.17: define mover.
   3. Exercise 5.18: Use define-struct to make a ball structure. Of the four indicated direction and speed functions, write one of {ns-direction,ew-direction}, and write one of {ns-speed, ew-speed}. One test case per function is sufficient. You don't need to provide a description of these four functions (their names are self-explanatory), but you do still need to provide the contract, e.g. ns-speed: ball --> posn.
   4. Exercise 5.19: define move.
   You will provide test cases as usual. You can additionally run some graphical simulations if you want, using the functions tracer and trace-ball as indicated.

   For further fun: You can develop and run examples as discussed in the book about drawing shapes, playing hangman, and playing a complete pingpong game.