Comp 210 Lab 12: Arrays and Vectors

Simple loops, Assignment

General tip: Use your comp210 directory for all your programs. It's not required, but it's a good habit to get into. Furthermore, set the protection of the directory so that only you can use it: chmod og-rwx comp210. That way, noone else can copy your work. If someone copies your homework, even without your knowledge, you can be under suspicion for the honor code violation!

General tip: You should always use good style in any of your programs. E.g., use comments, name variables mnemonically, and indent code to align similar things. If anything, this is extra important in C because it is a lower-level language that can be difficult to debug.

We'll be switching back and forth betwen Scheme and C examples throughout lab.

One of our favorite examples has been to sum a bunch of numbers.

1. Write a recursive function sum_vec that takes a vector vec and natural numbers low and high, and returns the sum of the numbers in the low...highth positions (inclusive) of vec.
2. Use this to sum all the integers in, say, (make-vector 13 5).
3. Write a tail-recursive version using while-fn:

   (define while-fn
       (lambda (cnd body)
           (if (cnd)
               (begin (body) (while-fn cnd body))
               void)))
        

4. Write a C version using while or for.

Some C off-by-one errors are harder to find than in Scheme. In Scheme, what happens when you try summing one more element than is actually in the vector? Try it. In C, what happens when you do this? Try it. The difference is bounds checking -- Scheme does it, and C doesn't. This is one of many places where C lets you get away with a mistake (usually) without any complaints, and it's one reason why debugging C code can be VERY difficult.

Rather than computing the single sum of all of the vector elements, let's compute the sums for elements in the ranges 0..0, 0..1, 0..2, 0..3, etc. These are known as the prefix sums. The result is a vector of sums, of the same length as the original vector. In Scheme, write a program prefix_sum for this. You should be able to use any of your sum_vec programs as a helper function. Once you have a version of prefix_sum, try writing it with a single function (no helper) with two uses of while-fn, one nested inside the other.

Here's a simple example of changing a vector:

(define vec (make-vector 10 5))
(vector-set! vec 4 7)
vec

{
  int vec[10]={5,5,5,5,5,5,5,5,5,5};
  vec[4]=7;
  for (int i=0; i<10; i=i+1) cout << vec[i] << " ";
}

Try the following Scheme program. What are the values of the vectors at the end?

(define vec1 (make-vector 10 5))
(define vec2 (make-vector 10 5))
(vector-set! vec1 4 7)

(define vec3 (make-vector 10 5))
(define vec4 vec3)
(vector-set! vec3 4 7)

Explain what happened. Consider how this corresponds to what is really happening in our machine, the JAM2000.

This shows that you need to be very careful in how you use assignment. Changing one vector can change another vector if they really are the same thing. This is a very powerful tool that let's you do some tricky things. But it can make debugging much more difficult.

Here's a related example. What is the value of the vector at the end?

(define foo
   (lambda (v)
      (vector-set! v 0 0)))
(define vec (make-vector 10 5))
(foo vec)

Can you translate these examples into C? You should see the same behaviors.

As we did with lists, to see if two vectors simply contain the same data, we'd have to write our own equal function which looked at all of the elements. But it's not difficult to test if two vectors really are the same vector. One way would just mimic the previous examples. Easier is to just use Scheme's eq? or C's ==.

Let's look at returning locally declared vectors from functions. In Scheme:

(define foo
   (lambda ()
      (local ((define v (make-vector 10 5)))
          v)))
(define vec (foo))

(int []) foo()
{
   int v[10]={5,5,5,5,5,5,5,5,5,5};
   return v;
}
int main()
{
   int vec[10]=foo();
   ...
}