COMP 210 Lab 12: More state

set! vs. set-struct-field!, set! examples, Vector basics, "For" Loops, "Until" Loops

Review: set! vs. set-struct-field!

As a reminder,

set! examples

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.

  4. How does set! interact with functions?

    First, try this at your current Advanced language level. Then, try it against at the Pretty Big language level. 

                  (define b 17)
              (define c 5)
              (define x 7)

              (define (foo a b)
                 (begin
                   (set! a b)
                   (set! b c)
                   (set! c a)))

              (foo c x)
              b
              c
              x
    An aside

    Note: It is generally considered bad style to set! a function parameter. Some other languages, given code much like this example, have different behavior. This is a result of a choice between call-by-value (as in Scheme, where function arguments are evaluated before calling the function) and call-by-reference. Thus, there is a possibility of getting confused about what it means to set! a function parameter, which is one main reason to avoid doing this.

  5. For contrast, how does set!-struct-field interact with functions? 

                  (define-struct abox (field))

              (define b (make-abox 17))
              (define c (make-abox 5))
              (define x (make-abox 7))

              (define (bar a b)
                 (begin
                   (set-abox-field! a (abox-field b))
                   (set-abox-field! b (abox-field c))
                   (set-abox-field! c (abox-field a))))

              (bar c x)
              b
              c
              x

Vector Basics

A list can contain as many items as you like, but you can only access the first element directly. In contrast, we'll introduce a new structure, vectors, where you can access (say) the 17th element directly, but the structure contains exactly a pre-determined fixed number of items.

Vector example

