Week 5: Notes

optional parameters

You can make a method parameter optional by giving it a default value:

void fill(int[] a, int start = 0, int val = -1) {
    for (int i = start ; i < a.Length ; ++i)
        a[i] = val;
}

The caller can omit any optional parameters:

int[] a = new int[10];
fill(a);  // same as fill(a, 0, -1)
fill(a, 5);  // same as fill(a, 5, -1)
fill(a, 7, 3);

Optional parameters must appear after any non-optional parameters in a parameter list.

named arguments

When you invoke any method, you may precede any argument with a parameter name, followed by a colon.

For example, the Substring method in the string class is defined as

public string Substring (int startIndex, int length);

We may invoke it in any of these ways:

string s = "bowling ball";

string t = s.Substring(1, 3);  // "owl"
string u = s.Substring(startIndex: 1, length: 3);  // identical
string v = s.Substring(length: 3, startIndex: 1);  // identical

Notice that named arguments may appear in any order, and must appear after any non-named arguments in an argument list.

If some parameters are optional, you may specify any subset of them you like using named arguments. For example, we may invoke the fill function from the previous section as

fill(a, val: 4)  // same as fill(a, 0, 4)

overloaded methods and constructors

In a class you may declare multiple methods or constructors that have the same name but have different numbers and/or types of parameters. This is called overloading.

For example, here's a class that implements a vector with any number of dimensions:

class Vec {
    double[] a;

    public Vec(params double[] a) {
        this.a = a;
    }

    public Vec(int dims) {
        this.a = new double[dims];
    }

    // Compute the sum of this vector and the vector w.
    public Vec add(Vec w) {
        double[] b = new double[a.Length];
        for (int i = 0 ; i < a.Length ; ++i)
            b[i] = this.a[i] + w.a[i];
        return new Vec(b);
    }
}

Notice that there are two overloaded constructors: one takes any number of parameters representing coordinates, and the other creates a zero vector of any number of dimensions. Let's create two vectors using these constructors:

Vec v = new Vec(2.0, 5.0, 10.0);
Vec w = new Vec(5);   // 5-dimensional zero vector

Notice that if the second overloaded constructor above did not exist, then the call newVec(5) would call the first constructor, since 5 can be implicitly converted to a double. When both constructors exist, the call newVec(5) is potentially ambiguous, but C# resolves the ambiguity by choosing the constructor that does not require an implicit conversion.

inheritance

C# supports inheritance, a mechanism that allows a class to extend another class and to change its behavior. We have already seen inheritance in Programming 1, where we discussed inheritance between classes in Python. However we will emphasize inheritance more in Programming 2. Inheritance plays a major role in the C# collection class library and in other popular class libraries such as graphical interface toolkits. Furthermore, in Programming 2 we'll start to write larger programs in which we may have our own uses for inheritance.

Consider a simple C# class that implements a fixed-size stack of values of type int:

class IntStack {
    int[] a;
    int n;

    public IntStack(int limit) {
        a = new int[limit];
    }

    public int count => n;

    public void push(int i) {
        a[n++] = i;
    }

    public int pop() => a[--n];

    public int this[int i] => a[n - 1 - i];

    public static bool operator ! (IntStack s) =>
        s.count == 0;
}

Notice that our class contains

a property count that returns the number of items currently on the stack
an indexer that returns an item by index, where s[0] is the top item on the stack s, s[1] is the second item from the top, and so on
a unary overloaded operator !, where !s is true if the stack s is empty

We'd now like to write a class AvgStack that is like IntStack, but has an additional property avg that can report the average value of the numbers that are currently on the stack. We'd like avg to run in O(1). To achieve that, AvgStack will keep track of the current total of all numbers on the stack. (As you may recall, we saw a similar example in Python in Programming 1.)

We can write AvgStack using inheritance. Here's an implementation:

class AvgStack : IntStack {
    int sum;

    public AvgStack(int limit) : base(limit) { }

    public AvgStack() : this(20) { }

    public override void push(int i) {
        base.push(i);
        sum += i;
    }

    public override int pop() {
        int i = base.pop();
        sum -= i;
        return i;
    }

    public double avg => (double) sum / n;
}

The notation class AvgStack : IntStack means that the class AvgStack inherits from IntStack. In this situation, we say that IntStack is the superclass (or parent class or base class), and AvgStack is a subclass (or derived class).

