set!

Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention.

set! review

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

While define introduces a new variable and initializes its value, set! changes the value of a pre-defined variable. You can't define a variable multiple times. (Of course, you can define the same name in different scopes, but each is considered a different variable.) You can't set! a variable unless it's been defined previously.

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

1. Evaluate exp to a value val.

2. Replace the previous definition of the variable with (define variable val).

set! exercises

We'll review set! by some small artificial examples.

set! examples/exercises

Try evaluating the following examples. First try them in your head or on paper. Then try them in DrScheme to see if you were right. (define x 1) (define y 2) (set! x (+ x 1)) (set! y (+ y 1)) (set! x (+ x y)) What are the values of the variables x and y now? It might help you to ask what values x and y have after each set!. Let's look at changing local variables: (define x 1) (define y 0) (local [(define x 3)] (begin (set! x (+ x 1)) (set! y x) y)) What are the values of x and y now? (define x 5) (+ (begin (set! x 6) x) x) (define y 5) (+ y (begin (set! y 6) y)) For each, do you get 10, 11, or 12? What are the values of x and y at the end? What does that tell you about the order of evaluation of function arguments? The last 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.

Now, let's try some more useful examples of set!.

set! exercises

Develop the following function. Each call to factorial-count! not only returns the factorial, but also increments a global counter, factorial-counter. (Note the use of the "effects" comment to describe the side-effects.) ; factorial-count! : natural -> natural ; Purpose: Returns the factorial of its argument. ; Effects: Increments factorial-counter. ; Examples: ; > factorial-counter ; 0 ; > (factorial-count! 3) ; 6 ; > factorial-counter ; 1 ; > (factorial-count! 5) ; 120 ; > factorial-counter ; 2 While this might seem kind of silly, this idea comes up all the time. More generally, we can keep track of lots of kinds of information about how a function is used. A common reason is to profile the function, to see how often a function is used or what its arguments typically are, to know how to better optimize it. A solution. However, we would like to hide the counter factorial-count locally inside the function factorial-count!, so that nobody else can change it. Simply moving the definition into a local is easy enough, but there are two big problems if the counter isn't global: we need control over when the counter is initialized, and we need some way to view the counter. Develop the function factorial-count! : ('init or 'count or natural) -> (void or natural) The input is simply a "message" indicating one of the possible actions of the function: given 'init, it (re)initializes the counter to zero and returns nothing (i.e., void); given 'count, it returns the current count; or given a natural number, it returns the factorial and increments the count. Part of the program just follows the three-case template for the above input type -- that should be easy. The "trick" is to define the counter in the right place in the definition. Every call to factorial-count! should use the same counter. A solution.

In Scheme, it is common convention to give imperative functions names ending with an exclamation mark.

Imperative Programming

This course has dealt primarily with a style of programming known as functional programming. Another style is imperative programming, which focuses primarily on side-effects (e.g., set!), rather than passing arguments.

Let's get a hint at the relation between these two styles of programming. In particular, let's see an example of how recursion and looping are related.

1. We start with a simple structurally recursive program:

   (define (sum-list alon)
      (cond [(empty? alon) 0]
            [(cons? alon)
             (+ (first alon) (sum-list (rest alon)))]))
   

2. We can then write an accumulator version:

   (define (sum-list alon)
      (local [(define (sum-list-acc the-lon accum)
                 (cond [(empty? the-lon) accum]
                       [(cons? the-lon)
                        (sum-list-acc (rest the-lon)
                                      (+ (first the-lon) accum))]))]
         (sum-list-acc alon 0)))
   
   

   As you've seen, sometimes this step is difficult. Remember that this version adds up the numbers in the oppositive order. It was easy to write this version because addition is commutative, a+b+c = c+b+a, and thus adding in the opposite order gives the same result.

3. We can rewrite this to avoid passing arguments in the helper function and, instead, change only local variables. This is a straightforward syntactic translation of the accumulator version:

   (define (sum-list alon)
      (local [(define accum 0)
              (define the-lon alon)
              (define (sum-list!)
                 (cond [(empty? the-lon) accum]
                       [(cons? the-lon)
                        (begin
                           (set! accum
                                 (+ (first the-lon) accum))
                           (set! the-lon
                                 (rest the-lon))
                           (sum-list!))]))]
         (sum-list!)))
   

   Q: Does the order of the two set!s matter? Why or why not?

