CMP.15:4 - Solution
Construct the semantic intersection before relying on the mechanism that binds it. Use the same required combinations to choose a representation, assemble contributions, qualify their guarantees and compare a simpler alternative. CMP.15:5 develops one binding example in executable and typed forms; these are alternative realizations of the method.
CMP.15:4.1 - Select the two extension axes and required combinations
Name the data variants and the operations separately. For an expression language, Literal, Variable, Add and Let are variants; evaluation and free-variable analysis are operations. A variant description gives its fields and their meaning, including which fields contain further expressions and where a name is bound. An operation description gives its inputs, result and intended meaning.
Choose the receiving application before requiring every conceivable combination. An evaluator may accept Let while an exporter intentionally accepts only arithmetic expressions. That restriction can be adequate if inputs are checked before export and the unsupported case is reported. If the exporter promises the full language, the missing Let case is an unfulfilled obligation.
For finite sets of variants V and operations O, let R be the required pairs drawn from O × V. Obtain R from admitted inputs and reachable calls, not just the constructors seen at the roots of sample expressions. An old Add can contain a new Let. An operation can invoke another operation, so its dependencies may enlarge the required set. For mutually recursive operations, continue following these dependencies until no new required pair appears.
A conservative complete set is often cheaper than proving that a difficult pair is unreachable. When reachability depends on arbitrary program behavior, a small collection of successful runs does not settle it. Restrict the admitted input language, require an explicit capability before the call, or retain a checked failure before consequential effects. State which choice bounds the use.
Reuse adequate constructor meanings and operation rules. If these remain unclear, use CMP.12:4.1–4.2 to construct the interpretation; NOT.2 and NOT.3 supply expression structure and meaning when the notation itself is being designed. Return the resulting rules to this composition rather than inferring them from a dispatch key.
CMP.15:4.2 - Assign and provide the joining contribution
A data-extension author supplies the new variant and the operations that the extension promises. An operation-extension author supplies that operation for the variants it promises. For a required intersection unknown to both, one contributor who understands both agreements supplies the missing body. This can be either author or the application’s integrator. The application must have a way to obtain that body; merely naming a future contributor leaves the combination unsupported.
The joining contribution contains an implementation and the grounds for using it: the accepted variant, operation meaning, required context, dependent operations and a case that distinguishes it from a plausible wrong implementation. Place it in a module that can depend on both additions without making either old module depend on its future users. The original contributions remain independently usable on their established cases.
Shared construction can replace many individually written bodies when its law applies. A structural fold, for example, combines results already obtained for children. It is useful when that summary suffices for the operation. Binding, control, object identity or effects can require additional information or a different recursion. Establish what the generic rule preserves before deriving a new intersection from it.
Check whether the implementation environment permits the intended contribution. Some languages restrict implementation of an externally defined interface for an externally defined type. A local wrapper, an explicit object containing the operations, or a contribution maintained by one interface owner can then provide the join. These choices change representation, calling conventions or maintenance; they do not remove the semantic obligation.
When the contributions will be supplied as independently maintained extensions, use SYSE.27 to arrange a reproducible contribution, its dependencies and its support. Bring that obtainable implementation back here. Package availability is necessary for execution but does not establish the meaning of its operations.
CMP.15:4.3 - Derive the new operation from the variant’s meaning
Consider the nonrecursive lexical construct Let(name, value, body). The value is evaluated in the incoming environment; the name is then bound locally while evaluating the body. The binding does not govern occurrences inside its own value expression.
Free-variable analysis returns the names with lexically free occurrences. It is not, in general, the smallest set of external values on which a particular execution depends. For the old forms its rules are:
FV(Literal(k)) = {}
FV(Variable(n)) = {n}
FV(Add(a,b)) = FV(a) union FV(b)
To derive the missing rule, divide the occurrences by field. Every free occurrence in value remains free in the whole Let, because the new binding does not reach that field. In body, the new binding captures free occurrences of its own name; other free occurrences remain free. Therefore:
FV(Let(n,v,b)) = FV(v) union (FV(b) minus {n})
For let x = 2 in x + y, the value contributes no free names and the body contributes {x,y}; removing the body’s bound x leaves {y}. Unioning every child’s result would return {x,y}. Both results are sets of names, so an ordinary result-type check cannot choose between them.
The location of the subtraction matters. For let x = x + 1 in x + y, the x in the value refers to the incoming environment. The whole expression has free names {x,y}. Subtracting x after unioning both fields would incorrectly return only {y}.
For another constructor, repeat this derivation from its rules. A recursive binding has different scope; a branch may require preserving which child is evaluated; a graph analysis may require identity and a fixed-point computation. Use the relevant CMP.12 interpretation or other supplied operation to obtain those facts, then implement the intersection. A common syntax shape alone does not justify copying this Let rule.
CMP.15:4.4 - Bind one applicable body and keep recursion open
Assemble contributions under an explicit selection rule. The simplest rule uses an exact pair (operation, variant). Reject two bodies for the same pair unless the composition explicitly selects one before assembly. Silently letting the last loaded body win makes loading order a semantic decision.
If selection uses subtyping or predicates, determine which bodies apply and how one is chosen. No applicable body means missing support. Several applicable bodies can be acceptable when one is uniquely more specific under the declared rule; incomparable best candidates leave ambiguity. An explicit body for their intersection, a restriction of applicability or an explicit composition-level choice can resolve it. Each repair still needs a semantic justification.
For recursive data, pass recursive requests through the assembled operation. One simple interface is:
run(operation, expression, context):
body = select(operation, expression.variant)
return body(run, expression, context)
The body receives run as its recursive entry. Thus an old Add handler can process a Let child using the new body selected by this composition. Calling a private old evaluator from that handler would close recursion over the old cases and defeat the extension. For an algebraic construction that receives already interpreted children, the parameterized algebra performs the corresponding composition during term construction; CMP.15:5.3 shows that alternative.
Connect dependencies between operations in the same manner. If an analysis calls a printer, choose which printer it uses, its required variants and the result it returns. If the analysis still calls its obsolete private printer, redirect that dependency to the selected printer.
Keep the composed selection stable for the execution being qualified. With a copied exact-key table, later additions to a source collection need not alter that table. Shared mutable state inside a handler still can alter behavior. If the application replaces methods during an execution, qualify visibility and interaction through CMP.14 rather than assuming that a successful assembly settles them.
CMP.15:4.5 - Choose checking and binding conditions separately
Choose when contributions become connected and when the required obligations are checked. These are distinct decisions: dynamic composition can carry static constraints, and early registration can still leave semantic errors until execution.
| Needed guarantee | What must support it |
|---|---|
| Old source modules remain unchanged | The extension and joining modules use published interfaces; composition happens outside the old modules. |
| Modules can be checked and compiled separately | The language and build arrangement expose sufficient interfaces, constraints and dependency information without requiring all implementation sources together. |
| A required missing body is found before execution | A static capability requirement or a complete composition check covers the admitted combinations and their dependencies. |
| Old behavior is preserved | Old calls retain suitable bodies and assumptions, with an argument over the observations promised. |
A static realization can express each operation as an implementation of a constructor signature. A term using Let requires that extended signature. An implementation of only the old signature cannot be supplied to it without failing the relevant type requirement. CMP.15:5.3 gives the bodies and the rejected combination. This establishes availability and type compatibility only to the extent enforced by the chosen language; an unchecked cast can conceal the missing obligation. Correctly typed but wrong FV(Let) remains possible.
A dynamic realization can collect explicit bodies, reject conflicts and compare their keys with R before running any handler. Missing pairs then fail during composition rather than halfway through an effectful operation. The check is complete for R; it covers the application only if R covers its reachable uses. Guard calls outside that scope. Loading another extension requires constructing or qualifying another composition.
Keep three failures distinct:
| Failure | Diagnosis and useful repair |
|---|---|
| No applicable implementation | Supply the missing body, make an existing body available, or narrow the admitted use explicitly. |
| No unique selected implementation | Resolve the conflict or ambiguity by a stated selection, applicability or intersection rule. |
| One selected implementation returns the wrong meaning | Repair its semantic rule and dependent uses; availability and ordinary types have not established correctness. |
Malformed input, an unbound variable and a language-defined arithmetic error are errors of the represented language or its inputs. A loaded method that is not visible to the running computation is a binding or visibility issue. Diagnose those conditions separately from a missing semantic implementation.
The historical expression problem asks for stronger properties than practical plug-in loading alone, including static type safety and extension without recompiling existing code. Wadler’s formulation supplies those comparison criteria. Use the name as a search cue; state which properties the construction achieves.
CMP.15:4.6 - Establish preservation on the promised old uses
Preserve the old meanings as well as the old files. For each established operation, compare which body an old input selects after extension and which dependencies that body invokes. A new, more specific method can redirect an old call in a subtype-based dispatcher. Disallow that override, explicitly retain the earlier selection, or treat it as a behavior change requiring its own correspondence.
For a pure tree interpreter with exact keys, a useful preservation argument is available. Suppose the old keys still select the same bodies, the old expressions contain only old constructors, and primitives, environments and dependent operations retain their meaning. A leaf obtains the same result. At a compound old node, induction gives the same child results, and the unchanged body combines them in the same way. Every finite old expression therefore retains its result. This argument depends on those premises; unchanged source text alone does not prove them.
Test a new form beneath an old constructor as a different obligation. It was not an old expression, so the preservation argument does not establish its new meaning. This case checks whether open recursion reaches the supplied intersection and whether the resulting composition obeys the new rules.
When effects, failures or concurrent replacement matter, use the observations and correspondence from CMP.12 and the interaction method in CMP.14. Preserving a returned number may leave an extra effect or a changed failure observable. Selected tests can expose such differences; a promise for an entire class of executions needs an argument at that scope.
CMP.15:4.7 - Bound the cost and retain the simplest adequate composition
Count the work that the architecture moves as well as the work it removes. Independent authors avoid editing a central list, but someone still writes or derives the required intersections, connects dependencies, diagnoses rejected compositions and supports the result. A generic derivation can reduce the number of bodies; its applicability and exception handling still have a cost.
For an exact-key table with H supplied bodies and Q required pairs, assembly and coverage checking take expected order H + Q dictionary operations and order H table storage. Each recursive dispatch adds an expected constant-time lookup under the hash-table assumptions. Count the bodies separately: free-variable analysis copies or unions sets, and evaluation may copy environments. With N visited nodes and at most K names in intermediate sets, straightforward set operations can cost order N K, rather than merely N. Large-integer arithmetic and representation conversion have their own costs.
A static representation can move selection into compilation or construct terms through operation dictionaries, but it can introduce interface complexity, generated instances, code size, specialization and build dependencies. A dynamic representation adds assembly, visibility, possible runtime failures and often indirect calls. Measure or derive the relevant total for the actual workload; neither label guarantees the cheaper execution.
Compare a closed alternative using the same required cases. For four stable variants, two fixed operations and one maintainer, two exhaustive functions may be easier to understand and maintain than a registry and its coverage description. They still need the correct Let rule. Conversely, repeatedly editing another team’s module for each new operation or variant gives independent composition a concrete benefit. Use SYSE.23 when the broader engineering choice needs comparison of anticipated changes and their complete cost.
Stop with the smallest construction that provides the receiving application’s operations under its admitted inputs and extension conditions. Retain explicit unsupported cases rather than implying a complete open world. Reopen the selection when a new required pair, operation dependency, binding rule, loading condition or change workload invalidates it.