程序代写代做代考 Fortran flex Java algorithm Computer Systems

Computer Systems
Topic – Subroutines and Stacks
Dr. Mian M. Hamayun
M.M.Hamayun@cs.bham.ac.uk
Credits to:
Ata Kaban & Steve Vickers

Lecture Objectives
To introduce the fundamentals concepts of subroutines and how they are implemented using stacks.
Slide #2 of 43

Lecture Outline
 How a Subroutine Works? Call / Return Instructions
 Introduction to Stacks Saving Registers Stacks for Calculation
 Reverse Polish Notation
 Bitwise Boolean Operations
 Conditional & Unconditional Jumps  Summary
Slide #3 of 43

Subroutines (Methods) – Example
Slide #4 of 43

Subroutines (Methods)
Slide #5 of 43

Subroutines (Methods)
Slide #6 of 43

Subroutines (Methods)
Could jump to 94 for subroutine, but how to know where to jump back afterwards?
Must store the return address somewhere.
Slide #7 of 43

Call / Return Instructions
 Two new operations:
 call operand : Like jump, but stores current PC value
(the return address) somewhere suitable.
 ret : Read return address from where it was stored, and load it into PC.
Slide #8 of 43

Storing the Return Address
Idea #1: In each subroutine, its first byte is used to store the return address

Slide #9 of 43

Disadvantage of Idea #1
 Can only store one return address
 Consequence: subroutine cannot call itself
 If it were to call itself it would need to store 2 return addresses
Slide #10 of 43

History: 2 Early Programming Languages
 FORTRAN (“FORmula TRANslation”)
 Used jumps (GOTO), conditional jumps
 Banned recursion (i.e. for a method to call itself) to allow idea 1.
 Algol (“Algorithmic language”)
 structured programming (if .. then .. else, etc.)  Allowed recursion
 Initially, FORTRAN was more successful, but modern languages (e.g. C, Java) took forward the ideas from Algol.
Slide #11 of 43

What is a Stack?
Slide #12 of 43

How Stacks Work?
 A stack can flexibly store a variable number of bytes  LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
54
13
27
42
9
-6
10
2
9
-6
10
2
push a
Slide #13 of 43

How Stacks Work?
 A stack can flexibly store a variable number of bytes  LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
54
13
27
13
42
9
-6
10
2
42
9
-6
10
2
push c
Slide #14 of 43

How Stacks Work?
 A stack can flexibly store a variable number of bytes  LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
13
13
27
42
9
-6
10
2
13
42
9
-6
10
2
pop b
Slide #15 of 43

How Stacks Work?
 A stack can flexibly store a variable number of bytes  LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
13
13
42
9
-6
10
2
42
9
-6
10
2
pop d
Slide #16 of 43

In Memory
 Give CPU another register
 sp (stack pointer) – shows where top is
 Don’t need to know where bottom is!
 Provided that we are careful: only pop when you know you’ve pushed
Slide #17 of 43

In Memory
 To push a value X:
 Write the value to memory at address sp  Add 1 to sp
 To pop a value:
 Subtract 1 from sp
 Read value from memory at address sp
Slide #18 of 43

In Memory – Push a Value
 To push a value X:
 Write the value to memory at address sp  Add 1 to sp
Slide #19 of 43

In Memory – Pop a Value
 To pop a value:
 Subtract 1 from sp
 Read value from memory at address sp
The value read is Y.
Still in memory but will be overwritten by a later push operation.
Slide #20 of 43

Storing the Return Address
Idea #2: Store the return address on a stack.

Slide #21 of 43

Why should we Save Registers?
 Subroutine may need to use registers for its calculations.
 But previous register values are needed on return!
 Common pattern for subroutines:  Start by pushing all registers
 Pop them back before return
 Return address & saved registers = stack frame Java method-calls develop this idea.
Slide #22 of 43

Saving Registers – Stack Frame
Slide #23 of 43

Saving Registers – Stack Frame
Slide #24 of 43

Toy CPU (For the Exercises)
Slide #25 of 43

