Week 6: Notes

The 'var' keyword

When you declare a local variable, you can use the var keyword to tell the compiler to infer its type. For example:

var s = "distant hill";

This is equivalent to

string s = "distant hill";

var does not allow a variable to hold values of any type at all! C# is statically typed, so any assignment to a variable declared with var must match the type that the compiler inferred. For example:

var s = "distant hill";
s = 14;    // error: cannot implicitly convert 'int' to 'string'

I personally don't use var much. I think code is generally easier to read when variable types are explicit.

exceptions

Like Python and most other modern languages, C# has exceptions. Code may throw an exception to indicate that an exceptional situation has occurred, typically some sort of error. In an addition, the C# language itself will throw an exception in some situations, such as if code attempts to access an array element that's out of bounds, or attempts to access a property of null.

When an exception is thrown, it will pass up the call stack, aborting the execution of any methods in progress until some block of code catches the exception and continues execution. If the exception is not caught, the program will print an error message and terminate.

An exception in C# is an object, specifically any object belonging to the System.Exception class or any of its subclasses. A large number of exception classes are built into the standard library including IndexOutOfRangeException, NullReferenceException, FormatException, and others.

throwing an exception

The throw statement throws an exception, either of a built-in or user-defined exception class. (This is like raise in Python.) For example:

class OpException : Exception {
    char op;

    public OpException(char op) {
        this.op = op;
    }
}

int compute(char op, int a, int b) =>
    op switch {
        '+' => a + b,
        '-' => a - b,
        '*' => a * b,
        _ => throw new OpException(op)
    };

catching exceptions

The try statement attempts to execute a block of code. It may have one or more catch clauses, each of which will execute if a certain type of exception is thrown. For example:

