[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 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 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 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 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