The goals of this lab are to review the design recipes for defining functions and for defining data as well as examine the behavior of the DrRacket programs that contain loops and programs that compute with inexact numbers. Additionally, we will assign the homework partners and introduce the environment for managing your projects in an svn repository.
Working in DrRacket you may have seen some strange results. Here are some examples:
> (sqrt 2) #i1.4142135623730951 > pi #i3.141592653589793 > (sqrt 10) #i3.1622776601683795
Furthermore,
> (equal? 1.4142135623730951 (sqrt 2)) false > (/ 10 3) 3.3 > (equal? 3.3 (/ 10 3)) true (equal? (/ 10 3) (/ 100 30)) true
Well, the computer is right. Square root of 2 is an irrational number. When we compute (/ 10 3), DrRacket shows a bar over the second digit 3 in the result, indicating the infinite expansion 3.3333333.... The first of these represents inexact numbers. The computer has a finite space in its memory for every numerical value that is saved, and so can remember only certain number of decimal digits of the exact value of the number. So, the value 1.4142135623730951 is only an approximation of the value of (sqrt 2). DrRacket recognizes this and marks the inexact numbers in a special way. The second number is a rational number, and DrRacket remembers that it is an exact fraction computed by dividing 10 by 3. It converts it to the approximate decimal value only when needed in some computation.
Why does this matter? Computers deal with large amounts of data. Large amount of inexact data can lead to large accumulated errors or inaccuracies, and the programmer needs be aware of this. The field of numerical mathamatics studies the compound effects of inaccuracies in approximations and helps in understanding where the problems lie.
Here is a simple example.
;; a list of a few inexact numbers
(define NUM-LIST
(list #i+9e23
#i+8e23
#i-1e23
#i+6e23))
(define (sum-right alist)
(foldr + 0 alist))
(define (sum-left alist)
(foldl + 0 alist))
;; one way to add all numbers
(sum-right NUM-LIST)
;; another way to add all numbers
(sum-left NUM-LIST)
Run this and observe the results. Actually, both results are inaccurate! Try the following, and reson about the numbers yourself, to see what the correct result should be.
;; adding the large numbers first (+ (+ #i+9e23 #i+8e23) #i+6e23) ;; then subtracting the small one => correct result (+ (+ (+ #i+9e23 #i+8e23) #i+6e23) #i-1e23)
We have two problems here. The inaccuracies in compound computations with inexact numbers are inevitable and we will not solve this problem here - we just want to make sure you are aware of it when writing your own programs. The second problem can be illustrated as follows. Run the stepper for the following two problems:
;; one way to add all numbers (sum-right (list 1 2 3 4 5 6)) ;; another way to add all numbers (sum-left (list 1 2 3 4 5 6))
Notice the difference. The definition of foldr and foldl shows how the computation proceeds:
;; foldr: [X Y -> Y] Y [Listof X] -> Y ;; (foldr f base (list x1 x2 ... xn)) = (f x1 (f x2 ... (f xn base)...)) (define (foldr f base alox ...) ;; foldl: [X Y -> Y Y [Listof X] -> Y ;; (foldl f base (list x1 x2 ... xn)) = (f xn ... (f x2 (f x1 base))...) (define (foldl f base alox) ...)
Define two functions sum-recipe and sum-accumulator that add the numbers in the given list - once from left to right, once from right to left. For the first method follow the design recipe. For the second one use an accumulator. Which one is which?
We start with designing data - designing classes of data that are connected to each other in a systematic way, showing that the Design recipe for Data Definitions can be used virually without change in a completely different language than we have used in the first part.
We start designing methods in the functional style, i.e., every
method produces a new value (primitive or a new object) and makes no
changes in the existing data. This allows us to use a very simple
language, one where the only two statements are return
and if (condition) then statement else statement.
The programs we provide give you examples of the progressively more complex data (class) definitions, and illustrate the design of methods for these class Hierarchies.
The design of methods follows
the same Design Recipe we have seen before. The only
difference here is that for classes that represent a union type (for
example classes Circle and Rectangle that
are both a part of the union type Shape, the conditional
statement used in teachScheme! inventory is replaced by the
dynamic dispatch into the class whose constructor has been used to
define the specific object.
Loops process a collection of data (in our case mostly a list of data) one item at a time and apply some function to every item, producing a new value. A map produces a list of items that are the result of applying the function to every item in the list. A filter applies a predicate to every item and includes in the resulting list only the items for which the predicate produces a true value. The two fold loops apply the given function to two values, the base and the current item, producing a new accumulated value. The function for the subsequent data items is applied to this accumulated value and the current item, until we exhaust all items in the list.
At times, we cannot solve the problem without remembering something about the list of data we traverse. Think of how we compute the distance along a path, given as a list of locations, if we know how to compute the distance between two locations. Try it: design the function total-distance with the following purpose and header:
;; compute the distance along the route given by the list of posn-s ;; total-distance: [Listof Posn] -> Number (define (total-distance alop)...)
Assume, we already have the function:
;; compute the distance between two posn-s
;; dist: Posn Posn -> Number
(define (dist p1 p2)
(sqrt (+ (* (- (posn-x p1) (posn-x p2)) (- (posn-x p1) (posn-x p2)))
(* (- (posn-y p1) (posn-y p2)) (- (posn-y p1) (posn-y p2))))))
(check-expect (dist (make-posn 0 3) (make-posn 4 0)) 5)
Hint You will need the following hepler function:
;; compute the remaining distance from the most recent point along the given path, ;; if we have already traveled the given accumulated distance to get to this point ;; total-distance-acc: [Listof Posn] Posn Number -> Number (define (total-distance-acc alop pos acc) ...)
When defining functions that use the accumulator always make sure the purpose statement explains what is the meaning of the accumulated value and how is it updated during each loop iteration.
Another reason for using accumulators is to avoid the delay in computing the result until we have seen all items in the collection (list). So, we can add alll items in the list by delaying the application of the addition until we see the last item in the list, or we can apply it to the first item (and the base), and carry with us the accumulated partial sum. We will learn later when and how we can convert the loops into the accumulator style.
It is time for each of you to select (with our help) a homework partner for the first four weeks. Please, let your TA know who are the partners, or ask for help in finding one.
Managing your work
Professional programmers need to keep track of the changes to their programs in a systematic way. Several different version control systems are designed to keep track of all changes in the program over its lifetime. They allow programmer to access their code from different computers, to return to an earlier version if the new changes prove to be ill conceived, and allow others to see what changes have been made over the lifetime of the program.a
We will use the svn version control system to manage the work of each homework pair. It will help you from loosing your work if a computer craches, it will allow the partners to collaborate on the project, and will let us see your progress, aswell as the final completed project.
We will be getting set up with the svn next week. Come to the lab with at least a part of your first assignment ready to submit.
To use the svn repository you will need to have an CCIS user id. If you do not have it already, please, fill out the yellow form, submit it to the CCIS system's inbox, and follow the instructions for setting up an account.
Give your CCIS user name to your lab TA, so we can set up the repository for you and your partner.
Next week, make sure you log into the lab computer using your CCIS credentials.