Decorators, Closures & Function Metaprogramming

In Python, functions are first-class citizens. They are runtime objects instantiated from the built-in function type, possessing internal state, code objects, namespace dictionaries, and lexical environments. This first-class status enables metaprogramming—the paradigm where software inspects, wraps, transforms, and dynamically synthesizes program logic at runtime.

Decorators and closures form the architectural backbone of modern Python frameworks, from routing in FastAPI and Flask to ORM field tracking in SQLAlchemy and automated dependency injection. However, using them effectively in high-concurrency, mission-critical systems requires a deep understanding of CPython runtime internals: the LEGB scoping rules, cell objects, bytecode execution frames, and descriptor binding mechanics.

This guide provides an exhaustive, university-grade architectural analysis of Python closures, decorator patterns, and runtime function metaprogramming. We trace CPython bytecode opcodes, formalize lexical scope cell binding, implement production-grade telemetry decorators, diagnose classic closure pathologies, and solve four comprehensive quantitative checkpoint problems.

1. Lexical Scoping and the Mechanics of CPython Closures#

A closure is a function object that retains access to variables in its enclosing lexical environment, even after the execution frame of the enclosing function has returned and terminated.

+-------------------------------------------------------------------------------------------------+
|                                 CPYTHON CLOSURE MEMORY TOPOLOGY                                 |
|                                                                                                 |
|   Outer Function Execution Frame (Terminated)                                                   |
|   +---------------------------------------------+                                               |
|   | outer_func(x)                               |                                               |
|   |   Stack frame popped off call stack!        |                                               |
|   +---------------------------------------------+                                               |
|                          |                                                                      |
|                          | x promoted to heap cell object                                       |
|                          v                                                                      |
|   [PyCellObject] on Heap                                                                        |
|   +---------------------------------------------+                                               |
|   | ob_refcnt: 2                                |                                               |
|   | ob_type:   &PyCell_Type                     |                                               |
|   | ob_ref:    ---> [PyLongObject: value = 42]  |                                               |
|   +---------------------------------------------+                                               |
|                          ^                                                                      |
|                          | referenced via func.__closure__[0]                                   |
|   Inner Function Object  |                                                                      |
|   +---------------------------------------------+                                               |
|   | inner_func                                  |                                               |
|   |   __closure__ = ( <cell at 0x7f...>, )      |                                               |
|   |   __code__.co_freevars = ('x',)             |                                               |
|   +---------------------------------------------+                                               |
|                                                                                                 |
|   Opcode Execution: LOAD_DEREF 0 (Dereferences Cell Object directly from heap)                   |
+-------------------------------------------------------------------------------------------------+

The LEGB Scoping Rule#

CPython resolves variable identifiers across four nested scopes in strict sequential order:

1. Local (L): Identifiers bound inside the currently executing function (via parameter names, assignment statements, or as targets).
2. Enclosing (E): Identifiers bound in the local scope of any enclosing function definitions from innermost to outermost.
3. Global (G): Identifiers bound at the top level of the current module file.
4. Built-in (B): Identifiers predefined in the builtins module (e.g., len, range, ValueError).

If an identifier is not resolved in any of these four scopes, CPython raises a NameError.

CPython Internal Bytecode: `co_cellvars` and `co_freevars`#

When CPython compiles a function definition containing nested functions, the compiler inspects which local variables are referenced by inner functions:

• If a local variable in the outer function is captured by an inner function, the compiler registers it in __code__.co_cellvars.
• In the inner function, that captured identifier is registered in __code__.co_freevars.

Instead of allocating the variable on the execution frame's ephemeral value stack, CPython allocates a persistent heap-allocated PyCellObject. When the outer function returns and its stack frame is deallocated, the cell object persists in heap memory because the inner function's __closure__ tuple holds an active reference to it.

import dis

def outer(x):
    def inner():
        return x + 10
    return inner

fn = outer(42)
print("Outer cellvars:", outer.__code__.co_cellvars) # ('x',)
print("Inner freevars:", fn.__code__.co_freevars)   # ('x',)
print("Closure cell contents:", fn.__closure__[0].cell_contents) # 42

Inspecting the disassembled bytecode using dis.dis(fn):

  3           0 LOAD_DEREF               0 (x)
              2 LOAD_CONST               1 (10)
              4 BINARY_OP                0 (+)
              8 RETURN_VALUE

