CS计算机代考程序代写 Java flex Fortran algorithm Computer Systems

Computer Systems
Topic – Subroutines and Stacks

Dr. Mian M. Hamayun
M.M. .ac.uk

Credits to:
&

Slide #2 of 43

Lecture Objectives

To introduce the fundamentals concepts of subroutines
and how they are implemented using stacks.

Slide #3 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 #4 of 43

Subroutines (Methods) – Example

Slide #5 of 43

Subroutines (Methods)

Slide #6 of 43

Subroutines (Methods)

Slide #7 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 #8 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 #9 of 43

Storing the Return Address

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

Slide #10 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 #11 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.

https://en.wikipedia.org/wiki/Fortran
https://en.wikipedia.org/wiki/ALGOL

Slide #12 of 43

What is a Stack?

Slide #13 of 43

How Stacks Work?

 A stack can flexibly store a variable number of bytes
 LIFO = Last In, First Out (aka FILO)

9

-6

10

2

a b c d

42 54 13 27

push a

42

9

-6

10

2

Slide #14 of 43

How Stacks Work?

 A stack can flexibly store a variable number of bytes
 LIFO = Last In, First Out (aka FILO)

42

9

-6

10

2

a b c d

42 54 13 27

push c

13

42

9

-6

10

2

Slide #15 of 43

How Stacks Work?

 A stack can flexibly store a variable number of bytes
 LIFO = Last In, First Out (aka FILO)

13

42

9

-6

10

2

a b c d

42 13 13 27

pop b

42

9

-6

10

2

Slide #16 of 43

How Stacks Work?

 A stack can flexibly store a variable number of bytes
 LIFO = Last In, First Out (aka FILO)

42

9

-6

10

2

a b c d

42 13 13 42

pop d

9

-6

10

2

Slide #17 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 #18 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 #19 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 #20 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 #21 of 43

Storing the Return Address

 Idea #2: Store the return address on a stack.

Slide #22 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 #23 of 43

Saving Registers – Stack Frame

Slide #24 of 43

Saving Registers – Stack Frame

Slide #25 of 43

Toy CPU (For the Exercises)

Slide #26 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 #27 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 #28 of 43

Stacks for Calculation

 Example:

Slide #29 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

8

3

6

10

Apply +
11

6

10

Slide #30 of 43

RPN for the Example

Slide #31 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 #32 of 43

Notation for Operand Stack

 To show what an operation does to the stack:
 e.g. subtraction

Slide #33 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)

https://en.wikipedia.org/wiki/Order_of_operations
https://www.theregister.co.uk/Print/2014/01/03/ten_classic_calcutors/
https://en.wikipedia.org/wiki/Forth_(programming_language

Slide #34 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 #35 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 #36 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 #37 of 43

Machine Instructions as Stack Operators

[Forget the Toy CPU – remember these mnemonics (JVM)]

Slide #38 of 43

Example of a Stack Machine (JVM mnemonics)

Slide #39 of 43

Bitwise Boolean Operations

Slide #40 of 43

Jumps

 Unconditional jumps
Operand stack is not used!

 Conditional jumps

Slide #41 of 43

Conditional Jumps with Other Comparisons

Slide #42 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 #43 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

https://en.wikipedia.org/wiki/Shunting-yard_algorithm

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43