Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #11: State and a Little I/O   

1. Complete the function create-cat.

                 (define-struct cat (name age high? buddy))
                 ;
                 ; A cat is:
                 ;   (make-cat [symbol] [number] [boolean] [cat])
                 ; where age is in cat-years,
                 ; high? is whether they are high on catnip,
                 ; and buddy is a cat.
          
                 ; A dummy value to use for cats' "buddy" field, initially;
                 ; presumably we'll remember to assign it a real value,
                 ; before we ever need to use it!
                 ;
                 (define no-buddy '??dummy??)
   
                 ;; create-cat: symbol, number --> cat
                 ;; Return a newly-created cat, 
                 ;; with name nm and age yrs,
                 ;; who is not high and has the buddy field initialized
                 ;; to no-buddy.
                 ;;
                 (define (create-cat nm yrs)
                   ...)
   
                 (define cat01 (create-cat 'morris 23))
                 (define cat02 (create-cat 'leo    47))
                 (define cat03 (create-cat 'cheshire 1))
   
                 (define mgm-logo cat02)
                 

2. On paper, draw a picture of what things are like. Hint: draw all cat structures in a row in the middle of the page. Keep all "define"s off on the left of the page. (Each placeholder is bound to a *reference*, which you can draw as an arrow.)

3. One can have structures in a list, not bound to placeholders, as in the following examples.

                 (define others (list (create-cat 'puss   11)
                                      (create-cat 'shere-khan 22)))
   
                 (define housecats (list (first others) cat03))
                 

   Extend your picture to include these changes. Hint: Make each list a row of cons cells, all in a row, with references off to the cats in the middle of the page.

   Compare with the pictures that the lab-leader should have drawn on the board! Being able to draw the relations between structures is a skill which you'll need to have down cold!

4. What are the values of cat03, others, and housecats, after the following?

                 (set-cat-high?! cat03 true)   ; Light up his smile.
                 

5. How would you make a narcissistic cat, i.e., one that is its own buddy?

6. Discuss with your partner and/or labby: Does the following data definition make sense?

   • A movie is a structure which contains, among other things, a list of stars.
   • An actor is a structure which contains, among other things, a list of movies they've starred in.

   Sketch a few pictures of what this might look like. (Keep your example small :-))

7. Write the following very easy function.

                 ;; befriend!: cat, cat, -> (void)
                 ;; Effect: Set c1's buddy to be c2.
                 ;; Note that c2's buddy remains unchanged.
                 ;;
                 (define (befriend! c1 c2)
                    ...)
                 

   Note the "effects" comment. You should always provide such a comment when your function changes state that is visible outside the function.

   That wasn't very interesting. But, we'd like to modify befriend! so that it returns a boolean: is c1's friendship reciprocated by c2? That is, we set c1's buddy to be c2, but is it the case that c2's buddy is now c1?

   However, writing code for this presents a problem: a function's body consists of exactly one expression, but we want to have two expressions: one to set-cat-buddy! as before, and another to test whether c2's buddy is equal to c1.

   Note: Some consider it bad practice to have functions that both calculate/return a value, and have a side-effect. In practice, doing so is very handy in a few situations, but by and large leads to bugs, since later you might call your function for a value, but forget that it has a side-effect, or vice versa. In this example, it would be much better to write a separate function reciprocates?, instead of blending this function in with befriends!.

   Rewrite befriend! to accomplish its new goal.

8. Write the following function.

                 ;; pass-the-catnip: cat --> (void)
                 ;; Set not only this cat's metabolic status to being high on catnip,
                 ;; but also it's buddy's status (and, that buddy's status, and ...).
                 

   Uh-oh: the data definition for cats refers to itself, and doesn't have any base case! This is an instance of generative recursion. How can we avoid an infinite loop here? Two approaches come to mind; you can try either one:

   • Keep an accumulator of which cats have already been processed; if given a cat which is already in the processed-cats, stop and return a dummy value.
   • Add a new field to cat, called "has-been-processed?"; if given a cat which has-been-processed, stop and return a dummy value.

       (define mylist (list 1 3 5 7))
       (define yourlist (rest mylist))

       (set-first! yourlist 10)         ; The first should be a list element.
       ; what is mylist now?
       ; what is yourlist now?

       (set-rest! mylist (list 2 4))   ; The rest should be a list.
       ; what is mylist now?
       ; what is yourlist now?

       (set-rest! (rest mylist) mylist)
       ; what is mylist now?
       ; what is yourlist now?
       

DrScheme has a version of tracing built-in that is very easy to use.

1. Load the teachpack trace.ss.

   Sorry, this teachpack is missing from the current installation. Skip this exercise.

2. Evaluate (trace buggy-fact), to turn tracing on for that function.

3. Call buggy-fact with some example inputs to see what the tracing information look like and to see buggy-fact's incorrect output.

4. Fix it!