Introduction

This book is a collection of all my notes from my degree (computer systems engineering).

It exists for a few purposes:

  • To consolidate knowledge
  • To aid revision
  • To act as a reference during exams

Contributing

If you wish to contribute to this, either to make any additions or just to fix any mistakes I've made, feel free.

The sources are all available on my Github.

CS118

This section is mainly just a reference of some of the more detailed bits of the module. It assumes a pretty strong prior knowledge of object oriented programming so doesn't aim to be comprehensive, it just specifies some details to remember for the exam.

The version of Java on DCS systems at the time of writing is 11. This is also the version these notes refer to.

Useful Resources

  • https://en.wikipedia.org/wiki/Single-precision_floating-point_format
  • The Oracle documentation for specifics on how Java implements stuff

IEEE 754

IEEE 754 is a standardised way of storing floating point numbers with three components

  • A sign bit
  • A biased exponent
  • A normalised mantissa
TypeSignExponentMantissaBias
Single Precision (32 bit)1 (bit 31)8 (bit 30 - 23)23 (bit 22- 0)127
Double Precision (64 bit)1 (bit 63)11 (bit 62 - 52)52 (51 - 0)1023

The examples below all refer to 32 bit numbers, but the principles apply to 64 bit.

  • The exponent is an 8 bit unsigned number in biased form
    • To get the true exponent, subtract 127 from the binary value
  • The mantissa is a binary fraction, with the first bit representing , second bit , etc.
    • The mantissa has an implicit , so 1 must always be added to the mantissa

Formula

Decimal to Float

The number is converted to a binary fractional format, then adjusted to fit into the form we need. Take 12.375 for example:

  • Integer part
  • Fraction part

Combining the two parts yields . However, the standard requires that the mantissa have an implicit 1, so it must be shifted to the right until the number is normalised (ie has only 1 as an integer part). This yields . As this has been shifted, it is actually . The three is therefore the exponent, but this has to be normalised (+127) to yield 130 . The number is positive (sign bit zero) so this yields:

SignBiased ExponentNormalised Mantissa
01000 0010100011

Float to Decimal

Starting with the value 0x41C80000 = 01000001110010000000000000000000:

SignBiased ExponentNormalised Mantissa
01000 00111001
  • The exponent is 131, biasing (-127) gives 4
  • The mantissa is 0.5625, adding 1 (normalising) gives 1.5625
  • gives 25

Special Values

  • Zero
    • When both exponent and mantissa are zero, the number is zero
    • Can have both positive and negative zero
  • Infinity
    • Exponent is all 1s, mantissa is zero
    • Can be either positive or negative
  • Denormalised
    • If the exponent is all zeros but the mantissa is non-zero, then the value is a denormalised number
    • The mantissa does not have an assumed leading one
  • NaN (Not a Number)
    • Exponent is all 1s, mantissa is non-zero
    • Represents error values
ExponentMantissaValue
00
2550
0not 0denormalised
255not 0NaN

OOP Principles

Constructors

All Java classes have a constructor, which is the method called upon object instantiation.

  • An object can have multiple overloaded constructors
  • A constructor can have any access modifier
  • Constructors can call other constructors through the this() method.
  • If no constructor is specified, a default constructor is generated which takes no arguments and does nothing.
  • The first call in any constructor is to the superclass constructor.
    • This can be elided, and the default constructor is called
      • If there is no default constructor, a constructor must be called explicitly
    • Can call explicitly with super()

Access Modifiers

Access modifiers apply to methods and member variables.

  • private: only the members of the class can see
  • public: anyone can see
  • protected: only class and subclasses can see
  • Default: package-private, only members of the same package can see

Inheritance

  • To avoid the diamond/multiple inheritance problem, Java only allows for single inheritance
  • This is done using the extends keyword in the class definition
  • Inherits all public and protected methods and members
  • Can, however, implement multiple interfaces

Example:

public class Car extends Vehicle implements Drivable, Crashable{
    // insert class body here
}

The Car class extends the Vehicle base class (can be abstract or concrete) and implements the behaviours defined by the interfaces Drivable and Crashable.

static

The static keyword defines a method, a field, or a block of code that belongs to the class instead of the object.

  • Static fields share a mutable state accross all instances of the class
  • Static methods are called from the class instead of from the object
  • Static blocks are executed once, the first time the class is loaded into memory

Polymorphism

Polymorphism: of many forms. A broad term describing a few things in java.

Dynamic Polymorphism

An object is defined as polymorphic if it passes more than one instanceof checks. An object can be referred to as the type of any one of it's superclasses. Say for example there is a Tiger class, which subclasses Cat, which subclasses Animal, giving an inheritance chain of Animal <- Cat <- Tiger, then the following is valid:

Animal a = new Tiger();
Cat c = new Tiger();
Tiger t = new Tiger();

When referencing an object through one of it's superclass types, you can only call objects that the reference type implements. For example, if there was two methods, Cat::meow and Tiger::roar, then:

c.meow() //valid
t.meow() //valid
a.meow() //not valid - animal has no method meow
t.roar() //valid
c.roar() // not valid - cat has no method roar

Even though all these variables are of the same runtime type, they are being called from a reference of another type.

When calling a method of an object, the actual method run is the one that is furthest down the inheritance chain. This is dynamic/runtime dispatch.

public class Animal{
    public speak(){return "...";}
}

public class Dog extends Animal{
    public speak(){return "woof";}
}

public class Cat extends Animal{
    public speak(){return "meow";}
}

Animal a = new Animal();
Animal d = new Dog();
Animal c = new Cat();

a.speak() // "..."
d.speak() // "woof"
c.speak() // "meow"

Even though the reference was of type Animal, the actual method called was the overridden subclass method.

Static Polymorphism (Method Overloading)

Note: different to overridding

  • Multiple methods with the same name can be written, as long as they have different parameter lists
  • The method that is called depends upon the number of and type of the arguments passed

Example:

public class Addition{
    private int add(int x, int y){return x+y;}
    private float add(float x, float y){return x+y;}
    public static void main(String[] args){
        add(1,2); //calls first method
        add(3.14,2.72); //calls second method
        add(15,1.5); //calls second method
    }
}

Abstraction

Abstraction is the process of removing irrelevant details from the user, while exposing the relevant details. For example, you don't need to know how a function works, it's inner workings are abstracted away, leaving only the function's interface and details of what it does.

In the example below, the workings of the sine function are abstracted away, but we still know what it does and how to use it.

float sin(float x){
    //dont care really
}
sin(90); // 1.0

Encapsulation

Encapsulation is wrapping the data and the code that acts on it into a single unit. The process is also known as data hiding, because the data is often hidden (declared private) behind the methods that retrieve them (getters/setters).

Reference Variables

There is no such thing as an object variable in Java. Only primitives (int,char,float...), and references. All objects are heap-allocated (new), and a reference to them stored. Methods are all pass by value: either the value of the primitive, or the value of the reference. Java is not pass by reference . Objects are never copied/cloned/duplicated implicitly.

If a reference type is required (ie Integer), but a primitive is given ((int) 1), then the primitive will be autoboxed into it's equivalent object type.

Abstract Classes and Interfaces

  • Abstract classes are classes that contain one or more abstract methods.
    • A class must be declared abstract
    • Abstract methods have no body, ie are unimplemented.
    • The idea of them is to generalise behaviour, and leave it up to subclasses to implement
    • Abstract classes cannot be instantiated directly, though can still have constructors for subclasses to call
  • Interfaces are a special kind of class that contain only abstract methods (and fields declared public static final)
    • Used to define behaviour
    • Technically can contain methods, but they're default implementations
      • This raises all sorts of issues so is best avoided
    • Don't have to declare methods abstract, it's implicit

The diagram shows the inheritance hierarchy of the java collections framework, containing interfaces, abstract classes, and concrete classes.

Exceptions

Exceptions

Exceptions are events that occur within the normal flow of program execution that disrupt the normal flow of control.

Throwing Exceptions

Exceptions can occur when raised by other code we call, but an exception can also be raised manually using a throw statement. Any object that inherits, either directly or indirectly, from the Throwable class, can be raised as an exception.

//pop from a stack
public E pop(){
    if(this.size == 0)
        throw new EmptyStackException();
    //pop the item
}

Exception Handling

  • Exceptions can be caught using a try-catch block
  • If any code within the try block raises an exception, the catch block will be executed
    • catch blocks must specify the type of exception to catch
    • Can have multiple catch blocks for different exceptions
      • Only 1 catch block will be executed
  • A finally block can be included to add any code to execute after the try-catch, regardless of if an exception is raised or not.
  • The exception object can be queried through the variable e
try{
    //try to do something
} catch (ExceptionA e){
    //if an exception of type ExceptionA is thrown, this is executed
} catch (ExceptionB e){
    //if an exception of type ExceptionB is thrown, this is executed
} finally{
    //this is always executed
}

Exception Heirachy

  • The Throwable class is the parent class of all errors and exceptions in Java
  • There are two subclasses of Throwable
    • Error, which defines hard errors within the JVM that aren't really recoverable
    • Exception, which defines errors that may occur within the code
      • There are two kinds of exception, checked and unchecked

Checked and Unchecked Exceptions

  • Checked exceptions must be either caught or re-thrown
    • IOException is a good example
  • When a method that may throw a checked exception is required, there are two options
    • Wrap the possibly exception-raising code in a try-catch
    • Use the throws keyword in the method definition to indicate that the method may throw a checked exception
public static void ReadFile() throws FileNotFoundException{
    File f = new File("non-existant-file.txt")
    FileInputStream stream = new FileInputStream(f);
}
// OR
public static void ReadFile(){
    File f = new File("non-existant-file.txt")
    try{
        FileInputStream stream = new FileInputStream(f);
    } catch (FileNotFoundException){
        e.printStackTrace();
        return;
    }
}
  • Unchecked Exceptions all subclass RunTimeException
    • ie NullPointerException and ArrayIndexOutOfBoundsException
  • Can be thrown at any point and will cause program to exit if not caught

Custom Exceptions

  • Custom exception classes can be created
  • Should subclass Throwable
    • Ideally the most specific subclass possible
    • Subclassing Exception gives a new checked exception
    • Subclassing RunTimeException gives a new unchecked exception
  • All methods such as printStackTrace and getMessage inherited from superclass
  • Should provide at least one constructor that overrides a superclass constructor
public class IncorrectFileExtensionException
  extends RuntimeException {
    public IncorrectFileExtensionException(String errorMessage, Throwable err) {
        super(errorMessage, err);
    }
}

Generics

Generics allow for classes to be parametrised over some type or types, to provide additional compile time static type checking. A simple box class parametrised over some type E, for example:

public class Box<E>{
    E item;

    public Box(E item){
        this.item = item;
    }
    public E get(){
        return item;
    }
    public E set(E item){
        this.item = item;
    }
}

Generic Methods

Methods can be generic too, introducing their own type parameters. The parameters introduced in methods are local to that method, not the whole class. As an example, the static method below compares two Pair<K,V> classes to see if they are equal.

public static <K, V> boolean compare(Pair<K, V> p1, Pair<K, V> p2) {
        return p1.getKey().equals(p2.getKey()) &&
               p1.getValue().equals(p2.getValue());
    }

Type erasure

Type information in generic classes and methods is erased at runtime, with the compiler replacing all instances of the type variable with Object. Object is also what appears in the compiled bytecode. This means that at runtime, any type casting of generic types is unchecked, and can cause runtime exceptions.

CS126

The book Data Structures and Algorithms in Java by Goodrich, Tamassia and Goldwasser is a good resource as it aligns closely with the material. It can be found online fairly easily.

Arrays & Linked Lists

Arrays

Arrays are the most common data structure and are very versatile

  • A sequenced collection of variables of the same type (homogenous)
  • Each cell in the array has an index
  • Arrays are of fixed length and so have a max capacity
  • Can store primitives, or references to objects
  • When inserting an element into the array, all to the right must be shifted up by one
  • The same applies in reverse for removal to prevent null/0 gaps being left

Sorting Arrays

  • The sorting problem:
    • Consider an array of unordered elements
    • We want to put them in a defined order
    • For example [3, 6, 2, 7, 8, 10, 22, 9] needs to become [2, 3, 6, 7, 8, 9, 10, 22]
  • One possible solution: insertion sort:
    • Go over the entire array, inserting each element at it's proper location by shifting elements along
public static void insertionSort(int[] data){
    int n = data.length;
    for(int k = 1; k < n; k++){             //start with second element
        int cur = data[k];                  //insert data[k]
        int j = k;                          //get correct index j for cur
        while(j < 0 && data[j-1] > cur){    //data[j-1] must go after cur
            data[j] = data[j-1];            // slide data[j-1] to the right
            j--;                            //consider previous j for cur
        }
        data[j] = cur; //cur is in the right place
    }
}
  • Insertion sort sucks
  • Has worst case quadratic complexity, as k comparisons are required for k iterations.
  • When the list is in reverse order (worst case), comparisons are made
  • Can do much better with alternative algorithms

Singly Linked Lists

  • Linked lists is a concrete data structure consisting of a chain of nodes which point to each other
  • Each node stores the element, and the location of the next node
  • The data structure stores the head element and traverses the list by following the chain
  • Operations on the head of the list (ie, prepending) are efficient, as the head node can be accessed via its pointer
  • Operations on the tail require first traversing the entire list, so are slow
  • Useful when data needs to always be accessed sequentially
  • Generally, linked lists suck for literally every other reason

Doubly Linked Lists

  • In a doubly linked list, each node stores a pointer to the node in front of and behind it
  • This allows the list to be traversed in both directions, and for nodes to be easily inserted mid-sequence
  • Sometimes, special header and trailer "sentinel" nodes are added to maintain a reference to the head an tail of the list
    • Also removes edge cases when inserting/deleting nodes as there is always nodes before/after head and tail

Analysis of Algorithms

This topic is key to literally every other one, and also seems to make up 90% of the exam questions (despite there being only 1 lecture on it) so it's very important.

  • Need some way to characterise how good a data structure or algorithm is
  • Most algorithms take input and generate output
  • The run time of an algorithm typically grows with input size
  • Average case is often difficult to determine
    • Focus on the worst case
  • Runtime analysis and benchmarks can be used to determine the performance of an algorithm, but this is often not possible
    • Results will also vary from machine to machine
  • Theoretical analysis is preferred as it gives a more high-level analysis
    • Characterises runtime as a function of input size

Pseudocode

  • Pseudocode is a high level description of an algorithm
  • Primitive perations are assumed to take unit time
  • For example
    • Evaluating an expression
    • Assigning to a variable
    • Indexing into an array
    • Calling a method

Looking at an algorithm, can count the number of operations in each step to analyse its runtime

public static double arrayMax(double[] data){
    int n = data.length; //2 ops
    double max = data[0]; //2 ops
    for (int j=1; j < n;j++) //2n ops
        if(data[j] > max) //2n-2 ops
            max = data[j]; //0 to 2n-2 ops
    return max; //1 op
}
  • In the best case, there are primitive operations
  • In the worst case,
  • The runtime is therefore
    • is the time to execute a primitive operation

Functions

There are 7 important functions that appear often when analysing algorithms

  • Constant -
    • A fixed constant
    • Could be any number but 1 is the most fundamental constant
    • Sometimes denoted where
  • Logarithmic -
    • For some constant ,
    • Logarithm is the inverse of the power function
    • Usually, because we are computer scientists and everything is base 2
  • Linear -
      • is a fixed constant
  • n-log-n -
    • Commonly appears with sorting algorithms
  • Quadratic -
    • Commonly appears where there are nested loops
  • Cubic -
    • Less common, also appears where there are 3 nested loops
    • Can be generalised to other polynomial functions
  • Exponential -
      • is some arbitrary base, is the exponent

The growth rate of these functions is not affected by changing the hardware/software environment. Growth rate is also not affected by lower-order terms.

  • Insertion sort takes time
    • Characterised as taking time
  • Merge sort takes
    • Characterised as
  • The arrayMax example from earlier took time
    • Characterised as
  • A polynomial of degree , is of order

Big-O Notation

  • Big-O notation is used to formalise the growth rate of functions, and hence describe the runtime of algorithms.
  • Gives an upper bound on the growth rate of a function as
  • The statement " is " means that the growth rate of is no more than the growth rate of
  • If is a polynomial of degree , then is
    • Drop lower order terms
    • Drop constant factors
  • Always use the smallest possible class of functions
    • is , not
  • Always use the simplest expression
    • is , not

Formally, given functions and , we say that is if there is a positive constant and a positive integer constant , such that

where , and

Examples

is :

The function is not The inequality does not hold, since must be constant.

Big-O of :

Big-O of :

is

Asymptotic Analysis

  • The asymptotic analysis of an algorithm determines the running time big-O notation
  • To perform asymptotic analysis:
    • Find the worst-case number of primitive operations in the function
    • Express the function with big-O notation
  • Since constant factors and lower-order terms are dropped, can disregard them when counting primitive operations

Example

The th prefix average of an array is the average of the first elements of . Two algorithms shown below are used to calculate the prefix average of an array.

Quadratic time

//returns an array where a[i] is the average of x[0]...x[i]
public static double[] prefixAverage(double[] x){
    int n = x.length;
    double[] a = new double[n];
    for(int j = 0; j < n; j++){
        double total = 0;
        for(int i = 0; i <= j; i++)
            total += x[i];
        a[j] = total / (j+1);
    }
    return a;
}

The runtime of this function is . The sum of the first integers is , so this algorithm runs in quadratic time. This can easily be seen by the nested loops in the function too.

Linear time

//returns an array where a[i] is the average of x[0]...x[i]
public static double[] prefixAverage(double[] x){
    int n = x.length;
    double[] a = new double[n];
    double total = 0;
    for(int i = 0; i <= n; i++){
        total += x[i];
        a[i] = total / (i+1);
    }
    return a;
}

This algorithm uses a running average to compute the same array in linear time, by calculating a running sum.

Big-Omega and Big-Theta

Big-Omega is used to describe the best case runtime for an algorithm. Formally, is if there is a constant and an integer constant such that

Big-Theta describes the average case of the runtime. is if there are constants and , and an integer constant such that

The three notations compare as follows:

  • Big-O
    • is if is asymptotically less than or equal to
  • Big-
    • is if is asymptotically greater than or equal to
  • Big-
    • is if is asymptotically equal to

Recursive Algorithms

Recursion allows a problem to be broken down into sub-problems, defining a problem in terms of itself. Recursive methods work by calling themselves. As an example, take the factorial function:

In java, this can be written:

public static int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n-1);
}

Recursive algorithms have:

  • A base case
    • This is the case where the method doesn't call itself, and the stack begins to unwind
    • Every possible chain of recursive calls must reach a base case
      • If not the method will recurse infinitely and cause an error
  • A recursive case
    • Calls the current method again
    • Should always eventually end up on a base case

Binary search is a recursively defined searching algorithm, which works by splitting an array in half at each step. Note that for binary search, the array must already be ordered.

Three cases:

  • If the target equals data[midpoint] then the target has been found
    • This is the base case
  • If the target is less than data[midpoint] then we binary search everything to the left of the midpoint
  • If the target is greater than data[midpoint] then we binary search everything to the right of the midpoint

public static boolean binarySearch(int[] data, int target, int left, int right){
    if (left > right)
        return false;
    int mid = (left + right) / 2;
    if(target == data[mid])
        return true;
    else if (target < data[mid])
        return binarySearch(data,target,low,mid-1);
    else
        return binarySearch(data,target,mid+1,high);

}

Binary search has , as the size of the data being processed halves at each recursive call. After the call, the size of the data is at most .

Linear Recursion

  • The method only makes one recursive call
  • There may be multiple possible recursive calls, but only one should ever be made (ie binary search)
  • For example, a method used in computing powers by repeated squaring:

public static int pow(int x, int n){
    if (n == 0) return 1;
    if (n % 2 == 0){
        y = pow(x,n/2);
        return x * y * y;
    }
    y = pow(x,(n-1)/2);
    return y * y;
}

Note how despite multiple cases, pow only ever calls itself once.

Binary Recursion

Binary recursive methods call themselves twice recursively. Fibonacci numbers are defined using binary recursion:

  • = 0