Here as some self-explanatory examples of how to use vectors. Type them into DrScheme and see what happens. 

     (define colors (vector 'teal 'ecru 'lilac 'maroon 'red))

     (vector-ref colors 3)
     (vector-ref colors 0)
     (vector-ref colors 5) ; ERROR -- indices must be in [0,5).

     (vector-length colors)

     (vector-set! colors 3 'macaroni)
     (vector-ref colors 3)

In addition to creating vectors via vector, there is also a function build-vector, which creates a vector where the ith location is initialized to a function of i.

Vector exercise

What should the following return? 

     (build-vector 5 sqr)
     (build-vector 5 (lambda (i) (* 2 i)))

In comments, we'll often write "v[i]", as a shorthand for "(vector-ref v i)".

Vectors are another abstraction for collections of data. Like a structure, each element of a vector is named, in this case with a number. I.e., they are named 0, 1, 2, 3, … in order. Vectors can be of any length when created, although you cannot change the length of a particular vector.

Let's compare three somewhat similar kinds of data structures:

When to use a list:
you don't know in advance how many data you will have; and
you tend to process all the data together (rather than just the 17th item).
When to use a vector:
the data is inherently indexed (e.g., the measurement taken on the ith day);
you routinely want to access an item by its index, and not process the rest of your data; and
you know in advance how many data you will have.
When to use a structure:
the data is inherently named (e.g., Mary's first name, last name, and student ID);
you routinely want to access an item, and not process the rest of your data; and
you know in advance how many data you will have (and typically, this number is small).
An example

When msn.net was first set up, people could sign up for accounts. When they got their one-millionth customer, their code broke -- the site was down for three days, and a million customers couldn't log on to the net. Presumably they'd used vectors, when a list would be more appropriate.

(They wanted the constant-time random-access of a vector, but didn't know the number of elements in advance. At the very least, their code for adding a new customer should have had refused the millionth customer, rather than crashing the system for everybody!

Remember that vector elements are indexed starting with 0, not 1! That means you should never use code like 

     (vector-ref vec (vector-length vec))
because there is no such element in the vector. While there is a historical reason for 0-indexing, today the primary motivation is tradition. Almost all programming languages follow this tradition.

Note that we can have empty vectors, just like empty lists: 

     (vector)
This is a vector with zero elements. (Fairly useless, isn't it?)

We won't worry about all of the following, but for your reference, here is a summary of the most common built-in vector functions:

Vector exercises

  1. Using build-vector, develop a function that, given a vector of numbers, returns a new vector of the same length containing the squares of the numbers in the original vector, as in the following: 

             (define v (vector 7 3 5 2))
         (define w (vector-square v))
         v                             evaluates to (vector 7 3 5 2)
         w                             evaluates to (vector 49 9 25 4)

  2. Develop a function vector-square! that, given a vector of numbers, destructively changes the vector to contain the squares of the old elements, as in the following example: 

             (define v (vector 7 3 5 2))
         (vector-square! v)
         v                             evaluates to (vector 49 9 25 4)

    Here's code to get you started. The function can either return some dummy value like 'woohoo, or (slightly more helpfully) the same vector that was passed in. 

             (define (vector-square! v)
            (local
                ([;; vector-square-help!: natnum --> …
                  ;; Destructively square the first n elements of v.
                  ;;
                  (define (vector-square-help! n)
                     …)])
              (vector-square-help! v (vector-length v))))

    Observe that this describes n as the number of elements left to change, not as the index of the next element to change. Discuss: What is the difference? What is the problem with using the index?

  3. Optional: Modify vector-square! so that instead of following the NatNum template, counting down to 0, instead it counts up from 0. I.e., change the contract of the helper to 

             ;; vector-square-help!: vector, natnum --> …
         ;; Destructively square the last n elements of v.

    This is simply another approach that more closely resembles the tradition for loops, as discussed in the next section.

"For" Loops

In that last exercise, there are really two different things:

  1. Given i, do a task involving i: (vector-set! v i (sqr (vector-ref v i)))
  2. Do this task, for each i in the range 0, 1, 2, …, n-1.
Let's separate these two things explicitly.

We'll loop through each of these values. When using loops, it is more common to count upwards, so we'll do that. So, the latter part is looping from 0 to n-1. (Note that if n=0, that means doing nothing.) Note that this is an abstraction similar to foldr for natural numbers: it allows us to seperate the code for an individual task from the iterative process of calling that task on 0, 1, 2, …)

Loop examples

  • To square each element of the vector nums, we'll be able to write the following: 

           (loop-for 0
                 (vector-length nums) 
                 (lambda (i) (vector-set! nums i (sqr (vector-ref nums i)))))

  • We saw printf in last week's lab, where (printf "x is ~v." x) will (as a side-effect) print the value of x to the screen. With our loop construct, one could write the following: 

           (loop-for 10
                 20
                 (lambda (i) (printf "The square root of ~v is ~v.~n" i (sqrt i))))
"For" Loop exercises

  1. What is the general form for this looping function, loop-for? Write the general function loop-for, where you explicitly return 'done if the start-val equals or exceeds the stop-val; otherwise you do two things: call body!, then recursively call loop-for. 

           ;; loop-for: num, num, (num-->(void)) --> 'done
       ;;
       (define (loop-for start-val stop-val body!)
          …)

  2. Using loop-for, write a function which sums all the numbers in a vector.

    Hint: Define a variable sum-so-far to be 0 initially, and then as you loop, set! that variable.

To think about: What if we frequently wanted to do something with every other number in a range? Should we modify the task (i.e., body!), or modify the control logic in charge of applying body! to the right values? Both ways work; the latter is better, since it separates the individual task from the looping.

Do we need to use mutation, to make use of a "for" loop? No, we actually have been doing stuff all along which didn't. Consider the following examples: 

     (triangle-number 3)  = 1 + 2 + 3 = 6
     (countdown 3) = (list 3 2 1 'blastoff)


     (define (triangle-number n)
       (loop-for-acc 1
                     (add1 n)
                     0                                    ; The initial sum-so-far (accumulator).
                     (lambda (i so-far) (+ i so-far))))   ; A body which creates new accum.

     (define (countdown n)
       (loop-for-acc 0
                     n
                     '(blastoff)                          ; Initial accumulator value.
                     (lambda (i so-far) (cons (add1 i) so-far))))
"For" Loop exercises

Write a version of loop-for-acc which separates the work that you're doing from of doing that work with 0, then with 1, …, then with i-2, then with i-1. 

       (define (loop-for-acc strt stop init body )
         …)

"Until" Loops

Let's see another example of how recursion and looping are related. Some of the corresponding syntactic pieces are highlighted in color.

  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 obtain the 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. Thus, part of the reason it was relatively easy to obtain this version is that addition is associative and commutative.

  3. We can rewrite this to avoid passing arguments in the helper function and, instead, change only local variables. This step is similar to the assembly-language code that a compiler would produce. This is a straightforward syntactic translation: 

         (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!)))

    Question

    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. (Make sure you're using DrScheme's "Pretty Big" language level.) This is another straightforward syntactic translation: 

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

    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 loop value from the current one, and a function to evaluate on each loop iteration.

    Question

    What must the contract for loop-until be?

    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). Then, it is typically called a "while" loop.

This process is insufficient for all programs, but it shows that recursion and iteration are closely related. They are both useful tools.

Which version of sum-list is best?

Loop exercises

  1. If you have time left, write imperative versions of factorial and foldl. You may use the above steps if you find them helpful, or just skip to the solution.

  2. Think about: How would you sum the elements of a binary tree using loops?