AvgStack has a public constructor that takes a single argument limit, just like the parent class. The notation : base(limit) means that the AvgStack constructor chains to the base class constructor – in other words, it calls the base class constructor, passing it the same value of limit that it itself received.

The AvgStack constructor does not need to initialize the sum field to 0, since 0 is the default value for fields of type int_.

The second AvgStack constructor takes no arguments and chains to a different constructor in the same class. When chaining to a constructor in the same class, we write : this(); when chaining to a constructor in the base class, we write : base().

AvgStack overrides the push() and pop() methods from its parent class. That means that AvgStack provides its own implementation of these methods. In the push() method, AvgStack calls base.push(d) to call the same-named method in the base class. It then runs sum += i to update the running total. pop() is similar.

Note that if you attempt to build the IntStack and AvgStack classes as written above, the code will not compile! We need to make two changes to the base class IntStack:

1. We must modify the push() and pop() methods to be virtual:

public virtual void push(int i) {
    a[n++] = i;
}

public virtual int pop() => a[--n];

In C#, a subclass may only override base class methods if they are virtual.

2. We must modify the field n in the base class to be protected:

protected int n;    // in IntStack class

That is because the avg property in AvgStack accesses n:

public double avg => (double) sum / n;   // in AvgStack class

In C#, the default access level for any member (e.g. field, method) is private. So if we use the simple declaration "int count;", then count will be private, which means that it will accessible only within its own class. A protected member, by constract, is accessible within its own class and within any subclasses. Finally, as we have seen before, a member marked as public is accessible from anywhere.

using base and derived types

We can create instances of each of the IntStack and AvgStack classes as follows:

IntStack s = new IntStack(100);   // create an IntStack
AvgStack t = new AvgStack(100);   // create an AvgStack

How about the following – will this work?

AvgStack t = new IntStack(100);    // ERROR - does not compile

We are creating a IntStack, and attempting to store it in a variable of type AvgStack. The code will not compile. If t has type AvgStack, then it cannot hold this object because an IntStack is not an AvgStack. In general, an instance of a superclass (e.g. IntStack) is not an instance of a subclass (e.g. AvgStack) because it doesn't have the extended capabilities that the subclass provides.

On the other hand, consider this:

IntStack s = new AvgStack(100);   // works OK

This code will compile: a variable of type IntStack can hold an AvgStack, because an AvgStack is a kind of IntStack. In general, an instance of a subclass counts as an instance of its superclass (or of any ancestor class).

What happens if we invoke a method through a variable whose type is the superclass? In other words, how will the following code behave?

IntStack s = new AvgStack(100);
for (int i = 0 ; i < 10 ; ++i)
    s.push(i);   // which push() will this call?

Which implementation of push() will be invoked by the code above – the implementation in IntStack, or in the subclass AvgStack?

The code will call the implementation in AvgStack. Even though the object is held in a variable of type IntStack, it is actually an AvgStack. A call to a virtual method is resolved based on an object's actual class – the type of the variable holding the object is irrelevant.

The assigment IntStacks=newAvgStack(100) works because the type AvgStack is implicitly convertible to IntStack. Because of this phenomenon, we may write a method that works on IntStack objects and may pass it instances of the AvgStack subclass. For example:

static void empty(IntStack s) {
    while (!s.isEmpty)
        Console.WriteLine(s.pop());
}

We may pass an AvgStack to this method:

AvgStack s = new AvgStack(100);
for (int i = 0 ; i < 10 ; ++i)
    s.push(i);
empty(s);

We have seen that C# will implicitly convert from a subclass to a superclass type. In the other direction, C# provides an explicit conversion that we can access via a type cast. For example:

IntStack s = new AvgStack(100);
AvgStack t = (AvgStack) s;    // explicit conversion

We can use an explicit conversion to a subclass type when we are sure that a variable holds a object of that subclass. On the other hand, if the object does not actually belong to the subclass then the program will exit with an exception:

IntStack s = new IntStack(100);
AvgStack t = (AvgStack) s;  // compiles, but will throw an exception when run

is

The is operator returns true if a value is not null and belongs to a given type. It works with both reference types and nullable types:

IntStack s = getStack();
if (s is AvgStack) {
    AvgStack a = (AvgStack) s;
    WriteLine($"average = {a.avg}");
}

It's also possible to declare a local variable inside an is expression. The lines above may be rewritten as follows:

IntStack s = getStack();
if (s is AvgStack a)
    WriteLine($"average = {a.avg}");

Note that is works even with value types such as int:

int? i = abc();
if (i is int)  // true if i != null
    WriteLine(i);

You can conveniently use is in a while loop to capture all input lines. For example, the following loop will read all lines from standard input and echo them back out to standard output:

while (ReadLine() is string line)
    WriteLine(line);

as

The as operator checks whether a value belongs to a type. If so, it returns the value; otherwise it returns null:

IntStack s = getStack();
AvgStack? ls = s as AvgStack;  // if s was not an AvgStack, ls will be null

abstract classes and methods

In Introduction to Algorithms we learned how to store an arithmetic expression using a tree. Here is a set of classes we might use to store expression trees in C#:

class Expr {
}

class OpExpr : Expr {
    char op;
    Expr left, right;

    public OpExpr(char op, Expr left, Expr right) {
        this.op = op; this.left = left; this.right = right;
    }
}

class IntExpr : Expr {
    int i;

    public IntExpr(int i) {
        this.i = i;
    }
}

An interior node of the tree is an OpExpr, which contains an operator (such as '+' or '-') plus pointers to children. Each child may be either another interior node, or a leaf node stored in the IntExpr class.

For example, the expression 2 + (3 * 4) could be stored as follows:

    // 2 + (3 * 4)
    Expr e = new OpExpr('+',
        new IntExpr(2),
        new OpExpr('*', new IntExpr(3), new IntExpr(4)));

(Of course, really it would be nice to write a parser function that can parse any arithmetic expression and generate a tree for it.)

Now suppose that we'd like to add an eval() method that will evaluate an expression. For example, e.eval() should return 14. We will have implementations of eval() in the OpExpr and IntExpr classes. Because these are implementations of the same method, it will need to be defined in the base class Expr as well. In theory we could define eval() there with a dummy implementation that will never be called:

    public virtual int eval() => 0;

However there is a better alternative. We can define the base class Expr as abstract, and define eval() as an abstract method in that class. An abstract class can never be instantiated directly – it exists only so that subclasses can extend it. Similarly, an abstract method can exist only in an abstract class, and has no implementation – it exists only so that subclasses can implement it.

Here is the complete implementation:

abstract class Expr {
    public abstract int eval();
}

class OpExpr : Expr {
    char op;
    Expr left, right;

    public OpExpr(char op, Expr left, Expr right) {
        this.op = op; this.left = left; this.right = right;
    }

    public override int eval() {
        int l = left.eval();
        int r = right.eval();
        switch (op) {
            case '+': return l + r;
            case '-': return l - r;
            // ... other operator here ...
            default: throw new Exception("unknown operator");
        }
    }
}

class IntExpr : Expr {
    int i;

    public IntExpr(int i) {
        this.i = i;
    }

    public override int eval() => i;
}

Note that an abstract class may even contain fields and non-abstract methods, though we don't have any such members in this simple example.

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

interfaces

In Introduction to Algorithms we learned about various abstract data types, such as stacks and queues. For each abstract data type, we described the methods that it provides. For example, a stack has methods push(), pop() and isEmpty(). We saw that we can implement each abstract data type in various ways. For example, we can implement a stack either using a linked list, or an array. Different implementations of an abstract data type will have equivalent functionality, though they might have different performance characteristics.

C# interfaces formalize this concept. An interface defines a set of methods or other members in an abstract data type. For example, here is an interface for a stack of integers:

interface IStack {
    bool isEmpty();
    void push(int i);
    int pop();
}

There is no implementation yet - just a set of methods to be implemented. We can write a concrete class LinkedStack that implements a stack using a linked list. It might begin like this:

class LinkedStack : IStack {
    Node? head;

    public bool isEmpty() => head == null;
  
    public void push(int i) {
        head = new Node(i, head);
    }
  
    public int pop() { … }
}

Above, "class LinkedStack : IStack" means that we are defining a class LinkedStack that implements the IStack interface. The compiler will check that our class provides an implementation of every method that was declared in the interface. If any implementations are missing, we will get a compiler error.

We might then write a second class ArrayStack that implements a stack using a fixed-size array. It could begin like this:

class ArrayStack : IStack {
    int[] a;
    int num;  // number of elements currently on the stack

    public ArrayStack(int limit) {
        a = new int[limit];
    }

    public bool isEmpty() { return num == 0; }

    …
}

We now have two different concrete implementations of an IStack. We might create two IStack objects as follows:

IStack s = new LinkedStack();
IStack t = new ArrayStack(100);

Notice that a variable can have an interface type, such as the variables s and t above. A variable with an interface type can hold any object that implements that interface.

Method parameters can also have an interface type. For example, here is a method that will empty a Stack, printing all values as it does so:

static void empty(IStack s) {
    while (!s.isEmpty()) {
        int i = s.pop();
        WriteLine(i);
    }
}

We may pass either a LinkedStack or an ArrayStack to this method. For example:

ArrayStack as = new ArrayStack(100);
for (int i = 0 ; i < 5 ; ++i)
    as.push(i);
empty(as);

Notice that an interface may not contain a constructor. Any class that implements an interface may have its own constructor(s), but those are not part of the interface.

An interface may, however, contain properties and indexers. For example, let's modify the IStack interface so that isEmpty is a read-only property, not a method:

interface IStack {
    bool isEmpty { get; }
    void push(int i);
    int pop();
}

All members in an interface are implicitly public, so you should not write the keyword public in an interface declaration. However, when you write a class that implements an interface, all implementations of the interface's members must be declared public (as you can see in the examples above).

Note that a class may implement more than one interface. For example, let's write an interface ICountable for any type that has a current element count:

interface ICountable {
    int count { get; }
}

Now we can modify our ArrayStack class so that it implements both IStack and ICountable:

class ArrayStack : IStack, ICountable {
    int[] a;
    int num;  // number of elements currently on the stack

    public ArrayStack(int limit) {
        a = new int[limit];
    }

    public bool isEmpty => num == 0;  // implementation of property from Stack

    public int count => num;  // implementation of property from Countable

    …
}

interface inheritance

Up to now we have only discussed inheritance between classes. C# also allows an interface to inherit from another interface. An inheriting interface has all the members of its parent interface, and can add additional members of its own. Here is a somewhat abstract example:

interface IShape {
    double perimeter();
    double area();
}

interface IPolygon : IShape {
    int num_vertices { get; }
}

class Circle : IShape { … }

class Rectangle : IPolygon { … }

class Triangle : IPolygon { … }

In this example, an IShape represents a shape in two dimensions and a Polygon is an IShape that has a finite number of vertices. Because the Triangle class implements Polygon, it must provide an implementation of num_vertices as well as of the perimeter() and area() methods.

single and multiple inheritance

C# provides

single class inheritance: a class may inherit from only one other class
multiple interface inheritance: a class may implement multiple interfaces; an interface may inherit from multiple interfaces

This particular combination was popularized by Java. Some object-oriented languages (including Python) have a more general mechanism: they have multiple class inheritance, so that one class may have several immediate superclasses. That is more powerful, but creates various complexities that C# avoids through its simpler model.

You have have noticed that an interface is somewhat similar to an abstract class, since it defines functionality that must be implemented by another class. Here are some differences:

An abstract class may contain fields, but an interface may not.
A class may implement multiple interfaces, but may inherit from only one abstract class.
All members in an interface are automatically public and virtual. Also, you don't need to specify the override keyword when implementing a method declared in a parent interface.

collection class hierarchy

Using what we have learned about classes, interfaces, and inheritance, we could now build a hierarchy of collection classes. It might look something like this:

In this picture there is a top-level interface ICollection with methods that are shared by all collection classes. Below that are the interfaces IStack, IQueue and ISet. Each of these includes the methods of some particular abstract data type. Below that, we see classes that implement data structures, which are concrete implementations of these interfaces. The Deque class represents a double-ended queue, and implements both IStack and IQueue. We also see that the ArrayStack class has a subclass AvgStack.

You should now be able to implement every class in this picture using your knowledge from Introduction to Algorithms and Programming 2.

Next week we'll study the actual C# collection class hierarchy, which is broadly similar to this picture. One important difference is that the C# collection classes are generic, as we will learn in the next lecture.