The Halting Problem

Is it possible to write a program A that takes another program B as input and which determines if B will halt or loop forever?

Well it turns out that an assumption that the answer is “yes” leads to a paradox and hence there is a proof by contradiction that the correct answer must be “no”.

The proof goes like this:

Assume program A can determine if program B will halt or loop forever.

Now I write a program C that calls program A as follows:

B = input_program
if A says B will halt then
   loop forever
else
   stop
end if

And I now feed program C to itself as input.

The result is that if C will halt, then it will loop forever, but if it will loop forever, then it will halt.

Disassembling C code to see the assembly language

We’ve been talking about assembly language in class recently and I’ve found a nice way of comparing source code with the assembly that the compile outputs. This is C, a compiled language.

int main() {
  divmod(26, 5);
}

int divmod (int dividend, int divisor) {
  int quotient = 0;
  while (dividend - divisor >= 0) {
    dividend = dividend - divisor;
    quotient = quotient + 1;
  }
}

The code divides 26 by 5 to give a quotient of 5 and remainder of 1, which is left stored in the dividend variable.

(This file was saved as divmod.c and then compiled using gcc, which is probably already installed on Mac computers. If you’re on Windows, you are advised to install the Community Edition of Microsoft Visual C++.)

Now, using a utility called objdump, which is preinstalled on my Linux laptop, I can now output the assembly code that was generated by the compiler. The output file of the compiler is called a.out, so that is the input to objdump. The flags tell objdump to include the source code intermixed with the assembly code, which is very handy for us!

The command to disassemble the compiled code is:

objdump -Sd --dwarf=info a.out

This provides a whole load of output, but in amongst it you can find the assembly code for the divmod function:

objdump output

Ordered Array Class

Arrays are static data structures, so their size is fixed when they are created. Array elements are contiguous in RAM. This means that if you want to slot a value into the middle of an array, you need to shift the other values first. Imagine trying to slot yourself in between two people in a crowded cinema.

2018-09-19_06-43

A good exercise is to code an OrderedArray class. This is a wrapper for an array of Integer object (use Integers not ints so that we can check for nulls) that has an insert method that slots new values in ascending order.

I would say that the complexity of this code is about as tough as it gets at SL. If you need some scaffolding, use the class template below. Otherwise just have a go at it yourself. In addition, code a constructor that allows you to set the size of the array.

class Main {
  // This main class is just for testing.
  public static void main(String[] args) {
    OrderedArray oArr = new OrderedArray(50);
    for (int i = 0; i < 30; i++) {
      java.util.Random r = new java.util.Random();
      oArr.insert(r.nextInt(100));
    }
    // You will need to code this method.
    // The numbers should be in order.
    oArr.print();
  }  
}

class OrderedArray {

  // What instance variables will you need?

  public OrderedArray(int size) {
  // Use the size parameter to set the size of the array.
  }

  void insert(int n) {
  // Insert the new number in the right place.
  // 1. Find out where it should go.
  // 2. Make room for it.
  }

  void print() {
  // Print the numbers to the console.
  }
}

 

Interfaces and functional interfaces

Java interfaces are not in the IB syllabus, but if you want to call yourself a higher level computer scientist you should at least have some idea about them.

An interface is like a class but it doesn’t have code in its methods. What is the point of that? Well imagine that I am on your team of programmers and you want me to do some coding for you. By creating an interface, you can specify what methods my classes should have, without actually coding them. This means you can go ahead and write code that calls those methods before I have even written them, and therefore we can both be programming at the same time, taking advantage of concurrency.

Some well-known Java interfaces are Serializable, Iterable and Comparable. Here I define an interface called Flickable. In order for a class to be Flickable, it should have a flick() method:

public class FunctionalInterfaceDemo {

    public static void main(String[] args) {
        Switch s = new Switch();
        s.flick();
        
        Flickable f = new Flickable () {
            public void flick() {
                System.out.println("Anonymous inner flickable class flicked.");
            }
        };
        f.flick();
    }
}

class Switch implements Flickable {
    // This class MUST implement a flick() method, otherwise
    // the code will not compile.
    public void flick() {
        System.out.println("Switch flicked.");
    }
}

interface Flickable {
    // This states that if you want to call yourself flickable,
    // you have to implement a flick() method.
    void flick();
}

This is a powerful aid to object-oriented programming because you can anticipate the behaviour of classes that claim to implement an interface safe in the knowledge that if they don’t implement the interface the compiler will already have detected the problem.

But there is a different problem. Suppose now I make a change to my Flickable interface and add a line void unflick();. I have now moved the goalposts and said that any class that claims to be flickable must implement not only a flick() method but an unflick() method. The upshot is that all code that implements the flickable interface is now broken and will no longer compile!

From Java 8 onwards, you can declare an interface to be a functional interface. The reason for this is well beyond the scope of this post, but has to do with Java’s push to incorporate more practices from a programming paradigm called functional programming. The good news is that with the @FunctionalInterface compile directive, we can tell the compiler that our interface cannot have more than one method. This substantially reduces the possibility of breaking code by making a change to an interface, because the compiler will prevent it.

interface Flickable {
    // This states that if you want to call yourself flickable,
    // you have to implement a flick() method.
    void flick();

    // If you uncomment the next line you will break
    // break all classes that implement Flickable:    

    // void otherMethod(); 
}

@FunctionalInterface
interface Proddable {
    void prod();

    // If you uncomment the next line you will get a
    // compile error. You can't have more than one method 
    // in a functional interface.
    
    // void otherMethod(); 
}

Referential versus structural equality

This came up in class the other day.

Expressions involving the comparison operator (==) and two object references return true if the operands point to the same object. If you want to make a more meaningful comparison you have to override the equals method that all objects inherit from java.lang.Object.

See the Java code below to see how to override the equals method.

ref

public class EqualityDemo {

    public static void main(String[] args) {
        Student s = new Student("Fred", 123);
        Student t = s;
        Student u = new Student("Fred", 123);
        System.out.println(s==t);
        System.out.println(s==u);
        System.out.println(s.equals(u));
    }
}

class Student {

    String name;
    int id;

    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }   

    @Override
    public boolean equals(Object object) {
        Student student = (Student)object;
        return this.id == student.id && this.name.equalsIgnoreCase(student.name);
    }
}
Output:
true
false
true