Complexity: The Enemy

When building large programs, our enemy is complexity.

Some tools for managing complexity:

  • Hierarchical abstraction.
    • Create layers of abstraction, with clear abstraction barriers!
  • “Design for change” (D. Parnas)
    • Organize program around objects.
    • Let objects decide how things are done.
    • Hide information others don’t need.

As the user of an ArrayDeque, you cannot observe its internals.

  • Even when writing tests, you don’t (usually) want to peer inside.

Java is a great language for enforcing abstraction barriers with syntax.

A module is said to be encapsulated if its implementation is completely hidden, and it can be accessed only through a documented interface.

  • Instance variables private. Methods like resize private.
  • As we’ll see: Implementation inheritance (e.g. extends) breaks encapsulation!

Suppose we have a Dog class with the two methods shown.

1
2
3
4
5
6
7
8
9
public void bark() {
   System.out.println("bark");
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        bark();  
    }
}

We could just as easily have implemented methods as shown below.

  • From the outside, functionality is exactly the same, it’s just a question of aesthetics.
1
2
3
4
5
6
7
8
9
public void bark() {
   barkMany(1);
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        System.out.println("bark");  
    }
}

Higher Order Functions

Higher Order Function: A function that treats another function as data.

Example in Python:

1
2
3
4
5
6
7
def tenX(x):
    return 10*x

def do_twice(f, x):
    return f(f(x))

print(do_twice(tenX, 2))

Old School (Java 7 and earlier)

  • Fundamental issue: Memory boxes (variables) cannot contain pointers to functions.

Can use an interface instead: Java code below is equivalent to given python code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public interface IntUnaryFunction {
    int apply(int x);
}

public class TenX implements IntUnaryFunction {
    public int apply(int x) {
        return 10 * x;
    }
}

public class HoFDemo {
    public static int do_twice(IntUnaryFunction f, int x) {
        return f.apply(f.apply(x));
    }
    public static void main(String[] args) {
        System.out.println(do_twice(new TenX(), 2));
    }
}

In Java 8, new types were introduced: now can hold references to methods.

  • You’re welcome to use these features, but we won’t teach them.
  • Why? The old way is still widely used, e.g. Comparators (see next lecture).
1
2
3
4
5
6
7
8
9
10
11
12
public class Java8HoFDemo {
    public static int tenX(int x) {
        return 10*x;
    }
    public static int doTwice(Function<Integer, Integer> f, int x) {
        return f.apply(f.apply(x));
    }
    public static void main(String[] args) {
        int result = doTwice(Java8HoFDemo::tenX, 2);
        System.out.println(result);
    }
}

Implementation Inheritance Cheatsheet

VengefulSLList extends SLList means a VenglefulSLList is-an SLList. Inherits all members!

  • Variables, methods, nested classes.
  • Not constructors.
  • Subclass constructor must invoke superclass constructor first.
  • Use super to invoke overridden superclass methods and constructors.

Invocation of overridden methods follows two simple rules:

  • Compiler plays it safe and only lets us do things allowed by static type.
  • Compiler chooses 2
  • For overridden methods the actual method invoked is based on dynamic type of invoking expression, e.g. Dog.maxDog(d1, d2).bark(); Does not apply to overloaded methods!
  • Can use casting to overrule compiler type checking.