Computer Systems
Lecture 8
Control Structures
2
Outline
• History: the first programmer in the world • Programming languages and Compiling • Jumping and comparing
• Compilation patterns
• Programming techniques
3
History: the first programmer in the world
• Who could it be?
• There was one person who…
– Wrote the first substantial programs for a real computer
– Made fundamental discoveries that underlie programming (techniques)
• This work also contained ideas related to the discoveries of Alan Turing
4
Ada Lovelace (1815-1852)
• Daughter of Lord Byron, the poet
• Deeply interested in science, mathematics, and technology
• Studied Babbage’s plans for Analytical Engine
• Worked out something that Babbage hadn’t fully realised – The Engine could store programs in its memory
• Even more significantly, she also realised the profound significance of this • A major programming language Ada was named after her
5
Translation of monograph on Analytical Engine
• Luigi Menabrea, an Italian engineer, visited Babbage and wrote a monograph on the Analytical Engine
– Before: no documentation, no user manual
• Ada translated it into English
• She found the text sketchy, and extended it with “Notes”
– It’s worth reading, first document about computing programming! – http://www.fourmilab.ch/babbage/sketch.html
• The Notes contained original research and completely new insights
6
Ada Lovelace
“The world’s first computer programmer”
7
Outline
• History: the first programmer in the world • Programming languages and Compiling • Jumping and comparing
• Compilation patterns
• Programming techniques
8
Compiling
• Computers cannot execute programs in a high-level programming language – We must translate a program into assembly language
• Translating from high-level language to assembly language is called compiling
• This is done by software called a compiler
– It reads in a program in e.g. C++ and translates it to assembly language
• Benefits of using compilers
– A computer can run programs in many languages (using many compilers) – Compilers can make programming easier: good error messages, etc
– Languages can be designed to fit well for different purposes
• For each type of high level language construct, we will translate to assembly language following a standard pattern
9
Statements in high level languages
• A program contains
– Statements that perform calculations
• Assignment statements (e.g. x := 2 + 3)
– Statements that determine the order of the calculations (control structures) • Conditionals: if-then-else
• Loops: while, repeat, for
• Structuring computation: functions, procedures, coroutines, etc
10
High level control structures
• Notation
– S, S1, S2, etc means “any statement” (e.g. an assignment statement) – bexp means “any boolean expression”, either True or False (e.g. x>3)
• Block: We treat several statements as a single statement
{S1; S2; S3;}
• if-then:
• if-then-else:
• while-loop:
• And there are many more
if bexp then S;
if bexp then S1 else S2; while bexp do S
11
Low level constructs
• Assignment statements: • Goto:
• Conditional:
x := a * 2
goto computeTotal
if x < y then goto loop
• Translation procedure
1. Firsttranslatehigh-levelconstructsintotheselow-levelstatements 2. Thentranslatethelow-levelstatementsintoassemblylanguage
12
The Goto statement
S; loop: S;
S;
S;
goto loop;
• Many (not all) programming languages have a goto statement
• Any statement may have a label (for example “loop”)
• Normally execution proceeds from one statement to the next, on and on • A goto L transfers control to the statement with label L
13
Using the goto statement
• The first programming language (Fortran, 1955) didn't have fancy control structures
– You had to do nearly everything with goto
• But goto leads to unreadable programs and unreliable software
• The modern view
– In a high level language, you should not use goto
– For low level programming (like assembly language) goto serves as the foundation for implementing the higher level control statements
• We will use two forms
– Inconditional: goto L
– Conditional: if b then goto L
14
The conditional goto statement
if bexp then goto label
• bexpisaBooleanexpression: x
• Otherwise we just move on the next statement
• The only thing you can put after then is a goto statement
15
Outline
• History: the first programmer in the world • Programming languages and Compiling • Jumping and comparing
• Compilation patterns
• Programming techniques
16
Machine language: Jumping
• The foundation of control structures is jump instructions
• Jumping is the machine language equivalent of goto
• An instruction may have a label
• The label is a name, starting with a letter, and must appear in the first character of a line
• The unconditional instruction jump loop[R0] means goto loop
17
Comparison instruction: Boolean form
• cmp Ra,Rb: compares the values in registers Ra and Rb, and then sets bits (or flags) in R15 to indicate the result
– The instruction performs both binary and two’s complement comparison • The notation R15.i means bit i in R15 thus R15.0 is the leftmost bit of R15
– Note that sigma16 uses “big endian” representation (when we saw binary arithmetic it was “little endian”)
• The resulting bits (or flags) are
– binary less than (L) in R15.0
– two’s complement less than (<) in R15.1
– equal in R15.2
– binary greater than (G) in R15.3
– two's complement greater than (>) in R15.4
18
Conditional jumps: Boolean decision
• The result of a cmp instruction can be used to control a conditional jump
jumplt < jumple <= jumpne != jumpeq = jumpge >= jumpgt >
• Example:
cmp R2,R3 jumplt loop[R0]
less than
less than or equal not equal
equal
greater than or equal greater than
; compare R2 with R3
; if R2 < R3 then goto loop
19
Conditional jumps: Boolean decision
• There are two more instructions: jump if a register contains 0 or ≠ 0 • jumpz Rd,label[R0] ; jump if Rd contains 0
– jumpz R4,label1[R0]
– Means if R4=0 then goto label1
• jumpnz Rd,label[R0] ; jump if Rd contains any value other than 0
– jumpnz R5,label2[R0]
– Means if R5 ≠ 0 then goto label2
20
Outline
• History: the first programmer in the world • Programming languages and Compiling • Jumping and comparing
• Compilation patterns
• Programming techniques
21
Compilation patterns
• Each programming construct is translated according to a standard pattern • It's useful to translate in two steps
– First, translate complex high-level statements to simple low-level ones • goto label, if b then goto label
• The “goto” form corresponds closely to machine instructions
– Then complete the translation to assembly language
• Assignment statements: loads, then arithmetic, then store
• goto label: jump label[R0]
• if b then goto label: jumpnz R5,label[R0] where R5 contains b
• if not b then goto label: jumpz R5,label[R0] where R5 contains b
22
Compiling an assignment statement
• Load the operands; do calculations; store results ; x := a + b*c;
Compiled into
load R1,a[R0] load R2,b[R0] load R3,c[R0] mul R4,R2,R3 add R4,R1,R4 store R4,x[R0]
; R1 = a
; R2 = b
; R3 = c
; R4 = b*c
; R4 = a + (b*c) ; x := a+(b*c)
23
if bexp then S
if x
then { a := 5; } b := 6;
25
Example: translating if-then
; x := 2;
lea R1,2[R0] store R1,x[R0]
; if y>x
load R1,y[R0] load R2,x[R0] cmp R1,R2 jumple skip[R0]
; then { a := 5; }
lea R1,5[R0] store R1,a[R0]
; b := 6;
skip lea R1,6[R0] store R1,b[R0]
; R1 := 2 ; x := 2
; R1 := y
; R2 := x
; compare R1 with R2
; if y <= x then goto skip
; R1 := 5 ; a := 5
; R1 := 6 ; b := 6
26
if bexp then S1 else S2
if x