Compilation etc part 2 Flashcards
Suroutines & Stacks
What is a subroutine?
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.
What is a method in programming?
A method is a type of subroutine associated with an object or class in object-oriented programming. It defines a behavior for objects.
What does the call instruction do?
call operand jumps to a subroutine and stores the current program counter (PC) value (the return address) before jumping.
What does the ret instruction do?
‘ret’ retrieves the stored return address and loads it back into the program counter (PC), resuming execution after the subroutine.
How is ‘call’ different from a regular ‘jump’ instruction?
‘call’ saves the current location (return address) before jumping, while a regular ‘jump’ simply moves to a new location without saving.
Where is the return address typically stored during a ‘call’ operation?
The return address is usually stored in a register or on the stack to be retrieved later by the ‘ret’ instruction.
What is one idea for storing the return address in a subroutine call?
The first byte of the subroutine can be used to store the return address.
Why might storing the return address in the subroutine’s first byte be problematic?
It can overwrite important instructions or data at the start of the subroutine, making the subroutine unreliable.
What is the return address?
It is the memory location where the program should continue execution after a subroutine finishes.
In simple systems, why is using the first byte for the return address considered?
It simplifies design by avoiding the need for a dedicated return address stack or register.
What is a major disadvantage of storing the return address in the first byte of a subroutine?
Only one return address can be stored.
What happens if a subroutine that uses Idea #1 tries to call itself (recursion)?
It would need to store a second return address, which Idea #1 cannot handle.
Why can’t a subroutine call itself under Idea #1?
Because overwriting the single return address would lose the original return location, breaking program execution.
What programming feature becomes impossible if only one return address can be stored?
Recursion (a subroutine calling itself).
What does FORTRAN stand for, and what were its features?
FORTRAN stands for “FORmula TRANslation”; it used jumps (GOTO) and conditional jumps but banned recursion.
Why did FORTRAN ban recursion?
To support a simple return address storage method like storing it in the first byte (Idea #1).
What was Algol, and how was it different from FORTRAN?
Algol (“Algorithmic Language”) introduced structured programming (if..then..else, etc.) and allowed recursion.
Which early language’s ideas influenced modern languages like C and Java?
Algol’s ideas influenced the design of modern programming languages.
What is a stack in computer science?
A stack is a structure that can flexibly store a variable number of bytes, handling data dynamically.
What does LIFO mean in the context of stacks?
LIFO stands for “Last In, First Out” — the last item added to the stack is the first one removed.
What is another name for LIFO?
FILO, which stands for “First In, Last Out.”
Why are stacks useful for storing return addresses?
They can store multiple return addresses and retrieve them in the correct order, allowing recursion and nested subroutine calls.
What is the purpose of the sp (stack pointer) register?
The ‘sp’ register points to the top of the stack in memory.
Do we need to know where the bottom of the stack is?
No, as long as we are careful to only pop values that have been pushed.
What can happen if you pop from the stack without pushing first?
It can lead to errors like retrieving invalid data or causing crashes.
What are the steps to push a value onto the stack?
Write the value to memory at address sp, then add 1 to sp.
How does the CPU interact with the stack in memory?
The CPU uses the stack pointer (sp) to keep track of where data is pushed and popped.
What are the steps to pop a value from the stack?
Subtract 1 from sp, then read the value from memory at the address sp.
When pushing a value, why do we increment the stack pointer (sp) after writing?
So the sp always points to the next free location on the stack.
When popping a value, why do we decrement the stack pointer (sp) first?
To point back to the last pushed value, ensuring correct retrieval.
What is the first step when pushing a value X onto the stack?
Write the value X to memory at the address pointed to by sp.
After writing the value to memory during a push, what is the next step?
Add 1 to the stack pointer (sp).
Why do we increment sp after a push operation?
To move the stack pointer to the next empty memory location.
What would happen if you forgot to increment sp after a push?
The next push would overwrite the same memory location, causing data loss.
What is Idea #2 for storing the return address?
Store the return address on a stack.
Why is storing the return address on a stack a better approach than using a fixed memory location (like the first byte)?
The stack can dynamically store multiple return addresses, allowing for recursion and nested function calls.
What advantage does using the stack for return addresses provide for recursion?
It allows each recursive call to store its return address separately, so each function call can return to the correct location.
How does the stack work to manage return addresses during nested calls?
Each return address is pushed onto the stack during a subroutine call and popped off in reverse order when returning from the subroutine.
Why do we need to save registers during subroutine calls?
Subroutines may use registers for calculations, but we need to restore the previous values of those registers when the subroutine returns.
What is the common pattern for saving and restoring registers in subroutines?
The pattern is to push all registers onto the stack at the beginning and pop them back before returning.
What is a “stack frame” in the context of subroutine calls?
A stack frame includes the return address and any saved registers, allowing the subroutine to work without affecting the calling function’s state.
How do Java method calls relate to the concept of a stack frame?
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.
What is Reverse Polish Notation (RPN)?
RPN is a mathematical notation where the order of operations is as written, without the need for parentheses.
Why are parentheses unnecessary in Reverse Polish Notation?
Because RPN defines the order of operations explicitly, eliminating the need for brackets to indicate precedence.
How does a stack work in Reverse Polish Notation?
The stack stores intermediate results. Numbers and variables are pushed onto the stack, and operations are applied to the top elements of the stack.
What happens when an operation is encountered in RPN?
The operation is applied to the top elements of the stack, and the result is pushed back onto the stack.
What are the initial steps in converting an infix expression to postfix?
Initialise an empty stack for operators and an empty list for the output.
How do you handle operands (numbers or variables) during the conversion?
If the token is an operand, add it directly to the output list.
What do you do when you encounter an operator in the infix expression?
- 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.
- Push the current operator onto the stack.
How are parentheses handled during the conversion?
- 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.
What is the final step after processing the entire infix expression?
Pop any remaining operators from the stack and append them to the output list to get the final postfix expression.
Can any expression be converted to Reverse Polish Notation (RPN)?
Yes, any expression can be converted to RPN, making it easy to execute using a stack.
What are some real-world applications of Reverse Polish Notation?
- 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).
What is the Forth programming language’s approach to stacks?
Forth uses two stacks:
- Operand stack for calculations.
- Return stack for module calls.
Where can you learn more about the Forth programming language and its use of stacks?
How is Reverse Polish Notation used in compilers?
Compilers often convert expressions into RPN form, which is then executed directly. This simplifies evaluation and execution.
Can you give an example of a system that uses Reverse Polish Notation for execution?
Postscript format (used for printable files) is an example. Postscript uses RPN, and printers execute these RPN instructions to render documents.
How is RPN used in Java bytecode?
Java bytecode uses operand stacks for calculations. Each Java bytecode instruction operates on an operand stack, allowing efficient computation.
How does Java handle operand stacks in method calls?
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.
What are the two stacks used in a stack machine?
- Return stack for subroutine returns.
- Operand stack for Reverse Polish Notation (RPN) calculations.
Why don’t stack machines need registers like a, b, and c?
Because all operations are performed using the stacks, which store operands and results instead of using separate registers.
What is the advantage of using stacks instead of registers in a stack machine?
- 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.
What is a disadvantage of using stacks instead of registers in a stack machine?
It can be harder to know where things are on the stack, making it more difficult to track operands and results during execution.
What is the underlying meaning of an “operand”?
An operand is whatever an operator operates on; it’s the target of an operation.
What is the first meaning of an operand?
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.
What is the second meaning of an operand?
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).
How should you avoid confusion when thinking about operands?
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).
What happens during an unconditional jump in a stack machine?
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.
What is the role of the operand stack in an unconditional jump?
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.
What are conditional jumps?
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.
Does the operand stack play a role in conditional jumps?
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.
