Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #12: More state   

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

As a reminder,

• (define var expr) introduces a new variable and initializes its value to be the result of evaluating the expression expr.

• (set! var expr) changes the value of the pre-existing variable var to be the result of evaluating the expression expr.

• (set-struct-field! struct-expr expr), changes the value stored in the named field of a structure, which is obtained as the result of evaluating struct-expr, to be the result of evaluating expr.

set! examples

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 17^th element directly, but the structure contains exactly a pre-determined fixed number of items.

     (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 i^th location is initialized to a function of i.

     (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 17^th item).

When to use a vector:

the data is inherently indexed (e.g., the measurement taken on the i^th 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 v0 … vn-1) creates a vector of length n of the given elements.
• (build-vector n f) creates a vector of length n of elements (f 0) … (f (sub1 n))
• (make-vector n v) creates a vector of length n, of n instances of v. It is essentially a special case of build-vector.
• (vector-length vec) returns the length of the given vector.
• (vector-ref vec n) returns the n^th element of the vector (counting from zero).
• (vector-set! vec n v) changes the n^th element of the vector to be the given element (counting from zero).

Vector exercises

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) 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? 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

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!) …) 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?

• 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 one 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 the programming language is implemented.

Loop exercises

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. Think about: How would you sum the elements of a binary tree using loops?

Last Revised Tuesday, 24-Aug-2004 13:49:13 CDT

©2004 Stephen Wong and Dung Nguyen