CS 241 - Foundations of Sequential Programming
Sequential programs are procedurally driven programs which only use a single process at a time. They
are single-threaded and do not run processes concurrently. For this course, we are not interested in
what those programs do, but simply in how they do it.
These programs can be written in machine language, assembly, higher-level languages... whatever. Since
each is an abstraction of a lower level to which we can build a compiler, all of them will give us the
same ▯nal result.
A computer sees a string such as "10000011" as a sequence of bits, without regards to any sort of
encoding. This could be binary, hexadecimal, decimal, ascii... pretty much everything, but the computer
can not know which.
Hexadecimal is represented with the characters "01234567899ABCDEF". We tend to write them in the
form 0x2A, which is equal to 42 in decimal.
With n bits, we can represent 2 numbers in binary. To represent negative numbers we can use the
sign and magnitude
sign and magnitude: use the ▯rst bit as an indicator of sign and the remaining bits as magnitude
method, though this is subject to some weirdness. We will end up with both a positive and a negative
zero and will need specialized hardware for both addition and subtraction.
A better method is to use two’s complement
1 two’s complement: uses the congruences of numbers to represent their negatives
We can convert a number into two’s complement form by the following method:
-6 can be converted by taking the absolute value in binary (0110), then
ipping all of its bits (1001)
and adding 1 (1010). Obviously this method can be used backwards: subtract 1,
ip the bits, and add
a negative number.
Alternatively, subtract 2 if and only if the ▯rst bit is non-zero (to go from two’s complement to decimal).
Parts of a Processor
A processor is comprised of a control unit, which controls the execution of the program and keeps
track of the next instruction to execute. It can interpret strings of binary as command instructions
and controls the signals to and from any external devices. It contains a timing device for synchronised
operations. The processor also contains an arithmetic logic unit, which is responsible for arithmetic
and logic operations.
The program counter (PC) is a 32-bit register which contains the address of the next instruction to
be executed. The Instruction Register (IR) contains the current instruction address.
We also have General Purpose Registersthirty-two zero-indexed registers which are 32-bits in size
though they are somewhat slow.
Range of Registers
Our registers range from $0 ▯ $31. Register $0 always contains the value 0 and register $31 always
contains the value of the return address. Register $30 contains the address of the top of the stack.
How a Program is Executed
The OS invokes the "loader" to load the program into memory starting at some given memory address,
virtually always zero. The loader places the starting address in the PC: "PC ! 0x00".
We then fetch, decode, and execute each instruction in order. In e▯ect:
fetch // IR expr op expr
op -> +|-|*|/
expr -> term
term -> a|b|c|d...
can be used to derive the input string "a + b". Beginning with an expr we can use the following
expr -> expr op expr
expr -> term
term -> a
op -> +
expr -> term
term -> b
If we include a rule such as expr ! ( expr ), we ▯nd ourselves with a CFG which can accept a
potentially in▯nte level of nested brackets.
We formally specify CFGs as follows: each is a 4-tuple (N;T;P;S) where we have
▯ N is a ▯nite set of non-terminals
▯ T is a ▯nite set of terminals
▯ P is a ▯nite set of production rules
▯ S is a unique non-terminal with which we start
If we always expand the left-most terminal ▯rst, we will ▯nd ourselves with a left-most / left canonical
derivation. Similarly, expanding the right-most terminals ▯rst gives us a right canonical derivation.
7 For any given input string, thes