The LOAD_DEREF opcode retrieves the reference contained inside the cell object without requiring any global dictionary lookups.

The `nonlocal` Keyword: Rebinding vs. Mutation#

In Python, assignment to a variable identifier inside a function body defaults to creating a local variable unless explicitly declared otherwise. If an inner function assigns to an outer variable without nonlocal, CPython treats it as local, causing an UnboundLocalError:

def make_counter():
    count = 0
    def counter():
        # count += 1  # Raises UnboundLocalError: local variable 'count' referenced before assignment
        nonlocal count
        count += 1
        return count
    return counter

The nonlocal keyword instructs the CPython bytecode compiler to emit STORE_DEREF rather than STORE_FAST, mutating the contents of the heap cell object directly.

The Late-Binding Closure Trap#

A classic Python pathology occurs when creating closures inside loops:

# Pathological Late-Binding
callbacks = []
for i in range(5):
    callbacks.append(lambda: i * 2)

# Execution
results = [cb() for cb in callbacks]
print(results)  # Outputs: [8, 8, 8, 8, 8] instead of [0, 2, 4, 6, 8]!

CPython Root Cause: All five lambda functions capture the exact same single cell object holding the identifier i. The variable i is looked up dynamically when the lambda is called, not when it is defined. By the time the loop completes, the cell object contains i = 4.

Remediation: Force eager binding at definition time using default parameter arguments:

# Fixed via Eager Default Argument Binding
callbacks = [lambda x=i: x * 2 for i in range(5)]
print([cb() for cb in callbacks])  # Outputs: [0, 2, 4, 6, 8]

Because default arguments are evaluated when the function definition executes, the integer value of i is bound immediately to the local parameter x.

2. The Mechanics of Python Decorators#

A decorator is a callable that accepts a function (or class) as an argument, modifies or wraps its behavior, and returns a callable object.

Syntactic Transformation#

The @decorator syntax is pure syntactic sugar. The declaration:

@logging_decorator
def calculate_pnl(portfolio_id, date):
    ...

is evaluated by the CPython parser as an immediate post-definition assignment:

def calculate_pnl(portfolio_id, date):
    ...
calculate_pnl = logging_decorator(calculate_pnl)

Because decorator evaluation occurs at module import time, any code in the outer body of the decorator executes immediately when the module is imported into the Python runtime.

Preserving Metadata: The `functools.wraps` Protocol#

When a decorator replaces a function with an inner wrapper, the original function's introspection metadata is lost:

• fn.__name__ becomes "wrapper".
• fn.__doc__ becomes the wrapper's docstring.
• fn.__module__ points to the decorator's module.
• inspect.signature(fn) reflects (*args, **kwargs).

This metadata destruction breaks documentation generators (Sphinx), serialization tools, and web routing frameworks (FastAPI, Flask) that rely on __name__ for endpoint mapping.

To preserve metadata, decorators must invoke functools.wraps:

import functools
import time

