[SOLVED] CS Fortran c++ assembly ada compiler Computer Systems

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 Babbages plans for Analytical Engine
Worked out something that Babbage hadnt 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
Its 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 worlds 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 procedure1. Firsttranslatehigh-levelconstructsintotheselow-levelstatements 2. Thentranslatethelow-levelstatementsintoassemblylanguage12The Goto statementS; 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 L13Using 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 L14The conditional goto statementif bexp then goto label bexpisaBooleanexpression: x def If the bexp is True the statement goes to the label
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 twos 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
twos 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 loop19Conditional 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 label220Outline History: the first programmer in the world Programming languages and Compiling Jumping and comparing Compilation patterns Programming techniques21Compilation 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 b22Compiling an assignment statement Load the operands; do calculations; store results ; x := a + b*c;Compiled intoload 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)23if bexp then Sif x 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 := 626if bexp then S1 else S2if x