RustySpigot
software solutions
Computer Science » Notes » Computer Science Notes
Computer Science Notes
The following notes on Computer science were made my myself as revision, and are taken largely from Wikipedia and Lecture notes.
Part IB Computer Science
Revision Notes
Mainly from lecture notes and Wikipedia.
Last updated 21/05/07
Table of Contents
Part IB Computer Science................................................................................................................ 1
Revision Notes.............................................................................................................................. 1
Examinations................................................................................................................................. 8
Lecture Courses............................................................................................................................ 9
Algorithms II ................................................................................................................................ 10
Syllabus................................................................................................................................... 10
Computer Design ....................................................................................................................... 11
Syllabus................................................................................................................................... 11
CISC & RICS.......................................................................................................................... 13
Register Files......................................................................................................................... 13
Load and Store....................................................................................................................... 13
Example: Iterative Fibonacci in ARM................................................................................... 13
Virtual Addresses................................................................................................................... 14
Real and Protected Mode..................................................................................................... 16
The Java Virtual Machine (JVM)........................................................................................... 17
Memory Hierarchy.................................................................................................................. 17
Cache Principles.................................................................................................................... 17
Dyadic (2 part) Instruction Encoding.................................................................................... 18
ARM Thumb Code................................................................................................................. 19
MIPS (Microprocessor without Interlocked Pipeline Stages)............................................ 19
Pipelines................................................................................................................................. 19
The Classic RISC Pipeline.................................................................................................... 21
Load Delay Slots.................................................................................................................... 21
Exception Handling in Pipelines........................................................................................... 21
Instruction Replays................................................................................................................. 22
Parallel Communication........................................................................................................ 22
Serial Communication........................................................................................................... 22
RS232..................................................................................................................................... 22
USB......................................................................................................................................... 22
Concurrent Systems and Applications .................................................................................... 23
Syllabus................................................................................................................................... 23
Java Revision......................................................................................................................... 25
If B extends A.......................................................................................................................... 26
Abstract methods................................................................................................................... 27
Static modifier........................................................................................................................ 27
Interfaces................................................................................................................................. 27
Nested classes/interfaces..................................................................................................... 27
Design patterns...................................................................................................................... 27
Reflection................................................................................................................................ 30
Serialization............................................................................................................................ 31
Swing follows a model-view-controller................................................................................. 31
Components and Containers................................................................................................ 31
javax.accessibility................................................................................................................... 32
Garbage Collection................................................................................................................ 32
Finalizers................................................................................................................................. 33
Reference Objects................................................................................................................. 33
Java Native Interface.............................................................................................................. 34
Class Loaders........................................................................................................................ 34
Concurrency............................................................................................................................ 35
Threads................................................................................................................................... 35
Safety....................................................................................................................................... 35
Liveness.................................................................................................................................. 35
Shared data............................................................................................................................ 36
Mutual Exclusion Locks......................................................................................................... 36
Synchronized.......................................................................................................................... 36
Deadlock................................................................................................................................. 36
Deadlock Detection............................................................................................................... 37
Condition Variables............................................................................................................... 37
Multiple Reader, Single Writer example.............................................................................. 39
First Come First Server example......................................................................................... 39
Compare and Swap (CAS)................................................................................................... 40
Semaphores........................................................................................................................... 40
Transactions........................................................................................................................... 45
ECAD .......................................................................................................................................... 52
Syllabus................................................................................................................................... 52
Floating-Point Computation ...................................................................................................... 54
Syllabus................................................................................................................................... 54
IEEE Floating point................................................................................................................ 55
Definitions............................................................................................................................... 55
Errors....................................................................................................................................... 55
Logic and Proof .......................................................................................................................... 58
Syllabus................................................................................................................................... 58
Prolog .......................................................................................................................................... 60
About Prolog........................................................................................................................... 61
Uses of Prolog........................................................................................................................ 61
Creating a Program............................................................................................................... 61
Key commands....................................................................................................................... 61
Asking a question................................................................................................................... 61
Goal finding............................................................................................................................. 61
Objects.................................................................................................................................... 61
Backtracking........................................................................................................................... 62
Software Engineering ................................................................................................................ 63
Syllabus................................................................................................................................... 63
Introduction.............................................................................................................................. 65
Rates of Software Engineering Failure................................................................................ 65
Stages in the Software Life Cycle........................................................................................ 66
Links & Resources................................................................................................................. 67
Validation and Verification.................................................................................................... 67
The Spiral Model.................................................................................................................... 70
Brooks Law............................................................................................................................. 71
Critical Software..................................................................................................................... 71
Particular Problems of Large Systems................................................................................ 72
The Capability Maturity Model.............................................................................................. 73
Hazards................................................................................................................................... 73
Documentation....................................................................................................................... 74
Testing..................................................................................................................................... 74
Alternative Philosophies and Extreme Programming........................................................ 76
C and C++ .................................................................................................................................. 78
History...................................................................................................................................... 79
Abstract................................................................................................................................... 79
Hello World.............................................................................................................................. 79
Basic Types............................................................................................................................ 79
Variables................................................................................................................................. 80
Operators................................................................................................................................ 80
Functions................................................................................................................................. 81
The Pre-Processor................................................................................................................. 81
Pointers................................................................................................................................... 82
Structures................................................................................................................................ 82
C++............................................................................................................................................... 83
Major Updates........................................................................................................................ 83
Calling Functions.................................................................................................................... 83
Classes................................................................................................................................... 84
Exceptions.............................................................................................................................. 84
Templates............................................................................................................................... 84
Compiler Construction................................................................................................................ 85
Syllabus................................................................................................................................... 85
Compiler Construction ............................................................................................................... 85
Languages.............................................................................................................................. 87
From old notes........................................................................................................................ 88
Other notes.............................................................................................................................. 92
Important notes (new)............................................................................................................. 97
Compilation as a sequence of transformations ................................................................. 97
Front-end................................................................................................................................. 97
Middle End.............................................................................................................................. 98
Back End................................................................................................................................. 98
Computation Theory ................................................................................................................ 108
Hilberts Decision Problem.................................................................................................. 110
What is an algorithm?.......................................................................................................... 110
The Halting Problem............................................................................................................ 110
Diophantene Equations....................................................................................................... 110
Notation................................................................................................................................. 110
Register Machines............................................................................................................... 111
Coding Register as Numbers............................................................................................. 112
Informal Definition of a Turing Machine............................................................................. 115
Church-Turing Thesis........................................................................................................... 116
Primitive Recursive Functions............................................................................................ 117
Partial recursive functions................................................................................................... 119
Ackermann's Function......................................................................................................... 120
Recursive and recursively enumerable sets...................................................................... 120
Computer Graphics and Image Processing ......................................................................... 122
What is an image?............................................................................................................... 124
The eye.................................................................................................................................. 124
Illuminants.............................................................................................................................. 124
Munsells Colour Classification........................................................................................... 124
XYZ Colour Space............................................................................................................... 125
Luv, Lab Colour Space........................................................................................................ 125
RGB Space.......................................................................................................................... 125
CMYK Space........................................................................................................................ 125
Sampling Resolution and Quantization.............................................................................. 125
The frame buffer................................................................................................................... 126
Cathode Ray Tubes (CRT)................................................................................................. 126
Liquid Crystal Displays........................................................................................................ 127
Plasma Displays.................................................................................................................. 128
Digital Micro mirror Devices............................................................................................... 128
Printers.................................................................................................................................. 128
Greyscale printing................................................................................................................ 128
Drawing a Straight Line....................................................................................................... 128
Midpoint line drawing algorithmic....................................................................................... 130
Bezier Cubes........................................................................................................................ 131
Overhausers Cubic.............................................................................................................. 132
Douglas & Pucker's algorithm............................................................................................ 132
Clipping................................................................................................................................. 132
Scanline Polygon Fill Algorithm.......................................................................................... 133
Sutherland-Hodgman Polygon Clipping I.......................................................................... 133
Homogeneous 2d co-ordinates.......................................................................................... 133
Matrix transformations......................................................................................................... 133
Bounding boxes................................................................................................................... 135
Bit block transfer (BitBit)..................................................................................................... 135
Typefaces............................................................................................................................. 135
Viewing Co-ordinates.......................................................................................................... 135
Bezier Patches..................................................................................................................... 139
3D line drawing.................................................................................................................... 139
Depth sort polygon drawing............................................................................................... 140
Binary Space-Partitioning trees......................................................................................... 140
Z-buffering............................................................................................................................. 140
Anti-aliasing.......................................................................................................................... 141
Reflective surfaces............................................................................................................... 141
Phong shading..................................................................................................................... 142
Ray tracing............................................................................................................................ 142
Sampling texture space: interpolation methods............................................................... 143
GIF......................................................................................................................................... 143
JPEG..................................................................................................................................... 143
Concepts in Programming Languages ................................................................................. 144
Concepts............................................................................................................................... 146
Calling/Passing by Value/Name......................................................................................... 146
Types..................................................................................................................................... 147
Object Orientated Programming........................................................................................ 149
Comparison of Languages................................................................................................. 150
Major advances in Languages........................................................................................... 151
Fortran................................................................................................................................... 151
Lisp........................................................................................................................................ 152
Algol....................................................................................................................................... 153
Pascal................................................................................................................................... 154
BCPL..................................................................................................................................... 154
C............................................................................................................................................ 155
Introduction............................................................................................................................ 155
Simula................................................................................................................................... 155
Small Talk............................................................................................................................. 156
Java....................................................................................................................................... 157
C#.......................................................................................................................................... 157
Simplicity............................................................................................................................... 157
Digital Communication I .......................................................................................................... 159
Multiplexing........................................................................................................................... 162
Naming, Addressing and Routing...................................................................................... 164
ARP ...................................................................................................................................... 164
Foundations of Functional Programming .............................................................................. 168
Mathematical Methods for Computer Science ..................................................................... 169
Probability ................................................................................................................................. 170
Relationship to set theory.................................................................................................... 172
Events.................................................................................................................................... 172
Random Variables............................................................................................................... 172
Rules of Probability.............................................................................................................. 173
Bayes Theorem.................................................................................................................... 173
Semantics of Programming Languages ............................................................................... 175
Artificial Intelligence I ............................................................................................................... 176
Requirements....................................................................................................................... 178
Agents................................................................................................................................... 178
Solving Problems by Searching......................................................................................... 180
Informed Search and Exploration....................................................................................... 181
Constraint Satisfaction Problems...................................................................................... 182
Games................................................................................................................................... 183
Planning................................................................................................................................ 184
Learning from Observation................................................................................................. 185
Knowledge in Learning........................................................................................................ 185
Complexity Theory ................................................................................................................... 190
Compiler Construction............................................................................................................. 192
Syllabus................................................................................................................................. 192
Languages............................................................................................................................ 194
From old notes..................................................................................................................... 195
Important notes (new).......................................................................................................... 206
Compilation as a sequence of transformations ............................................................... 206
Front-end............................................................................................................................... 206
Middle End............................................................................................................................ 207
Back End.............................................................................................................................. 207
Databases ................................................................................................................................ 214
GROUP BY Example (Copied from W3Schools.com).................................................... 218
Economics................................................................................................................................. 220
Why Every Economist Should Learn Some Auction Theory................................................ 227
Glossary..................................................................................................................................... 229
Software patents - Obstacles to software development....................................................... 230
Introduction to Security ............................................................................................................ 231
Diffie-Hellman key exchange.............................................................................................. 236
ElGamal Encryption............................................................................................................. 236
ElGamal signature............................................................................................................... 236
Public-key infrastructure...................................................................................................... 237
Identification and entity authentication............................................................................... 237
Authentication Protocols..................................................................................................... 237
Discretionary Access Control............................................................................................. 238
Elevated Rights.................................................................................................................... 239
Windows NT/2000/XP access control............................................................................... 240
Mandatory Access Control Policies................................................................................... 240
Bell Model............................................................................................................................. 240
Covert Channel Problem..................................................................................................... 241
Trusted Computing Base.................................................................................................... 241
Stack overflow attack........................................................................................................... 241
Examinations
| 4th June | 5th June | 6th June | 7th June |
| Paper 3 | Paper 4 | Paper 5 | Paper 6 |
 |
 |
