Compilation etc part 2

Question 1

What is a subroutine?

Answer 1

A subroutine is a set of instructions designed to perform a frequently used operation, packaged as a unit. It can be called from different parts of a program to avoid code repetition.

Question 2

What is a method in programming?

Answer 2

A method is a type of subroutine associated with an object or class in object-oriented programming. It defines a behavior for objects.

Question 3

What does the call instruction do?

Answer 3

call operand jumps to a subroutine and stores the current program counter (PC) value (the return address) before jumping.

Question 4

What does the ret instruction do?

Answer 4

‘ret’ retrieves the stored return address and loads it back into the program counter (PC), resuming execution after the subroutine.

Question 5

How is ‘call’ different from a regular ‘jump’ instruction?

Answer 5

‘call’ saves the current location (return address) before jumping, while a regular ‘jump’ simply moves to a new location without saving.

Question 6

Where is the return address typically stored during a ‘call’ operation?

Answer 6

The return address is usually stored in a register or on the stack to be retrieved later by the ‘ret’ instruction.

Question 7

What is one idea for storing the return address in a subroutine call?

Answer 7

The first byte of the subroutine can be used to store the return address.

Question 8

Why might storing the return address in the subroutine’s first byte be problematic?

Answer 8

It can overwrite important instructions or data at the start of the subroutine, making the subroutine unreliable.

Question 9

What is the return address?

Answer 9

It is the memory location where the program should continue execution after a subroutine finishes.

Question 10

In simple systems, why is using the first byte for the return address considered?

Answer 10

It simplifies design by avoiding the need for a dedicated return address stack or register.

Question 11

What is a major disadvantage of storing the return address in the first byte of a subroutine?

Answer 11

Only one return address can be stored.

Question 12

What happens if a subroutine that uses Idea #1 tries to call itself (recursion)?

Answer 12

It would need to store a second return address, which Idea #1 cannot handle.

Question 13

Why can’t a subroutine call itself under Idea #1?

Answer 13

Because overwriting the single return address would lose the original return location, breaking program execution.

Question 14

What programming feature becomes impossible if only one return address can be stored?

Answer 14

Recursion (a subroutine calling itself).

Question 15

What does FORTRAN stand for, and what were its features?

Answer 15

FORTRAN stands for “FORmula TRANslation”; it used jumps (GOTO) and conditional jumps but banned recursion.

Question 16

Why did FORTRAN ban recursion?

Answer 16

