In lecture, makeCons wasn't shown; you can probably figure it out, but here it is:

/* 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? Think it over in your head, and then check here. Exercise: Make a copy of the file ~comp210/Labs/lab13/List.c, and add a function length, which takes in an argument of type Cons* and returns an int. Hint: write the corresponding Scheme function, and it should translate easily into C.
Exercise: Write a tail-recursive version of length. What C construct does tail-recursion translate into?
If you want more practice, you can also right the function sum, in both a non-tail-recursive and tail-recursive fashion. Check with your therapy leader (or send mail to ian or any TA) to make sure your loop is correct.

Lists in Java

Whereas Scheme is a functional language (predisposed towards using functions without side-effects), Java is (like C) an imperative language: its basic unit of computation is the assignment statement. In fact, Java borrows a lot of superficial syntax from C: =, if, ==, for, while, etc.

However, Java is also object-oriented. An object is a structure which has been beefed up to not only have fields (like ints or chars), but also have functions associated with the structure. Such functions happen to be called methods. (Another object-oriented language is SmallTalk; C++ claims to be one, too.)

Let's look at an example. We will mirror the data description for lists:

A List (of integers) is either

Null, or

Cons( int car, List cdr );

We will say that there is a class List. However, every list actually has a more specific type; it is one of the two sub-classes Null or Cons. Here is how we write this in Java. This is part of the file ~comp210/Labs/lab13/List.java. For the moment, ignore lines mentioning length(); we'll come back to that.

abstract class List {

  // Any List, of any subclass, can tell us its length.
  // However, the code must wait, since the answer depends on whether
  // the List is ultimately a native instance of Cons or Null.
  //
  abstract public int length();
  }


class Null extends List {
  public int length() { 
    // --- you'll complete this function momentarily! ---
    return -99;
    }
  }

class Cons extends List {
  public int car;
  public List cdr;

  public Cons( int datum, List rest ) {    // The constructor for a Cons object
    car = datum;                           //   (this is what "new" calls).
    cdr = rest;
    }

  public int length() { 
    // --- you'll complete this function momentarily! ---
    return -99;
    }
  }

There's not a whole lot involved with class Null. However, if an object is of class Cons, then it has a car and cdr. Just as we did for C structures, we declare those fields.

However, recall that in C we had wrote a function makeCons which (1) called new to create the structure, and then (2) filled in the structure. Since this pattern happens so often with objects, object-oriented languages have special methods called constructors. The constructor for a class is a function which has the same name as the class itself, no declared return type, and does the above two steps. So in this case, the method Cons( int datum, List rest ) is the constructor. If lst is an instance of a List, then new Cons( 4, lst ) creates a new Cons object, and passes 4, lst to the constructor.

Finally, just include the keyword public as a matter of faith, putting it in front of each field and method of an object. (Actually, you can get by with only using it for main and toString, but that's another story.)

For example, here is a short test-program for Lists:

  /* List.main
   * A test suite.
   * This method should be inside the class List.
   */
  public static void main( String[] args ) {
    List l1, l2;
    l1 = new Null();
    l2 = new Cons( 3, new Cons( 5, new Cons( 4, new Null() )));

    System.out.println( "l1 is " + l1 + ", and has length " + l1.length() + "." );
    System.out.println( "l2 is " + l2 + ", and has length " + l2.length()  + ".");
    }
  }

    l1 = new Null();
    l2 = new Cons( 3, new Cons( 5, new Cons( 4, new Null() )));

Running a Java Program

As with C programs, there are two steps to running the program:

  owl% java List

Casting

    List lst3;
    // ...lst3 is assigned the value (3 5 4)
    lst3 = new Cons( 17, lst3.cdr );   // NOT QUITE -- must cast lst3 on rhs
    // That was the equivalent of "(set! lst3 (cons 17 (cdr lst3)))", so
    // now, lst3 is the list (17 5 4)

Well, it turns out, the compiler doesn't know (it's not smart enough to infer this). If you were to try compiling the above, you would get the error "No method cdr for class List". But we know, by cleverly looking at how lst3 gets a value, that at the moment, lst3 really is a Cons, not just any old List. You do this by casting lst3 to be a Cons: A cast consists of preceding an expression by its type in parentheses. Thus instead of l3.cdr, write write ((Cons) lst3).cdr.

instanceof

A safer way might be to do a sanity-check, to make sure the cast is legal. Java provides an operator instanceof which asks if an object can be interpreted as an instance of some class. For instance:

if (lst3 instanceof Cons)
  lst3 = new Cons( 17, ((Cons) lst3).cdr );  // this cast guaranteed safe
else
  // hmm, hopefully shouldn't reach this
  System.out.println( "List.main: Uh-oh, lst3 is unexpected." + lst3 );

Exercise: Copy ~comp210/Labs/lab13/List.java to your own directory, and modify it so that Null.length() and Cons.length() work correctly.
Exercise: Declare the method sum(), and write it.
Exercise: Re-write length and sum so they are equivalent to their tail-recursive version. Be sure to use a loop.

Of course, in all these examples, there's nothing special about using lists of int; any type would do. The final homework will have you work with lists of String.

I'll start compiling a list of some common Java errors.