public static int fib(int n){
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

This method calls itself twice, which isn't very efficient. It can end up having to compute the same result many many times. A better alternative is shown below, which uses linear recursion, and is therefore much much more efficient.

public static Pair<Integer,Integer> linearFib(int n){
    if(k = 1) return new Pair(n,0);
    Pair result = linearFib(n-1);
    return new Pair(result.snd+1, result.fst);
}

Multiple Recursion

Multiple recursive algorithms call themselves recursively more than twice. These are generally very inefficient and should be avoided.

Stacks & Queues

Abstract Data Types (ADTs)

  • An ADT is an abstraction of a data structure
  • Specifies the operations performed on the data
  • Focus is on what the operation does, not how it does it
  • Expressed in java with an interface

Stacks

  • A stack is a last in, first out data structure (LIFO)
  • Items can be pushed to or popped from the top
  • Example uses include:
    • Undo sequence in a text editor
    • Chain of method calls in the JVM (method stack)
    • As auxillary storage in multiple algorithms

The Stack ADT

The main operations are push() and pop(), but others are included for usefulness

public interface Stack<E>{
    int size();
    boolean isEmpty();
    E peek(); //returns the top element without popping it
    void push(E elem); //adds elem to the top of the stack
    E pop(); //removes the top stack item and returns it
}

Example Implementation

The implementation below uses an array to implement the interface above. Only the important methods are included, the rest are omitted for brevity.

public class ArrayStack<E> implements Stack<E>{
    private E[] elems;
    private int top = -1;

    public ArrayStack(int capacity){
        elems = (E[]) new Object[capacity];
    }

    public E pop(){
        if (isEmpty()) return null;
        E t = elems[top];
        top = top-1;
        return t;
    }
    public E push(){
        if (top == elems.length-1) throw new FullStackException; //cant push to full stack
        top++;
        return elems[top];
    }
}
  • Advantages
    • Performant, uses an array so directly indexes each element
    • space and each operation runs in time
  • Disadvantages
    • Limited by array max size
    • Trying to push to full stack throws an exception

Queues

  • Queues are a first in, first out (FIFO) data structure
  • Insertions are to the rear and removals are from the front
    • In contrast to stacks which are LIFO
  • Example uses:
    • Waiting list
    • Control access to shared resources (printer queue)
    • Round Robin Scheduling
      • A CPU has limited resources for running processes simultaneously
      • Allows for sharing of resources
      • Programs wait in the queue to take turns to execute
      • When done, move to the back of the queue again

The Queue ADT

public interface Queue<E>{
    int size();
    boolean isEmpty();
    E peek();
    void enqueue(E elem); //add to rear of queue
    E dequeue(); // pop from front of queue
}

Lists

The list ADT provides general support for adding and removing elements at arbitrary positions

The List ADT

public interface List<E>{
    int size();
    boolean isEmpty();
    E get(int i); //get the item from the index i
    E set(int i, E e); //set the index i to the element e, returning what used to be at that index
    E add(int i, E e); //insert an element in the list at index i
    void remove(int i); //remove the element from index i
}

Array Based Implementation (ArrayList)

Array lists are growable implementations of the List ADT that use arrays as the backing data structure. The idea is that as more elements are added, the array resizes itself to be bigger, as needed. Using an array makes implementing get() and set() easy, as they can both just be thin wrappers around array[] syntax.

  • When inserting, room must be made for new elements by shifting other elements forward
    • Worst case (inserting to the head) runtime
  • When removing, need to shift elements backward to fill the hole
    • Same worst case as insertion,

When the array is full, we need to replace it with a larger one and copy over all the elements. When growing the array list, there are two possible strategies:

  • Incremental
    • Increase the size by a constant
  • Doubling
    • Double the size each time

These two can be compared by analysing the amortised runtime of the push operation, ie the average time required for a pushes taking a total time .

With incremental growth, over push operations, the array is replaced times, where is the constant amount the array size is increased by. The total time of push operations is proportional to:

Since is a constant, is , meaning the amortised time of a push operation is .

With doubling growth, the array is replaced times. The total time of pushes is proportional to:

Thus, is , meaning the amortised time is

Positional Lists

  • Positional lists are a general abstraction of a sequence of elements without indices
  • A position acts as a token or marker within the broader positional list
  • A position p is unaffected by changes elsewhere in a list
    • It only becomes invalid if explicitly deleted
  • A position instance is an object (ie there is some Position class)
    • ie p.getElement() returns the element stored at position p
  • A very natural way to implement a positional list is with a doubly linked list, where each node represents a position.
    • Where a pointer to a node exists, access to the previous and next node is fast ()

ADT


public interface PositionalList<E>{
    int size();
    boolean isEmpty();
    Position<E> first(); //return postition of first element
    Position<E> last();  //return position of last element
    Position<E> before(Position<E> p); //return position of element before position p
    Position<E> after(Posittion<E> p); //return position of element after position p
    void addFirst(E e); //add a new element to the front of the list
    void addLast(E e); // add a new element to the back of the list
    void addBefore(Position<E> p, E e); // add a new element just before position p
    void addAfter(Position<E> p, E e); // add a new element just after position p
    void set(Position<E> p, E e); // replaces the element at position p with element e
    E remove(p); //removes and returns the element at position p, invalidating the position
}

Iterators

Iterators are a software design pattern that abstract the process of scanning through a sequence one element at a time. A collection is Iterable if it has an iterator() method, which returns an instance of a class which implements the Iterator interface. Each call to iterator() returns a new object. The iterable interface is shown below.

public interface Iterator<E>{
    boolean hasNext(); //returns true if there is at least one additional element in the sequence
    E next(); //returns the next element in the sequence, advances the iterator by 1 position.
}
// example usage
public static void iteratorOver(Iterable<E> collection){
    Iterator<E> iter = collection.iterator();
    while(iter.hasNext()){
      E var = iter.next();
      System.out.println(var);
    }
}

Maps

  • Maps are a searchable collection of key-value entries
  • Lookup the value using the key
  • Keys are unique

The Map ADT

public interface Map<K,V>{
    int size();
    boolean isEmpty();
    V get(K key); //return the value associated with key in the map, or null if it doesn't exist
    void put(K key, V value); //associate the value with the key in the map
    void remove(K key); //remove the key and it's value from the map
    Collection<E> entrySet(); //return an iterable collection of the values in the map
    Collection<E> keySet(); //return an iterable collection of the keys in the map
    Iterator<E> values(); //return an iterator over the map's values
}

List-Based Map

A basic map can be implemented using an unsorted list.

  • get(k)
    • Does a simple linear search of the list looking for the key,value pair
    • Returns null if search reaches end of list and is unsuccessful
  • put(k,v)
    • Does linear search of the list to see if key already exists
      • If so, replace value
    • If not, just add new entry to end
  • remove(k)
    • Does a linear search of the list to find the entry and removes it
  • All operations take time so this is not very efficient

Hash Tables

  • Recall the map ADT
  • Intuitively, a map M supports the abstraction of using keys as indices such as M[k]
  • A map with n keys that are known to be integers in a fixed range is just an array
  • A hash function can map general keys (ie not integers) to corresponding indices in a table/array

Hash Functions

A hash function maps keys of a given type to integers in a fixed interval .

  • A very simple hash function is the mod function:

    • Works for integer keys
    • The integer is the hash value of the key
  • The goal of a hash function is to store an entry at index

  • Function usually has two components:

    • Hash code
      • keys -> integers
    • Compression function
      • integers -> integers in range
    • Hash code applied first, then compression - Some example hash functions:
  • Memory address

    • Use the memory address of the object as it's hash code
  • Integer cast

    • Interpret the bits of the key as an integer
    • Only suitable with 64 bits
  • Component sum

    • Partition they key into bitwise components of fixed length and sum the components
  • Polynomial accumulation

    • Partition the bits of the key into a sequence of components of fixed length , , ... ,
    • Evaluate the polynomial for some fixed value
    • Especially suitable for strings
    • Polynomial can be evaluated in time as

Some example compression functions:

  • Division
    • The size is usually chosen to be a prime to increase performance
  • Multiply, Add, and Divide (MAD)
    • and are nonnegative integers such that

Collision Handling

Collisions occur when different keys hash to the same cell. There are several strategies for resolving collisions.

Separate Chaining

With separate chaining, each cell in the map points to another map containing all the entries for that cell.

Linear Probing

  • Open addressing
    • The colliding item is placed in a different cell of the table
  • Linear probing handles collisions by placing the colliding item at the next available table cell
  • Each table cell inspected is referred to as a "probe"
  • Colliding items can lump together, causing future collisions to cause a longer sequence of probes

Consider a hash table that uses linear probing.

  • get(k)
    • Start at cell
    • Prove consecutive locations until either
      • Key is found
      • Empty cell is found
      • All cells have been unsuccessfully probed
  • To handle insertions and deletions, need to introduce a special marker object defunct which replaces deleted elements
  • remove(k)
    • Search for an entry with key k
    • If an entry (k, v) is found, replace it with defunct and return v
    • Else, return null

Double Hashing

  • Double hashing uses two hash functions h() and f()
  • If cell h(k) already occupied, tries sequentially the cell for
  • f(k) cannot return zero
  • Table size must be a prime to allow probing of all cells
  • Common choice of second hash func is where q is a prime
  • if then we have linear probing

Performance

  • In the worst case, operations on hash tables take time when the table is full and all keys collide into a single cell
  • The load factor affects the performance of a hash table
    • = number of entries
    • = number of cells
  • When is large, collision is likely
  • Assuming hash values are true random numbers, the "expected number" of probes for an insertion with open addressing is
  • However, in practice, hashing is very fast and operations have performance, provided is not close to 1

Sets

A set is an unordered collection of unique elements, typically with support for efficient membership tests

  • Like keys of a map, but with no associated value

Set ADT

Sets also provide for traditional mathematical set operations: Union, Intersection, and Subtraction/Difference.

public interface Set<E>{
    void add(E e); //add element e to set if not already present
    void remove(E e); //remove element e from set if present
    boolean contains(E e); //test if element e is in set
    Iterator<E> iterator(); //returns an iterator over the elements
    //updates the set to include all elements of set T
    // union
    void addAll(Set<E> T);
    //updates the set to include only the elements of the set that are also in T
    //intersection
    void retainAll(Set<E> T);
    //updates the set to remove any elements that are also in T
    //difference
    void removeAll(Set<E> T);
}

Generic Merging

Generic merge is a generalised merge of two sorted lists A and B to implement set operations. Uses a template method merge and 3 auxillary methods that describe what happens in each case:

  • aIsLess
    • Called when the element of A is less than the element of B
  • bIsLess
    • Called when the element of B is less than the element of A
  • bothEqual
    • Called when the element of A is equal to the element of B
public static Set<E> merge(Set<E> A, Set<E> B){
    Set<E> S = new Set<>();
    while (!A.isEmpty() && !B.isEmpty()){
        a = A.firstElement();
        b = B.firstElement();
        if(a < b){
            aIsLess(a,S);
            A.remove(a);
        }
        else if (b < a){
            bIsLess(b,S);
            B.remove(b);
        }
        else{ //b == a
            bothEqual(a,b,S);
            A.remove(a);
            B.remove(b);
        }
        while(!A.isEmpty()){
            aIsLess(a,S);
            A.remove(a);
        }
        while(!B.isEmpty()){
            bIsLess(b,S);
            B.remove(b);
        }
    }
    return S;
}
  • Any set operation can be implemented using generic merge
  • Union
    • aIsLess adds a into S
    • bIsLess adds b into S
    • bothEqual adds a (or b) into S
  • Intersection
    • aIsLess and bIsLess do nothing
    • bothEqual adds a (or b) into S
  • Difference
    • aIsLess adds a into S
    • bIsLess and bothEqual do nothing
  • Runs in linear time, , provided the auxillary methods are

Trees

  • A tree is an abstract model of a heirarchical structure
  • A tree consists of nodes with a parent-child relationship
    • A parent has one or more children
    • Each child has only one parent
  • The root is the top node in the tree, the only node without a parent
  • An internal node has at least one child
  • An external node (or leaf) is a mode with no children
  • Nodes have ancestors (ie, the parent node of a parent)
  • The depth of a node is its number of ancestors
  • The height of a tree is its maximum depth

Tree ADT

Tree ADTs are defined using a similar concept to positional lists, as they don't have a natural ordering/indexing in the same way arrays do.

public interface Tree<E>{
    int size();
    boolean isEmpty();
    Node<E> root(); //returns root node
    Node<E> parent(Node<E> n); //returns parent of Node n
    Iterable<Node<E>> children(Node<E> n); //collection of all the children of Node n
    int numChildren(Node<E> n);
    Iterator<E> iterator(); //an iterator over the trees elements
    Iterator<Node<E>> nodes(); //collection of all the nodes
    boolean isInternal(Node<E> n); //does the node have at least one child
    boolean isExternal(Node<E> n); //does the node have no children
    boolean isRoot(Node<E> n); //is the node the root

}

Tree Traversal

Trees can be traversed in 3 different orders. As trees are recursive data structures, all 3 traversals are defined recursively. The tree below is used as an example in all 3 cases.

Pre-order

  • Visit the root
  • Pre order traverse the left subtree
  • Pre order traverse the right subtree

Pre-order traversal of the tree gives: F B A D C E G I H

In-order

  • In order traverse the left subtree
  • Visit the root
  • In order traverse the right subtree

In-order traversal of the tree gives: A B C D E F G H I

Post-order

  • Post order traverse the left subtree
  • Post order traverse the right subtree
  • Visit the root

Post-order traversal of the tree gives: A C E D B H I G F

Binary Trees

A binary tree is a special case of a tree:

  • Each node has at most two children (either 0, 1 or 2)
  • The children of the node are an ordered pair (the left node is less than the right node)

A binary tree will always fulfil the following properties:

Where:

  • is the number of nodes in the tree
  • is the number of external nodes
  • is the number of internal nodes
  • is the height/max depth of the tree

Binary Tree ADT

The binary tree ADT is an extension of the normal tree ADT with extra accessor methods.

public interface BinaryTree<E> extends Tree<E>{
    Node<E> left(Node<E> n); //returns the left child of n
    Node<E> right(Node<E> n); //returns the right child of n
    Node<E> sibling(Node<E> n); //returns the sibling of n
}

Arithmetic Expression Trees

Binary trees can be used to represent arithmetic expressions, with internal nodes as operators and external nodes as operands. The tree below shows the expression . Traversing the tree in-order will can be used to print the expression infix, and post-order evaluating each node with it's children as the operand will return the value of the expression.

Implementations

  • Binary trees can be represented in a linked structure, similar to a linked list
  • Node objects are positions in a tree, the same as positions in a positional list
  • Each node is represented by an object that stores
    • The element
    • A pointer to the parent node
    • A pointer to the left child node
    • A pointer to the right child node
  • Alternatively, the tree can be stored in an array A
  • A[root] is 0
  • If p is the left child of q, A[p] = 2 * A[q] + 1
  • If p is the right child of q, A[p] = 2 * A[q] + 2
  • In the worst, case the array will have size

Binary Search Trees

  • Binary trees can be used to implement a sorted map
  • Items are stored in order by their keys
  • For a node with key , every key in the left subtree is less than , and every node in the right subtree is greater than
  • This allows for support of nearest-neighbour queries, so can fetch the key above or below another key
  • Binary search can perform nearest neighbour queries on an ordered map to find a key in time
  • A search table is an ordered map implemented using a sorted sequence
    • Searches take
    • Insertion and removal take time
    • Only effective for maps of small size

Methods

Binary trees are recursively defined, so all the methods operating on them are easily defined recursively also.

  • Search
  • To search for a key
    • Compare it with the key at
    • If , the value has been found
    • If , search the right subtree
    • If , search the left subtree
  • Insertion
    • Search for the key being inserted
    • Insert at the leaf reached by the search
  • Deletion
    • Find the internal node that is follows the key being inserted in an in order traversal (the in order successor)
    • Copy key into the in order successor node
    • Remove the node copied out of

Performance

  • Consider a binary search tree with items and height
  • The space used is
  • The methods get, put, remove take time
    • The height h is in the best case, when the tree is perfectly balanced
    • In the worst case, when the tree is basically just a linked list, this decays to

AVL Trees

  • AVL trees are balanced binary trees
    • For every internal node of the tree, the heights of the subtrees of can differ by at most 1
  • The height of an AVL tree storing keys is
  • Balance is maintained by rotating nodes every time a new one is inserted/removed

Performance

  • The runtime of a single rotation is
  • The tree is assured to always have , so the runtime of all methods is
  • This makes AVL trees an efficient implementation of binary trees, as their performance does not decay as the tree becomes unbalanced

Priority Queues

A priority queue is an implementation of a queue where each item stored has a priority. The items with the highest priority are moved to the front of the queue to leave first. A priority queue takes a key along with a value, where the key is used as the priority of the item.

Priority Queue ADT

public interface PriorityQueue<K,V>{
    int size();
    boolean isEmpty();
    void insert(K key, V value); //inserts a value into the queue with key as its priority
    V removeMin(); //removes the entry with the lowest key (at the front of the queue)
    V min(); //returns but not removes the smallest key entry (peek)
}

Entry Objects

  • To store a key-value pair, a tuple/pair-like object is needed
  • An Entry<K,V> object is used to store each queue item
    • Key is what is used to defined the priority of the item in the queue
    • Value is the queue item
  • This pattern is similar to what is used in maps
public class Entry<K,V>{
    private K key;
    private V value;

    public Entry(K key, V value){
        this.key = key;
        this.value = value;
    }

    public K getKey(){
        return key;
    }

    public V getValue(){
        return value;
    }

}

Total Order Relations

  • Keys may be arbitrary values, so they must have some order defined on them
    • Two entries may also have the same key
  • A total order relation is a mathematical concept which formalises ordering on a set of objects where any 2 are comparable.
  • A total ordering satisfies the following properties
    • or
      • Comparability property
    • If , then
      • Transitive property
    • If and , then
      • Antisymmetric property
      • Reflexive property

Comparators

  • A comparator encapsulates the action of comparing two objects with a total order declared on them
  • A priority queue uses a comparator object given to it to compare two keys to decide their priority
public class Comparator<E>{
    public int compare(E a, E b){
        if(a < b)
            return -1;
        if(a > b)
            return 1;
        return 0;
    }
}

Implementations

Unsorted List-Based Implementation

A simple implementation of a priority queue can use an unsorted list

  • insert() just appends the Entry(key,value) to the list
    • time
  • removeMin() and min() linear search the list to find the smallest key (one with highest priority) to return
    • Linear search takes time

Sorted List-Based Implementation

To improve the speed of removing items, a sorted list can instead be used. These two implementations have a tradeoff between which operations are faster, so the best one for the application is usually chosen.

  • insert() finds the correct place to insert the Entry(key,value) in the list to maintain the ordering
    • Has to find place to insert, takes time
  • As the list is maintained in order, the entry with the lowest key is always at the front, meaning removeMin() and min() just pop from the front
    • Takes time

Sorting Using a Priority Queue

The idea of using a priority queue for sorting is that all the elements are inserted into the queue, then removed one at a time such that they are in order

  • Selection sort uses an unsorted queue
    • Inserting items in each time takes time
    • Removing the elements in order
    • Overall time
  • Insertion sort uses a sorted queue
    • Runtimes are the opposite to unsorted
    • Adding elements takes time
    • Removing elements in each time takes time
    • Overall runtime of again

Heaps

  • A heap is a tree-based data structure where the tree is a complete binary tree
  • Two kinds of heaps, min-heaps and max-heaps
  • For a min-heap, the heap order specifies that for every internal node other than the root,
    • In other words, the root of the tree/subtree must be the smallest node
    • This property is inverted for max heaps
  • Complete binary tree means that every level of the tree, except possibly the last, is filled, and all nodes are as far left as possible.
    • More formally, for a heap of height , for there are nodes of depth
    • At depth , the internal nodes are to the left of the external nodes
    • The last node of a heap is the rightmost node of maximum depth
  • Unlike binary search trees, heaps can contain duplicates
  • Heaps are also unordered data structures
  • Heaps can be used to implement priority queues
    • An Entry(Key,Value) is stored at each node

Insertion

  • To insert a node z into a heap, you insert the node after the last node, making z the new last node
    • The last node of a heap is the rightmost node of max depth
  • The heap property is then restored using the upheap algorithm
  • The just inserted node is filtered up the heap to restore the ordering
  • Moving up the branches starting from the z
    • While parent(z) > (z)
      • Swap z and parent(z)
  • Since a heap has height , this runs in time

Removal

  • To remove a node z from the heap, replace the root node with the last node w
  • Remove the last node w
  • Restore the heap order using downheap
  • Filter the replacement node back down the tree
    • While w is greater than either of its children
      • Swap w with the smallest of its children
  • Also runs in time

Heap Sort

For a sequence S of n elements with a total order relation on them, they can be ordered using a heap.

  • Insert all the elements into the heap
  • Remove them all from the heap again, they should come out in order
  • calls of insert take time
  • calls to remove take time
  • Overall runtime is
  • Much faster than quadratic sorting algorithms such as insertion and selection sort

Array-based Implementation

For a heap with n elements, the element at position p is stored at cell f(p) such that

  • If p is the root, f(p) = 0
  • If p is the left child q, f(p) = 2*f(q)+1
  • If p is the right child q, f(p) = 2*f(q)+2

Insert corresponds to inserting at the first free cell, and remove corresponds to removing from cell 0

  • A heap with n keys has length

Skip Lists

  • When implementing sets, the idea is to be able to test for membership and update elements efficiently
  • A sorted array or list is easy to search, but difficult to maintain in order
  • Skip lists consists of multiple lists/sets
    • The skip list
    • contains all the elements, plus
    • is a random subset of , for
      • Each element of appears in with probability 0.5
    • contains only

To search for an element in the list:

  • Start in the first position of the top list
  • At the current position , compare with the next element in the current list
    • If , return
    • If , move to the next element in the list
      • "Scan forward"
    • If , drop down to the element below
      • "Drop down"
  • If the end of the list () is reached, the element does not exist

Insertion

To insert an element into the list:

  • Repeatedly toss a fair coin until tails comes up
    • is the number of times the coin came up heads
  • If , add to the skip list new lists
    • Each containing only the two end keys
  • Search for and find the positions of the items with the largest element in each list
    • Same as the search algorithm
  • For , insert k into list after position

Deletion

To remove an entry from a skip list:

  • Search for in the skip list and find the positions of the items containing
  • Remove those positions from the lists
  • Remove a list if neccessary

Implementation

A skip list can be implemented using quad-nodes, where each node stores

  • It's item/element
  • A pointer to the node above
  • A pointer to the node below
  • A pointer to the next node
  • A pointer to the previous node

Performance

  • The space used by a skip list depends on the random number on each invocation of the insertion algorithm
    • On average, the expected space usage of a skip list with items is
  • The run time of the insertion is affected by the height of the skip list
    • A skip list with items has average height
  • The search time in a skip list is proportional to the number of steps taken
  • The drop-down steps are bounded by the height of the list
  • The scan-forward steps are bounded by the length of the list
    • Both are
  • Insertion and deletion are also both

Graphs

A graph is a collection of edges and vertices, a pair , where

  • is a set of nodes, called vertices
  • is a collection of pairs of vertices, called edges
  • Vertices and edges are positions and store elements

Examples of graphs include routes between locations, users of a social network and their friendships, and the internet.

There are a number of different types of edge in a graph, depending upon what the edge represents:

  • Directed edge
    • Ordered pair of vertices
    • First vertex is the origin
    • Second vertex is the destination
    • For example, a journey between two points
  • Undirected edge
    • Unordered pair of vertices
  • In a directed graph, all edges are directed
  • In an undirected graph, all edged are undirected

Graph Terminology

  • Adjacent vertices
    • Two vertices and are adjacent (ie connected by an edge)
  • Edges incident on a vertex
    • The edges connect to a vertex
    • , , and are incident on
  • End vertices or endpoints of an edge
    • The vertices connected to an edge
    • and are endpoints of
  • The degree of a vertex
    • The number of edges connected to it
    • has degree 5
  • Parallel edges
    • Edges that make the same connection
    • and are parallel
  • Self-loop
    • An edge that has the same vertex at both ends
    • is a self-loop
  • Path
    • A sequence of alternating vertices and edges
    • Begins and ends with a vertex
    • Each edge is preceded and followed by its endpoints
    • is a simple path
  • Cycle
    • A circular sequence of alternating vertices and edges
      • A circular path
    • A simple cycle is one where all edges and vertices are distinct
    • A non-simple cycle contains an edge or vertex more than once
    • A graph without cycles (acyclic) is a tree
  • Length
    • The number of edges in a path
    • The number of edges in a cycle

Graph Properties

Notation:

  • is the number of vertices
  • is the number of edges
  • is the degree of vertex

The sum of the degrees of the vertices of a graph is always an even number. Each edge is counted twice, as it connects to two vertices, so . For example, the graph shown has and .

In an undirected graph with no self loops and no multiple edges, . Each vertex has degree at most and . For the graph shown,

The Graph ADT

A graph is a collection of vertices and edges, which are modelled as a combination of 3 data types: Vertex, Edge and Graph.

  • A Vertex is just a box object storing an element provided by the user
  • An Edge also stores an associated value which can be retrieved
public interface Graph{
    int numVertices();

    Collection vertices(); //returns all the graph's vertices

    int numEdges();

    Collection<Edge> edges(); //returns all the graph's edges

    Edge getEdge(u,v); //returns the edge between u and v, if on exists
    // for an undirected graph getEdge(u,v) == getEdge(v,u)

    Pair<Vertex, Vertex> endVertices(e); //returns the endpoint vertices of edge e

    Vertex oppsite(v,e); //returns the vertex adjacent to v along edge e

    int outDegree(v); //returns the number of edges going out of v

    int inDegree(v); //returns the number of edges coming into v
    //for an undirected graph, inDegree(v) == outDegree(v)

    Collection<Vertex> outgoingEdges(v); //returns all edges that point out of vertex v

    Collection<Vertex> incomingEdges(v); //returns all edges that point into vertex v
    //for an undirected graph, incomingEdges(v) == outgoingEdges(v)

    Vertex insertVertex(x); //creates and returns a new vertex storing element x

    Edge insertEdge(u,v,x); //creates and returns a new edge from vertices u to v, storing element x in the edge

    void removeVertex(v); //removes vertex v and all incident edges from the graph

    void removeEdge(e); //removes edge e from the graph
}

Representations

There are many different ways to represent a graph in memory.

Edge List

An edge list is just a list of edges, where each edge knows which two vertices it points to.

  • The Edge object stores
    • It's element
    • It's origin Vertex
    • It's destination Vertex
  • The edge list stores a sequence of Edge objects

Adjacency List

In an adjacency list, each vertex stores an array of the vertices adjacent to it.

  • The Vertex object stores
    • It's element
    • A collection/array of all it's incident edges
  • The adjacency list stores all Vertex Objects

Adjacency Matrix

An adjacency matrix is an matrix, where is the number of vertices in the graph. It acts as a lookup table, where each cell corresponds to an edge between two vertices.

  • If there is an edge between two vertices and , the matrix cell will contain the edge.
  • Undirected graphs are symmetrical along the leading diagonal

Subgraphs

  • A subgraph of a graph is a graph such that:
    • The vertices of are a subset of the vertices of
    • The edges of are a subset of the edges of
  • A spanning subgraph of is a subgraph that contains all the vertices of
  • A graph is connected if there is a path between every pair of vertices
  • A tree is an undirected graph such that
    • is connected
    • has no cycles
  • A forest is an undirected graph without cycles
  • The connected components of a forest are trees

  • A spanning tree of a connected graph is a spanning subgraph that has all vertices covered with a minimum possible number of edges
    • A spanning tree is not unique unless the graph is a tree
      • Multiple spanning trees exist
    • Spanning trees have applications in the design of communication networks
    • A spanning forest of a graph is a spanning subgraph that is a forest

DFS is a general technique for traversing a graph. A DFS traversal of a graph will:

  • Visit all vertices and edges of
  • Determine whether is connected
  • Compute the spanning components of
  • Compute the spanning forest of

DFS on a graph with vertices and edges takes time. The algorithm is:

  • For a graph and a vertex of
  • Mark vertex as visited
  • For each of 's outgoing edges
    • If has not been visited then
      • Record as the discovery edge for vertex
      • Recursively call DFS with on

DFS(G,V) visits all vertices and edges in the connected component of v, and the discovery edges labelled by DFS(G,V) form a spanning tree of the connected component of v.

DFS can also be extended to path finding, to find a path between two given vertices and . A stack is used to keep track of the path, and the final state of the stack is the path between the two vertices. As soon as the destination vertex is encountered, the contents of the stack is returned.

DFS can be used for cycle detection too. A stack is used to keep track of the path between the start vertex and the current vertex. As soon as a back edge (an edge we have already been down in the opposite direction) is encountered, we return the cycle as the portion of the stack from the top to the vertex .

To perform DFS on every connected component of a graph, we can loop over every vertex, doing a new DFS from each unvisited one. This will detect all vertices in graphs with multiple connected components.

BFS is another algorithm for graph traversal, similar to DFS. It also requires time. The difference between the two is that BFS uses a stack while DFS uses a queue. The algorithm is as follows:

  • Mark all vertices and edges as unexplored
  • Create a new queue
  • Add the starting vertex to the queue
  • Mark as visited
  • While the queue is not empty
    • Pop a vertex from the queue
    • For all neighbouts of
      • If is not visited
        • Push into the queue
        • Mark as visited

For a connected component of graph containing :

  • BFS visits all vertices and edges of
  • The discovery edges labelled by BFS(G,s) form a spanning tree of
  • The path of the spanning tree formed by the BFS is the shortest path between the two vertices

BFS can be specialised to solve the following problems in time:

  • Compute the connected components of a graph
  • Compute a spanning forest of a graph
  • Find a simple cycle in G
  • Find the shortest path between two vertices
    • DFS cannot do this, this property is unique to BFS

Directed Graphs

A digraph (short for directed graph) is a graph whose edges are all directed.

  • Each edge goes in only one direction
  • Edge goes from a to b but not from b to a
  • If the graph is simple and has vertices and edges,
  • DFS and BFS can be specialised to traversing directed edges
    • A directed DFS starting at a vertex determines the vertices reachable from
    • One vertex is reachable from another if there is a directed path to it

Strong Connectivity

A digraph is said to be strongly connected if each vertex can reach all other vertices. This property can be identified in time with the following algorithm:

  • Pick a vertex in the graph
  • Perform a DFS starting from
    • If theres a vertex not visited, return false
  • Let be with all the edge directions reversed
  • Perform a DFS starting from in
    • If theres a vertex not visited, return false
    • Else, return True

Transitive Closure

Given a digraph , the transitive closure of is the digraph such that:

  • has the same vertices as
  • If has a directed path from to , then G* also has a directed *edge* from to
  • In , every pair of vertices with a path between them in is now adjacent
  • The transitive closure provides reachability information about a digraph

The transitive closure can be computed by doing a DFS starting at each vertex. However, this takes time. Alternatively, there is the Floyd-Warshall algorithm:

  • For the graph , number the vertices
  • Compute the graphs
    • has directed edge if has a directed path from to with intermediate vertices
  • Digraph is computed from
  • Add if edges and appear in

In pseudocode:

for k=1 to n
    Gk = Gk_1
      for i=1 to n (i != k)
          for j=1 to n (j != i, j!=k)
              if G_(k-1).areAdjacent(vi,vk) && G_(k-1).areAdjacent(vk,vj)
                  if !G_(k-1).areAdjacent(vi,vj)
                      G_k.insertDirectedEdge(vi,vj,k)
  return G_n

This algorithm takes time. Basically, at each iteration a new vertex is introduced, and each vertex is checked to see if a path exists through the newly added vertex. If it does, a directed edge is inserted to transitively close the graph.

Topological Ordering

  • A Directed Acyclic Graph (DAG) is digraph that has no directed cycles
  • A topological ordering of a digraph is a numbering of the vertices such that for every edge ,
    • The vertex it points to is always greater than it
  • A digraph can have a topological ordering if and only if it is a DAG

A topological ordering can be calculated using a DFS:

public static void topDFS(Graph G, Vertex v){
    v.visited = true
    for(Edge e: v.edges){
        w = opposite(v,e)
        if(w.visited = false)
            topDFS(G,w)
        else{
            v.label = n
            n = n-1
        }
    }
}

The first node encountered in the DFS is assigned , the one after that , and so on until all nodes are labelled.

CS132

Note that specifics details of architectures such as the 68k, its specific instruction sets, or the PATP are not examinable. They are included just to serve as examples.

The 68008 datasheet can be found here, as a useful resource.

Digital Logic

Digital logic is about reasoning with systems with two states: on and off (0 and 1 (binary)).

Basic Logic Functions

Some basic logic functions, along with their truth tables.

NOT

Af
01
10

AND

ABf
000
010
100
111

OR

ABf
000
011
101
111

XOR

ABf
000
011
101
110

NAND

ABf
001
011
101
110

NOR

ABf
001
010
100
110

X-NOR

ABf
001
010
100
111

Logic Gates

Logic gates represent logic functions in a circuit. Each logic gate below represents one of the functions shown above.

Logic Circuits

Logic circuits can be built from logic gates, where outputs are logical functions of their inputs. Simple functions can be used to build up more complex ones. For example, the circuit below implements the XOR function.

Another example, using only NAND gates to build XOR. NAND (or NOR) gates can be used to construct any logic function.

Truth tables can be constructed for logic circuits by considering intermediate signals. The circuit below has 3 inputs and considers 3 intermediate signals to construct a truth table.

ABCPQRf
0000000
0010000
0100000
0110101
1000000
1010011
1101001
1111111

Truth tables of circuits are important as they enumerate all possible outputs, and help to reason about logic circuits and functions.

Boolean Algebra

  • Logic expressions, like normal algebraic ones, can be simplified to reduce complexity
    • This reduces the number of gates required for their implementation
    • The less gates, the more efficient the circuit is
      • More gates is also more expensive
  • Sometimes, only specific gates are available too and equivalent expressions must be found that use only the available gates
  • Two main ways to simplify expressions
    • Boolean algebra
    • Karnaugh maps
  • The truth table for the expression before and after simplifying must be identical, or you've made a mistake

Expressions from Truth Tables

A sum of products form of a function can be obtained from it's truth table directly.

ABCf
0001
0011
0100
0110
1001
1010
1101
1111

Taking only the rows that have an output of 1:

  • The first row of the table:
  • The second row:
  • Fifth:
  • Seventh:
  • Eight:

Summing the products yields:

Boolean Algebra Laws

There are several laws of boolean algebra which can be used to simplify logic expressions:

NameAND formOR form
Identity Law
Null Law
Idempotent Law
Inverse Law
Commutative Law
Associative Law
Distributive Law
Absorption Law
De Morgan's Law
  • Can go from AND to OR form (and vice versa) by swapping AND for OR, and 0 for 1

Most are fairly intuitive, but some less so. The important ones to remember are:

De Morgan's Laws

De Morgan's Laws are very important and useful ones, as they allow to easily go from AND to OR. In simple terms:

  • Break the negation bar
  • Swap the operator

Example 1

When doing questions, all working steps should be annotated.

Example 2

Karnaugh Maps

  • Karnaugh Maps (k-maps) are sort of like a 2D- truth table
  • Expressions can be seen from the location of 1s in the map
ABf
00a
01b
10d
11c

  • Functions of 3 variables can used a 4x2 or 2x4 map (4 variables use a 4x4 map)

  • Adjacent squares in a k-map differ by exactly 1 variable
    • This makes the map gray coded
  • Adjacency also wraps around

The function is shown in the map below.

Grouping

  • Karnaugh maps contain groups, which are rectangular clusters of 1s -
  • To simplify a logic expression from a k-map, identify groups from it, making them as large and as few as possible
  • The number of elements in the group must be a power of 2
  • Each group can be described by a singular expression
  • The variables in the group are the ones that are constant within the group (ie, define that group)

Sometimes, groups overlap which allow for more than one expression

The function for the map is therefore either or (both are equivalent)

Sometimes it is not possible to minimise an expression. the map below shows an XOR function

Don't Care Conditions

Sometimes, a certain combination of inputs can't happen, or we dont care about the output if it does. An X is used to denote these conditions, which can be assumed as either 1 or 0, whichever is more convenient.

Combinatorial Logic Circuits

Some useful circuits can be constructed using logic gates, examples of which are shown below. Combinatorial logic circuits operate as fast as the gates operate, which is theoretically zero time (realistically, there is a nanosecond-level tiny propagation delay).

1-Bit Half Adder

  • Performs the addition of 2 bits, outputting the result and a carry bit.

ABSumCarry
0000
0110
1010
1101

1-Bit Full Adder

  • Adds 2 bits plus carry bit, outputting the result and a carry bit.

Carry inABSumCarry out
00000
00101
01001
01110
10001
10110
11010
11111

N-Bit Full Adder

  • Combination of a number of full adders
  • The carry out from the previous adder feeds into the carry in of the next

N-Bit Adder/Subtractor

  • To convert an adder to an adder/subtractor, we need a control input such that:
  • is calculated using two's complement
    • Invert the N bit binary number B by doing
    • Add 1 (make the starting carry in a 1)

Encoders & Decoders

  • A decoder has binary input pins, and one output pin per possible input state
  • eg 2 inputs has 4 unique states so has 4 outputs
    • 3 inputs has 8 outputs
  • Often used for addressing memory
  • The decoder shown below is active low
    • Active low means that 0 = active, and 1 = inactive
      • Converse to what would usually be expected
    • Active low pins sometimes labelled with a bar, ie
  • It is important to be aware of this, as ins and outs must comform to the same standard

000111
011011
101101
111110
  • Encoders are the opposite of decoders, encoding a set of inputs into outputs
  • Multiple input pins, only one should be active at a time
  • Active low encoder shown below

011100
101101
110110
111011

Multiplexers & De-Multiplexers

Multiplexers have multiple inputs, and then selector inputs which choose which of the inputs to put on the output.

Y
00
01
10
11

De-Multiplexers are the reverse of multiplexers, taking one input and selector inputs choosing which output it appears on. The one shown below is active low

00A111
011A11
1011A1
11111A

Multiplexers and De-Multiplexers are useful in many applications:

  • Source selection control
  • Share one communication line between multiple senders/receivers
  • Parallel to serial conversion
    • Parallel input on X, clock signal on S, serial output on Y

Sequential Logic Circuits

A logic circuit whose outputs are logical functions of its inputs and it's current state

Flip-Flops

Flip-flops are the basic elements of sequential logic circuits. They consist of two nand gates whose outputs are fed back to the inputs to create a bi-stable circuit, meaning it's output is only stable in two states.

  • and are active low set and reset inputs
  • is set high when and
  • is reset (to zero) when and
  • If then does not change
  • If both and are zero, this is a hazard condition and the output is invalid
QP
00XX
0110
1001
11XX

The timing diagram shows the operation of the flip flop

D-Type Latch

A D-type latch is a modified flip-flop circuit that is essentially a 1-bit memory cell.

  • Output can only change when the enable line is high
  • when enabled, otherwise does not change ()
  • When enabled, data on goes to
Enable
00
01
1001
1110

Clocked Flip-Flop

There are other types of clocked flip-flop whose output only changes on the rising edge of the clock input.

  • means rising edge responding

N-bit Register

  • A multi-bit memory circuit built up from d-type latches
  • The number on is stored in the registers when the clock rises
  • The stored number appears on the outputs
  • cannot change unless the circuit is clocked
  • Parallel input, parallel output

N-bit Shift Register

  • A register that stores and shifts bits taking one bit input at a time
  • Serial input, parallel output
  • When a clock transition occurs, each bit in the register will be shifted one place
  • Useful for serial to parallel conversion

N-bit Counter

  • The circles on the clock inputs are inverted on all but the first
  • Each flip-flop is triggerd on a high -> low transition of the previous flip-flop
  • Creates a counter circuit

Output is 0000, 1000, 0100, 1100, 0010, etc...

  • The first bit swaps every clock
  • 2nd bit swaps every other clock
  • 3rd bit swaps every fourth clock
  • etc...

Three State Logic

  • Three state logic introduces a third state to logic - unconnected
  • A three-state buffer has an enable pin, which when set high, disconnects the output from the input
  • Used to prevent connecting outputs to outputs, as this can cause issues (short circuits)

This can be used to allow different sources of data onto a common bus. Consider a 4-bit bus, where 2 4-bit inputs are connected using 3-state buffers. Only one of the buffers should be enabled at any one time.

  • When , A will be placed on the bus
  • When , B will be placed on the bus

Physical Implementations

Logic gates are physical things with physical properties, and these have to be considered when designing with them. Typical voltage values for TTL (Transistor-Transistor Logic):

  • 5v - max voltage
  • 2.8v - minimum voltage for a logical 1
  • 2.8-0.8v - "forbidden region", ie voltages in this region are undefined
  • 0.8-0v - voltage range for a logical 0

Propagation Delay

  • Logic gates have a propagation delay, the amount of time it takes for the output to reflect the input
    • Typically a few nanoseconds or less
  • This limits the speed at which logic circuits can operate
  • Delay can be reduced by increasing density of gates on an IC

Integrated Circuits

  • Elementary logic gates can be obtained in small ICs
  • Programmable deviced allow large circuits to be created inside a single chip
    • PAL - Programmable Array Logic
      • One-time programmamble
    • PLA - Programmable Logic Array
      • Contains an array of AND and OR gates to implement any logic functions
    • FPGA - Field Programmable Gate Array
      • Contains millions of configurable gates
      • More modern

PLA example

A PLA allows for the implementation of any sum-of-products function, as it has an array of AND gates, then OR gates, with fuses that can be broken to implement a specific function.

Assembly

Microprocessor Fundamentals

The CPU

  • The CPU controls and performs the execution of instructions
  • Does this by continuously doing fetch-decode-execute cycle
  • Very complex, but two key components
    • Control Unit (CU)
      • Decodes the instructions and handles logistics
    • Arithmetic Logic Unit (ALU)
      • Does maths

Fetch-Decode-Execute

  • Three steps to every cycle
    • Fetch instructions from memory
    • Decode into operations to be performed
    • Execute to change state of CPU
  • Takes place over several clock cycles

The components of the CPU that are involved in the cycle:

  • ALU
  • CU
  • Program Counter (PC)
    • Tracks the memory address of the next instruction to be executed
  • Instruction Register (IR)
    • Contains the most recent instruction fetched
  • Memory Address Register (MAR)
    • Contains address of the memory location to be read/written
  • Memory Data/Buffer Register (MDR/MBR)
    • Contains data fetched from memory or to be written to memory

The steps of the cycle:

  • Fetch
    • Instruction fetched from memory location held by PC
    • Fetched instruction stored in IR
    • PC incremented to point to next instruction
  • Decode
    • Retrieved instruction decoded
    • Establish opcode type
  • Execute
    • CU signals the necessary CPU components
    • May result in changes to data registers, ALU, I/O, etc

The 68008

The 68008 is an example of a CPU. The "programmer's model" is an abstraction that represents the internals of the architecture. The internal registers as shown below are part of the programmer's model.

  • Internal registers are 32 bits wide
  • Internal data buses are 16 bit wide
  • 8 bit external data bus
  • 20 bit external address bus
  • D0-D7 are 32 bit registers used to store frequently used values
    • Can be long (32 bits), word (16 bits), or byte (8 bits)
  • Status register (CCR) consists of 2 8-bit registers
    • Various status bits are set or reset depending upon conditions arising from execution
  • A0-A6 are pointer registers
  • A7 is system stack pointer to hold subroutine return addresses
  • Operations on addresses do not alter status register/ CCR
    • Only ALU can incur changes in status
  • The stack pointer is a pointer to the next free location in the system stack
    • Provides temporary storage of state, return address, registers, etc during subroutine calls and interrupts

The diagram shows the internal architecture of the CPU, and how the internal registers are connected via the buses. Note how and which direction data moves in, as indicated by the arrows on the busses.

Register Transfer Language

The fetch-decode-execute cycle is best described using Register Transfer Language (RLT), a notation used to show how data moves around the internals of a processor and between registers.

  • For example [MAR] <- [PC] denotes the transfer of the contents of the program counter to the memory address register
  • Computer's main memory is called Main Store (MS), and the contents of memory location N is denoted [MS(N)]
  • RLT does not account for the pipelining of instructions
  • Fetching an instruction in RTL:
RLTMeaning
[MAR] <- [PC]Move contents of PC to MAR
[PC] <- [PC] + 1Increment PC
[MBR] <- [MS([MAR])]Read address from MAR into MBR.
[IR] <- [MBR] -Load instruction into I
CU <- [IR(opcode)]Decode the instruction

Assembly Language

  • Assembly is the lowest possible form of code
  • High level code (for example C) is compiled to assembly code
  • Assembly is then assembled into machine code (binary)
  • Assembly instructions map 1:1 to processor operations
  • Uses mnemonics for instructions, ie MOV or ADD
  • Languages vary, but format tends to be similar: LABEL: OPCODE OPERAND(S) | COMMENT

An example program is shown below

    ORG  $4B0      | this program starts at hex 4B0
    move.b #5, D0  | load D0 with number 5
    add.b  #$A, D0 | add 10 (0x0A) to D0
    move.b D0, ANS | move contents of D0 to ANS
ANS: DS.B 1        | leave 1 byte of memory empty and name it ANS
  • # indicates a literal
  • $ means hexadecimal
  • % means binary
  • A number without a prefix is a memory address
  • ANS is a symbolic name
  • ORG (Origin) indicates where to load the program in memory
  • DS (Define Storage) tells the assembler where to put data

The 68008 Instruction Set

  • Instructions are commands that tell the processor what to do
  • 5 main kinds of instructions
    • Logical
      • Bitwise operations
      • AND, LSL (Logical Shift Left)
    • Branch
      • Cause the processor to jump execution to a labelled address
      • Condition is specified by testing state of CCR set by previous instruction
      • BRA - branch unconditionally
      • BEQ - branch if equal
    • System Control
  • Instructions are also specified with their data type, .b for byte, .w for word, .l for long
    • move.w moves 2 bytes

Data Movement

  • Similar to RTL
move.b D0,   D1 | [D1(0:7)] <- [D0(0:7)]
move.w D0,   D1 | [D1(0:15)] <- [D0(0:15)]
swap   D2       | swap lower and upper words
move.l $F20, D3  | [D3(24:31)] ← [MS($F20)]
                | [D3(16:23)] ← [MS($F21)]
                | [D3( 8:15)] ← [MS($F22)]
                | [D3( 0:7)] ← [MS($F23)]
                | copied 8 bytes at a time in big endian order

Arithmetic

  • Maths performed on the ALU
  • The 68008, like many older processors, has no FPU, so only integer operations are supported
add.l   Di, Dj  | [Dj] ← [Di] + [Dj]
addx.w  Di, Dj  | also add in x bit from CCR
sub.b   Di, Dj  | [Dj] ← [Dj] - [Di]
subx.b  Di, Dj  | also subtract x bit from CCR
mulu.w  Di, Dj  | [Dj(0:31)] ← [Di(0:15)] * [Dj(0:15)]
                | unsigned multiplication
muls.w  Di, Dj  | signed multiplication

Logical

  • Perform bitwise operations on data
  • Also done by ALU
  • AND, OR, etc but also shifts and rotates
  • Logical shift (LSL/LSR) adds a 0 when shifting
    • Bit shifted out goes into C and X
  • Arithmetic shift preserves sign bit (ASL/ASR)
  • Normal rotate (ROL/ROR) moves the top of the bit to the bottom bit and also puts the top bit into C and X
  • Rotate through X (ROXL/ROXR) rotates the value through the X register
AND.B #$7F, D0 | [D0] <- [D0] . [0x7F]
OR.B  D1,  D0 | [D0] <- [D0] + [D1]
LSL D0,    2  | [D0] <- [D0] << [2]

Branch

  • Cause the processor to move execution to a new pointer (jump/GOTO)
  • Instruction tests the state of the CCR bits against certain condition
  • Bits set by previous instructions
BRA | branch unconditionally
BCC | branch on carry clear
BEQ | branch on equal

System Control

  • Certain instructions used to issue other commands to the microprocessor

Subroutines and Stacks

  • Subroutines are useful for frequently used sections of code for obvious reasons
  • Can jump and return from subroutines in assembly
    • JSR <label> - Jump to Subroutine
    • RTS - Return from Subroutine
  • When returning, need to know where to return to
  • The stack is used as a LIFO data structure to store return addresses
  • JSR pushes the contents of the PC on the stack
  • RTS pops the return address from the stack to the PC
  • Can nest subroutine calls and stack will keep track

Addressing Modes

  • Addressing modes are how we tell the computer where to find the data it needs
  • 5 Kinds in the 68006, and many other processors have equivalents
    • Direct
    • Immediate
    • Absolute
    • Address Register Indirect
      • 5 variations
    • Relative

Direct Addressing

  • Probably the simplest
  • The address of an operand is specified by either a data or address register
move D3, D2 | [D2] <- [D3]
move D3, A2 | [A2] <- [D3]

Immediate Addressing

  • The operand forms part of the instruction (is a literal) and remains a constant
  • Note the prefix # specifying a literal and the prefix specifying the base of the number
move.b #$42, D5 | [D5] <- $42

Absolute Addressing

  • Operand specifies the location in memory
  • Does not allow for position-independent code: will always access the exact address given
move.l D2, $7FFF0 | [MS(7FFF0)] <- [D2]

Address Register Indirect Addressing

  • Uses offsets/increments/indexing to address memory based upon the address registers
  • Bad, rarely used
  • Not examinable

Relative Addressing

  • Specifies an offset relative to the program counter
  • Can be used to write position independent code
move 16(PC), D3 | [D3] <- [MS(PC + 16)]

Memory Systems

The Memory Hierarchy

  • Memory systems must facilitate the reading and writing of data
  • Many factors influence the choice of memory technology
    • Frequency of access
    • Access time
    • Capacity
    • Cost
  • Memory wants to be low cost, high capacity, and also fast
  • As a tradeoff, we organise memory into a hierarchy
    • Allows for some high speed, some high capacity

  • Data has to be dragged up the hierarchy
  • Memory access is somewhat predictable
  • Temporal locality - when a location accessed, likely the same location will be accessed again in the near future
  • Spatial locality - when a location accessed, likely that nearby locations will be referenced in the near future
    • 90% of memory access is within 2Kb of program counter

Semiconductor Memory Types

Memory TypeCategoryErasureWrite MechanismVolatility
Random Access Memory (RAM)Read-WriteElectronically, at byte-levelElectronically writtenVolatile
Read Only Memory (ROM)Read onlyNot possibleMask WrittenNon-volatile
Programmable ROM (PROM)Read onlyNot possibleElectronically writtenNon-volatile
Erasable PROM (EPROM)Read (mostly)UV light at chip levelElectronically writtenNon-volatile
Electrically Erasable PROM (EEPROM)Read (mostly)Electronically, at byte-levelElectronically writtenNon-volatile
Flash MemoryRead (mostly)Electronically, at byte-levelElectronically writtenNon-volatile
  • Particularly interested in random access
  • RAM is most common - implements main store
    • nb that all types shown here allow random access, name is slightly misleading
  • RAM is also volatile, meaning it is erased when de powered

Cache

  • If 90% of memory access is within 2Kb, store those 2Kb somewhere fast
  • Cache is small, fast memory right next to CPU
  • 10-200 times faster
  • If data requested is found in cache, this is a "cache hit" and provides a big speed improvement
  • We want things to be in cache
  • Cache speed/size is often a bigger bottleneck to performance than clock speed

Moore's Law

  • As said by the co-founder of intel, Gordon Moore, the number of transistors on a chip will double roughly every 18 months
    • Less true in recent years
  • Cost of computer logic and circuitry has fallen dramatically in the last 30 years
  • ICs become more densely paced
  • CPU clock speed is also increasing at a similar rate
  • Memory access speed is improving much more slowly however

Cache Concepts

  • Caching read-only data is relatively straightforward
    • Don't need to consider the possibility data will change
    • Copies everywhere in the memory hierarchy remain consistent
  • When caching mutable data, copies can become different between cache/memory
  • Two strategies for maintaining parity
    • Write through - updates cache and then writes through to update lower levels of hierarchy
    • Write back - only update cache, then when memory is replaced copy blocks back from cache

Cache Performance

Cache performance is generally measured by its hit rate. If the processor requests some block of memory and it is already in cache, this is a hit. The hit rate is calculated as

Cache misses can be categorised:

  • Compulsory - misses that would occur regardless of cache size, eg the first time a block is accessed, it will not be in cache
  • Capacity - misses that occur because cache is not large enough to contain all blocks needed during program execution
  • Conflict - misses that occur as a result of the placement strategy for blocks not being fully associative, meaning a block may have to be discarded and retrieved
  • Coherency - misses that occur due to cache flushes in multiprocessor systems

Measuring performance solely based upon cache misses is not accurate as it does not take into factor the cost of a cache miss. Average memory access time is measured as hit time + (miss rate miss penalty).

Cache Levels

Cache has multiple levels to provide a tradeoff between speed and size.

  • Level 1 cache is the fastest as it is the closest to the cpu, but is typically smallest
    • Sometimes has separate instructions/data cache
  • Level 2 cache is further but larger
  • Level 3 cache is slowest (but still very fast) but much larger (a few megabytes)
  • Some CPUs even have a level 4 cache

Different levels of cache exist as part of the memory hierarchy.

Semiconductors

  • RAM memory used to implement main store
  • Static RAM (SRAM) uses a flip-flop as the storage element for each bit
    • Uses a configuration of flip-flops and logic gates
    • Hold data as long as power is supplied
    • Provide faster read/write than DRAM
    • Typically used for cache
    • More expensive
  • Dynamic RAM (DRAM) uses a capacitor, and the presence to denote a bit
    • Typically simpler design
    • Can be packed much tighter
    • Cheaper to produce
    • Capacitor charge decays so needs refreshing by periodically supplying charge
  • The interface to main memory is a critical performance bottleneck

Memory Organisation

The basic element of memory is a one-bit cell with two states, capable of being read and written. Cells are built up into larger banks with combinatorial logic circuits to select which cell to read/write. The diagram shows an example of a 16x8 memory IC (16 words of 8 bytes).

For a 16x8 memory cell:

  • 4 address inputs
  • 8 data lines
    • word size

Consider alternatively a 1Kbit device with 1024 cells

  • Organised as a 128x8 array
    • 7 address pins
    • 8 data pins
  • Or, could organise as 1024x1 array
    • 10 address pins
    • 1 data pins
  • Less pins but very poorly organised
  • Best to keep memory cells square to make efficient use of space

Error Correction

Errors often occur within computer systems in the transmission of data dude to noise and interference. This is bad. Digital logic already gives a high degree of immunity to noise, but when noise is at a high enough level, this collapses.

Two common ways in which errors can occur:

  • Isolated errors
    • Occur at random due to noise
    • Usually singular incidences
  • Burst errors
    • Errors usually occur in bursts
    • A short period of time over which multiple errors occur
    • For example, a 1ms dropout of a connection can error many bits

Majority Voting

  • A simple solution to correcting errors
  • Just send every bit multiple times (usually 3)
    • The one that occurs the most is taken to be the true value
  • Slow & expensive

Parity

  • Parity adds an extra parity bit to each byte
  • Two types of parity system
    • Even parity
      • The value of the extra bit is chosen to make the total number of 1s an even number
    • Odd parity
      • The value of the extra bit is chosen to make the total number of 1s an odd number
  • 7 bit ascii for A is 0100 0001
    • With even parity - 0100 0001
    • Odd parity - 1100 0001
  • Can be easily computed in software
  • Can also be computed in hardware using a combination of XOR gates
    • Usually faster than in software
  • Allows for easy error detection without the need to significantly change the model for communication
  • Parity bit is computed and added before data is sent, parity is checked when data is received
  • Note that if there is more than one error, the parity bit will be correct still and the error won't be detected
    • Inadequate for detecting bursts of error

Error Correcting Codes

  • ECCs or checksums are values computed from the entire data
  • If any of the data changes, the checksum will also change
  • The checksum is calculated and broadcast with the data so it can be checked on reception
  • Can use row/column parity to compute an checksum
    • Calculate parity of each row and of each column
    • Diagram shows how parity bits detect an error in the word "Message"

I/O

Memory Mapped I/O

  • With memory mapped I/O, the address bus is used to address both memory and I/O devices
  • Memory on I/O devices is mapped to values in the main address space
  • When a CPU accesses a memory address, the address may be in physical memory (RAM), or the memory of some I/O device
  • Advantages
    • Very simple
    • CPU requires less internal logic
    • Can use general purpose memory instructions for I/O
  • Disadvantages
    • Have to give up some memory
      • Less of a concern on 64-bit processors
      • Still relevant in smaller 16 bit CPUs

Polled I/O

  • Polling is a technique for synchronising communication between devices.
  • Most I/O devices are much slower than the CPU
  • Busy-wait polling involves constantly checking the state of the device
    • Usually the device replies with nothing
    • Can interleave polls with something else useful

  • Advantages
    • Still relatively simple
  • Disadvantages
    • Wastes CPU time and power
    • Interleaving can lead to delayed responses from CPU

Synchronisation methods also need some way to transfer the data, so are sometimes used in conjunction with memory-mapped I/O. Methods for synchronising devices and methods for reading/writing data are not directly comparable.

Handshaking

Another form of synchronisation

  • Computer responds to the printer being ready by placing data on the data bus and signalling DATA_VALID
    • Can do this either in hardware or in software
  • Timing diagram shows data exchange
  • During periods where both signals are at a logical 0, data is exchanged

Handshaking Hardware

Handshaking is usually done using an external chip, such as the 6522 VIA (Versatile Interface Adapter)

Setting bit values in the PCR (Peripheral Control Register) on the VIA allows to control the function.

  • Use PORT B as output
  • CB1 control line as PRINTER_READY
  • CB2 control line as DATA_VALID
  • For CB1 and CB2 control, 8 bit register is set to 1000xxxx
    • Last 4 bits not used, don't care

Interrupts

  • Asynchronous I/O
  • Two kinds of interrupts (in 6502 processor)
    • Interrupt Request (IRQ)
      • Code can disable response
      • Sent with a priority
      • If priority lower than that of current task, will be ignored
      • Can become non-maskable if ignored for long enough
    • Non-Maskable Interrupt (NMI)
      • Cannot be disabled, must be serviced
  • An interrupt forces the CPU to jump to an Interrupt Service Routine (ISR)
    • Switches context, uses stack to store state of registers
  • ISRs can be nested
  • Interrupts usually generated by some external device
    • Hard drive can generate an interrupt when data is ready
    • A timer can generate an interrupt repeatedly at a fixed interval
    • A printer can generate an interrupt when ready to receive data
  • Advantages
    • Fast response
    • No wasted CPU time
  • Disadvantages
    • All data transfer still CPU controlled
    • More complex hardware/software

Direct Memory Access (DMA)

  • The CPU is a bottleneck for I/O
  • All techniques shown so far are limited by this bottleneck
  • DMA is used where large amounts of data must be transferred quickly
  • Control of system busses surrendered from CPU to a DMA Controller (DMAC)
    • DMAC is a dedicated device optimised for data transfer
  • Can be up to 10x faster than CPU-driven I/O

DMA Operation

  • DMA transfer is requested by I/O
  • DMAC passes request to CPU
  • CPU initialises DMAC
    • Input or Output?
    • Start address is put into DMAC address register
    • Number of words is put into DMAC count register
    • CPU enables DMAC
  • DMAC requests use of system busses
  • CPU responds with DMAC ack when ready to surrender busses
  • DMAC can operate in different modes
    • Cycle stealing
      • Uses system busses when they're not being used by CPU
    • Burst mode
      • Requires busses for extended period of time, locks the CPU out for a fixed time, until transfer complete, or until CPU receives interrupt from device of higher priority

DMA Organisation

There are multiple ways a DMA can be incorporated into a system:

  • Single bus, detached DMA
    • All modules (DMA, I/O devices, memory, CPU) share system bus
    • DMA uses programmed I/O to exchanged data between memory and I/O device
    • Straightforward, as DMA can just mimic processor
    • Inefficient
  • Separate I/O bus
    • Only one interface to DMA module
    • The bus the DMA shares with processor and memory is only used to transfer data to and from memory

Summary

  • **Memory-mapped **deviced are accessed in the same way as RAM, at fixed address locations
  • Polled I/O is for scheduling input and output, where the CPU repeatedly checks for data
  • I/O devices are slow, so handshaking techniques coordinate CPU and device for transfer of data
  • Interrupts avoid polled I/O by diverting the CPU to a special I/O routine when necessary
  • A DMA controller can be used instead of the CPU to transfer data into and out of memory, faster than the CPU but at additional hardware cost

Microprocessor Architecture

  • Computer architecture concerns the structure and properties of a computer system, from the perspective of a software engineer
  • Computer organisation concerns the structure and properties of a computer system, from the perspective of a hardware engineer

The PATP

The Pedagogically Advanced Teaching Processor is a very simple microprocessor. The specifics of it are not examinable, but it is used to build an understanding of microprocessor architecture.

Programmer's model

The PATP has 8 instructions. Each instruction is 1 8-bit word, with the first 3 bits as the opcode and last 5 as the operand, if applicable.

OpcodeMnemonicMacro OperationDescription
000CLEAR[D0] <- 0Set D0 to 0 (and set Z)
001INC[D0] <- [D0] + 1Increment the value in D0 (and set Z if result is 0)
010ADD #v[D0] <- [D0] + vAdd the literal v to D0 (and set Z if result is 0)
011DEC[D0] <- [D0] - 1Decrement the value in D0 (and set Z if result is 0)
100JMP loc[PC] <- locJump unconditionally to address location loc
101BNZ locIf Z is not 0 then [PC] <- locJump to address location loc if Z is not set
110LOAD loc[DO] <- [MS(loc)]Load the 8 bit value from address location loc to D0
111STORE loc[MS(loc)] <- [D0]Write the 8 bit value from D0 to address location loc

This is not many instructions, but it is technically Turing-complete. The other specs of the PATP are:

  • An address space of 32 bytes (the maximum address is 11111)
  • A single 8-bit data register/accumulator D0
  • A CCR with only 1 bit (Z, set when an arithmetic operation has a result of zero)
  • A 5-bit program counter (only 5 bits needed to address whole memory)

Internal Organisation

There are several building blocks that make up the internals of the PATP:

  • The data register D0
    • An 8 bit register constructed from D-type flip-flops
    • Has parallel input and output
    • Clocked

  • The ALU
    • Built around an 8-bit adder/subtractor
    • Has two 8-bit inputs P and Q
    • Capable of
      • Increment (+1)
      • Decrement (-1)
      • Addition (+n)
    • Two function select inputs F1 and F2 which choose the operation to perform
      • 00: Zero output
      • 01: Q + 1
      • 10: Q + P
      • 11: Q - 1
    • An output F(P, Q) which outputs the result of the operation
    • A Z output for the CCR

  • The main system bus
    • Uses 3-state buffers to enable communication

  • The control unit
    • Controls:
      • The busses (enables)
      • When registers are clocked
      • ALU operation
      • Memory acccess
    • Responsible for decoding instructions and issuing micro-instructions
    • Inputs
      • Opcode
      • Clock
      • Z register
    • Outputs
      • Enables
        • Main store
        • Instruction register IR
        • Program counter
        • Data register D0
        • ALU register
      • Clocks
        • Memory address register MAR
        • Instruction register IR
        • Program counter
        • Data register D0
        • ALU register
      • F1 and F2 on the ALU
      • R/W to control bit for main store

All the components come together like so:

Micro and Macro Instructions

There are several steps internally that are required to execute a single instruction. For example, to execute an INC operation:

  • D0 need to be put on the system bus
    • CU enables the three-state buffer for D0
    • [ALU(Q)] <- D0
  • The correct ALU function must be selected
    • F1 = 0, F2 = 1
    • Signals asserted by CU
    • [ALU(F)] <- 01
  • The output from the ALU must be read into the ALU register
    • ALUreg clocked by CU
    • [ALUreg] <- [ALU]
  • D0 reads in the ALU output from the ALU register
    • CU enables the three-state buffer for ALUreg
    • D0 is clocked by CU

Macro instructions are the assembly instructions issued to the processor (to the CU, specifically), but micro instructions provide a low level overview of how data is moved around between internals of the CPU and what signals are asserted internally. The PATP can execute all instructions in 2 cycles. The table below gives an overview of the micro operations required for each macro instruction, along with the macro operations for fetching from main store.

Control Signals

The control unit asserts control signals at each step of execution, and the assertion of these control signals determine how data moves internally. For the PATP:

  • Enable signals are level-triggered
  • Clock signals are falling edge-triggered
  • An output can be enabled onto the main bus and then clocked elsewhere in a single time step
  • ALU timings assume that, if values are enabled at P and Q at the start of a cycle, then the ALU register can be clocked on the falling edge of that cycle
  • MS timings assume that if MAR is loaded during one cycle, then R, W and EMS can be used in the next cycle

The diagram below shows the timing for a fetch taking 4 cycles, and which components are signalled when. Notice which things happen in the same cycle, and which must happen sequentially.

cycleMicro-OpControl Signals
1[MAR] <- [PC]Enable PC, Clock MAR
2[IR] <- [MS(MAR)]Set read for MAR, Enable MS, Clock IR
3[ALU(Q)] <- [PC]Enable PC
3[ALU(F) <- 01]F1 = 0, F2 = 1
3[ALUreg] <- [ALU]Clock ALUreg
4[PC] <- [ALUreg]Enable ALUreg, Clock PC

Control Unit Design

The task of the control unit is to coordinate the actions of the CPU, namely the Fetch-Decode-Execute cycle. It generates the fetch control sequence, takes opcode input, and generates the right control sequence based on this. It can be designed to do this in one of two ways:

  • Hardwired design (sometimes called "random logic")
    • The CU is a combinatorial logic circuit, transforming input directly to output
  • Microprogrammed
    • Each opcode is turned into a sequence of microinstructions, which form a microprogram
    • Microprograms stored in ROM called microprogram memory

Hardwired

  • A sequencer is used to sequence the clock cycles
    • Has clock input and n outputs T1 ... Tn
    • First clock pulse is output from T1
    • Second is output from T2
    • Clock pulse n output from Tn
    • Pulse n+1 output from T1
  • This aligns the operation of the circuit with the control steps
  • Advantages
    • Fast
  • Disadvantages
    • Complex, difficult to design and test
    • Inflexible, cant change design to add new instructions
    • Takes a long time to design
  • This technique is most commonly used in RISC processors and has been since the 80s

  • The control signal generator maps each instruction to outputs
  • The sequencer sequences the outputs appropriately
  • The flip-flop is used to regulate control rounds

Microprogrammed

  • The microprogram memory stores the required control actions for each opcode
  • The CU basically acts as a mini CPU within the CPU
    • Microaddress is a location within microprogram memory
    • MicroPC is the CU's internal program counter
    • MicroIR is the CU's internal microinstruction register
  • The microPC can be used in different ways depending upon implementation
    • Holds the next microaddress
    • Holds the microaddress of microroutine for next opcode
  • When powered initially holds microaddress 0
    • The fetch microprogram
  • Each microinstruction sets the CU outputs to the values dictated the instruction
    • As the microprogram executes, the CU generates control signals
  • After each microinstruction, the microPC is typically incremented, so microinstructions are stepped through in sequence
  • After a fetch, the microPC is not incremented, but is set to the output from the opcode decoding circuit (labelled OTOA in the diagram)
  • After a normal opcode microprogram, the microPC is set back to 0 (fetch)
  • When executing the microprogram for a conditional branch instruction, the microPC value is generated based upon whether the CU's Z input is set

  • Advantages
    • Easy to design and implement
    • Flexible design
    • Simple hardware compared to alternative
    • Can be reprogrammed for new instructions
  • Disadvantages
    • Slower than hardwired
  • Most commonly used for CISC processors

RISC and CISC

In the late 70s-early 80s, it was shown that certain instructions are used far more than others:

  • 45% data movement (move, store, load)
  • 29% control flow (branch, call, return)
  • 11% arithmetic (add, sub)

The overhead from using a microprogram memory also became more significant as the rest of the processor became faster. This caused a shift towards RISC computing. Right now, ARM is the largest RISC computing platform. Intel serve more for backwards compatibility with a CISC instruction set. In an modern intel processor, simplest instructions are executed by a RISC core, more complex ones are microprogrammed.

  • RISC has simple, standard instructions whereas CISC has lots of more complex instructions
    • x86 is often criticised as bloated
  • RISC allows for simpler, faster, more streamlined design
  • RISC instructions aim to be executed in a single cycle
  • CISC puts the focus on the hardware doing as much as possible, whereas RISC makes the software do the work

Multicore Systems

  • The performance of a processor can be considered as the rate at which it executes instructions: clock speed x IPC (instructions per clock).
  • To increase performance, increase clock speed and/or IPC
  • An alternative way of increasing performance is parallel execution
  • Multithreading separates the instruction stream into threads that can execute in parallel
  • A process is an instance of a program running on a computer
    • A process has ownership of resources: the program's virtual address space, i/o devices, other data that defines the process
    • The process is scheduled by the OS to divide the execution time of the processor between threads
    • The processor switches between processes using the stack

CS141

#notacult

Types & Typeclasses

Haskell is a strongly, statically typed programming language, which helps prevent us from writing bad programs.

  • Java, C, Rust - strongly typed
  • Python, Ruby - dynamically typed

Types have many benefits:

  • Describe the value of an expression
  • Prevent us from doing silly things
    • not 7 gives Type Error
  • Good for documentation
  • Type errors occur at compile time

GHC checks types and infers the type of expressions for us. Types are discarded after type checking, and are not available at runtime.

Type notation

We say an expression has a type by writing expression :: type, read as "expression has type".

  • If we can assign a type to an expression, it is "well typed"
  • A type approximates and describes the value of an expression.
42 :: Int
True :: Bool
'c' :: Char
"Cake" :: String
0.5 :: Double
4 + 8 :: Int
2 * 9 + 3 :: Int
True && False :: Bool
"AB" ++ "CD" :: String
even 9 :: Bool

Before writing a definition, it is good practice to write its type.

daysPerWeek :: Int
daysperWeek = 7

Function Types

The types of functions are denoted using arrows ->. The not function is defined as not :: Bool -> Bool, read "not has type bool to bool". It means if you give me a Bool, I will give you back another Bool.

The definition of the not function is shown below.

not :: Bool -> Bool
not True = False
not False = True
not True :: Bool

The last line shows how function application eliminates function types, as by applying a function to a value, one of the types from the function definition is removed as it has already been applied.

The xor function takes two boolean arguments and is defined:

xor :: Bool -> Bool -> Bool
xor False True = True
xor False False = False
xor True True = False
xor True False = True

Applying one argument to a function that takes two is called partial function application, as it partially applies arguments to a function to return another function. This is because all functions in haskell are curried, meaning all functions actually only take one argument, and functions taking more than one argument are constructed from applying multiple functions with one argument.

xor :: Bool -> Bool -> Bool
xor True :: Bool -> Bool -- partially applied function
xor True False :: Bool

Polymorphic Types

What is the type of \x -> x ? Could be:

f :: Int -> Int
f :: Bool -> Bool
f :: Char -> Char

These are all permissible types. To save redifining a function, we can use type variables. Anything with a single lowercase character is a type variable (a in this case).

\x -> x :: a -> a

\x -> x is the identity function, as it returns its argument unchanged. We can also have functions with more than one type variable, to specify that arguments have different types:

const :: a -> b -> a
const x y = x

Tuples

Tuples are a useful data structure

(4, 7) :: (Int, Int)
(4, 7.0) :: (Int, Double)
('a', 9, "Hello") :: (Char, Int, String)

--can nest tuples
((4, 'g'), False) :: ((Int, Char), Bool)

--can also contain functions
(\x -> x, 8.15) :: (a->a, Double)

Functions on pairs. These are all in the standard library

fst :: (a,b) -> a
snd :: (a,b) -> b
swap :: (a,b) -> (b,a)

-- these functions can also be defined by pattern matching
fst (x,y) = x
snd (x,y) = y
swap (x,y) = (y,x)

Type Classes

Type classes are used for restricting polymorphism and overloading functions.

  • The (+) operator probably has type (+) :: Int -> Int -> Int,
    • This is correct, as this typing is permissible
  • What about 1.2 + 3.4?
    • Will raise an error with this definition of (+)
  • Can polymorphism help?
  • (+) :: a -> a -> a
    • This is stupid
    • Allows any types
    • Won't work
  • A type class constraint is needed
  • The actual type is (+) :: Num a => a -> a -> a
    • The Num a => part is the constraint part
    • Tells the compiler that a has to belong to the typeclass Num
  • Type class constraints are used to constrain type variables to only types which support the functions or operators specified by the type class
  • Type class names start with an uppercase character
  • Num is a type class that represents all types which support arithmetic operations

Defining Type Classes

A type class is defined as follows:

class Num a where
    (+) :: a -> a -> a
    (-) :: a -> a -> a
    abs :: a -> a
  • Num is the name of the type class
  • a is the type variable representing it in the method typings
  • The type class contains method signatures for all functions that members of the type class must implement

The type class contains type definitions, but no implementations for the functions. To implement them, we need to tell the compiler which types implement the type class and how they implement the functions in the type class. The Show typeclass tells the compiler that a type can be converted to a string.

-- typeclass definition
class Show a where
    show :: a -> String

-- instance of typeclass for bool type
instance Show Bool where
    show True = "True"
    show False = "False"

The instance definition tells the compiler that Bool is a member of Show, and how it implements the functions that Show defines.

Prelude Type Classes

  • Num for numbers
  • Eq for equality operators == /=
  • Ord for inequality/comparison operators > <= etc
  • Show for converting things to string
  • Many More

The REPL makes extensive use of Show to print things. There are no show instances for function types, so you get an error if you try to Show functions. Typing :i in the REPL gets info on a type class. :i Num gives:

class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
  {-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}
        -- Defined in ‘GHC.Num’
instance Num Word -- Defined in ‘GHC.Num’
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’

Types of Polymorphism

In Java, there are two kinds of polymorphism:

  • Parametric polymorphism
    • (Generics/Templates)
    • A class is generic over certain types
    • Can put whatever type you like in there to make a concrete class of that type
  • Subtype polymorphism
    • Can do class Duck extends Bird
    • Can put Ducks wherever Birds are expected

Haskell has two kinds of polymorphism also:

  • Parametric polymorphism
    • Type variables
    • id :: a -> a
    • Can accept any type where a is
  • Ad-hoc polymorphism
    • Uses type classes
    • double :: Num a => a -> a
    • double x = x * 2

Further Uses of Constraints

An example Show instance for pairs:

instance (Show a, Show b) => Show (a,b) Show where
    show (x,y) = "(" ++ show x ++ ", " ++ show y ++ ")"

The (Show a, Show b) => defines a constraint on a and b that they must both be instances of show for them to be used with this instance. The instance is actually defined on the type (a,b).

Can also define that a typeclass has a superclass, meaning that for a type to be an instance of a typeclass, it must be an instance of some other typeclass first. The Ord typeclass has a superclass constraint of the Eq typeclass, meaning something cant be Ord without it first being Eq. This makes sense, as you can't have an ordering without first some notion of equality.

class Eq a => Ord a where
    (<) :: a -> a -> Bool
    (<=) :: a -> a -> Bool

Default Implementations

Type classes can provide default method implementations. For example, (<=) can be defined using the definition of (<), so a default one can be provided using (==)

class Eq a => Ord a where
    (<) :: a -> a -> Bool
    (<=) :: a -> a -> Bool
    (<=) x y = x < y || x == y
    -- or defined infix
    x <= y = x < y || x == y

Derivable Type Classes

Writing type class instances can be tedious. Can use the deriving keyword to automatically generate them, which does the same as manually defining type class instances.

data Bool = False | True
    deriving Eq
data Module = CS141 | CS118 | CS126
    deriving (Eq, Ord, Show)

Certain other typeclasses can be dervied too, by enabling language extensions within GHC. The extension XDeriveFunctor allows for types to include a deriving Functor statement.

Data Types

How do we make our own data types in haskell? Algebraic data types.

  • Bool is a type
  • There are two values of type Bool
    • True
    • False
data Bool = True | False

A type definition consists of the type name Bool and it's data constructors, or values True | False. A type definition introduces data constructors into scope, which are just functions.

True :: Bool
False :: Bool

We can pattern match on data constructors, and also use them as values. This is true for all types.

not :: Bool -> Bool
not True = False
not False = True

More examples:

data Module = CS141 | CS256 | CS263

data Language = PHP | Java | Haskell | CPP

--for this one, the type name and constructor name are separate names in the namespace
data Unit = Unit

-- this one has no values
data Void

Parametrised Data Constructors

Parameters can be added to a data constructor by adding their types after the constructor's name. The example below defines a type to represent shapes. Remember that data constructors are just functions, and can be partially applied just like other functions.

data Shape = Rect Double Double | Circle Double
Rect :: Double -> Double -> Shape
Circle :: Double -> Shape

-- functions utilising the Shape type

-- constructs a square
square x :: Double -> Shape
square x = Rect x x

-- calculates area of a shape using pattern matching on constructors
area :: Shape -> Double
area (Rect w h) = w * h
area (Circle r) = pi * r * r

isLine :: Shape -> Bool#
isLine (Rect 1 h) = True
isLine (Rect w 1) = True
isLine _ = False

-- examples
area (square 4.0)
=> area (Rect 4.0 4.0)
=> 4.0 * 4.0
=> 16.0

area (Circle 5.0)
=> pi * 5.0 * 5.0
=> pi * 25.0
=> 78.53981...

Parametrised Data Types

The Maybe type is an example of a data type parametrised over some type variable a. It exists within the standard library, defined as data Maybe a = Nothing | Just a. This type is used to show that either there is no result, or some type a.

A function using the Maybe type to perform devision safely, returning Nothing if the divisor is 0, and the result wrapped in a Just if the division can be done.

data Maybe a = Nothing | Just a

safediv :: Int -> Int -> Maybe Int
safediv x 0 = Nothing
safediv x y = Just (x `div y)
-- safediv 8 0 => Nothing
-- safediv 8 4 = Just (8 `div` 4) = Just 2

-- this is included in stdlib for extracting the value using pattern matching
fromMaybe :: a -> Maybe a -> a
fromMaybe x Nothing = x
fromMaybe _ (Just x) = x

Null references were invented in the 1960s ... the guy who invented them called them his "billion dollar mistake". The Maybe type is a good alternative, which makes it clear that a value may be absent. Similar concepts exist in other procedural languages (Swift, Rust)

Recursive Data Types

In Haskell, data types can be defined in terms of themselves. An example definition of the natural numbers is shown below, where a number is either zero, or one plus another number.

data Nat = Zero | Succ Nat

Zero :: Nat
Succ :: Nat -> Nat

one = Succ Zero
two = Succ one
three = Succ two

add :: Nat -> Nat -> Nat
add Zero     m = m
add (Succ n) m = Succ (add n m)

mul :: Nat -> Nat -> Nat
mul Zero     m = Zero
mul (Succ n) m = add m (mul n m)

Another example defining binary trees in terms of themselves. A binary tree consists of subtrees (smaller binary trees). This type is parametrised over some type variable a also.

Data BinTree a = Leaf a | Node (BinTree a) (BinTree a)

--converts a binary tree to a list
flatten :: BinTree a -> [a]
flatten (Leaf x)   = [x]
flatten (Node l r) = flatten l ++ flatten r

-- computes the max depth of the tree
depth :: BinTree a -> Int
depth (Leaf _)   = 1
depth (Node l r) = 1 + max (depth l) (depth r)

Type Aliases

Types can be aliased. For example, String has been an alias of [Char] all along.

type String = [Char]

Another example, defining a Predicate type

type Predicate a = a -> Bool

isEven :: Predicate Int
isEven n = n `mod` 2 == 0

isEven' :: (Eq a, Integral a) => Predicate a
isEven' n = n `mod` 2 == 0

Recursion

Recursion is a way of expressing loops with no mutable state, by defining a function in terms of itself. The classic example, the factorial function. Defined mathematically:

In haskell:

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)

It can be seen how this function reduced when applied to a value:

factorial 2
=> 2 * factorial (2-1)
=> 2 * factorial 1
=> 2 * 1 * factorial (1-1)
=> 2 * 1 * factorial 0
=> 2 * 1 * 1
=> 2

Another classic example, the fibonacci function:

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-1)

In imperative languages, functions push frames onto the call stack every time a function is called. With no mutable state, this is not required so recursion is efficient and can be infinite.

Haskell automatically optimises recursive functions to make execution more efficient:

fac' :: Int -> Int -> Int
fac' 0 m = m
fac' n m = fac' (n-1) (n*m)

This version of the function prevents haskell from building up large expressions:

fac 500
=> fac' 500 1
=> fac' (500-1) (500*1)
=> fac' 499 500
=> fac (499-1) (499 * 500)
=> fac' 498 249500

Notice the pattern for all recursive functions, where there is a recursive case, defining the function in terms of itself, and a base case. Without a base case, the function would recurse infinitely. The cases are usually defined as pattern matches.

Recursion on Lists

Recursion is the natural way to operate on lists in haskell. Defining the product function, which returns the product of all the items in the list:

product :: [Int] -> Int
product [] = 1
product (n:ns) = n * product ns

Here, the base case is the empty list [] and pattern match is used to "de-cons" the head off the list and operate on it (n:ns). The function reduces as follows:

product [1,2,3,4]
=> 1 * product [2,3,4]
=> 1 * 2 * product [3,4]
=> 1 * 2 * 3 * product [4]
=> 1 * 2 * 3 * 4 * product []
=> 1 * 2 * 3 * 4 * 1
=> 24

let and where

let and where clauses can be used to introduct local bindings within a function, which are useful in defining recursive functions. the splitAt function, which splits a list into two at a certain index.

splitAt :: Int -> [a] -> ([a],[a])
splitAt 0 xs = ([],xs)
splitAt n [] = ([],[])
splitAt n (x:xs) = (x:ys, zs)
    where (ys,zs) = splitAt (n-1) xs
-- alternatively
splitAt n xs =
  let
    ys = take n xs
    zs = drop n xs
  in (ys,zs)

let and where can also define functions locally, as everything in haskell is a function.

Higher Order Functions

Higher order functions are functions which operate on functions.

Associativity of functions

Function expressions associate to the right (one argument is applied at a time)

xor a b = (a || b ) && not (a && b)
-- equivalent to
xor = \a -> \b -> (a || b) && not (a && b)
-- equivalent to
xor = \a -> (\b -> (a || b) && not (a && b))

  • All functions in haskell are technically nameless, single-parameter functions
  • Currying allows for functions which return other functions
  • Functions are expressions
    • The body of a function is an expression
  • When a function is applied to an argument it reduces to it's body.

Function application associates to the left:

xor True True
=> (xor True) True
=> ((\a -> (\b -> (a || b) && not (a && b))) True) True
=> (\b -> (True || b) && not (True && b)) True
=> (True || True) && not (True && True)

Function types, however, associate to the right:

xor :: Bool -> Bool -> Bool
xor = \a -> \b -> (a || b) && not (a && b)
--equivalent to
xor :: Bool -> (Bool -> Bool)
xor = xor = \a -> (\b -> (a || b) && not (a && b))

The table below shows how functions application and types associate:

Without ParenthesesWith Parentheses
f x y (f x) y
\x -> \y -> ...\x -> (\y -> ...)
Int -> Int -> IntInt -> (Int -> Int)

Functions as Arguments (map)

Haskell functions can be taken as arguments to other functions. Functions that take/return functions are called higher order functions. An example, increasing every element of a list by one:

incByOne :: [Int] -> [Int]
incByOne xs = [x+1 | x <- xs]
-- or using recursion
incByOne [] = []
incByOne (x:xs) = x+1 : incByOne xs

All this function does is applies the function (+ 1) to every element. This pattern can be generalised using the map function: a function that applies a function given as an argument to every element of a list:

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

Note the type signature of the map function is map :: (a -> b) -> [a] -> [b], meaning the first argument is a function of type (a -> b). Using this to implement incByOne:

incByOne = map (+1)
-- tracing it's evaluation:
incByOne [1,2,3]
=> map (+1) [1,2,3]
=> (1+1) : map (+1) [2,3]
=> (1+1) : (1+2) : map (+1) [3]
=> (1+1) : (1+2) : (1+3) : map (+1) []
=> (1+1) : (1+2) : (1+3) : []
=> [2,3,4]

Effectively, map f [x, y, z] evaluates to [f x, f y, f z]

Sections

Sections are partially applied operators. Operators are functions like any other, and as such can be partially applied, passed as arguments, etc. The addition operator is shown as an example, but the same applies to any binary operator.

(+) :: Num a => a -> a -> a
(+ 4) :: Num a => a -> a
(4 +) :: Num a => a -> a
(+) 4 8 = 4 + 8
(+ 4) 8 = 8 + 4
(4 +) 8 = 4 + 8

Filter

Filter is an example of another higher order function, which given a list, returns a new list which contains only the elements satisfying a given predicate.

filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
    | p x       = x : filter p xs
    | otherwise =     filter p xs

Some examples:

-- remove all numbers less than or equal to 42
greaterThan42 :: (Int -> Bool) -> [Int] -> [Int]
greaterThan42 xs = filter (>42) xs
-- only keep uppercase letters
uppers :: (Char -> Bool) -> String -> String
uppers xs = filter isUpper xs

Curried vs Uncurried

Tuples can be used to define uncurried functions. A function that takes two arguments can be converted to a function that takes an a tuple of two arguments, and returns a single argument/

uncurriedAdd :: (Int, Int) -> Int
uncurriedAdd (x, y) = x + y

There are higher-order functions, curry and uncurry, which will do this for us:

curry :: ((a,b) -> c) -> a -> b -> c
curry f x y = f (x,y)

uncurry :: (a -> b -> c) -> (a,b) -> c
uncurry f (x,y) = f x y

-- examples
uncurriedAdd :: (Int, Int) -> Int
uncurriedAdd = uncurry (+)

curriedAdd :: Int -> Int -> Int
curriedAdd = curry uncurriedAdd

addPairs :: [Int]
addPairs = map (uncurry (+)) [(1, 2), (3, 4)]

Folds

foldr and foldl "collapse" a list by applying a function f to each element in the list in turn, where the first argument is an accumulated value, and the second is the starting value passed. There are several functions which follow this pattern, all reducing a list to a single value using recursion:

-- and together all bools in the list
and :: [Bool] -> Bool
and [] = True
and (b:bs) = ((&&) b) (and bs)

-- product of everything in the list
product :: Num a => [a] -> a
product [] = 1
product (n:ns) = ((*) n) (product ns)

-- length of list
length :: [a] -> Int
length [] = 0
length (x:xs) = ((+) 1) (length xs)

All of these functions have a similar structure, and can be redefined using foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

-- examples
and :: [Bool] -> Bool
and = foldr (&&) True

product :: Num a => [a] -> a
product = foldr (*) 1

length :: [a] -> Int
length = foldr (\x n -> n + 1) 0

In essence, foldr f z [1, 2, 3] is equal to f 1 (f 2 (f 3 z)). foldr folds from right (r) to left, starting by applying the function to the last element of the list first. foldl, however, works in the opposite direction:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

foldl f z [1, 2, 3] is equal to f (f (f z 1) 2) 3. For some functions (commutative ones), there is no difference, but often the choice of which to use is important.

Function Composition

In haskell, functions are composed with the (.) operator, a higher order function defined as:

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)

Function composition is used to chain functions, so instead of f (g (h x)), you can write f.g.h x. An example, defining a function count to count the number of occurrences of an element in a list:

count :: Eq a => a => [a] -> Int
count _ [] = 0
count y (x:xs)
    | y == x    = 1 + count y xs
    | otherwise =     count y xs

--alternatively, using a fold
count y = foldr (\x l -> if y==x then 1+l else l) 0

-- the stdlib can do this
count y x = length (filter (==y) xs)
count y = length . filter (==y) -- using composition

Lazy Evaluation

Evaluation Strategies

How are programs evaluated? There are a number of strategies for evaluating a program. For example, the expression (4+8) * (15 + 16) can be evaluated in different ways:

(4+8) * (15 + 16)
=> 12 * (15+16)
=> 12 * 31
=> 372

-- or

(4+8) * (15 + 16)
=> (4 + 8) * 31
=> 12 * 31
=> 372

The final value when reducing an expression (it cannot be reduced further) is the normal form, 372 in this case. No matter how the expression is reduced, the normal form is the same. Haskell's type system prevents us from writing anything that cannot reduce to normal form.

A sub-expression (anything partially reduced that can still be reduced further) is called a redex, short for reducible expression. Evaluation strategies only matter when there are multiple redexes, otherwise there is only one route we can take to evaluate an expression.

Strict Evaluation

A programming language is strict if the arguments of the function are evaluated before the function is called.

Evaluating fac 500 using a strict method:

fac :: Int -> Int
fac n = fac' n 1

fac' :: Int -> Int -> Int
fac n m = case n of
  0 -> m
  _ -> fac' (n-1) (n*m)

fac 500      -- a redex, function application
=> fac' 500 1   -- another redex
=> fac' (500-1) (500*1)     -- 3 redexes, two multiplications and function application
=> fac' 499 (500*1)     -- two redexes now as 500-1=499 is now in normal form
=> fac' 499 500         -- now only one redex
=> fac' (499-1) (499*500) -- back to 3 redexes
... -- this goes on for a while

Call-by-value means that all function arguments are reduced to their normal forms (values), and then passed as such to the function. The call-by-value strategy is an example of strict evaluation. This is the evaluation strategy used by most programming languages: Java, JS, PHP, C/C++, OCaml, F#, Python, Scala, Swift. Note that some of these are also functional languages.

Haskell, on the other hand, is far superior. It is non-strict: aka lazy.

Call-by-name

A non-strict evaluation strategy by which expressions given to functions as arguments are not reduced before the function call is made.
Expressions are only reduced when their value is needed. Same example as before:

fac 2
=> fac' 2 1  -- still a redex here
=> case 2 of
     0 -> 1
     _ -> fac' (2-1) (2*1)   -- the function call is expanded to its expression
=> fac' (2-1) (2*1) -- left with 3 redexes now
=> case 2-1 of
     0 -> 2*1
     _ -> fac' ((2-1)-1) ((2-1) * (2*1)) -- a lot of redexes, but we don't need to know the value of any except the one in the case expression. this one is evaluated but not the others
=> case 1 of
     0 -> 2*1
     _ -> fac' ((2-1)-1) ((2-1) * (2*1)) -- something actually got evaluated, as we needed it's value. we still have a lot of redexes though

Note how that the same argument ((2-1)) is there 3 times, but it is only evaluated when it is needed. This means that it is evaluated possibly more than once, as it may be needed more than once at different points. With call-by-value (strict), an expression is only reduced once but will only ever be reduced once, but with call-by-name (lazy), expressions may end up being evaluated more than once.

Sharing

Sharing avoids duplicate evaluation. Arguments to functions are turned into local definitions, so that when an expression is evaluated, any expressions that are identical are also evaluated. The same example again, using both call-by-name and sharing:

fac' :: Int -> Int -> Int
fac' n m = case n of
  0 -> m
  _ -> let x = n-1
           y = n*m
       in fac' x y

-- the compiler has replaced the expression arguments with let-bound definitions

fac 2
=> fac' 2 1
=> case 2 of
     0 -> 1
     _ -> let x0 = 2-1
              y0 = 2*1
          in fac' x0 y0 --expressions bound to variables

=> let x0 = 2-1
       y0 = 2*1 -- two redexes
   in fac' x0 y0
=> let x0 = 2-1
       y0 = 2*1
   in case x0 of
        0 -> y0
        _ -> let x1 = x0-1
                 y1 = x0 * y0
            in fac' x1 y1 -- even more redexes and bindings
    -- x0 can be replaced by 1, which evaluates the expresion in all places where x0 is used

Can think of let or where bindings as storing expressions in memory in such a way that we can refer to them from elsewhere using their names.

The combination of call-by-name and sharing is known as lazy evaluation, which is the strategy haskell uses. Nothing is evaluated until it is needed, and work is only ever done once. (Strict evaluation is done sometimes if the compiler decides to, so it is technically non-strict instead of lazy.)

Evaluation in Haskell

An example, using haskell's lazy evaluation strategy:

length (take 2 (map even [1,2,3,4]))
=> length (take 2 (even 1 : map even [2,3,4])) -- check argument is non-empty list
=> length (even 1 : take (2-1) (map even [2,3,4])) -- even 1 cons'd to take 1 of map
=> 1 + length (take (2-1) (map even [2,3,4])) --know length is at least 1, take out
=> 1 + length(take 1 (map even [2,3,4]))
=> 1 + length (take 1 (even 2 : map even [3,4])) --another map call
=> 1 + (1 + length (take (1-1) (map even [3,4])) -- length again
=> 1 + (1 + length []) --take 0 so empty list
=> 1 + 1 + 0 -- return 0
=> 2 -- done

Note how half the map wasn't evaluated, because haskell knew we only cared about the first 2 elements. However this trace doesn't show any of the internal bindings haskell makes for sharing expressions. The compiler does this by transforming the expression:

length (take 2 (map even [1,2,3,4]))
-- becomes
let
  xs = take 2 (map even [1,2,3,4])
in length xs
-- becomes
let
  ys = map even [1,2,3,4]
  xs = take 2 ys
in length xs
-- becomes
let
  ys = map even (1:(2:(3:(4:[]))))
  xs = take 2 ys
in length xs
-- finally
let
  zs4 = 4:[]
  zs3 = 3:zs4
  zs2 = 2:zs3
  zs  = 1:zs2
  ys  = map even zs
  xs  = take 2 ys
in length xs

In this representation, everything is let bound it it's own definition, and nothing is applied except to some literal or to another let bound variable. The representation in memory looks something like this:

These things in memory are called closures. A closure is an object in memory that contains:

  • A pointer to some code that implements the function it represents (not shown)
  • A pointer to all the free variables that are in scope for that definition
    • A free variable is any variable in scope that is not a parameter

The closures form a graph, where the closures all point to each other.

Another example, using map:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

-- removing all syntactic sugar, done by compiler

map = \f -> \arg ->
  case arg of
    []      -> []
    (x: xs) -> let
                 y  = f x
                 ys = map f xs
                in (y:ys)

Using this definition of map to evaluate the expression from before (length (take 2 (map even [1,2,3,4]))):

let
  zs4 = 4:[]
  zs3 = 3:zs4
  zs2 = 2:zs3
  zs  = 1:zs2
  xs  = map even zs
  ys  = take 2 xs
in length ys
-- new closures allocated by map, using 2nd case of map function
let
  zs4 = 4:[]
  zs3 = 3:zs4
  zs2 = 2:zs3
  zs  = 1:zs2
  y0 = even 1
  ys0 = map even zs2 -- new closures
  xs  = y0 : ys -- updated to be a cons cell
  ys  = take 2 xs
in length ys

The graph of closures representing this:

Strictness in Haskell

Things can be evaluated strictly in haskell, if you want. This is prefereable in some cases for performance reasons. The \$! operator forces strict function application. The version of the function below forces the recursive call to be evaluated first.

fac' :: Int -> Int -> Int
fac' 0 m = m
fac' n m = (fac' \$! (n-1)) (n*m)

Infinite Data Structures

Laziness means data structures can be infinite in haskell. This is also facilitated by the lack of call stack, as there is no "max recursion depth" like in strict languages.

from :: Int -> [Int]
from n = n : from (n+1)

This function builds an infinite list of a sequence of Ints, starting with the Int passed. An example usage, showing how lazy evaluation works with it:

take 3 (from 4)
=> take 3 (4 : from 5)
=> 4 : take 2 (from 5)
=> 4 : take 2 (5 : from 6)
=> 4 : 5 : take 1 (from 6)
=> 4 : 5 : take 1 (6 : from 7)
=> 4 : 5 : 6 : take 0 (from 7)
=> 4 : 5 : 6 : []
=> [4,5,6]

The infinite evaluation is short-circuited, as the compiler knows it only needs the first 3 elements.

Reasoning About Programs

Haskell can use normal software testing methods to verify correctness, but because haskell is a pure language, we can do better and formally prove properties of our functions and types.

Natural Numbers

Natural numbers can be defined as data Nat = Z | S Nat in haskell. Alternatively, using mathematical notation, this can be written . Addition can then be defined recursively:

add :: Nat -> Nat -> Nat
add Z     m = m
add (S n) m = S (add n m)

Addition has certain properties which must hold true:

  • Left identity: ∀m :: Nat, add Z m == m
  • Right identity: ∀m :: Nat, add m Z == m
  • Associativity: ∀x y z :: Nat, add x (add y z) == add (add x y) z

These can be proven using equational reasoning, which proves that an equality holds in all cases. Generally, either a property can be proved by applying and un-applying either side of an equation, and/or by induction.

To prove the left identity is easy, as it is an exact match of one of our equations for add:

add Z m
-- applying add
= m

The right identity is a little harder, as we can't just directly apply one of our equations. We can instead induct on m. First, the base case:

add Z Z
-- applying add
= Z

Using the induction hypothesis add m Z = m, we need to show the inductive step holds for S m (m+1):

add (S m) Z
-- applying add
= S (add m Z)
-- applying induction hypothesis
= S m

This proves the right identity. To prove associativity we will again use induction, this time on x. The base case is add Z (add y z):

add Z (add y z)
-- applying add
= add y z
-- un-applying add
= add (add Z y) z

The proof holds for x = Z. Here, the proof was approached from either end to meet in the middle, but written as a single list of operations for clarity. Sometimes it is easier to do this and work from either direction, especially when un-applying functions as it is more natural.

The induction hypothesis is add x (add y z) == add (add x y) z, and can be assumed. We need to prove the inductive step add (S x) (add y z) == add (add (S x) y) z:

add (S x) (add y z)
-- applying add
= S (add x (add y z))
-- applying induction hypothesis
= S (add (add x y ) z)
-- un-applying add
= add (S (add x y)) z
-- un-applying add
= add (add (S x) y) z

This proves associativity.

Induction on Lists

We can induct on any recursive type, including lists: data List a = Empty | Cons a (List a). Using this definition, we can prove map fusion. Map fusion states that we can turn multiple consecutive map operations into a single one with composed functions:

  • map f (map g xs) = map (f.g) xs
    • ∀f :: b -> c
    • ∀g :: a -> b
    • ∀xs :: [a]

The definitions of map and . may be useful:

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)

Map fusion can be proved by induction on xs. The base case is map f (map g []) = map (f.g) []:

map f (map g [])
-- applying map
= map f []
-- applying map
= []
-- un-applying map
= map (f.g) []

Using the induction hypothesis map f (map g xs) = map (f.g) xs, we can prove the inductive case map f (map g (x : xs)) = map (f.g) (x : xs):

map f (map g (x : xs))
-- applying map
= map f (g x : map g xs)
-- applying map
= f (g x) : map f (map g xs)
-- induction hypothesis
= f (g x) : map (f.g) xs
-- un-applying (.)
= (f.g) x : map (f.g) xs
-- un-applying map
= map (f.g) (x : xs)

Proving a Compiler

Given a simple expression language:

data Expr = Val Int | Plus Expr Expr

And a simple instruction set:

data Instr = Push Int | Add
type Program = [Instr]
type Stack = [Int]

We can write an exec function as an interpreter for our instruction set:

exec :: Program -> Stack -> Stack
exec []                    s  = s
exec (Push n : p)          s  = exec p (n : s)
exec (Add    : p) (y : x : s) = exec p (x + y : s)

An eval function to evaluate our expressions:

eval :: Expr -> Int
eval (Val n)    = n
eval (Plus l r) = eval l + eval r

And a comp function as a compiler for our Expr language to our Instr instruction set:

comp :: Expr -> Program
comp (Val n) = [PUSH n]
comp (Plus l r) = comp l ++ comp r ++ [ADD]

Our compiler will be considered correct if for any expression, evaluating it yields the same result as compiling and then executing it:

∀ e :: Expr, s :: Stack . eval e : s == exec (comp e) s

This can be proved by induction on e. The base case for Expr is for Vals, and we want to show that eval (Val n) s == exec (comp (Val n)) s. This time, we start with the RHS:

exec (comp (Val n)) s
-- applying comp
= exec [Push n] s
-- applying exec
= exec [] (n : s)
-- applying exec
= (n : s)
-- unappplying eval
= eval (Val n) s

Our inductive case to be proved is eval (Plus l r) s == exec (comp (Plus l r)) s. Since the Plus constructor has two values of type Expr, there are two induction hypotheses:

  • for l: eval l : s == exec (comp l) s
  • for r: eval r : s == exec (comp r) s
exec (comp (Plus l r)) s
-- applying comp
= exec (comp l ++ comp r ++ [Add]) s
-- distributivity of (++)
= exec (comp l ++ (comp r ++ [Add])) s
-- distributivity lemma
= exec (comp r ++ [Add]) (exec (comp l) s)
-- distributivity lemma
= exec [Add] (exec (comp r) (exec (comp l) s))
-- induction hypothesis
= exec [Add] (exec (comp r) (eval l : s))
-- induction hypothesis
= exec [Add] (eval r : (eval l : s))
-- applying exec
= exec [] ((eval l + eval r) : s)
-- applying exec
= (eval l + eval r) : s
-- un-applying exec
= eval (Plus l r) s

The proof holds, but relies on a lemma proving the distributivity of the exec function, which states that executing a program where a list of instructions xs is followed by a list of instructions ys is the same as first executing xs and then executing ys with the stack that results from executing xs: ∀ xs ys::Program, s::Stack . exec (xs++ys) s == exec ys (exec xs s).

This can be proved by induction on xs. The base case is the empty list []: exec ([] ++ ys) s == exec ys (exec [] s):

exec ys (exec [] s)
-- applying exec
= exec ys s
-- un-applying (++)
= exec ([] ++ ys) s

The induction hypothesis is exec (xs++ys) s == exec ys (exec xs s). The inductive step is exec ((x : xs) ++ ys) s == exec ys (exec (x : xs) s). As x could be either Push x or Add, we perform case analysis on x, first with the case where x = Push n:

exec ys (exec (Push n : xs) s)
-- applying exec
= exec ys (exec xs (n : ns))
-- induction hypothesis
= exec (xs ++ ys) (n : s)
-- un-applying exec
= exec (Push n : (xs ++ ys)) s
-- un-applying (++)
= exec ((Push n : xs) ++ ys) s

The inductive step holds for the Push n case. The Add case:

exec ys (exec (Add : xs) s)
-- assuming stack has at least 2 elements
exec ys (exec (Add : xs) (b : a : s'))
-- applying exec
exec ys (exec xs (a + b : s'))
-- induction hypothesis
exec (xs ++ ys) (a + b : s')
-- un-applying exec
exec (Add : (xs ++ ys)) (b : a : s')
-- un-applying (++)
exec ((Add : xs) ++ ys) (b : a : s')
-- assumption
exec ((Add : xs) ++ ys) s

This proves the inductive case for the Add instruction, and therefore the proof for the distributivity of exec lemma, which supported our initial proof of the correctness of our compiler.

Functors & Foldables

The \$ Operator

The \$ operator is an operator for function application. It has signature:

(\$) :: (a -> b) -> a -> b
f \$ x = f x

At first it doesn't look like it does much, but it is actually defined as infixr 0 meaning it is:

  • An infix operator with right associativity
  • Has the lowest precedence possible.

In contrast, normal function application is left associative and has the highest precedence possible. Practically, this means it can be used where you would otherwise have to use parentheses, to make code a lot cleaner. Some examples:

-- elem finds if an item x is contained in the list xs
elem :: Eq a => a -> [a] -> Bool
elem x xs = not (null (filter (==x) xs))
-- rewritten, without parentheses
elem x xs = not \$ null \$ filter (==x) xs
-- or using function composition (.)
elem x = not . null . filter (==x)

Another example, shown along with a trace of it's reduction:

map (\$ 4) [even, odd]
=> (even $ 4) : map (\$ 4) [odd]
=> (even \$ 4) : (odd \$ 4) : []
=> True : (odd \$ 4) : []
=> True : False : []
=> [True, False]

Foldables

It has already been shown how many examples of recursive functions can be rewritten with a fold. folding is a an example of a useful design pattern in functional programming.

A Trip to Michael's Tree Nursery

Binary trees are recursive data structures, that can be recursively operated on (much like lists). The example below shows a simple definition of a binary tree along with some functions to operate on it.

-- our binary tree type
data BinTree a = Leaf | Node (BinTree a) a (BinTree a)
 deriving Show

-- simple recursive functions
-- how big is the tree?
size :: BinTree a -> Int
size Leaf = 0
size Node (l _ r) = 1 + size l + size r

-- is x contained within the tree?
member:: Eq a => a -> BinTree a -> Bool
member _ Leaf = False
member x (Node l y r) = x == y || member x l || member x r

-- what is the sum of all the Nums in the tree
tsum :: Num a => BinTree a -> a
tsum Leaf =0
tsum (Node l n r) = n + tsum l + tsum r

These are all recursive functions operating on a tree, and can be generalised by defining our own version of a fold for trees, dubbed toldr. Note the similarities between foldr and toldr.

toldr :: (a -> b -> b) -> b -> BinTree a -> b
toldr f z Leaf = z
toldr f z (Node l x r) = f x (toldr f (toldr f z r) l)

tsum :: Num a => BinTree a -> a
tsum = toldr (+) 0

member :: Eq a => a -> BinTree a -> Bool
member x = toldr (\y r -> x==y || r) False

size :: BinTree a -> Int
size = toldr(\_ r -> 1 + r) 0

The Foldable Typeclass

This abstraction does actually exist in the standard libary, as a typeclass. A type can be an instance of Foldable (like lists), which then allows foldr to be used on it.

class Foldable t where
  foldr :: (a -> b -> b) -> b -> t a -> b

-- for lists
-- exists in prelude
instance Foldable [] where
  foldr f z [] = z
  foldr f z (x:xs) = f x (foldr f z xs)

-- for our bintree
instance Foldable BinTree where
  foldr _ z Leaf         = z
  foldr f z (Node l x r) = f x (foldr f (foldr f z r) l)

This instance of Foldable for BinTree can now be used to generalise our functions that operate on it:

sum :: (Foldable t, Num a) => t a -> t
sum = foldr (+) 0

elem :: (Foldable t, Eq a) => a -> t a -> Bool
elem x = foldr (\y r -> x==y || r) False

length :: Foldable t => t a -> Int
length = foldr (\_ r -> 1 + r) 0

These methods are actually part of the Foldable typeclass, so when defining an instance of Foldable on some type, you get them for free, and they are polymorphic over all foldable types.

Foldable is also a derivable typeclass using the language extension -XDeriveFoldable, so all of this can be derived automatically.

Functors

Bringing back our safediv function from previously:

data Maybe a = Nothing | Just a

safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv x y = Just (x `div` y)

divAndAdd :: Int -> Int -> Maybe Int
divAndAdd x y = 5 + safediv x y -- doesn't work, type error

-- using a case statement
divAndAdd x y = case safediv x y of
  Nothing -> Nothing
  Just r -> Just (5+r)
-- bit messy

The pattern of applying a function a value within a Maybe can be generalise. Defining a function pam to do this for us:

pam :: (a -> b) -> Maybe a -> Maybe b
pam _ Nothing = Nothing
pam f (Just x) = Just (f x)

-- much nicer!
divAndAdd :: Int -> Int -> Maybe Int
divAndAdd x y = pam (5+) (safediv x y)

It would be nice if there was some way to generalise the pattern of applying a function to element(s) in a container. The Functor typeclass does this for us. A type is a functor if we can apply a function to it. Lists are functors, as that is what the map function does. Maybe and BinTrees are also functors.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

instance Functor [] where
  fmap = map

instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

instance Functor BinTree where
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Node lr ) = Node (fmap f l) (fmap f r)

Functors can be thought of as "boxes", and when given a function, will apply it to the value in the box, and return the result in the same box. Some examples of definitions using functors:

-- increases all Ints in the "box" by 5
incByFive :: Functor f => f Int -> f Int
incByFive = fmap (+5)

-- applies the odd function to all Ints in the box
odds :: Functor f => f Int -> f Bool
odds = fmap odd

-- redefining using fmap
divAndAdd :: Functor f => Int -> Int -> Maybe Int
divAndAdd x y = fmap (5+) (safediv x y)

Functor is also another typeclass that can be derived by GHC, using the -XDeriveFunctor extension.

The <\$> Operator

An operator that is essentially just an infix version of the fmap function.

infixl 4 <\$>
(<\$>) :: Functor f => (a -> b) -> f a -> f b
(<\$>) = fmap

fmap (replicate 6) (safediv 8 4)
== replicate 6 <\$> safediv 8 4
=> Just [2,2,2,2,2,2]


-- redefining using <\$>
divAndAdd :: Functor f => Int -> Int -> Maybe Int
divAndAdd x y = (5+) <\$> (safediv x y)

Functor Laws

There are certain laws that functors must obey for their properties to hold. A type f is a functor if there exists a function fmap :: (a-> b) -> f a -> f b , and the following laws hold for it:

  • fmap id = id
    • If the values in the functor are mapped to themselves, the result will be an unmodified functor
  • fmap (f.g) = (fmap f) . (fmap g)
    • The fusion law
    • If two fmaps are applied one after the other, the result must be the same as a single fmap which applies the two functions in turn
  • These laws imply that a data structure's "shape" does not change when fmapped

Applicative Functors

Kinds

  • For the compiler to accept a program, it must be well typed
  • Kinds are the "types of types"
  • Types are denoted with expression :: type
    • eg True :: Bool
  • Kinds are denoted the same: type :: kind
    • Bool :: *
  • The compiler infers kinds of types the same way it infers types of expressions
  • * is the kind of types
  • Bool :: * because Bool has no type parameters
    • data Bool = True | False
  • Maybe is parametrised over some type a, so the kind signature Maybe :: * -> * means that if given a type as an argument to the type constructor Just, it will give back some other type of kind *
  • [] :: * -> *
    • [] is the type constructor for lists

Kinds are important when defining typeclasses. Take Functor, for example:

class Functor f where
  fmap :: (a -> b) -> f a-> f b

This definition shows that the type f is applied to one argument (f a), so f :: * -> *

-- Maybe :: * -> *
instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

-- invalid
-- Maybe a :: *
-- As the type is already applied to a
instance Functor (Maybe a) where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

The Either Type

Either is usually used to represent the result of a computation when it could give one of two results. Right is used to represent success, and a is the wanted value. Left is used to represent error, with e as some error code/message.

data Either e a = Left e | Right a
Left :: e -> Either e a
Right :: a -> Either e a

Either has kind * -> * -> *, as it must be applied to two types e and a before we get some other type.

Only types of kind * -> * can be functors, so we need to apply Either to one argument first. The functor instance for Either applies the function to the Right value.

instance Functor (Either e) where
  fmap :: (a -> b) -> Either e a -> Either e b
  fmap f (Left x)  = Left x
  fmap f (Right y) = Right (f y)

The Unit Type ()

  • () is called the unit type
  • () :: ()
    • (), the unit value, has type ()
    • () is the only value of type ()
  • Can be thought of as defined data () = ()
  • Or an empty tuple

Semigroups and Monoids

A type is a semigroup if it has some associative binary operation defined on it. This operator (<>) is the "combine" operator.

class Semigroup a where
  (<>) :: a -> a -> a

instance Semigroup [a] where
  -- (<>) :: [a] -> [a] -> [a]
  (<>) = (++)

instance Semigroup Int where
  -- (<>) :: Int -> Int -> Int
  (<>) = (+)

A type is a monoid if it is a semigroup that also has some identity value, called mempty:

class Semigroup a => Monoid a where
  mempty ::a

instance Monoid [a] where
  -- mempty :: [a]
  mempty = []

instance Monoid Int where
  -- mempty :: Int
  mempty = 0

Applicatives

Applicative Functors are similar to normal functors, except with a slightly different type definition:

class Functor f => Applicative f where
  pure :: a -> f a
  <*>  :: f (a -> b) -> f a -> f b

The typeclass defines two functions:

  • pure just lifts the value a into the "box"
  • <*> (the apply operator) takes some function (a -> b) in a box f, and applies it to a value a in a box, returning the result in the same box.
    • "box" is a rather loose analogy. It is more accurate to say "computational context".

Different contexts for function application:

-- vanilla function application
(\$) :: (a -> b) -> a -> b
-- Functor's fmap
(<\$>) :: Functor f => (a -> b) -> f a -> f b
-- Applicative's apply
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Maybe and Either e are both applicative functors:

instance Applicative Maybe where
  pure x = Just x
  Nothing <*> _ = Nothing
  (Just f) <*> x = f <\$> x

instance Applicative (Either e) where
  pure = Right
  Left err <*> _ = Left err
  Right f  <*> x = f <\$> x

The "context" of both of these types is that they represent error. All data flow in haskell has to be explicit due to its purity, so these types allow for the propagation of error.

Another example of an applicative functor is a list:

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

Every function in the left list is applied to every function in the right:

[f, g] <*> [x, y, z]
=> [f x, f y, f z, g x, g y, g z]

g <\$> [x,y] <*> [a,b,c]
=> [g x, g y] <*> [a,b,c]
=> [g x a, g x b, g x c, g y a, g y b, g y c]

The context represented by lists is nondeterminism, ie a function f given one of the arguments [x, y, z] could have result [f x, f y, f z].

Applicative Laws

Applicative functors, like normal functors, also have to obey certain laws:

  • pure id <*> x = x
    • The identity law
    • applying pure id does nothing
  • pure f <*> pure x = pure (f x)
    • Homomorphism
    • pure preserves function application
  • u <*> pure y = pure (\$ y) <*> u
    • Interchange
    • Applying something to a pure value is the same as applying pure ($ y) to that thing
  • pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
    • Composition
    • Function composition with (.) works within a pure context.

Left and Right Apply

<* and *> are two more operators, both defined automatically when <*> is defined.

const :: a -> b -> a
const x y = x

flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x

(<*) :: Applicative f => f a -> f b -> f a
a0 <* a1 = const <\$> a0 <*> a1

(*>) :: Applicative f => f a -> f b -> f b
a0 *> a1 = flip const <\$> a0 <*> a1

In simple terms *> is used for sequencing actions, discarding the result of the first argument. <* is the same, except discarding the result of the second.

Just 4 <* Just 8
=> const <\$> Just 4 <*> Just 8
=> Just (const 4) <*> Just 8
=> Just (const 4 8)
=> Just 4

Just 4 <* Nothing
=> const <\$> Just 4 <*> Nothing
=> Just (const 4) <*> Nothing
=> Nothing

Just 4 *> Just 8
=> flip const <\$> Just 4 <*> Just 8
=> Just (flip const 4) <*> Just 8
=> Just (flip const 4 8)
=> Just (const 8 4)
=> Just 8

Nothing *> Just 8
=> Nothing

These operators are perhaps easier to understand in terms of monadic actions:

as *> bs = do as
              bs
as *> bs = as >> bs

as <* bs = do a <- as
              bs
              pure a

Example: Logging

A good example to illustrate the uses of applicative functors is logging the output of a compiler. If we have a function comp that takes some Expr type, representing compiler input, and returns some Program type, representing output :

comp :: Expr -> Program
comp (Val n) = [PUSH n]
comp (Plus l r) = comp l ++ comp r ++ [ADD]
-- extending to return a String for a log
comp :: Expr -> (Program, [String])
comp (val n) = ([PUSH n],["compiling a value"])
comp (Plus l r) = (pl ++ pr ++ [ADD], "compiling a plus" : (ml ++ mr))
  where (pl, ml) = comp l
        (pr, mr) = comp r

This is messy and not very clear what is going on. There is a much nicer way to do this, using the Writer type:

-- w is the "log"
-- a is the containing type (the type in the "box")
data Writer w a = MkWriter (a,w)
--type of MkWriter
MkWriter :: (a,w) -> Writer w a
-- kind of Writer type
Writer :: * -> * -> *

instance Functor (Writer w) where
  -- fmap :: (a -> b) -> Writer w a -> Writer w b
  fmap f (MkWriter (x,o)) = MkWriter (f x, o) -- applies the function to the x value

-- a function to write a log
-- generates a new writer with a msg and unit type in it's box
writeLog :: String -> Writer [w] ()
writeLog msg = MkWriter((), [msg])

Using this to redefine comp:

comp :: Expr -> Writer [String] Program
comp (Val n) = MkWriter ([PUSH n], m)
  where (MkWriter (_, m)) = writeLog "compiling a value"
comp (Plus l r) = MkWriter (pl ++ pr ++ [ADD], m ++ ml ++ mr)
  where (MkWriter (pl, ml)) = comp l
        (MkWriter (pr, mr)) = comp r
        (MkWriter (_, m))   = writeLog

This definition of comp combines the output using Writer, but is messy as it uses pattern matching to deconstruct the results of the recursive calls and then rebuild them into the result. It would be nice if there was some way to implicitly keep track of the log messages.

We can define an instance of the Applicative typeclass for Writer to do this. There is the additional constraint that w must be an instance of Monoid, because we need some way to combine the output of the log.

instance Monoid w => Applicative (Writer w) where
  --pure :: a -> Writer w a
  pure x = MkWriter (x, mempty)
  -- <*> Monoid w => Writer w (a -> b) -> Writer w a -> Writer w b
  MkWriter (f,o1) <*> MkWriter (x,o2) = MkWriter (f x, o1 <> o2)
  -- f is applied to x, and o1 and o2 are combined using their monoid instance

Using this definition, the comp function can be tidied up nicely using <*>

comp :: Expr -> Writer [String] Program
comp (Val n) = writeLog "compiling a value" *> pure [PUSH n]
comp (Plus l r) = writeLog "compiling a plus" *>
    ((\p p' -> p ++ p' ++ [ADD]) <\$> comp l <*> comp r)

The first pattern uses *>. Recall that *> does not care about the left result, which in this case is the unit type, so only the result of the right Writer is used, which is the [PUSH n] put into a Writer by pure, with a mempty, or [] as the logged value.

The second pattern applies the anonymous function (\p p' -> p ++ p' ++ [ADD]) to the result of the recursive calls. The lambda defines how the results of the recursive calls are combined together, and the log messages are automatically combined by the definition of <*>. *> is used again to add a log message to the program.

Monads

ṱ̴̹͙̗̣̙ͮ͆͑̊̅h̸̢͔͍̘̭͍̞̹̀ͣ̅͢e̖̠ͫ̒ͦ̅̉̓̓́͟͞ ͑ͥ̌̀̉̐̂͏͚̤͜f͚͔͖̠̣͚ͤ͆ͦ͂͆̄ͥ͌o̶̡̡̝͎͎̥͖̰̭̠̊r̗̯͈̀̚b̢͙̺͚̅͝i̸̡̱̯͔̠̲̿dͧ̈ͭ̑҉͎̮d̆̓̂̏̉̏͌͆̚͝͏̺͓̜̪͓e̎ͯͨ͢҉͙̠͕͍͉n͇̼̞̙͕̮̣͈͓ͨ͐͛̽ͣ̏͆́̓ ̵ͧ̏ͤ͋̌̒͘҉̞̞̱̲͓k͔̂ͪͦ́̀͗͘n͇̰͖̓ͦ͂̇̂͌̐ȯ̸̥͔̩͒̋͂̿͌w̞̟͔̙͇̾͋̅̅̔ͅlͧ͏͎̣̲̖̥ẻ̴̢̢͎̻̹̑͂̆̽ͮ̓͋d̴̪͉̜͓̗̈ͭ̓ͥͥ͞g͊̾̋̊͊̓͑҉͏̭͇̝̰̲̤̫̥e͈̝̖̖̾ͬ̍͢͞

Monads are another level of abstraction on top of applicatives, and allow for much more flexible and expressive computation. Functors => Applicatives => Monads form a hierarchy of abstractions.

The Monad typeclass

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b

  return :: a -> m a
  return = pure

The >>= operator is called bind, and applies a function that returns a wrapped value, to another wrapped value.

  • The left operand is some monad containing a value a
  • the right operand is a function of type a -> m b, ie it takes some a and returns a monad containing something of type b
  • The result is a monad of type b

The operator can essentially be thought of as feeding the wrapped value into the function, to get a new wrapped value. x >>= f unwraps the value in x from it, and applies the function to f to it. Understanding bind is key to understanding monads.

return is just the same as pure for applicatives, lifting the value a into some monadic context.

Some example monad instances:

instance Monad Maybe where
  Nothing >>= _ = Nothing
  Just x  >>= f = f x

instance Monad (Either e) where
  Left l >>= _ = Left l
  Right r >>= f = f r

  pure = Right

instance Monad [] where
  xs >>= f = concat (map f xs)

Monads give effects: composing computations sequentially using >>= has an effect. With the State Monad this effect is "mutation". With Maybe and Either the effect is that we may raise a failure at any step. Effects only happen when we want them, implemented by pure functions.

Monad Laws

For a type to be a monad, it must satisfy the following laws:

  • return a >>= h = h a
    • Left identity
  • m >>= return = m
    • Right identity
  • (m >>= f) >>= g = m >>= (\x -> f x >>= g)
    • Associativity

Example: Evaluating an Expression

A type Expr is shown below that represents a mathematical expression, and an eval function to evaluate it. Note that it is actually unsafe and could crash at runtime due to a div by 0 error. The safediv function does this using Maybe.

data Expr = Val Int | Add Expr Expr | Div Expr Expr

eval :: Expr -> Int
eval (Val n)   = n
eval (Add l r) = eval l + eval r
eval (Div l r) = eval l `div` eval r

safediv :: Int -> Int -> Maybe Int
safediv x 0 = Nothing
safediv x y = Just (x `div` y)

If we want to use safediv with eval, we need to change it's type signature. The updated eval is shown below using applicatives to write the function cleanly and propagate any errors:

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Add l r) = (+) <\$> eval l <*> eval r
eval (Div l r) = safediv <\$> eval l <*> eval r

If any recursive calls return a Nothing, the entire expression will evaluate to Nothing. Otherwise, the <\$> and <*> will evaluate the expression within the Maybe context. However, this is still wrong as the last expression now has type of Maybe (Maybe Int). This can be fixed using >>=. Note the use of lambdas.

eval (Div l r) = eval l >>= \x ->
                 eval r >>= \y ->
                 x `safediv` y

The Expr type can be extended to include a conditional expression, where If Condition True False`.

data Expr = Val Int
          | Add Expr Expr
          | Div Expr Expr
          | If Expr Expr Expr

eval :: Expr -> Maybe Int
eval (Val n)    = Just n
eval (Add l r)  = eval l >>= \x ->
                  eval r >>= \y ->
                  Just (x+y)
eval (Div l r)  = eval l >>= \x ->
                  eval r >>= \y ->
                  x `safediv` y
eval (If c t f) = ifA <\$> eval c <*> eval t <*> eval f
  where ifA b x y = if b /= 0 then x else y
```

With this definition using applicatives, both branches of the conditional branch are evaluated. If there is an error in the false branch, the whole expression will fail. Here, using bind, the semantics are correct.

```haskell
eval' (If c t f) = eval' c >>= \b ->
    if b /= 0 then eval t else eval f
```

## `<*>` vs `>>=`

Bind is a much more powerful abstraction than apply:

```haskell
<*>  :: m (a -> b) -> m a -> m b
(>>=) :: m a -> (a -> m b) -> m b
```

- Apply operates on functions already inside a context
  - This function can't determine anything to do with the context
  - With a `Maybe`, it can't determine if the overall expression returns `Nothing` or not
- Bind takes a function that returns a context, and can therefore can determine more about the result of the overall expression
  - It knows if it's going to return `Nothing`

## `do` Notation

Notice the pattern of `>>=` being used with lambdas a fair amount. This can be tidied up with some nice syntactic sugar, called `do` notation. Rewriting the earlier example:

```haskell
eval :: Expr -> Maybe Int
eval (Val n)   = return n
eval (Add l r) = do
    x <- eval l
    y <- eval r
    return (x+y)
eval (Div l r) = do
    x <- eval l
    y <- eval r
    x `safediv` y
```

This looks like imperative code, but is actually using monads behind the scenes. The arrows bind the results of the evaluation to some local definition, which can then be referred to further down the block.

- A block must always end with a function call that returns a monad -
  - usually `return`, but `safediv` is used too
- If any of the calls within the `do` block shown returns `Nothing`, the entire block will short-circuit to a `Nothing`.

## Example: The `Writer` Monad

The example of `Writer` as an [applicative](./cs141/applicatives#example-logging) instance can be extended to make it a `Monad` instance.

```haskell
data Writer w a = MkWriter (a,w)

instance Functor (Writer w) where
  -- fmap :: (a -> b) -> Writer w a -> Writer w b
  fmap f (MkWriter (x,o)) = MkWriter(f x, o)

instance Monoid w => Applicative (Writer w) where
  -- pure :: Monoid w => a -> Writer w a
  pure x = MkWriter (x, mempty)
  -- <*> :: Monoid w => Writer w (a -> b) -> Writer w a -> Writer w b
  MkWriter (f,o1) <*> MkWriter (x,o2) = MkWriter (f x, o1 <> o2)

instance Monoid w => Monad (Writer w) where
  -- return :: Monoid w => a -> Writer w a
  return = MkWriter (x, mempty) --pure
  (Writer (x, o1)) >>= f = MkWriter (y, o2 <> o1)
                          where (MkWriter (y,o2)) = f x
```

Bind for `Writer` applies the function to the `x` value in the writer, then combines the two attached written values, and return the new value from the result of `f x` along with the combined values.

Now we have a monad instance for the `Writer` monad, we can rewrite our `comp` function with `do` notation:

```haskell
comp' :: Expr -> Writer [String] Program
comp' (Val n)    = do
                   writeLog "compiling a value"
                   pure [PUSH n]
comp' (Plus l r) = do writeLog "compiling a plus"
                   pl <- comp l
                   pr <- comp r
                   pure (pl ++ pr ++ [ADD])
```

Type Level Programming

Type level programming is about encoding more information in our types, so make them more descriptive. The more descriptive types are, the easier it is to avoid runtime errors, as the type checker can do more at compile time.

The GHC language extensions used here are:

  • -XDataKinds
  • -XGATDs
  • -XKindSignatures
  • -XScopedTypeVariables
  • -XTypeFamilies

Type Promotion

As we already know, types have kinds:

  • Bool :: *
  • Maybe :: * -> *
  • [] :: * -> *
  • State :: * -> * -> *

Also recall that we have to partially apply type constructors with kinds greater than * -> * to use them as monads:

-- Maybe :: * -> *
instance Monad Maybe where
    ...

-- State :: * -> * -> *
instance Monad (State s) where
    ...

-- Either :: * -> * -> *
instance Monad Either where
    ... -- type error

instance Monad (Either e) where
    ... -- works

Type Promotion is used to define our own kinds. The DataKinds extension allows for this. Without DataKinds, data Bool = True | False gives us two constructors, True and False. At the three levels in haskell:

  • At the kind-level: *
  • At the type-level Bool
  • At the value-level: True or False

With DataKinds, we also get the following two new types, both of kind Bool:

  • 'True :: Bool
  • 'False :: Bool

The value constructors True and False have been promoted to the type level as 'True and 'False. A new kind is introduced too, Bool instead of just *. We now have booleans at the type level.

DataKinds promotes all value constructors to type constructors, and all type constructors to kinds.

Another example, recursively defined natural numbers. Zero is 0, and Succ Nat is Nat + 1.

data Nat = Zero | Succ Nat

-- values :: types
Zero :: Nat
Succ :: Nat -> Nat

-- types :: kinds
'Zero :: Nat
'Succ :: Nat -> Nat

Generalised Algebraic Data Types

GADTs allow for more expressive type definitions. Normal ADT syntax:

data Bool = True | False
-- gives two values
True :: Bool
False :: Bool

Usually, we define the type and its values, which yields two value constructors. With a GADT, we explicitly specify the type of each data constructor:

data Bool where
  True :: Bool
  False :: Bool

data Nat where
  Zero :: Nat
  Succ :: Nat -> Nat

The example below defines a recursively defined Vector type.

-- Normally
data Vector a = Nil | Cons a (Vector a)

-- GADT
data Vector a where
  Nil  :: Vector a
  Cons :: a -> Vector a -> Vector a

Example: A Safe Vector

The vector definition above can use another feature, called KindSignatures, to put more detail into the type of the GADT definition:

data Vector (n :: Nat) a where
  Nil :: Vector n a
  Cons :: a -> Vector n a -> Vector n a

This definition includes an n to encode the size of the vector in the type. n is a type of kind Nat, as defined above. The values and types were promoted using DataKinds. The type variable n can also be replaced with concrete types:

data Vector (n :: Nat) a where
  Nil :: Vector `Zero a
  Cons :: a -> Vector n a -> Vector (`Succ n) a

-- example
cakemix :: Vector ('Succ ('Succ Zero)) String
cakemix = Cons "Fish-Shaped rhubarb" (Cons "4 large eggs" Nil)

This further constrains the types to make the types more expressive. Now we have the length of the list expressed at type level, we can define a safer version of the head function that rejects zero-length lists at compile time.

vhead :: Vector ('Succ n) a -> a
-- this case will throw an error at compile time as it doesn't make sense
vhead Nil = undefined
vhead (Cons x xs) = x

Can also define a zip function for the vector type that forces inputs to be of the same length. The type variable n tells the compiler in the type signature that both vectors should have the same length.

vzip :: Vector n a -> Vector n b -> Vector n (a,b)
vzip Nil Nil = Nil
vzip (Cons x xs) (Cons y ys) = Cons (x,y) (vzip xs ys)

Singleton types

Singletons are types with a 1:1 correspondence between types and values. Every type has only a single value constructor. The following GADT is a singleton type for natural numbers. The (n :: Nat) in the type definition annotates the type with it's corresponding value at type level. The type is parametrised over n, where n is the value of the type, at type level.

data SNat (n :: Nat) where
    SZero :: SNat 'Zero
    SSucc :: Snat n -> SNat ('Succ n)

-- there is only one value of type SNat 'Zero
szero :: SNat 'Zero
szero = SZero

-- singleton value for one and it's type
sone :: SNat ('Succ 'Zero)
sone = SSucc SZero

stwo :: SNat ('Succ ('Succ Zero))
sone = SSucc sone

There is only one value of each type. The data is stored at both the value and type level.

This can be used to define a replicate function for the vector:

vreplicate :: SNat n -> a -> Vector n a
vreplicate SZero x = Nil
vreplicate (SSucc n) x = Cons x (vreplicate n x)

The length of the vector we want is SNat n at type level, which is a singleton type. This allows us to be sure that the vector we are outputting is the same size as what we told it, making sure this type checks.

Proxy Types & Reification

We are storing data at the type level, which allows us to access the data at compile time and statically check it. If we want to access that data at runtime, for example to find the length of a vector, we need a proxy type. Proxy types allow for turning type level data to values, ie turning a type level natural number (Nat) into an Int. Haskell has no types at runtime (due to type erasure), so proxies are a hack around this.

-- a type NatProxy parametrised over some type a of kind Nat
data NatProxy (a :: Nat) = MkProxy
-- NatProxy :: Nat -> *
-- MkProxy :: NatProxy a

This proxy type is parametrised over some value of type a with kind Nat, but there is never actually any values of type a involved, the info is at the type level. a is a phantom type.

zeroProxy :: NatProxy 'Zero
zeroProxy = MkProxy

oneProxy :: NatProxy ('Succ 'Zero)
oneProxy = MkProxy

These two proxies have the same value, but different types. The Nat type is in the phantom type a at type level.

We can then define a type class, called FromNat, that is parametrised over some type n of kind Nat:

class FromNat (n :: Nat) where
  fromNat :: NatProxy n -> Int

The function fromNat takes a NatProxy, our proxy type, and converts it to an int. Instances can be defined for the two types of Nat to allow us to covert the type level Nats to Ints.

-- instance for 'Zero
instance FromNat 'Zero where
  -- fromNat :: NatProxy 'Zero -> int
  fromNat _ = 0

instance FromNat n => FromNat ('Succ n) where
    fromNat _ = 1 + fromNat (MkProxy :: NatProxy n)

The arguments to these functions are irrelevant, as the info is in the types. The variable n refers to the same type variable as in the instance head, using scoped type variables. This hack allows for passing types to functions using proxies, and the converting them to values using reification.

Type Families

Type families allow for performing computation at the type level. A type family can be defined to allow addition of two type-level natural numbers:

type family Add (n :: Nat) (m :: Nat) :: Nat where
  Add 'Zero m = m
  Add ('Succ n) m = 'Succ (Add n m)

-- alternatively
type family (n :: Nat) + (m :: Nat) :: Nat where
  'Zero   + m = m
  'Succ n + m = 'Succ (n + m)

The type family for (+) is whats known as a closed type family: once it's defined it cannot be redfined or added to. This type family can be used to define an append function for our vector:

vappend :: Vector n a -> Vector m a -> Vector (n+m) a
vappend Nil         ys = ys
vappend (Cons x xs) ys = Cons x (vappend xs ys)

Importing GHC.TypeLits allows for the use of integer literals at type level instead of writing out long recursive type definitions for Nat. This means we can now do:

data Vector (n :: Nat) a where
  Nil :: Vector 0 a
  Cons :: a -> Vector n a -> Vector (n+1) a

vappend Nil          Nil          :: Vector 0 a
vappend (Cons 4 Nil) Nil          :: Vector 1 Int
vappend (Cons 4 Nil) (Cons 8 Nil) :: Vector 2 Int

Associated (Open) Type Families

The definition below defines a typeclass for a general collection of items:

class Collection c where
  empty :: c a
  insert :: a -> c a -> c a
  member :: a -> c a -> Bool

instance Collection [] where
  empty = []
  insert x xs = x : xs
  member x xs = x `elem` xs

However, the list instance will throw an error, as elem has an Eq constraint on it, while the member type from the typeclass doesn't. Another example, defining the red-black tree as an instance of Collection (the tree is defined in one of the lab sheets):

instance Collection Tree where
  empty = empty
  insert x t = insert t x
  member x t = member x t

This will raise two type errors, as both insert and member for the tree need Ord constraints, which Collection doesn't have.

To fix this, we can attach an associated type family to a type class.

class Collection c where
  type family Elem c :: *

  empty :: c
  insert :: a -> c -> c
  member :: a -> c -> Bool

For an instance of Collection for some type c, we must also define a case for c for a type level function Elem, this establishing a relation between c and some type of kind *.

We can now define instance for list and tree, where Eq and Ord constraints are placed in instance definition.

instance Eq a => Collection [a] where
    type Elem [a] = a

    empty = []
    insert x xs = x : xs
    member x xs = x `elem` xs


instance Ord a => Collection (L.Tree a) where
    type Elem (L.Tree a) = a

    empty      = L.Leaf
    insert x t = L.insert t x
    member x t = L.member x t

ES191

A (yet incomplete) collection of notes for ES191 Electrical and Electronic Circuits.
This one aims to be fairly comprehensive, so let me know if you think anything is missing. If you're looking for notes on digital logic, see CS132

Other Useful Resources

Circuit Symbols and Conventions

Circuits model electrical systems

  • Voltage is work done per unit charge
  • Potential difference- difference in electrical potential between two points in an electric field
  • A force used to move charge between two points in space

  • Moving charges produce an electric current
  • Moving charges can do electrical work the same way moving objects do mechanical work

  • Electrical energy is the capacity to do electrical work
  • Electrical power is the rate at which work is done

Resistance

  • Resistance is the opposition to the flow of current
  • Ohm's Law:

  • Resistance is also proportional to the Resistivity of the material
    • and are the length and area of the conductor, respectively.

Sources and Nodes

Everything in a circuit can be modelled as either a source, or a node.

Voltage Sources

  • DC and AC voltage sources
  • DC source has positive and negative terminals
  • Ideal voltage source has 0 internal resistance (infinite conductance)
  • Supplies constant voltage regardless of load
    • This is an assumption, is not the case in reality

Current Sources

  • Ideal current source has infinite resistance (0 conductance)
  • Supplies constant current regardless of load
    • Also an assumption
    • In reality, will have some internal resistance and therefore a maximum power limit

Dependant sources

  • Diamond-shaped
  • Sources depend on values in other parts of the circuit
  • Model real sources more accurately

Nodes

All passive elements: generate no electrical power.

  • Resistors provide resistance/impedance in Ohms ()
  • Inductors provide inductance in Henries ()
  • Capacitors provide capacitance in Farads ()

The voltage rise across an impedance conducting current is in opposition to the flow of current in the impedance.

Basic Conventions

Electrical current always flows from high to low potential.

  • If the direction of the current in a circuit is such that it leaves the positive terminal of a voltage source and enters the negative terminal, then the voltage is designated as negative
  • If the direction of the current is such that it leaves the negative and enters the positive, then the voltage is positive
    • The sign of the loop current is the terminal that it flows into

The power absorbed/produced by a source is .

  • A voltage source is absorbing power if it is supplying a negative current
  • A voltage source is producing power if it is supplying a positive current

The power dissapated in a resistor is .

Resistors in series and parallel

Resistors in series:

Resistors in parallel:

Resistors dissipate electrical power, so there is a drop in voltage accross them, in the direction of current flow. Therefore, the voltage rise is in opposition to the direction of current

Voltage dividers

Using two resistors to divide a voltage

In the general case:

Current Dividers

Similar deal to voltage divider

Nodal Analysis

Kirchhoff's Current Law

The sum of currents entering a node is equal to the sum of currents leaving a node.

  • Currents flowing into a node are denoted as negative
  • Currents flowing out of a node are denoted positive
  • The sum of currents around a node must always be 0

Nodal Analysis

A technique used to analyse circuits to calculate unknown quantities. Allows the voltage at each circuit node to be calculated, using KCL.

An important point to remember is that the bottom of any circuit diagram is ground (0V), by convention.

Steps

  • Choose 1 node as the reference node
  • Label any remaining voltage nodes
  • Substitute any known voltages
  • Apply KCL at each unknown node to form a set of simultaneous equations
  • Solve simultaneous equations for unknowns
  • Calculate any required values (usually currents)

Generally speaking, there will be a nodal equation for each node, formed using KCL, and then these equations will solve simultaneously.

Example

Calculate the voltages at nodes and .

There are 4 currents at

  • Flowing from 15V source to accross 2 resistor
  • Flowing from to ground accross 16 resistor
  • Flowing between and accross 7 resistor
  • 5A, from current source

Each current is calculated using ohm's law, which gives the following nodal equation:

When the direction of each current is not known it is all assumed to be positive, and the voltage at the node is labelled as postive, with any other voltages being labelled as negative. Similar can be done for node :

We now have two equations with two unknowns, which can easily be solved.

Admittance Matrices

The system of equations above can also be represented in matrix form

This matrix equation always takes the form .

is known as the Admittance Matrix.

Calculating Power Dissapated

Sometimes, it is required that the power dissapated by voltage/current sources is calculated. For example, calculate the power supplied by the current sources in the following:

KCL at node :

KCL at node :

KCL at node :

From the node voltages, the power dissapated in the sources can be calculated. In the 2A source:

And in the 3A source:

Note that the voltage accross the current source is always calculated as the node the current is flowing to, minus the node the current is flowing from, ie (to - from). This makes the sign correct so it is known whether the source is delivering or absorbing power. If the direction of the current source oppose the direction of the voltage rise, it will be absorbing power..

If correct, the total power delivered to the circuit will equal the total dissapated. This calculation can be done to check, if you're bothered.

Dependant Sources

Some circuits contain current/voltage sources which are dependant upon other values in the circuit. In the example below, a current is assumed between the two nodes where the dependant voltage source is.

Calculate the power dissipated by the 50 resistor, and the power delivered by the current source.

At Node :

At Node :

We have two equations in 3 unknowns, so another equation is needed. Using :

These can be equated about to give

This system of equations solves to give , and .

Therefore,

  • The power delivered by the current source
  • The power dissapated by the 50 resistor is

Mesh Analysis

Achieves a similar thing to nodal analysis, using Kirchhoff's voltage law, and meshes instead of nodes.

Kirchhoff's Voltage Law

The sum of voltages around a closed loop always equals zero

Sign convention

  • If voltage rise and current in a voltage source are in the same direction, the voltage is denoted as negative
  • If voltage rise and current are in opposite direction, voltage is positive
  • In a resistor, current opposes voltage rise

Steps

  • Identify meshes (loops) (always clockwise) and assign currents etc to those loops
  • Apply KVL to each mesh to generate system of equations
  • Solve equations

Where there are elements that are part of multiple meshes, subtract the currents of the other meshes from the mesh currently being considered to consider the total current through that circuit element.

Example

There are three meshes in this circuit, labelled , , .

For :

For :

For :

This forms a system of equations:

Solving yields , , and .

Impedance Matrices

Similar to how systems of equations from nodal analysis form admittance matrices, mesh analysis forms impedance matrices which describe the circuit being analysed. The matrix equation takes the form . As an example, the matrix equation for the system above is:

Therefore, the impedance matrix for the system is:

Another Example

Determine the currents in the circuit shown below:

Loop 1:

Loop 2:

Where there is a current source, a voltage is assumed accross it.

Loop 3:

There are now 3 equations with 4 unknowns. However, it can be seen from the diagram that (the direction of the current source opposes our clockwise current), so the system can be solved as follows:

Example with dependant sources

Calculate the power dissapated in the 4 resistor and the power delivered/absorbed by the current dependant voltage source.

KVL round :

KVL round :

KVL round :

, so this can be substituted into equation 3 to obtain a fourth equation:

The system of equations then solves: