turner-townsend-backend-assessment/stack/README.md

# Stack

Original assessment brief: https://github.com/turner-townsend/backend-assessment/blob/master/README.md#stack

A Python implementation of the Fifth stack-based programming language, demonstrating clean code practices, robust error handling, and modern Python features.

## What is Fifth?

Fifth is a stack-based language that operates on a stack of integers. All operations work with the top elements of the stack, following the last-in-first-out (LIFO) principle. This implementation provides an interactive REPL (read-eval-print loop) for executing Fifth commands.

## Features

- **Stack operations**: `PUSH`, `POP`, `SWAP`, `DUP`
- **Arithmetic operations**: `+`, `-`, `*`, `/` (floor division)
- **Comprehensive error handling**: Input validation, stack state checking, and clear error messages
- **Interactive REPL**: Command-line interface with readline support for command history (↑/↓)
- **Case-insensitive commands**: Commands work in both upper and lowercase

## Installation and usage

### Requirements

- Python 3.9+ (uses modern type hint syntax `list[int]`)
- No external dependencies

### Running the interpreter

```bash
python <filename>.py
```

The interpreter will start with a help message and enter interactive mode, displaying the current stack state before each command.

## Commands reference

| Command    | Description                 | Stack effect                  | Example   |
| ---------- | --------------------------- | ----------------------------- | --------- |
| `PUSH <n>` | Push integer n onto stack   | `[] → [n]`                    | `PUSH 42` |
| `POP`      | Remove top element          | `[..., n] → [...]`            | `POP`     |
| `SWAP`     | Swap top two elements       | `[..., a, b] → [..., b, a]`   | `SWAP`    |
| `DUP`      | Duplicate top element       | `[..., n] → [..., n, n]`      | `DUP`     |
| `+`        | Add top two elements        | `[..., a, b] → [..., (a+b)]`  | `+`       |
| `-`        | Subtract (second - top)     | `[..., a, b] → [..., (a-b)]`  | `-`       |
| `*`        | Multiply top two elements   | `[..., a, b] → [..., (a*b)]`  | `*`       |
| `/`        | Floor divide (second / top) | `[..., a, b] → [..., (a//b)]` | `/`       |
| `HELP`     | Show available commands     | No change                     | `HELP`    |
| `EXIT`     | Quit the program            | -                             | `EXIT`    |

### Example session

```
Available commands: HELP, PUSH, POP, SWAP, DUP
Available operations: +, -, *, /
stack is []
PUSH 3
stack is [3]
PUSH 11
stack is [3, 11]
+
stack is [14]
DUP
stack is [14, 14]
PUSH 2
stack is [14, 14, 2]
*
stack is [14, 28]
SWAP
stack is [28, 14]
/
stack is [2]
+
ERROR: two numbers required
POP
stack is []
exit
```

## Tests

Run the test suite:

```bash
pytest -v
```

Example output:

```shell
➜  stack git:(main) ✗ pytest -v
================================================================ test session starts ================================================================
platform linux -- Python 3.12.2, pytest-8.3.4, pluggy-1.5.0 -- /home/jamey/.venv/bin/python
cachedir: .pytest_cache
rootdir: /home/jamey/Projects/turner-townsend-backend-assessment/stack
plugins: mock-3.14.0, asyncio-0.21.2
asyncio: mode=Mode.STRICT
collected 22 items

test_stack.py::test_push_and_pop PASSED                                                                                                       [  4%]
test_stack.py::test_push_invalid_value PASSED                                                                                                 [  9%]
test_stack.py::test_pop_empty_stack PASSED                                                                                                    [ 13%]
test_stack.py::test_swap PASSED                                                                                                               [ 18%]
test_stack.py::test_swap_insufficient_elements PASSED                                                                                         [ 22%]
test_stack.py::test_dup PASSED                                                                                                                [ 27%]
test_stack.py::test_dup_empty_stack PASSED                                                                                                    [ 31%]
test_stack.py::test_addition PASSED                                                                                                           [ 36%]
test_stack.py::test_subtraction PASSED                                                                                                        [ 40%]
test_stack.py::test_multiplication PASSED                                                                                                     [ 45%]
test_stack.py::test_division PASSED                                                                                                           [ 50%]
test_stack.py::test_division_by_zero PASSED                                                                                                   [ 54%]
test_stack.py::test_binary_op_insufficient_elements PASSED                                                                                    [ 59%]
test_stack.py::test_execute_unknown_command PASSED                                                                                            [ 63%]
test_stack.py::test_execute_push_command PASSED                                                                                               [ 68%]
test_stack.py::test_execute_pop_command PASSED                                                                                                [ 72%]
test_stack.py::test_execute_swap_command PASSED                                                                                               [ 77%]
test_stack.py::test_execute_dup_command PASSED                                                                                                [ 81%]
test_stack.py::test_help PASSED                                                                                                               [ 86%]
test_stack.py::test_execute_empty_command PASSED                                                                                              [ 90%]
test_stack.py::test_execute_whitespace_command PASSED                                                                                         [ 95%]
test_stack.py::test_case_insensitivity PASSED                                                                                                 [100%]

================================================================ 22 passed in 0.03s =================================================================
```

## Design decisions and architecture

### Core design philosophy

The implementation prioritises **clarity and maintainability** over performance optimisation, following the principle of being "explicit over implicit" and "discoverable over performant" as requested in the brief.

### Key architectural choices

#### 1. Class-based structure (`FifthStack`)

- **Reasoning**: Encapsulates state (the stack) with behaviour (operations), making the code more organised and testable
- **Alternative considered**: Functional approach with global state, rejected for testing difficulties and state management complexity

#### 2. Command dictionary pattern

```python
self.commands: dict[str, Callable] = {
    "help": self.help,
    "push": self.push,
    # ...
}
```

- **Reasoning**: Makes adding new commands trivial and eliminates long if/elif chains
- **Benefit**: Extensible design - new commands require only adding to the dictionary
- **Trade-off**: Slight memory overhead for the dictionary, but gains significant maintainability

#### 3. Separate binary operations dictionary

```python
self.binary_ops: dict[str, Callable[[int, int], int]] = {
    "+": operator.add,
    # ...
}
```

- **Reasoning**: Leverages Python's `operator` module for built-in mathematical operations
- **Benefit**: Consistent behaviour with Python's arithmetic, less error-prone than custom implementations
- **Design**: Separate from commands because they have different signatures and error handling needs

#### 4. Method extraction for each operation

Each stack operation is implemented as a separate method rather than inline logic:

- **Testing**: Each operation can be unit tested independently
- **Debugging**: Stack traces clearly identify which operation failed
- **Extensibility**: New operations are self-contained and don't affect existing code
- **Readability**: Each method has a single, clear responsibility

#### 5. Defensive programming with `_require()` helper

```python
def _require(self, number, message):
    if len(self.stack) < number:
        print(f"ERROR: {message}")
        return False
    return True
```

- **Reasoning**: Centralizes stack size validation logic
- **Benefit**: Consistent error messages and reduces code duplication
- **DRY principle**: Single source of truth for stack requirement checking

#### 6. Error recovery strategy

- **Division by zero**: Restores original stack state (`self.stack.extend([a, b])`)
- **Invalid input**: Provides clear error messages without crashing
- **Insufficient stack**: Fails gracefully with descriptive messages
- **Reasoning**: Interpreter should be robust and not crash on user errors

#### 7. Modern Python features used

**Type hints with generic collections (Python 3.9+)**:

```python
self.stack: list[int] = []
```

- **Reasoning**: Improves code readability and enables better IDE support
- **Choice**: Used `list[int]` instead of `typing.List[int]` for cleaner, modern syntax

**Input processing centralization**:

```python
def _normalize_input(self, command: str) -> list[str]:
    return command.lower().strip().split()
```

- **Reasoning**: Single source of truth for command normalization and tokenization
- **Benefit**: Both REPL and direct execution paths use identical processing logic
- **Design choice**: Avoided walrus operator in favour of explicit method extraction for better testability and clarity

**f-string formatting**:

- **Reasoning**: More readable than `.format()` or `%` formatting
- **Performance**: Faster than alternative string formatting methods

#### 8. REPL design choices

**Stack display**: Shows stack state after each command

- **Reasoning**: Follows the specified output format from the brief
- **Implementation choice**: Used Python's native list representation for consistency with the expected format
- **Benefit**: Maintains familiar syntax for Python developers while meeting requirements

**Case insensitive commands**:

```python
command.lower().strip().split()
```

- **Reasoning**: More user-friendly, follows principle of least surprise
- **Benefit**: Reduces user errors from capitalisation mistakes

**Graceful exit**: Handles both `exit` command and Ctrl+C/EOF

- **Reasoning**: Proper CLI applications should handle interrupts gracefully
- **Implementation**: Try/catch for `EOFError` and `KeyboardInterrupt`

### Alternative approaches considered

1. **Parser-based approach**: Could have used a formal parser (e.g. PLY), but rejected as over-engineering for this simple language

2. **Functional approach**: Could have used pure functions with immutable data but rejected because:

   - Stack operations naturally mutate state
   - Would require returning new stack state from every function
   - Less intuitive for this particular problem domain

3. **Command pattern with classes**: Could have made each command a separate class but rejected due to:

   - Unnecessary complexity for simple operations
   - Would require more boilerplate code
   - Current approach is more discoverable

4. **eval() for arithmetic**: Could have used `eval()` for mathematical expressions but rejected due to:
   - Security concerns
   - Need for custom stack-based evaluation order
   - Loss of control over error handling

### Testing strategy

The design facilitates testing through:

- **Isolated methods**: Each operation can be tested independently
- **Dependency injection**: Stack state can be set up for specific test scenarios
- **Clear return values**: Methods have predictable behaviour and side effects
- **Error conditions**: All error paths are reachable and testable

### Extensibility

Adding new features is straightforward:

- **New commands**: Add to `self.commands` dictionary and implement method
- **New operators**: Add to `self.binary_ops` dictionary
- **New data types**: Modify type hints and validation logic
- **New output formats**: Modify display logic in main loop

This architecture balances simplicity with software engineering practices, to keep the code readable and maintainable.