COMP 210 Lab 11: State and a Little I/O

Index: set! examples, set-struct-field! examples, set! vs. set-struct-field! I/O

Work through the many small exercises on your own, asking labbies at your leisure!

Sequencing with begin

We can sequence operations with begin. For example, 

     ; An uninteresting use of begin.
     (begin (+ 2 3)
            (* 2 3)
            (- 2 3))

     ; An interesting use of begin.
     (define x 3)
     (begin (set! x (add1 x))
            (set! x (add1 x))
            x)
evaluates each of its (three) expressions, throws away the results of all but the last, and returns the value of the last expression. In this case, -1 and 5, respectively. Unless the prior expressions mutate state, sequencing is not useful.

set! examples

To change which thing a variable refers to, we use set!, as introduced in class.

set! exercises

For each, first try it in your head or on paper, then check your answer using DrScheme. These are "toy" examples that are not necessarily typical of real programs. However, they illustrate important issues of using state.

  1. What are the values of the variables x and y after the following? It might help you to ask what values x and y have after each set!. 

                  (define x 1)
              (define y 2)
              (set! x (+ x 1))
              (set! y (+ y 1))
              (set! x (+ x y))

    The hand-evaluation rule for (set! variable exp) is

    1. Evaluate exp to a value val.
    2. Replace the previous definition of the variable with (define variable val).

  2. What are the values of x and y after the following? 

                  (define x 1)
              (define y 0)
              (local [(define x 3)]
                 (begin
                   (set! x (+ x 1))
                   (set! y x)
                   y))

  3. For each of the following, do you get 10, 11, or 12? What are the values of x and y after the following? What does that tell you about the order of evaluation of function arguments? 

                  (define x 5)
              (+ (begin (set! x 6) x)
                 x)

              (define y 5)
              (+ y
                 (begin (set! y 6) y))

    This example is very bad style. You should not write code that depends on the the order of evaluation because it is very confusing. Moreover, by definition, a different implementation of Scheme isn't guaranteed to use the same order.

set-struct-field! examples

In class we discussed how constructors (e.g., make-foo) evaluate to a reference to a new structure, and not to the new structure itself. This allows us to share references to the same structure. Also, we discussed how to mutate (change) structures. This lets our program more closely match what we're modeling.

set-struct-field! exercises

  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 their best buddy (which every cat has).
       
              ; 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. Optional: 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.
    Can you sketch a few pictures of what htis 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. If you have time, 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.

Cons-cells are just predefined kinds of structures, using a naming convention that doesn't quite correspond to user-defined structures. For mutating these structures, Scheme provides the functions set-first! and set-rest!. (Remember that a list is not just a single structure, but a bunch of cons-cells, or empty (which is a flat value -- not a (reference to a) structure!)

List mutation exercises 
       (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?

Input and output

Since Scheme automatically displays the result of whatever expression we give it, so far we haven't needed to know how to display something ourselves. Here are a few functions for getting information into and out of our programs, although Scheme has lots more. Try them out.

printf

printf displays information to the screen. It takes at least one argument: a string giving the format of what to display. printf may take more arguments, if so specified by the format. E.g., 

     (printf "hello, world~n")
displays the string hello, world, followed by a newline. The ~n means a newline. 

     (printf "hello, ~v~n" 'world)
displays the same thing. The ~v indicates that the next argument's value should be printed in place of the ~v. (Mnemonic: "v" meaning any value.) 

     (printf "~v ~v ~v~n" (+ 1 1) (list 'a 'b) true)
displays three things separated by spaces and terminated by a newline. The three things displayed are the values of the remaining arguments.

error

error causes an error to happen and displays an error message. In this class, we haven't been concerned with writing functions that check for bad inputs. In real life and later classes, we'd want to check and report any errors, including bad inputs. 

     (error 'myfunction "error message")
causes an error. It also displays an error message using the symbol provided (typically the current function name), the string for the error message. The format function can be used to format the error string before it is passed to error.

read

read stops a program, waits for the user to type something in, and returns the value that the user just typed in. It takes no arguments. Each time it is used, it could return a different value, since the user can type in something different each time.

read exercise
Execute the following code, typing in answers when prompted. 
     (printf "I will read, but immediately forget the next thing you type.~n")
     (read)

     (printf "What is your name? ")
     (define name (read))
     (printf "Howdy there, ~v.~n" name)
Observe how words you type in are read as symbols. You can click on "eof" to type in an "end-of-file" signal. (Aside: you can use ~a to format output suitable for non programmers -- that is, symbols aren't preceded by ' and strings aren't surrounded by "s.)

Tracing

So far, you have used two good techniques for debugging code:

Another technique is called tracing (or printf debugging). At the beginning of each function, we'll print out the name of the function, and all of the arguments. At the end of each function, we'll print out the name of the function, and the return value. This allows us to track what is going on during execution, but with less detail than stepping. Variations on this theme allow you more control over what parts of the program you trace and how much information you see.

Consider the following incorrect version of factorial. 

     ;; buggy-fact: natnum --> number
     ;; Return n!.
     ;;   OOPS -- doesn't work -- always returns 0?!!
     ;;
     (define (buggy-fact n)
         (cond [(zero? n) 1]
               [else      (* (sub1 n) (buggy-fact (sub1 n)))]))

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

  1. Load the teachpack trace.ss.

  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!

For the curious... Some programming environments like DrScheme having tracing built-in. But, some don't. So, it can be valuable to understand how to incorporate tracing into your own program. The basic idea is simply to add printf's to print out the input(s) and output(s) of the function. (Thus the name "printf debugging", since the function is also called printf in the language C, where this technique is common.) 

     (define debug? true)  ; Do I want to display debugging info?

     ;; buggy-fact: natnum --> number
     ;; Return n!.
     ;;   OOPS -- doesn't work -- always returns 0?!!
     ;;
     (define (buggy-fact n)
        (begin
           (when debug? (printf "buggy-fact input: ~v~n" n))
           (local [(define result
                       (cond [(zero? n) 1]
                             [else      (* (sub1 n)
                                           (buggy-fact (sub1 n)))]))]
               (begin
                  (when debug? (printf "buggy-fact output: ~v~n" result))
                  result))))

Here, we used a boolean flag debug? to indicate whether or not to print out debugging info. This makes turning on/off debugging very easy. It can get very annoying to add and remove debugging repeatedly.

Also, we used a conditional called when: 

     (when test-exp exp ... exp)
evaluates its test-exp, and if true it returns (begin exp ... exp)); if the test-exp is false, then no useful value is returned (just as set-struct-field! and printf don't return any useful value).

There are lots of variations on this idea to make it more useful. For example, we'd like to encapsulate the debugging aspect into a separate function. And we'd like finer control over what specific functions we want to trace.