To support a simple return address storage method like storing it in the first byte (Idea #1).

Question 17

What was Algol, and how was it different from FORTRAN?

Answer 17

Algol (“Algorithmic Language”) introduced structured programming (if..then..else, etc.) and allowed recursion.

Question 18

Which early language’s ideas influenced modern languages like C and Java?

Answer 18

Algol’s ideas influenced the design of modern programming languages.

Question 19

What is a stack in computer science?

Answer 19

A stack is a structure that can flexibly store a variable number of bytes, handling data dynamically.

Question 20

What does LIFO mean in the context of stacks?

Answer 20

LIFO stands for “Last In, First Out” — the last item added to the stack is the first one removed.

Question 21

What is another name for LIFO?

Answer 21

FILO, which stands for “First In, Last Out.”

Question 22

Why are stacks useful for storing return addresses?

Answer 22

They can store multiple return addresses and retrieve them in the correct order, allowing recursion and nested subroutine calls.

Question 23

What is the purpose of the sp (stack pointer) register?

Answer 23

The ‘sp’ register points to the top of the stack in memory.

Question 24

Do we need to know where the bottom of the stack is?

Answer 24

No, as long as we are careful to only pop values that have been pushed.

Question 25

What can happen if you pop from the stack without pushing first?

Answer 25

It can lead to errors like retrieving invalid data or causing crashes.

Question 26

What are the steps to push a value onto the stack?

Answer 26

Write the value to memory at address sp, then add 1 to sp.

Question 26

How does the CPU interact with the stack in memory?

Answer 26

The CPU uses the stack pointer (sp) to keep track of where data is pushed and popped.

Question 27

What are the steps to pop a value from the stack?

Answer 27

Subtract 1 from sp, then read the value from memory at the address sp.

Question 28

When pushing a value, why do we increment the stack pointer (sp) after writing?

Answer 28

So the sp always points to the next free location on the stack.

Question 29

When popping a value, why do we decrement the stack pointer (sp) first?

Answer 29

To point back to the last pushed value, ensuring correct retrieval.

Question 29

What is the first step when pushing a value X onto the stack?

Answer 29

Write the value X to memory at the address pointed to by sp.

Question 30

After writing the value to memory during a push, what is the next step?

Answer 30

Add 1 to the stack pointer (sp).

Question 31

Why do we increment sp after a push operation?

Answer 31

To move the stack pointer to the next empty memory location.

Question 32

What would happen if you forgot to increment sp after a push?

Answer 32

The next push would overwrite the same memory location, causing data loss.

Question 33

What is Idea #2 for storing the return address?

Answer 33

Store the return address on a stack.

Question 34

Why is storing the return address on a stack a better approach than using a fixed memory location (like the first byte)?

Answer 34

The stack can dynamically store multiple return addresses, allowing for recursion and nested function calls.

Question 35

What advantage does using the stack for return addresses provide for recursion?

Answer 35

It allows each recursive call to store its return address separately, so each function call can return to the correct location.

Question 36

How does the stack work to manage return addresses during nested calls?

Answer 36

Each return address is pushed onto the stack during a subroutine call and popped off in reverse order when returning from the subroutine.

Question 37

Why do we need to save registers during subroutine calls?

Answer 37

Subroutines may use registers for calculations, but we need to restore the previous values of those registers when the subroutine returns.

Question 38

What is the common pattern for saving and restoring registers in subroutines?

Answer 38

The pattern is to push all registers onto the stack at the beginning and pop them back before returning.

Question 39

What is a "stack frame" in the context of subroutine calls?

Answer 39

A stack frame includes the return address and any saved registers, allowing the subroutine to work without affecting the calling function’s state.

Question 40

How do Java method calls relate to the concept of a stack frame?

Answer 40

Java method calls develop the idea of stack frames by saving the method’s state (parameters, return address, and registers) to ensure proper execution flow and return.

Question 41

What is Reverse Polish Notation (RPN)?

Answer 41

RPN is a mathematical notation where the order of operations is as written, without the need for parentheses.

Question 42

Why are parentheses unnecessary in Reverse Polish Notation?

Answer 42

Because RPN defines the order of operations explicitly, eliminating the need for brackets to indicate precedence.

Question 43

How does a stack work in Reverse Polish Notation?

Answer 43

The stack stores intermediate results. Numbers and variables are pushed onto the stack, and operations are applied to the top elements of the stack.

Question 44

What happens when an operation is encountered in RPN?

Answer 44

The operation is applied to the top elements of the stack, and the result is pushed back onto the stack.

Question 45

What are the initial steps in converting an infix expression to postfix?

Answer 45

Initialise an empty stack for operators and an empty list for the output.

Question 46

How do you handle operands (numbers or variables) during the conversion?

Answer 46

If the token is an operand, add it directly to the output list.

Question 47

What do you do when you encounter an operator in the infix expression?

Answer 47

1. While the stack is not empty, pop operators from the stack and add them to the output if their precedence is greater than or equal to the current operator. 2. Push the current operator onto the stack.

Question 48

How are parentheses handled during the conversion?

Answer 48

- For an opening parenthesis ‘(’, push it onto the stack. - For a closing parenthesis ‘)’, pop from the stack and add to the output until an opening parenthesis is encountered, then discard the opening parenthesis.

Question 49

What is the final step after processing the entire infix expression?

Answer 49

Pop any remaining operators from the stack and append them to the output list to get the final postfix expression.

Question 50

Can any expression be converted to Reverse Polish Notation (RPN)?

Answer 50

Yes, any expression can be converted to RPN, making it easy to execute using a stack.

Question 51

What are some real-world applications of Reverse Polish Notation?

Answer 51

- Humans can use RPN directly (e.g., in calculators). - Some pocket calculators from the 1970s, like the HP-41C, used RPN. (See more details on classic calculators here).

Question 52

What is the Forth programming language's approach to stacks?

Answer 52

Forth uses two stacks: 1. Operand stack for calculations. 2. Return stack for module calls.

Question 53

Where can you learn more about the Forth programming language and its use of stacks?

Question 54

How is Reverse Polish Notation used in compilers?

Answer 54

Compilers often convert expressions into RPN form, which is then executed directly. This simplifies evaluation and execution.

Question 55

Can you give an example of a system that uses Reverse Polish Notation for execution?

Answer 55

Postscript format (used for printable files) is an example. Postscript uses RPN, and printers execute these RPN instructions to render documents.

Question 56

How is RPN used in Java bytecode?

Answer 56

Java bytecode uses operand stacks for calculations. Each Java bytecode instruction operates on an operand stack, allowing efficient computation.

Question 57

How does Java handle operand stacks in method calls?

Answer 57

In Java, each method call has its own operand stack, which is used to evaluate expressions and handle local variables during the method’s execution.

Question 58

What are the two stacks used in a stack machine?

Answer 58

1. Return stack for subroutine returns. 2. Operand stack for Reverse Polish Notation (RPN) calculations.

Question 59

Why don’t stack machines need registers like a, b, and c?

Answer 59

Because all operations are performed using the stacks, which store operands and results instead of using separate registers.

Question 60

What is the advantage of using stacks instead of registers in a stack machine?

Answer 60

- More space for calculations: The stacks can dynamically store a large number of operands. - Opcodes don't need to specify registers: The operations just refer to the top of the stack, simplifying the instruction set.

Question 61

What is a disadvantage of using stacks instead of registers in a stack machine?

Answer 61

It can be harder to know where things are on the stack, making it more difficult to track operands and results during execution.

Question 62

What is the underlying meaning of an "operand"?

Answer 62

An operand is whatever an operator operates on; it’s the target of an operation.

Question 63

What is the first meaning of an operand?

Answer 63

An operand can be the extra bytes after the instruction opcode in memory. For example, in the instruction ld a 42, 42 is the operand.

Question 64

What is the second meaning of an operand?

Answer 64

In the context of a stack machine, operands refer to entries in the operand stack. These are the values used for calculations in Reverse Polish Notation (RPN).

Question 65

How should you avoid confusion when thinking about operands?

Answer 65

Remember that operands can refer either to memory values (like in the instruction ld a 42) or to values on the operand stack in a stack machine (used for RPN calculations).

Question 66

What happens during an unconditional jump in a stack machine?

Answer 66

An unconditional jump does not use the operand stack. The program simply jumps to a new location in the code, and no operands are involved in this operation.

Question 67

What is the role of the operand stack in an unconditional jump?

Answer 67

The operand stack is not used in an unconditional jump. The jump is purely based on the program counter (PC) and not dependent on stack values.

Question 68

What are conditional jumps?

Answer 68

A conditional jump is a jump that only occurs if a certain condition is met, often based on the value of the operand stack or a specific comparison.

Question 69

Does the operand stack play a role in conditional jumps?

Answer 69

Yes, conditional jumps usually depend on the values on the operand stack to decide whether the jump should happen, making the stack a crucial part of the condition evaluation.