Answer

I built and verified a complete reference implementation. The deliverable is at ~/solution/SOLUTION.md (self-contained, with code round-trip tested), plus the two runnable files. Here is the solution.

---

Incremental Type-Checking for Nested Modules, Overloaded Operators, and Hygienic Macros

Problem class: py-20261007-hygienic-incremental-typecheck Environment: Python 3.11+ (verified on 3.14) Artifacts: ~/solution/incremental_typecheck.py, ~/solution/test_solution.py, ~/solution/SOLUTION.md

1. Root-cause analysis

Four independent defects make a naive incremental checker unsound or unbounded:

#	Root cause	Why it fails
1	Name-keyed memo caches	Once macros are hygienic, a gensym tmp is a different symbol per expansion. Keying by source name both allows capture and lets a macro-body edit reuse a stale cache entry for a semantically different expansion.
2	Module-granular invalidation	Rechecking only the edited module is unsound (dependents hold old values); rechecking everything is O(program). The minimal sound object is the constraint-level reverse-dependency closure, not modules.
3	Cyclic imports	A↔B has no topological order. Naive propagation loops forever or silently drops one side of the cycle.
4	Concurrent edits	Reading a declaration and its dependent type in two steps can interleave with an edit, yielding a "torn" pair that existed in no program state — a stale diagnostic.

The key insight for (1): hygienic identity must be content-addressed, i.e. (module, name, hygiene_tag) with hygiene_tag = gensym:<sha256(macro def)>:<use-site>. Editing the macro changes the hash, retiring old keys and minting new ones, which automatically invalidates every consumer.

2. The fix — a symbol-versioned constraint store

Core algorithm (abridged; full file is incremental_typecheck.py):

SymbolKey = Tuple[str, str, str]   # (module, name, hygiene_tag)

# --- minimal sound invalidation frontier ------------------------------
def _closure(self, seeds):
    """Reverse-dependency closure: every constraint reachable from seeds."""
    affected, stack = set(), [c for c in seeds if c in self.constraints]
    while stack:
        cid = stack.pop()
        if cid in affected:
            continue
        affected.add(cid)
        for o in self.constraints[cid].outputs:
            for r in self.readers.get(o, ()):
                if r not in affected:
                    stack.append(r)
    return affected

def set_symbol(self, s, value):
    old = self.values.get(s, _MISSING)
    if old is not _MISSING and old == value:
        return False
    self.version[s] = self.version.get(s, 0) + 1
    self.values[s] = value
    self.dirty |= self._closure(self.readers.get(s, set()))
    return True

# --- cyclic imports: Tarjan SCC, sinks-first, bounded fixpoint --------
def recompute(self):
    frontier = {c for c in self.dirty if c in self.constraints}
    self.last_frontier = set(frontier)
    self.nonconverged = []
    for comp in self._scc_order(frontier):     # dependencies first
        if not self._eval_component(comp):     # iterate to fixpoint
            self.nonconverged.append(tuple(comp))   # bounded, reported
    self.dirty = set()
    return len(frontier)

# --- concurrent edits: MVCC read-set validation -----------------------
def get(self, s, default=None):
    with self.engine.lock:
        self.reads[s] = self.engine.version.get(s, 0)
        return self.engine.values.get(s, default)

def commit(self):
    with self.engine.lock:
        for s, v in self.reads.items():
            if self.engine.version.get(s, 0) != v:
                raise StaleReadError(f"stale read of {s}")

Front-end rules that tie it together:

• Hygiene: a macro body sees only its parameter (body_known = {param: g}), where g = (module, f"{name}${param}", f"gensym:{macro.version}:{prefix}").
• Overloaded operators: each module publishes a versioned overload table symbol; every operator application depends on the local + transitively imported tables. Editing an overload dirties exactly the applications that read it.
• Minimality: on edit, constraints are diffed by sha256 signature; unchanged constraints are never re-registered, so they never enter the dirty set.
• Atomicity: update_module holds the engine lock across recompile + recompute, and recompiles only the transitive-importer closure.
• Boundedness: dirty closure is one traversal; SCC evaluation is capped at max_iters with divergence reported; transaction retries are capped.

3. Verification

cd ~/solution
python3 test_solution.py

All 24 checks pass:

[1] minimal sound invalidation frontier
  [ok] answer edit dirties mid.doubled
  [ok] answer edit does NOT dirty mid.hi2
  [ok] unrelated const not rechecked
  [ok] frontier strictly smaller than program (9 < 21)

[2] hygienic macro expansion / identity change
  [ok] macro edit changed gensym identity (old key retired)
  [ok] macro body edit dirties macro consumer
  [ok] user symbol 'twice$x' not captured by gensym (distinct tag)
  [ok] stale success replaced by fresh error diagnostic

[3] cyclic imports bounded and sound
  [ok] a.x resolved inside cycle
  [ok] cyclic update bounded (0.000s)
  [ok] cycle reached a fixpoint

[4] divergent cycle is bounded
  [ok] divergent SCC bounded (0.000s)
  [ok] divergence reported as one non-converged SCC

[5] MVCC prevents stale diagnostics under concurrent edits
  [ok] stale commit rejected by read-set validation
  [ok] no torn (answer, d) pair observed (0 violations)   # 4 readers vs 400 writer edits

I also verified the document is genuinely self-contained: extracting the two fenced code blocks from SOLUTION.md and running them reproduces RESULT: ALL CHECKS PASSED.

Soundness argument for the frontier

Let compute be pure. If every symbol in inputs(c) has an unchanged version since c was last computed, then value(c) is still correct. Hence only constraints transitively reading a bumped symbol can be wrong — exactly _closure. Evaluating that closure in SCC-reverse-topological order, with a fixpoint inside each SCC, guarantees each constraint observes final dependency values. Clean constraints are never recomputed, so the frontier is simultaneously minimal and sound, and the max_iters cap plus Tarjan condensation keeps the worst case bounded even for cyclic imports.

# Evidence
- Problem class: py-20261007-hygienic-incremental-typecheck
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-10-07T10:37:38.835Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build an incremental type-checking engine for a language with nested modules, overloaded operators, and hygienic macros, where an edit may invalidate only a subset of cached constraints but macro expansion can change symbol identity. Compute the minimal sound invalidation frontier and explain how to prevent stale diagnostics under concurrent edits while keeping worst-case behavior bounded for cyclic imports.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "py-20261007-hygienic-incremental-typecheck", "provider": "openrouter", "solved_at": "2026-10-07T10:37:38.835Z", "version": "3.11"}