CMP.15:5 - Archetypal Grounding
CMP.15:5.1 - Find the absent intersection before connecting it
Start with integer expressions Literal, Variable and Add, together with evaluation. Contributor A adds nonrecursive lexical Let and its evaluation. Contributor B independently adds free-variable analysis for the original forms.
| Variant | Evaluation after A’s extension | Free-variable analysis after B’s extension |
|---|---|---|
| Literal | Return its integer. | Return the empty set. |
| Variable | Look up its name in the incoming environment. | Return its name as a singleton set. |
| Add | Evaluate both children and add their values. | Union the children’s free-name sets. |
| Let | Evaluate the value in the incoming environment, then the body with one local binding. | Not yet supplied. |
If the application accepts all four variants for both operations, seven available bodies leave one required pair absent. The joining contributor derives the eighth body as in CMP.15:4.3. For let x = 2 in x + y, evaluation under y = 4 is 6 and free-variable analysis is {y}.
Changing the question to evaluation alone makes the seven-body composition sufficient for that operation. This is a legitimate narrower use, not a repair of the still-unsupported analysis. Changing the binding to recursive Let reopens both its evaluation and free-variable rule.
CMP.15:5.2 - Assemble and run the contributions with exact keys
The following Python 3 example is a complete small realization for finite, well-formed expression trees. Tuple tags stand for already parsed constructors. It has no parser, effects, method replacement or static type checking. Environments are maps from names to integers; missing names raise UnboundName. Set-valued results are compared by membership.
Each contribution is a sequence of explicit bodies. The assembler copies them into a private table, rejects repeated keys and checks any declared required pairs before invoking a handler.
class MissingCase(Exception):
pass
class MissingCoverage(Exception):
pass
class ConflictingCase(Exception):
pass
class UnboundName(Exception):
pass
def lookup(environment, name):
if name not in environment:
raise UnboundName(name)
return environment[name]
def compose(*contributions, required=()):
bodies = {}
for contribution in contributions:
for operation, variant, body in contribution:
key = (operation, variant)
if key in bodies:
raise ConflictingCase(key)
bodies[key] = body
missing = set(required) - bodies.keys()
if missing:
raise MissingCoverage(frozenset(missing))
def run(operation, expression, environment=None):
key = (operation, expression[0])
if key not in bodies:
raise MissingCase(key)
context = {} if environment is None else environment
return bodies[key](run, expression, context)
return run
base = [
("eval", "lit", lambda r, e, env: e[1]),
("eval", "var", lambda r, e, env: lookup(env, e[1])),
("eval", "add",
lambda r, e, env: r("eval", e[1], env) + r("eval", e[2], env)),
]
data_extension = [
("eval", "let",
lambda r, e, env:
r("eval", e[3], {**env, e[1]: r("eval", e[2], env)})),
]
operation_extension = [
("free", "lit", lambda r, e, env: set()),
("free", "var", lambda r, e, env: {e[1]}),
("free", "add",
lambda r, e, env: r("free", e[1]) | r("free", e[2])),
]
joining_contribution = [
("free", "let",
lambda r, e, env: r("free", e[2]) | (r("free", e[3]) - {e[1]})),
]
wrong_join = [
("free", "let",
lambda r, e, env: r("free", e[2]) | r("free", e[3])),
]
old = ("add", ("lit", 2), ("var", "x"))
term = ("let", "x", ("lit", 2),
("add", ("var", "x"), ("var", "y")))
required = {
(operation, variant)
for operation in ("eval", "free")
for variant in ("lit", "var", "add", "let")
}
baseline = compose(base)
partial = compose(base, data_extension, operation_extension)
assert baseline("eval", old, {"x": 3}) == 5
assert partial("eval", term, {"y": 4}) == 6
try:
partial("free", term)
except MissingCase as error:
assert error.args[0] == ("free", "let")
else:
raise AssertionError("The absent body was not reported.")
try:
compose(base, data_extension, operation_extension, required=required)
except MissingCoverage as error:
assert error.args[0] == frozenset({("free", "let")})
else:
raise AssertionError("Coverage checking admitted an absent pair.")
incorrect = compose(base, data_extension, operation_extension,
wrong_join, required=required)
assert incorrect("free", term) == {"x", "y"}
complete = compose(base, data_extension, operation_extension,
joining_contribution, required=required)
assert complete("free", term) == {"y"}
assert complete("eval", term, {"y": 4}) == 6
assert complete("eval", old, {"x": 3}) == baseline("eval", old, {"x": 3})
embedded = ("add", term, ("var", "x"))
assert complete("eval", embedded, {"x": 10, "y": 4}) == 16
assert complete("free", embedded) == {"x", "y"}
outer_name = ("let", "x",
("add", ("var", "x"), ("lit", 1)),
("add", ("var", "x"), ("var", "y")))
assert complete("eval", outer_name, {"x": 10, "y": 4}) == 15
assert complete("free", outer_name) == {"x", "y"}
shadowed = ("let", "x", ("lit", 2),
("let", "x", ("add", ("var", "x"), ("lit", 1)),
("add", ("var", "x"), ("var", "y"))))
assert complete("eval", shadowed, {"y": 4}) == 7
assert complete("free", shadowed) == {"y"}
try:
compose(base, data_extension, operation_extension,
joining_contribution, wrong_join, required=required)
except ConflictingCase as error:
assert error.args[0] == ("free", "let")
else:
raise AssertionError("Two bodies for one pair were accepted.")
The absent pair can be found at use or, when required is supplied, during assembly. The wrong join passes coverage and returns a set, yet fails the semantic requirement. Supplying both joins fails before any handler runs.
An operation can also depend on another operation rather than only on its own recursive calls. Suppose IsClosed(e) asks whether FreeVariables(e) is empty. For each admitted variant, its body calls the assembled free-variable operation: lambda r, e, env: not r("free", e). The required set for this use contains both IsClosed and FreeVariables on all four reachable variants; evaluation is unnecessary. Supplying every IsClosed body without FreeVariables(Let) must therefore fail coverage before execution. This dependency closure is chosen from the bodies’ calls; the assembler does not infer it.
For let x = 2 in x, the correct free-variable join returns the empty set, so IsClosed returns true. The wrong union returns {x}, so IsClosed returns false even though all required bodies are present. Both the missing dependency and the wrong meaning propagate into the receiving operation. Calling a private older analysis would evade the selected join instead of repairing either failure.
The embedded case sends a new Let through an unchanged Add body. Its sibling variable x still reads the outer value 10 because the Let handler extends a copy of its incoming environment. The outer_name and shadowed cases distinguish the binding rules: the value expression sees the incoming binding, while the body sees the new one.
For this grammar, all recursive calls stay within the declared eight pairs. Coverage checking therefore settles absence for these two operations over well-formed trees of the four constructors. It establishes neither the meaning of a body nor static type safety. Arbitrary supplied Python functions could mutate external state or call other operations; those would need an enlarged dependency account and preservation conditions. The induction in CMP.15:4.6, rather than the finite assertions alone, explains preservation for all old trees under the stated pure semantics.
CMP.15:5.3 - Express the same obligation through a typed signature
A static alternative represents a term by its use of constructor operations. Instead of first constructing a stored tree and then dispatching on it, the term receives an algebra: a collection of constructor functions whose common result type R is chosen by the interpretation.
The notation below is typed pseudocode. Base<R> and LetPart<R> are records of functions; & requires both sets of fields. It specifies the constraints a realization must enforce.
Base<R> = {
literal: Integer -> R,
variable: Name -> R,
add: (R, R) -> R
}
LetPart<R> = {
let_: (Name, R, R) -> R
}
old<R>(a: Base<R>): R =
a.add(a.literal(2), a.variable("x"))
extended<R>(a: Base<R> & LetPart<R>): R =
a.let_("x", a.literal(2),
a.add(a.variable("x"), a.variable("y")))
withLet<R>(base: Base<R>, part: LetPart<R>):
Base<R> & LetPart<R> =
{literal = base.literal, variable = base.variable,
add = base.add, let_ = part.let_}
For evaluation, choose R = Environment -> Integer. The result of constructing each subexpression is a function awaiting its environment. This delays lookup until the expression’s binding context is known. Let extend(env,n,k) return a new environment that maps n to k and otherwise agrees with env.
evalBase: Base<Environment -> Integer> = {
literal = k -> (env -> k),
variable = n -> (env -> lookup(env,n)),
add = (f,g) -> (env -> f(env) + g(env))
}
evalLet: LetPart<Environment -> Integer> = {
let_ = (n,v,b) -> (env -> b(extend(env,n,v(env))))
}
For free-variable analysis, choose R = Set<Name>:
freeBase: Base<Set<Name>> = {
literal = k -> {},
variable = n -> {n},
add = (a,b) -> a union b
}
freeLet: LetPart<Set<Name>> = {
let_ = (n,v,b) -> v union (b minus {n})
}
old(freeBase) = {"x"}
extended(withLet(freeBase, freeLet)) = {"y"}
extended(withLet(evalBase, evalLet))({y = 4}) = 6
The expression extended(freeBase) lacks the required let_ field and is rejected in a realization that enforces these record constraints. The operation author can keep freeBase unchanged; the joining contributor supplies freeLet, and the application assembles them with withLet. A wrong freeLet returning v union b has the required type, demonstrating the same semantic limit as the dynamic example.
Here withLet copies only the old constructor functions and supplies one new field, so it does not silently override an old field. A richer composition with overlapping signatures needs its own explicit selection rule. Interface union alone does not combine implementations. The chosen language must also support any promised separate compilation; satisfying these mathematical signatures does not establish how a build system handles dependencies.
This representation suits operations expressible through the supplied constructor algebra. Context-sensitive evaluation works because its result is an environment-taking function. An operation needing raw child identity, multiple interacting analyses or cyclic data can need richer results, additional operations or a different representation. Previously serialized trees require a reader that recognizes the extended syntax and applies the right constructor functions; adding LetPart does not update an old parser.
CMP.15:5.4 - Stop when independent extension has no useful payoff
Suppose a private calculator has the same four constructors and two operations, and one maintainer changes them together. A closed tagged data type with an exhaustive evaluation function and an exhaustive free-variable function makes every required case visible. Adding Let means editing those two functions, deriving exactly the same binding rule and checking the new cases.
That arrangement loses independent addition without edits, but the application does not require it. A registry, separate contribution interfaces and loading rules would add work without removing an obstacle for this maintainer. Keep the closed design.
If a separately maintained analyzer must later add an operation while another team extends the expression language, repeat the comparison. The new independent change requirement can justify interfaces and an external joining module. It still leaves that module’s semantic body to be supplied.