def timing_decorator(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        start = time.perf_counter_ns()
        result = func(*args, **kwargs)
        duration_ns = time.perf_counter_ns() - start
        print(f"Executed {func.__name__} in {duration_ns / 1_000_000:.3f} ms")
        return result
    return wrapper

Internally, functools.wraps calls functools.update_wrapper, which copies WRAPPER_ASSIGNMENTS (__module__, __name__, __qualname__, __doc__, __annotations__) and sets wrapper.__wrapped__ = func. This allows developers to access the underlying undecorated function via fn.__wrapped__.

Decorators with Arguments (Three-Tier Closures)#

When a decorator takes configuration arguments (e.g., @retry(max_attempts=3, backoff_seconds=2)), the expression after @ is an active function call that must return the actual decorator:

def retry(max_attempts=3, backoff_seconds=1.0):
    # Tier 1: Decorator Factory (accepts configuration arguments)
    def decorator(func):
        # Tier 2: The Decorator (accepts target function)
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            # Tier 3: The Execution Wrapper (accepts runtime arguments)
            attempts = 0
            while attempts < max_attempts:
                try:
                    return func(*args, **kwargs)
                except Exception as ex:
                    attempts += 1
                    if attempts >= max_attempts:
                        raise
                    time.sleep(backoff_seconds * (2 ** (attempts - 1)))
        return wrapper
    return decorator

Syntactic transformation: calculate_pnl = retry(max_attempts=5)(calculate_pnl).

3. Advanced Metaprogramming Patterns#

Beyond simple wrapper functions, decorators can be structured as stateful classes, descriptor-aware method interceptors, and high-performance caching proxies.

Class-Based Decorators and the Descriptor Protocol#

A decorator can be implemented as a class implementing __call__. This provides clean object-oriented state accumulation:

class CallCounter:
    def __init__(self, func):
        self.func = func
        self.count = 0
        functools.update_wrapper(self, func)

    def __call__(self, *args, **kwargs):
        self.count += 1
        return self.func(*args, **kwargs)

The Instance Method Binding Trap#

If a class-based decorator is applied to an instance method inside another class, a catastrophic failure occurs:

class AccountService:
    @CallCounter
    def compute_interest(self, principal):
        return principal * 0.05

service = AccountService()
# service.compute_interest(1000)  
# FAILS: TypeError: compute_interest() missing 1 required positional argument: 'principal'

CPython Root Cause: Normal Python functions implement the Descriptor Protocol via function.__get__, which binds the function to the instance (self) to produce a types.MethodType object. However, our CallCounter class does not implement __get__. When accessed via service.compute_interest, Python returns the raw CallCounter instance without passing service as the first argument.

Remediation: Implement the Descriptor Protocol (`__get__`):

import types

class CallCounter:
    def __init__(self, func):
        self.func = func
        self.count = 0
        functools.update_wrapper(self, func)

    def __call__(self, *args, **kwargs):
        self.count += 1
        return self.func(*args, **kwargs)

    def __get__(self, instance, owner=None):
        if instance is None:
            return self
        # Bind the instance to __call__ to produce a bound method
        return types.MethodType(self, instance)

Now, service.compute_interest(1000) correctly passes service as self, supporting both standalone functions and instance methods seamlessly.

4. Production Engineering Case Study: High-Performance Distributed Token-Bucket Rate Limiter#

Consider a mission-critical FinTech payment ingestion gateway handling thousands of requests per second. The engineering organization requires an atomic, low-overhead rate limiting decorator to protect internal settlement engines from traffic spikes.

+-------------------------------------------------------------------------------------------------+
|                               TOKEN BUCKET DECORATOR ARCHITECTURE                               |
|                                                                                                 |
|   Inbound Request: @rate_limit(capacity=100, refill_rate=20.0 tokens/sec)                       |
|                                 |                                                               |
|                                 v                                                               |
|   [Closure State: Lock & Bucket Math]                                                           |
|     1. Elapsed Time = now() - last_refill_timestamp                                             |
|     2. Tokens Added = Elapsed Time * refill_rate                                                |
|     3. Current Tokens = min(capacity, current_tokens + Tokens Added)                             |
|                                 |                                                               |
|                  Is Current Tokens >= Requested?                                                |
|                        /                  \                                                     |
|                      YES                  NO                                                    |
|                      /                      \                                                   |
|       [Deduct 1 Token & Allow]        [Raise RateLimitExceeded Exception]                       |
|       [Execute Wrapped Function]      [Emit Metric: rate_limit.rejected]                        |
+-------------------------------------------------------------------------------------------------+

Production Implementation#

import functools
import time
import threading

class RateLimitExceeded(Exception):
    def __init__(self, retry_after_seconds: float):
        super().__init__(f"Rate limit exceeded. Retry after {retry_after_seconds:.2f} seconds.")
        self.retry_after_seconds = retry_after_seconds

def token_bucket_rate_limit(capacity: int, refill_rate_per_sec: float):
    # Thread-safe in-memory Token Bucket rate limiter decorator.
    # Formula:
    #   Tokens_added = (now - last_refill) * refill_rate_per_sec
    #   Tokens_current = min(capacity, Tokens_previous + Tokens_added)
    def decorator(func):
        lock = threading.Lock()
        tokens = float(capacity)
        last_refill = time.perf_counter()

        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            nonlocal tokens, last_refill
            
            with lock:
                now = time.perf_counter()
                elapsed = now - last_refill
                last_refill = now
                
                # Refill tokens based on elapsed physical time
                tokens = min(float(capacity), tokens + (elapsed * refill_rate_per_sec))
                
                if tokens >= 1.0:
                    tokens -= 1.0
                else:
                    # Calculate required wait time for exactly 1 token to replenish
                    deficit = 1.0 - tokens
                    wait_time = deficit / refill_rate_per_sec
                    raise RateLimitExceeded(retry_after_seconds=wait_time)

            return func(*args, **kwargs)

        # Expose telemetry inspection interface
        def get_telemetry():
            with lock:
                return {"capacity": capacity, "available_tokens": tokens}

        wrapper.get_telemetry = get_telemetry
        return wrapper
    return decorator

5. Anti-Patterns & Common Pitfalls#

The "Decorator Side Effects at Import Time" Anti-Pattern#

Because decorators execute when the module is imported, performing expensive operations (such as opening database connections, fetching remote network secrets, or warming caches) directly in the decorator factory blocks application startup:

# Anti-Pattern: Heavy I/O during import
def validate_remote_license():
    response = requests.get("https://license.internal/verify") # BLOCKS MODULE IMPORT!
    def decorator(func):
        ...

Remediation: Defer all network and database operations to the wrapper invocation phase, or use lazy singleton initialization.

Mutable Default Arguments in Decorators#

Decorators that store state in default parameter lists share that state across all decorated functions in the Python process:

# Anti-Pattern: Shared mutable default across all instances
def audit_trail(events=[]):
    def decorator(func):
        def wrapper(*args, **kwargs):
            events.append(func.__name__) # Shared across all functions decorated with @audit_trail!
            return func(*args, **kwargs)
        return wrapper
    return decorator

Remediation: Use events=None and initialize a dedicated collection inside the decorator factory scope.

6. Checkpoint Practice Problems#

The following four multi-part quantitative problems demonstrate the practical application of closure bytecode introspection, late-binding closure mathematics, class-based descriptor method binding, and LRU cache telemetry modeling. Complete step-by-step solutions follow each problem prompt.

Problem 1: CPython Closure Bytecode Analysis & Cell Object Inspection#

Context:

A senior systems software engineer is auditing an in-memory accumulator factory implemented in Python 3.12:

def make_accumulator(initial_value: int, multiplier: int):
    total = initial_value
    def accumulate(delta: int) -> int:
        nonlocal total
        total = total + (delta * multiplier)
        return total
    return accumulate

acc = make_accumulator(100, 3)

Questions:

1. Identify the identifiers stored in make_accumulator.__code__.co_cellvars and accumulate.__code__.co_freevars.
2. Trace the exact sequence of CPython bytecode instructions executed when acc(5) is called, specifying the stack operations for LOAD_DEREF and STORE_DEREF.
3. Calculate the integer value stored in acc.__closure__[0].cell_contents before and after the execution of acc(5).
4. If a developer removes the nonlocal total statement, what exact exception is raised when acc(5) executes? Explain why at the bytecode opcode level.

Solution:

Step 1: Cellvars and Freevars Identification

• In make_accumulator:

- total is defined locally and mutated by the inner function -> stored in co_cellvars.

- multiplier is a local parameter accessed (read-only) by the inner function -> stored in co_cellvars.

- Therefore, make_accumulator.__code__.co_cellvars = ('multiplier', 'total').

• In accumulate:

- delta is a local parameter -> stored in co_varnames.

- total and multiplier are free variables captured from the enclosing scope -> stored in co_freevars.

- Therefore, accumulate.__code__.co_freevars = ('multiplier', 'total').

Step 2: Bytecode Instruction Trace for `acc(5)`

When acc(5) is invoked, CPython creates a frame with co_varnames = ('delta',) and co_freevars = ('multiplier', 'total').

1. LOAD_DEREF (total): Pushes the PyObject pointer contained in acc.__closure__[1] (total = 100) onto the evaluation stack. [Stack: 100]
2. LOAD_FAST 0 (delta): Pushes the local argument delta (5). [Stack: 100, 5]
3. LOAD_DEREF (multiplier): Pushes the PyObject pointer in acc.__closure__[0] (multiplier = 3). [Stack: 100, 5, 3]
4. BINARY_OP 5 (*): Pops 5 and 3, multiplies them, pushes 15. [Stack: 100, 15]
5. BINARY_OP 0 (+): Pops 100 and 15, adds them, pushes 115. [Stack: 115]
6. STORE_DEREF (total): Pops 115 from the stack and writes its pointer into the heap-allocated total cell object (ob_ref). [Stack: empty]
7. LOAD_DEREF (total): Pushes the reference from total cell object (115). [Stack: 115]
8. RETURN_VALUE: Pops 115 and returns it to the caller.

Step 3: Cell Contents Inspection

• Before execution:

- acc.__closure__[0].cell_contents = 3 (multiplier)

- acc.__closure__[1].cell_contents = 100 (initial total)

• After execution of acc(5):

- Computation: 100 + (5 × 3) = 115.

- acc.__closure__[1].cell_contents = 115.

Step 4: Impact of Removing `nonlocal total`

If nonlocal total is omitted:

• Because line 5 contains an assignment total = ..., the Python compiler classifies total as a Local variable (co_varnames), not a free variable.
• Consequently, line 5 compiles to:

LOAD_FAST (total) followed by STORE_FAST (total).

• When acc(5) executes, the first operation tries to execute LOAD_FAST (total). But no value has been assigned to local total in this frame yet.
• Exception: `UnboundLocalError: cannot access local variable 'total' where it is not associated with a value`.

Problem 2: Late-Binding Closure Evaluation & Scope Isolation#

Context:

An asynchronous microservice builds a list of mathematical transformation pipelines using closures:

def generate_linear_transformers(coefficients):
    transformers = []
    for a in coefficients:
        transformers.append(lambda x: x * a + offset)
    return transformers

offset = 10
coefficients = [2, 4, 6, 8]
pipeline = generate_linear_transformers(coefficients)
offset = 25

Questions:

1. Calculate the outputs of evaluating each of the 4 functions in pipeline with input x = 5.
2. Mathematically identify the number of distinct PyCellObject instances allocated on the heap for the free variable a across the 4 lambda functions.
3. Refactor generate_linear_transformers using a nested closure factory function to guarantee true lexical isolation for a and offset without using default arguments.
4. Calculate the outputs of the refactored pipeline for input x = 5.

Solution:

Step 1: Evaluation of the Naive Pipeline

In the loop:

• a is captured by reference via a single cell object. At the end of the loop, a = 8.
• offset is a global variable. When the functions execute, the global variable offset has been reassigned to 25.

For every function i ∈ \{0, 1, 2, 3\}:

Output = x · a + offset = 5 · 8 + 25 = 40 + 25 = 65.

The pipeline outputs: [65, 65, 65, 65].

Step 2: Cell Object Allocation Count

In generate_linear_transformers, the variable a is a single local variable belonging to the function frame that is captured by all 4 lambdas.

CPython allocates exactly 1 PyCellObject on the heap for a. All 4 lambda closures point to this identical cell memory address:

pipeline[0].__closure__[0] is pipeline[1].__closure__[0] is pipeline[2].__closure__[0] is pipeline[3].__closure__[0] evaluates to True.

Step 3: Refactoring via Closure Factory

To allocate an independent stack frame and distinct heap cell for each coefficient:

def generate_linear_transformers(coefficients, base_offset):
    def make_transformer(coeff, off):
        # A new execution frame is created for each call,
        # producing distinct heap cell objects for coeff and off!
        return lambda x: x * coeff + off

    return [make_transformer(a, base_offset) for a in coefficients]

Step 4: Output of the Refactored Pipeline

Pipeline initialized with coefficients = [2, 4, 6, 8] and base_offset = 10:

• Transformer 0 (a = 2): 5 × 2 + 10 = 20
• Transformer 1 (a = 4): 5 × 4 + 10 = 30
• Transformer 2 (a = 6): 5 × 6 + 10 = 40
• Transformer 3 (a = 8): 5 × 8 + 10 = 50

Outputs: [20, 30, 40, 50]. Subsequent mutation of global offset = 25 has zero effect on the encapsulated closure state.

Problem 3: Class-Based Decorator Method Binding & Descriptor Protocol Integration#

Context:

A telemetry engineer implements an @audit_log class-based decorator:

import functools

class audit_log:
    def __init__(self, func):
        self.func = func
        self.invocation_count = 0
        functools.update_wrapper(self, func)

    def __call__(self, *args, **kwargs):
        self.invocation_count += 1
        print(f"Audit: {self.func.__name__} called {self.invocation_count} times")
        return self.func(*args, **kwargs)

class FinancialReport:
    def __init__(self, account_name):
        self.account_name = account_name

    @audit_log
    def generate_statement(self, period: str):
        return f"Report for {self.account_name}: {period}"

When running:

report = FinancialReport("Treasury")
report.generate_statement("Q3-2026")

The program crashes with:

TypeError: generate_statement() missing 1 required positional argument: 'period'

Questions:

1. Explain why the TypeError occurred, identifying what arguments were actually passed into FinancialReport.generate_statement.
2. Formulate the CPython Descriptor Protocol and show how Python functions normally bind to instance objects (self).
3. Add the complete implementation of __get__ to audit_log so that it seamlessly functions as a decorator for both regular functions and class methods.
4. Verify the behavior of report.generate_statement("Q3-2026") with the corrected decorator.

Solution:

Step 1: Root Cause Analysis of the TypeError

When FinancialReport is defined, the @audit_log decorator replaces the function generate_statement with an instance of audit_log:

FinancialReport.generate_statement = audit_log(generate_statement).

When report.generate_statement("Q3-2026") is invoked:

• Python performs attribute lookup: getattr(report, "generate_statement").
• Because audit_log does not implement __get__, Python returns the raw audit_log instance.
• The call ("Q3-2026") triggers audit_log.__call__(self, "Q3-2026").
• Inside audit_log.__call__, it calls self.func(*args, **kwargs).
• The positional arguments are: args = ("Q3-2026",).
• But the underlying generate_statement function expects two positional arguments: (self, period).
• self was never passed! Hence: missing 1 required positional argument: 'period'.

Step 2: The Descriptor Protocol and Function Binding

A Python function is a descriptor. Its __get__ method is defined in C (func_descr_get):

def __get__(self, instance, owner=None):
    if instance is None:
        return self  # Accessed via class (e.g. FinancialReport.generate_statement)
    return types.MethodType(self, instance)  # Binds instance to first argument!

When accessed via an instance report.generate_statement, MethodType creates a bound method wrapper that prepends instance (report) to the argument tuple before invoking the underlying callable.

Step 3: Corrected Implementation of `audit_log` with `__get__`

import functools
import types

class audit_log:
    def __init__(self, func):
        self.func = func
        self.invocation_count = 0
        functools.update_wrapper(self, func)

    def __call__(self, *args, **kwargs):
        self.invocation_count += 1
        return self.func(*args, **kwargs)

    def __get__(self, instance, owner=None):
        if instance is None:
            # Accessed from class namespace (e.g., FinancialReport.generate_statement)
            return self
        # Return a bound method binding 'instance' as the first positional argument (self)
        return types.MethodType(self, instance)

Step 4: Verification

When report.generate_statement("Q3-2026") is executed:

1. report.generate_statement calls audit_log.__get__(report, FinancialReport).
2. It returns a MethodType wrapping the audit_log instance and report.
3. Invoking the bound method executes audit_log.__call__(report, "Q3-2026").
4. self.func is called with args = (report, "Q3-2026").
5. Returns: "Report for Treasury: Q3-2026".
6. Increments self.invocation_count to 1. Success!

Problem 4: High-Performance In-Memory LRU Cache Decorator with Memory Bounds#

Context:

A data engineering squad is building a custom Least Recently Used (LRU) caching decorator @bounded_lru_cache(max_size=3) for computationally intensive string transformations.

The caching algorithm requirements:

• Implemented using an OrderedDict inside the decorator closure.
• On cache hit: Move accessed entry to the most-recently-used end of the dictionary and return cached value immediately without executing the wrapped function.
• On cache miss: Compute value by calling wrapped function, store entry at the most-recently-used end. If current size exceeds max_size, evict the least-recently-used entry (index 0).
• Telemetry: Maintain cumulative hits, misses, and evictions.

@bounded_lru_cache(max_size=3)
def compute_hash(s: str) -> str:
    return f"hash({s})"

Execution Workload Sequence:

The following queries arrive sequentially:

1. compute_hash("alpha")
2. compute_hash("beta")
3. compute_hash("gamma")
4. compute_hash("alpha")
5. compute_hash("delta")
6. compute_hash("beta")
7. compute_hash("epsilon")

Questions:

1. Trace the exact internal dictionary state (keys in order from least-recently-used to most-recently-used) after each of the 7 requests.
2. Calculate the final cumulative count of hits, misses, and evictions.
3. Compute the Cache Hit Ratio: Hit Ratio = Hits / (Hits + Misses).
4. Write the complete, production-grade Python implementation of bounded_lru_cache.

Solution:

Step 1: Workload Trace

Capacity C = 3. Order maintained from LRU (left) to MRU (right):

• Request 1: `compute_hash("alpha")`

- State: Key "alpha" not in cache -> MISS.

- Execute function -> Store "alpha".

- Cache: ["alpha"] (Size: 1/3)

- Evictions: 0

• Request 2: `compute_hash("beta")`

- State: Key "beta" not in cache -> MISS.

- Execute function -> Store "beta".

- Cache: ["alpha", "beta"] (Size: 2/3)

- Evictions: 0

• Request 3: `compute_hash("gamma")`

- State: Key "gamma" not in cache -> MISS.

- Execute function -> Store "gamma".

- Cache: ["alpha", "beta", "gamma"] (Size: 3/3, at capacity)

- Evictions: 0

• Request 4: `compute_hash("alpha")`

- State: Key "alpha" is in cache -> HIT.

- Move "alpha" to MRU position.

- Cache: ["beta", "gamma", "alpha"] (Size: 3/3)

- Evictions: 0

• Request 5: `compute_hash("delta")`

- State: Key "delta" not in cache -> MISS.

- Capacity exceeded (3 + 1 > 3). Evict LRU key: "beta".

- Store "delta" at MRU.

- Cache: ["gamma", "alpha", "delta"] (Size: 3/3)

- Evictions: 1 ("beta" evicted)

• Request 6: `compute_hash("beta")`

- State: Key "beta" not in cache (was previously evicted) -> MISS.

- Capacity exceeded. Evict LRU key: "gamma".

- Store "beta" at MRU.

- Cache: ["alpha", "delta", "beta"] (Size: 3/3)

- Evictions: 2 ("gamma" evicted)

• Request 7: `compute_hash("epsilon")`

- State: Key "epsilon" not in cache -> MISS.

- Capacity exceeded. Evict LRU key: "alpha".

- Store "epsilon" at MRU.

- Cache: ["delta", "beta", "epsilon"] (Size: 3/3)

- Evictions: 3 ("alpha" evicted)

Final Cache State: ["delta", "beta", "epsilon"].

Step 2: Cumulative Metrics

• Hits: 1 (Request 4)
• Misses: 6 (Requests 1, 2, 3, 5, 6, 7)
• Evictions: 3 (Requests 5, 6, 7)

Step 3: Cache Hit Ratio

Hit Ratio = Hits / (Hits + Misses) = 1 / (1 + 6) = 1 / 7 ≈ 0.1429 (14.29%).

Step 4: Complete Implementation of `bounded_lru_cache`

import functools
from collections import OrderedDict
import threading

def bounded_lru_cache(max_size: int = 128):
    def decorator(func):
        cache = OrderedDict()
        lock = threading.Lock()
        hits = 0
        misses = 0
        evictions = 0

        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            nonlocal hits, misses, evictions
            
            # Construct a hashable cache key
            key = (args, tuple(sorted(kwargs.items())))

            with lock:
                if key in cache:
                    hits += 1
                    cache.move_to_end(key)  # Promote to most-recently-used
                    return cache[key]
                misses += 1

            # Compute value outside lock to prevent blocking concurrent reads
            result = func(*args, **kwargs)

            with lock:
                if key in cache:
                    # Another thread computed it in the interim
                    cache.move_to_end(key)
                    return cache[key]

                cache[key] = result
                if len(cache) > max_size:
                    cache.popitem(last=False)  # Evict least-recently-used (index 0)
                    evictions += 1

            return result

        def cache_info():
            with lock:
                return {
                    "hits": hits,
                    "misses": misses,
                    "evictions": evictions,
                    "curr_size": len(cache),
                    "max_size": max_size
                }

        def cache_clear():
            with lock:
                cache.clear()

        wrapper.cache_info = cache_info
        wrapper.cache_clear = cache_clear
        return wrapper
    return decorator