Exercise #1 (Home Work)
Write mnemonics and machine code (for the Toy CPU) for the following tasks:
a) A subroutine, starting at location 10 (hex) that sums memory locations, then stores the result after them. Assume that the calling routine initialized the register b with the address of the memory location of the summands, and the register c with the number of them. Don’t forget the return instruction.
b) A main routine, starting at location 00, that calls the subroutine twice: once for summing 4 locations starting at 2A, and once for summing 6 locations starting at 38.
Slide #26 of 43

Exercise #2 (Home Work)
Your answer to Ex. 1(a) will have used the a, b and c registers in its own calculations. Suppose this is inconvenient for the main program and it would be better not to lose the values that those three registers had when the subroutine was stored.
Rewrite the subroutine so that it pushes the three registers at the start, saving their values on the stack, and then pops them back at the end so that the calling routine gets them back unchanged. Make sure you pop them in the right order!
Slide #27 of 43

Stacks for Calculation
 Example:
Slide #28 of 43

Reverse Polish Notation (RPN)
 Order of operations is as written
 No brackets needed
 Powerful use of stack (= operand stack) to store intermediate results
 If its a Number or Variable: push it on the stack
 If its an Operation: apply to the top elements on stack
& push result back on the stack
11
6
10
8
3
6
10
Apply +
Slide #29 of 43

RPN for the Example
Slide #30 of 43

How to use RPN along with a Stack?
 Suppose that x has value 3, and y has value 4
 Now, evaluate the expression. (Top of stack is on right.)
Slide #31 of 43

Notation for Operand Stack
 To show what an operation does to the stack:  e.g. subtraction
Slide #32 of 43

More on Reverse Polish Notation
 Any expression can be converted to Reverse Polish Notation and then its easy to execute with a stack.
 Applications
 Humans use reverse Polish directly (See Details)
 e.g. some pocket calculators – HP in 1970s (HP-41C) https://www.theregister.co.uk/Print/2014/01/03/ten_classic_calcutors/
 Forth programming language has two stacks:
 Operand stacks for calculations
 Return stack for module calls
More details: https://en.wikipedia.org/wiki/Forth_(programming_language)
Slide #33 of 43

Applications of Reverse Polish Notation
 Compile to a reverse Polish form that is then executed. e.g. Postscript format, for printable files
► executed by printers e.g. Java byte code
► uses operand stacks for calculations
 In Java, each method call has its own operand stack.
Slide #34 of 43

Stack instead of Registers (Stack Machines)
 Use 2 stacks
return stack for subroutine return
operand stack for Reverse Polish calculations
 Don’t need a,b,c registers  Advantages
► More space for calculations
► Opcodes don’t need to specify registers  Disadvantages
► Harder to know where things are on the stack
Slide #35 of 43

What is an Operand?
 Underlying meaning:
Whatever an operator operates on?
 Two meanings here (don’t confuse them):
1) Extra bytes after the instruction opcode in memory,
e.g.
ld a 42
2) Entries in the operand stack.
Slide #36 of 43

Machine Instructions as Stack Operators
[Forget the Toy CPU – remember these mnemonics (JVM)]
Slide #37 of 43

Example of a Stack Machine (JVM mnemonics)
Slide #38 of 43

Bitwise Boolean Operations
Slide #39 of 43

Jumps
 Unconditional jumps Operand stack is not used!
 Conditional jumps
Slide #40 of 43

Conditional Jumps with Other Comparisons
Slide #41 of 43

Summary
We have now seen:
 What is a subroutine and how it is implemented.
 What is a stack and how it is used for implementing subroutines.
 What is the importance of saving registers and how these can be used to perform computations.
 What is reverse polish notation and how it is used to to do calculations using an operand stack.
 What is a stack machine and how it operates using a stack instead of registers.
 What are Bitwise Boolean operations and Jump instructions.
Slide #42 of 43

Notes on Exercises 3 & 4
 You will need to use an algorithm to convert math expressions from the usual “infix” notation to reverse- Polish. This algo is called Dijkstra’s Shunting-Yard Algorithm.
 You can also read the Wikipedia page on this algo https://en.wikipedia.org/wiki/Shunting-yard_algorithm
Slide #43 of 43