||
Lecture Courses
| Course | Exam Q's | Lectures | Exam Q's/ Lectures |
| Floating Point Computation | 1 | 4 | 0.25 |
| Introduction to Security | 2 | 8 | 0.25 |
| Concepts In Programming Languages | 2 | 8 | 0.25 |
| ECAD | 1 | 4 | 0.25 |
| Graphics And Image Processing | 3 | 16 | 0.1875 |
| Probability | 2 | 12 | 0.166666667 |
| Mathematical Methods for CS | 2 | 12 | 0.166666667 |
| Computation Theory | 2 | 12 | 0.166666667 |
| Artificial Intelligence I | 2 | 12 | 0.166666667 |
| Compiler Construction | 3 | 18 | 0.166666667 |
| Algorithms II | 1 | 6 | 0.166666667 |
| Software Engineering | 1 | 6 | 0.166666667 |
| Digital Communications I | 2 | 12 | 0.166666667 |
| Databases | 2 | 12 | 0.166666667 |
| Logic And Proof | 2 | 12 | 0.166666667 |
| Foundations of Func. Programming | 2 | 12 | 0.166666667 |
| Semantics of Programming Language | 2 | 12 | 0.166666667 |
| Complexity Theory | 2 | 12 | 0.166666667 |
| Economics and Law | 1 | 8 | 0.125 |
| C and C++ | 1 | 8 | 0.125 |
| Concurrent Systems and Applications | 3 | 24 | 0.125 |
| Prolog | 1 | 8 | 0.125 |
| Computer Design | 2 | 16 | 0.125 |
Algorithms II
Syllabus
Aims
The aim of this course is to give further insights into the design and analysis of non-trivial algorithms through the discussion of several complex algorithms in the fields of graphs and computer graphics, which are increasingly critical for a wide range of applications.
Lectures
· Graph algorithms. Graph representations. Breadth-first and depth-first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms. Shortest paths. Bellman-Ford and Dijkstra algorithms. Maximum flow. Ford-Fulkerson method. Matchings in bipartite graphs. [Ref: Ch 22, 23, 24, 25, 26] [4-5 lectures]
· Geometric algorithms. Intersection of segments. Convex hull: Graham's scan, Jarvis's march. [Ref: Ch 33] [1-2 lectures]
Objectives
At the end of the course students should
· have a good understanding of how several elaborate algorithms work
· have a good understanding of how a smart choice of data structures may be used to increase the efficiency of particular algorithms
· be able to analyse the space and time efficiency of complex algorithms
· be able to design new algorithms or modify existing ones for new applications and reason about the efficiency of the result
Recommended reading
* Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2001). Introduction to Algorithms. MIT Press (2nd ed.). ISBN 0-262-53196-8
Sedgewick, R. (2004). Algorithms in Java, vol 2. (note that C and C++ editions are also available and are equally good for this course). Addison-Wesley. ISBN 0-201-36121-3.
Kleinberg, J. & Tardos, É. (2006). Algorithm design. Addison-Wesley. ISBN 0-321-29535-8.
Students are expected to buy and make extensive use of one of the above references: those not doing so will be severely disadvantaged. The easiest and recommended choice is Cormen et al. which covers all the topics in the syllabus: the pointers in the syllabus are to chapters in that book. The other textbooks are all excellent alternatives and are sometimes clearer or more detailed than Cormen, but they are not guaranteed to cover every item in the syllabus. Their relative merits are discussed in the course handout.
Computer Design
Syllabus
Prerequisite courses: none, but Operating Systems, Digital Electronics and ECAD would be helpful
This course is a prerequisite for the Part II courses Comparative Architectures and VLSI Design.
Aims
The aims of this course are to introduce the hardware/software interface models and the hardware structures used in designing computers. The first seven lectures are concerned with the hardware/software interface and cover the programmer's model of the computer. The last nine lectures look at hardware implementation issues at a register transfer level.
Lectures
· Introduction to the course and some background history.
· Historic machines. EDSAC versus Manchester Mark I.
· Introduction to RISC processor design and the ARM instruction set.
· ARM tools and code examples.
· Operating system support including memory hierarchy and management.
· Intel x86 instruction set.
· Java Virtual Machine.
· Memory hierarchy (caching).
· Executing instructions. An algorithmic viewpoint.
· Basic processor hardware. Pipelining and data paths.
· Extending the ARM pipeline including load and branch delay slots.
· Implementation of a MIPS processor [3 lectures].
· Internal and external communication.
· Data-flow and comments on future directions.
Objectives
At the end of the course students should
· be able to read assembler given a guide to the instruction set and be able to write short pieces of assembler if given an instruction set or asked to invent an instruction set
· understand the differences between RISC and CISC assembler
· understand what facilities a processor provides to support operating systems, from memory management to software interrupts
· understand memory hierarchy including different cache structures
· appreciate the use of pipelining in processor design
· understand the communications structures, from buses close to the processor, to peripheral interfaces
· have an appreciation of control structures used in processor design
· have an appreciation of how to implement a processor in Verilog
Recommended reading
* Hennessy, J.L. & Patterson, D.A. (2002). Computer architecture: a quantitative approach. Morgan Kaufmann (3rd ed.). (2nd ed., 1996, is also good.)
Patterson, D.A. & Hennessy, J.L. (2004). Computer organization and design. Morgan Kaufmann (3rd ed., as an alternative to the above). (2nd ed., 1998, is also good.)
Pointers to sources of more specialist information are included in the lecture notes and on the associated course web page.
CISC & RICS
CISC tried to make the semantic gap between high level language and assembler smaller, but this resulted in large, slow instruction sets.
RISC makes the common case fast.
Register Files
A register file is an array of registers. It is used to localise intermediate results for speed gains.
ARM has 15 registers r0-r14. r15 is the program counter. There is also the cspr (current program status register) which contains 4 conditional bit fields. Conditional branches check these values.
The accumulator is a special register in that it can be used implicitly (it doesn't have to be stated) e.g.
ADD memoryaddress
will add the accumulator to the memory address.
Load and Store
STR R0, [Rbase] Store R0 at Rbase.
STR R0, [Rbase, Rindex] Store R0 at Rbase + Rindex.
STR R0, [Rbase, #index] Store R0 at Rbase + index.
Index is an immediate value.
STR R0, [R1, #16] would load R0
from R1+16.
STR R0, [Rbase, Rindex]! Store R0 at Rbase + Rindex, &
write back new address to Rbase.
STR R0, [Rbase, #index]! Store R0 at Rbase + index, &
write back new address to Rbase.
STR R0, [Rbase], Rindex Store R0 at Rbase, & write back
Rbase + Rindex to Rbase.
STR R0, [Rbase, Rindex, LSL #2] will store R0 at the address
Rbase + (Rindex * 4)
STR R0, place Will generate a PC-relative offset
to 'place', and store R0 there.
The multiple data transfer instructions (LDM and STM) are used to load and store multiple words of data from/to main memory.
The main use of LDM/STM is to dump registers that need to be preserved onto the stack. We've all seen STMFD R13!, {R0-R12, R14}.
Example: Iterative Fibonacci in ARM
;assume x is held in r0 at start
mov r1,#1 ;initialisation
mov r2,#1
mov r3,#2
loop: cmp r3,r0 ;if i>x
bgt finish ;then jump to finish
add r1,r1,r2 ;a:=a+b
sub r2,r1,r2 ;b:=a-b
add r3,r3,#1 ; i:=i+1
b loop
finish: mov r0,r1 ;return result in r0
Where x is held in register r0, a is held in register r1, b is held in register r2, i is held in register r3
Virtual Addresses
As computers became more complex, it became difficult for programs to keep track of the different types of memory in different locations. To solve this problem, the operating system fabricates a "virtual memory space".
With a multiple address space scheme, each application resides in its own virtual memory space and can't accesses any other memory. UNIX uses this ,but it makes sharing libraries difficult.
With the single address space scheme, all applications share the same memory space. This is simple, and means there is only one virtual address for each physical address.
A 32-bit machine can reference 4GB or memory, though it may only have say 16M of real physical memory- but with virtual addressing it can use the secondary memory(hard disk) to pretend it has the full 4GB. This 4GB virtual address space is split up into chunks, commonly 4K in size, called pages. The physical memory is also split up into chunks, also commonly 4K in size, called frames. A program's text segment might start at the virtual address 0x00000004 - page number 0x0, and offset 0x4, but in reality, this may correspond to the physical address 0xff0e0004 - frame number 0xff0e, and offset 0x4. What the virtual memory system does is convert virtual addresses into physical addresses, essentially, mappings between pages and frames. The page table is used for this purpose.
When an application attempts to use a page which has been swapped to disk an exception is raised and the OS swaps an existing page with the required one.
Translation Lookaside Buffers (TLBs)
A TLB is a cache in the CPU used to improve the speed of virtual address translation.
Many architectures also have direct hardware support for virtual memory, providing what is known as a translation lookaside buffer (TLB), which is filled with page-frame mappings initially, and instead of having the virtual memory system entirely in software, when the hardware looks up a memory address and does the page-frame translation, virtual address to page-frame mapping is cached in the TLB, which gains us a performance increase.
However, the TLB can only hold a fixed number of page-frame mappings. It is the job of the virtual memory system to extend this into software, and to hold extra page-frame mappings. The virtual memory system does so by means of a page table.
The TLB contains not only translation information, but also the protection data. A permission fault is raised if an application attempts to access a page it doesn't have the right to access.
If a TLB hit takes 1 clock cycle, a miss takes 30 clock cycles, and the miss rate is 1%, the effective memory cycle rate is an average of 
clock cycles per memory access.
 |
Translating Virtual Addresses to Physical Addresses
The page table
Say a program is running and it tries to access memory in the virtual address 0xd09fbabe. The virtual address is broken up into two: 0xd09f is the page number and 0xbabe is the offset, within the page 0xd09f.
With hardware support for virtual memory, the address is looked up within the TLB. The TLB is specifically designed to perform this lookup in parallel, so this process is extremely fast. If there is a match for page 0xd09f within the TLB (a TLB hit), the physical frame number is retrieved, the offset replaced, and the memory access can continue. However, if there is no match (called a TLB miss), the second port-of-call is the page table.
When the hardware is unable to find a physical frame for a virtual page, it will generate a processor interrupt called a page fault. Hardware architectures offer the chance for an interrupt handler to be installed by the operating system to deal with such page faults. The handler can look up the address mapping in the page table, and can see whether a mapping exists in the page table. If one exists, it is written back to the TLB, as the hardware accesses memory through the TLB in a virtual memory system, and the faulting instruction is restarted, with the consequence that the hardware will look in the TLB again, find the mapping, and the translation will succeed.
However, the page table lookup may not be successful for two reasons:
· there is no translation available for that address - the memory access to that virtual address is thus bad or invalid, or
· the page is not resident in physical memory (it is full).
In the first case, the memory access is invalid, and the operating system must take some action to deal with the problem. On modern operating systems, it will send a segmentation fault to the offending program. In the second case, the page is normally stored elsewhere, such as on a disk. To handle this case, the page needs to be taken from disk and put into physical memory. When physical memory is not full, this is quite simple, one simply needs to write the page into physical memory, modify the entry in the page table to say that it is present in physical memory (see the next section), write the mapping into the TLB and restart the instruction.
However, when physical memory is full, and there are no free frames available, pages in physical memory may need to be swapped with the page that needs to be written to physical memory. The page table needs to be updated to mark that the pages that were previously in physical memory are no longer so, and to mark that the page that was on disk is no longer so also (and to of course write the mapping into the TLB and restart the instruction). This process of swapping pages between physical memory and disk is known sometimes as, obviously, swapping (though the term is sometimes used to describe swapping entire processes). This process however is extremely slow in comparison to memory access via the TLB or even the page table, which lies in physical memory.
Safety
One of the most important benefits of virtual addressing is that each process can write only to the physical memory for which the operating system has created page table entries. This prevents one process from overwriting another process's data. The OS often splits up the memory into text (instructions), data (constants) and stack regions to reduce the chances of the stack overwriting the text area etc.
Thrashing is when the OS is constantly moving data between primary and secondary storage.
Real and Protected Mode
The physical address is generated by multiplying the segment register by 16, then adding a 16-bit offset. Using 16-bit offsets implicitly limits the CPU to 64k segment sizes.
In protected mode, memory segmentation is defined by a set of tables (called descriptor tables) and the segment registers contain pointers into these tables.
The Java Virtual Machine (JVM)
Virtual machines allow portability and numerous at run time performance improvements.
The JVM has 4 special registers (Pc, base address of local memory, address of top of operand stack, base of current frame). A frame contains local variables, operand stack and run time data.
Memory Hierarchy
● register file (~128 bytes), multiported SRAM,multiple read/writes per cycle
● 1st level cache (~64 kbytes), SRAM, 1 or 2 read/writes per cycle
● 2nd level cache (~1Mbytes), SRAM, 0.75 read/write per cycle
● main memory (~2GBytes), DRAM 50 cycles for first read/write, then 5 (burst mode)
● hard disk for virtual memory (~200 GBytes), slow but has cache
Main memory can be built from the fast SRAM (5 transistors/bit) or the cheaper DRAM (1 transistor/bit).
Cache Principles
● Temporal locality: then it is likely to be accessed again
● If a word is accessed then its neighbours are likely to be accessed soon
Cache lines take advantage of spatial locality: rather than storing words randomly in memory they are stored next to each other in lines of 4 or 8 words and area all read at once from DRAM in a burst.
Direct Mapped Cache
A direct-mapped cache scheme makes picking the slot very simple. It treats the slot as a large array, and the index of the array is picked from bits of the address (which is why we need the number of slots to be a power of 2---otherwise we can't select bits from the address)
The scheme can suffer from many addresses "colliding" to the same slot, thus causing the cache line to be repeatedly evicted, even though there may be empty slots that aren't being used, or being used with less frequency.
("Slot" is normally called Index)
Suppose you have address B31-0.
l Use bits B11-5 to find the slot.
l See if bits B31-12 match the tag of the slot.
l If so, get the byte at offset B4-0.
l If not, fetch the 32 bytes from memory, and place it in the slot, updating valid bit, dirty bit, and tag as needed.
Car Park analogy: "Your parking spot is the first 3 digits of your student Id number,"
Set Associative Cache
Direct mapped cache have a set of cache lines at each location used to indicate which element to read from.
Car park analogy: "Your parking spot is based on the first 2 digits of your student ID number. In this case, you use the first 2 digits of your student ID, and have up to 10 different parking spots you can park at. "
Victim Cache
A victim cache is a cache used to hold blocks evicted from a CPU cache due to a conflict or capacity miss. The victim cache lies between the main cache and its refill path, and only holds blocks that were evicted from that cache on a miss. This technique is used to reduce the penalty incurred by a cache on a miss.
Cache Line Replacement Policies
Least Recently Used, Not Last Used, Random
Write Back and Write Through
Write through: Data is written to both cache and lower level memory
Write back: Data is written to the cache only, then written to lower level memory when cache line is replaced.
Dyadic (2 part) Instruction Encoding
● Fetch instruction from memory at address PC, increase PC (word increment so PC:=PC +4)
● Decode opcode
● Check conditionals
● Execution: Fetch operands 1+2
● Shift operand 2 is required
● Perform operation (ALU)
● Write result to destination register
● If S bit is set then set condition codes
Monadic instructions are the same except operand 1 doesn't need to be fetched.
ARM Thumb Code
The thumb instruction set uses 16-bit instructions, so requiring less memory but generally more instructions.
MIPS (Microprocessor without Interlocked Pipeline Stages)
One major barrier to pipelining was that it required interlocks to be set up to ensure that instructions that took multiple clock cycles to complete would stop the pipeline from loading more data -- basically to pause while it completed. A major design aspect of the MIPS design was to demand that all instructions take only one cycle to complete, thereby removing any needs for interlocking.
Pipelines
Pipe lining, as opposed to sequential execution, allows numerous instructions to be processed at once.
Many designs include pipelines as long as 31 stages (like in the Intel Pentium 4).The downside of a long pipeline is when a program branches, the entire pipeline must be flushed, a problem that branch predicting helps to alleviate. ARM uses the cleared stages in the pipeline to save the corrected version of the PC to R14 and to write the branch address to the PC.
A pipelined system typically requires more resources (circuit elements, processing units, computer memory, etc.) than one that executes one batch at a time, because its stages cannot reuse the resources of a previous stage. Moreover, pipelining may increase the time it takes for an instruction to finish.
The pipeline controller would take a typical instruction like ADD A, B, C
and translate it into something like:
LOAD A, R1
LOAD B, R2
ADD R1, R2, R3
STORE R3, C
LOAD next instruction
And then execute the instructions on the pipeline.
The following diagram has four pipelines (in this pipeline execute and write back are separate stages):
In this example, the purple instruction gets delayed at the fetch stage, stalling all further instructions by one clock cycle.
The ARM710 pipeline has 3 stages: fetch, decode and execute. The pipelines throughput is limited by the worst case performance of a particular stage. The ARM's execute stage includes register reads, a shift, an ALU operation and register write back- so it takes a long time. Adding extra stages improves performance, at the cost of power consumption and transistor count.
We could speed up the pipeline by taking "register fetch" and "register write back" out of the execution stage:
| instruction fetch | decode | register fetch | execute | register write back |
But this creates a problem when the result of the next instruction depends on the prior:
add R1,R1,R3
add R1,R1,R3
There are two options here: either stall the execution until the write back has occurred, or feedforward/bypass the output of the execution stage straight back to its input. The second option is faster but consumes more transistors.
Note: In practice, register write back and read are performed in the same cycle as they don't take long.
The Classic RISC Pipeline
| instruction fetch | register fetch | execute | memory access | register write back
|
Load Delay Slots
The data from a load has to be bypassed two pipeline stages. If there is a data dependency, the next instruction will have to be stalled at the register fetch/decode stage.
nop instructions can be put in by the assembler, so the hardware doesn't have to worry. Alternatively, the hardware can use a method such as scoreboarding (every register has a flag to indicate whether its value is available, or will be made available via a bypass).
Exception Handling in Pipelines
Precise exceptions are hardware intensive and allow the OS to know exactly what happened, and the PC is saved.
Instruction Replays
You tend to find out about a cache miss late, so replay the instructions.
Parallel Communication
This doesn't work well for high clock frequencies over long distances due to timing skew.
Serial Communication
The clock is recovered from the data stream, and data is coded.
RS232
Designed for dumb devices, many non standard devices. Asynchronous serial line.
USB
Devices can be chained together. A twisted data pair (bidirectional differential signalling).
Plug and play (devices hold vendor, class information).
Up to page 25 in Comp Design 2
Concurrent Systems and Applications
Syllabus
Aims
The aims of this course are (a) to introduce the modular design of application software, using the facilities of the Java and C# programming language as running examples, (b) to explore the need for and implementation of concurrency control and communication in inter-process and intra-process contexts and (c) to introduce the concept of transactions and their implementation and uses.
Lectures
· Programming with objects. Revision overview of the Java programming language. Structuring programs using encapsulation and inheritance. Design patterns. [4 lectures]
· Further Java topics. Graphical user interfaces. Reflection and serialization. Finalizers. Class loaders. Software testing. [8 lectures]
· Concurrent systems. Reasons for multi-threaded programming. Correctness criteria. Mutual exclusion locks and condition variables. Alternative concurrency-control primitives. [5 lectures]
· Distributed systems & transactions. General problems in distributed systems. Naming. Access control. IDLs. Message passing and the use of sockets in Java. Remote method invocation. Compound operations & correctness criteria. Crash recovery. Isolation. [5 lectures]
· Generics in Java. Single-compilation templated classes. Type specialisation and typing constraints. Interactions with reflection, serialisation, and the class loader. Advanced implementation techniques using Generics. [2 lectures]
Objectives
At the end of the course students should
· understand the terminology of object oriented programming and be able to use it with precision
· be able to illustrate the use of object oriented techniques through examples of the kind seen in the Java standard libraries
· understand the need for and implementation of concurrency control
· understand different mechanisms for communication within or between applications and evaluate their trade-offs in different scenarios
· understand the concept of transactions and their application in a range of systems
· understand why software testing is not always easy and the techniques used to achieve thorough testing
Recommended reading
* Bacon, J. & Harris, T. (2003). Operating systems or Bacon, J. (1997) Concurrent systems (2nd ed.). Addison-Wesley.
Myers, G.J. (2004). The art of software testing. Wiley (2nd ed.).
Lea, D. (1999). Concurrent programming in Java. Addison-Wesley (2nd ed.).
Bracha, G., Gosling, J., Joy, B. & Steele, G. (2000). The Java language specification. Addison-Wesley (2nd ed.). http://java.sun.com/docs/books/jls/
Gamma, E., Helm, R., Johnson, R. & Vlissides, J. (1994). Design patterns. Addison-Wesley.
Java Revision
| x <
x > x <= x >= |
More than x
Less than x More than/= to x Less than/= to x |
==
!= |
Equal to
Not equal to |
|
| Any numeric comparison returns 0 if either number is a NaN | ||||
| +,-,*,/ | Obvious | x % y | r where x=qy+r | |
| byte
short int long float double char boolean |
Represents -128 to 127
-215 to 215 -1 -231 to 231 -1 -263 to 263 -1 32 bit floating point value 64 bit floating point value A single character |
|||
| \n
\r \u[Hex number] |
New line
Carriage return Unicode character |
\"
\' \\ |
"
' \ |
|
| <<
>> >>> |
Shift every bit left
Shift every bit right Same,fills with 0's |
(type)x
Final type name
|
Casts x
Makes a constant
|
|
| ~x
& ^ | |
-x
And Exclusive Or Inclusive Or |
While (case) {}
do {} while(); break continue |
Continue while case
Condition at end Exit loop Jump to next cycle |
|
| Switch (var) {
case x: ...; break; default: ...; |
Compare var
If var =x then ... Exit switch If no case found |
Throw x
try { catch (Arg) {..} finally
|
Raise Exception X
Precedes catch If exception arg ..
Do at end of try
|
|
| assert x
import [class] extends x
implements x |
If x and -ea flag at command line then raise exception
Allows you to directly reference members of [class] Creates a subclass of x, ie the new class begins as x and can then be extended The new class adheres to x, the name,number and type of arguments in the class must match the interface/inherited class |
|||
| This.x
abstract
final
static
super.method(); strictfp |
Refers to the main x in top class
Class is abstract if declared or contains abstract method. Can't be instantiated buy can make object references. When a method is final it cant be overridden by any derived class. A final class can't be sub-classed. Also constants. Associated with class, not instantiations: A single global class variable meaning it can be referred to globally just as Class.ItemName Calls method() from the class that the current class extended The method/class will be executed using IEE754 floating point |
|||
| Private
Package protected public
|
A method or variable declared as private can only be referenced from within the class in which it is defined.
Any class in the same package can reference a value (default). Visible in derived classes even if they are in other packages. Names available regardless of packages and inheritance |
|||
| synchronized
volatile
transient native |
Ensures that several threads in a multi-threaded applications do not access the same class/method at the same time
Rather than caching the JVM will re-read variables each time they're accessed Transient fields aren't serialized Non-java code |
|||
|
|
|
|||
| Printf("...
%i$ %< %d |
Prints argument i Re-use argument Prints an integer |
%s
%n %tD %c |
Anything to string
Newline Date Prints a character |
|
Reference types are class types, interface types and array types .
The substitution principle states that sub-types must be substitutable for supertypes. This is true so
long as for each method in the super type, the sub type must have a corresponding method.
The instanceof operator requires an object as its left operand and the name of a reference type as its
right operand. It evaluates to true if the object is an instance of the specified type.
If B extends A...
If B extends A, then an array of type A[] can hold objects of type A or B, but an array of type B can only hold objects of type B.
A field in the sub-class B is said to hide a field in the super-class if it has the same name. The hidden field can be accessed by casting the object reference to the type on which the field is defined, or by writing super.name (ie A.name) to get to the immediate super-class.
The sub-class B can overload the methods in its superclass A by making additional definitions with different signatures (ie taking different arguments).
It can override them by supplying new definitions with the
same signature.
Abstract methods
It is not permitted to instantiate an abstract class, but we can use object references of the type of the abstract class.
Static modifier
A static field/method is associated with the class rather than objects.
Interfaces
An interface definition declares method signatures and static final fields (constants).
A class that implements an interface must either supply definitions for all declared methods or be declared abstract.
Nested classes/interfaces
There are four cases:
● inner classes in which the enclosed class is an ordinary class (i.e. non-static)
● static nested classes in which the enclosed definition is declared static
● nested interfaces in which an interface is declared within an enclosing class or interface
● anonymous inner classes
Each inner class is said to be "enclosed" by the class that it is in. Inner classes can access fields in the outer class, and the outer class itself can be accessed using [outer-class].this
Static nested classes are often used as "helper" functions.
Anonymous inner classes are declared with just "{ }"
Design patterns
The observer design pattern
One or more observers/listeners watch for events raised by the observed object.
Subect class has a list of observers and the following functions:
The Attatch() itself to list of observers on the object. Also Detach(). Notify() calls the update function in each observer.
The abstract observer class has it's Update() function overridden by subclasses.
The singleton pattern
Ensures that a class can be instantiated at most once. Private constructor ensures external classes cannot instantiate the class by calling new. A static method creates an instance when first called and subsequently returns an object reference to the same instance.
class Singleton {
static Singleton theInstance = null;
private Singleton() {...}
static Singleton getInstance() {
if (theInstance == null)
return (theInstance = new Singleton());
return theInstance;
}
void method1() {...}
void method2() {...}
void method3() {...}
}
The abstract factory pattern
An example of this would be an abstract factory class DocumentCreator that provides interfaces to create a number of products (eg. createLetter() and createResume()). The system would have any number of derived concrete versions of the DocumentCreator class like FancyDocumentCreator or ModernDocumentCreator, each with a different implementation of createLetter() and createResume() that would create a corresponding object like FancyLetter or ModernResume.
/*
* GUIFactory example
*/
abstract class GUIFactory
{
public static GUIFactory getFactory()
{
int sys = readFromConfigFile("OS_TYPE");
if (sys == 0)
{
return new WinFactory();
}
else
{
return new OSXFactory();
}
}
public abstract Button createButton();
}
class WinFactory extends GUIFactory
{
public Button createButton()
{
return new WinButton();
}
}
class OSXFactory extends GUIFactory
{
public Button createButton()
{
return new OSXButton();
}
}
abstract class Button
{
public abstract void paint();
}
class WinButton extends Button
{
public void paint()
{
System.out.println("I'm a WinButton: ");
}
}
class OSXButton extends Button
{
public override void paint()
{
System.out.println("I'm a OSXButton: ");
}
}
public class Application
{
public static void main(String[] args)
{
GUIFactory factory = GUIFactory.getFactory();
Button button = factory.createButton();
button.paint();
}
// Output is either:
// "I'm a WinButton:"
// or:
// "I'm a OSXButton:"
}
The adapter pattern
The adapter design pattern 'adapts' one interface for a class into one that a client expects. An adapter allows classes to work together that normally could not because of incompatible interfaces by wrapping its own interface around that of an already existing class. The adapter is also responsible for handling any logic necessary to transform data into a form that is useful for the consumer. For instance, if multiple boolean values are stored as a single integer but your consumer requires a 'true'/'false', the adapter would be responsible for extracting the appropriate values from the integer value.
Visitor Pattern
Use a hierarchy of classes to represent the nodes in a data structure, e.g. a tree.
A concrete sub-class of Visitor is constructed for each kind of operation on the data structure:
abstract class Visitor {
abstract void apply(Object o);
}
class VisitorCountNulls extends Visitor {
int count=0;
void apply(Object o) {if (o == null) ++count;}
}
class VisitorSumIntegers extends Visitor {
int sum=0;
void apply(Object o) {
if (o instanceof Integer) {
sum += ((Integer) o).intValue();
}
}
}
Reflection
Reflection is provided by a number of classes in the java.lang and java.lang.reflect packages.
Can get errors eg java.lang.ClassNotFoundException and java.lang.SecurityException.
You can access public fields with getFields();
public class ReflExample3 {
public static int field1 = 10;
public static int field2 = 11;
public static void main(String [] args) {
try {
Class c = Class.forName(args[0]);
java.lang.reflect.Field f;
f = c.getField(args[1]);
int value = f.getInt(null);
System.out.println(value);
} catch (Exception e) {
System.out.println(e);
}
}
}
You can invoke methods, eg;
Object parameters[] = new Object [2];
parameters[0] = ref1;
parameters[1] = ref2;
m.invoke(target,parameters);
The parameters must be wrapped, eg rather than just 42 you have to write new Integer(42).
Serialization
You could use reflection to get the contents of fields at run time, then save them.
ObjectInputStream and ObjectOutputStream classes automate this procedure e.g;
FileOutputStream s = new FileOutputStream("file");
ObjectOutputStream o = new ObjectOutputStream(s);
o.writeObject(drawing);
o.close();
Classes must implement the java.io.Serializable interface to indicate that the programmer believes this is a suitable way of loading or saving instance state.
A 0-argument constructor must be accessible to the sub-classes being serialized: it is used to initialize fields of the non-serializable super-classes.
Swing follows a model-view-controller
Components and Containers
Containers implement an add method to place components within them.
Components represent the building blocks of the interface: for example, buttons, check-boxes, text boxes, etc.
A JFrame has a root pane which contains the main content pane and the menu bar.
Methods which extend java.awt.event and java.awt.event are invoked on a listener for input.
Anonymous inner classes can be used to handle input eg;
addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
...
}
});
Another way is to define inner classes that extend adapter classes from the java.awt.event package.
javax.accessibility
Swing components implement Accessible, defining a single method getAccessibleContext().
Garbage Collection
Reclaiming Space
The JVM guarantees that storage space will not be reclaimed while an object remains reachable, defined as being if it:
· is referred to by a static field in a class;
· is referred to by a local variable in a running thread;
· still needs to be finalized; or
· is referred to by another reachable object.
Methods of collection
Generational collection: "most objects die young" ->
keep a small young generation which can be collected
quickly and frequently.
Parallel collection: multiple processors work on GC at the
same time -> application pauses for less time.
Concurrent collection: GC occurs at the same time as
application execution.
Incremental collection: GC occurs in small bursts, e.g.
each time an object is allocated: -Xincgc.
Finalizers
When the GC detects that an object is otherwise unreachable (e.g. D and E two slides previous) then it can run a finalizer method on it. These are ordinary methods that override a default version defined on java.lang.Object.
The finalizer method can be used for cleaning up eg; closing network connections.
The JVM gives few guarantees about finalizer methods: they will be run at most once and will not be run on an object before it becomes unreachable.
System.runFinalization() will cause the JVM to try to complete any outstanding finalizations.
Reference Objects
The referant is selected at instantiation and can be subsequently obtained using the get() method.
A weak reference object acts as a normal object, except that it requires explicit calls to get(). Once the object becomes unreachable, subsequent calls to get() return null.
A reference queue supports three operations:
poll() attempts to remove a reference object from the queue, returning null if none is available;
remove(x) attempts to remove a reference object, blocking up to x milliseconds; and
remove() attempts to remove a reference object, blocking indefinitely.
A reference can be associated with a reference queue rq at declaration:
Reference ref = new WeakReference(obj,rq);
After clearing reference objects the garbage collector will (possibly some time later) append those associated with reference queues to the appropriate queue.
It is the reference object (ref), not the referent (obj), that is appended to the queue.
This prevents the problem of `resurrected' objects.
There are three kinds of reference object, in decreasing strength they are:
A SoftReference can be cleared by the GC when memory is tight, so long as the referent isn't reachable by ordinary references. Useful for memory-sensitive caches.
A WeakReference can be cleared by the GC once the referant isn't reachable by ordinary or soft references. Useful for hashtables where data can be discarded once no longer in use.
A PhantomReference is enqueued once the referent isn't reachable through ordinary, soft or weak references and once it has been finalized. get() always returns null. Useful to be sub-classed and used with reference queues as a more flexible alternative to finalizers.
Java Native Interface
Useful to access hardware, old libraries or to optimize code. The native side of the code, and objects passed to it, aren''t garbage collected.
1 class HelloWorld {
2 public native void displayHelloWorld();
3
4 static {
5 System.loadLibrary("hello");
6 }
7
8 public static void main(String args[]) {
9 new HelloWorld().displayHelloWorld();
10 }
11 }
Line 2 defines the signature of a native method.
Lines 4-6 are a static initializer, executed by the JVM
when the class is loaded.
Line 9 instantiates the class and calls the native method.
Compile the Java and create the C function signatures:
$ javac HelloWorld.java
$ javah -jni HelloWorld
Creates HelloWorld.class and HelloWorld.h
The native, eg C, side of the code will look something like:
JNIEXPORT void JNICALL Java_ClassName_MethodName
(JNIEnv *env, jobject obj)
{
//Implement Native Method Here
}
The JNIEnv parameter refers to an environment structure containing the function pointers for these operations, eg GetSuperClass.
Class Loaders
Class loaders can be used to dynamically load classes at run time, eg from across a network or classes that have been dynamically generated.
Class loaders are Java objects extending java.lang.ClassLoader.
c.loadClass(name) requests that c loads the named class, returning a java.lang.Class object.
Within the JVM, classes are identified by the pair of their fully-qualified name and the class loader that created them.
Concurrency
Threads
Threads are controlled by the scheduler- they are associated with a thread control block (TCB) which contains the thread state, context information and priority etc.
You can create a thread by sub-classing java.lang.Thread and overriding the run() method- run contains the code that will be executed by the thread. You can then create a new instance of you're subclass and call start() on it, eg;
Thread t1 = new MyThread();
t1.start();
The second way of creating a thread is to define a class that implements the java.lang.Runnable interface. The implementation is slightly more complex, but doesn't take away the ability to sub-class a parent:
class MyCode implements Runnable { public void run() { } }
MyCode mt = new MyCode();
Thread t_a = new Thread(mt);
t_a.start();
Threads can be interrupted with thread.interrupt(),try to change thread with thread.yield(), pause with thread.sleep(). Methods that deal with threads should throw InterruptedException.
The join method on java.lang.Thread causes the currently running thread to wait until the target thread dies. setPriority and getPriority cannot be relied upon to control data access as different JVMs implement thread control differently.
Non-preemptive schedulers (which only switch when the running thread yields, becomes blocked, or exits) are commonly used by the JVM. The OS typically uses preemption.
When a thread reads or writes a field declared volatile it must actually access the memory location in which that field's value is held. This is an alternative to mutexes.
Safety
Invariants are things that must remain true. In consistent object states all invariants are satisfied
Liveness
"Something good eventually happens"
Deadlock--a circular dependency between processes holding resources and processes requiring them. Typically the `resources' are exclusive access to locks.
Livelock--a thread keeps executing instructions but makes no useful progress, e.g. busy-waiting on a condition that will never become true.
Missed wake-up (wake-up waiting)--a thread misses a notification that it should continue with some operation and instead remains blocked.
Starvation--a thread is waiting for some resource but never receives it--e.g. a thread with a very low scheduling priority may never receive the CPU.
Distribution failures--of nodes or network connections in a distributed system.
Shared data
Most field acesses in Java are atomic, however this is not true for long and double types. So you could read the first part, then another thread writes to it, and read a different second half- giving an incorrect value. This is an example of a race condition.
Mutual Exclusion Locks
The JVM associates a separate mutex with each object.
Synchronized
The synchronized keyword can be used in two ways--either applied to a method or applied to a block of code.
Locks are re-entrant, meaning that the thread may call one synchronized method from another.
If a static synchronized method is called then the thread must acquire a lock associated with the class rather than with an individual object.
Eg; synchronized (x) { System.out.println("1"); }
The synchronized region locks the mutex associated with the object to which x refers, performs the println operation, and then releases the lock.
When an exception is thrown in a synchronized block the mutex is released before entering the catch code -to prevent deadlock, but you have to be careful you don't access sensitive data in the catch code.
See http://www.cs.duke.edu/~chase/cps210-archive/slides/sync6.pdf for more on mutexes.
Deadlock
Suppose that a and b refer to two different shared objects,
| Thread P
synchronized (a) synchronized (b) { ... } |
Thread Q
synchronized (b) synchronized (a) { ... } |
If P locks both a and b then it can complete its operation and release both locks, thereby allowing Q to acquire them.
Similarly, Q might acquire both locks, then release them and thus allow P to continue.
But, if P locks a and Q locks b then neither thread can continue: they are each deadlocked waiting for the resources that the other has.
If all of the following conditions are true then deadlock exists:
1. A resource request can be refused--e.g. a thread cannot acquire a mutual-exclusion lock because it is already held by another thread.
2. Resources are held while waiting--e.g. while a thread blocks waiting for a lock it does not have to release any others that it holds.
3. No pre-emption of resources is permitted--e.g. once a thread acquires a lock then it is up to that thread to choose when to release it, it cannot be taken away from the thread.
4. Circular wait--a cycle of threads exists such that each holds a lock requested by the next process in the cycle, and that request has been refused.
In the case of mutual exclusion locks in Java, 1-3 are always true (they are static properties of the language), and so the existence of a circular wait leads to deadlock.
 |
In the following diagram, a is held by thread P and P is requesting object b:
Deadlock Detection
You can avoid deadlock by working out all the resources that every process could possibly want, then if there are no overlaps then the execution is safe. However, this is slow and there may be no safe states.
You can also use schemes that allow more concurrency, eg multiple reader single writer, or make processes acquire all resources at one time rather than waiting with held resources or pre-emption can be used.
Alternatively you can combine locks so just one lock is used for many/all resources, or enforce a locking order.
Another problem is that a low priority process can get stuck holding a resource that a high priority task requires. The solution is to boost the holder of every locks priority to that of the greatest priority thread requiring the object.
Condition Variables
In general, condition variables support cv.CVWait(m) which causes the current thread to atomically release a lock on mutex m and to blox itself on condition variable cv, reacquiring the lock on m before it completes; and a cv.CVNotify(m) operation that wakes up threads blocked on cv.
Eg;
public synchronized int removeValue() {
while (!full) cv.CVWait(this);
full = false;
cv.CVNotify();
return value;
}
Internally each condvar has private fields that hold a queue of threads that are waiting on the condition variable and an additional mutex cvLock that is used to give the atomicity required by CVWait().
cv.CVWait(m) proceeds by:
1 Acquire mutex cv.cvLock
2 Add the current thread to cv.queue
3 Release mutex m
4 Release mutex cv.cvLock
5 Suspend current thread
6 Re-acquire mutex m
cv.CVNotify() proceeds by:
1 Acquire mutex cv.cvLock
2 Remove one thread from cv.queue
3 Resume that thread
4 Release mutex cv.cvLock
However, Java doesn't provide individual condition variables in this way. Instead, each object o has an associated condition variable which is accessed by:
o.wait() is the equivalent of cv.CVWait(o) on the condition variable associated with o.
o.notify() unblocks exactly one thread (if any are any waiting)
o.notifyAll() unblocks all waiting threads.
Eg;
public synchronized int removeValue()
throws InterruptedException
{
while (!full) wait();
full = false;
notifyAll();
return value;
}
With notifyAll() the programmer must ensure that every thread blocked on the condition variable can continue safely.
notify() selects arbitrarily between the waiting threads: the programmer must therefore be sure that the exact choice does not matter.
The suspend() and resume() methods defined on java.lang.Thread allow one thread to temporarily stop and start the execution of another (or to suspend itself), however they are depreceated and shouldnt be used as they can lead to deadlocks.
Multiple Reader, Single Writer example
class MRSWImpl1 implements MRSW {
private int numReaders = 0;
private int numWriters = 0;
//A reader must wait until numWriters is zero. A writer must wait until both fields are zero.
synchronized void enterReader()
throws InterruptedException
{
while (numWriters > 0) wait();
numReaders++;
}
synchronized void enterWriter()
throws InterruptedException
{
while ((numWriters > 0) ||
(numReaders > 0)) wait();
numWriters++;
}
synchronized void exitReader() {
numReaders--;
notifyAll();
}
synchronized void exitWriter() {
numWriters--;
notifyAll();
}
}
Advantages:
Simple design: Create a class containing fields, write entry protocols and write exit protocols.
Disadvantages:
notifyAll() is safe but inefficient.
First Come First Server example
class FCFSImpl implements CCInterface {
private int currentTurn = 0;
private int nextTicket = 0;
//Threads take a ticket and wait until it becomes their turn:
synchronized void enter()
throws InterruptedException
{
int myTicket = nextTicket++;
while (currentTurn < myTicket)
wait();
}
synchronized void exit() {
currentTurn++;
notifyAll();
}
}
Advantages:
Simple
Disadvantages:
If a thread is interrupted during wait() then its ticket is lost.
Compare and Swap (CAS)
The compare-and-swap instruction is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value.
class Mutex {
int lockField = 0;
void lock() {
while (CAS(&lockfield,0,1) != 0) {
/* someone else has the lock */
}
}
void unlock() {
lockField = 0;
}
}
The problem with this is that the lock operation uses CPU time whilst waiting.
Semaphores
In Pseudocode:
class CountingSemaphore {
CountingSemaphore (int x) {
...
}
native void P();
native void V();
}
P (sometimes called wait) decrements the value and then blocks if the result is less than
zero. V (sometimes called signal) increments the value and then, if the result is zero or
less, selects a blocked thread and unblocks it. Using semaphores directly is intricate--the
programmer must ensure P() / V() are paired correctly.
The mutex is considered unlocked when the value of the counting semaphore is 1 (it is
initialized unlocked) and is locked when the value is 0 or less.
Event Counts and Primitives
An event count is represented by an integer, initilialized to 0, supporting the atomic
operations:
● advance() - Increment by one, return value
● read() - Return current value
● await(i) - Wait until value is greater or equal to i
A sequencer is represented by an integer, initialised to 0, supporting
● ticket() - Increment value by one, return old value
Mutual exclusion is simple: A thread takes a ticket entering a critical region and invokes
await() to receive its turn.
The values returned by await() can be used directly in implementing a single-producer
single-consumer N-slot buer: they give the modulo-N indices to read/write.
Monitors
Monitors are abstract data types, and so have the advantages associated with oop.
if busy wait(free)
busy=true;
// do stuff
busy=false;
notify(free);
-Busy is a boolean, free is a condition variable
Active Objects
Active objects have a dedicated thread that performs operations.; using conditional
ACCEPT statements.
Threads Communicating between different Machines and Address Spaces may have different low level data representations and different file-name locations.
The sender needs to agree marshalling and the receiver marshalling.
Distributed Systems
Problems include different machine performances, communication delay, failure and
different clocks.
Naming
A directory service can be used to look up eg "the closest server providing xyz". Unique
ID's can be simply assigned as successive integers- simply but centralized and can run
out of UID's. Hierarchical namespaces are generally better for allow local allocation.
A pure name, eg 113, contains no information about the object.
An impure name, eg mrf34@cam.ac.uk gives information about the object.
A namespace is a collection of names recognised by a name service. A naming domain is
a section of a namespace operated under a single administrative authority.
Namespaces can be replicated for availability, distributed and allow caching.
Using a name service at run-time to resolve names, rather than embedding addresses
directly in a program is considered good practice.
Security
Use a security manager class (java.lang.SecurityManager) to limit what the JVM is
able to do.
● e.g. limiting the IP addresses to which it can connect or whether it is permitted to
write to your files.
● If using network sockets directly, then make the program robust to unexpected
input.
Eg;
checkPermission(
new RuntimePermission(
"loadLibrary."+lib));
UDP
UDP sockets provide unreliable datagram-based communication that is subject to:
● Loss: datagrams that are sent might never be received.
● Duplication: the same datagram might be received several times.
● Re-ordering: datagrams are forwarded separately within the network and might
arrive out of order.
With UDP you have to re-invent the wheel, including flow & congestion control.
marshalling, loss detection.
What is provided:
● A checksum is used to guard against corruption (corrupt data is discarded by the
protocol implementation and the application perceives it as packet loss).
● The framing within datagrams is preserved|a UDP datagram might be fragmented
into separate packets within the network but these are reassembled by the receiver.
Communication is between an ip and a port number.
You can use multicast to broadcast to an entire group.
In Java
UDP sockets are represented by instances of java.net.DatagramSocket.
Datagrams are represented in Java as instances of java.net.DatagramPacket eg;
DatagramPacket(byte buf[], int length, InetAddress address, int port)
MulticastSocket defines a UDP socket capable of receiving multicast packets.
Example
import java.net.*;
public class Send {
public static void main(String args[]) {
try {
DatagramSocket s = new DatagramSocket();
byte[] b = new byte[1024];
int i;
for (i=0;i<args.length-2;++i)
b[i] = Byte.parseByte(args[2+i]);
DatagramPacket p = new DatagramPacket (
b, i,
InetAddress.getByName(args[0]),
Integer.parseInt(args[1]));
s.send(p);
} catch (Exception e) {
System.out.println("Caught " + e);
}}}
TCP
TCP provides a reliable bi-directional connection-based byte-stream with flow control and
congestion control.
● Unlike UDP framing must be provided explicitly.
● Marshalling must still be done explicitly|but serialization may help here.
● Communication is always one-to-one.
● Used for HTTP.
In Java
java.net.Socket represents a connection over which data can be sent and received.
java.net.ServerSocket represents a socket awaiting incoming connections. ServerSocket
provides an accept() operation that blocks the caller until an incoming connection is
received (or the wait is interrupted).
Example
import java.net.*;
import java.io.*;
public class TCPSend {
public static void main(String args[]) {
try {
Socket s = new Socket (
InetAddress.getByName(args[0]),
Integer.parseInt(args[1]));
OutputStream os = s.getOutputStream();
while (true) {
int i = System.in.read();
os.write(i);
}
} catch (Exception e) {
System.out.println("Caught " + e);
}}}
RMI
● Similar code to local calls
● Uses TCP and UDP, so is simple but doesn't provide much functionality
● The provider and user of the network service agree on how to access data using
interfaces
● It is better to use a name service at run time than embedding addressees directly
into a program
Java RMI is rather unusual in using ordinary language facilities to dene remote interfaces.
Usually a separate interface denition language (IDL) is used.
How it works
A server registers a reference to a remote object with the registry (a basic name service)
and deposits associated .class files in a shared location, the RMI codebase.
2. A client queries the registry to obtain a reference to a remote object.
3. If they are not directly available, the client obtains the .class files needed to access the
remote object.
4. The client makes an RMI call to the remote object.
The registry acts as a name service, with names being of the form
rmi://linux2.pwf.cl.cam.ac.uk/jkf21/example-1.2
Parameters and results are generally passed by making
deep copies when passed or returned over RMI.
Remote objects are passed by reference and so both caller and callee will interact with the
same remote object if a reference to it is passed or returned.
Note that Java only supports remote method invocation|changes to fields must be made
use get/set methods.
Implementations
1 package remifc;
2
3 import java.rmi.*;
4
5 public interface FishFinder extends Remote
6 {
7 public static final String NAME
8 = "rmi://magic.voidstar.org.uk/jkf/fishfinder";
9
10 public FishLocation
11 getFish(FishLocation me)
12 throws RemoteException;
13 }
All RMI invocations are made across remote interfaces extending java.rmi.Remote. All
remote methods must throw RemoteException.
Instead of defining a separate IDL and per-language bindings, the Microsoft .NET platform
denes a common language subset and programming conventions for making denitions
that conform to it.
Transactions
We say that a transaction commits atomically (if it completes successfully) or it aborts (if it
fails for some reason). Aborted transactions leave the state wholly unchanged.
In more detail we would like committed transactions to satisfy four ACID properties:
● Atomicity: Either all of the tasks of a transaction are performed or none of them are. The transfer of funds can be completed or it can fail for a multitude of reasons, but atomicity guarantees that one account won't be debited if the other is not credited as well. It must be ensured that no partial transactions are performed (atomicity) and also that apparently-committed transactions aren't lost (durability)
● Consistency: Invariants must be preserved across accounts, eg; totals across
accounts. If an integrity constraint states that all accounts must have a positive balance, then any transaction violating this rule will be aborted.
● Isolation: refers to the ability of the application to make operations in a transaction
appear isolated from all other operations. Isolation means the transaction history is
serializable. Eg. another transaction shouldn't read the source and destination amounts midtransfer and then commit.
● Durability: refers to the guarantee that once the user has been notified of success, the transaction will persist, and not be undone. This means it will survive system failure, and that the system has checked the integrity constraints and won't need to abort the transaction. Typically, all transactions are written into a log that can be played back to recreate the system to its state right before the failure. A transaction can only be deemed committed after it is safely in the log.
Eg; If there was a system failure and something was undone the transaction would
fail durability.
These histories show non-serializable executions in which one read sees an old value and
the other sees a new value:
In general, "cycles" are caused by three kinds of problem:
● Lost updates (e.g. by another transaction overwriting them before they are
committed)
● Dirty reads (e.g. of updates before they are committed)
● Unrepeatable reads (e.g. before an update by another transaction overwrites it)
A concurrent execution is serializable if there is some serial execution of the same
transactions that gives the same result|the programmer cannot distinguish between
parallel execution and the simple one-at-a-time scheme.
Strict isolation: actually ensure that transactions are isolated during their execution|prohibit all three problems.
● Non-strict isolation: ensure that a transaction was isolated before it's allowed to
commit.
● Non-strict isolation may permit more concurrency but can lead to delays on commit
(e.g. a transaction that performed a dirty read cannot commit until the writer has)
and cascading aborts (if the writer actually aborts).
Two Phase Locking 2PL
In two-phase locking (2PL) each transaction is divided into:
a phase of acquiring locks; and a phase of releasing locks.
1 transaction {
2 if (server.getBalance(src) >= amount) {
3 server.credit(dest, amount);
4 server.debit (src, amount);
5 return true;
6 } else
7 return false;
8 }
Could require explicit invocations by the programmer, e.g.
● expose lock() and unlock() operations on the server:
● acquire a read lock on src before 2, release if the else clause is taken;
● upgrade to a write lock on src before 3;
● acquire a write lock on dest before 4;
● release the lock on src any time after acquiring both locks; and
● release the lock on dest after 4.
Some problems can be addressed by Strict 2PL, in which all locks are held until commit/abort:
transactions never see partial updates made by others. Strict 2PL prevents transactions reading
uncommitted data, overwriting uncommitted data, and unrepeatable reads. Thus, it prevents
cascading aborts, since exclusive locks (for write privileges) must be held until a transaction
commits.
Strict 2PL has two rules:
1. If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.
2. All exclusive locks held by transaction T are released when T commits (and not before).
The rules for non-strict 2PL are similar to those of Strict 2PL:
1. If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.
2. A transaction cannot request additional locks on any object once it releases any lock, and it can release locks at any time (not only at commit time as in Strict 2PL).
Advantages:
● Ensures serializable execution if implemented correctly.
● Allows other transactions to access objects as soon as they have been unlocked increases concurrency.
Disadvantages:
● Complexity of programming
● Would be nice to provide startTransaction and endTransaction rather than individual lock operations.
● Risk of deadlock.
● If Tb locks an object just released by Ta then isolation requires that:
- Tb cannot commit until Ta has done so; and
-Tb must abort if Ta does (a cascading abort).
Time Stamp Ordering
Each transaction has a timestamp, eg. of its start time, which are subject to a total ordering. Every object in the database has a read timestamp, which is updated whenever the object's data is read, and a write timestamp, which is updated whenever the object's data is changed.
● The ordering between the timestamps is used to give a serializable order for the transactions.
● Transactions must access objects in the order of their timestamps
If a transaction wants to read an object:
● but the transaction started before the object's write timestamp it means that something changed the object's data after the transaction started. In this case, the transaction is cancelled and must be restarted.
● and the transaction started after the object's write timestamp, it means that it is safe to read the
● object. In this case, if the transaction timestamp is after the object's read timestamp, it is set to the transaction timestamp. If a transaction wants to write to an object,
● but the transaction started before the object's read timestamp it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid so the transaction is aborted and must be restarted.
● and the transaction started before the object's write timestamp it means that something has changed the object since we started our transaction. In this case we simply cancel our transaction and continue as normal; it does not have to be restarted.
● otherwise, the transaction writes to the object, and the object's write timestamp is set to the transaction's timestamp.
Advantages:
● The decision of whether to admit a particular operation is based on information local to the object
● Simple to implement, e.g. by interposing checks on each invocation at the server (contrast with non-strict 2PL).
● Avoiding locking might increase concurrency.
● Deadlock is not possible ( as there are no locks)
Disadvantages:
● Needs a roll-back mechanism.
● Cascading aborts are possible
Eg; if T1,2 had updated A then it would need to be undone and T2 would have to abort because it might have been influenced by T1. You could delay T2,2 until T1 either commits or aborts (stilln avoiding deadlock)....
● -Serializable executions might be rejected if they do not agree with the transactions' timestamps. (e.g. executing T2 in its entirety, then T1).
● Generally: the low overheads and simplicity make TSO good when conflicts are rare.
Optimistic Concurrency Control
OCC is an optimistic schemes assume transactions rarely conflict. Rather than ensuring isolation during execution a transaction proceeds directly and serializability is checked at commit-time.
Transactions use shadow copies of each object it uses (made on first access) so changes remain local/isolated from other transactions.
There are three phases in an OCC transaction:
1 Read
A transaction proceeds by taking shadow copies of each object it uses (when it accesses it
for the first time). It works on these shadows so changes remain local--isolated from other
transactions.
2 Validation
Validation is required to show that the shadows were consistent and that no other
transaction has updated the object in the meantime in a way that conflicts.
If the validation returns ok then the updates are committed to their permanent objects, if
not then the transaction is aborted and retried. Until commit, updates are made locally.
Validation is the complex part of OCC, one way is giving transactions timestamps. During
validation there is a check to see if transactions are in a correct order; if they are then the
transactions cotinue, otherwise the transaction is aborted.
3 Write
If there is no possibility of conflict then the transaction commits.
Persistent Storage- Logging
● Write details of the proposed update to a write-ahead log|e.g. in a simple case
giving the old and new values of the data, or giving a list of smaller updates as a set
of (address,old,new) tuples.
● Proceed through the log making the updates. More generally we can record details
of multiple transactions in the log by associating each with a transaction ID.
Complete records, held in an append-only log, are of the form:
After a transaction has aborted or become deadlocked:
If deadlocked is detected using a deadlock detection algorithm then the transaction can be
aborted and restarted.
Once a transaction has been aborted an algorithm like the following can be used:
The recovery manager keeps UNDO (initialized to set of transactions active at the last
checkpoint) and REDO (initially empty). Search forwards from the (most recent)
checkpoint record:
· Add transactions that start to the UNDO list.
· Move transactions that commit from the UNDO list to the REDO list.
Then work backwards through the log from the end to the checkpoint record:
· UNDOing the effects of transactions on the UNDO list.
Then work forwards through the log from the checkpoint record:
· REDOing the effects of transactions in the REDO list.
Generics
http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
The cast to Integer in this code snippet is typical of Java code pre-1.5, and is annoying.
The programmer knows that the list contains Integers because (s)he put them there. The
type system is getting in the way (and adding run-time overhead).
List listOfInts = new LinkedList();
listOfInts.add(new Integer(42));
Integer i = (Integer) listOfInts.iterator().next();
● The problem is that the compiler can only guarantee that the iterator's next item will be an
instance of java.lang.Object so the cast is needed to perform a run-time check on the type
of the object returned by next().
● Generics allow us to encode sufficient extra information in the source code that the
compiler can relax the requirement for the programmer to cast to the subtype.
With generics:
List<Integer> gil = new LinkedList<Integer> ();
gil.add(new Integer(42));
Integer i = gil.iterator().next(); // whohoo!
How do we write parametrically polymorphic definitions?
public interface List<T> {
void add(T item);
Iterator<T> iterator();
}
public interface Iterator<S> {
S next();
boolean hasNext();
}
We can use T and S as if they were the names of declared types.
Relations
List<String> ls = new ArrayList<String>();
List<Object> lo = ls; // error!
This gives a compile-time error.
In general, List<A> is not a supertype of List<B> (and List<B> is not a subtype of
List<A>).
Wildcards
Because Collection<Object> is not the superclass of other Collections, we cannot write a
method that is able to operate on a collection of \anythings". The type of the argument
supplied to the method would not match that declared type of the parameter.
Instead, we can use wildcards:
void printThemAll(Collection<?> c) {
for (Object e : c) System.out.println(e);
}
The solution to the problem of not being able to insert into collections of unknowns is to
use generic methods.
ECAD
Syllabus
Aims
This course aims to introduce electronic computer aided design (ECAD) with a particular emphasis on the Verilog hardware description language (HDL). The course differs from previous years since the first four lectures have been replaced by an interactive tutor system to teach Verilog (the Intelligent Verilog Compiler, or IVC). The IVC will be used for the first two laboratory sessions and completed as homework. The material the IVC covers is a prerequisite for the remaining seven practical sessions. Material taught is prerequisite for the remaining seven practical sessions.
Lectures
· Introduction and motivation. Current technology, technology trends, ECAD trends, challenges.
· Logic modelling, simulation and synthesis. Logic value and delay modelling. Discrete event and device simulation. Automatic logic minimisation.
· Chip, board and system testing. Production testing, fault models, testability, fault coverage, scan path testing.
· Verilog systems design. Practicalities of mapping Verilog and ARM assembler onto an FPGA board. Signal processing of inputs. Tips and pitfalls when generating larger modular designs.
On-Line Learning Component: Interactive Verilog Compiler
· The interactive Verilog compiler (IVC) teaches the synthesisable subset of Verilog which is required to complete the laboratory sessions.
Objectives
At the end of the course students should
· be able to design, prototype and debug circuits using Verilog targeted at programmable gate arrays (FPGA)
· understand circuit simulation, synthesis and testing concepts
· appreciate hardware/software codesign
Recommended books
The following books are recommended for reference only:
Smith, D.R. & Franzon, P.D. Verilog styles for synthesis of digital systems. Prentice Hall.
Thomas, D.E. & Moorby, P. (1995). The Verilog hardware description language. Kluwer Academic Publishers.
Sternheim, E., Singh, R., Madhaven, R. & Trivedi, Y. (1993). Digital design and synthesis with Verilog HDL. Automata.
From the Part IA Digital Electronics course:
Katz, R.H. (1994). Contemporary logic design. Benjamin/Cummings.
Pointers to sources of more specialist information are included in the lecture notes and on the associated course web page.
Floating-Point Computation
Syllabus
Aims
This course has two aims: firstly to provide an introduction to (IEEE) floating-point data representation and arithmetic; and secondly to show, mainly by fun examples backed up by simple analysis, how naïve implementations of obvious mathematics can go badly wrong.
Lectures
· IEEE Floating-point representation and arithmetic (32 and 64 bits). Overflow, underflow, progressive loss of significance. Rounding modes.
· How floating-point computations diverge from real-number calculations. Absolute Error, Relative Error, Machine epsilon. Solving a quadratic.
· Iteration and when to stop. Why summing a Taylor series is problematic (loss of all precision, range reduction, non-examinable hint at economisation).
· Ill-conditioned or chaotic problems. Testing. Packages. Non-examinable: exact real arithmetic.
Objectives
At the end of the course students should
· be able to convert simple decimal numbers to and from IEEE floating-point format, and to perform simple arithmetic
· be able to identify problems with floating-point implementations of simple mathematical problems
· know when a problem is likely to yield incorrect solutions no matter how it is processed numerically
· know to use a professional package whenever possible
IEEE Floating point
For example, IEEE 754 with 32-bits:
[1xSign Bit][8xExponent bits][23xBits mantissa]
127 is taken away from the unsigned value of the exponent, so a stored value of 1 is interpreted as -126
Value = sign × 2e × mantissa
Where e is the stored value - 127.
Definitions
Emax and Emin represent the maximum and minimum values of e (the exponent) respectively. In IEE754 emax is 127 and emin is -126.
The mantissa's leftmost digit mustn't be zero, ensuring this is called normalization. By doing this you don't need to record the position of a point (unlike with a decimal point in standard decimal system).
Denormalised numbers represent very small numbers.
When a number is normalized, its leftmost mantissa bit is always going to be 1, so it doesn't have to be stored. This is known as the hidden bit.
NaN's (Not a Number) are used when an arithmetic result cannot be returned eg; the square root of a negative number or the result of invalid input.
| Type | Exponent | Mantissa |
| Zeroes | 0 | 0 |
| Denormalized numbers | 0 | non zero |
| Normalized numbers | 1 to 2e − 2 | any |
| Infinities | 2e − 1 | 0 |
| NaNs | 2e − 1 | non zero |
Errors
It is generally more useful to say Π = Π* + Error than to say Π ≈ Π*.
Absolute Error
Given a value a and an approximation of it, b, the absolute error is:
|a-b| ie the difference between the actual and the approximation value.
Relative Error
The relative error is the absolute error divided by the actual value.
Let the true value of a quantity be 
and the measured or inferred value 
. Then the relative error is defined by
|
where 
is the absolute error. The relative error of the quotient or product of a number of quantities is less than or equal to the sum of their relative errors. The percentage error is 100% times the relative error.
Example
What are the absolute and relative errors of the approximation 3.14 to the value π?
Eabs = |3.14 - π| ≈ 0.0016
Erel = |3.14 - π|/|π| ≈ 0.00051
Rounding Errors
The error we get by using finite arithmetic during a computation, as it can't represent all reals.
Truncation Errors
The error we get by stopping an infinitary process after a finite point.
Loss of Significance
Gradual loss of significance is when an error propagates, so whilst say 16 significant figures is stored, in fact say 8 bits may be correctly/accurately stored.
Machine Epsilon
Machine epsilon represents the "distance" between each sequential number in floating point. It is defined in ISO C as the difference between 1 and the smallest representable number greater than 1, i.e. 2^-23 in single precision and 2^-53 in double.
Taylor Errors
The rounding error is mach_eps/h
Interval Arithmetic
Rather than using one floating point number, this uses two: one for a max and one for a min value.
Arbitrary Precision Floating Points
Adaptive precision.
Logic and Proof
Syllabus
Aims
This course will teach logic, especially the predicate calculus. It will present the basic principles and definitions, then describe a variety of different formalisms and algorithms that can be used to solve problems in logic. Putting logic into the context of Computer Science, the course will show how the programming language Prolog arises from the automatic proof method known as resolution. It will introduce topics that are important in mechanical verification, such as binary decision diagrams (BDDs), SAT solvers and modal logic.
Lectures
· Introduction to logic. Schematic statements. Interpretations and validity. Logical consequence. Inference.
· Propositional logic. Basic syntax and semantics. Equivalences. Normal forms. Tautology checking using CNF.
· The sequent calculus. A simple (Hilbert-style) proof system. Natural deduction systems. Sequent calculus rules. Sample proofs.
· Binary decision diagrams. General concepts. Fast canonical form algorithm. Optimisations. Applications.
· First order logic. Basic syntax. Quantifiers. Semantics (truth definition).
· Formal reasoning in FOL. Free versus bound variables. Substitution. Equivalences for quantifiers. Sequent calculus rules. Examples.
· Clausal proof methods. Clause form. A SAT-solving procedure. The resolution rule. Examples. Refinements.
· Skolem functions and Herbrand's theorem. Prenex normal form. Skolemisation. Herbrand models and their properties.
· Unification. Composition of substitutions. Most general unifiers. A unification algorithm. Applications and variations.
· Prolog. Binary resolution. Factorisation. Example of Prolog execution. Proof by model elimination.
· Modal logics. Possible worlds semantics. Truth and validity. A Hilbert-style proof system. Sequent calculus rules.
· Tableaux methods. Simplifying the sequent calculus. Examples. Adding unification. Skolemisation. The world's smallest theorem prover?
Objectives
At the end of the course students should
· be able to manipulate logical formulas accurately
· be able to perform proofs using the presented formal calculi
· be able to construct a small BDD
· understand the relationships among the various calculi, e.g. SAT solving, resolution and Prolog
· be able to apply the unification algorithm and to describe its uses
Recommended reading
* Huth, M. & Ryan, M. (2004). Logic in computer science: modelling and reasoning about systems. Cambridge University Press (2nd ed.).
Ben-Ari, M. (2001). Mathematical logic for computer science. Springer (2nd ed.).
Gentle introduction:
Barwise, J. & Etchemendy, J. (1999). Language proof and logic. CSLI Publications.
Prolog
Aims
The aim of this course is to introduce programming in the Prolog language. The cut operator and assert/retract are included to allow real uses of the language to be understood and to make the language an option to use in a Part II project. The course includes case studies of familiar algorithms in the declarative idiom.
Lectures
· Syntax and Unification. Prolog's slim syntax is described. Unification is described with examples to show how pattern matching is achieved.
· Lists, terms and arithmetic. The Prolog syntax is used to create lists and terms, and to perform simple arithmetic.
· Graphs. Classic graph algorithms are presented in the declarative Prolog style.
· Trees. Classic tree algorithms are presented in the declarative Prolog style.
· Non-determinism. The backtracking mechanism for finding alternative solutions is described and illustrated, with techniques to modify the default behaviour.
· Negation as failure. The reasons why Prolog saying ``No'' differs from ``false'' are discussed and illustrated.
· Difference structures. Difference lists are described and students participate in a re-write of programs from classical lists to difference lists.
· Using difference structures. Copying trees is used as an example to show the optimisations possible for large programs when the difference structure technique is used.
Objectives
At the end of the course students should
· be able to write programs in Prolog using techniques such as accumulators and difference structures.
· know how to model the backtracking behaviour of program execution.
· appreciate the unique perspective Prolog gives to problem solving and algorithm design.
· understand how larger programs can be created using the basic programming techniques used in this course.
Recommended reading
* Bratko, I. (2001). PROLOG programming for artificial intelligence. Addison-Wesley (3rd ed).
About Prolog
Prolog is short for PROgramming in LOGic, it is a logcial and declarative language. It is considered to be a very high level language, and was made particularly popular afte the Japanese government invested in its usage. You can get a good, free interpreter here.
Uses of Prolog
· Natural Language Systems
· AI
· Expert Systems
· Theorem Proving
Creating a Program
Programs are normally written in text editors then interpreted by a prolog implementation. An example of a statment is
likes(mary,food).
Note the full stop, they are important like the ; in other language.
Key commands
· You can see prologs actions as it works through a goal by tyiping trace.
· You can see what information prolog has recorded by typing listing.
Asking a question
You can tell prolog that bob is pats parent with parent (bob, pat).
You can can ask prolog who's pats parent with ?- parent (X, pat). and it should return X=bob.
You can attatch two requirements together with a comma. For example parent (X, Y), parent (Y, pat). will find the grandparent of pat.
There are three kinds of clauses in Prolog:
· Facts declare things that are always true
· Rules declare things are true dependant upon conditions
· Questions return what is true, and what makes a clause true. Unary relations are used to declare simple facts, eg; male(pat).
Goal finding
If a goal fails, prolog backtracks and will try another path.
Objects
Atoms start with a lower-case letter pat is an atom in male(pat).
Variables start with an upper case letter. Structures have multiple components eg; date(13,April,1976)
Lists can be made of any objects, even lists eg; [1, 2, 3, [pat, tom, mary ] ]
Backtracking
Automatic backtracking is useful as it saves you having to program it explicitly, but it can be inefficient. The cut command is used to prevent backtracking when it would be futile or if you don't want multiple answers.
If a variable is used only once an underscore character can be used in its place.
Software Engineering
Syllabus
Aims
This course aims to introduce the students to software engineering, and in particular to the problems of building large systems, safety-critical systems and real-time systems. Case histories of software failure are used to illustrate what can go wrong, and current software engineering practice is studied as a guide to how failures can be avoided.
Lectures
· The software crisis. Examples of large-scale project failure, such as the London Ambulance Service system. Intrinsic difficulties with software.
· The software life cycle. Getting the requirements right; requirements analysis methods; modular design; the role of prototyping; the waterfall, spiral and evolutionary models.
· Critical software. Examples of catastrophic failure; particular problems with real-time systems; the difficulty of achieving ultra-high reliability; verification and validation.
· Quality assurance. The contribution of reviews and testing; reliability growth models; software maintenance and configuration management; life cycle costs.
· Tools. The effect of high-level languages; object-oriented systems and object reuse; an overview of formal methods with some application examples; project planning tools; automated testing tools.
· Large software systems. The role of application domain knowledge; changing requirements; risk reduction versus due diligence; communications failure; organisational factors.
Objectives
At the end of the course students should know how writing programs with tough assurance targets, in large teams, or both, differs from the programming exercises they have engaged in so far. They should appreciate the waterfall, spiral and evolutionary models of software development and be able to explain which kinds of software project might profitably use them. They should appreciate the value of other tools and the difference between incidental and intrinsic complexity. They should understand the software development life cycle and its basic economics. They should be prepared for the organisational aspects of their Part IB group project.
Recommended books
* Pressman, R.S. (1994). Software engineering. McGraw-Hill.
Leveson, N. (1994). Safeware. Addison-Wesley.
Maguire, S. (1993). Writing solid code. Microsoft Press.
Further reading:
Brooks, F.P. (1975). The mythical man month. Addison-Wesley.
Neumann, P. (1994). Computer-related risks. ACM Press.
Report of the inquiry into the London Ambulance Service (SW Thames RHA, 40 Eastbourne Terrace, London W2 3QR, February 1993).
http://www.cs.ucl.ac.uk/staff/A.Finkelstein/las.html
Anderson, R. (2001). Security engineering (Chapters 22 and 23). Wiley. Also available at
http://www.cl.cam.ac.uk/users/rja14/book.html
Introduction
Software Engineering is often overlooked in computer science courses, however experienced programmers should know its value. As software projects increase in size, they likelihood of failure increases up to almost 50%.
Software engineering is hard becuase it is about managing complexity. Much of the incidental complexity can be removed using tools (such as high level languages,time sharing and integrated development environments) but the intrinsic complexity remains.
The following pages are intended to give an overview of this vast subject, and are mainly culled from lecture notes and classic papers.
Rates of Software Engineering Failure
| Requirements | Very High |
| Specification | Low |
| Design | Low |
| Implementation | Low |
| Installation | High |
| Operation | Enormous |
| Maintenance | Very High |
Requirements
The rate of failure is high for requirements as they are developed by two or more groups of people who come from different disciplines and speak different languages.
Specification,Design,Implementation
These activities are done by a group of similarly disciplined professionals.
Installation
Installation is often done by people who weren't involved in the implementation and don't understand the system.
Operation
Operation is often left to people who dont understand the system or what it is meant to achieve.
Robert Courtney, a New York security consultant, examined thousands of security beaches in both industry and government and found that 68% of them were due to careless operations or incompetent operations.
Maintenance
Maintenance is often done as an afterthought by people who dont understand what they are changing.
Stages in the Software Life Cycle
Abstract
The Software Life Cycle Model consists of the System Development Cycle and the System Maintenance Cycle.
The software life cycle (according to IEEE1074) starts with the selection of an appropriate life cycle model followed by recruitment. There are many life cycle models that can be chosen. The following stages are in the sequential order of the Waterfall Model, due to its simplicity and prevalance in software engineering.
· Project planning and a feasibility study are required to determine first of all if a new system is needed, and if it is possible within reasonable costs and time restraints.
· Requirement analysis is one of the first stages in the waterfall model, in which the requirements of the new system are found through interviews with potential users and management, and feedback on prototypes. It is important that those chosen to be interviewed are technically capable or the interviewer can extrapolate what the user wants form their feedback and spot possible requirement contradictions.
· From the requirements a formal specification can be written up; normally a strict and mathematical description of what the system must achieve. These come directly from the requirements, and may follow more informal specifications. When the application is further into the development cycle it will be continuously checked against the specifications to ensure the system fulfils the its required purpose.
· The central stage in the waterfall model is the implementation and (unit & system) testing. Implementation is the most obvious part of creating a system, but often one of the smaller sections time and cost wise. Testing is important to prevent bugs and to test the implementations against the specifications. A failure is generally considered to be when a system doesn't perform as intended, whilst a fault is a programming error that may develop into a failure. It is important testing is thorough,as the earlier a defect is detected the cheaper it is to fix. Testing generally starts during the requirement analysis stage of the software development life cycle. Testing then continues into the development and then execution stages. Unit testing typically follows implementation, followed by integration testing.
· Acceptance, installation and deployment are the final stages of initial development where the software is put into practice and runs actual business. Choices in deployment time and back up strategies in case of system failure are essential for critical services (eg the failure of the LAS to have a back up ambulance system to switch back to after the failed system deployment).
· Training and support of the users then increases the likelihood of correct usage of the system.
· Maintenance can be a very expensive task, as it essentially lasts as long as the system. It may require some of the original programmers to be employed continuously to ensure the correct running of the system and for keeping it appropriately up to date. If requirements change at a late stage it can prove very expensive.
Typically about 40% of development time is spent in the requirements stage of the life cycle, just 20% in the actual implementation and the remaining 40% in testing.
Links & Resources
At the time of writing (Dec 06) the following resources were useful
· Software Develoment Process Wikipedia.org
· Quick Study Notes Computerworld.com
· The Mythical Man Month Fred Brooks
Validation and Verification
Validation
In the waterfall model, validation operations provide feedback from Specification to Requirements and from Implementation/unit testing to Specification.
· Validation can be thought of as "Are we building the righy system?"
Verification
Verification operations provide feedback from Integration/ system testing to Implementation/unit testing, and from operations/maintenance back to Integration/system testing.
· Verification asks "Are we building this system right/correctly?"
The waterfall model is reportedly employed by both the US D.O.D and NASA as their main software development model, due to its strict design practices and clear progress markers. This is despite being described as "risky and invites failure" by W.W.Royce, who . originally created the term "Waterfall model" and criticized it in favor of an iterative approach.
The waterfall model is a top down sequential model split into the sections shown in the software life cycle article, and illustrated by the image below
Image by Paul A. Hoadley, Creative Commons license
Note that:
· Requirements are written in the user's language
· Specification is written in system language
· Unit testing checks units against the spec
· System testing checks the requirements are met
The waterfall model is well understood and time tested but generally considered to be less useful than it once was due to the increasing complexity of systems. It "works well for automating the tasks of clerks and accountants, less well for knowledge works such as experts trying to solve problems" (Information Center Quarterly article, Larry Runge). Another problem is that in the waterfall model users only input is in specifying requirements and that all requirements must be specified at one points before production begins. However, requirements typically change through the process and require more feedback.
Summary of advantages:
· Easy for managers to understand, plan by and to test progress against as it has very clear sequential milestones
· Encourages good design practices such as early clarification of system goals, which in turn save time and money (the earlier a bug is caught, the less harm it can cause)
· Due to lots of up front design planning, should the project be stopped and taken up at a later date, or should project members change, implementation can continue far easier than with more agile development models where there is considerably less design documentation.
· Compatible with a wide range of design strategies
Summary of disadvantages
· Users may change requirements often, at stages beyond the requirements stage
· Users may not be able to state requirements until they see a working prototype that they can criticise
· At the implementation stage programmers may find that there is a near impossible problem to implement, and it may be easier to change the original design than to proceed ahead as planned.
· Constant verification of each stage is required to ensure that the next phase can start on a correct base
· Technology may change during development
Most of the problems of the waterfall model are solved by iterative and evolutionary models such as the Spiral Model
The Spiral Model
Iterative Design
One of the main objections to the waterfall model is that in the real world requirements change during design for a number of reasons: you simply cant create a specification at the start of a project and expect it to be the same when the project is completed.
The solution to these objections is the notion of iterative development, where there is feedback between prototypes and design.
The Spiral Model
The spiral model (Barry Boehm, 1988) attempts to combine the advantages of the waterfall model with the flexibility of an iterative approach.
Advantages
· Estimates (i.e. budget, schedule, etc.) get more realistic as work progresses, because important issues are discovered earlier.
· It is more able to cope with the (nearly inevitable) changes that software development generally entails.
· Software engineers (who can get restless with protracted design processes) can get their hands in and start working on a project earlier.
Further reading
· A Spiral Model of Software Development and Enhancement (PDF) - Barry Boehm's original article
Brooks Law
Abstract
The Mythical Man Month attacked the idea that men and months are interchangeable in software engineering. Brook wrote "Oversimplifying outrageously, we state Brooks' Law:"
"Adding manpower to a late software project makes it later."
Factors
· Communications Complexity The more people, the more communications complexity.
b people means n(n-1)/2 channels and 2n cliques)
· Training new people takes time
Example
Consider a project predicted to take 4 months with 3 men.
· However, the design falls behind and takes 2 months not 1! So there are two months (x3 men = 6 man months) left to do work that was originally estimated at 9 man-months
· 6 men are added to ensure that the project is done in time.
· But tTraining takes 1 month so all the 9 man-months must be done in the last month.
· However, the work that 3 men could do in 3 months can't be done by 9 men in 1 month (complexity, interdependencies, testing, ...) Hence Brooks law, also stated by himself as "The bearing of a child takes nine months, no matter how many women are assigned."
Further reading
· See Boehms Emprical Study for the results of empirical studies into Brooks law.
· Brooks' Law Repealed? IEEE Software, November/December 1999
Critical Software
Safety Critical Software
Systems where failure could cause death or injury are called safety critical systems. For example, nuclear reactor and flight control systems.
Security Cricital Software
Systems where failure could lead to reavealing classified, confidential business or personal data are called security cirtical systems. For example, payroll systems.
Business Critical Software
Systems where failure could affect important operations are called business critical systems.
Example- Patriot Missiles
Anti-missile patrior missiles failed to intercept an Iraqi SCUD missile on 25/2/91- the SCUD struck a US barracks in Dhahran. Other SCUD's got through to Isreal and Saudi Arabia.
Reason for failure
· The system measured time in 1/10 sec, truncated from binary representation .0001100110011....
· As the system was upgraded from anti-aircraft to anti-missile, greater accuracy introduced - but not everywhere in the code
· Two modules got out of step by 1/3 sec after 100 hours operation. Target not acquired
· Defect not found in testing as the spec called for 14 hour continuous operation only
Many critical systems failures are multifactorial: "a reliable system can't fail in a simple way"
Particular Problems of Large Systems
In 1988 Curtis,Kramer and Iscoe studied 17 large systems and why they failed. Over 97 interviews team and organistational factors were investigated. The main findings were that large software projects fail because of 1. A thin spread of applciation domain knowledge
· 2. Fluctuating and conflicting requirements
· 3. Breakdown of communication and coordination
They found the tytpical progression to disaster was 1 -> 2 ->3
Thin spread of application domain knowledge
It is rare to find someone who understands the entire solution. In some areas, eg pilot training, there is a structured effort to overcome this. Otherwise, with luck, you may get a genuine "guru" but even then you can expect specification mistakes.
Changing requirements
Competing products, new standards, new equipment and new users all combine to changing requirements.
Communication problems
Problems with communications increase with the more layers and more managers. Coping mechanisms such as committees increase the hierarchy. Managers are often loth to believe bad news, much less pass it on.
The Capability Maturity Model
By the mid-80's people had begun to realise the importance of keeping teams together. The ability to work as a team grows over time, this is the basis of the "capability maturity model".
As well as a team, good management is required.
Hazards
Hazard Analysis
The Federal Aviation Administration (FAA) recognizes five categories of failure conditions and five software-level definitions.
Categories of Failure
| Failure Condition | Software Level |
| Catastrophic | Level A |
| Hazardous/Severe - Major | Level B |
| Major | Level C |
| Minor | Level D |
| No Effect | Level E |
In practice, the differences between levels A and B are small:
· Certain objectives of the software design process must be independently verified.
· Source code accuracy, consistency, and compliance with the software architecture must be independently verified.
· Robustness of object code with low-level requirements must be independently verified.
· Test coverage of software structure (modified condition/decision) must be satisfied independently for level A, and is optional for level B and lower.
Different hazard categories require different failure rates and ifferent levels of investment in varying software engineering techniques. For example, a nuclear capable US navy cruiser had ten seperate stages of analysis (eg subsystem analysis, radiation hazard analysis, inadvertant launch analysis) which overlapped and on which the development was based, rather than being added retrofitted.
Hazard Elimination
Many hazards can be eliminated by small changes in design.
· Eg Motor reversing circuit:
If the switches dont move together there is a short circuit, and a fire could occur.
The solution is to redesign so it is intrinsically safe. Intrinsically safe software is the holy grail, however this normally requires a system level approach.
Nuclear reactors normally have mechanical fail safes as you can never completely trust software (unless it is a tiny program that you can prove mathematically). Eg pebble bed reactors which are self controlling (as the reactive pebbles and the gas around them heat up, they push each other apart)
Documentation
A typical project has a number of management and engineering documents. As well as being useful for people outside the original development to read, documents can act as a contract.
Engineering Documents
· Requirements
· Hazard analysis
· Specification
· Test plan
· Code
Management Documents
· Contracts
· Budgets
· Activity charts and graphs
· Staff schedules
Methods of Ensuring Sufficient Documentation
· High tech: CASE tool
· Bureaucratic: Plans and controls dept
· Convention: Self documenting code
Testing
Testing can take up to half the cost of development in industry. Bill Gates: "are we in the business of writing software, or test harnesses?"
Testing takes place at a number of levels:
· Validation of the initial design
· Module test after coding
· System test after integration
· Beta test/field trial
· Subsequent litigation
· ...
Note that testing earlier is far less expensive than testing late.
Regression testing
The major advance in package software in the last ten years has been in testing.
Regression testing involves checking that the new version of the software gives the same answers as the old version.
A database is continually updated, containing every bug ever found. Unless all previous bugs are tested for bugs have a ~20% chance of reoccuring unexpectedly. It is best to test data given by real users, as this is what is most likely to be noticed.
Reliability growth models help us asses mean time to failure, the number of bugs remaining and the economics of further testing. It is found emprically. Based on these models the rate of software failure drops exponentially at first, then settles down to decrease at k/t.
Changing testers often makes new bugs visibile, as shown below
Failure to understand the environment in which the system will actually be deployed often leads to incorrect testing and failures. A military approach (a hostile review followed by prolonged field testing) can be very effective, but in industry corporate politics normally prevents a wide uptake of good practices.
Risk Reduction vs Due Diligence
Often one can never be certain about how many bugs are left. Organisations are highly averse to such uncertainty and prfer to avoid risk issues. Legal and cultural pressures replace risk reduction with "due diligence": a standard (but often insufficient) checklist is followed to ensure the legal pressures are satisfied but often not the problem itself.
Summary
A lack of consistent testing can cause programs to behave incorrectly, fail or be insecure. For example in March 2002 it was reported that software bugs in Britain's national tax system resulted in more than 100,000 erroneous tax overcharges. The problem was partly attributed to the difficulty of testing the integration of multiple systems.
Testing is important as there will inevitably be bugs in any program of significant length. These may be caused by a variety of factors at various stages in the development cycle. The earlier a defect is found the cheaper it is to fix -if a product has to be recalled due to a serious fault the cost can be enormous. Inadequate testing may mean no one notices a problem until a vital system crashes. Testing itself however can be very time consuming and expensive and there can never be testing of 100% of real world situations in any program of complexity. More safety critical and military projects will employ greater testing, through large amounts of simulation testing. Often mathematical proofs will be used to show that algorithms work in theory, complementing real world tests.
There are numerous testing techniques and models, application depends upon who the final system is for. Tests can be broadly split into black box tests (external, based on functionality) and white box testing (based on knowledge of the internal workings of the program, following branches etc.) Unit testing tests particular methods and is useful for the micro scale examination of individual parts of a program.
If the product is mass produced a company will generally factor the cost of testing against the possible cost of a recall. For such mass market software often beta testing is used, where large numbers of volunteers test the product and report errors before the final product is shipped. This will test common errors as the people testing are fairly normal users, but they lack the expertise to test extreme cases and to notice many bugs and their causes.
In a "test-driven software development model" unit tests are written first, and as more and more code of the main project is written less and less of the unit tests are failed.
In a clean room process probabilities are assigned to paths users can take both correct and incorrect, and the most common paths are tested more thoroughly. This method was employed by Ericson in their OS development, cutting errors down to 1 per 1000 lines of code, down from the industry average of about 25 per 1000 (Scientific American, 1994).
A good test engineer will have the ability to take the point of view of the customer, a desire for quality and attention and good judgement on where to focus testing efforts with scarce time resources.
Alternative Philosophies and Extreme Programming
Chief Programmer Teams
Chief programmer teams were developed at IBM (70-72) to capitalise on the fact that some programmers are far more productive than others- often by a factor of ten or more.
The team revolves around one chief programmer, one apprentice/assistant, a tool smith, a librarian, an administrative assistant etc. to get the maximum productivity from the available talent.
These teams can be very effective during the implementation stage of a project, and is complementary to project management methodologies eg; Waterfall/ Spiral.
Ego less Programming
Ego less programming (Weinberg, 1971) is in direct opposition to the "chief programmer team" idea; code should be owned by the team not an individual.
Literate Programming
The code should be a work of art, designed not just for the machine but also for subsequent human readers. Code designed to be elegant may take far longer to develop than code designed more practically.
Definitions
Some of these definitions are particular to software engineering, especially the contradictory definitions of fault in computer science and electrical engineering (see below).
· An error is a design flaw, or deviation from the intended state
· A failure has occurred if the system hasn't performed in some subset of the specified environmental conditions
· In Computer Science, a fault is produced by an error which in turn produces a failure. Whereas in electrical engineering an error produces a failure which produces a fault.
· Reliability is measure as the "mean time to failure"
· An accident is an unintended event that results in a specific level of loss
· A hazard is a set of conditions on the system, if occur with certain environmental conditions (ie a failure), will lead to an accident.
· The risk is the probability of a hazard and its severity combined with the exposure (ie how likely the hazard is to cause an accident)
· Safety relates to freedom from accidents
C and C++
Lecturer: Dr A.R. Beresford
No. of lectures: 8
Prerequisite courses: None, though Operating Systems would be helpful.
Aims
The aims of this course are to provide a solid introduction to programming in C and C++ and to provide an overview of the principles and constraints that affect the way in which the C and C++ programming languages have been designed and are used.
Lectures
· Introduction to the C language. Background and goals of C. Types and variables. Expressions and statements. Functions. Multiple compilation units. [1 lecture]
· Further C concepts. Preprocessor. Pointers and pointer arithmetic. Data structures. Dynamic memory management. Examples. [2 lectures]
· Introduction to C++. Goals of C++. Differences between C and C++. References versus pointers. Overloading functions. [1 lecture]
· Objects in C++. Classes and structs. Operator overloading. Virtual functions. Multiple inheritance. Virtual base classes. Examples. [2 lectures]
· Further C++ concepts. Exceptions. Templates and meta-programming. STL generic programming. Examples. [2 lectures]
Objectives
At the end of the course students should
· be able to read and write C and C++ programs
· understand the interaction between C and C++ programs and the host operating system
· be familiar with the structure of C and C++ program execution in machine memory
· understand the object-oriented paradigm presented by C++
· be able to make effective use of templates and meta-programming techniques as used in the STL
· understand the potential dangers of writing programs in C and C++
Recommended reading
* Eckel, B. (2000). Thinking in C++, Vol. 1: Introduction to Standard C++. Prentice Hall (2nd ed.). Also available at
http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html
Kernighan, B.W. & Ritchie, D.M. (1988). The C programming language. Prentice Hall (2nd ed.).
Stroustrup, B. (1994). The design and evolution of C++. Addison-Wesley.
Lippman, S.B. (1996). Inside the C++ object model. Addison-Wesley.
History
C is the successor to B, which was a stripped down version of the BCPL language.
It became particularly popular when the Unix system was re-written in C in 1973.
Abstract
C is a very low level language, and is designed to be as minimal as possible. For this reason it generally produces very efficient programs that are simliar to those hand coded in assembler.
In particular, C has the following properties:
· Weak typing: For example you can create a character then treat it as an integer.
· A very simple core language, which relies heavily on importing libraries for extended functionality
· A preprocessor, which performs simple text manipulations
Hello World
As always, the best introduction to C is through a very simple introduction:
/* The pre-processor replaces this line with the contents of stdio.h */
#include
/* The special function main, which is loaded first, returns an integer and takes no arguments */
int main(void)
/* Call the function printf, included in stdio.h, with the string "Hello, world" */
{printf("Hello, world\n");
/* Return a 0, to indicate successful execution */
return 0;
} Compiled with:
$ cc example1.c
Execute program with:
$ ./a.out
Hello, world
Basic Types
C has a small set of built-in types:
| type | description | format | example |
| char | characters (>8 bits) | character | 'c' |
| int | integer values (> 16 bits, normally one word) | number, escape sequence etc. | 12 |
| long int | long integers | suffix L | 2165L |
| float | ~real | Number with '.','e',or 'E' and suffix f | 1.23e45f |
| double | ¬real | number with '.','e' or 'E' | 1.324e5 |
Data type sizes
Data type sizes are platform specific, the following is a typical example:
Type Bytes Bits Range
short int 2 16 -32,768 -> +32,767 (32kb)
unsigned short int 2 16 0 -> +65,535 (64Kb)
unsigned int 4 32 0 -> +4,294,967,295 ( 4Gb)
int 4 32 -2,147,483,648 -> +2,147,483,647 ( 2Gb)
long int 4 32 -2,147,483,648 -> +2,147,483,647 ( 2Gb)
signed char 1 8 -128 -> +127
unsigned char 1 8 0 -> +255
float 4 32
double 8 64
long double 12 96
Source: phim.unibe.ch
Variables
Variables must be defined exactly once, eg;
int i = 4;
· Global or static variables are declared outside variables and are accesible anywhere. Static is used with global variables and functions to set their scope to the containing file.
· A const variable can only be assigned a value when it is defined. Egg;
const int *const p is a const pointer to a const int
· The volatile keyword can be used the warn the compiler that a variable may be affected by hardware etc.
typedef can be used to create synonyms for types, eg;
typedef Wheels int;
Wheels w = 5;
Operators
| type | operators |
| arithmetic | + - * / ++ -- % |
| logic | == != > >= < <= || && ! |
| bitwise | | & << >> ^ ~ |
| assignment | = += -= *= /= %= <<= >>= &= |= ^= |
Enum
Enumeration is used to set constants. It will automatically assign the predecessor +1 unless otherwise specified.
For example:
enum boolean {F,T,FALSE=0,TRUE,N=0,Y}
Will assign F=0,T=1,FALSE=0,TRUE=1,N=0,Y=1.
Type Conversion
Unlike Java, C allows you to treat variables pretty much as what you want. You can also assign larger types (eg float) to smaller types (eg chars), causing an overflow but no compiler error eg;
int i = 1234;
char c;
c = i+1; /* i overflows c */
Arrays
One or more objects of the same type can be grouped into an array. Eg;
long int j[5];
Strings are just arrays of characters, terminated with the special \0 character.
char hi[] ="hello world";
C doesnt require you to set the size of string arrays, saving you having to work it out yourself.
When passing multi dimensional arrays to a function the the first dimension doesnt have to be specified as you will get setting it later. Eg;
void example(int i[][3]) { }
Functions
A function that is defined without values, eg example(), means that the arguments shouldnt be type-checked.
Void functions dont return values.
A function can be declared inline, telling the compiler insert the complete body of the function in every context where that function is used.
The Pre-Processor
The pre processor can be used for textual substitutions. Note that it is only used as a "search and replace" tool before the compiler.
We have already met #include, used to copy a file into the source.
There are also conditional directives, #if #else #elif #endif
Particularly powerful is define:
#define PI 3.141592654 /*Replaces PI with 3.141592654
#define square(a) (a)*(a) /*Replaces a with a*a */
Pointers
In the example above, ppi is a pointer to a pointer, pi, which is a pointer to the integer value 7.
Pointers just contain the memory address of what they point to. The more memory, the larger pointers will have to be.
| operator | description | example |
| * | Retrieve/set the value pointed to | int x = *pi; x now contains the value that pi points to, 7. |
| int *pi = 5; The value that pi points to, i, is now set to 5. |
||
| & | Returns the memory address | int x = π x now contains the memory address pi points to, 0x9d. |
The void pointer, void *p, can be used to point to any type. Whilst useful in dealing with dynamic memory, it is bad practice to use it unless necessary.
Pointers can be used to index into arrays. Eg; char str[] "hello";
char *pc = str; /* pc now points to the beginning of the array */
*pc = &str[1]; /* pc now points to the second element : h */
Pointer Arithmetic
If pc points to the first element, after pc +=2;, pc then points to the third element.
pc[2] represents the value of the element two head of the element pointed to by pc.
Structures
Creating a structure creates a new type that contains one or more variables. For example:
struct square {int x; int y}; /* Define a structure square */
struct square c = {3,4}; /* Create an instance of square *
Members can be accessed with structname.member;
You can also create a pointer to a strucutre with struct square *pc
A structure can contain a member that is a pointer of the same type, eg; trees and linked lists.
Unions
A union is a single variable which can hold one of a number of different types, its size is that of the largest member.
Bit Fields
Bit fields are low level access to individual bits of a word. Specified inside a struct.
Volatile, Const, Typedef and Inline
The volatile keyword can be used to state that a variable can be changed by hardware.
A const variable can only be assigned a value when it is defined.
Typedef creates a synonym for a type.
Inline tells the compiler to call the function faster.
Dynamic Memory Allocation
Dynamic memory allocation is supplied by stdlib.h with malloc.
C++
Major Updates
C++ introduces bool.
Enumerations define a new type.
References are alternate names for variables.
It is efficient to pass large structs as references.
Operators can be overloaded.
Calling Functions
Overloaded functions have the same number but different argument types. Type conversion is used for a best match.
Default arguments come after non-default arguments.
The use of a function or variable from a different namespace must be qualified by the name of the namespace.
To get a function to accept any type, ie polymorphic behaviour, declare it virtual. Selecting the right function is a run time decision.
Classes
Classes have access control private, protected and public.
A class defined with struct has members with default access public, defined with class they're default acces is private.
A member function with the same name as the class is the destructor. One constructor can be named.
The keyword this returns a pointer to the current object.
An unreferenced temporary object exists only during execution of a full expression.
A friend function can access the private members of a class instance it befriends.
Classes can inherit features of another class using :
Exceptions
If an exception is thrown the stack is unwound until a function is found that catches the exception.
A class is often used to define an exception.
Templates
Templates allow code to be evauluated at compile time rather than run time, and allow types to be parameters in a program.
Eg; template<class T> class Stack {
Where class T can be any C++ type.
Compiler Construction
Syllabus
Compiler Construction
Lecturer: Dr T.G. Griffin
No. of lectures: 18
This course is a prerequisite for Optimising Compilers (Part II).
Aims
This course aims to cover the main technologies associated with compiling programming languages, viz. lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation.
The course will be based around the study a simple compiler called MinCaml (http://min-caml.sourceforge.net/index-e.html) that was designed and implemented by Eijiro Sumii at the University of Tokyo. Dr Griffin will also make available extensions to this compiler tailored to the needs of this course.
Lectures
· Survey of execution mechanisms. The spectrum of interpreters and compilers; compile-time and run-time. Structure of a simple compiler, virtual machines.
· Lexical analysis and syntax analysis. Regular expressions and finite state machine implementations. Parsing algorithms: recursive descent and SLR(k)/LALR(k). Abstract syntax tree; expressions, declarations and commands. Summary of Lex and Yacc.
· Simple type-checking. Type of an expression determined by type of subexpressions; inserting coercions.
· Translation phase. Intermediate code design. Translation of expressions, commands and declarations. Compilation as a sequence of translations.
· Low-level representations. Variable binding, functions, higher-order functions. Environments, function values are closures. Free variable treatment, static and dynamic chains, ML free variables. Argument passing mechanisms. Objects and inheritance; implementation of methods. Storage allocation, garbage collection.
· Code generation. Typical machine codes. Code generation from intermediate code.
· Object modules and linkers. Resolving external references. Static and dynamic linking.
Objectives
At the end of the course students should understand the overall structure of a compiler, and will know significant details of a number of important techniques commonly used. They will be aware of the way in which language features raise challenges for compiler builders.
Recommended reading
* Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions. The ML edition is best for this course). Cambridge University Press.
* MinCaml code and documentation. http://min-caml.sourceforge.net/index-e.html
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: principles, techniques and tools. Addison-Wesley.
Bennett, J.P. (1990). Introduction to compiling techniques: a first course using ANSI C, LEX and YACC. McGraw-Hill.
Levine, J.R. (1999). Linkers and loaders. San Francisco: Morgan Kaufmann.
Languages
A language is a set of strings; each string is a finite sequence of symbols taken from a finite aplhabet. For parsing, the strings are source programs, the symbols are lexical tokens, and the alphabet is the set of token types returned by the lexical analyzer.
A leftmost derivation is one in which the leftmost nonterminal symbol is always the one expanded; in a rightmost derivation, the rightmost nonterminal is always next to be expanded.
A grammar is ambiguous if it can derive a sentence with two different parse trees.
Grammars whose predictive parsing tables contain no duplicate entries are called LL(1).
Recursive descent, or predictive, parsing works only on grammars where the first terminal symbol of each subexpression provides enough information to choose which production to use.
First(y) is the set of all terminal symbols that can be any string derived from y.
Follow(x) is the set of terminals that can immediately follow x.
When computing first set of (X Y) it x is nullable you also have to take into account Y.
Eg for the grammar:
| Z -> d | Y -> | X->Y |
| Z -> X Y Z | Y -> c | X -> a |
| Nullable | FIRST | FOLLOW | |
| X | yes | A c | A c d |
| Y | yes | c | A c d |
| Z | no | A c d |
Eliminating left recursion:
The two productions
E -> E + T
E -> T
are certain to cause duplicate entries in the LL(1) parsing table, since any token in FIRST(T) will also be in FIRST(E + T). The problem is that E appears as the first right-hand-side symbol in an E production; this is called left recursion. To eliminate left recursion, rewrite using right recursion.
The common way to rewrite is
A -> A a.
A -> b.
|
v
A -> b A'.
A'-> a A'.
A'-> .
To re-write using right recursion
Simliarly we can rewrite
S -> if E then S else S
S -> if E then S
As:
S -> if E then S X
X ->
X -> else S
From old notes
3.1 Type 2 grammar
In the Chomsky type 2 grammar the left hand side of every production is restricted to just a single
non-terminal symbol. Such symbols are often called syntactic categories. Type 2 grammars are known as context-free grammars and have been used frequently in the specification of the syntax of programming languages, most notably Algol 60 where it was first used. The notation is sometime called Backus Naur Form or BNF after two of the designers of Algol 60. A simple example of a type 2 grammar is as follows:
S −> A B
A −>! a
A −>A B b
B −> b c
B −> B a
A slightly more convenient way of writing the above grammar is:
S −> A B
A −> a | A B b
B −> b c | B a
The alphabet for this grammar is {S, A, B, a, b, c, d}. The non-terminals are S, A, B being
the symbols occurring on the left-hand-side of productions, with S being identified as the start
symbol. The terminal symbols are a, b, c, d, these being the characters that only appear on the right hand side. Sentences that this grammar generates include, for instance:
abc
abcbbc
abcbca
abcbbcaabca
 |
Where the last sentence, for instance, is generated from the sentence symbol by means of the following productions:
A grammar is ambiguous if there are two or more ways of generating the same sentence.
Convince yourself that the follow three grammars are ambiguous:
a) S −> A B
A −> a | a c
B −> b | c b
b) S −> a T b | T T
T −> a b | b a
c) C −> if E then C else C | if E then C
This is the most restrictive of the phrase structured grammars. In it all productions are limited to being one of the following two forms:
A −> a
A −> a B
That is, the right hand side must consist of a single terminal symbol possibly followed by a single non-terminal. It is sometimes possible to convert a type 2 grammar into an equivalent type 3 grammar. Try this for the grammar for floating point constants given earlier.
Type 3 grammars can clearly be parsed using a finite state recogniser, and for this reason
they are often called regular grammars.
6.1 Relevant JVM instruction set
The JVM has already been covered in the course "Computer Design". This section can be seen as a reminder which focuses on particular points relevant to compilation.
In these notes the stack is upwards growing,6 so that subsequent parameters and local variables occupy increasing memory locations (this is not necessary for the JVM but makes the pictures easier to understand). The version of the JVM we present has a stack-pointer SP register which points to the first free location on the stack. In addition, it has a so-called frame-pointer FP register which points to a constant place during the activation of a procedure. Although strictly not necessary, this simplifies explanations and aids debuggers, since local variables will remain at the same constant offset from FP but their offset from SP will vary during pushes and pops to the stack. Evaluation of a procedure uses a stack frame which will be addressed from FP. Note that both arguments and local variables are addressed as negative offsets from FP. A stack frame has
the following form:
Here FP points to (or rather into) the current stack frame. FP points to the so-called linkage information which allows a function call to return. This consists of the previous value of FP, here called FP0 and a pointer L (the return address) to the machine instruction to be next evaluated after the function's return. To the left (at lower addresses) of the linkage information are stored the function's parameters and (user-declared) local variables; on the right is the local stack (used for evaluating temporaries and for storing arguments), SP is a pointer to the first free cell of this (which coincides with the first free cell of the whole stack). To clarify explanations of function call, we will use the word parameters to refer to the identifiers holding arguments to the current procedure and restrict the word arguments to refer to expressions which are being, or have been,
evaluated on the stack in order to be passed to a further function. At the end of each Java
statement we can expect the local stack to be empty and hence SP to point exactly two words further along the stack from FP. In general these notes will assume that the JVM stack is an array of (32-bit) words, and so addresses of stack items will differ by one.
8.2 Dynamic linking
Consider a situation in which a user has many small programs (maybe 50k bytes each in terms of object files) each of which uses a graphics library which is several megabytes big. The classical idea of linking (static linking) presented above would lead to each executable file being megabytes big too. In the end the user's disc space would fill up essentially because multiple copies of library code rather than because of his/her programs. Another disadvantage of static linking is the following.
Suppose a bug is found in a graphics library. Fixing it in the library (.OBJ) file will only fix it in my program when I re-link it, so the bug will linger in the system in all programs which have not been re-linked--possibly for years.
An alternative to static linking is dynamic linking. We create a library which defines stub
procedures for every name in the full library.
9.13 Static and dynamic scoping
This final point is worth a small section on its own; the normal state in modern programming languages is that free variables are looked up in the environment existing at the time the function was defined rather than when it is called. This is called static scoping or static binding or even lexical scoping; the alternative of using the calling environment is called dynamic binding and was used in many dialects of Lisp. The difference is most easily seen in the following example:
let a = 1;
let f() = a;
let g(a) = f();
print g(2);
Check your understanding of static and dynamic scoping by observing that this prints 1 under the former and 2 under the latter.
You might be tempted to believe that rebinding a variable like `a' in dynamic scoping is
equivalent to assigning to `a'. This is untrue, since when the scope ends (in the above by g being exited) the previous binding of `a' (of value one) again becomes visible, whereas assignments are
not undone on procedure exit.
10.1 Evaluation Using a Stack--Static Link Method
We saw in the first part of the notes how the JVM uses a stack to evaluate expressions and function calls. Essentially, two registers (FP and SP) respectively point to the current stack frame and its fringe.
Evaluation on a stack is more efficient than in the lambda-interpreter presented above in
that no search happens for variables, they are just extracted from their location. However, the JVM as defined only provides instructions which can access local variables (i.e. those on the local stack frame accessed by FP) and static variables (often called global or top-level variables in other languages) which are allocated once at a fixed location.
Indeed Java forbids the textual nesting of one function within another, so the question of how to access the local variables of the outer function from within the inner function does not need to be addressed in the JVM. However, for more general languages we need to address this issue.
The usual answer is to extend the linkage information so that in addition to holding the return address L and the old frame pointer FP0, also known as the dynamic link as it points to the frame of its caller, it also holds a pointer S, the static link17 which points to the frame of its definer.
Other notes
1. x+y*z:
<Exp> => <Exp> + <Term> => <Term> + <Term> => <Factor> + <Term> => x + <Term> => x + <Term> * <Factor> => x + <Factor> * <Factor> => x + y * <Factor> => x + y * z
x+y*z: Full derivation-tree of non-terminals and replacements.
The result of parsing is often returned as a parse-tree based on a simpler abstract syntax. The abstract syntax corresponds to the datatype of parse trees returned by the parser.
x+y*z: Parse tree.
2. (x+y)*z:
Parentheses '(' and ')' can be used to force a different parsing:
(x+y)*z: Full derivation-tree of non-terminals and replacements.
(x+y)*z: Parse tree.
Note that parentheses do not appear in any parse tree. They directed the parser to build a certain tree and after that they are unnecessary. The structure of the tree shows the binding of operators to operands without the need for (). Parentheses are only needed in strings.
· Formal Grammars and Languages:
· Definition of formal grammar (start symbol, terminal symbols, non-terminal symbols, grammar rules). (Also called a context-free grammar or a BNF grammar.)
· Derivation sequences (leftmost and rightmost).
· Language accepted by (or recognized by) a formal grammar.
· Parse trees. (Each derivation sequence determines a unique parse tree, but a parse tree might have many derivations.)
· Ambiguity. (Definition: There is a sentence with more than one parse tree, or with more than one leftmost derivation, or with more than one rightmost derivation.)
· Ambiguity is bad.
· Remove ambiguity by either:
· rewriting the grammar, such as changing
E ----> E + E (AMBIGUOUS)
E ----> E * E
E ----> ( E )
E ----> id
to
E ----> E + T (NOT AMBIGUOUS)
E ----> T
T ----> T * F
T ----> F
F ----> ( E )
F ----> id
· introducing special rules, such as
· Precedence of one operator over another. (Present with + and * in the first example above.)
· Associativity of an operator (left-to right or right-to-left). (Present with both + and * in the first example above.)
· Rule that an else matches then nearest unmatched if. (Present in the following example:
stmt ----> "if" "(" expr ")" stat (AMBIGUOUS)
stmt ----> "if" "(" expr ")" stat "else" stat
· Parsers and the Use of Grammars:
· Recursive Descent Parsers:
· Top-down parser, starts with the start symbol and works down toward the given sentence (string of terminal symbols), constructing a leftmost derivation).
· Must rewrite grammar to avoid left recursion. (There are other possible problems also, beyond the scope of this course.) The simple grammar above would be rewritten:
E ----> T { "+" T } ({} means "zero of more times")
T ----> F { "*" F } (terminals are in quotes or id)
F ----> "(" E ")"
F ----> id
· Write a function corresponding to each non-terminal symbol in the grammar. The code of the function mirrors the right side of the rule.ｄｆｄｆｄ
Important notes (new)
Compilation as a sequence of transformations
 |
● Each transformation preserves semantics
● Each transformation addresses only one aspect of "the gap"
● Each transformation is fairly easy to understand.
In: Program Text
The compiler composes of a front, middle and back end
Front-end
Lexical Analysis
Analysis of the text to find meaning and validity, based on finite automaton and regular expressions.
The lexical tokens that the program text is split into are passed down to Parsing
Parsing
Parsing theory based on push-down automaton and context-free grammars.
This stage outputs error messages and a Parse Tree.
A simple parse tree
Middle End
Analysis of symbol definitions and use
This stage outputs errors such as variables not being declared. The parse tree is annotated and then passed on..
Type Checking
Type errors are reported here. The annotated parse tree is then passed on again..
Intermediate code generation
Depending on the compiler, intermediate code is now created. It may be optimised using optimisation algorithms, then a targeted assembly language file is outputted.
Back End
The assembly code is then assembled into an object code file, then linked with object code libraries.
Out: Machine code program
http://www.cs.ucl.ac.uk/staff/l.capra/teaching/2010/2010-regexp.pdf
 |
Common example:
let rec compose f g =
let rec composed x = g (f x) in
composed in
let rec dbl x = x + x in
let rec inc x = x + 1 in
let rec dec x = x - 1 in
let h = compose inc (compose dbl dec) in
print_int (h 123)
let LABEL(composed) [f, g] x = let TMP1 = APPLY_CLOSURE(f x) in APPLY_CLOSURE(g TMP1) in
let LABEL(compose) [] f g = let cl = (LABEL(composed); [f, g] ) in cl in
let LABEL(dbl) [] x = (x + x) in
let LABEL(inc) [] x = let TMP1 = 1 in (x + TMP1) in
let LABEL(dec) [] x = let TMP1 = 1 in (x - TMP1) in
let closure dbl = ( LABEL(dbl); [] ) in
let closure inc = ( LABEL(inc); [] ) in
let closure dec = ( LABEL(dec); [] ) in
let TMP2 = APPLY_DIRECT(LABEL(compose) dbl dec) in
let h = APPLY_DIRECT(LABEL(compose) inc TMP2) in
let TMP3 = 123 in
let TMP4 = APPLY_CLOSURE(h TMP3) in
APPLY_DIRECT(LABEL(min_caml_print_int) TMP4)
Solutions:
Restrict programming language so the problem goes away! That is, use FORTRAN.
Force programmer to worry about it (use malloc and free in C...)
Automation
Reference Counting
Mark and Sweep
Copy Collection
Generational Collection
... there are other techniques...
Computation Theory
Aims
The aim of this course is to introduce several apparently different formalisations of the informal notion of algorithm; to show that they are equivalent; and to use them to demonstrate that there are uncomputable functions and algorithmically undecidable problems.
Lectures
· Introduction: algorithmically undecidable problems. Decision problems. The informal notion of algorithm, or effective procedure. Examples of algorithmically undecidable problems. [1 lecture]
· Register machines. Definition and examples; graphical notation. Register machine computable functions. Doing arithmetic with register machines. [1 lecture]
· Universal register machine. Natural number encoding of pairs and lists. Coding register machine programs as numbers. Specification and implementation of a universal register machine. [2 lectures]
· Undecidability of the halting problem. Statement and proof. Example of an uncomputable partial function. Decidable sets of numbers; examples of undecidable sets of numbers. [1 lecture]
· Turing machines. Informal description. Definition and examples. Turing computable functions. Equivalence of register machine computability and Turing computability. The Church-Turing Thesis. [2 lectures]
· Primitive recursive functions. Definition and examples. Primitive recursive partial function are computable and total. [1 lecture]
· Partial recursive functions. Definition. Existence of a recursive, but not primitive recursive function. Ackermann's function. A partial function is partial recursive if and only if it is computable. [2 lectures]
· Recursive and recursively enumerable sets. Decidability and recursive sets. Generability and recursive enumeration. Example of a set that is not recursively enumerable. Example of a recursively enumerable set that is not recursive. Alternative characterisations of recursively enumerable sets as the images and the domains of definition of partial recursive functions. [2 lectures]
Objectives
At the end of the course students should
· be familiar with the register machine and Turing machine models of computability
· understand the notion of coding programs as data, and of a universal machine
· be able to use diagonalisation to prove the undecidability of the Halting Problem
· understand the mathematical notion of partial recursive function and its relationship to computability
· be able to develop simple mathematical arguments to show that particular sets are not recursively enumerable
Recommended reading
· Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to automata theory, languages, and computation. Addison-Wesley (2nd ed.).
Cutland, N.J. (1980). Computability. An introduction to recursive function theory. Cambridge University Press.
Davis, M.D., Sigal, R. & Weyuker E.J. (1994). Computability, complexity and languages. Academic Press (2nd ed.).
Sudkamp, T.A. (1995). Languages and machines. Addison-Wesley (2nd ed.).
Hilberts Decision Problem
Is there an algorithm which, when given any formal mathematical statement in first order logic determines in a finite number of operations whether the statement is provable ?
If there was we could solve problems such as Goldbach's Conjecture (can all even numbers be written as the sum of two primes?)
You can specify the decision problem with a set S of datastructures/formulae and a property P of elements of S (eg that it has a proof). The prolem is then to find an algorithm which will return 1 iff the S it is fed has property P.
What is an algorithm?
Turing proved that both his Turing machines and Lambda's calculus were computationally equivalent.
-Expand this from Wiki
The Halting Problem
This is the decision problem with S=set of all pairs (A,D) where A is an algorithm and D is a datum on which it is designed to operate, P= "when A is applied to D it eventually halts".
Sketch of the proof:
H(A,D)= { 1 if A(D) halts, 0 if A(D) otherwise/doesn't halt }
If there was such an algorithm H, we could define an algorithm C:
C(A)= { Halt if H(A,A) is 0/Loops, Loop if H(A,A) is 1/Halt }
By setting A=C we derive a contradiction:
C(C) will halt if H(C,C) loops ie if C(C) loops.
C(C) will loop if H(C,C) halts ie if C(C) halts.
The final step in the proof of the undecidability of Hilberts Decision Problem was to construct an algorithm to encode instances A(D) as arithmetic statements: so if the arithmetic statement was provable then A(D) halted.
Diophantene Equations
"Given an algorithm which, when started with any Diophantine equation, determines in a finite number of steps whether there are natural numbers satisfying the equation."
This was later shown to be equivalent to the halting problem, and hence unsolvable.
Notation
A partial function from a set X to a set Y is specified by any subset f ⊆ X x Y satisfying (x,y) ε f & (x,y') ⊆ f => y=y'
f(x)=y means (x,y)ε f
f(x)ê means there is some y such that (x,y)ε f
f(x)é means there is no y such that (x,y)ε f
Pfn(X,Y)= set of all partial functions from X to Y
Fun(X,Y)= set of all total functions from X to Y
Register Machines
Elementary Operations
· Add 1 to a natural number
· Test whether a natural number is 0
· Subtract 1 from a positive natural number
· Jump
· Conditional (If-then-else)
Components
Finitely many registers R0,...,Rn
A program consisting of a finite list of instructions of the form
Label: body of instruction
Instructions labelled sequentially from 0.
There are three instructions:
L: R+ -> L' Add 1 to contents of register R and jump to instruction labelled L'
- L: R- -> L', L'' If contents of R is > 0, subtract 1 from it and jump to L', otherwise jump to L''
L: HALT
A computation either continues forever, obeys a HALT, or jumps to a non-existant label (erroneous halt).
The relation between initial and final register content defined by a register machine is a partial function.
A partial function f(x)=y is register machine computable if a register M can start with x in Rin and 0 in all other registers halts with Rout containing y.
f(x0,...,xn)=y is register machine computable iff there is a register machine M with at least n registers R0,...,Rn if starting with x0-xn in R0-Rn the machine halts with R0 containing y.
Coding Register as Numbers
A key part of the Turing/Chruch solution of Hilberts decision problem was the ability to describe algorithms as numbers.
Pairs
í x,y î = 2x.(2y+1)= |y in binary|1|x 0's|
< x,y > = 2x.(2y+1)-1=|y in binary|0|x 1's| (So you can have 0)
Eg;
í 0,0 î = 20(0+1)=1
Lists
N* = set of finite lists = {} U N U ... U Nn (lists of length N) U ...
You can apply cons, head and tail to a list.
[nil]=0
Cons(x,l)= í x,l î = 2x.(2l+1)
Thus [x1,...,xn]= íx1, íx2,... íxn,0î .. î î
[x1,...,xn]= |1| xn 0's| 1|xn-1 0's| ... | 1 | x1 0's|
Eg;
[2,1,3] = 100010100
Note the reversal of order when reading in binary.
Coding Programs
The (i+1)th instruction in the program listing is labelled Li.
If a program Prog is
L0: body0
L1: body1
...
Lm: bodym
Then [Prog] = [cody(body0),...,code(bodym)]
Where:
code(R+ -> Lj) = í 2i,j î
code(Ri- -> Lj, Lk) = í 2i+1, <j,k> î
code(HALT) = 0
Decoding a program
Any natural number decodes uniquely as a program: first decode as a list [x1,...,xn] and then decode each xi as an instruction:
- If x =0 then the instruction is HALT
- Else decode x as a pair í y,z î and
- If y is even then instruction is
Ri+ -> Lj where i=y/2 & j=z
-
- Else (y is odd and) decode Z as a pair Z=<u,v> and the instruction is
Ri- -> Lj, Lk where I = (y-1)/2, j=u & k=v
Example:
666 = 1010011010 = [1,1,0,1,1]
0= HALT
1= í 0,0 î (as 20(0+1) ), y=0 & z=0, y is even, i=0/2 & j=z=0, R0+ -> L0
2= í 1,0 î = í 1, <0,0> î, R0- -> L0,L0
So the program is
L0: R0+ -> L0
L1: R0+ -> L0
L2: HALT
L3: R0- -> L0,L0
L4: R0+ -> L0
Universal Register Machine
U has registers P(rogram), A(rgument).
Loading P with e (The index of a program) and A with a (the value of the registers), U will decode e as a program and run it with a as a list of register values and carry out the computation.
U will:
1 Copy P to T, and the PCth (currently executing) item in T to N
2 Decode N
3 Remove register values in A up to one required, putting in R and saving preceding values in S
4 Execute instruction on value in R, update PC, restore register values from R and S to A, loop to 1
The registers of U
P- Code of register machine to be simulated
A- Current contents of registers of the register machine being simulated
PC- Program counter - holds the number of the current instruction
N- Holds the code of the current instruction
C- Indicates the type of the current instruction
R- Holds the contents of simulated machines register that is to be incremented/decremented by current instruction
T- Holds a working copy of the program code
S,Z- Auxilarry registers for intermediate computations
The Halting Problem, in terms of register machines
A register machine H decides the Halting Problem if, loading R1 with e and R2 with [a1,...,an], the computation of H halts with R0 containing either 0 or 1;
R0 contains 1 at halting iff the computation of the program e with registers set to [a1,...,an] does halt.
Let C be obtained from H by replacing START by
(where Z is a register not mentioned in H's program)
Ie So when you start C with R1=C you also set the registers (a1,...,an in R2) to be C.
And also by replacing all HALTs (and jumps to a label with no instruction) with:
Ie So C halts when H halts with R0=0 ie if the computation of e loops forever.
So:
C started with R1=C eventually halts iff
H started with R1=C halts with R0=0 iff
Progc started with R1=C does not halt iff
C started with R1=C does not halt
Contradiction.
Undecidable Sets of Numbers
A subset S of N is register machine decidable iff there is a register machine M with the property that when started with R1= x always halts with R0 containing 0 or 1; moreover R0=1 iff x is an element of S.
S is called undecidable if no such M exists. Ie if you can't work out if something is a member of S then S isn't decidable.
For example:
S1 = {<e,a> | фe(a)! }
Ie A one argument version of the Halting Problem
S ⊆ N is decidable iff the characteristic function of S
Xs(X)={ 1 if x є S, 0 if x ! є S
is computable. Such subsets are also called recursive.
Informal Definition of a Turing Machine
The machine starts with the tape head pointing to 
Computes in discrete steps, the result of which depends only on current state and symbol at tape head position
Possible actions are:
- Overwrite current tape cell with a symbol
- Move left, right, or stay stationary
- Change to another state
Formal Definition
- A finite set Σ of tape symbols containing (first symbol) and
(blank symbol) - A finite set K of machine states containing a special element S= initial state
- The transition function ð є Fun (K x Σ, K U {acc,rej} x Σ x {L,R,S})
ð(q,a) = (q',a',D)
q=current state, a=current tape symbol, q'=next state,a'=next symbol,D=direction
· If q' = acc the machine has reached an accepting state (it overwrites a with a' then halts)
· If q' = rej the machine has reached a rejecting state (it overwrites a with a' then halts)
· If q' є K the machine:
o Overwrites a with a'
o Changes to state q'
§ Moves one cell Left if D=L
§ Moves one cell Right if D=R
§ Stays stationary if D=S
A Turing machine can be specified by (q,l,r)
q: Current state є K U {acc, rej}
l: Finite non-nil list of elements of Σ starting with the current symbol, reading to the left, and ending with
r: Finite, possibly nil, list of elements to the right of the current symbol
The transition relation holds iff the order of l and r are preserved.
Example Turing Machine Computation
If a Turing machine is in state q and reads the value 0 and the relevant part of the transition function is:
| 0 | |
| q | (q',1,R) |
| q' | (rej,1,S) |
It would overwrite the 0 with a 1, go into state q' and move to the right. Say the character on the right was also a 0, the Turing machine would write a 1 and halt in a rejecting state.
Turing machines can be implemented by register machines
- Number all states (including acc,rej,S) and all tape symbols (including and )
- Use the coding of lists to code Turing machine configurations (q,l,r) as numbers [q,[l],[r]]
- Use registers S(tate), T(ape symbol), D(irection, L=0 R=1 S=2 say)
ð(S,T) = (S,T,D)
- Use registers C to hold codes of Turing machine configurations
- L to hold codes of current tape symbol and all to the left
- R to hold codes of all the tape symbols to the right
The register machine halts iff the Turing machine halts and in that case C holds the code of the final configuration.
(Copy image from p73)
Register machines can be implemented by Turing machines
- To code lists on a Turing machine tape:
- Represent a number x by x 1's. Eg; 3=111
- Mark the beginning and end of a list with 0
separates numbers on the list
01111110 = (3,2,1)
The tape will look like:
- 0111 111110... = (3,4,1)
A partial function is Turing computable iff it is register machine computable.
Church-Turing Thesis
"Every algorithm (in the intuitive sense) can be realized as a Turing machine/ register machine"
Our intuitive idea of an algorithm has properties such as:
- Finite description of the procedure in terms of "elementary operations"
- Deterministic (ie next step is uniquely determined)
- Procedure may not terminate on some input data, but can recognize when it does and what the result is
The Church-Turing thesis isn't a statement that can be proved formally, as the notion of an algorithm is informal. However, there is empirical evidence that supports the thesis: many alternative formalizations of the intuitive notion of algorithm have turned out to determine the same collection of computable functions.
Primitive Recursive Functions
A function is defined to be primitive recursive if and only if it is one of the 5 basic functions or can be obtained from the basic functions by applying the operators a finite number of times.
The basic functions:
| Projection | For every n≥1 and each i with 1≤i≤n, the n-ary projection function Pin, which returns its i-th argument, is primitive recursive. |
|
| Constant | The 0-ary constant function 0 is primitive recursive. |  |
| Successor | The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive. |  |
Note: the arity of a function is the number of arguments or operands that the function takes.
Composition of Partial Functions
Composition: Given f, a k-ary primitive recursive function, and k m-ary primitive recursive functions g1,...,gk, the composition of f with g1,...,gk, i.e. the m-ary function h(x1,...,xm) = f(g1(x1,...,xm),...,gk(x1,...,xm)), is primitive recursive.
Or as the notes say:
f º (g1,...,gn) is the unique m-ary partial function h satisfying
h(x1,...,xm) = f(g1(x1,...,xm),...,gn(x1,...,xm))
Primitive recusrion
Primitive recursion: Given f, a k-ary primitive recursive function, and g, a (k+2)-ary primitive recursive function, the (k+1)-ary function defined as the primitive recursion of f and g, i.e. the function h where h(0,x1,...,xk) = f(x1,...,xk) and h(S(n),x1,...,xk) = g(h(n,x1,...,xk),n,x1,...,xk), is primitive recursive.
pn(f,g) is the unique (n+1)-ary partial function that:
● f(x1,...,xn)=y0
● g(x1,...,xn,i,yi)=yi+1 for i=0,...,x-1
● yx=y
If f and g1,...,gn are all computable, then so is f º (g1,...,gn)
If f and g are computable, then so is pn(f,g)
The proofs involve register machine programs F and Gi computing f(y1,...,yn) and gi(xi,...,xm) in R0 .
Examples of primitive recursion
Addition
Intuitively, addition can be recursively defined with the rules:
add(0,x)=x,
add(n+1,x)=add(n,x)+1.
In order to fit this into a strict primitive recursive definition, define:
add(0,x)=P11(x) ,
add(S(n),x)=S(P13(add(n,x),n,x)).
Here P13 is the projection function that takes 3 arguments and returns the first one.
P11 is simply the identity function; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of f. The composition of S and P13, which is primitive recursive, plays the role of g.
Subtraction
Because primitive recursive functions use natural numbers rather than integers, and the natural numbers are not closed under subtraction, a limited subtraction function is studied in this context. This limited subtraction function sub(a,b) returns b − a if this is nonnegative and returns 0 otherwise.
The predecessor function acts as the opposite of the successor function and is recursively defined by the rules:
pred(0)=0,
pred(n+1)=n.
These rules can be converted into a more formal definition by primitive recursion:
pred(0)=0,
pred(S(n))=P22(pred(n),n).
The limited subtraction function is definable from the predecessor function in a manner analogous to the way addition is defined from successor:
sub(0,x)=P11(x),
sub(S(n),x)=pred(P13(sub(n,x),n,x)).
Here sub(a,b) corresponds to b-a; for the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion. This could easily be rectified using composition with suitable projections.
Other primitive recursive functions include exponentiation and primality testing. Given primitive recursive functions e, f, g, and h, a function which returns the value of g when e≤f and the value of h otherwise is primitive recursive.
Every primitive recursive function is both computable and total
Note:
To prove every member of PRIM (the set of primitive recursive functions) has property P, it suffices to show that:
● The 3 basic functions (projection,zero,successor) satisfy P
● The composition satisfies P
● If f & g satisfies P then so does pn(f,g)
To prove "Every primitive recursive function is both computable and total" we already know they are computable, and the first two satisfactions are evident.
If f & g are total then for all (x1,...,xn) the definition of pn(f,g) gives pn(f,g)(x1,...,xn,0)ò
Partial recursive functions
A partial recursive function is a partial function that can be built up from the basic functions by repeated use of the operations of composition, primitive recursion and minimization.
The set of PR (partial recursive functions) that are total are called total recursive functions.
A function f from words to words (over a finite alphabet) is called computable if there exists an method - any method at all - to compute it. It is recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts every input, and when given input string x, leaves the string f(x) on its tape upon acceptance.
A partial function is called partial recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts input x exactly when f(x) is defined, in which case it leaves the string f(x) on its tape upon acceptance.
By Church's thesis, a function is recursive if and only if it is computable.
Minimization: the μ operator
"The least value of y -- given y is less than z -- such that R(x, y) is true."
μ (f)(x1,...,xn) = { the least x such that
f(x1,...,xn,x)=0 and
f(x1,...,xn,i)>0 for i<x
μ (f)(x1,...,xn)é if no x exists satisfying these conditions.
If f is computable, then so is μ (f)
Example of minimization:
The everywhere undefined function is partial recursive. for if f(x,y)=1, then μ(f(x)é for all x;
and f=suc º zero2; so μ(f) = μ(f=suc º zero 2) is partial recursive.
All primitive recursive functions (PRIM) are partial recursive (PR) and total
but there are total recursive functions which are not primitive recursive
Ackermann's Function
Ack is recursive but not primitive recursive
ack є Fun(NxN,N) satisfying
ack(0,y) = y+1
ack(x+1,0) = ack(x,1)
ack(x+1,y+1)=ack(x,ack(x+1,y)
A partial function is (register machine) computable if & only if it is partial recursive.
The proof that a function is partial recursive if it is computable starts on p114.
Recursive and recursively enumerable sets
A set S is effectively enumerable if there is some algorithm A which lists the elements of S:
S = { A(0), A(1), A(2), ... }
The set PR is effectively enumerated by the algorithm A which, given input x,
decodes x as a pair x = <n,e>, then
decodes e as a register machine program Proge,
and returns the n-ary computable (hence partial recursive) function Фen(x1,...,xn) = y <def> computation of Proge started with R1,...,Rn set to x1,...,xn halts with R0=y.
A subset S ⊆ N of numbers is recursively enumerable iff either it is empty or there is a (total) recursive function f є Fun(N,N) so that S = { f(n) | n є N }
S ⊆ N is decidable iff the characteristic function of S
Xs(X)={ 1 if x є S, 0 if x ! є S
is computable. Such subsets are also called recursive.
Every recursive set is recursively enumerable
Since Xs is recursive so is f(x)=ifzero(xs(x),x0,x) and S={f(x) | x є N }, so S is r.e.
The set of total functions isn't recursively enumerable,.
You can have an r.e. set that isn't recursive:
The halting problem is undecidable, ie not recursive. But H is r.e. because the domain of the partial recursive function f(x)=u(x,0) -u=universal register machine.
The following are equivalent
For a subset S ⊆ N:
● S is recursively enumerable
● S = Im(f), the image of a unary partial recursive function
● S = Dom(f), the domain of a unary partial recursive function
● S is semi-decidable, meaning that the partial function
ins(x)={1 if x є S
undefined if x ! є S
is partial recursive.
Co-recursive
A subset S ⊆ N is called co-recursive iff N \ S (def { x є N | x є S } ) is r.e.
S is recursive iff it is both r.e. and co-re.
Note
S is countably infinite if there is some bijection (on-one and onto function) between N and S.
S is countable if it is either finite or countably infinite.
S is uncountable if it is not countable.
Eg; By Cantor's diagonal slash argument Fun(N,N) is uncountable.
Computer Graphics and Image Processing
Aims
To introduce the necessary background, the basic algorithms, and the applications of computer graphics and image processing. A large proportion of the course considers the design and optimisation of algorithms, so can be considered a practical application of the lessons learnt in the Algorithms course.
Lectures
· Background. What is an image? What are computer graphics, image processing, and computer vision? How do they relate to one another? Image capture. Image display. Human vision. Resolution and quantisation. Colour and colour spaces. Storage of images in memory, and double buffering. Display devices: the inner workings of CRTs, LCDs, and printers. [3 lectures]
· 2D Computer graphics. Drawing a straight line. Drawing circles and ellipses. Cubic curves: specification and drawing. Clipping lines. Filling polygons. Clipping polygons. 2D transformations, vectors and matrices, homogeneous co-ordinates. Uses of 2D graphics: HCI, typesetting, graphic design. [5 lectures]
· 3D Computer graphics. Projection: orthographic and perspective. 3D transforms and matrices. 3D clipping. 3D curves. 3D scan conversion. z-buffer. A-buffer. Ray tracing. Lighting: theory, flat shading, Gouraud, Phong. Texture mapping. [5 lectures]
· Image processing. Operations on images: filtering, point processing, compositing. Halftoning and dithering, error diffusion. Encoding and compression: difference encoding, predictive, run length, transform encoding (including JPEG). [3 lectures]
Objectives
At the end of the course students should be able to
· explain the basic function of the human eye and how this impinges on resolution, quantisation, and colour representation for digital images; describe a number of colour spaces and their relative merits; explain the workings of cathode ray tubes, liquid crystal displays, and laser printers
· describe and explain the following algorithms: Bresenham's line drawing, mid-point line drawing, mid-point circle drawing, Bezier cubic drawing, Douglas and Pucker's line chain simplification, Cohen-Sutherland line clipping, scanline polygon fill, Sutherland-Hodgman polygon clipping, depth sort, binary space partition tree, z-buffer, A-buffer, ray tracing, error diffusion
· use matrices and homogeneous coordinates to represent and perform 2D and 3D transformations; understand and use 3D to 2D projection, the viewing volume, and 3D clipping
· understand Bezier curves and patches; understand sampling and super-sampling issues; understand lighting techniques and how they are applied to both polygon scan conversion and ray tracing; understand texture mapping
· explain how to use filters, point processing, and arithmetic operations in image processing and describe a number of examples of the use of each; explain how halftoning, ordered dither, and error diffusion work; understand and be able to explain image compression and the workings of a number of compression techniques
Recommended reading
* Foley, J.D., van Dam, A., Feiner, S.K. & Hughes, J.F. (1990). Computer graphics: principles and practice. Addison-Wesley (2nd ed.).
Gonzalez, R.C. & Woods, R.E. (1992). Digital image processing. Addison-Wesley. [Gonzalez, R.C. & Wintz, P. (1977). Digital image processing is the earlier edition and is almost as useful.]
* Slater, M., Steed, A. & Chrysanthou, Y. (2002). Computer graphics and virtual environments: from realism to real-time. Addison-Wesley.
What is an image?
A real image is a two dimensional function. The value at any point is an intensity or color.
The eye
The retina is an array of light detection cells.
The fovea is the high resolution area of the retina.
The optic nerve takes signals from the retina to the visual cortex in the brain.
Cones come in three types, sensitive to short, medium and long wavelengths.
They are concentrated at the center of the retina, many in the fovea.
The distribution of rods in the fovea is about 7% short, 37% medium and 56% long, so we cannot see fine detail in blue. The luminance in the fovea is the sum of the response functions of the rods, the luminance outside the fovea is the response function of the rods.
Outside the fovea there are mainly rods, which are low resolution and monochromatic which are used for peripheral vision and in the dark.
The eye can do edge detection very well, and can discriminate intensity well (except in extremes of dark or light) but aren't so good at discriminating colours.
The pre-processing can cause illusions, e.g. Mach bands and Ghost squares.
Illuminants
The light source illuminating an object has a great effect on what the object looks like, eg; sunlight is quite uniform but light bulbs are very red.
Illuminant x reflection = reflected light
Munsells Colour Classification
Three axes:
● hue > what is the principal colour?
● value > how light or dark is it?
● chroma > how vivid or dull is it?
Based on testing people, so quite irregular, but easy to use by humans.
HSV is based on Munsell, "value"="hue" and "saturation"="chroma"
XYZ Colour Space
Y is the measure of brightness/luminance.
The chroma (colour) is specified by x,y,z - which are derived from X,Y,Z :
Based on measurements of the eye. Not perceptually uniform, ie you won't notice a big change in green but will notice a little change in red.
Luv, Lab Colour Space
Based on XYZ, but designed to be more perceptually uniform.
RGB Space
Used by televisions, CRT & LCD Screens etc.
Maps to a triangle in XYZ space: not all of XYZ space can be displayed.
Luminance Y = .3R + .6R + .1G
CMYK Space
Printers make colours by mixing inks, at its simplest is the inverse of RGB
● cyan absorbs red, reflects blue and green
● magneta absorbs green, reflects red and blue
● yellow absorbs blue, reflects green and red
● key (black) gives a good black
Sampling Resolution and Quantization
A digital image is a sampled and quantized (for example seeking to reduce the number of colors required to represent an image). It is stored as a rectangular array of intensity or color values.
Printers have a low bit depth (low quantization/reduced number of intensity levels) but high resolution as the eye can pick up detail on something stationary.
Grey scale
Commonly 1 byte is used, so an image of size WxH can be stored in a block of WxH bytes.
One way to store pixel [x][y] is at memory location x+ Width.y
Colour images
Commonly 24 bits: One bit red, one green, one blue
Size will be W x H x 3. Normally stored in 3 WxH planes (one for each colour).
The frame buffer
|
|
|
Most computers have a special piece of memory reserved for storage of the current image being displayed.
The frame buffer is normally built from DRAM.
When the image is being updated we nay see bits of the old image being displayed halfway through the update. Double buffering solves this: draw into one frame, display from the other. Once drawing is complete, we switch buffers.
Cathode Ray Tubes (CRT)
Used in monitors, TVs.
● The heater emits electrons, which are accelerated by the potential difference between cathode and anode. Electrons hitting the front screen excite the phosphor, making it emit visible light
● Changing voltage changes the intensity of the beam and hence spot
● Deflection coils magnetically deflect the electron beam to any position on the screen
● Beam scans screen left to right, cuts power then whizzes back to start and up a line
● Repeated fast enough, (>20Hz) gives illusion of continuous picture.
Colour is achieved through three separate electron guns (one for each colour) and three separate colour phosphors. To ensure the guns hit the right colored phosphor shadow masks are used.
Cutaway rendering of a color CRT
1. Electron guns
2. Electron beams
3. Focusing coils
4. Deflection coils
5. Anode connection
6. Mask for separating beams for red, green, and blue part of displayed image
7. Phosphor layer with red, green, and blue zones
8. Close-up of the phosphor-coated inner side of the screen
Liquid Crystal Displays
● Before applying an electric field the molecules twist to try to line up. Half of the light is absorbed by the first polarizing filter, but otherwise the entire assembly is transparent.
● Applying a voltage ruins the twisting phenomenon so the pixel becomes opaque (no light can get through the two polarizers at 90).
● Colour is achieved with colour filters
Lower power consumption,thin.
Plasma Displays
● A high voltage across the electrodes ionizes a noble gas (xenon, neon)
● The noble gas emits ultraviolet light
● The ultraviolet light excites the phosphor, which emits visible light
Large and thin but lots of power and expensive.
Digital Micro mirror Devices
● Manufactured like a silicon chip
● Used increasingly in projectors
● Colour achieved from three DMD chips, or one chip and a rotating colour filter
Printers
● Inkjet sprays ink onto paper. May use electrostatic field. 300-1200 dpi. Home printer.
● Laser printer uses a laser to lay down pattern of charge on a drum, which picks up charged toner and is then pressed onto the paper and fixed. 300-1200 dpi. Office printer.
● Commercial photo typesetter. Whole page put on plates with a roller, repeatedly inked and pressed against paper. High quality 2400 dpi, thousands of copies. CMYK plus spot colour to produce one colour (eg corporate logo) without half toning.
● Dye sublimation gives true greyscale, but is very expensive
Greyscale printing
● Half toning: Split into a grid. The greater the intensity, the larger the spot.
Can create obvious line effects though, and photocopies badly
● Dithering is similar but instead of a single blob patterns which don't make lines are used
Drawing a Straight Line
A straight line can be defined by y=mx+c
You get the best line by choosing to draw the closest pixel to the line in each column, not every pixel through which the line passes.
Bresenham's line drawing algorithm
(For the first octant)
//Find the gradient: how much the line increases in y every x++
d= (y1 -y0) / (x1 - x0)
//Initialise
x = x0
yi = y0
y = y0
//Draw the first point
DRAW(x,y)
//While we're not at the end of the line
WHILE x <x1 DO
//Move along the line one
x = x + 1
//Find actual y position at current x
yi = yi + d
//Round y to get plottable value
y = ROUND(yi)
DRAW(x,y)
END WHILE
As floating point calculations are slow, instead of rounding can use an if:
IF (yf > 1/2) THEN
y = y + 1
yf = y -1
END IF
(yf instead of yi, initialized to 0)
Can now multiple all operations involving yf by 2(x1-x0), removing floating point arithmetic if end points have integer co-ordinates.
Midpoint line drawing algorithmic
A decision variable decides whether next pixel is on to the right, or one to the right and up one.
a = (y1 - y0)
b = -(x1 - x0)
c = x1y0 - x0y1
x = ROUND(x0)
y = ROUND(y0 - (x - x0)(a/b))
d = a * (x=1) + b * (y+1/2) + c
DRAW(x,y)
WHILE x < (x1 - 1/2) DO
x = x + 1
IF d < 0 THEN
d = d + a
ELSE
d = d + a + b
y = y + 1
END IF
DRAW(x,y)
END WHILE
This can easily be extended to draw circles, wher ethe decision variable d can be
d = x2 + y2 - r2
Bezier Cubes
Four points P0, P1, P2 and P3 in the plane or in three-dimensional space define a cubic Bézier curve. The curve starts at P0 going toward P1 and arrives at P3 coming from the direction of P2. Usually, it will not pass through P1 or P2; these points are only there to provide directional information. The distance between P0 and P1 determines "how long" the curve moves into direction P2 before turning towards P3.
The parametric form of the curve is:
The weighting functions (P0-P3) sum to one.
Joins at end points can be:
● C1 continuity both position and tangent vector
● G1 continuous in position, tangent vector in same direction
● C0 continuous in position only
We could just draw a bezier curve as a set of short line segments between Bezier(t) and Bezier(t+step).
A better way is adaptive sub-devision:
● Check if straight line between P0 and P3 is an adequate approximation to the Bezier
● If so: draw the straight line
● If not: divide the Bezier into two halves, each a Bezier, and repeat for the two new Beziers
Checking for flatness:
S = AB.AC / |AB|2
Overhausers Cubic
Given points A,B,C,D the Bezier control points are:
P0 = B P1 = B + (C-A)/6 P3 = C P2=C-(D-B)/6
Douglas & Pucker's algorithm
This reduces the number of line segments in a chain without compromising quality
● find point C, at greatest distance from segment AB
● if distance from C to AB is more than some specified tolerance then subdivide into AC and CB, repeat for each of the subdivisions
● otherwise approximate entire chain from A to B by the single line segment AB
Clipping
When clipping around a rectangle, you could just check every line against each of the four edges.
 |
The Cohen-Sutherland clipper uses a 4 bit code for each section around the rectangle. If you and each end of the line with the section code it is in, and the result is 0, then nothing has to be clipped-otherwise you know where to clip.
Make a four bit code, one bit for each inequality
A = x < Xleft B = x > Xright C = y < Ybottom D = y > Yright
Evaluate this for both end points Q1 = A1B1C1D1 Q2 = A2B2C2D2
If both Q1 and Q2 are zero then both ends are in the rectangle, accept
If Q1 AND Q2 != 0 then both ends must have the same bit code as 1 - both ends outside and in the same section - reject
Otherwise, intersect line with one of the edges loop, clip
Scanline Polygon Fill Algorithm
Create and edge list
Start with the left most point of the polygon, move right filling in all pixels whose centers lie inside the polygon, move up a line once scanned entire line.
To find the intersection points use an incremental line drawing algorithm.
Sutherland-Hodgman Polygon Clipping I
Clip polygon against an infinite line, then pass the result on and clip with next edge.
Homogeneous 2d co-ordinates
Homogeneous coordinates solve the problem of representing translation as a matrix operation.
For every x,y in normal space there is an infinite number of x,y,w points where
(x,y,w) = (x/w,y/w)
w=0 represents a point at infinity, the inverse transform is (x,y) = (x,y,1)
In 3d:
(x,y,z,w) = (x/w,y/w,z/w)
Matrix transformations
Note that concatenation is not commutative.
Translation
To move points (x,y,w) to (x+x0,y+y0,w'):
multiply (x,y,w) by the matrix
1 0 x0
0 1 y0
0 0 1
In 3d:
Scale
About origin, factor m
To scale about a point, translate to center, scale, then translate back again.
In 3d:
Rotate
About origin, angle Ө
In 3d, about x-axis:
In 3d, about y-axis
In 3d, about z-axis
Do nothing
Identity
In 3d:
Shear
Parallel to x axis, factor a
Bounding boxes
Speed up some operations, can clip around them at increasing levels of detail.
Bit block transfer (BitBit)
Often quicker to predraw something then copy the image to the correct position on the screen when required. Copy an image is essentially a memory operation.
Typefaces
● Pre-rendered bit maps. Use BitBit to put into frame buffer. Don't scale well.
● Outline definitions. Scale well, need to fill to put into frame buffer.
Viewing Co-ordinates
The camera in world co-ordinates is specified by:
● eye (camera) position at 
● look point (center of screen) at 
● up along vector 
- perpendicular to el
You can trim along a pyramid just as you would with a 2D rectangle.
You can also project to 2D (giving you lots or rectangles as you progress through z) then clip.
To transform from world to viewing co-ordinates:
e goes to (0,0,0) and l goes to (0,0,d)
● T=translate eye point 
to origin (0,0,0)
● S=scale so that the eye point to look point distance, el, is distance from origin to screen centre
● Align el with z-axis:
transform e and l into new co-ordinate system
e'' = S x T x e =0 l'' = S x T x l
R1= Rotate e''l'' into yz plane, rotating about y-axis
● R2=Rotate viewing vector again, this time about the x-axis so it aligns with the z-axis
● R3=Rotate the up vector about the z-axis so that it lies in the positive y half of the yz plane
Examples
The joints of a robot arm can only move in the xy-plane, the shoulder is attached to a z-axis vertical slider.
The initial position of the arm is
● shoulder joint: position (0,0,0), rotation 0°
● elbow joint: position (2,0,0), rotation 0°
● hand: position (3,0,0)
There is a soft drink can located at position (1,1,1). Make the arm touch it.
To rotate elbow about Z-axis by 90:
| Cos90 | -sin90 | 0 | 0 |
| Sin90 | Cos90 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
To rotate elbow about Y-axis by 90
| Cos90 | 0 | Sin90 | 0 |
| 0 | 1 | 0 | 0 |
| -sin90 | 0 | Cos90 | 0 |
| 0 | 0 | 0 | 1 |
Sin90=1, cos90=0
To move shoulder -2 along x-axis
| 1 | 0 | 0 | -2 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
Give a matrix, in homogeneous co-ordinates which will project 3D space onto the plane z=d with the origin as the center of projection.
Looking for
=> 
Got 
which comes from 
Bezier Patches
Bézier patches are defined by a 4×4 grid of 16 evenly spaced control points that form a surface made up of nine rectangular sub-patches.
where 
Online demo at http://www.nbb.cornell.edu/neurobio/land/OldStudentProjects/cs490-96to97/anson/BezierPatchApplet/index.html
Simliarly to Bezier curves, Bezier patches can be drawn by approximating them with planar polygons (subdividing according to tolerance level).
Continuity between Bezier patches
● C0 - continuous in position (the four edge control points must match)
● C1 - continuous in position and tangent vector (four edge control points must match, the two control points on either side of each of the four edge control points must be co-linear with both the edge point and each another and be equidistant from the edge point)
3D line drawing
● project end points onto the 2D screen
● use a line drawing algorithm to draw the lines- giving a wireframe version
● remove hidden lines
Depth sort polygon drawing
● transform all polygon vertices into viewing co-ordinates and project these into 2D, keeping z information
● calculate a depth ordering for polygons, based on the most distant z co-ordinate in each polygon
● resolve any ambiguities caused by polygons overlapping in z- split polygons if necessary and throw away original
● draw the polygons in depth order from front to back with a 2D polygon scan conversion.
don't draw back facing parts of solid polyhedrons-they will be hidden by the front
Slow with large numbers
Binary Space-Partitioning trees
Binary space partitioning data is calculated for a level before play, recursively splitting space by hyperplanes and storing in a tree.
BSP algorithm:
1. Start at the root node.
2. Draw the child nodes of this node recursively. The child node closest to the camera is drawn first. This can be found from looking at which side of the node's dividing line the camera is on.
3. When a sub sector is reached, draw it.
The algorithm stops when all pixels have been drawn, preventing double drawing.
Walls are drawn completely vertically aligned along the Y axis, meaning you cant look up and down but rendering is quick.
Z-buffering
If two objects in the scene share the same pixel on the projected screen, the closer one is drawn.
Test the z - depth of each surface to determine the closest (visible) surface. Declare an array z buffer(x, y) with one entry for each pixel position. Initialize the array to the maximum depth.
for each polygon P
for each pixel (x, y) in P
compute z_depth at x, y
if z_depth < z_buffer (x, y) then
set_pixel (x, y, colour)
z_buffer (x, y) <= z_depth
An A-buffer averages the different visible polygon colours to get an acceptable result, whereas in simple z buffering only the exact center of pixels is considered- leading to jagged edges and some small polygons not being drawn at all.
Fast and easy to implement in hardware.
Anti-aliasing
● Using the centre of piels for colours leads to small polygons being missed, agged edges etc.
● Getting rid of these artefact's is called anti-aliasing
Methods include:
● Averaging the colour
● Super sampling (sample on a finer grid)
● A-buffering
Reflective surfaces
Note that most specular surfaces aren't perfect and so the incident angle isn't the same as the reflection.
Common assumptions when shading a polygon include:
● There is only diffuse reflection
● No interaction between polygons
● Light source is infinitely far away, so vector is same across whole polygon
Diffuse shading calculation
● L is a normalized vector pointing in the direction of the light source
● N is the normal to the polygon
● Ii is the intensity of the light source
● Kd is the proportion of light which is diffusely reflected by the surface
● I is the intensity of the light reflected by the surface
Gourad shading
Calculate the diffuse illumination at each vertex rather than for each polygon
Phong shading
Approximation to specular reflection
Ray tracing
● 
Shoot a ray from the eye through the center of every pixel and see what it hits
● Shoots rays from that point to all of the light sources, and calculate the diffuse and specular reflections off the object at this point
● Check whether another object is between that point and the light and is hence casting shadow
Often use random or poisson discs patterns for super sampling for anti-aliasing
Sampling texture space: interpolation methods
● nearest neighbour: fast, artefact's
● biinear: fairly fast, blurry
● bicubic: good but slow
Some more things around p 306
GIF
GIF is a standard 8 bit bitmap format, with LZW lossless compression.
JPEG
Converted from RGB to YCbCr color space.
The channels are split into 8x8 blocks of pixels
The Cb and Cr components are seen in less detail by the human eye, so these are downsampled.
Each component is tiled into sections of 8x8 pixels using a discrete cosine transform.
High frequency brigthness variations are hard to tell apart by the human eye, so high frequency colour areas are averaged out.
The lossless data compression algorithm "entropy encoding" is applied.
Concepts in Programming Languages
Aims
The general aim of this course is to provide an overview of the basic concepts that appear in modern programming languages, the principles that underlie the design of programming languages, and their interaction.
Lectures
· Introduction, motivation, and overview. What is a programming language? Application domains in language design. Program execution models. Theoretical foundations. Language standardisation. History.
· The first procedural language: FORTRAN (1954-58). Execution model. Data types. Control structures. Storage. Subroutines and functions. Parameter passing.
· The first declarative language: LISP (1958-62). Expressions, statements, and declarations. S-expressions and lists. Recursion. Static and dynamic scope. Abstract machine. Garbage collection. Programs as data. Parameter passing. Strict and lazy evaluation.
· Block-structured procedural languages: Algol (1958-68), BCPL (1967), Pascal (1970), C (1971-78). Block structure. Parameters and parameter passing. Stack and heap storage. Data types. Arrays and pointers.
· Object-oriented languages -- Concepts and origins: Simula (1964-67), Smalltalk (1971-80). Dynamic lookup. Abstraction. Subtyping. Inheritance. Object models.
· Types, data abstraction, and modularity: C++ (1983-98), SML (1984-97). Types in programming. Type systems. Type checking and type inference. Polymorphism. Overloading. Type equivalence. Information hiding. Modularity. SML module system: signatures, structures, and functors. [2 lectures]
· State of the art.
Objectives
At the end of the course students should
· be familiar with several language paradigms and how they relate to different application domains
· understand the design space of programming languages, including concepts and constructs from past languages as well as those that may be used in the future
· develop a critical understanding of the programming languages that we use by being able to identify and compare the same concept as it appears in different languages
Recommended reading
Books:
* Mitchell, J.C. (2003). Concepts in programming languages. Cambridge University Press.
* Pratt, T.W. & Zelkowitz, M.V. (2001). Programming languages: design and implementation. Prentice Hall.
Papers:
Kay, A.C. (1993). The early history of Smalltalk. ACM SIGPLAN Notices, Vol. 28, No. 3.
Kerninghan, B. (1981). Why Pascal is not my favorite programming language. AT&T Bell Laboratories. Computing Science Technical Report No. 100.
Koenig, A. (1994). An anecdote about ML type inference. USENIX Symposium on Very High Level Languages.
McCarthy, J. (1960). Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3(4):184-195.
Stroustrup, B. (1991). What is Object-Oriented Programming? (1991 revised version). Proceedings 1
European Software Festival.
Concepts
Calling/Passing by Value/Name
Pass/Call-by-value. The most common method is to evaluate the expressions in the actual-parameter list, and pass the resulting values.
In pass-by-value, the actual parameter is evaluated. The value of the actual parameter is then stored in a new location allocated for the function parameter.
Under call-by-value, a formal parameter corresponds to the value of an actual parameter. That is, the formal x of a procedure P takes on the value of the actual parameter.
The idea is to evaluate a call P(E) as follows:
x := E;
execute the body of procedure P;
if P is a function, return a result.
Pass/Call-by-name.? A less common method is to transmit the expression in the actual parameter list unevaluated, and let the call function evaluate them as needed using
eval.
1. In pass-by-reference, the actual parameter must have an
L-value. The L-value of the actual parameter is then
bound to the formal parameter.
2. Under call-by-reference, a formal parameter becomes a
synonym for the location of an actual parameter. An actual
reference parameter must have a location.
important to the programmer in several ways:
Side effects. Assignments inside the function body may have different effects under pass-by-value and pass-by-reference.
Aliasing. Aliasing occurs when two names refer to the same object or location.
Aliasing may occur when two parameters are passed by reference or one parameter passed by reference has the same location as the global variable of the procedure.
Call-by-value/result is also known as copy-in/copy-out
because the actuals are initially copied into the formals and the formals are eventually copied back out to the actuals. Actuals that do not have locations are passed by value.
Actuals with locations are treated as follows:
1. Copy-in phase. Both the values and the locations of the actual parameters are computed. The values are assigned to the corresponding formals, as in call-by-value,
and the locations are saved for the copy-out phase.
2. Copy-out phase. After the procedure body is executed, the nal values of the formals are copied back out to the locations computed in the copy-in phase.
A parameter in Pascal is normally passed by value. It is passed by reference, however, if the keyword var appears before the declaration of the formal parameter.
procedure proc(in: Integer; var out: Real);
The only parameter-passing method in C is call-by-value;
however, the effect of call-by-reference can be achieved using pointers. In C++ true call-by-reference is available using reference parameters.
In Java Objects are not passed by reference. A correct statement would be Object references are passed by value.
Ada supports three kinds of parameters:
1. in parameters, corresponding to value parameters;
2. out parameters, corresponding to just the copy-out phase of call-by-value/result; and
3. in out parameters, corresponding to either reference parameters or value/result parameters, at the discretion of the implementation./
The Algol 60 report describes call-by-name as follows:
1. Actual parameters are textually substituted for the formals.
Possible conflicts between names in the actuals and local names in the procedure body are avoided by renaming the locals in the body.
2. The resulting procedure body is substituted for the call. Possible conflicts between nonlocals in the procedure body and locals at the point of call are avoided by renaming the locals at the point of call.
ALGOL 60 allowed for two evaluation strategies for parameter passing: the common call-by-value, and call-by-name. Call-by-name had certain limitations in contrast to call-by-reference, making it an undesirable feature in imperative language design. For example, it is impossible in ALGOL 60 to develop a procedure that will swap the values of two parameters if the actual parameters that are passed in are an integer variable and an array that is indexed by that same integer variable
A formal parameter is a declaration that appears in the declaration of the subprogram. (The computation in the body of the subprogram is written in terms of forma parameters.)
An actual parameter is a value that the calling program sends to the subprogram.
Types
A type is a collection of computational entities that share
some common property.
There are three main uses of types in programming
languages:
1. naming and organizing concepts,
2. making sure that bit sequences in computer memory
are interpreted consistently,
3. providing information to the compiler about data
manipulated by the program.
A type system for a language is a set of rules for associating a
type with phrases in the language.
Terms strong and weak refer to the effectiveness with which
a type system prevents errors. A type system is strong if it
accepts only safe phrases. In other words, phrases that are
accepted by a strong type system are guaranteed to evaluate
without type error. A type system is weak if it is not strong.
A programming language is type safe if no program is allowed
to violate its type distinctions.
A type error occurs when a computational entity is used in a
manner that is inconsistent with the concept it represents.
Type checking is used to prevent some or all type errors,
ensuring that the operations in a program are applied properly.
Run-time type checking: The compiler generates code so
that, when an operation is performed, the code checks to
make sure that the operands have the correct types.
Examples: LISP, Smalltalk.
Compile-time type checking: The compiler checks the
program text for potential type errors.
Example: SML.
Name equality. Pure name equality. A type name is equal
to itself, but no constructed type is equal to any other
constructed type.
Transitive name equality. A type name is equal to itself
and can be declared equal to other type names.
Type-expression equality. A type name is equal only to
itself. Two type expressions are equal if they are
formed by applying the same constructor to equal
expressions. In other words, the expressions have to
be identical.
Type inference is the process of determining the types
of phrases based on the constructs that appear in them.
Object Orientated Programming
Four main language concepts for object-oriented languages:
1. Dynamic lookup.
2. Abstraction.
3. Subtyping.
4. Inheritance.
ML isn't an OOP so attempts such as:
val BoolStack = ref {pop=fn,push=fn}
: {pop:unit -> bool, puattempts ssh:bool -> unit} ref
fail.
Dynamic lookup means that when a message is sent to an object, the method to be executed is selected dynamically, at run time, according to the implementation of the object that receives the message. In other words, the object .chooses. how to respond to a message. The important property of dynamic lookup is that different objects may implement the same operation differently, and so may respond to the same message in different ways.
Abstraction means that implementation details are hidden inside a program unit with a specic interface. For objects, the interface usually consists of a set of methods that
manipulate hidden data. Abstraction based on objects is similar in many ways to abstraction based on abstract data types: Objects and abstract data types both combine functions and data, and abstraction in both cases involves distinguishing between a public interface and private implementation. Other features of object-oriented languages, however, make abstraction in object-oriented languages more exible than abstraction with abstract data types.
Subtyping is a relation on types that allows values of one type to be used in place of values of another. Specically, if an object a has all the functionality of another object b,
then we may use a in any context expecting b. The basic principle associated with subtyping is substitutivity: If A is a subtype of B, then any expression of type A may be used without type error in any context that requires an expression of type B.
The primary advantage of subtyping is that it permits uniform operations over various types of data.
Inheritance is the ability to reuse the denition of one kind of object to dene another kind of object.
The importance of inheritance is that it saves the effort of duplicating (or reading duplicated) code and that, when one class is implemented by inheriting form another, changes to one affect the other. This has a significant impact on code maintenance and modification.
Comparison of Languages
| Language | Typing | Value passing | OOP | Model of execution | Paradigms | Datatypes |
| Fortran | Incomplete. Strong-static. | Reference | 2003 onwards. | Compilation | imperative,procedural, object-oriented | Can't resize arrays. |
| Lisp | Untyped (though scheme is strong, dynamic) | Call by value+
name. |
No | Interpretation, Compilation | functional | |
| C | static, weak, unsafe | Arrays and functions by reference, rest by value. | No | Compilation | imperative, flow-driven | |
| C++ | static, strong, unsafe, nominative | Both | Yes | Compilation | imperative, object-oriented, generic,multi-platform | |
| C# | static, strong, both safe and unsafe | Both. Keyword ref | Yes | JIT compilation | imperative, object-oriented, generic, multi-platform | |
| Algol | strong | Value and name | No | |||
| Pascal | static, strong, safe | No. Object pascal. | Compilation | imperative | ||
| Small Talk | dynamic, strong, safe, duck | Yes | JIT compilation | object-oriented, functional, concurrent, event-driven, imperative, declarative | ||
| SML | strong, static | Pass by value. | No | Interpretation | multi-paradigm: functional, imperative | |
| Java | static, strong | Pass by value | Yes | Interpretation | imperative, object-oriented, multi-platform, generic |
Major advances in Languages
● FORTRAN: Flat register machine; memory arranged as linear array
● LISP: cons cells, read-eval-print loop
● Algol family: stack of activation records; heap storage
● BCPL, C: underlying machine + abstractions
● Simula: Object references
● FP, ML: functions are basic control structure
● Smalltalk: objects and methods, communicating by messages
● Java: Java virtual machine
Fortran
Example
C FORTRAN IV WAS ONE OF THE FIRST PROGRAMMING
C LANGUAGES TO SUPPORT SOURCE COMMENTS
WRITE (6,7)
7 FORMAT(13H HELLO, WORLD)
STOP
END
Execution model
● A FORTRAN program= main program +subprograms
Each is compiled separately, during loading different programs are linked into an executable form.
● All storage is allocated statically before program execution begins; no run-time memory management
● Register machine- memory is a linear array. No stacks, no recursion
● A value is returned in a FORTRAN function by assigning a value to the name of a function.
● Parameter passing is uniformly by reference.
Data types
● Can't resize arrays and character strings.
● Incomplete type checking.
● Global or local scope.
COMMON blocks are are named blocks of data used to share data between different subprograms.
EQUIVALANCE allows two or more variables to link to the same data location-aliasing.
In a block-structured language, each program or subprogram is organised as a set of nested blocks. The trend in programming is to reduce the size of subprograms, so the
use of unnamed blocks is less useful than it used to be.
Fortran 2003 is oop : type extension and inheritance, polymorphism, dynamic type allocation, and type-bound procedures.
Lisp
Expressions. A syntactic entity that may be evaluated to
determine its value.
Statement. A command that alters the state of the
machine in some explicit way.
Declaration. A syntactic entity that introduces a new
identier, often specifying one or more attributes.
Type
Most operations in LISP take list arguments and return list
values.
( cons '(a b c) '(d e f) )
Lisp is an untyped language.
Scheme has strong, dynamic typing.
Scope
In the program text; dynamic scope rules relate references with associations for names during program execution.
There are two main rules for nding the declaration of a global identier:
Static scope. A global identier refers to the identier with that name that is declared in the closest enclosing scope of the program text.
Dynamic scope. A global identier refers to the identier associated with the most recent environment.
Abstract
The idealized abstract machine for Pure LISP has four parts:
1. A LISP expression to be evaluated.
2. A continuation, which is a function representing the remaining of the program to evaluate when done with the current expression.
3. An association list, also know as the A-list.
The purpose of the A-list is to store the values of variables that may occur either in the current expression to be evaluated or in the remaining expressions in the program.
4. A heap, which is a set of cons cells (or dotted pairs) that might be pointed to by pointers in the A-list.
Recursion: In general . . . , the routine for a recursive function uses itself as a
subroutine.
Garbage Collection
At a given point in the execution of a program P, a memory location ` is garbage if no completed execution of P from this point can access location `. In other words, replacing the contents of ` or making this location inaccessible to P cannot affect any further
execution of the program.
Garbage collection is the process of detecting garbage during the execution of a program and making it available.
LISP data and LISP program have the same syntax and internal representation. This allows data structures to be executed as programs and programs to be modified as data.
Passing parameters
The actual parameters in a function call are always expressions, represented as lists structures.
LISP provides two main methods of parameter passing:
call/pass by value and call/pass by name.
Algol
Introduction
The main characteristics of the Algol family are:
the familiar semicolon-separated sequence of statements, block structure, functions and procedures, and static typing.
/
Typing
Automatic type conversions were not fully specified
(e.g., x := x/y was not properly defined when x and y were integers )
The type of a procedure parameter to a procedure does not include the types of parameters.
An array parameter to a procedure is given type array, without array bounds.
Algol 60 was designed around two parameter-passing mechanisms, call-by-name and call-by-value. Call-by-name interacts badly with side effects; call-by-value is expensive for arrays.
Pascal
Pascal is a block-structured language in which static scope rules are used to determine the meaning of nonlocal references to names.
Pascal is a quasi-strong, statically typed programming language.
BCPL
Data types
The most important feature is the store: a set of numbered storage cells arranged so that the numbers labelling adjacent cells differ by one.
All storage cells are of the same size and each of them holds a value (= bit-pattern). A value is the only kind of object that can be manipulated directly in BCPL, and every variable and expression in that language will always
evaluate to one of these.
The design of BCPL distinguishes between two classes of data types.
1. Conceptual types. The kind of abstract object the programmer had in mind.
2. Internal types. Basic types for modelling conceptual types.
There is no need for type declarations in the language. This helps to make programs concise and also simplies problems such as the handling of actual/formal parameter correspondence and separate compilation.
2. It gives the language nearly the same power as one with dynamically varying types (as in LISP), and yet retains the efciency of a language (like FORTRAN) with manifest types. In languages (such as Algol) where the elements of arrays must all have the same type, one needs some other linguistic device in order to handle dynamically varying data structures.
BCPL uses a form of static storage, called global vector, which allows separately compiled modules to reference and call each other and to share data. This facility is not
unlike the FORTRAN COMMON storage area.
In BCPL, variables may be divide into two classes:
1. Static variables. The extent of a static variable is the entire execution time of the program. The storage cell is allocated prior to execution and continues to exist until execution is complete.
2. Dynamic variables. A dynamic variable is one whose extent starts when its declaration is executed and continues until
A pointer in BCPL is the address of a word of store.
Parameters
The BCPL procedure call uses the call-by-value technique for parameter passing.
BCPL has been carefully designed so that it is possible to represent a procedure by a simple BCPL value, called the procedure value. The procedure value is placed in a
variable bearing the name of the procedure.
C
Introduction
B was a pared-down version of BCPL, designed to run on the small computer used by the Unix project. The main difference between B and C is that B was untyped whereas C has types and type-checking rules.
The C programming language is similar to Algol 60, Algol 68, and Pascal in some respects: command-oriented syntax, blocks, local declarations, and recursive functions.
However, C also shares some features with its untyped precursor BCPL, such as pointer arithmetic. C is also more restricted than most Algol-based languages in that functions cannot be declared inside nested blocks: All functions are declared outside the main program. This simplies storage management.
Simula
OOP was invented with SIMULA and improved with small talk.
Simula: Extremely influential as the first language with classes objects, dynamic lookup, subtyping, and inheritance.
Objects in SIMULA
Class: A procedure returning a pointer to its activation record.
Object: An activation record produced by call to a class, called an instance of the class.
Objects are deallocated by the garbage collector (which deallocates objects only when they are no longer reachable from the program that created them).
Objects: A SIMULA object is an activation record produced by call to a class.
Classes: A SIMULA class is a procedure that returns a pointer to its activation record. The body of a class may initialise the objects it creates.
Dynamic lookup: Operations on an object are selected from the activation record of that object.
Abstraction: Hiding was not provided in SIMULA 67 but was added later and used as the basis for C++.
Subtyping: Objects are typed according to the classes that create them. Subtyping is determined by class hierarchy.
Inheritance
Example
POINT CLASS COLOREDPOINT(C); COLOR C;
BEGIN
BOOLEAN PROCEDURE EQUALS(Q); REF(COLOREDPOINT) Q;
...;
END***COLOREDPOINT**
Small Talk
Methods are public.
Any code with a pointer to an object may send any message to that object. If the corresponding method is defined in the class of the object, or any superclass, the method will be invoked. This makes all methods of an object visible to any code that can access the object.
Instance variables are protected.
The instance variables of an object are accessible only to methods of the class of the object and to methods of its subclasses.
The run-time structures used for Smalltalk classes and objects support dynamic lookup in two ways.
1. Methods are selected through the receiver object.
2. Method lookup starts with the method dictionary of the class of the receiver and then proceeds upwards through the class hierarchy.
● Objects: A Smalltalk object is created by a class.
At run time, an object stores its instance variables and a pointer to the instantiating class.
● Classes: A Smalltalk class defines variables, class methods, and the instance methods that are shared by all objects of the class.
● Abstraction: Abstraction is provided through protected instance variables. All methods are public but instance variables may be accessed only by the methods of the class and methods of subclasses.
● Subtyping: Smalltalk does not have a compile-time type system. Subtyping arises implicitly through relations between the interfaces of objects. Subtyping depends on the set of messages that are understood by an object, not the representation of objects or whether inheritance is used.
● Inheritance: Smalltalk subclasses inherit all instance variables and methods of their superclasses. Methods defined in a superclass may be redefined in a subclass or deleted.
Java
The language itself derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities.
are not objects. Primitive types store their values in the stack rather than being references to values. This was a conscious decision by Java's designers for performance reasons. Because of this, Java is not considered to be a pure object-oriented programming language.
Java does not support pointer arithmetic as is supported in for example C++. This is because the garbage collector may relocate referenced objects, invalidating such pointers. Another reason that Java forbids this is that type safety and security can no longer be guaranteed if arbitrary manipulation of pointers is allowed.
C#
Simplicity
-perhaps a reaction against C++
-though even Java 1.0 had complex features: e.g. overloading resolution, multiple class loaders
-Safety and security
-strongly typed (mostly static)
-automatic memory management (=> no pointer errors)
-code access security by "stack inspection"
-Portability
-compiled to bytecode, executed by Java Virtual Machine
-Object-orientation
-simple model of implementation inheritance for classes
-multiple interface inheritance
Digital Communication I
Aims
The aims of this course are to develop an understanding of communications networks from a wide perspective, within a framework of principles rather than technologies or architectures. Technologies and architectures will, however, be used as examples and motivation.
Lectures
· Scope. Two example systems: Ethernet and the telephone system: basic operation; common issues; differing constraints; differing approaches.
· Partitioning the problem. Abstraction, service versus implementation; layering as a restricted form of abstraction; motivation for layering; the channel as an abstraction; layered channels.
· Fundamental transmission. Emphasis on the service provided by physical channel; limitations: noise, attenuation. Channel capacity (bandwidth). Modulation techniques for digital systems.
· Coding. Coding as a general concept: modulation as a form of coding, A/D,D/A, error correcting and detecting codes, other forms of coding, relation to layering.
· Multiplexing. Basic definitions, FDM, synchronous and asynchronous TDM. Circuit switching, packet switching, ATM. Shared media networks with particular emphasis on media access control. Packet scheduling. Non orthogonal multiplexing. Multiplexing and channel characteristics.
· Switching and routing. Introduction from LAN perspective (repeaters, bridges, routers). Fundamental view of switching extended to telephone network, connectionless versus connection oriented.
· Protocols and state. Imperfect view of state at far end of channel. ARQ as an example of an error control protocol; sliding window ARQ as an example of a flow control protocol; flow control in general: X.25 as an example.
· Naming, addressing and routing. Service access points, binding. Hierarchical versus flat address spaces. Routing classifications and algorithms.
· The Internet. Internet architecture, context of development, addressing and routing, transmission control protocol (TCP), higher layer protocols, evolution.
· Standards. Role of standards, dynamics of standards process, standards bodies.
Objectives
At the end of the course students should
· be able to analyse a communication system by separating out the different functions provided by the network
· understand that there are fundamental limits to physical transmission systems
· understand the general principles behind multiplexing, addressing, routing and stateful protocols as well as specific examples of each
· understand what FEC is and how CRCs work
· be able to compare communications systems in how they solve similar problems
· have an informed view of the internal workings of the Internet
Recommended reading
* Peterson, L.L. & Davie, B.S. (2003). Computer networks: a systems approach. Morgan Kaufmann (3rd ed.).
Comer, D. & Stevens, D. (1995). Internetworking with TCP-IP, vol. 1 and 2. Prentice Hall (3rd ed.).
Schwartz, M. (1987). Telecommunication networks: protocols, modeling and analysis. Addison-Wesley.
| OSI Model | |||
| Data unit | Layer | Function | |
| Host layers |
Data | Application | Network process to application |
| Presentation | Data representation and encryption | ||
| Session | Interhost communication | ||
| Segments | Transport | End-to-end connections and reliability (TCP) | |
| Media layers |
Packets | Network | Path determination and logical addressing (IP) |
| Frames | Data link | Physical addressing (MAC & LLC) | |
| Bits | Physical | Media, signal and binary transmission | |
Noise may be systematic or random
Attenuation: Signal looses energy as it travels along a channel.
C=B log_2(1+ S/N)
· C= information capacity
· B= bandwidth
· S/N= signal to noise ratio
Modulation: Transform to apporiate signal for transmission medium.
This technique of letting each shift of a wave represent some bit value is phase shift keying. But the real key is to shift each wave relative to the wave that came before it.
Forward error correction (FEC) is a system of error control for data transmission, whereby the sender adds redundant data to its messages, which allows the receiver to detect and correct errors (within some bound) without the need to ask the sender for additional data. The advantage of forward error correction is that retransmission of data can often be avoided, at the cost of higher bandwidth requirements on average, and is therefore applied in situations where retransmissions are relatively costly or impossible.
A trivial example of FEC to send three times, use majority voting.
Block coding is another type of FEC. Typically, a block code takes a k-digit information word, and transforms this into an n-digit codeword. If the sent data, doesn't match a codeword-but is very near then it was probably that one. Decoding is the hard part.
A cyclic redundancy check (CRC) is a type of hash function, which is used to produce a small, fixed-size checksum of a larger block of data, such as a packet of network traffic or a computer file. The checksum is used to detect errors after transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards by the recipient to confirm that no changes occurred in transit. CRCs are popular because they are simple to implement in binary hardware, are easy to analyse mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.
Multiplexing
Coding distinguishes higher level channels apart, policy determines how the lower layer channel is shared out.
Frequency division multiplexing distinguishes by different frequencies, eg TV.
Time division multiplexing eg different programmes (higher layer) on a certain TV channel (lower layer).
Synchronous time division multiplexing is when the receiver gets data at certain periodic intervals, eg digital telephony gets 8bits of data every 125us. No data identification needed as it's identity is known by the time at which it is sent.
In Asynchronous time division multiplexing identification needs to be sent with packets, to distinguish different senders. Hopes that senders will want to send at different times, otherwise could have a long queue.
Ethernet uses random access in which senders try and send, then if a collision is detected whilst being sent, then sending is aborted and tried again later.
Token rings, and radio conversation ("over") use tokens: once the transmitter is finished they pass the token along.
Reservation systems reserve time in advance.
Slotted systems divide the bandwidth into fixed size slots marked either free or busy.
Packet switching
Two dimensional parity makes the numbers of 1's both horizontally and vertically even.
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
(The bottom left 0 applies to the row of parity bits, not the column).
Checksums simply provide the result of adding all sent data.
With CRC you work out what you need to add or subtract from the data (treated as a polynomial) to make it exactly divisible by a set number (in Ethernet CRC it is a certain 32bit number) and send that as well as the message.
http://en.wikipedia.org/wiki/Mathematics_of_CRCs
ARQ (Automatic Repeat Request)
If gets data and valid CRC, sends ACK
If gets incorrect CRC or data too long, send NACK
Stop-and-wait
Stop and wait is the simplest ARQ scheme. Send, if no ACK receieved within a certain time or a NACK then resend with a leading 0 (instead of 1) so receiver knows its getting a second copy- not the next frame. This is a slow method as it can't send any data whilst waiting for an ACK.
The sliding window algorithm
The sender sends up to fixed number of frames without waiting for an ACK.
The sender maintains three variables: SWS (send window size), LAR (latest acknowledgement received) and LFS (last frame sent) and maintains
LFS - LAR < SWS
The receiver maintains RWS (receive window size), LAF (largest acceptable frame) and LFR (last frame received) and maintains
LAF - LFR < RWS
Eg if the receiver receives 7 and 8 but not 6 (and LFR=5, RWS=4 so LAF=4+5=9) then it will wait until 6 is received to send ACK's.
Naming, Addressing and Routing
Eg;
Name: John Leslie
Address: FN15
Route: Up one floor, across the hall
Names identify things, addreses identify attatchment points, routes identify paths.
Service access points are the points of attatchment between an upper layer and lower layer entity- you can view addresses as denoting service access points.
Flat address spaces have no structure, eg Ethernet 48. They give few clues to routing protocols.
Class based addresses are normally one of three types (with 0,10 or 110 at the beginning) and the word is split into network and host bits.
ARP
If A knows B's IP address but needs to know B's Ethernet address in order to communicate-
A sends out, using Ethernet broadcast address and ARP request packet containing:
l Tag saying this is an ARP request
l Tag saying IP is the protocol
l A's IP and Ethernet Address
l B's IP address
If B receives this packet and recognises its IP address, it updates its tables about A and transmits to A vie A's Ethernet address:
l Tag saying this is an ARP reply
l Tag saying IP is the protocol
l B's IP and Ethernet Address
l A's IP and Ethernet Address
Routing
A network bridge connects multiple network segments at the data link layer (layer 2) of the OSI model. Bridges are similar to repeaters or network hubs, devices that connect network segments at the physical layer, however a bridge works by using bridging where traffic from one network is managed rather than simply rebroadcast to adjacent network segments. In Ethernet networks, the term "bridge" formally means a device that behaves according to the IEEE 802.1D standard - this is most often referred to as a network switch in marketing literature.
Since bridging takes place at the data link layer of the OSI model, a bridge processes the information from each frame of data it receives. In an Ethernet frame, this provides the MAC address of the frame's source and destination. Bridges use two methods to resolve the network segment that a MAC address belongs to.
A router acts as a junction between two or more networks to buffer and transfer data packets among them. A router is different from a switch and a hub: a router is working on layer 3 of OSI model, a switch on layer 2 and a hub on layer 1. This makes them work for different situations: a switch connects devices to form a Local area network (LAN) (which might, in turn, be connected to another network via a router).
One easy illustration for the different functions of routers and switches is to think of switches as neighborhood streets, and the router as the intersections with the street signs. Each house on the street has an address within a range on the block. In the same way, a switch connects various devices each with their own IP address(es) on a LAN. However, the switch knows nothing about IP addresses except its own management address. Routers connect networks together the way that on-ramps or major intersections connect streets to both highways and freeways, etc. The street signs at the intersection (routing table) show which way the packets need to flow.
In order to route packets, a router communicates with other routers using routing protocols and using this information creates and maintains a routing table. The routing table stores the best routes to certain network destinations, the "routing metrics" associated with those routes, and the path to the next hop router. See the routing article for a more detailed discussion of how this works.
Routing is most commonly associated with the Internet Protocol, although other less-popular routed protocols are in use.
Router means Connection between different networks... sample example: 192.168.0.1 to 10.0.0.1.
Forwarding: Taking a packet, looking at is destination address, consulting a table, and sending the packet in a direction determined by that table. Routing is the process by which routing tables are built.
The forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as Ethernet address of the next hop.
The routing table, on the other hand, is the table that is built up by the routing algorithms as a precursor to building the forwarding table.
Can get the source to choose the route and embed it in the packet.
The internet
Internet Protocol (IP) service is the delivery of internet datagrams- a low level common service.
Eg; over Ethernet the frame data section contains the ip header and ip data.
The IP Address has two parts: network address and host address.
Datagram = connectionless
Virtual circuit = connection orientated
TCP
To establish a connection, TCP uses a three-way handshake. Before a client attempts to connect with a server, the server must first bind to a port to open it up for connections: this is called a passive open. Once the passive open is established, a client may initiate an active open. To establish a connection, the three-way (or 3-step) handshake occurs:
1. The active open is performed by sending a SYN to the server.
2. In response, the server replies with a SYN-ACK.
3. Finally the client sends an ACK (usually called SYN-ACK-ACK) back to the server.
At this point, both the client and server have received an acknowledgement of the connection.
Example:
1. The initiating host (client) sends a synchronization (SYN flag set) packet to initiate a connection. Any SYN packet holds a Sequence Number. The Sequence Number is a 32-bit field in TCP segment header. For example let the Sequence Number value for this session be x.
2. The other host receives the packet, records the Sequence Number of x from the client, and replies with an acknowledgment and synchronization (SYN-ACK). The Acknowledgment Number is a 32-bit field in TCP segment header. It contains the next sequence number that this host is expecting to receive (x + 1). The host also initiates a return session. This includes a TCP segment with its own initial Sequence Number value of y.
3. The initiating host responds with the next Sequence Number (x+1) and a simple Acknowledgment Number value of y + 1, which is the Sequence Number value of the other host + 1.
TCP is different to UDP in that it provides:
l Ordered data transfer
l Retransmission of lost packets
l Discarding duplicate packets
l Error-free data transfer
l Congestion control
Foundations of Functional Programming
Aims
This course aims (a) to show how lambda-calculus and related theories can provide a foundation for a large part of practical programming, (b) to present students with one particular type analysis algorithm so that they will be better able to appreciate the Part II Types course, and (c) to provide a bridge between the Part IA Foundations of Computer Science course and the theory options in Part II.
Lectures
· Introduction. Combinators. Constants and Free Variables. Reduction. Equality. The Church-Rosser theorem. Normal forms.
· The Lambda calculus. Lambda-terms, alpha and beta conversions. Free and bound variables. Abbreviations in the notation. Pure and applied lambda calculi. Relationship between combinators, lambda calculus and typical programming languages. Eager and Lazy evaluation.
· Encoding of data: booleans, tuples, lists and trees, numbers. The treatment of recursion: the Y combinator and its use.
· Modelling imperative programming styles: handling state information and the continuation-passing style. Return address seen as an additional continuation parameter.
· Relationship between this and Turing computability, the halting problem etc.
· Combinator reduction as tree-rewrites. Conversion from lambda-calculus to combinators. The treatment of lambda-bindings in an interpreter: the environment. Closures. ML implementation of lambda-calculus. SECD machine. Brief survey of performance issues.
· Let-polymorphism reviewed following the Part IA coverage of ML. Unification. A type-reconstruction algorithm. Decidability and potential costs.
Objectives
At the end of the course students should
· understand the rules for the construction and processing of combinatory terms and terms in the lambda calculus
· know how to model all major aspects of general-purpose computation in terms of these primitives
· know how lambda terms may be efficiently interpreted by machine
· be able to derive ML-style type judgements for languages based upon the lambda-calculus
Recommended reading
Hindley, J.R. & Seldin, J.P. (1986). Introduction to combinators and lambda-calculus. Cambridge University Press (now out of print but try a library).
Revesz, G.E. (1988). Lambda calculus, combinators and functional programming. Cambridge University Press (now out of print but try a library).
Mathematical Methods for Computer Science
Aims
The aim of this course is to introduce and develop mathematical methods that are key to many modern applications in Computer Science. The course proceeds on two fronts: (i) Fourier methods and their generalisations that lie at the heart of modern digital signal processing, coding and information theory and (ii) probability modelling techniques that allow stochastic systems and algorithms to be described and better understood. The style of the course is necessarily concise but will attempt to blend a mix of theory with examples and glimpse ahead at applications taken up in Part II courses.
Lectures
· Fourier methods. Inner product spaces and orthonormal systems. Periodic functions and Fourier series. Results and applications. The Fourier transform and its properties. [3 lectures]
· Discrete Fourier methods. The Discrete Fourier transform and applications. The Fast Fourier Transform algorithm. [2 lectures]
· Wavelets. Introduction to wavelets with computer science applications. [1 lecture]
· Inequalities and limit theorems. Bounds on tail probabilities, moment generating functions, notions of convergence, weak and strong laws of large numbers, the central limit theorem, statistical applications, Monte Carlo simulation. [3 lectures]
· Markov chains. Discrete-time Markov chains, Chapman-Kolmogorov equations, classifications of states, limiting and stationary behaviour, time-reversible Markov chains. Examples and applications. [3 lectures]
Objectives
At the end of the course students should
· grasp key properties and uses of Fourier analysis, transforms, and wavelets
· understand discrete transform techniques
· understand basic probabilistic inequalities and limit results and be able to apply them to commonly arising models
· be familiar with the fundamental properties and uses of discrete-time Markov chains
Reference books
Oppenheim, A.V. & Willsky, A.S. (1997). Signals and systems. Prentice Hall.
* Pinkus, A. & Zafrany, S. (1997). Fourier series and integral transforms. Cambridge University Press.
Mitzenmacher, M. & Upfal, E. (2005). Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press.
* Ross, S.M. (2002). Probability models for computer science. Harcourt/Academic Press.
Probability
Lecturer: Dr F.H. King
No. of lectures: 12
This course is a prerequisite for Mathematical Methods for Computer Science, and the following Part II courses: Artificial Intelligence II, Computer Systems Modelling, Information Theory and Coding, Computer Vision, Digital Signal Processing.
Aims
The principal aim of this course is to provide a foundation course in Probability with particular emphasis on discrete distributions. A secondary aim is to provide a somewhat formal approach to the subject but one which is accessible to those with single subject A-level Mathematics.
Lectures
· Single random variable. Chance phenomena, discrete versus continuous. Probability in Computer Science. Experiments. Need for a probability calculus. Random variables. P(X = r) notation. Probability models. Elementary events. Sample space. Relationship to set theory. Probability axioms. Addition theorem. Conditional probability.
· Two or more random variables. Independence. Distinguishability. Multiplication theorem. Uniform distribution. Array diagrams. Event trees. Bayes's theorem. Combinatorial numbers. Pascal's triangle. Binomial theorem.
· Discrete distributions. Uniform distribution. Triangular distribution. Binomial distribution. Trinomial distribution. Multinomial distribution. Expectation or mean.
· Means and variances. Derived random variables. Variance and standard deviation. Geometric distribution. Poisson distribution. Revision of summation (double-sigma sign). Mean and variance when there are two or more random variables. Independence and covariance.
· Correlation. Correlation coefficient. Complete positive correlation. Complete negative correlation. Means and variances of particular distributions. A polynomial with probabilities as coefficients.
· Probability generating functions. Generating functions. Means and variances of distributions revisited. Application of generating functions to P(X + Y = t).
· Difference equations. General introduction to linear, second-order difference equations with constant coefficients. How these equations are found in Probability. How to solve both homogeneous and inhomogeneous difference equations.
· Stochastic processes. Random walks, recurrent versus transient. Gambler's ruin, absorbing barriers, probability of winning and losing, expected length of a game.
· Continuous distributions. Continuous probability models. Probability density functions. Expectation and variance. Uniform distribution. Poisson distribution. Negative exponential distribution.
· Bivariate distributions. Normal distribution. The central limit theorem. Bivariate distributions. Illustrations.
· Transforming probability density functions. Revision of integration by substitution. Application to probability density functions. Transforming a uniform distribution. Illustrations.
· Transforming bivariate probability density functions. Transforming a Uniform distribution into a Normal distribution using Excel. Revision of integration with two independent variables. Jacobians. Application to bivariate probability density functions. The Box-Muller transformation.
Objectives
At the end of the course students should
· have some feeling for Probability to the extent that they can recognise which of the techniques that have been covered in the course might be appropriate in given circumstances
· have some appreciation of the assumptions that need to be made when a particular technique is used or when a particular distribution may apply
Recommended book
Grimmett, G. & Welsh, D. (1986). Probability: an introduction. Oxford University Press.
Relationship to set theory
The collection of outcomes possible from an experiment can be represented as a set.
For example, in the case of a die the sample space can be written:
Ω = {1,2,3,4,5,6}
Events
You may be betting on an Event, that is a particular subset of outcomes.
For example, you may be betting that the result of a die will be an even number, ie that the result will be a member of the subset:
E = {2,4,6}
The likelihood of the result of a throw being the empty set Ø={} is 0, the likelihood of Ω is certain.
An elementary event corresponds to a single sample point. The elementary event {5} is a subset of Ω whereas 5 is a member of Ω.
The cardinality (number of members) of a set is written as |A|. It is obvious that for dice where the likelihood of numbers is equal:
P(A) = |A| / |Ω|
Two events are independent if P(B|A)= P(B)
Random Variables
A random variable can be assigned to different values. The notation { X=r } refers to a random variable with name X and value r.
Discrete Variables
If there is a limited number of possible outcomes, then the the outcome is a discrete random variable.
Events are said to be exhaustive if the union of the sets includes every possible sample point.
Events are said to be exclusive the the associated sets are disjoint.
Capital P Notation
P({X=r}) means the probability of the random variable X being r.
P(E) means the probability of the event E.
Double Sigma Notation
Say you are rolling the dice twice, the first result being labelled r and the second s. You can write the sum as:
Rules of Probability
P(B|A) = Probability of B given A = 
Bayes Theorem
from medicine.mcgill.ca
Semantics of Programming Languages
Aims
The aim of this course is to introduce the structural, operational approach to programming language semantics. It will show how to specify the meaning of typical programming language constructs, in the context of language design, and how to reason formally about semantic properties of programs.
Lectures
· Introduction. Transition systems. The idea of structural operational semantics. Transition semantics of a simple imperative language. Language design options.
· Types. Introduction to formal type systems. Typing for the simple imperative language. Statements of desirable properties.
· Induction. Review of mathematical induction. Abstract syntax trees and structural induction. Rule-based inductive definitions and proofs. Proofs of type safety properties.
· Functions. Call-by-name and call-by-value function application, semantics and typing. Local recursive definitions.
· Data. Semantics and typing for products, sums, records, references.
· Subtyping. Record subtyping and simple object encoding.
· Semantic equivalence. Semantic equivalence of phrases in a simple imperative language, including the congruence property. Examples of equivalence and non-equivalence.
· Concurrency. Shared variable interleaving. Semantics for simple mutexes; a serializability property.
· Low-level semantics. Monomorphic typed assembly language.
Objectives
At the end of the course students should
· be familiar with rule-based presentations of the operational semantics and type systems for some simple imperative, functional and interactive program constructs
· be able to prove properties of an operational semantics using various forms of induction (mathematical, structural, and rule-based)
· be familiar with some operationally-based notions of semantic equivalence of program phrases and their basic properties
Recommended reading
Hennessy, M. (1990). The semantics of programming languages. Wiley. Out of print, but available on the web at http://www.cogs.susx.ac.uk/users/matthewh/semnotes.ps.gz
* Pierce, B.C. (2002). Types and programming languages. MIT Press.
Winskel, G. (1993). The formal semantics of programming languages. MIT Press.
Artificial Intelligence I
Aims
The aim of this course is to provide an introduction to some basic issues and algorithms in artificial intelligence (AI). The course approaches AI from an algorithmic, computer science-centric perspective; relatively little reference is made to the complementary perspectives developed within psychology, neuroscience or elsewhere. The course aims to provide some basic tools and algorithms required to produce AI systems able to exhibit limited human-like abilities, particularly in the form of problem solving by search, representing and reasoning with knowledge, planning, and learning.
Lectures
· Introduction. What is it that we're studying? Why is something that looks so easy to do actually so difficult to compute? Theories and methods: what approaches have been tried? What does this course cover, and what is left out?
· Agents. A unifying view of AI systems. How could we approach the construction of such a system? How would we judge an AI system? What should such a system do and how does it interact with its environment?
· Search I. How can search serve as a fundamental paradigm for intelligent problem-solving? Simple, uninformed search algorithms.
· Search II. More sophisticated heuristic search algorithms.
· Search III. Search in an adversarial environment. Computer game playing.
· Constraint satisfaction problems.
· Knowledge representation and reasoning. How can we represent and deal with commonsense knowledge and other forms of knowledge? Semantic networks, frames and rules. How can we use inference in conjunction with a knowledge representation scheme to perform reasoning about the world and thereby to solve problems? Inheritance, forward and backward chaining.
· Planning. Methods for planning in advance how to solve a problem. The partial-order planning algorithm.
· Learning. A brief introduction to supervised learning from examples, focusing on neural networks. [4 lectures]
Objectives
At the end of the course students should
· Appreciate the distinction between the popular view of the field and the actual research results.
· Appreciate different perspectives on what the problems of artificial intelligence are and how different approaches are justified.
· Be able to design basic problem solving methods based on AI-based search, reasoning, planning, and learning algorithms.
Recommended reading
* Russell, S. & Norvig, P. (2003). Artificial intelligence: a modern approach. Prentice Hall (2nd ed.).
Luger, G.F. & Stubblefield, W.A. (1998). Artificial intelligence: structures and strategies for complex problem solving. Addison-Wesley.
Dean, T., Allen, J. & Aloimonos, Y. (1995). Artificial intelligence: theory and practice. Benjamin/Cummings.
Requirements
● Knowledge representation to store what it knows or hears
● Automated reasoning to use the stored information to answer questions and to draw new conclusions
● Machine learning to adapt to new circumstances and to detect and extrapolate patterns
Agents
An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. We use the term percept to refer to the agents perceptual inputs at any given instance. An agent's percept sequence is the complete history of everything the agent has ever perceived. The mathematical agent function maps any given percept sequence to an action, and is implemented by an agent program.
Example: email spam filter.
Percepts: the textual content of individual email messages. (A more
sophisticated program might also take images or other attachments
as percepts.)
Actions: send to the in box, delete, or ask for advice.
Goals: remove spam while allowing valid email to be read.
Environment: an email program.
A rational agent is one that does the right thing, that is every entry in the table for the agent function is filled out correctly. A performance measure embodies the criterion for success of an agent's behaviour. Autonomy is the extent to which an agent can act without relieving on prior knowledge from its designer.
Definition or a rational agent:
"For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has"
● In general, we will be interested in success over the long term.
For example, we might not want to favour a car-cleaner that's extremely fast in the rest hour and then sits around reading, over one that works consistently.
● We are generally interested in expected performance because usually agents are not omniscient. they don't infallibly know the outcome of their actions.
As a general rule it is better to design performance measures according to what one actually wants in the environment, rather than according to how one thinks the agent should behave.
In designing an agent we design the task environment which is defined by PEAS (Performance, Environment, Actuators, Sensors)
Environments
● An environment is fully observable if if an agents sensor give it access to the complete state of the environment of each point in time.
● If the next state of the environment is completely determined by the current state and the action executed by the agent, then we say the environment is deterministic.
● In an episodic task environment, the agent's experience is divided into atomic episodes.
● Static if the environment doesn't change whilst deliberating.
● Discrete environment (time,actions) eg chess as opposed to taxi driving
● Single environment eg crossword as opposed to chess.
Keeping track of the environment:
action agent (percept)
{
static state;
static rules;
state = update(state,percept);
rule = match(state,rules);
next_action = find_action(rule);
state = update(state,action);
return next_action;
}
Simple reflex agents are the simplest kind of agents. These agents act on the current percept, as opposed to the rest of the percept history. Eg; if car-in-front-is-breaking then initiate-breaking. These kind of agents only work if the environment is fully observable.
Model-based reflex agents maintain internal state to track aspects of the world that are not evident on the current percept.
Goal based agents act to achieve their goals
Utility based agents -they try to maximize their maximum expected happiness
Learning agents -as Turing suggested, this is the easier way of creating complex AI. These agents have a learning element and a performance element (action performing) and the problem generator.
Solving Problems by Searching
There are methods that an agent can use to select actions in environments that are deterministic, observable, static and completely known. In such cases the agent can construct sequences of actions that achieve its goals; this process is called search.
● Before an agent can start searching for solutions, it must formulate a goal and then use the goal to formulate a problem.
● A problem consists of four parts: the initial state, a set of actions, a goal test function, and a path cost function. The environment of the problem is represented by a state space. A path through the state space from the initial state to a goal state is a solution.
● A single, general TREE-SEARCH algorithm can be used to solve any problem; specific variants of the algorithm embody different strategies.
● Search algorithms are judged on the basis of completeness, optimality, time complexity, and space complexity. Complexity depends on b, the branching factor in the state space, and d, the depth of the shallowest solution.
● Breadth-first search selects the shallowest unexpanded node in the search tree for expansion. It is complete, optimal for unit step costs, and has time and space complexity of O(bd). The space complexity makes it impractical in most cases. Uniform-cost search is similar to breadth-first search but expands the node with lowest path cost, g(n). It is complete and optimal if the cost of each step exceeds some positive bound e.
● Depth-first search selects the deepest unexpanded node in the search tree for expansion. It is neither complete nor optimal and has time complexity of O(bm) and space complexity of O(bm), where m is the maximum depth of any path in the state space.
● Depth-limited search imposes a fixed depth limit on a depth-first search.
● Iterative deepening search calls depth-limited search with increasing limits until a goal is found. It is complete, optimal for unit step costs, and has time complexity of O(bd) and space complexity of O(bd).
● Bidirectional search can enormously reduce time complexity, but it is not always applicable and may require too much space.
● When the state space is a graph rather than a tree, it can pay off to check for repeated states in the search tree. The GRAPH-SEAERCH algorithm eliminates all duplicate states.
● When the environment is partially observable, the agent can apply search algorithms in the space of belief states, or sets of possible states that the agent might be in. In some cases, a single solution sequence can be constructed; in most other cases, the agent needs a contingency plan, to handle unknown circumstances that may arise.
Notes from lectures:
the total cost=path cost+search cost
● Uninformed or blind search is applicable when we only distinguish goal states from non-goal states. Methods are distinguished by the order in which nodes in the search tree are expanded. These methods include: breadth-first, uniform cost, depth-rst, depth-limited, iterative deepening, bidirectional.
● Informed or heuristic search is applied if we have some knowledge of the path cost or the number of steps between the current state and a goal. These methods include: best first, greedy, A*, iterative deepening A* (IDA*), SMA*.
Uniform-cost search differs in that it always expands the node with the lowest path-cost first
A heuristic function, usually denoted h(n) is one that estimates the cost of the best path from any node to a goal. If n is a goal then h(n)=0.
A* search combines the good points of:
greedy search—by making use of h(n)
uniform-cost search- by being optimal and complete.
It uses path cost g(n) and also the heuristic function h(n) by forming
f(n) = g(n) + h(n)
where
g(n) = cost of path to n
and
h(n) = estimated cost of best path from n
So: f(n) is the estimated cost of a path through n.
Definition: an admissible heuristic f(n) is one that never overestimates the cost of the best path from n to a goal.
Iterative deepening search used depth-first search with a limit on depth that gradually increased.
IDA * does the same thing with a limit on f cost.
It is complete and optimal under the same conditions as A*.
It only requires space proportional to the longest path.
The time taken depends on the number of values h can take.
Informed Search and Exploration
This section examines the application of heuristics to reduce search costs. Optimality comes at a stiff price in terms of search cost, even with good heuristics.
● Best-first search is just GRAPH-SEARCH where the minimum-cost unexpanded nodes (According to some measure) are selected for expansion. Best-first algorithms typically use a heuristic function h(n) that estimates the cost of a solution from n.
● Greedy best-first search expands nodes with minimal h(n). It is not optimal, but is often efficient.
● A* search expands nodes with minimal f(n) = g(n) + h(n). A* is complete and optimal, provided that we guarantee that h(n) is admissible (for TREE-SEARCH) or consistent (for GRAPH-SEARCH). The space complexity of A* is still prohibitive.
● The performance of heuristic search algorithms depends on the quality of the heuristic function. Good heuristics can sometimes be constructed by relaxing the problem definition, by pre computing solution costs for subproblems in a pattern database, or by learning from experience with the problem class.
● RBFS and SMA* are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems that A* cannot solve because it runs out of memory.
● Local search methods such as hill climbing operate on complete-state formulations, keeping only a small number of nodes in memory. Several stochastic algorithms have been developed, including simulated annealing, which returns optimal solutions when given an appropriate cooling schedule. Many local search methods can also be used to solve problems in continues spaces.
● A genetic algorithm is a stochastic hill-climbing search in which a large population of states is maintained. New states are generated by mutation and by crossover, which combines pairs of states from the population.
● Exploration problems arise when the agent has no idea about the states and actions of its environment. For safely explorable environments, online search agents can build a map and find a goal if one exists. Updating heuristic estimates from experience provides an effective method to escape from local minima.
Constraint Satisfaction Problems
● Constraint satisfaction problems consist of variables with constraints on them. Many important real-world problems can be described as CSPs. The structure of a CSP can be represented by its constraint graph.
● Backtracking search, a form of depth-first search, is commonly used for solving CPSs.
● The minimum remaining values and degree heuristics are domain-independent methods for deciding which variable to choose next in a backtracking search. The least-constraining-value heuristic helps in ordering the variable values.
● By propagating the consequences of the partial assignments that it constructs, the backtracking algorithm can reduce greatly the branching factor of the problem. Forward checking is the simplest method for doing this. Arc consistency enforcement is a more powerful technique, but can be more expensive to run.
● Backtracking occurs when no legal assignment can be found for a variable. Conflict-directed backjumping backtracks directly to the source of the problem.
● Local search using the min-conflicts heuristic has been applied to constraint satisfaction problems with great success.
● The complexity of solving a CSP is strongly related to the structure of its constraint graph. Tree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one and is very efficient if a small cutset can be found. Tree decomposition techniques transform the CSP into a tree of sub problems and are efficient if the tree width of the constraint graph is small.
Games
● A game may be defined by the initial state (how the board is set up), the legal actions in each state, a terminal test (which says when the game is over), and a utility function that applies to terminal states.
● In two-player zero-sum games with perfect information, the minimax algorithm can select optimal moves using a depth-first enumeration of the game tree.
● The alpha-beta search algorithm computes the same optimal move as minimax, but achieves much greater efficiency by eliminating sub trees that are provably irrelevant.
● Usually, it is not feasible to consider the whole game tree (even with alpha-beta), so we need to cut the search off at some point and apply an evaluation function that gives an estimate of the utility of a state.
● Games of chance can be handled by an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children nodes, weighted by the probability of each child.
● Optimal play in games of imperfect information, such as bridge, requires reasoning about the current and future belief states of each player. A simple approximation can be obtained by averaging the value of an action over each possible configuration of missing information.
● Programs can match or beat the best human players in checkers, Othello, and backgammon and are close behind in bridge, A program has beaten the world chess champion in one exhibition match. Programs remain at the amateur level in Go.
Lecture notes:
CSPs standardise the manner in which states and goal tests are represented.
As a result we can devise general purpose algorithms and heuristics.
The form of the goal test can tell us about the structure of the problem.
Consequently it is possible to introduce techniques for decomposing problems.
We can also try to understand the relationship between the structure of a problem and the difficulty of solving it.
Clearly a CSP can be formulated as a search problem in the familiar sense:
Initial state:
--no variables are assigned.
Successor function: assigns value(s) to currently unassigned variable(s) provided constraints are not violated.
Goal: reached if all variables are assigned.
Path cost: constant # per step.
In addition:
The tree is limited to depth so depth-first search is usable.
It is fairly easy to see that a CSP can be give as an incremental formulation as a standard search problem as follows:
● Initial state: the empty assignment {}, in which all variables are unassigned.
● Successor function: a vallue can be assigned to any unassigned variable, provided that it does nto conflict with previously assigned variables.
● Goal test: the current assignment is complete.
● Path cost: a constant cost (eg 1) for every step.
Every solution must be a complete assignment and therefore appears at depth n if there are n variables. Furthermore, the search tree extends only to depth n. For these reasons, depth-first search algorithms are popular for CSPs.
Planning
● Planning systems are problem-solving algorithms that operate on explicit propositional (or first-order) representations of states and actions. These representations make possible the derivation of effective heuristics and the development of powerful and flexible algorithms for solving problems.
● The STRIPS language describes actions in terms of their preconditions and effects and describes the initial and goal states as conjunctions of positive literals. The ADL language replaces some of these constraints, allowing disjunction, negation and quantifiers.
● State0space search can operate in the forward direction (progression) or backward direction (regression). Effective heuristics can be derived by making a subgoal independence assumption and by various relaxations of the planning problem.
● Partial-order planning (POP) algorithms explore the space of plans without committing to a totally ordered sequence of actions. They work back from the goal, adding actions to the plan to achieve each subgoal. They are particularly effective on problems amenable to a divide-and-conquer approach.
● A planning graph can be constructed incrementally, starting form the intitial state. Each layer contains a superset o fall the literals or actions that could occur at that time step and encodes mutual exclusion, or mutex, relations among literals or actions that cannot co-occur. Planning graphs yield useful heuristics for state-space and partial-order planners and can be used directly in the GRAPHPLAN algorithm.
● The SATPLAN algorithm translates a planning problem into propositional axioms and applies a satisfiability algorithm to find a model that corresponds to a valid plan. Several different propositional representations have been developed, with carying degrees of compactness and efficiency.
● Each of the major approaches to planning as its adherents, and there is as yet no consensus on which is best. Competition and cross-fertilization among the approaches have resulted in significant gains in efficiency for planning systems.
Learning from Observation
● Learning takes many forms, depending on the nature of the performance element, the component to be improved, and the available feedback,.
● If the available feedback, either from a teacher or from the environment, provides the correct value for the examples, the learning problem is called supervised learning. The task, also called inductive learning, is then to learn a function from examples of its inputs and outputs. Learning a discrete-valued function is called classification; learning a continuous function is called regression.
● Inductive learning involves finding a consistent hypothesis that agrees with the examples. Ockham's razor suggests choosing the simplest consistent hypothesis. The difficulty of this task depends on the chosen representation.
● Decision trees can represent all Boolean functions. The information gain heuristic provides an efficient method for finding a simple, consistent decision tree.
● The performance of a learning algorithm is measured by the learning curve, which shows the prediction accuracy on the test set as a function of the training set size.
● Ensemble methods such as boosting often perform better than individual methods.
● Computation learning theory analyses the sample complexity and computational complexity of inductive learning. There is a trade-off between the expressiveness of the hypothesis language and the ease of learning.
Knowledge in Learning
● The use of prior knowledge leads to a picture of cumulative learning. In which learning agents improve their learning ability by eliminating otherwise consistent ypotheses and by "filling in" the explanations of examples, thereby allowing for shorter hypotheses. These contributions often result in faster learning from fewer examples.
● Understanding the different logical roles played by prior knowledge, as expressed by entailment constraints, help to define a variety of learning techniques.
● Explanation based learning (EBL) extracts general rules from single examples by exaplining the examples and generalizing the explanation. It provides a deductive method turning first-principles knowledge into useful, efficient, special-purpose expertise.
● Relevence-based learning (RBL) uses prior knowledge in the form of determinations to identify the relevant attrivutres, thereby generating a reduced hypohtesis space and speeding up learning. RBL also allows deductive gneerazlizations from single examples.
● Knowledge-based inductive learning (KBIL) finds inductive hypotheses that explain sets of observations with the help of background knowledge.
● Inductive logic programming (ILP) techniques perform KBIL on knowledge that is expressed in first-order logic. ILP methods can elarn relational knowledge htat is not expressible in attribute based systems.
● ILP can be done with a top-down approach or refining a very general rule or though a bottom-up approach of inverting the deductive process.
● ILP methods generate new predicates with which concise new theories can be expressed and show promise as general-purpose scientific theory formation systems.
Boolean CSPs include as special cases some NP-complete problems, such as 3SAT. In the worst case, therefore, we cannot expect to solve finite-domain CSPs in less than exponential time. In most practical applications, however, general-purpose CSP algorithms can solve problems orders of magnitude larger than those solvable via the general-purpose (non heuristic) searches described below.
The complexity of solving a CSP is strongly related to the structure of its constraint graph. Tree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one and is very efficient if a small cutset can be found. Tree decomposition techniques transform the CSP into a tree of sub problems and are efficient if the tree width of the constraint graph is small.
Breadth-first search is complete and optimal, but has exponential cost both in terms of space and time. Depth first search is neither complete nor optimal, but has exponential time complexity yet linear space complexity. Iterative deepening search is complete, optimal for unit step costs, and exponential time complexity and linear space complexity.
Informed or heuristic search is applied if we have some knowledge of the path cost or the number of steps between the current state and a goal, and whilst more intelligent they can still fare poorly in terms of performance. Greedy search is not optimal nor complete, and has exponential time and space complexity - it can however, be very effective provided you have a good heuristic function. A* search combines the good points of greedy search (By making good use of h(n) ) and also of uniform-cost search (complete and optimal). Whilst being optimally efficient (ie no other optimal algorithm that works by constructing paths from the root can guarantee to examine fewer nodes) it still has exponential time and space complexity. IDA* has only linear space complexity but still has exponential time complexity.
The term backtracking search is used for a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign.
In pseudo-code:
function BACKTRACKING-SEARCH(csp) returns a solution, or failure
return RECURSIVE-BACKTRACKING( {}, csp)
function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure
if assignment is complete then return assignment
var <-- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
if value is consistent with assignment according to CONSTRAINTS[csp] then
add { var = value } to assignment
result <-- RECURSIVE-BACKTRACKING(assignment, csp)
if result != failure then return result
remove { var = value } from assignment
return failure
This simple version of backtracking uses chronological backtracking, a better way would be to go back to one of the set of variables that caused the failure (with a conflict set).
By default, SELECT-UNASSIGNED-VARIABLE in my answer above simply selects the next unassigned variable in the order given by the list VARIABLE[csp]. This static variable ordering seldom results in the most efficient search. A better way to do it would be to assign the variable with the least number of possible "legal values" next. For example, at a certain stage there may be only one possible value that a variable could take- it would make sense to assign that value now and not have to worry about it later. This idea is called the minimum remaining values (MRV) heuristic.
The degree heuristic attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables.
Once a variable has been selected, the algorithm must decide on the order in which to examine its values. The least-constraining-value heuristic can be effective in some cases; it prefers the value that rules out the fewest choices for the neighbouring variables in the constraint graph. In general, the heuristic is trying to leave the maximum flexibility for subsequent variable assignments.
An admissible heuristic h is a function that gives a guaranteed lower bound on the distance from any node u to the destination t.
● Natural example: straight-line distance (at maximum speed) to t.
h(n) is monotonic if f(n) = g(n)+h(n) never decreases along a path from the root.
● Almost all admissible heuristics are monotonic
● h(n) is monotonic iff it obeys the triangle inequality
Or rephrased (from Course Text...)
"A heuristic h(n) is monotonic if, for every node n and every successor n' or n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' plus the estimated cost of reaching the goal from n':
h(n) < c(n,a,n') + h(n)
(This is a form of the general triangle inequality)."
Best-first search is an instance of the general TREE-SEARCH algorithm in which a node is selected fro expansion based on an evaluation function f(n) = estimated cost of the cheapest path from node n to a goal node.
Greedy best first search tries to expand the node that is closest to the goal (ie f(n)=h(n) ).
A* search however evaluates nodes by combining g(n), the cost to reach the node, and h(n), the estimated cost of the cheapest path from n to the goal:
f(n) = g(n) + h(n) or in words
f(b) = estimated cost of the cheapest solution through n.
A* is optimal if h(n) is an admissible heuristic.
Proof A* is optimal:
Let Goalopt be an optimal goal state with
f(Goalopt) = g(Goalopt) = fopt
Let Goal2 be a suboptimal goal state with
f(Goal2) = g(Goal2) = f2 > fopt
We need to demonstrate that the search can never select Goal2 (a suboptimal goal state)
Let n be a leaf node on an optimal path to Goalopt. So
fopt > f(n)
because h is admissible and we're assuming it's also monotonic.
Now say Goal2 is chosen for expansion before n. This means that
f(n) > f2
so we've established that
fopt > f2 = g(Goal2).
But this means that Goalopt is not optimal. Contradiction!
A* search is also complete provided:
● The graph has finite branching factor;
● There is a finite, positive constant c such that each operator has cost at least c.
The search expands nodes according to increasing f(n). So the only way it can fail to find a goal is if there are infinitely many nodes with f(n) < f(Goal).
There are two ways this can happen:
● There is a node with an infinite number of descendants
● There is a path with an infinite number of nodes but a finite path cost.
Given a game tree, the optimal strategy can be determined by examining the minimax value of each node, MINIMAX-VALUE(n). The minimax value of a node is the utility (for MAX, ie current player) of being in the corresponding state, assuming that both players play optimally from there to the end of the game. The minimax decision is the optimal choice for MAX because it leads to the successor with the highest minimax value. The minimax algorithm computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceeds all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds.
The minimax algorithm performs a complete depth-first exploration of the game tree.
If the maximum depth of the tree is m, and there are b legal moves at each point, then the time complexity of the minimax algorithm is O(bm). The space complexity is O(bm) for an algorithm that generates all successors at once, or O(m) for an algorithm that generates successors one at a time.
For real games the time cost is impractical, so a number of time saving techniques are implemented. Whilst we can't eliminate the exponent from the computational complexity, we can effectively cut it in half with alpha-beta pruning.
Consider a node n somewhere in the tree, such that Player has a choice of moving to that node. If Player has a better choice m either at the parent node of n or at any choice point further up, then n will never be reached in actual play. So once we have found out enough about n (by examining its descendants) to reach this conclusion, we can prune it.
Alpha beta-pruning gets its name from the following two parameters that describe bounds on the backed-up values that appear anywhere along the path:
● α = the value of the best (ie highest value) choice we have found so far at any choice point along the path for MAX.
● β = the value of the best (ie lowest value) choice we have found so far at any choice point along the path for MIN.
Alpha-beta search updates the values of α and β as its goes along and prunes the remaining branches at a node as soon as the value of the current node is known to be worse than the current α or β value for MAX or MIN, respectively.
Complexity Theory
Aims
The aim of the course is to introduce the theory of computational complexity. The course will explain measures of the complexity of problems and of algorithms, based on time and space used on abstract models. Important complexity classes will be defined, and the notion of completeness established through a thorough study of NP-completeness. Applications to cryptographic protocols will be considered.
Lectures
· Algorithms and problems. Complexity of algorithms and of problems. Lower and upper bounds. Examples: sorting and travelling salesman.
· Time and space. Models of computation and measures of complexity. Time and space complexity on a Turing machine. Decidability and complexity.
· Time complexity. Time complexity classes. Polynomial time problems and algorithms. P and NP.
· Non-determinism. Non-deterministic machines. The class NP redefined. Non-deterministic algorithms for reachability and satisfiability.
· NP-completeness. Reductions and completeness. NP-completeness of satisfiability.
· More NP-complete problems. Graph-theoretic problems. Hamiltonian cycle and clique.
· More NP-complete problems. Sets, numbers and scheduling. Matching, set covering and bin packing.
· coNP. Validity of boolean formulas and its completeness. NP
coNP. Primality and factorisation.
· Cryptographic complexity. One-way functions. The class UP.
· Space complexity. Deterministic and non-deterministic space complexity classes. The reachability method. Savitch's theorem.
· Hierarchy. The time and space hierarchy theorems and complete problems.
· Protocols. Interactive proofs. Zero knowledge.
Objectives
At the end of the course students should
· be able to analyse practical problems and classify them according to their complexity
· be familiar with the phenomenon of NP-completeness, and be able to identify problems that are NP-complete
· be aware of a variety of complexity classes and their interrelationships
· understand the role of complexity analysis in cryptographic protocols
Recommended books
* Papadimitriou, Ch.H. (1994). Computational complexity. Addison-Wesley.
Sipser, M. (1997). Introduction to the theory of computation. PWS.
http://www.cs.swan.ac.uk/~csoliver/AlgorithmsComplexity200607/Skripte/AlgorithmsComplexity200607_10a.pdf
Lk-COL,LSAT,LISO,LHAM contained in LSpace.
and computable in expopnential time
Np:
It may by hard to find a solution, but a possible solution is relatively small, once you have guessed one it is easy to verify whether it is actually a solution.
More precisely, the class NP P({0, 1})
(as "nondeterministic polynomial time", roughly
"polynomial time using guessing") is defined as the
set of all languages L {0, 1} (aka problems), such
that there exists a
"verification algorithm" V
running in polynomial times, which takes as input a
pair (x,w) 2 {0, 1}, where x is a "problem" and w
is a possible "witness" for x 2 L, and outputs 0 or 1
(where in case V (x,w) = 1 it follows x 2 L), and there
exists a polynomial p, such that for all x 2 {0, 1} we
have
x 2 L if and only if there is a w 2 {0, 1} with
|w| p(|x|) and V (x,w) = 1.
We have
LISO,Lk-COL,LHAM 2 NP.v
Compiler Construction
Syllabus
Lecturer: Dr T.G. Griffin
No. of lectures: 18
This course is a prerequisite for Optimising Compilers (Part II).
Aims
This course aims to cover the main technologies associated with compiling programming languages, viz. lexical analysis, syntax analysis, type checking, run-time data organisation and code-generation.
The course will be based around the study a simple compiler called MinCaml (http://min-caml.sourceforge.net/index-e.html) that was designed and implemented by Eijiro Sumii at the University of Tokyo. Dr Griffin will also make available extensions to this compiler tailored to the needs of this course.
Lectures
· Survey of execution mechanisms. The spectrum of interpreters and compilers; compile-time and run-time. Structure of a simple compiler, virtual machines.
· Lexical analysis and syntax analysis. Regular expressions and finite state machine implementations. Parsing algorithms: recursive descent and SLR(k)/LALR(k). Abstract syntax tree; expressions, declarations and commands. Summary of Lex and Yacc.
· Simple type-checking. Type of an expression determined by type of subexpressions; inserting coercions.
· Translation phase. Intermediate code design. Translation of expressions, commands and declarations. Compilation as a sequence of translations.
· Low-level representations. Variable binding, functions, higher-order functions. Environments, function values are closures. Free variable treatment, static and dynamic chains, ML free variables. Argument passing mechanisms. Objects and inheritance; implementation of methods. Storage allocation, garbage collection.
· Code generation. Typical machine codes. Code generation from intermediate code.
· Object modules and linkers. Resolving external references. Static and dynamic linking.
Objectives
At the end of the course students should understand the overall structure of a compiler, and will know significant details of a number of important techniques commonly used. They will be aware of the way in which language features raise challenges for compiler builders.
Recommended reading
* Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions. The ML edition is best for this course). Cambridge University Press.
* MinCaml code and documentation. http://min-caml.sourceforge.net/index-e.html
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: principles, techniques and tools. Addison-Wesley.
Bennett, J.P. (1990). Introduction to compiling techniques: a first course using ANSI C, LEX and YACC. McGraw-Hill.
Levine, J.R. (1999). Linkers and loaders. San Francisco: Morgan Kaufmann.
In: Program Text
The compiler composes of a front, middle and back end
Front-end
Lexical Analysis
Analysis of the text to find meaning and validity, based on finite automaton and regular expressions.
The lexical tokens that the program text is split into are passed down to Parsing
Parsing
Parsing theory based on push-down automaton and context-free grammars.
This stage outputs error messages and a Parse Tree.
A simple parse tree
Middle End
Analysis of symbol definitions and use
This stage outputs errors such as variables not being declared. The parse tree is annotated and then passed on..
Type Checking
Type errors are reported here. The annotated parse tree is then passed on again..
Intermediate code generation
Depending on the compiler, intermediate code is now created. It may be optimised using optimisation algorithms, then a targeted assembly language file is outputted.
Back End
The assembly code is then assembled into an object code file, then linked with object code libraries.
Out: Machine code program
Languages
A language is a set of strings; each string is a finite sequence of symbols taken from a finite aplhabet. For parsing, the strings are source programs, the symbols are lexical tokens, and the alphabet is the set of token types returned by the lexical analyzer.
A leftmost derivation is one in which the leftmost nonterminal symbol is always the one expanded; in a rightmost derivation, the rightmost nonterminal is always next to be expanded.
A grammar is ambiguous if it can derive a sentence with two different parse trees.
Grammars whose predictive parsing tables contain no duplicate entries are called LL(1).
Recursive descent, or predictive, parsing works only on grammars where the first terminal symbol of each subexpression provides enough information to choose which production to use.
First(y) is the set of all terminal symbols that can be any string derived from y.
Follow(x) is the set of terminals that can immediately follow x.
When computing first set of (X Y) it x is nullable you also have to take into account Y.
Eg for the grammar:
| Z -> d | Y -> | X->Y |
| Z -> X Y Z | Y -> c | X -> a |
| Nullable | FIRST | FOLLOW | |
| X | yes | A c | A c d |
| Y | yes | c | A c d |
| Z | no | A c d |
Eliminating left recursion:
The two productions
E -> E + T
E -> T
are certain to cause duplicate entries in the LL(1) parsing table, since any token in FIRST(T) will also be in FIRST(E + T). The problem is that E appears as the first right-hand-side symbol in an E production; this is called left recursion. To eliminate left recursion, rewrite using right recursion.
The common way to rewrite is
A -> A a.
A -> b.
|
v
A -> b A'.
A'-> a A'.
A'-> .
To re-write using right recursion
Simliarly we can rewrite
S -> if E then S else S
S -> if E then S
As:
S -> if E then S X
X ->
X -> else S
From old notes
3.1 Type 2 grammar
In the Chomsky type 2 grammar the left hand side of every production is restricted to just a single
non-terminal symbol. Such symbols are often called syntactic categories. Type 2 grammars are known as context-free grammars and have been used frequently in the specification of the syntax of programming languages, most notably Algol 60 where it was first used. The notation is sometime called Backus Naur Form or BNF after two of the designers of Algol 60. A simple example of a type 2 grammar is as follows:
S −> A B
A −>! a
A −>A B b
B −> b c
B −> B a
A slightly more convenient way of writing the above grammar is:
S −> A B
A −> a | A B b
B −> b c | B a
The alphabet for this grammar is {S, A, B, a, b, c, d}. The non-terminals are S, A, B being
the symbols occurring on the left-hand-side of productions, with S being identified as the start
symbol. The terminal symbols are a, b, c, d, these being the characters that only appear on
the right hand side. Sentences that this grammar generates include, for instance:
abc
abcbbc
abcbca
abcbbcaabca
Where the last sentence, for instance, is generated from the sentence symbol by means of the
|
following productions:
A grammar is ambiguous if there are two or more ways of generating the same sentence.
Convince yourself that the follow three grammars are ambiguous:
a) S −> A B
A −> a | a c
B −> b | c b
b) S −> a T b | T T
T −> a b | b a
c) C −> if E then C else C | if E then C
This is the most restrictive of the phrase structured grammars. In it all productions are limited
to being one of the following two forms:
A −> a
A −> a B
That is, the right hand side must consist of a single terminal symbol possibly followed by a single
non-terminal. It is sometimes possible to convert a type 2 grammar into an equivalent type 3
grammar. Try this for the grammar for floating point constants given earlier.
Type 3 grammars can clearly be parsed using a finite state recogniser, and for this reason
they are often called regular grammars.
6.1 Relevant JVM instruction set
The JVM has already been covered in the course "Computer Design". This section can be seen
as a reminder which focuses on particular points relevant to compilation.
In these notes the stack is upwards growing,6 so that subsequent parameters and local variables
occupy increasing memory locations (this is not necessary for the JVM but makes the pictures
easier to understand). The version of the JVM we present has a stack-pointer SP register which
points to the first free location on the stack. In addition, it has a so-called frame-pointer FP
register which points to a constant place during the activation of a procedure. Although strictly
not necessary, this simplifies explanations and aids debuggers, since local variables will remain at
the same constant offset from FP but their offset from SP will vary during pushes and pops to the
stack. Evaluation of a procedure uses a stack frame which will be addressed from FP. Note that
both arguments and local variables are addressed as negative offsets from FP. A stack frame has
the following form:
Here FP points to (or rather into) the current stack frame. FP points to the so-called linkage
information which allows a function call to return. This consists of the previous value of FP, here
called FP0 and a pointer L (the return address) to the machine instruction to be next evaluated
after the function's return. To the left (at lower addresses) of the linkage information are stored
the function's parameters and (user-declared) local variables; on the right is the local stack (used
for evaluating temporaries and for storing arguments), SP is a pointer to the first free cell of this
(which coincides with the first free cell of the whole stack). To clarify explanations of function
call, we will use the word parameters to refer to the identifiers holding arguments to the current
procedure and restrict the word arguments to refer to expressions which are being, or have been,
evaluated on the stack in order to be passed to a further function. At the end of each Java
statement we can expect the local stack to be empty and hence SP to point exactly two words
further along the stack from FP. In general these notes will assume that the JVM stack is an array
of (32-bit) words, and so addresses of stack items will differ by one.
8.2 Dynamic linking
Consider a situation in which a user has many small programs (maybe 50k bytes each in terms of
object files) each of which uses a graphics library which is several megabytes big. The classical idea
of linking (static linking) presented above would lead to each executable file being megabytes big
too. In the end the user's disc space would fill up essentially because multiple copies of library code
rather than because of his/her programs. Another disadvantage of static linking is the following.
Suppose a bug is found in a graphics library. Fixing it in the library (.OBJ) file will only fix it in
my program when I re-link it, so the bug will linger in the system in all programs which have not
been re-linked--possibly for years.
An alternative to static linking is dynamic linking. We create a library which defines stub
procedures for every name in the full library.
9.13 Static and dynamic scoping
This final point is worth a small section on its own; the normal state in modern programming
languages is that free variables are looked up in the environment existing at the time the function
was defined rather than when it is called. This is called static scoping or static binding or even
lexical scoping; the alternative of using the calling environment is called dynamic binding and was
used in many dialects of Lisp. The difference is most easily seen in the following example:
let a = 1;
let f() = a;
let g(a) = f();
print g(2);
Check your understanding of static and dynamic scoping by observing that this prints 1 under the
former and 2 under the latter.
You might be tempted to believe that rebinding a variable like `a' in dynamic scoping is
equivalent to assigning to `a'. This is untrue, since when the scope ends (in the above by g being
exited) the previous binding of `a' (of value one) again becomes visible, whereas assignments are
not undone on procedure exit.
10.1 Evaluation Using a Stack--Static Link Method
We saw in the first part of the notes how the JVM uses a stack to evaluate expressions and function
calls. Essentially, two registers (FP and SP) respectively point to the current stack frame and its
fringe.
Evaluation on a stack is more efficient than in the lambda-interpreter presented above in
that no search happens for variables, they are just extracted from their location. However, the
JVM as defined only provides instructions which can access local variables (i.e. those on the local
stack frame accessed by FP) and static variables (often called global or top-level variables in other
languages) which are allocated once at a fixed location.
Indeed Java forbids the textual nesting of one function within another, so the question of how
to access the local variables of the outer function from within the inner function does not need to
be addressed in the JVM. However, for more general languages we need to address this issue.
The usual answer is to extend the linkage information so that in addition to holding the return
address L and the old frame pointer FP0, also known as the dynamic link as it points to the frame
of its caller, it also holds a pointer S, the static link17 which points to the frame of its definer.
1. x+y*z:
<Exp> => <Exp> + <Term> => <Term> + <Term> => <Factor> + <Term> => x + <Term> => x + <Term> * <Factor> => x + <Factor> * <Factor> => x + y * <Factor> => x + y * z
x+y*z: Full derivation-tree of non-terminals and replacements.
The result of parsing is often returned as a parse-tree based on a simpler abstract syntax. The abstract syntax corresponds to the datatype of parse trees returned by the parser.
x+y*z: Parse tree.
2. (x+y)*z:
Parentheses '(' and ')' can be used to force a different parsing:
(x+y)*z: Full derivation-tree of non-terminals and replacements.
(x+y)*z: Parse tree.
Note that parentheses do not appear in any parse tree. They directed the parser to build a certain tree and after that they are unnecessary. The structure of the tree shows the binding of operators to operands without the need for (). Parentheses are only needed in strings.
· Formal Grammars and Languages:
· Definition of formal grammar (start symbol, terminal symbols, non-terminal symbols, grammar rules). (Also called a context-free grammar or a BNF grammar.)
· Derivation sequences (leftmost and rightmost).
· Language accepted by (or recognized by) a formal grammar.
· Parse trees. (Each derivation sequence determines a unique parse tree, but a parse tree might have many derivations.)
· Ambiguity. (Definition: There is a sentence with more than one parse tree, or with more than one leftmost derivation, or with more than one rightmost derivation.)
· Ambiguity is bad.
· Remove ambiguity by either:
· rewriting the grammar, such as changing
E ----> E + E (AMBIGUOUS)
E ----> E * E
E ----> ( E )
E ----> id
to
E ----> E + T (NOT AMBIGUOUS)
E ----> T
T ----> T * F
T ----> F
F ----> ( E )
F ----> id
· introducing special rules, such as
· Precedence of one operator over another. (Present with + and * in the first example above.)
· Associativity of an operator (left-to right or right-to-left). (Present with both + and * in the first example above.)
· Rule that an else matches then nearest unmatched if. (Present in the following example:
stmt ----> "if" "(" expr ")" stat (AMBIGUOUS)
stmt ----> "if" "(" expr ")" stat "else" stat
· Parsers and the Use of Grammars:
· Recursive Descent Parsers:
· Top-down parser, starts with the start symbol and works down toward the given sentence (string of terminal symbols), constructing a leftmost derivation).
· Must rewrite grammar to avoid left recursion. (There are other possible problems also, beyond the scope of this course.) The simple grammar above would be rewritten:
E ----> T { "+" T } ({} means "zero of more times")
T ----> F { "*" F } (terminals are in quotes or id)
F ----> "(" E ")"
F ----> id
· Write a function corresponding to each non-terminal symbol in the grammar. The code of the function mirrors the right side of the rule.ｄｆｄｆｄ
http://www.cs.ucl.ac.uk/staff/l.capra/teaching/2010/2010-cfg.pdf
Common example:
let rec compose f g =
let rec composed x = g (f x) in
composed in
let rec dbl x = x + x in
let rec inc x = x + 1 in
let rec dec x = x - 1 in
let h = compose inc (compose dbl dec) in
print_int (h 123)
let LABEL(composed) [f, g] x = let TMP1 = APPLY_CLOSURE(f x) in APPLY_CLOSURE(g TMP1) in
let LABEL(compose) [] f g = let cl = (LABEL(composed); [f, g] ) in cl in
let LABEL(dbl) [] x = (x + x) in
let LABEL(inc) [] x = let TMP1 = 1 in (x + TMP1) in
let LABEL(dec) [] x = let TMP1 = 1 in (x - TMP1) in
let closure dbl = ( LABEL(dbl); [] ) in
let closure inc = ( LABEL(inc); [] ) in
let closure dec = ( LABEL(dec); [] ) in
let TMP2 = APPLY_DIRECT(LABEL(compose) dbl dec) in
let h = APPLY_DIRECT(LABEL(compose) inc TMP2) in
let TMP3 = 123 in
let TMP4 = APPLY_CLOSURE(h TMP3) in
APPLY_DIRECT(LABEL(min_caml_print_int) TMP4)
Solutions:
Restrict programming language so the problem goes away! That is, use FORTRAN.
Force programmer to worry about it (use malloc and free in C...)
Automation
Reference Counting
Mark and Sweep
Copy Collection
Generational Collection
... there are other techniques...
Important notes (new)
Slide 1: Compilation as a sequence of transformations
|
● Each transformation preserves semantics
● Each transformation addresses only one aspect of "the gap"
● Each transformation is fairly easy to understand.
Lexical Analysis
● Goal: recognise words and symbols in the source program and group them into tokens
● Token: sequence of characters that forms a unit in the grammar of the programming language
●
 |
Finite state automata to implement lexers that recognise tokens described by regular expressions
 |
Slide 2: The real lexing problem
Regular Expressions
● Language L = set of strings
● String = finite sequence of symbols
● Symbol = taken from a finite alphabet A
● Regular Expression RE describes a set of strings: L(RE)
 |
Slide 3: LL(k) vs. LR(k) reductions
● Top-Down parsing
- Read input Left-to-right and construct a Left-most derivation of the input token stream by subsequently applying the productions in G
- LL(k) grammars
LL(k) grammars
- Left-to-right, Left-most derivation, k-token lookahead - Derivation built forward - Start with the start symbol - End with token stream
To stop left recursion:
 |
PREDICTIVE TOP-DOWN PARSING
Question: can we know at any point what the right
production is?
Predictive parsing: the first terminal symbol(s) of the unparsed input stream provides enough information to choose the next production
LL(k) grammars= Left-to-right scanning, Leftmost derivation, k symbols read
● Bottom-Up parsing
- Read input Left-to-right and construct a Right-most derivation of the input token stream by subsequently applying the productions in G
- LR(k) grammars
Basic idea:
- Use a set of parser states
- Use a stack with alternating symbols and states
- E.g., 1 ( 6 S 10 + 3 ...
- Use a parsing table to:
- Determine which action to apply
- Determine the next state
 |
 |
Slide 4: Jargon Stack Frame
The stack pointer (SP) is a hardware feature of almost all
present-day processors. At a minimum, the SP points to the
present end of a queue which holds return addresses of all
the calls made to the moment. When a call is made, the
return address is pushed onto the stack; upon exiting the
called function, the return address is popped from the stack.
The frame pointer (FP) is an optional programming feature
used by some programming languages on some processors.
Not all processors have the hardware resources to implement
a frame pointer and some implementations don't want to have
the extra overhead of maintaining a frame pointer.
An FP, if used, points to a fixed point in the "user" stack
and points to a location in the stack where the arguments
and local variables for a called function are located. This
pointer is established upon entry to a function and remains
constant throughout the execution of the called function.
Thus, values can be pushed onto the user stack and popped
from it within the function without impacting the offsets
from the FP.
· 
Since a function will often require space for many variables (parameters, local variables, temporaries, etc.) it is more convenient to allocate all of that space at once.
· This means that we should predetermine the maximum amount of space a function will use.
· As long as we've determined that space, we might as well lay out the data in that space.
· The organization of local data for the invocation of a function is typically called a stack frame.
· A frame pointer indicates the beginning of the frame.
· Why have both frame pointer and stack pointer? At times, you need to keep track of other frames.
· What goes in a frame (or in accompanying registers)?
· Any local variables
· Parameters (subject to the caveats below)
· The return address (what statement to branch to when the method exits)
· Any temporaries
· Saved registers
· Space for the return value
· Other things ...
Slide 5: Closure conversion (similar to lambda lifting)
 |
Another gap still remaining between MinCaml and assembly is "nested function definitions," which are flattened by closure conversion. It is one of the most important processes when compiling functional languages.
This flattening of nested function definitions includes easy cases and hard cases. For example,
let rec quad x =
let rec dbl x = x + x in
dbl (dbl x) in
quad 123
can be flattened like
let rec dbl x = x + x in
let rec quad x = dbl (dbl x) in
quad 123
just by moving the function definition. However, a similar manipulation would convert
let rec make_adder x =
let rec adder y = x + y in
adder in
(make_adder 3) 7
into a nonsensical program
let rec adder y = x + y in
let rec make_adder x = adder in
(make_adder 3) 7.
This is because function dbl has no free variable while adder has a free variable x.
Thus, in order to flatten function definitions with free variables, we have to treat not only the bodies of functions like adder, but also the values of their free variables like x together. It is like
let rec adder x y = x + y in
let rec make_adder x = (adder, x) in
let (f, fv) = make_adder 3 in
f fv 7
in ML-style pseudo code. First, function adder takes the value of free variable x as an argument. Then, when the function adder is returned as a value, its body is paired with the value of its free variable, like (adder, x). This pair is called a function closure. When the function adder is called, its body f and the value fv of its free variable are extracted and supplied as arguments.
Closure conversion gets complicated when it comes to "which functions need closures and which functions can be called in ordinary ways." The simplest solution is to generate closures for all functions, but it is too inefficient.
Thus, the closure conversion Closure.g of MinCaml takes the set known of functions that are "known to have no free variables and can be called in ordinary ways," and closure-converts an expression. (It also takes type environment env in addition to the expression and known.)
http://cs.wellesley.edu/~cs251/spring05/closure-conversion.pdf
Slide 6: Solutions to Garbage collection
Every modern programming language allows programmers to allocate new storage dynamically
New records, arrays, tuples, objects, closures, etc.
Every modern language needs facilities for reclaiming and recycling the storage used by programs
COST: It's usually the most complex aspect of the run-time system for any modern language (Java, ML, Lisp, Scheme, Modula, ...)
Explicit MM:
User library manages memory; programmer decides when and where to allocate and deallocate
void* malloc(long n)
void free(void *addr)
Library calls OS for more pages when necessary
Advantage: people are clever
Disadvantage: people too clever and make mistakes. Getting it right can be costly. And don't we want to automate-away tedium? Advantage: Allows us to implement Garbage Collection!
Reference counting:
Keep track of the number of pointers to each object (the reference count).
When Object is created, set count to 1.
Every time a new pointer to the object is created, increment the count.
Every time an existing pointer to an object is destroyed, decrement the count
When the reference count goes to 0, the object is unreachable garbage
Cons
Space/time overhead to maintain count.
Memory leakage when cycles in data (wont detect cycles)
Pros
Incremental (no long pauses to collect...)
Has many useful applications
UNIX File System - Symbolic Links
Java's RMI management of Strings
Pure Functional Languages
Mark and sweep:
A two-phase algorithm
Mark phase: Depth first traversal of object graph from the roots to mark live data
Sweep phase: iterate over entire heap, adding the unmarked data back onto the free list
Cost of mark phase:
O(R) where R is the # of reachable words
Assume cost is c1 * R (c1 may be 10 instr's)
Cost of sweep phase:
O(H) where H is the # of words in entire heap
Assume cost is c2 * H (c2 may be 3 instr's)
Copying collection:
Basic idea: use 2 heaps
One used by program
The other unused until GC time
GC:
Start at the roots & traverse the reachable data
Copy reachable data from the active heap (from-space) to the other heap (to-space)
Dead objects are left behind in from space
Heaps switch roles
Pros
Simple & collects cycles
Run-time proportional to # live objects
Automatic compaction eliminates fragmentation
Cons
Precise type information required (pointer or not)
Tag bits take extra space; normally use header word
Twice as much memory used as program requires
Usually, we anticipate live data will only be a small fragment of store
Allocate until 70% full
From-space = 70% heap; to-space = 30%
Long GC pauses = bad for interactive, real-time apps
Objects that have survived a long time are likely to survive longer (most objects die young) so use generational gc for more efficiency.
Slide 7: Dynamic Dispatch
 |
In computer science, dynamic dispatch is the process of mapping a message to a specific sequence of code (method) at runtime. This is done to support the cases where the appropriate method cannot be determined at compile-time (i.e. statically). Dynamic dispatch is only used for code invocation and not for other binding processes (such as for global variables) and the name is normally only used to describe a language feature where a runtime decision is required to determine which code to invoke.
Normally in a typed language the dispatch mechanism will be performed based on the type of the arguments (most commonly based on the type of the receiver of a message). This might be dubbed 'per type dynamic dispatch'. Languages with weak or no typing systems often carry a dispatch table as part of the object data for each object. This allows instance behaviour as each instance may map a given message to a separate method.
Every class has a fixed set of methods (including inherited methods)
● A dispatch table indexes these methods
● dispatch table = an array of method entry points
● A method f lives at a fixed offset in the dispatch table for a class and all of its subclasses
Example:
 |
The dispatch pointer in an object of class X points to the dispatch table for class X.
Every method f of class X is assigned an offset Of in the dispatch table at compile time.
To implement a dynamic dispatch e.f() we
● Evaluate e. The result is a pointer to an object x
● Call D[Of]
● D is the dispatch table for x
● In the call, this is bound to x
Slide 8: Bytecode interpreter
Databases
Aims
The overall aim of the course is to cover the fundamentals of database management systems (DBMSs), paying particular attention to relational database systems. The course covers modelling techniques, transferring designs to actual database implementations, SQL, models of query languages, transactions as well as more recent developments, including data warehouses and On-line Analytical Processing (OLAP), and use of XML as a data exchange language. The lectures will make use of the open source DBMS, MySQL.
Lectures
· Introduction: What is a database system?
· Entity-relationship modelling.
· The relational data model.
· Relational algebra.
· Relational calculus.
· SQL and integrity constraints.
· Schema refinement: functional dependencies.
· Schema refinement: normalisation.
· Further relational algebra, SQL.
· Transaction management overview.
· On-line Analytical Processing (OLAP).
· XML as a data exchange format.
Objectives
At the end of the course students should
· be able to design entity-relationship diagrams to represent simple database application scenarios
· know how to convert entity-relationship diagrams to relational database schemas in the standard Normal Forms
· be able to program simple database applications in SQL
· understand the basic theory of the relational model and both its strengths and weaknesses
· be familiar with various recent trends in the database area
Recommended reading
* Date, C.J. (2000). An introduction to database systems. Addison-Wesley (7th ed.).
Elmasri, R. & Navathe, S.B. (2000). Fundamentals of database systems. Addison-Wesley (3rd ed.).
Silberschatz, A., Korth, H.F. & Sudarshan, S. (2002). Database system concepts. McGraw-Hill (4th ed.).
Ullman, J. & Widom, J. (1997). A first course in database systems. Prentice Hall.
Miszczyk, J. and others (1998). Mastering Data Warehousing Functions. (IBM Redbook DB2/400) Chapters 1 & 2 only. http://www.redbooks.ibm.com/abstracts/sg245184.html
Garcia-Molina, H. Data Warehousing and OLAP. Stanford University. http://www.cs.uh.edu/ ceick/6340/dw-olap.ppt
London Metropolitan University, Department of Computing. Data Warehousing and OLAP Technology for Data Mining. http://learning.unl.ac.uk/csp002n/CSP002N_wk2.ppt
An entity is a real world object that is distinguishable from other objects. Entity types are drawn as rectangles:
Attributes of entity types are drawn as ovals, and attached to the entity sets with lines eg;
Note that NI is underlined as it is a key attribute.
A relationship type among two or more entity types defines a set of associations between entities from those types. They are represented by diamonds.
Relationships can also have attributes, represented by ovals:
● Selection
Selecting a subset of rows.
Selects rows that satisfy a condition, written
R1 = σc(R2)
where c ks a condition involving the attributes of R2, e.g.
σrating>8(S2)
Returns all rows form S2 with more than 8 in the rating column
● Projection
Deletes fields that are not in the projection list
● 
where A is a list of attributes from the scheme of R2
For example, 
returns the columns ID and name of a table.
● Renaming
Renaming attributes
Returns a relation instance identical to R2 except that field A is renamed B
● Set theoretic operations
Union, intersection, difference
However the input to these operators must be union compatible (same number of fields, same field names and domains)
● Products and joins
Combining relations in useful ways
The Cartesian product AxB concatenates every row of A with every row of B
An Equijoin of the two relations R and S over all common attributes x. One occurrence of each common attribute is eliminated from the result.
A theta join
Defines a relation that contains tuples satisfying the predicate F from the Cartesian product of R and S.
The predicate F is of the form R.ai θ S.bi where θ may be one of the comparison operators (<, ≤, >, ≥, =, ≠).
An equi-join is a theta join with = as the F predicate.
First normal form requires that you eliminate duplicative columns from the same table and create separate tables for each group of related data and identify each row with a unique column (the primary key). 1NF prevents repeating groups.
To be in second normal form, as well as fulling 1NF, each nonkey attribute in the relation must be functionally dependent upon the primary key.
A 2NF table is in 3NF if and only if it does not feature any non-trivial functional dependencies between non-prime attributes. A non-prime attribute is one that does not belong to any candidate key.
A relation R is said to be in BCNF if whenever X -> A holds in R, and A is not in X, then X is a candidate key for R.
A full outer join combines the results of both left and right outer joins. The joined table will contain all records from both tables, and fill in NULLs for missing matches on either side.
Outer joins do not require that each record in the two joined tables has a matching record in the other table. Normally a tuple that doesn't join with any from the other relation is removed from the result, but with outer joins we "pad out" the result with nulls.
For example with a full outer join:
Let R=
| A | B |
| 1 | 2 |
| 3 | 4 |
Let S=
| B | C |
| 4 | 5 |
| 6 | 7 |
Then R |><| S =
| A | B | C |
| 3 | 4 | 5 |
But º|><|º=
| A | B | C |
| 1 | 2 | NULL |
| 3 | 4 | 5 |
| NULL | 6 | 7 |
(ii ) the aggregate and grouping operator. [5 marks]
Aggregation allows us to summarise a column. eg SUM, AVG, COUNT, MIN and MAX.
For example
SELECT AVG(T.MaxSpeed)
FROM TRAIN T
STATION S
WHERE S.Owner ="Wagn"
GROUP BY was added to SQL because aggregate functions (like SUM) return the aggregate of all column values every time they are called, and without the GROUP BY function it was impossible to find the sum for each individual group of column values.
GROUP BY Example (Copied from W3Schools.com)
This "Sales" Table:
| Company | Amount |
| W3Schools | 5500 |
| IBM | 4500 |
| W3Schools | 7100 |
And This SQL:
| SELECT Company, SUM(Amount) FROM Sales |
Returns this result:
| Company | SUM(Amount) |
| W3Schools | 17100 |
| IBM | 17100 |
| W3Schools | 17100 |
The above code is invalid because the column returned is not part of an aggregate. A GROUP BY clause will solve this problem:
| SELECT Company,SUM(Amount) FROM Sales
GROUP BY Company |
Returns this result:
| Company | SUM(Amount) |
| W3Schools | 12600 |
| IBM | 4500 |
Important Slides
Lecture 7
A functional dependency X-> Y is simply a pair of sets
We shall say that an FD set F logically implies X->Y and write F├ X-> Y
The closure of F is the set of all FDs logically implied by F.
X is a candidate key if it implies all the columns in the closure of F, and there is no subset of X that also implies all the columns in the closure of F.
Armstrong's Axioms
Reflexivity: If Y⊆X then F ╠ X->Y
(This is called a trivial dependency
Example: sname,address->address
Augmentation: If F ╠ X->Y then X,W -> Y,W
Example: As cid->cname, then cid, sid->cname,sid
Transivity: If F ╠ X->Y and F ╠ Z->Y then F ╠ X->Z
Example: As sid, cid->cid and cid->cname, then sid,cid->cname.
Consequences of Armstrong's Axioms:
Union: If ╠ X->Y and ╠ X-Z then ╠ X-Y,Z
Pseudo-transitivity: If ╠ X->Y and ╠ W,Y->Z then ╠ X,W->Z
Decomposition: If ╠ X->Y and Z⊆Y then F ╠ X->Z
Proof of union rule:
Suppose that F╠ X->Y and F╠ X->Z
By augmentation we have
F╠ X->X,Y
since X U X = X. Also by augmentation F╠ X,Y -> Z,Y
Therefore, by transitivity we have
F╠ X -> Z,Y
Why Armstrong's axioms?
Soundness
If F╠ X->Y is deduced using the rules, then X->Y is true in any relation in which the dependencies of F are true.
Completeness
If X,Y is true in any relation in which the dependencies of F are true, then F ╠ X->Y can be deduced using the fules.
Soundness:
Augmentation rule:
We have X-> Y, ie if t1. X = t2.X then t1.Y=t2Y
If in addition t1.W=t2.W then it is clear that t1.(Y,W) = t2(Y,W)
Transitivity rule:
We have X->Y ie if t1.X=t2.X then t1.Y=t2.Y *
We have Y->Z ie if t1 Y = t2 Y then tZ = t2Z **
Take two tuples s1 and s2 such that s1.X = s2.X then from * s1.Y = s2.Y and then from ** s1Z = s2 Z
 |
Economics
Lecturers: Professor R.J. Anderson and Mr N.D.F. Bohm
No. of lectures: 8
Professional Practice and Ethics (Part IA) provides a useful foundation for this course.
This course is a prerequisite for Security (Part II) and is desirable for the Part II courses Business Studies, and E-Commerce.
Aims
This course aims to give students an introduction to some basic concepts in economics and law.
Lectures
· Game theory. The choice between cooperation and conflict. Prisoners' Dilemma; Nash equilibrium; hawk-dove; iterated games; evolution of strategies; application to biology and computer science.
· Classical economics. Brief history of economics. Definitions: preference, utility, choice and budget. Pareto efficiency; the discriminating monopolist. Welfare and the Arrow theorem.
· Classical economics continued. Supply and demand; elasticity; utility; the marginalist revolution; competitive equilibrium. Trade; monopoly rents; public goods; oligopoly. The implications for innovation.
· Asymmetric information. The market for lemons; adverse selection; moral hazard; signalling; brands; transaction costs; theory of the firm.
· Auctions. English auctions; Dutch auctions; all-pay auctions; Vickrey auctions. The winner's curse. The revenue equivalence theorem. Mechanism design and the combinatorial auction. Problems with real auctions. Applicability of auction mechanisms in computer science.
· Principles of law. Contract and tort; copyright and patent; binding actions; liabilities and remedies; competition law; choice of law and jurisdiction.
· Law and the Internet. EU directives including distance selling, electronic commerce, data protection, electronic signatures and copyright; their UK implementation. UK laws, including RIP.
· Network economics. Real and virtual networks, supply-side versus demand-side scale economies, Metcalfe's law, the dominant firm model, price discrimination. Regulatory and other public policy issues of information goods and services markets.
Objectives
At the end of the course students should have a basic appreciation of economic and legal terminology and arguments. They should understand some of the applications of economic models to systems engineering and their interest to theoretical computer science. They should also understand the main constraints that markets and legislation place on firms dealing in information goods and services.
Recommended reading
* Shapiro, C. & Varian, H. (1998). Information rules. Harvard Business School Press.
Varian, H. (1999). Intermediate microeconomics - a modern approach. Norton.
A dominant strategy is an optimal choice regardless of what others choose to do. There is a dominant strategy equilibrium when all players continuously make the same choice, regardless of other players actions, as it is in their interests.
In Nash equilibrium each players optimal strategy depends on what they think the other will do.
We say that two strategies are in Nash equilibrium when one players choice is optimal given the others strategy.
With an ascending auction, the last person wins at the price at which the second-last dropped out.
With a sealed-bid second price auction the strategy is the same (in this case, you should bid truthfully).
A Dutch auction is a type of auction where the auctioneer begins with a high asking price which is lowered until some participant is willing to accept the auctioneer's price, or a predetermined reserve price (the seller's minimum acceptable price) is reached. The winning participant pays the last announced price. A sealed first-price auction is a form of auction where bidders submit one bid in a concealed fashion. The submitted bids are then compared and the person with the highest bid wins the award, and pays the amount of his bid to the seller. The two are strategically equivalent (you may reduce your bid if you think your valuation is much higher than everyone else's).
Revenue equivalence is a weaker concept, not "who will win" but how much money on average".
Assume each of a given number of risk neutral potential buyers has a privately-known valuation independently drawn from a strictly-increasing atomless distribution, and that no buyer wants more than one of the k identical indivisible prizes.
Then any mechanism in which
·the prizes always go to the k buyers with the highest valuations and
·any bidder with the lowest feasible valuation expects zero surplus, yields the same expected revenue (and results in each bidder making the same expected payment as a function of her valuation)
ie they all pay the lowest feasible (accepted) price.
Under the assumptions of the revenue equivalence theorem the expected revenue from an auction equals the expected marginal revenue of the winning bidders.
A question commonly addressed in the economic analysis of auctions is whether any two auction mechanisms are "revenue equivalent". Two auctions are said to be "revenue equivalent" if they result in the same expected sales price.
The revenue equivalence theorem states that,if all bidders are risk-neutral bidder and have independent private value for the auctioned items, then all four of the standard single unit auctions have the same expected sales price (or seller's revenue).The four standard single unit auctions are the English auction, the Dutch auction,first-price sealed-bid auction,and the second-price sealed-bid auction.
RET Fails if:
● If the bidders aren't risk neutral
Risk neutral is used to describe an individual who cares only about the expected return of an investment, and not the risk (variance of outcomes or the potential gains or losses). Risk neutral is in between risk aversion and risk seeking. The value that a risk-neutral individual assigns to a financial instrument is equal to the value of the instrument in each scenario, weighted by the probability of each scenario (in other words, it is equal to the expected value). A more mathematically advanced definition is "A risk neutral world is one where investors are assumed to require no extra return on average for bearing risks".
Risk averse bidders: If you'd rather have a certain profit of 1 than a 50% chance of 2, RET fails.
If a bidder on eBay is risk averse, they may bid over the odds to make sure they receive their item. If the bidder is risk seeking, they may bid lower than they believe the item is worth to try and get a bargain.
● Predation
If a company makes it very clear from the outset that they will crush any other bids, then few potential bidders will actually attempt to outbid that company, breaking the RET.
For example, before bidding for the California phone license, Pacific Telephone announced in the Wall Street Journal that "if somebody takes California away fromus, they'll never make any money" (Cauley and Carnevale, 1994, p.A4). Pacific Telephone also hired one of the world's most prominent auction theorists to give seminars to the rest of the industry to explain the winner's curse argument (that the winner of an auction is often the one who most overestimated the value) that justifies this statement, and reinforced the point in full page ads that in ran in the newspapers of the cities where their major competitors were headquartered (Koselka, 1995, p. 63). It also made organizational changes that demonstrated its commitment to winning the Los Angeles license (Klemperer).
If I leave a message on an eBay item saying "By the way, I've bid five thousand pounds for this Simpsons Dvd" then other bidders are unlikely to take me on... although the owner may bid themselves to try and push the price up.
● Collusion
There are numerous examples of companies joining forces to cheat bidding rules. For example,
in the November2000 Swiss sale of four third-generation mobile-phone licenses, there was considerable initial interest from potential bidders. But weaker bidders were put off by an auction form that gave an obvious advantage to stronger bidders.
Moreover, the government permitted last-minute joint-bidding agreements-essentially officially-sanctioned collusion. In the week before the auction, the field shrank from nine bidders to just four bidders for the four licenses! Since no bidder was allowed to take more than one license, the sale price was determined by the reserve price which was just one-thirtieth of the U.K. and German per capita revenues, and one-fiftieth of what the Swiss had once hoped for.
If there are two Simpson Dvd's for sale on eBay and I notice one other person bidding for the first, I could send them a message saying "If you don't bid against me when I buy the next one I won't bid against you when you buy the first one".
The Economics of Law and Security, Ross Anderson
● Systems are particularly prone to failure when the person guarding them is not the person who suffers when they fail.
● Network insecurity is somewhat like air pollution or traffic congestion, in that people who connect insecure machines to the Internet do not bear the full consequences of their actions.
● Insecure software dominates the market for the simple reason that most users cannot distinguish it from secure software; thus, developers are not compensated for costly efforts to strengthen their code.
● Insuring against attacks could also provide metrics by building a pool of data for valuing risks.
● Lots more ATM fraud in UK than US as responsibility is with customer
● People won't pay to stop trojans that DOS microsoft
● Legal theorists have long known that liability should be assigned to the party that can best manage the risk. Yet medical records systems are bought by hospital directors and insurance companies, whose interests in account management, cost control, and research are not well aligned with the patients' interests in privacy.
● Old P2P required users to serve a random selection of files from across the network (and so protect other users against censorship), more popular systems instead allow peer nodes to serve content they have down-loaded for their personal use, without burdening them with others' files.
● Consider a medieval city. If the main threat is a siege, and each family is responsible for maintaining and guarding one stretch of the wall, then the city's security will depend on the efforts of the laziest and most cowardly family. If, however, disputes are settled by single combat between champions, then its security depends on the strength and courage of its most valiant knight. But if wars are a matter of attrition, then it is the sum of all the citizens' efforts that matters. System reliability is no different; it can depend on the sum of individual efforts, the minimum effort anyone makes, or the maximum effort anyone makes.
● In the minimum-effort case, the agent with the lowest benefit-cost ratio dominates. As more agents are added, systems become increasingly reliable in the total-effort case but increasingly unreliable in the weakest-link case.
● Two security protocols that have already been widely deployed, SSH and IPsec, both overcame the bootstrapping problem by providing adopting firms with internal benefits. Thus, adoption could be done one firm at a time, rather than needing most organizations to move at once.
● vulnerability disclosure can improve system security over the long term.
● In many markets, the attitude of `ship it Tuesday and get it right by version 3' is perfectly rational behavior. Consumers generally reward vendors for adding features, for being first to market, or for being dominant in an existing market
● Insurance companies must charge higher premiums, so cyber-insurance markets lack the volume and liquidity to become efficient.
● Technology is increasing both the incentives and the opportunities for discriminatory pricing.
● the stock price of companies reporting a security breach is more likely to fall if the breach leaked confidential information.
Experiences Applying Game Theory to System Design
Ratul Mahajan Maya Rodrig David Wetherall John Zahorjan
University of Washington
● We applied techniques from game theory to help formulate and analyze solutions to two systems problems: discouraging selfishness in multi-hop wireless networks and enabling cooperation among ISPs in the Internet. It proved difficult to do so.
● First, it should be very hard, if not impossible, for a node to cheat without incurring a significant penalty. Second, the more egregious the cheating, the faster the node should suffer its consequences.
● ISPs are competing, autonomous entities, but they must cooperate by delivering packets to each other so that the packets are able to reach their ultimate destinations. Currently, ISPs make unilateral decisions about routing, including which peering1 link is used to send a packet to the downstream ISP. Unsurprisingly, the ISPs' routing decisions are driven by self-interest, and often do not take global consequences into account. For example, a prevalent policy is "early exit," where the upstream ISP routes a packet through the peering link that is nearest to the packet's source, even though this may lengthen the full path the packet must take relative to other available choices.
● Instead we rely on the fear of getting caught and social pressure to deter ISPs from cheating (by being dishonest about their utilities).
● The first incentive technique we considered was based on barter. A node would forward a packet for another node only if that node returned the favor by forwarding for the first node. Such a scheme is attractive because of its simplicity and low implementation cost compared to that of virtual currency
● These observations prompted us to modify our goal from inducing cooperative behavior to preserving cooperative behavior. That is, we wanted to design a system that stays cooperative if it starts with cooperative nodes. Cooperative nodes forwards all the packets they receive for forwarding.
● Like any modeling tool, game theory involves abstraction. Part of its power is that a set of cleanly defined concepts can be used to reason about complicated systems, reaching conclusions that might otherwise be obscured by the details.We encountered several difficulties translating from the abstract solutions to real implementations.
● We believe that game theoretic formulations targeted at mostly cooperative settings would be useful for many other applications such as peer-to-peer systems. Properly quantifying the desire to cooperate is challenging, though, and depends on the problem domain. But if achieved successfully, we believe that it will make game theoretic analyses applicable to a larger class of systems problems. From a systems perspective, the benefits of giving up the notion of perfect selfishness in problems that involve interacting, autonomous agents is analogous to the benefits of relaxing the notion of perfect availability when building distributed systems. In both cases, a slight relaxation of the requirement can result in dramatically lowered implementation costs.
fastcompany.com
● we assembled a panel of 30 respected game theorists around the world, and we sent them a survey asking, "Can you think of any examples of real, live companies that have consciously applied game-theoretical concepts to a real business problem?" The response was . . . a deafening chorus of head scratching. "The short answer is, I don't know," said David Levine of UCLA. "Let me think about this," replied MIT's Muhamet Yildiz. Others on our expert panel, while not offering up any actual, you know, examples, were willing to speculate on why they couldn't. Traditional game theory "prescribes a lot of advice that does not actually seem to work," admitted Paul Bartha of the University of British Columbia. Why not? Maybe because "the sorts of situations that would allow the application of formal methods are so simple that people can understand them without much help," suggested the University of Minnesota's Andy McLennan.
Why Every Economist Should Learn Some Auction Theory
Revenue Equivalence Theorem (RET)
Assume each of a given number of risk neutral potneital buyers has a privately-known valuation independently drawn from a strictly-increasing atomless distribution, and that no buyer wants more than one of the k identical indivisible prizes.
Then any mechanism in which
·the prizes always go to the k buyers with the highest valuations and
·any bidder with the lowest feasible valuation expects zero surplus, yields the same expected revenue (and results in each bidder making the same expected payment as a function of her valuation)
ie they all pay the lowest feasible (accepted) price.
Under the assumptions of the revenue equivalence theorem the expected revenue from an auction equals the expected marginal revenue of the winning bidders.
A question commonly addressed in the economic analysis of auctions is whether any two auction mechanisms are "revenue equivalent". Two auctions are said to be "revenue equivalent" if they result in the same expected sales price.
The revenue equivalence theorem states that,if all bidders are risk-neutral bidder and have independent private value for the auctioned items, then all four of the standard single unit auctions have the same expected sales price (or seller's revenue).The four standard single unit auctions are the English auction, the Dutch auction,first-price sealed-bid auction,and the second-price sealed-bid auction.
Internet may make price worse for consumers
+ Although the internet reduces consumers search costs, and and cuts costs by reducing the fixed costs of dealerships
- Transparent internet prices are readily observable by a firms competitors so lead, in effect, to an ascending auction; a firm knows if its prices are being beaten and will rapidly respon to a competitors price if it wishes. Ie they can collude. On the other hand, shopping to buy a car from a dealer is liked producring in a "sealed-bid" auction, where competitors are unaware of each others offers.
Sealed bid auctions encourage weaker competitors to give it a go, as they have more of a chance of winning than in ascending auctions.
Klemeprers anglo-dutch acution, used for fourth gneration mobile bands:
Everyone bids in increasing amounts (the english stage)
then when there are 5 left, enter 5 sealed bid. 4 pay the fourth highest amount (dutch stage)
An auctions expected revenue equlas the winning bidders expected marginal revenue.
In an ascending bid auction it is better to get more bidders than it is to try and convince few bidders.
A perfectly-competitive industry with fixed capacity K and Q consumers would gain less by fully certelisting the industry (and charging the monopoly price) than it would gain by attracting K new potential customers into the industry with no change in the intensity of competition, assuming (a') the K new potential consumers have teh same distribution of valuations as the xisting consumers, (b') all consumers valuations for the product exceed sellers supply cvosts (up to sellers capacity) and (c') the marginal-revenue curve constructed from the market-demand curve is downward sloping.
The "Bertrand Paradox" that states that with just two firms with constant and equal marginal costs in a homogeneous-products industry the unique equilibrium is for both firms to set price equal to marginal cost and firms earn zero profit.
Young smokers are important to tobacco companies as only 10% of smokers switch/year -brand loyalty.
Buisiness-buisiness autoparts auctions through GM+Ford account for $250 million of trade.
Glossary
Marginal cost- The total cost divided by the quantity.
A bad is a physical object that lowers a consumer's level of happiness, or stated alternately, a bad is an object whose consumption or presence lowers the utility of the consumer.
Risk neutral is used to describe an individual who cares only about the expected return of an investment, and not the risk (variance of outcomes or the potential gains or losses). Risk neutral is in between risk aversion and risk seeking. The value that a risk-neutral individual assigns to a financial instrument is equal to the value of the instrument in each scenario, weighted by the probability of each scenario (in other words, it is equal to the expected value). A far more mathematically advanced definition is "A risk neutral world is one where investors are assumed to require no extra return on average for bearing risks".
Risk averse bidders: If you'd rather have a certain profit of 1 than a 50% chance of 2, RET fails.
Software patents - Obstacles to software development
Richard Stallman
Software patents don't cover individual programs, they cover ideas.
-But richard, isn't that the whole point of a patent?
Inellectual property sums up a number of entirely different ideas into one.
Copyrights dont cover ideas (they cover the expression of a work), parents do.
Copyrights can last as long as 150 years. Patents only last 20 years.
Patents cover ideas even if you come up with them individually.
During the 18 months a patent may take to process application is secret. Eg in 1984 the compress program was written, then in 1985 a patent for LZW compression was released.
Patents are unclear and may use unusual terminology so you might not find the required patents when you write.
The Australian government studied the patent system in the 1980's, it concluded that aside from international pressure there was no reason to have a patent system.
There are three ways of dealing with a patent:
1). Avoid the patent
Eg; the authors of XyWrite downgraded their software to take out the facility to pre-define abbreviations.
BT holds a patent on using hyperlinks with dial up access, public key encryption was protected until 1997.
2). Licensing the patent
They can refuse, or charge alot.
If you are a big company you can trade patents, avoiding the problem of the patenting system.
"The patent system is like a lottery" - The Economist
If you are a small vendor and you threaten them with a patent, they will just claim your patent infringes their patents. Suckers.
Some companies exist just to sue people over patents.
Patents with pharmaceuticals cover just the chemical.
The complexity of software outranks that of eg car parts considerably, so a company has to be rich (and able to deal with patents) to build a 100,000 piece car but doesn't have to be to deal with a 100,000 piece of software.
Introduction to Security
Aims
This course is a broad introduction to both computer security and cryptography. It covers important basic concepts and techniques.
Lectures
· Cryptography. Introduction, terminology, classic ciphers, pseudo-random functions and permutations, computational security, secure hash functions, birthday problem, block ciphers, modes of operation, message authentication codes, applications of hash functions, random number generation. [2 lectures]
· Asymmetric cryptography. Key management problem, signatures and certificates, number theory revisited, discrete logarithm problem, Diffie-Hellman key exchange, ElGamal encryption and signature, hybrid cryptography.
· Authentication techniques. Passwords, one-way and challenge-response protocols, Needham-Schroeder, protocol failure examples, hardware tokens.
· Access control. Discretionary access control in POSIX and Windows, elevated rights and setuid bits, capabilities, mandatory access control, Clark/Wilson integrity.
· Operating system and network security. OS security functions, trusted computing base, malicious software, common implementation vulnerabilities, TCP/IP vulnerabilities and firewalls, security evaluation methodology and standards. [2 lectures]
· Security policies and management. Application-specific security requirements, targets and policies, security management, BS 7799.
Objectives
By the end of the course students should
· appreciate the range of meanings that ``security'' has across different applications
· be familiar with the most common security terms and concepts
· have a basic understanding of the most commonly used attack techniques and protection mechanisms
· have gained basic insight into aspects of modern cryptography and its applications
Recommended reading
* Gollmann, D. (2006). Computer Security. Wiley.
Stinson, D. (2002). Cryptography: theory and practice. Chapman & Hall/CRC (2nd ed.).
Further reading:
Anderson, R. (2001). Security engineering: a guide to building dependable distributed systems. Wiley.
Schneier, B. (1995). Applied cryptography: protocols, algorithms, and source code in C. Wiley (2nd ed.).
Cheswick, W.R., Bellovin, S.M. & Rubin, A.D. (2003). Firewalls and Internet security: repelling the wily hacker. Addison-Wesley (2nd ed.).
Garfinkel, S., Spafford, G. & Schwartz, A. (2003). Practical Unix and Internet security. O'Reilly (3nd ed.).
Unconditional security: Not enough information to decide whether one plain text possibility is more likely than another.
Electronic code book: Split into n-bit blocks, apply cipher function to each individually. Its crap.
 |
CBC: Use output of each block as part of input for next block O(the first input is random data)
MAC is like CBC put the block each time isn't outputted-you just get the final output (and the first input is plaint text). It is useful as a secure checksum.
A Fesitel cypher is a block cypher structure that includes muliple rounds of encryption.
The basic operation is as follows:
Split the plaintext block into two equal pieces, (L0, R0)
For each round 
, compute
Li = Ri − 1
where f is the round function and Ki is the sub-key.
Then the ciphertext is (Ln, Rn).
Decryption is accomplished via
Ri − 1 = Li
One advantage of this model is that the round function f used does not have to be invertible, and can be very complex.
This diagram illustrates both encryption and decryption. Note the reversal of the subkey order for decryption; this is the only difference between encryption and decryption:
In cryptography, a pseudorandom permutation, abbreviated PRP, is an idealized block cipher. It means the cipher that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on blocks of that size) with less computational effort than specified by the cipher's security parameters (this usually means the effort required should be about the same as a brute force search through the cipher's key space).
Three rounds are required. After one, the left half appears unmodified. After two, a single bit change in the right half of P causes just a single bit-change in the right half of C.
Diffie-Hellman key exchange
● Alice and Bob both select a suitably large prime number p, a base g (greater than 1, less than p-1), and each a random integer (from 1 to p-2) x and y respectively
● Alice sends Bob ga mod p
● Bob sends Alice ga mod p
● Both can form (gx)y = (gy)x from
Alice computes (gb mod p)a mod p
Bob computes (ga mod p)b mod p
And can now use a hash of (gy)x as a key.
ElGamal Encryption
In practice, rather than encrypting a whole message with this key, it will be used to encrypt a different key for decrypting the rest of the message with a good efficient block cipher.
ElGamal signature
If A has published (p,g,gx) as her public key and kept x as her private key, then in order to sign a message M she generates a random number y and solves the linear equation
x . gy + y . s = M (mod p) (1)
for s and sends to the verifier B the signed message
A -> B: M, gymod p, s = (M - x . g y)/y mos p
who will raise g to the power of both sides of (1) and test the resulting equation
(gx)gy . (gy)s = gM (mod p)
Public-key infrastructure
Public key encryption and signature algorithms allow the establishment of confidential and authenticated communication links with the owners of public/private key pairs.
In the absence of a personal exchange of keys, this can be mediated via a trusted third party. Such a certification authority C issues a digitally signed public key certificate
CertC(A) = { A, KA, T, L} KC-1
in which C confirms that the public key KA gelongs to A starting at time T and that this confirmation is valid for the time interval L, andall this is digitally signed with C's private signing key KC-1
Anyone who knows C's public key KC from a trustworthy source can use it o verify the certificate CertC(A) and obtain a trustworthy copy of A's key KA this way
We can use the operator o to describe the extraction of A's public key KA from a certificate CertC(A) with the certification authority publickey KC:
KC o CertC(A) = { KA if certificate valid, failure otherwise }
Identification and entity authentication
Humans can be identified by something they are (dna), something they do (signature), something they have (id card), something they know (password) where they are (GPS).
Some techniques to ensure security involve CTRL+ALT+DEL to close any GUI applications when logging in, passwords are stored hashed, don't use dictionary passwords, ensure minimum length and randomly generate.
Authentication Protocols
Alica and Bob share a secret Kab
Password:
B -> A Kab
Problems: Eavesdropper can capture secret and replat it. A can't confirm identity of B.
Simple challenge response:
A-> B N
B-> A h(Kab|N)
Mutual Challenge Response:
A->B Na
B->A {Na,Nk}K ab
A->B Nb
One time password:
B->A C,{C}K ab
A counter increases by one with each transmission, commonly used with car-keys to prevent replay.
Key generating key:
Each smart card Ai contains its serial number i and its card key Ki = {i}K. The master key K (key generating key) is only stored in the verifiation device B. Example with simple challenge response:
Ai -> B i
B ->Ai N
Ai -> B h(Ki|N)
Kerberos
User A and server B do'nt share a secret key initially, but authentication server S shares secret
Authentication protocol attack
Remember simple mutual authentication:
A-> B Na
B -> A {Na, Nb} Kab
A -> B Nb
Impersonation of B by B', who intercepts all messages to B and starts a new session to A simultaneously to have A decrypt her own challenge.
A->B': Na
B'->A Na
A->B' {Na,N'a} K ab
B'->A {Na,Nb = N'a}K ab
A->B' Nb
Discretionary Access Control
Access to objects (files etc.) is permitted based on user identity. Each object is owned by a user. Owners can specifiy freely (at their discretion) how they want to share their objects with other users, by specifying which other users can have which form of access to their objects.
In its most generic form usually formalized as an Access Control Matrix M of the form
M=(Mso)sЄ S,oЄO with 
where
S = set of subjects
O = set of objects
A = set of access privileges
Columns stored with objects "access control list"
Rows stored with subjects "capabilities"
Unix access control mechanism
User:
userId:groupId:supplementary group IDs
Process:
effective user ID: rel user ID: saved user ID
effective group ID: real group ID: saved group ID
supplementary group IDs
File:
owner user ID: group ID
set-user-ID bit: set-group-ID bit
owner RWX : group RWX
other RWX : sticky bit
● Processes started by a user inherit the user and group ID
● Each file carries each owners user ID and a single group ID
Elevated Rights
Many programs need access rights to files beyond those of the user, eg passwd
Unix files carry two additional permission bits for this purpose:
● set user ID - file owner determines process permissions
● set group-ID 0 file group ID determines process permissions
The user and group ID of each process comes in three flavours:
effective - the identity that determines the access rights
real - the identity of the calling user
saved - the effective identity when the program was started
A normal process started by user U will have the same value U stored as the effective, real and saved user Id and cannot change any of them.
When a program file owned by user O and with the set user ID bit set is started by user U, then both the effective and the saved user ID of the process will be set to O, whereas the real user ID will be set to U.
The program can now switch the effective user ID between U and O. Similarly with the group ID.
If a malicious user can crash a program that is running as root, they can often end up on the shell with root privileges.
Windows NT/2000/XP access control
All accesses are controlled by a Security Reference Monitor. Access control is applied to many different object types, each with its own list of permissions.
Every user or group is identified by security identification number (SID), every object carries a security descriptor with
● SID of the objects owner
● SID dof the objects group (only for POSIX compatibility)
● Access Control List, a list of Aces Control Entries
There is no equivalent of SUID's, and default installations of Windows NT use no acesss control lists for application software.
Mandatory Access Control Policies
Unlike chmod where the user controls access, system policies enforce MAC. MAC mechanisms are aimed at preventing untrusted application software.
Bell Model
Formal policy for mandatory access in a military environment. All subjects are labeled with a confidentiality level, eg
Unclassified < Confidential < Secret < Top Secret
A process that reads Top Secret becomes tagged as Top Secret by the OS, as will all files it writes into afterwards.
Covert Channel Problem
Preventing high level processes leaking to low level processes.
Eg if high level process has already created file F, a low level process will fail when trying to create a file of same name -> 1 bit information
Trusted Computing Base
The trusted computing base are the parts of a system that enforce a security policy.
A good security design should attempt to make the TCB as small as possible.
The TCB must be protected from external interference.
Stack overflow attack
If you don't check for the size of data in you're program its vulnerable to the return address being overwritten etc.
Similarly, input data should be checked in CGI scripts for malicious shell code.
