Build Your Own Bytecode Interpreter

Ever wondered how high-level programming languages like Python are executed? A crucial step involves translating your code into a lower-level representation called bytecode, which is then processed by a virtual machine. This challenge will guide you in building a simple bytecode interpreter in Python, giving you a hands-on understanding of how programs are executed.

Problem Description

Your task is to create a Python program that simulates a bytecode interpreter. This interpreter will read a sequence of bytecode instructions and execute them to produce a result. You will define a set of basic instructions, including operations like addition, subtraction, pushing values onto a stack, and halting execution. The interpreter will maintain a stack to store intermediate values and a program counter to track the current instruction.

Key Requirements:

1. Instruction Set: Define at least the following instructions:
   • PUSH <value>: Pushes an integer <value> onto the stack.
   • ADD: Pops two values from the stack, adds them, and pushes the result back onto the stack.
   • SUB: Pops two values from the stack (second popped is the minuend, first popped is the subtrahend), subtracts the first from the second, and pushes the result back onto the stack.
   • HALT: Stops the interpreter's execution.
2. Stack: Implement a stack data structure (e.g., using a Python list) to store operands.
3. Program Counter (PC): Maintain a variable that points to the current instruction being executed.
4. Execution Loop: Create a loop that fetches the current instruction based on the PC, decodes it, and executes the corresponding action. The PC should be incremented after each instruction, unless the instruction explicitly changes it (like HALT).
5. Error Handling: Implement basic error handling for situations like:
   • Stack underflow (attempting to pop from an empty stack).
   • Invalid instruction.
   • Program not ending with HALT.

Expected Behavior:

The interpreter should take a list of bytecode instructions as input. It should process these instructions sequentially, manipulating the stack as defined by each instruction. Upon encountering HALT, the interpreter should return the final value on top of the stack (if any), or a specific indicator if the stack is empty or an error occurred.

Edge Cases to Consider:

• Empty bytecode program.
• Program that doesn't include a HALT instruction.
• Programs that result in an empty stack when HALT is reached.
• Integer overflow (though for simplicity, standard Python integers can handle large values).

Examples

Example 1:

Input: [
    ("PUSH", 10),
    ("PUSH", 5),
    ("ADD",),
    ("HALT",)
]
Output: 15
Explanation:
1. PUSH 10: Stack: [10]
2. PUSH 5:  Stack: [10, 5]
3. ADD:     Pop 5, Pop 10. 10 + 5 = 15. Push 15. Stack: [15]
4. HALT:    Stop. Return top of stack.

Example 2:

Input: [
    ("PUSH", 20),
    ("PUSH", 7),
    ("SUB",),
    ("HALT",)
]
Output: 13
Explanation:
1. PUSH 20: Stack: [20]
2. PUSH 7:  Stack: [20, 7]
3. SUB:     Pop 7 (first), Pop 20 (second). 20 - 7 = 13. Push 13. Stack: [13]
4. HALT:    Stop. Return top of stack.

Example 3: Stack Underflow

Input: [
    ("ADD",),
    ("HALT",)
]
Output: Error: Stack underflow
Explanation:
1. ADD:     Attempt to pop from an empty stack. This is an error.

Example 4: No HALT

Input: [
    ("PUSH", 1),
    ("PUSH", 2),
    ("ADD",)
]
Output: Error: Program terminated without HALT
Explanation:
The interpreter reaches the end of the instructions without encountering HALT.

Constraints

• The bytecode instructions will be represented as tuples. The first element of the tuple is the instruction mnemonic (a string), and subsequent elements are arguments. For example, ("PUSH", 10). Instructions without arguments are just a single-element tuple, e.g., ("ADD",).
• All values pushed onto the stack will be integers.
• The maximum number of instructions in a program will be 1000.
• The maximum value of an integer pushed onto the stack will be 1,000,000.

Notes

• You can use a Python list as your stack. Remember that list.append() adds to the end, and list.pop() removes from the end, which is typical for stack operations.
• Consider how you will represent your instruction set. A dictionary mapping instruction mnemonics to handler functions or methods is a common approach.
• When implementing SUB, carefully consider the order of popping from the stack to ensure the correct subtraction.
• For simplicity, you don't need to implement complex control flow like jumps or loops in this initial challenge. Focus on the core execution of sequential instructions and stack manipulation.