static void Main() {
    StreamReader reader;
    try {
        reader = new StreamReader("numbers");
    } catch (FileNotFoundException e) {
        WriteLine("can't find input file: " + e.FileName);
        return;
    } catch (DirectoryNotFoundException) {
        WriteLine("invalid path");
        return;
    }
    …

When an exception is caught, the catch block (called an exception handler) executes. As you can see in the code above, a catch block may optionally specify a variable to receive the exception object.

A catch block may rethrow the exception it caught, or even a different exception. If a catch block does not throw an exception, execution resumes below the try statement.

Object class

All C# class automatically inherit from a top-level class called System.Object that contains several methods that are shared by all objects. The short name object is a synonym for System.Object.

One method in System.Object is ToString():

public virtual string ToString ();

C# automatically calls this method when it needs to convert any object to a string, for example in an interpolated string:

class Window { ... }


Window w = new Window();

Console.WriteLine($"the window is {w}");   // will automatically call w.ToString()

The default implementation of ToString() simply returns the name of the class, so the above code will write

the window is Window

You can override ToString() in your own classes if you'd like to change their printed representation. (ToString() is like the __repr magic method in Python.)

The Equals() method

The top-level Object class contains a method Equals():

virtual bool Equals (object obj);  // return true if this object equals (obj)

By default, the Equals() method, just like the == operator, tests reference equality, i.e. tests whether two objects are actually the same object. For example:

class Point {
    double x, y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

Point p = new(3.0, 4.0);
Point q = new(3.0, 4.0);
WriteLine(p.Equals(q));   // writes False

WriteLine(p == q);        // writes False

Sometimes we may want to override this method. Arguably two Point objects should be equal if they contain the same x- and y-coordinates. Let's override the Equals method to implement that notion of equality:

    // in class Point
    public override bool Equals(object? o) =>
        o is Point p && x == p.x && y == p.y;

The Equals() method takes a parameter of type object?, so we need to use the is operator to test whether it is a Point and is not null.

With that override, let's try comparing again:

Point p = new(3.0, 4.0);
Point q = new(3.0, 4.0);

WriteLine(p.Equals(q));   // writes True
WriteLine(p == q);        // writes False

Point objects with the same x- and y-coordinates are now equal according to the Equals() method. However, the == operator is still checking for reference equality, so it produces False when given two different objects. If we want, we can also provide an overloaded operator == that would return true in this situation:

    // in class Point

    public static bool operator == (Point p, Point q) =>
        p.x == q.x && p.y == q.y;

You'll notice that if we override Equals(), the C# compiler prints a warning saying that we should also override GetHashCode():

'Point' overrides Object.Equals(object o) but does not override Object.GetHashCode()

That's because two objects that are considered equal by the Equals() method must always have the same hash code, otherwise a HashSet and other collections will not work properly. In the Point class, we might implement GetHashCode by retrieving a hash code for the pair (x, y):

    // in class Point
    public override int GetHashCode() => (x, y).GetHashCode();

generic methods

C# also allows us to write generic methods (or generic functions) that take one or more type parameters, so they can work with values of various types.

For example, consider the swap() function that we saw in an earlier lecture:

void swap(ref int a, ref int b) {
    (a, b) = (b, a);
}

We may call the function like this:

int a = 10, b = 11;

swap(ref a, ref b);

WriteLine(a);    // writes 11, since 'a' and 'b' have swapped

Let's generalize the function so that it will work with values of any type:

void swap<T>(ref T a, ref T b) {
    T t = a;
    a = b;
    b = t;
}

In the code above, T is a type parameter. The name T is arbitrary; in its place we could write U, or any other name we like. However it's traditional in C# (and some other languages too) to use the name T for a single type parameter.

generic classes

A class in C# may also be generic. In fact we've already been using some generic classes from the standard library, such as List<T>. Let's now see how we may write our own generic classes.

Like a generic method, a generic class has one or more type parameters. Here is a generic class FixedStack<T> representing a fixed-size stack of objects of type T:

class FixedStack<T> {
    T[] a;
    int num;  // number of elements currently on the stack

    public FixedStack(int maxSize) {
        a = new T[maxSize];
    }

    public void push(T val) {
        a[num] = val;
        num += 1;
    }

    public T pop() {
        num -= 1;
        T ret = a[num];
        return ret;
    }
}

In the class above, T is a type parameter. When the caller creates a FixedStack, they will specify the type T:

FixedStack<int> s = new(100);  // create a stack of ints
s.push(15);
s.push(25);

FixedStack<string> t = new(100);  // create a stack of strings
t.push("hello");
t.push("goodbye");

Notice that inside the class FixedStack<T> the type T can be used like any other type: we can create an array of objects of type T, or use T as a method parameter type, a method return type or a variable type.

Observe that a FixedStack is not quite like a stack in a dynamically typed language such as Python, where a single stack can hold objects of various types. In C#, by contrast, each FixedStack is tied to some particular element type. That is a good thing: if we create a FixedStack<int>, intending to hold ints, and then attempt to push a string to it by mistake, we will get a compile-time error.

generic interfaces

An interface may also be generic. For example, here's a generic interface IStack<T>, which is a stack of elements of type T:

interface IStack<T> {
    bool isEmpty { get; }
    void push(T i);
    T pop();
}

Above, we wrote a class FixedStack<T>. Let's modify that class so that it implements the IStack<T> interface:

class FixedStack<T> : IStack<T> {
    T[] a;
    int num;  // number of elements currently on the stack
    … 
}

As we've seen before, a variable may have an interface type:

IStack<double> s = new FixedStack<double>(100);
s.push(2.0);
s.push(4.0);

generic method constraints

In the examples we saw above, a generic method or class took a type parameter T that could be any type at all. Sometimes we will want to require that the type T has certain capabilities, for example by requiring that it implements a certain interface. We can accomplish that via a generic constraint.

For example, consider a function that computes the sum of all integers in an array:

int sum(int[] a) {
    int s = 0;

    foreach (int i in a)
        s += i;
    return s;
}

We could write a similar function that computes the sum of an array of doubles, but it would be nicer to have a single function that we can use for int, double, or any other numeric type. We can't write the function using an unconstrained generic:

T sum<T>(T[] a) {
    T s = 0;            // ERROR: Cannot implicitly convert type 'int' to 'T'

    foreach (T i in a)
        s += i;         // ERROR: Operator '+=' cannot be applied to operands of type 'T'
    return s;
}

The type T must have a zero element and must support addition. In the library there's a generic interface INumber<T> for numeric types that support these and other numeric operations. The standard types int, float, and double implement INumber<T>. So we may add a constraint saying that T must implement that interface:

using System.Numerics;

T sum<T>(T[] a) where T : INumber<T> {
    T s = T.Zero;

    foreach (T i in a)
        s += i;
    return s;
}

Now the code will work fine. Note that we must write T.Zero to retrieve the zero element of type T. (Actually Zero is defined in INumberBase<T>, a parent interface of INumber<T>.)

generic class constraints

Suppose that we want to write a class TreeSet<T> that holds values of type T in a binary tree. As a first attempt, we might write

class Node<T> {
    public T val;
    public Node<T>? left, right;

    public Node(T val) { this.val = val; }
}

class TreeSet<T> {
    Node<T>? root;

    public bool contains(T x) {
        Node<T>? p = root;
        while (p != null) {
            if (x == p.val)      // ERROR: Operator '==' cannot be applied to operands of type 'T'
                return true;
            else if (x < p.val)  // ERROR: Operator '<' cannot be applied to operands of type 'T'
                p = p.left;
            else
                p = p.right;
        }
                
        return false;
    }

    // more methods here: insert(), delete(), ...
}

This code will not compile. The problem is that we can't use the > operator to compare two values of type T, because T might be some type that is not ordered – for example, T might be an array type, and arrays cannot be compared in C#.

The C# standard library contains a generic interface IComparable<T> that is implemented by all ordered built-in types. IComparable<T> means "comparable with objects of type T". For example, the built-in type int implements IComparable<int>, since integers are comparable with integers. IComparable<T> is defined like this:

interface IComparable<T> {

    int CompareTo (T other);

}

The CompareTo() method returns

• a negative number if this object is less than other

• 0 if this object equals other

• a positive number if this object is greater than other

For example:

WriteLine(4.CompareTo(7));  // writes -1, since 4 < 7

Let's add a constraint to TreeSet<T> that says that T must implement IComparable<T>. The code will now look like this:

class Node<T> {
    public T val;
    public Node<T>? left, right;

    public Node(T val) { this.val = val; }
}

class TreeSet<T> where T: IComparable<T> {
    Node<T>? root;

    public bool contains(T x) {
        Node<T>? p = root;
        while (p != null) {
            int c = x.CompareTo(p.val);
            if (c == 0)
                return true;
            else if (c < 0)
                p = p.left;
            else
                p = p.right;
        }
                
        return false;
    }

    // more methods here: insert(), delete(), ...
}

Notice that even if T is constrained to implement IComparable<T>, we still cannot use the < or == operators to compare two elements of type T – instead, we must call CompareTo(). This is inconvenient, and is arguably a weakness in C#. Above, we saw that an interface can provide operators: any class implementing the INumeric<T> interface must include + and other numeric operators. This is a relatively new feature (it first appeared in C# 11, released in 2022). Unfortunately IComparable<T> does not include operators such as < and == (probably for reasons of backward compatibility).

nested classes

In the TreeSet<T> example in the previous section, it was a bit inconvenient that we had to make the Node class generic and write Node<T> everywhere we wanted to use it. As an alternative, we can make Node be a nested class inside TreeSet<T>. Then it won't need to be declared as a generic class Node<T>, but will still be able to use the type variable T declared by its containing class TreeSet<T>. The code will look like this:

class TreeSet<T> where T: IComparable<T> {
    class Node {
        public T val;
        public Node? left, right;

        public Node(T val) { this.val = val; }
    }

    Node? root;

    public bool contains(T x) {
        Node? p = root;
        while (p != null) {
            int c = x.CompareTo(p.val);
            if (c == 0)
                return true;
            else if (c < 0)
                p = p.left;
            else
                p = p.right;
        }
                
        return false;
    }

    // more methods here: insert(), delete(), ...
}

In my opinion this is nicer. Node is just a helper class for TreeSet<T> anyway, so it makes sense for it to be nested.

multiple type parameters

A generic class may take multiple type parameters. For example, suppose that we want to write a Dictionary class that maps keys to values using a hash table. It might look like this:

class Dictionary<K, V> where K : IComparable<K> {
    …

    public void add(K key, V val) { … }

    public bool contains(K key) { … }
}

Here, K and V are two type parameters. When the caller creates a Dictionary, they will specify types for K and V:

Dictionary<int, string> d = new();   // maps int → string
d.add(10, "sky");
d.add(20, "purple");

Dictionary<string, double> e = new();  // maps string → double
e.add("purple", 55.2);

As we learned in Introduction to Algorithms, a hash table contains an array of hash chains, each containing a linked list of nodes. So we will need a Node class that holds a key of type K and a value of type V. We could declare it as a generic class Node<K, V>, but it will be easier to nest it inside the class Dictionary<K, V>, and then it will be able to use the types K and V directly. Our code might look like this:

class Dictionary<K, V> where K : IComparable<K> {
    class Node {
        public K key;
        public V val;
        public Node? next;

        public Node(K key, V val) {
            this.key = key; this.val = val;
        }
    }

    Node?[] a;  // array of hash chains
    
    ...
}

In fact we've already seen that the standard library contains a class Dictionary<K, V> that works similarly.

The 'default' operator

Suppose we want to write a generic array class ExtArray<T> that holds elements of type T and has a special behavior: if the caller attempts to read an element that is out of bounds, then instead of an exception they will receive a default value in return. We would like this default value to be the "natural" default for the element type; for example, an ExtArray<int> should return 0 if an access is out of bounds, but an ExtArray<bool> should return false.

C# provides an operator default that provides this. For any type T, default(T) returns C#'s default value for that type:

WriteLine(default(int));   // writes 0

WriteLine(default(bool));   // writes false

Now we can implement ExtArray<T> as follows:

class ExtArray<T> {
  T[] a;
  int count;

  …

  public T this[int index] {
    // return default value if out of bounds
    get => index < count ? a[index] : default(T);

    set => …
  }
}