Comp210
Due: 98.Sep.22 (Wed.) in class
Will be accepted until Thurs. Noon, DH3102
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².)
(+ (* (+ 2 4) (+ 3 -4)) (+ (+ 4 7) (- 6 7)))
(if (> 3 4) (/ 4 0) (if #t (+ 8 9) (/ 22 2)))
;; fib: num -> num ;; Calculate the nth Fibonacci number. ;; (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))) (fib 3)
(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. ;;
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 posn
s 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.)
²
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)