Problem class: incremental-macro-hygiene-20261009 · Language: Python 3.13+
I diagnosed the (empty) workspace, found only /workspace/problem.json, and implemented + verified the engine from scratch. The complete artifact is on disk at /workspace/SOLUTION.md, with the runnable engine at /workspace/solution/macro_engine.py and 17 passing assertions at /workspace/solution/test_engine.py. Below is the solution.
Problem class: incremental-macro-hygiene-20261009 · Language: Python 3.13+
A naive engine fails each requirement through a different shortcut:
gensym counter changes binding identity on every edit (invalidating downstream work); resetting it per run collides. Identity must derive from stable invocation identity, never a mutable counter/offset.let variable can shadow a macro, so expansion must resolve (name, marks) through a lexical environment.(name, frozenset[marks]). Template-introduced ids get the invocation mark; substituted args keep caller marks → no capture, pasted ids stay distinct.InvocationRegistry maps (scope-path, macro-name, ordinal) → stable id. Argument/unrelated edits keep the id, so mark = m<id>:<revision> (binding identity) survives edits.(own_revision, hash(expanded_args), revisions_of_referenced_macros) → minimal invalidation set.gensym. gs:<invocation-mark>:<prefix>:<ordinal-in-template> — deterministic per call site, stable across edits, distinct between calls.origins; rendering records output char ranges.(macro-name, text(instantiated_body)); repeat → E_CYCLE with call path, caught at top level so expand() returns diagnostics.macro_engine.py"""
Incremental, hygienic macro-expansion engine.
Features
--------
* nested lexical scopes and source-level shadowing
* token pasting via ``(paste LHS RHS)``
* generated identifiers via ``(gensym PREFIX)``
* per-invocation hygiene marks that are stable across edits
* dependency-tracked incremental re-expansion (cache + minimal invalidation)
* precise source maps (output char range -> source char ranges)
* expansion-cycle diagnostics with the offending call path
Language (token based, s-expressions)::
(defmacro NAME (P1 P2 ...) BODY) compile-time definition
(let ((V1 E1) (V2 E2) ...) BODY ...) nested lexical scope
(gensym PREFIX) fresh hygienic identifier
(paste LHS RHS) token paste (atoms only)
(NAME ARG ...) macro call if NAME is a macro
atom identifier / number / string
"""
from __future__ import annotations
import hashlib
from dataclasses import dataclass
from typing import Any, Iterable, Optional
# --------------------------------------------------------------------------- #
# Tokens / AST
# --------------------------------------------------------------------------- #
@dataclass(frozen=True)
class Token:
kind: str
text: str
start: int
end: int
marks: frozenset[str] = frozenset()
@dataclass
class Atom:
token: Token
def_scope: Optional["Scope"] = None
origins: tuple[tuple[int, int], ...] = ()
@property
def text(self) -> str:
return self.token.text
@property
def marks(self) -> frozenset[str]:
return self.token.marks
@dataclass
class SList:
children: list[Any]
start: int
end: int
origins: tuple[tuple[int, int], ...] = ()
Node = Atom | SList
def node_text(node: Node) -> str:
if isinstance(node, Atom):
return node.text
return "(" + " ".join(node_text(c) for c in node.children) + ")"
# --------------------------------------------------------------------------- #
# Lexer / parser
# --------------------------------------------------------------------------- #
def tokenize(src: str) -> list[Token]:
toks: list[Token] = []
i, n = 0, len(src)
while i < n:
c = src[i]
if c.isspace():
i += 1
continue
if c == ";":
while i < n and src[i] != "\n":
i += 1
continue
if c in "()":
toks.append(Token("punct", c, i, i + 1))
i += 1
continue
if src.startswith("##", i):
toks.append(Token("punct", "##", i, i + 2))
i += 2
continue
if c == '"':
j = i + 1
while j < n and src[j] != '"':
j += 2 if src[j] == "\\" else 1
j = min(j + 1, n)
toks.append(Token("str", src[i:j], i, j))
i = j
continue
j = i
while j < n and (src[j].isalnum() or src[j] in "_-+*<>=!?/."):
j += 1
if j == i:
j = i + 1
text = src[i:j]
kind = "num" if text[:1].isdigit() else "id"
toks.append(Token(kind, text, i, j))
i = j
toks.append(Token("eof", "", n, n))
return toks
class ParseError(Exception):
pass
def parse(src: str) -> list[Node]:
toks = tokenize(src)
pos = 0
def parse_node() -> Node:
nonlocal pos
t = toks[pos]
if t.kind == "eof":
raise ParseError("unexpected end of input")
if t.text == "(":
start = t.start
pos += 1
children: list[Node] = []
while toks[pos].text != ")":
if toks[pos].kind == "eof":
raise ParseError("unclosed '('")
children.append(parse_node())
end = toks[pos].end
pos += 1
return SList(children, start, end, ((start, end),))
if t.text == ")":
raise ParseError(f"unexpected ')' at {t.start}")
pos += 1
return Atom(t, None, ((t.start, t.end),))
out: list[Node] = []
while toks[pos].kind != "eof":
out.append(parse_node())
return out
# --------------------------------------------------------------------------- #
# Bindings / scopes
# --------------------------------------------------------------------------- #
@dataclass
class MacroDef:
name: str
params: tuple[str, ...]
body: Node
revision: int
def_scope: "Scope"
@dataclass
class Variable:
name: str
marks: frozenset[str]
class Scope:
__slots__ = ("parent", "bindings")
def __init__(self, parent: Optional["Scope"] = None):
self.parent = parent
self.bindings: dict[tuple[str, frozenset[str]], Any] = {}
def bind(self, name: str, marks: frozenset[str], value: Any) -> None:
self.bindings[(name, frozenset(marks))] = value
def lookup(self, name: str, marks: frozenset[str]) -> Any:
key = (name, frozenset(marks))
s: Optional[Scope] = self
while s is not None:
if key in s.bindings:
return s.bindings[key]
s = s.parent
return None
def flatten_macros(self) -> dict[str, "MacroDef"]:
acc: dict[str, MacroDef] = {}
s: Optional[Scope] = self
while s is not None:
for b in s.bindings.values():
if isinstance(b, MacroDef) and b.name not in acc:
acc[b.name] = b
s = s.parent
return acc
# --------------------------------------------------------------------------- #
# Output / diagnostics
# --------------------------------------------------------------------------- #
@dataclass(frozen=True)
class OutToken:
kind: str
text: str
marks: frozenset[str]
origins: tuple[tuple[int, int], ...]
@dataclass
class Diagnostic:
code: str
message: str
span: tuple[int, int]
call_path: tuple[tuple[str, tuple[int, int]], ...] = ()
class ExpansionCycleError(Exception):
def __init__(self, diagnostic: Diagnostic):
super().__init__(diagnostic.message)
self.diagnostic = diagnostic
# --------------------------------------------------------------------------- #
# Persistent invocation identity
# --------------------------------------------------------------------------- #
class InvocationRegistry:
"""Assign a persistent id to each macro invocation fingerprint.
The same fingerprint keeps its id across edits, therefore the hygiene mark
derived from the id is preserved (binding identity survives edits).
"""
def __init__(self) -> None:
self._by_fp: dict[str, list[int]] = {}
self._next = 1
self._pending: dict[str, list[int]] = {}
def begin(self) -> None:
self._pending = {k: list(v) for k, v in self._by_fp.items()}
def get_or_create(self, fp: str) -> int:
bucket = self._pending.get(fp)
if bucket:
return bucket.pop(0)
i = self._next
self._next += 1
return i
def commit(self, assignments: list[tuple[str, int]]) -> None:
d: dict[str, list[int]] = {}
for fp, i in assignments:
d.setdefault(fp, []).append(i)
self._by_fp = d
# --------------------------------------------------------------------------- #
# Expander
# --------------------------------------------------------------------------- #
@dataclass
class CacheEntry:
output: Node
mark: str
referenced: frozenset[str]
args_hash: tuple
@dataclass
class ExpansionResult:
tokens: list[OutToken]
text: str
source_map: dict[tuple[int, int], tuple[tuple[int, int], ...]]
diagnostics: list[Diagnostic]
recomputed: set[int]
reused: set[int]
marks_by_invocation: dict[int, str]
macro_revisions: dict[str, int]
class Expander:
def __init__(self) -> None:
self.registry = InvocationRegistry()
self.cache: dict[int, dict[tuple, CacheEntry]] = {}
self.revision = 0
self.macro_revisions: dict[str, int] = {}
self.macro_bodies: dict[str, str] = {}
# -- public --------------------------------------------------------------
def expand(self, src: str) -> ExpansionResult:
nodes = parse(src)
self.recomputed: set[int] = set()
self.reused: set[int] = set()
self.diags: list[Diagnostic] = []
self.marks_by_invocation: dict[int, str] = {}
self._assignments: list[tuple[str, int]] = []
self._fp_counts: dict[str, int] = {}
self._mark_path: list[str] = []
self._outputs: list[Node] = []
self._sig_stack: list[tuple[str, str, tuple[int, int]]] = []
self.registry.begin()
global_scope = Scope()
for n in nodes:
try:
self._expand_toplevel(n, global_scope)
except ExpansionCycleError:
break
self.registry.commit(self._assignments)
toks = self._flatten(self._outputs)
text, smap = self._render(toks)
return ExpansionResult(
tokens=toks,
text=text,
source_map=smap,
diagnostics=self.diags,
recomputed=set(self.recomputed),
reused=set(self.reused),
marks_by_invocation=dict(self.marks_by_invocation),
macro_revisions=dict(self.macro_revisions),
)
# -- top level -----------------------------------------------------------
def _expand_toplevel(self, n: Node, scope: Scope) -> None:
if isinstance(n, SList) and n.children and isinstance(n.children[0], Atom):
if n.children[0].text == "defmacro":
self._do_defmacro(n, scope)
return
self._outputs.append(self._expand_node(n, scope, []))
def _do_defmacro(self, n: SList, scope: Scope) -> MacroDef:
if len(n.children) != 4:
raise ParseError("(defmacro NAME (PARAMS...) BODY)")
name_atom, params_node, body = n.children[1], n.children[2], n.children[3]
if not isinstance(name_atom, Atom) or not isinstance(params_node, SList):
raise ParseError("malformed defmacro")
name = name_atom.text
params = tuple(c.text for c in params_node.children if isinstance(c, Atom))
body_text = node_text(body)
rev = self.macro_revisions.get(name)
if rev is None or self.macro_bodies.get(name) != body_text:
self.revision += 1
rev = self.revision
self.macro_revisions[name] = rev
self.macro_bodies[name] = body_text
mdef = MacroDef(name, params, body, rev, scope)
scope.bind(name, frozenset(), mdef)
return mdef
# -- expansion -----------------------------------------------------------
def _expand_node(self, n: Node, scope: Scope, stack: list[int]) -> Any:
if isinstance(n, Atom):
return n
if not n.children:
return SList([], n.start, n.end, n.origins)
head = n.children[0]
if isinstance(head, Atom):
h = head.text
if h == "defmacro":
self._do_defmacro(n, scope)
return SList([], n.start, n.end, n.origins)
if h == "let":
return self._expand_let(n, scope, stack)
if h == "gensym":
return self._expand_gensym(n, scope, stack)
if h == "paste":
return self._expand_paste(n, scope, stack)
mdef = self._resolve_macro(head, scope)
if mdef is not None:
return self._expand_macro(mdef, n, scope, stack, head)
children = [self._expand_node(c, scope, stack) for c in n.children]
return SList(children, n.start, n.end, n.origins)
def _resolve_macro(self, atom: Atom, scope: Scope) -> Optional[MacroDef]:
b = scope.lookup(atom.text, atom.marks)
if isinstance(b, MacroDef):
return b
if atom.def_scope is not None:
b = atom.def_scope.lookup(atom.text, frozenset())
if isinstance(b, MacroDef):
return b
b = scope.lookup(atom.text, frozenset())
if isinstance(b, MacroDef):
return b
return None
# . let ..................................................................
def _expand_let(self, n: SList, scope: Scope, stack: list[int]) -> SList:
bindings = n.children[1]
if not isinstance(bindings, SList):
raise ParseError("let expects a binding list")
new_scope = Scope(scope)
expanded_bindings: list[Node] = []
for pair in bindings.children:
if not isinstance(pair, SList) or len(pair.children) != 2:
raise ParseError("let binding must be (name expr)")
var, expr = pair.children
if not isinstance(var, Atom):
raise ParseError("let binding name must be an identifier")
new_scope.bind(var.text, var.marks, Variable(var.text, var.marks))
expanded_bindings.append(
SList([var, self._expand_node(expr, scope, stack)],
pair.start, pair.end, pair.origins)
)
body = [self._expand_node(b, new_scope, stack) for b in n.children[2:]]
blist = SList(expanded_bindings, bindings.start, bindings.end, bindings.origins)
return SList([n.children[0], blist, *body], n.start, n.end, n.origins)
# . gensym ...............................................................
def _expand_gensym(self, n: SList, scope: Scope, stack: list[int]) -> Atom:
prefix = (n.children[1].text
if len(n.children) > 1 and isinstance(n.children[1], Atom)
else "g")
inv = stack[-1] if stack else 0
mark = f"gs:{inv}:{prefix}:{n.start}"
return Atom(Token("id", f"{prefix}__{_short_hash(mark)}", n.start, n.end,
frozenset({mark})), scope, n.origins)
# . paste ................................................................
def _expand_paste(self, n: SList, scope: Scope, stack: list[int]) -> Atom:
if len(n.children) != 3:
raise ParseError("(paste LHS RHS) expects two arguments")
l, r = n.children[1], n.children[2]
if not isinstance(l, Atom) or not isinstance(r, Atom):
raise ParseError("paste arguments must be atoms")
inv = stack[-1] if stack else 0
mark = f"paste:{inv}:{n.start}"
origins = tuple(dict.fromkeys(l.origins + r.origins)) or n.origins
return Atom(Token("id", l.text + r.text, n.start, n.end,
l.marks | r.marks | frozenset({mark})), scope, origins)
# . macro call ...........................................................
def _expand_macro(
self, mdef: MacroDef, call: SList, scope: Scope,
stack: list[int], head: Atom,
) -> Node:
fp = self._call_fingerprint(call)
inv_id = self.registry.get_or_create(fp)
self._assignments.append((fp, inv_id))
args = [self._expand_node(a, scope, stack) for a in call.children[1:]]
args_hash = tuple(_fingerprint_canon(a) for a in args)
referenced = self._free_referenced_macros(mdef)
dep_revs = tuple(
sorted((self.macro_revisions.get(n, 0), n) for n in referenced)
)
key = (mdef.revision, args_hash, dep_revs)
entries = self.cache.setdefault(inv_id, {})
entry = entries.get(key)
if entry is not None:
self.reused.add(inv_id)
self.marks_by_invocation[inv_id] = entry.mark
return entry.output
mark = f"m{inv_id}:{mdef.revision}"
self.marks_by_invocation[inv_id] = mark
bindings = dict(zip(mdef.params, args))
stack.append(inv_id)
self._mark_path.append(mark)
try:
instantiated = self._instantiate(mdef.body, bindings, mark, mdef.def_scope, [0])
sig = (mdef.name, node_text(instantiated))
for idx, (n, b, sp) in enumerate(self._sig_stack):
if (n, b) == sig:
path = tuple(
(nm, (spn[0], spn[1]))
for nm, _b, spn in self._sig_stack[idx:]
) + ((mdef.name, (call.start, call.end)),)
diag = Diagnostic(
"E_CYCLE",
"expansion cycle: " + " -> ".join(p[0] for p in path),
(call.start, call.end),
path,
)
self.diags.append(diag)
raise ExpansionCycleError(diag)
self._sig_stack.append((mdef.name, sig[1], (call.start, call.end)))
try:
use_scope = _MergeScope(scope, mdef.def_scope)
expanded = self._expand_node(instantiated, use_scope, stack)
finally:
self._sig_stack.pop()
finally:
self._mark_path.pop()
stack.pop()
self.recomputed.add(inv_id)
entries[key] = CacheEntry(expanded, mark, referenced, args_hash)
return expanded
def _call_fingerprint(self, call: SList) -> str:
# Identity is based on the macro name and its position/context, *not*
# on the arguments. Editing an argument therefore re-uses the same
# invocation id, so the hygiene marks (binding identity) derived from
# it survive the edit.
name = (call.children[0].text
if call.children and isinstance(call.children[0], Atom)
else "?")
base = "|".join(self._mark_path) + "::" + name
n = self._fp_counts.get(base, 0)
self._fp_counts[base] = n + 1
return f"{base}@{n}"
def _free_referenced_macros(self, mdef: MacroDef) -> frozenset[str]:
names = _free_names(mdef.body, set(mdef.params))
macros = mdef.def_scope.flatten_macros()
return frozenset(n for n in names if n in macros)
# . instantiation (template substitution + hygiene) ......................
def _instantiate(
self, node: Node, bindings: dict[str, Node], mark: str,
def_scope: Scope, gs_counter: list[int],
) -> Node:
if isinstance(node, Atom):
if node.text in bindings:
return bindings[node.text]
return Atom(
Token(node.token.kind, node.token.text,
node.token.start, node.token.end,
node.token.marks | frozenset({mark})),
def_scope, node.origins,
)
if node.children and isinstance(node.children[0], Atom):
h = node.children[0].text
if h == "gensym":
prefix = (node.children[1].text
if len(node.children) > 1 and isinstance(node.children[1], Atom)
else "g")
gs_counter[0] += 1
key = f"gs:{mark}:{prefix}:{gs_counter[0]}"
return Atom(Token("id", f"{prefix}__{_short_hash(key)}",
node.start, node.end, frozenset({key})),
def_scope, node.origins)
if h == "paste":
kids = [self._instantiate(c, bindings, mark, def_scope, gs_counter)
for c in node.children]
if all(isinstance(k, Atom) for k in kids[1:]):
parts = "".join(k.text for k in kids[1:])
marks: frozenset[str] = frozenset()
for k in kids[1:]:
marks |= k.marks
return Atom(Token("id", parts, node.start, node.end, marks),
def_scope, node.origins)
return SList(kids, node.start, node.end, node.origins)
if h == "let":
kids: list[Node] = [node.children[0]]
binds = node.children[1]
new_binds = [self._instantiate(p, bindings, mark, def_scope, gs_counter)
for p in binds.children]
kids.append(SList(new_binds, binds.start, binds.end, binds.origins))
kids.extend(self._instantiate(c, bindings, mark, def_scope, gs_counter)
for c in node.children[2:])
return SList(kids, node.start, node.end, node.origins)
if h == "defmacro":
return node
return SList(
[self._instantiate(c, bindings, mark, def_scope, gs_counter)
for c in node.children],
node.start, node.end, node.origins,
)
# . output .................................................................
def _flatten(self, nodes: Iterable[Node]) -> list[OutToken]:
out: list[OutToken] = []
for n in nodes:
self._flatten_one(n, out)
return out
def _flatten_one(self, n: Node, out: list[OutToken]) -> None:
if isinstance(n, Atom):
t = n.token
out.append(OutToken(t.kind, t.text, t.marks,
n.origins or ((t.start, t.end),)))
return
if not n.children:
return
out.append(OutToken("punct", "(", frozenset(), n.origins or ((n.start, n.end),)))
for c in n.children:
self._flatten_one(c, out)
out.append(OutToken("punct", ")", frozenset(), n.origins or ((n.start, n.end),)))
def _render(self, toks: list[OutToken]):
parts: list[str] = []
smap: dict[tuple[int, int], tuple[tuple[int, int], ...]] = {}
pos = 0
prev: Optional[OutToken] = None
for t in toks:
if prev is not None and _needs_space(prev, t):
parts.append(" ")
pos += 1
start = pos
parts.append(t.text)
pos += len(t.text)
smap[(start, pos)] = t.origins
prev = t
return "".join(parts), smap
# --------------------------------------------------------------------------- #
# helpers
# --------------------------------------------------------------------------- #
class _MergeScope(Scope):
"""Caller scope first, then macro-definition scope."""
def __init__(self, primary: Scope, secondary: Scope):
super().__init__(None)
self._primary = primary
self._secondary = secondary
def lookup(self, name: str, marks: frozenset[str]) -> Any:
key = (name, frozenset(marks))
s: Optional[Scope] = self._primary
while s is not None:
if key in s.bindings:
return s.bindings[key]
s = s.parent
s = self._secondary
while s is not None:
if key in s.bindings:
return s.bindings[key]
s = s.parent
return None
def _short_hash(s: str) -> str:
return hashlib.sha1(s.encode("utf-8")).hexdigest()[:8]
def _needs_space(a: OutToken, b: OutToken) -> bool:
if a.text == "(":
return False
if b.text == ")":
return False
if a.text == ")":
return False
return True
def _fingerprint_canon(n: Any) -> str:
if isinstance(n, Atom):
return f"{n.text}{sorted(n.marks)}"
if isinstance(n, list):
return "(" + " ".join(_fingerprint_canon(c) for c in n) + ")"
return "(" + " ".join(_fingerprint_canon(c) for c in n.children) + ")"
_BINDING_FORMS = {"let"}
def _free_names(node: Node, bound: set[str]) -> set[str]:
"""Identifiers in a template not introduced by a local ``let``/params."""
if isinstance(node, Atom):
return {node.text} if node.token.kind == "id" else set()
if not node.children:
return set()
head = node.children[0]
if isinstance(head, Atom) and head.text in _BINDING_FORMS and len(node.children) >= 2:
binds = node.children[1]
new_bound = set(bound)
if isinstance(binds, SList):
for pair in binds.children:
if isinstance(pair, SList) and pair.children and isinstance(pair.children[0], Atom):
new_bound.add(pair.children[0].text)
free: set[str] = set()
for body in node.children[2:]:
free |= _free_names(body, new_bound)
# expressions of the bindings are evaluated in the outer scope
if isinstance(binds, SList):
for pair in binds.children:
if isinstance(pair, SList) and len(pair.children) == 2:
free |= _free_names(pair.children[1], bound)
return free
free = set()
for c in node.children:
free |= _free_names(c, bound)
return free
cd solution && python3 test_engine.py
The suite asserts: basic expansion; nested scopes + macro shadowing by a variable; hygiene (introduced identifiers share a fresh mark, caller identifiers unmarked → no capture); token pasting; gensym; E_CYCLE diagnostics with the a -> b -> a path; source-map accuracy; incremental reuse; minimal invalidation when a different macro's definition changes; transitive nested-macro invalidation; distinct per-call gensyms; and binding identity preserved across an argument edit.
Observed output (all 17 assertions pass):
PASS basic-expansion (+ 4 1)
PASS shadow-no-expand-inside (let ((bar 5))(+ 1 10))(+ 2 10)
PASS shadow-outside-expands (let ((bar 5))(+ 1 10))(+ 2 10)
PASS hygiene-4-tmps (let ((tmp 1))(let ((tmp 99))(list tmp tmp)))[frozenset(), frozenset({'m1:1'}), frozenset({'m1:1'}), frozenset()]
PASS hygiene-introduced-two-share
PASS hygiene-caller-unmarked
PASS paste foobar
PASS gensym-runs
PASS cycle-diagnostic ['expansion cycle: a -> b -> a']
path: ['a', 'b', 'a']
PASS sourcemap-arg [((32, 33),)]
PASS first-pass-recomputed-2 {1, 2}
PASS incremental-reuse reused={2} recomputed={1}
PASS stable-gensym-id {'z__899a10b7'} vs {'z__899a10b7', 'z__b2a1e038'}
PASS minimal-def-invalidation recomputed={1} reused={2}
PASS nested-dependency-invalidation text=(+ 5 100) recomputed={1, 2}
PASS gensym-distinct-per-call ['t__df8e3df0', 't__dca55a17']
PASS arg-edit-preserves-identity {'z__899a10b7'} vs {'z__899a10b7'} recomputed={1}
FAILURES: 0
Additional check: both Python blocks extracted from /workspace/SOLUTION.md compile independently, and python3 test_engine.py exits 0.
# Evidence - Problem class: incremental-macro-hygiene-20261009 - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-09T11:15:05.823Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an incremental macro-expansion engine for a language with nested scopes, token pasting, generated identifiers, and source-level shadowing, where edits may invalidate only a subset of prior expansions. Preserve hygienic binding identity across edits while producing minimal invalidation sets, and return precise source maps and diagnostics when expansion cycles occur.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "incremental-macro-hygiene-20261009", "provider": "openrouter", "solved_at": "2026-10-09T11:15:05.826Z", "version": "3.13"}