Comp 210 Lab 14: Lists in C

(While waiting for lab to start up, you can go ahead and copy ~comp210/Labs/lab14/list.cc to your own directory.)

Table of Contents

  • Passing by Reference in Extended C
  • Structures without *
  • Lists in C

    • Passing by Reference in Extended C

    Recall the code for swap in lecture: 
    // swap
// exchange the values of the ints *x and *y, as passed-by-reference
//
void swap( int *x, int *y ) {
  int tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
  }

int main() {
  int myScore = 23, yourScore = 92;
  swap( &myScore, &yourScore );        // cheating?

  cout << "Hey I got " << myScore << ", you got " << yourScore << ".\n";

  swap( &100, &myScore );              // ERROR: &100 doesn't make sense!

  return 0;
  }
    Exercise Leave off the ampersand before calling swap( &myScore, ...) and see what happens.

    By passing pointers to our variables, this achieved the effect of passing-by-reference. Smart-alecs (like Ian) might point out that really, you just passed the addresses of the variables by value.

    It turns out, that in C++ (a.k.a. Extended C), it is possible to pass by reference. (Of course what is really happening is that the computer takes care of manipulating pointers for you, so understanding the above code is still worthwhile.) 

    // swap
// Exchange the values of x and y;
// The compiler will automatically passed the arguments by reference.
//
void swap( int& x, int& y ) {       // int& pronounced "reference to int"
  int tmp;

  tmp = x;
  x = y;
  y = tmp;
  }

int main() {
  int myScore = 23, yourScore = 92;

  swap( myScore, yourScore );        // Notice the ease-of-calling
  cout << "Hey I got " << myScore << ", you got " << yourScore << ".\n";

  swap( 100, myScore );              // Warning: swap needs variables!
                                     // g++ happens to save our heinie: it will
                                     // actually create an integer variable, 
                                     // init it to 100, and pass that to swap!
  return 0;
  }
    So if you just want to pass variables so that their value is modifiable by the function, the proper way is to use references rather than messing with the pointers yourselves. (You'll still use raw pointers in other contexts, such as structures.)

    If you are using non-extended C, and are forced to manually use * and & to effect pass-by-reference, here are some notes to help you avoid bugs.

    Exercise: Write the function increment, which takes an integer passed by reference, and adds one to it. The function itself doesn't return anything. (This isn't the best way to increment a variable, but it's a simple pass-by-ref example.) Try writing it from scratch, instead of pattern-matching from the example above!

    Structures without *

    We've told you that whenever you make structures, use that funny * with it. It turns out that's not really necessary.

    In a C program, when you write 

    int x;
    what actually happens? The compiler simply sets aside some memory (typically four bytes hold an int) and associates the placeholder x with the contents of that memory.

    If you were to write 

    struct Complex {
   double re, im;
   };
Complex z;

z.re = cos( pi/4.0 );
z.im = sin( pi/4.0 );
    (note the lack of * with our structure Complex!) the exact same thing happens: the compiler simply sets aside some memory -- enough to hold a Complex, (my guess is that sixteen bytes suffices to hold two doubles) -- and associates the placeholder z with the contents of that memory. The fields of z can be accessed with z.re and z.im.

    Now you can treat Complex exactly as you would int, and get similar behavior: functions taking an int or a Complex can't change the values back in the calling code. If you leave the function in which the local int or Complex was declared, it goes away.

    When we insisted you always used a star * with structures, then really pointers were being used, which now explains why changing them in a function resulted in a change back in the calling code. (This is how structures in Scheme also work.)

    Structures with * revisited

    What happens when we write the following? 
    Complex *zp;
zp = new Complex;

(*zp).re = ...;   // zp->re is just shorthand for (*zp).re
(*zp).im = ...;
    The first line, Complex *zp, creates a pointer to a complex. However, no Complex has been created! Instead, that is what the new command does: it sets aside memory space for a Complex, and we set zp to point to that memory. (See picture drawn on the board.)

    You can use either structures, or pointers to structures; just realize that passing them to functions works differently. I don't recommend intermixing structures with pointers-to-structures; subtle bugs can crop up!

    Lists in C

    In lecture, you've seen a quick introduction to lists in C. Here, we'll go ahead and write code for them. Unlike Scheme lists, our type Cons* is only good for lists of ints. We'd need to make separate structures if we wanted lists of, say, doubles. 
    // Define the structure
struct Cons {
  int car;
  Cons* cdr;
  };

Cons *l, *m, *n;  // note -- we need three stars to declare three lists!

// Make an empty list:
//
l = NULL;

// Make the list (5)
//
m = new Cons;
m->car = 5;
m->cdr = NULL;

// Make the list (7 5)
//
n = new Cons;
n->car = 7;
n->cdr = m;
    A list is to be thought of as type Cons*, not type Cons. The empty list is represented by a pointer to nothing -- NULL (which can be had via #include <stdlib.h>).

    Remember that declaring Code *m declares a pointer, but you need new to actually create a structure. The sequence of calling new and then assigning to the newly-created car and cdr is clearly repeated over and over. Scheme did all of that with a single function named cons. So how would we write a function makeCons in C? That is, we'd like to create a two-element list named two just by writing Here's how!: 

    /* makeCons
 * create a list with desired car and cdr
 */
Cons* makeCons( int datum, Cons* rest ) {
  Cons* result;          // This is the value we'll return.
  result = new Cons;     // Create the new structure (with garbage contents).

  result->car = datum;   // Set up the innards of the structure.
  result->cdr = rest;

  return result;
  }

    How would you write a function to print out a list? Hint: Don't forget the data definition of a list! Think it over in your head, and then check the file list.cc.
    Exercise: Make a copy of the file ~comp210/Labs/lab14/list.cc, and add a function length, which takes in an argument of type Cons* and returns an int. Hint: write the corresponding Scheme function; it should translate easily into C.
    Exercise: (Optional) Write a tail-recursive version of length. What C construct does tail-recursion translate into?
    Exercise: Here's the loop-version of length in Scheme: 

    (define (length lst)
  (local [(define len 0)
          (define remaining lst)]
         (begin (while-fn (lambda () (cons? remaining))
                          (lambda () (set! remaining (cdr remaining))
                                     (set! len       (add1 len))))
                len)))

(define (while-fn test body)
  (if (test)
      (begin (body)
             (while-fn test body))
      (void)))
    Translate this version of length into C. What is going on, in memory? Draw a picture!

    If you want more practice, you can also write the function sum, in both a non-tail-recursive and tail-recursive fashion. Check with your labbie (or send mail to ian or any TA) to make sure your loop is correct.

    Back to Comp 210 Home