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
Type | Sign | Exponent | Mantissa | Bias |
---|---|---|---|---|
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:
Sign | Biased Exponent | Normalised Mantissa |
---|---|---|
0 | 1000 0010 | 100011 |
Float to Decimal
Starting with the value 0x41C80000 = 01000001110010000000000000000000:
Sign | Biased Exponent | Normalised Mantissa |
---|---|---|
0 | 1000 0011 | 1001 |
- 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
Exponent | Mantissa | Value |
---|---|---|
0 | 0 | |
255 | 0 | |
0 | not 0 | denormalised |
255 | not 0 | NaN |
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()
- This can be elided, and the default constructor is called
Access Modifiers
Access modifiers apply to methods and member variables.
private
: only the members of the class can seepublic
: anyone can seeprotected
: 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
- A class must be declared
- 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, thecatch
block will be executedcatch
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 recoverableException
, 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
- Wrap the possibly exception-raising code in a
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
andArrayIndexOutOfBoundsException
- ie
- 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
andgetMessage
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
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 positionp
- ie
- 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
- Does linear search of the list to see if key already exists
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 asM[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:
- Hash code
-
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 withdefunct
and returnv
- Else, return
null
- Search for an entry with key
Double Hashing
- Double hashing uses two hash functions
h()
andf()
- 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 ofB
- Called when the element of
bIsLess
- Called when the element of
B
is less than the element ofA
- Called when the element of
bothEqual
- Called when the element of
A
is equal to the element ofB
- Called when the element of
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 SbIsLess
adds b into SbothEqual
adds a (or b) into S
- Intersection
aIsLess
andbIsLess
do nothingbothEqual
adds a (or b) into S
- Difference
aIsLess
adds a into SbIsLess
andbothEqual
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 itemKey
is what is used to defined the priority of the item in the queueValue
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
- or
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 theEntry(key,value)
to the list- time
removeMin()
andmin()
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 theEntry(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()
andmin()
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
- An
Insertion
- To insert a node
z
into a heap, you insert the node after the last node, makingz
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
andparent(z)
- Swap
- While
- 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 nodew
- 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
- Swap
- While
- 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 childq
,f(p) = 2*f(q)+1
- If
p
is the right childq
,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
Search
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
- A circular sequence of alternating vertices and edges
- 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
- A spanning tree is not unique unless the graph is a tree
Depth First Search
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
- If has not been visited then
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.
Breadth First Search
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
- If is not 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
A | f |
---|---|
0 | 1 |
1 | 0 |
AND
A | B | f |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
OR
A | B | f |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
XOR
A | B | f |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
NAND
A | B | f |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
NOR
A | B | f |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
X-NOR
A | B | f |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
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.
A | B | C | P | Q | R | f |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |
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.
A | B | C | f |
---|---|---|---|
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
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:
Name | AND form | OR 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
A | B | f |
---|---|---|
0 | 0 | a |
0 | 1 | b |
1 | 0 | d |
1 | 1 | c |
- 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.
A | B | Sum | Carry |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1-Bit Full Adder
- Adds 2 bits plus carry bit, outputting the result and a carry bit.
Carry in | A | B | Sum | Carry out |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 1 |
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
- Active low means that 0 = active, and 1 = inactive
- It is important to be aware of this, as ins and outs must comform to the same standard
0 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 0 |
- 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
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 1 |
Multiplexers & De-Multiplexers
Multiplexers have multiple inputs, and then selector inputs which choose which of the inputs to put on the output.
Y | ||
---|---|---|
0 | 0 | |
0 | 1 | |
1 | 0 | |
1 | 1 |
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
0 | 0 | A | 1 | 1 | 1 |
0 | 1 | 1 | A | 1 | 1 |
1 | 0 | 1 | 1 | A | 1 |
1 | 1 | 1 | 1 | 1 | A |
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
Q | P | ||
---|---|---|---|
0 | 0 | X | X |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 1 | X | X |
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 | |||
---|---|---|---|
0 | 0 | ||
0 | 1 | ||
1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
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
- PAL - Programmable Array Logic
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
- Control Unit (CU)
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:
RLT | Meaning |
---|---|
[MAR] <- [PC] | Move contents of PC to MAR |
[PC] <- [PC] + 1 | Increment 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
orADD
- 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 nameORG
(Origin) indicates where to load the program in memoryDS
(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 unconditionallyBEQ
- branch if equal
- System Control
- Logical
- Instructions are also specified with their data type,
.b
for byte,.w
for word,.l
for longmove.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 SubroutineRTS
- 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 stackRTS
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 Type | Category | Erasure | Write Mechanism | Volatility |
---|---|---|---|---|
Random Access Memory (RAM) | Read-Write | Electronically, at byte-level | Electronically written | Volatile |
Read Only Memory (ROM) | Read only | Not possible | Mask Written | Non-volatile |
Programmable ROM (PROM) | Read only | Not possible | Electronically written | Non-volatile |
Erasable PROM (EPROM) | Read (mostly) | UV light at chip level | Electronically written | Non-volatile |
Electrically Erasable PROM (EEPROM) | Read (mostly) | Electronically, at byte-level | Electronically written | Non-volatile |
Flash Memory | Read (mostly) | Electronically, at byte-level | Electronically written | Non-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
- Even parity
- 7 bit ascii for
A
is0100 0001
- With even parity -
0100 0001
- Odd parity -
1100 0001
- With even parity -
- 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
- Have to give up some memory
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
- Interrupt Request (IRQ)
- 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
- Cycle stealing
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.
Opcode | Mnemonic | Macro Operation | Description |
---|---|---|---|
000 | CLEAR | [D0] <- 0 | Set D0 to 0 (and set Z ) |
001 | INC | [D0] <- [D0] + 1 | Increment the value in D0 (and set Z if result is 0) |
010 | ADD #v | [D0] <- [D0] + v | Add the literal v to D0 (and set Z if result is 0) |
011 | DEC | [D0] <- [D0] - 1 | Decrement the value in D0 (and set Z if result is 0) |
100 | JMP loc | [PC] <- loc | Jump unconditionally to address location loc |
101 | BNZ loc | If Z is not 0 then [PC] <- loc | Jump to address location loc if Z is not set |
110 | LOAD loc | [DO] <- [MS(loc)] | Load the 8 bit value from address location loc to D0 |
111 | STORE 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
andQ
- Capable of
- Increment (+1)
- Decrement (-1)
- Addition (+n)
- Two function select inputs
F1
andF2
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
- Memory address register
F1
andF2
on the ALUR
/W
to control bit for main store
- Enables
- Controls:
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.
cycle | Micro-Op | Control 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
- Has clock input and n outputs
- 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
givesType 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
(+)
- 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 typeclassNum
- The
- 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 classa
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 numbersEq
for equality operators==
/=
Ord
for inequality/comparison operators>
<=
etcShow
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
Duck
s whereverBird
s are expected
- Can do
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 Parentheses | With Parentheses |
---|---|
f x y | (f x) y |
\x -> \y -> ... | \x -> (\y -> ...) |
Int -> Int -> Int | Int -> (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 Int
s, 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 Val
s, 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
. fold
ing 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 BinTree
s 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
fmap
s are applied one after the other, the result must be the same as a singlefmap
which applies the two functions in turn
- These laws imply that a data structure's "shape" does not change when
fmap
ped
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
- eg
- 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 typesBool :: *
becauseBool
has no type parametersdata Bool = True | False
Maybe
is parametrised over some typea
, so the kind signatureMaybe :: * -> *
means that if given a type as an argument to the type constructorJust
, 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 valuea
into the "box"<*>
(the apply operator) takes some function (a -> b
) in a boxf
, and applies it to a valuea
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 apure
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 somea
and returns a monad containing something of typeb
- 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
orFalse
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 Nat
s to Int
s.
-- 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
- https://www.khanacademy.org/science/electrical-engineering/ee-circuit-analysis-topic/circuit-elements/a/ee-sign-convention
- https://spinningnumbers.org/
- https://www.electronics-tutorials.ws/opamp/opamp_1.html
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: