Lab 06 | NPRG035

Information below is not for the current semester. The current semester can be found here.

Part 1: Review of Virtual Methods

Recall from the lecture the critical difference between virtual, override, and new, and how they relate to the Virtual Method Table (VMT).

virtual: Used in a base class, this creates a new slot in the VMT for this method, storing a pointer to its implementation.
override: Used in a derived class, this replaces the pointer in an existing VMT slot inherited from the base class. It points to the new, overriding implementation.

This is captured by this simple example:

public class A {
    // Creates VMT[0] pointing to A.M implementation
    public virtual void M() { Console.WriteLine("A.M"); }
}

public class B : A {
    // Replaces VMT[0] to point to B.M implementation
    public override void M() { Console.WriteLine("B.M"); }
}

// Application
A myVar = new B();
myVar.M(); // Output: B.M

The compiler sees myVar is type A and M() is virtual, so it generates a virtual call (dynamic dispatch). At runtime, the system looks at the actual instance (which is B), finds its VMT, and calls the method implementation at slot [0], which B has replaced.

Note: We know that class A actually means class A : System.Object or class A : object (using C# shortcut for System.Object type) - and there are several virtual methods defined in System.Object - e.g. ToString() method. So if there are N virtual methods defined in System.Object in reality the A.M method will use slot N, and not slot 0 of A and B VMTs. For sake of simplicity, let’s ignore the System.Object methods for the rest of this document, and assume A.M occupies slot 0 in VMT as stated above.

Question 1

What would happen if you created a class C : B but used the new keyword instead of override?

public class C : B {
    public new void M() { Console.WriteLine("C.M"); }
}

An then run the following:

A myVar = new C();
myVar.M();

What would be printed to the console, and why? Solution

Part 2: Abstract Methods and `null` Slots

We can extend this VMT concept to understand abstract.

abstract: This keyword also creates a new VMT slot, just like virtual. However, the pointer in this slot is set to null.

If you have class C with abstract void F(), the VMT entry for F() is null.

If you could create an instance (new C()) and call myInstance.F(), the runtime would try to follow this null pointer, resulting in a NullReferenceException. But this is very unwanted behavior as the check would be done at runtime only - in a statically typed language like C# we want to enforce such check at compile-time. To prevent the problem, we need to enforce the C# compiler into forbidding you from instantiating any class that has null entries in its VMT by mistake.

Question 2

How can we enforce the highlighted behavior for such class? Solution

Question 3

Given this, why does the compiler force a class D that inherits from C (but does not override F()) to also be marked abstract?

I.e. why following does not compile?

public class D : C {
}

Solution

Part 3: The Adapter Design Pattern

Now, let’s apply these ideas to our project.

The Problem: You have a new, refactored system. The old, working, and fully-tested WordCounter class implements the IWordProcessor interface. Your new infrastructure, however, expects classes that implement ITokenProcessor.

// Old and tested:
public class WordCounter : IWordProcessor
{
    public void ProcessWord(string word) { /* ... */ }
}

// New infrastructure expects:
public interface ITokenProcessor
{
    void ProcessToken(Token t);
}

We do not want to rewrite WordCounter. It’s tested and it works. We would have to rewrite all its tests, introducing the risk of new bugs.

Question 4

How can we make our old WordCounter (which expects simple strings) compatible with the new system that sends complex Token objects, without modifying WordCounter itself?

Hint, Solution

Part 4: Test-Driven Development (TDD)

Test-Driven Development (TDD) reverses the order in which we have written code so far. In TDD, you write tests first without thinking about the implementation. Then, you provide the implementation and check that it passes each test, one by one.

The TDD Cycle:

Write a test according to the specification. It will fail to compile or run because the code doesn’t exist yet.
Write the absolute minimum amount of code required to make that test compile (e.g., creating the function signature). Don’t add features; don’t clean it up. Just make it compile. The test will now run, but it will fail.
Now, write the code to implement feature by feature and make the tests pass. You can rest assured that if you mess up or break any already-functioning code, the test you wrote will catch the error.

This forces you to think about the specification (“what” the code should do) before the implementation (“how” it should do it).

Question 5

How to approach the unit testing homework from last time effectively? Let’s say, you decide to try using ChatGPT to write your tests for the (buggy) ParagraphDetectingTokenReaderDecorator. You give the AI your implementation and say, “Write all unit tests for this.”

The AI generates 10 tests. 9 pass, but 1 fails. You think, “Great! The AI found a bug!”

…Or did it? What is the fundamental flaw in this approach? Solution

Part 5: New Assignment (Benchmarking)

Your new homework is to investigate performance. You will use the Benchmark.NET framework (that you know from the lecture) to measure the speed of different approaches.

You have two tasks.

Task 1: Dictionary Update Strategies

Compare the performance of three strategies for incrementing a word’s count in a regular Dictionary<string, int>.

Try/Catch: Access the index dict[word]++ and wrap it in a try ... catch (KeyNotFoundException) block to add the new word.
ContainsKey: Use if (dict.ContainsKey(word)) to check, then either update dict[word]++ or dict.Add(word, 1).
TryGetValue: Use dict.TryGetValue(word, out count), then set dict[word] = count + 1.

Task 2: Word Frequency Data Structures

Compare the performance of three different strategies for implementing a WordFrequencyCounter : IWordProcessor, which requires the output to be printed in sorted form:

SortedList<string, int>
SortedDictionary<string, int>
Dictionary<string, int> (and then sorting the result after all words are counted).

What you submit

The code is not the only important part of this assignment, the analysis of the results is as important!

You must submit:

Your Benchmark.NET code.
The results from running the benchmarks.
A written explanation in your code’s comments that answers:
- Which approach was fastest for each task?
- Why do you think you got those results? (e.g., consider the cost of exceptions, the cost of multiple lookups, the cost of sorting, etc.)
- Which solution would you choose based on this data?

We need a different pattern: the Adapter Pattern.

An Adapter’s job is to “adapt” one interface to another, acting as a translator. We will create a new class: TokenProcessorFromWordProcessorAdapter.

It implements the new interface (ITokenProcessor).
It wraps (holds a private instance of) the old interface (IWordProcessor).
Its ProcessToken method performs the translation:

public class TokenProcessorFromWordProcessorAdapter : ITokenProcessor
{
    private readonly IWordProcessor _wordProcessor;

    // Implementation of the ITokenProcessor interface
    // ...
}

Now we can plug our old code into the new system:

IWordProcessor oldCounter = new WordCounter();
ITokenProcessor adapter = new TokenProcessorFromWordProcessorAdapter(oldCounter);

The new infrastructure can now use the old code.