4. Lastly, we can rewrite this using one of Scheme's several looping constructs. loop-until takes four arguments: a starting value to loop on, a test for what value(s) to stop on, a function to get the next iteration's value from the current one, and a function to evaluate on each loop iteration. (loop-until is defined in the "Pretty Big" language level.)

   (define (sum-list alon)
      (local [(define accum 0)]
         (begin
            (loop-until alon
                        empty?
                        rest
                        (lambda (the-lon)
                           (set! accum (+ (first the-lon) accum))))
            accum)))
   

   Note: Most programming languages have a construct similar to this, except with a test for what value(s) to continue looping (i.e., the opposite of what's used here). It is typically called a while loop.

Looping exercises

What's the contract for loop-until? Go back to the Advanced Student language level and define the function loop-until. Test your answer on the above example use.

This shows that recursion and iteration are closely related. In fact, we think of iteration as one form of recursion. The process above works well for recursion/iteration on lists, but is too simple in general. Challenge: Think about why this doesn't work for recursion on trees, and how you can fix that.

Which version is "best"? The first is stylistically best, because it is the most easily understood. Also, it is much easier to make mistakes in the versions with set!. They are all essentially equally efficient -- they each recur once per list element. However, they may differ by constant factors. What these constant factors are and which version is fastest both depend completely on how DrScheme is implemented.

Imperative exercises

Write imperative versions of the following. You might want to use the above steps, but that's not necessary. factorial foldl using binary search to find a specific number in a sorted vector Challenge: foldr (This is harder than foldl because it is harder to obtain an accumulator-style version of it.) Challenge: the sum of the numbers in a tree

Input and output

Since DrScheme 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 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")
  

  This displays the string hello, world, followed by a newline. The ~n means a newline.

  (printf "hello, ~s~n" 'world)
  

  This displays the same thing. The ~s indicates that the next argument's value should be printed in place of the ~s. (The "s" is short for "s-expression", Scheme lingo for "any value".)

  (printf "~s ~s ~s~n" (+ 1 1) (list 'a 'b) #t)
  

  This displays three things, the remaining arguments, separated by spaces and terminated by a newline.

• As we've previously seen, 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, but in real life and later classes, we'd want to check and report any errors, including bad inputs.

  (error 'myfunction "error message about ~s~n" 'this-error)
  
  

  This causes an error. It also displays an error message using the symbol provided (typically the current function name), the format string, and any other arguments. Like printf, it expects only as many other arguments as specified by the format string.

• read pauses 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.

  (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, ~s.~n" name)
  

printf debugging

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

• running the code and checking outputs against expected results, and

• stepping through code with DrScheme's stepper or by hand.

Using printf appropriately can provide one more good technique, by displaying important pieces of information. You briefly saw an example of this in class. The most common places to do this are at the beginning of a function, the end of a function, and after a bunch of side-effects. With practice, you'll see that these and other techniques each have strengths and weaknesses.

The following version of factorial doesn't work:

      (define (buggy-factorial n)
          (cond [(zero? n) 1]
                [(positive? n)
                 (* (sub1 n) (buggy-factorial (sub1 n)))]))

We can rewrite our code to print out the input(s) and output(s) of the function:

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

      (define (buggy-factorial n)
         (begin
            (when debug? (printf "buggy-factorial input: ~s~n" n))
            (local [(define result
                        (cond [(zero? n) 1]
                              [(positive? n)
                               (* (sub1 n)
                                  (buggy-factorial (sub1 n)))]))]
                (begin
                   (when debug? (printf "buggy-factorial output: ~s~n" result))
                   result))))

We use 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. For larger programs, we can extend this idea in various ways. It would be better to hide debug?. It is often useful to use multiple debugging flags, e.g., to debug separate parts of the code independently. It is often useful to use numbers instead of booleans to display different amounts of debugging info.

It is important to label any debugging values you display so that you know what your output means.

The conditional used here, when, is shorthand for a cond that does nothing when the test is false.

        (when test-exp then-exp)
      = (cond [test-exp then-exp]
              [else void])

It is very easy to add the printf to display the input. However, it is somewhat cumbersome to add the

printf to display the output since we have to name the result to refer to it twice.

printf debugging exercises

Call this function with some example inputs to see what the printed messages look like. Add debugging output to your previous imperative versions of factorial and binary search.