Skip to content

DA6. Generics and Open Recursion

Question 1

Conduct an internet search and library research of the concept ‘Generics’ or ‘Generic Programming’ and report your findings as the response to this discussion question. As part of your response you must define what generics are, why it they are important in OOP and you must provide examples of generics used within an object oriented program.

Generics are a form of polymorphism, where a parametrized type of subprogram is used to create several instances of the program, an instance per possible type. If the type is known at compile time, it will be a static polymorphism, otherwise it will be a dynamic polymorphism (Ben-Ari, 2006).

Generics are most useful for data structures or other general purpose functionality in your program that may deal with different types of data; such Lists, Arrays, Trees, etc. (Ben-Ari, 2006). Generics promotes Reusability, Writablity, Maintainability (UoPeople, 2023).

Let’s take a look at the following example (in typescript):

class List<T> {
    private items: T[] = [];

    constructor(sortFn: (a: T, b: T) => number) {
        this.sort = sortFn;
    }

    public add(item: T): void {
        this.items.push(item);
    }

    public get(index: number): T {
        return this.items[index];
    }

    public sort: (a: T, b: T) => number;
}

type Person = {
    name: string;
    age: number;
};

const integerList = new List<number>((a, b) => a - b);
const stringList = new List<string>((a, b) => a.localeCompare(b));
const personList = new List<Person>((a, b) => a.age - b.age);
  • We notice the list is defined with a generic type T which is used to create different instances of the list for different types.
  • Our program can create a list of integers, strings, or persons, that is, three different lists, each with its own type, and our supplied sort function must be different for each type.
  • Instead of creating three different classes, we can create one generic class that can be instantiated for different types which promotes reusability.
  • To fix a problem in our list, we only need to fix it in one place, and it will be fixed for all types, which promotes maintainability.
  • The code size is very small compared to the three different classes, which promotes writablity.

Question 2

Conduct an internet search and library research of the concept ‘Open Recursion’ and report your findings as the response to this discussion question. As part of your response you must define what it is, why it is important in OOP and you must provide examples of how it can be used with an object oriented program.

The topic of open recursion is not covered in the lecture notes, and I faced hard time understanding it. I will collect some information from various sources and I will explain my findings at the end:

  • “Writing a code in the superclass that calls code in the subclass(es), wether it is overridden or not. The subclasses are defined and called after the superclass” (Turk, 2020).
  • “To enable open recursion, the call-graph of the method functions cannot be hard-wired, but needs to be implemented indirectly, via object self-reference. . Object self-reference can be achieved either by construction, making each object a recursive, self-referential value (the fixed-point model), or dynamically, by passing the object as an extra argument on each method call (the self-application or self-passing model).In either case, we will call these self-referential objects”. (MacQueen, 2002).
  • “Often the old (inherited) methods remain accessible through a special variable (typically super) even when overridden. Method overrides can rearrange the call-graph among the methods, affecting not only new methods, but the old, inherited methods as well. This effect is called open recursion” (MacQueen, 2002).
  • “So by “recursion” here, what he means is method definitions are mutually recursive so that they can see each other’s names. It doesn’t mean that they actually have to call each other at runtime and be recursive. Just that their names are in scope so that they could do that”.

Open Recursion

Inheritance is an important part of the object oriented paradigm. One of its features allows subclasses to override methods of the super class; but what if the class itself wants to call one of its own methods that may have been overridden by a subclass?.

In this case, the superclass needs to be open for extension, and recursively checks its subclasses for the method definition. But the super class is defined in the source code before the subclasses, so how can it call a method that is defined after it?. The solution is late-binding, thus the method is not bound until later in the compilation process where the subclasses are defined.

So According to (MacQueen, 2002), (Turk, 2020), and (Nystrom, 2013), open recursion is the ability of a superclass (or subclass) to call a method that may have been changed (overridden) and the caller must look for the latest definition of the method and/or recursively call different definitions of the method in classes through the inheritance hierarchy; plus the ability to call a method that is defined before or after the code that calls it without worrying that that method may be changed or undefined.

let’s take a look at the following example (in typescript):

class Parent {
    public sayHello(): void {
        console.log("Hello from Parent");
    }

    function callSayHello(): void {
        this.sayHello();
    }
}

class Child extends Parent {
    public sayHello(): void {
        super.sayHello();
        console.log("Hello from Child");
    }
}

const c = new Child(); // Hello from Parent, Hello from Child
c.callSayHello(); // Hello from Parent, Hello from Child
  • The child was able to call the parent’s method sayHello() even though it was overridden using the super keyword which recursively climbs up the inheritance hierarchy to find the method.
  • Also, The parent was able to call the child’s method sayHello() even though it was defined after the parent’s method callSayHello() where the parent was open to accept that the child will override the method, and recursively falls down the inheritance hierarchy to find the latest definition of the method.

References