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 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: xdef • 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 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 xx
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