Homework Three
Evaluation, List Processing, Using Defined Data Types

Comp210

Due: 98.Sep.22 (Wed.) in class

Will be accepted until Thurs. Noon, DH3102

  1. (3pts) During the evaluation of Scheme expressions, the Law of Function Application states that the expression (E0 E1 ... En) reduces to the expression (V0 V1 ... Vn), where Vi is the value of the expression Ei. It doesn't matter in which order these subexpressions are evaluated.¹

    When single-stepping with Donkey, you can see that it happens to evaluate the expressions Ei in left-to-right order: E1 to V1, then E2 to V2, ..., and finally En to Vn. Your task is to step through the evaluation of the following expressions using the same Law of Scheme, but when evaluating function-applications, evaluate sub-expressions in reverse (right-to-left) order. That is, first evaluate En to get Vn, then ..., then E1 to get V1, and finally E0 to get V0. This doesn't change the final value of the answer, of course. Your steps should resemble the sequence of expressions produced by Donkey during stepping.

    Note that if still evaluates its first expression first, and then only evaluates one of the two other expressions as needed. (It is a special form, since it doesn't follow the rule for ordinary function-application².) 

    1. (+ (* (+ 2 4) (+ 3 -4)) (+ (+ 4 7) (- 6 7)))
    2. (if (> 3 4) (/ 4 0) (if #t (+ 8 9) (/ 22 2)))
    3. ;; fib: num -> num
;; Calculate the nth Fibonacci number.
;;
(define fib
    (lambda (n)
        (if (< n 2)
            1
            (+ (fib (- n 1)) (fib (- n 2))))))
(fib 3)
    Show all steps except for (1) evaluating a value (to itself), and (2) evaluating a primitive-placeholder (to the function it stands for). Here is a sample problem/solution.

  2. (3 pts) 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 (cons 'a (cons 'b (cons 'c (cons 'a empty)))) = (cons 'a (cons 'b (cons 'c empty))). (The returned list can have the items in any order). As always, follow the program-design recipe from class, including the data definition of a list-of-symbols.

    Hint: First write a helper function 

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

  3. (4 pts) Do the book's exercise 6.4.1 (called 5.4.1 in the printed version), that is write the functions posn+, vec*, move. In order to internalize the data definition for vectors, you will need to type in the preceding code for make-vec, vec-x, vec-y; the corresponding functions for posns are built-in, as mentioned in exercise 6.3.3. In writing the later functions, be sure to re-use the earlier functions, rather than write the same code in several different functions.

    Since the data definition for vect are already given in the book, and posn is built-in to DrScheme, you don't need to repeat them, or give their templates. You will provide samples of the data, and test cases as usual. You can additionally run some graphical simulations if you want, using the function tracer as indicated. From "Languages" menu, "Set Library to..." the library teach/pingp-lib.ss (whose name is missing from the book). The name pingp-lib.ss will appear next to the Check Syntax button, indicating the library is loaded.

    (We will not develop all entire ping-pong game discussed in the book, though you are welcome to do this! Or, just play around with the drawing functions mentioned in the book.)

¹ Recall that additionally, the Law of Function Application goes on to say that the next step is to apply V0 (which had better be a function taking n arguments) to the values V1, ..., Vn. If V0 is a lambda-value, as opposed to a primitive, this means further work. (back)

² Why bother making if a special form? At first this seems to be an unnecessary complication -- just evaluate its three arguments, and then pass those values off to the actual function. That is almost, but not quite, satisfactory; consider the following: 

(define average
  (lambda (n sum)
    (if (not (zero? n))
        (/ sum n)
        1)))
Certainly, once this is written, I don't expect (average 0 0) to cause a divide-by-zero error! Yet if if weren't special, the Law would require evaluating all three arguments before actually invoking the function.

By the way, it is a good programming habit that, any time you write /, a little flag goes up in your mind, wondering whether it's necessary to guard against the denominator being zero.

As for this particular function average, should the average really be considered 1? This is certainly arguable. But 1 is the answer used in baseball: at the beginning of the season, everybody's batting-average is 1.000! (back)