Jump to text
On this page
Copy and source
Published source confirmed at last check

Source changed 2026-11-18 21:11:39 UTC · snapshot created 2026-11-18 21:12:35 UTC · last check 2026-11-18 22:15:20 UTC

CMP.16:4 - Solution

Construct a provisional whole with proposed units and operations, use its first consequential failure to revise them together, and justify the resulting level against both its clients and its implementation. The moves below can return to one another. Use an existing interface when it meets the requirements.

CMP.16:4.1 - Recover the behavior and the freedom to change its construction

State what a recipient must observe or do with the result. Include consequential continuations: a value may later be updated, an object traversed, a description interpreted, or an event acknowledged. Distinguish a finite answer from continuing behavior. For a continuing computation, state what must always hold and what response must eventually occur under which environmental assumptions.

Recover the admitted cases and the available operations through C.29.2. Separate required behavior from an inherited implementation choice. A requirement to preserve order does not require an array; a capacity limit does not necessarily require exposing a mutable counter. Conversely, a physical coupling, a particular external format or an existing client’s observation can be binding. Do not change those requirements merely to make the preferred construction easier.

Choose one whole use that exposes the difficulty and a consequential variation. These are design probes, not the scope of the method. If the proposed change would answer a different question, make that difference explicit and return it to the receiver instead of presenting the changed answer as preservation.

CMP.16:4.2 - Try the whole before fixing the units

Sketch the computation at a level where its intended effect can be followed. Treat a proposed higher operation as a temporary obligation: say what it receives, what it must return or change, and why the rest of the construction needs it. Do not yet assume that the operation exists or costs one step.

Suppose each proposed part has supplied exactly its promised result. Attempt the next join or continuation. At the first missing contribution, identify the distinction or action that would make the join possible. Typical remedies have different grounds:

  • Enrich a returned summary when the join needs information the part discarded. CMP.2 develops this for recursive construction.
  • Introduce a compound unit when a relation between smaller items must be preserved by every permitted assembly. Check that the new constructor still covers the required cases.
  • Change the operation boundary when separately exposed updates permit invalid states or repeated repair. Include the boundary’s interruption and visibility assumptions.
  • Pass context or postpone a choice when a part cannot correctly decide without information available at the join.
  • Change the decomposition when obtaining the missing contribution would repeat the original difficulty or exceed the resource limit.

Try a simple alternative alongside the favored design. Keeping the original units and checking the final result can be cheaper when invalid assemblies are rare and harmless. A stronger constructor is useful when it makes repeated use or reasoning materially easier.

CMP.16:4.3 - Give the proposed unit a meaning through its uses

Describe what a unit represents and which operations clients may perform. Include constructors, observations, transformations and combinations needed by the whole. State conditions of use: an operation can be partial, require ownership of a token, depend on an environment, or report failure. Such conditions must be obtainable and respected by the client, not hidden in a proof that the client cannot satisfy.

Decide which distinctions can be hidden. If two lower-level states represent the same unit, the permitted observations and continuations must respect that identification on the promised scope. A summary that forgets the order of items cannot support an arbitrary future order query. A mutable object and an independent copy may have the same current values but differ after a change. MATH.2 and MATH.18 supply the mathematical identification and interpretation questions; the construction here chooses what the computational client needs them to preserve.

For pure composition, state the operations and the laws the intended assembly uses. Associativity permits regrouping, not reordering. An identity supplies an empty case; an inverse is needed only if the proposed operation undoes a contribution. For stateful behavior, state admissible transitions and observations instead of forcing it into a pure algebra. For a language of descriptions, specify constructors and meanings; CMP.12 develops the corresponding interpreter or translation.

This is an abstraction boundary only when clients can use the stated operations without depending on hidden detail. If a client bypasses it by editing internal state or inspecting an undocumented encoding, either include that behavior in the agreement or remove the bypass.

CMP.16:4.4 - Obtain the operations and establish usable composition

Construct each required operation from available steps, or obtain a sufficiently qualified supplier. For a constructor, show how it produces a valid unit from admitted input, or how it detects and reports an unsupported input before the client relies on validity. For an update, derive the changed state from the invariant rather than assuming that a familiar assignment preserves it.

Then establish the whole-forming claim. For a pure assembly, show that the join of admissible contributions has the required meaning and remains usable in the next join. Account for base and empty cases. For a transition system, show that initialization establishes the state condition and every permitted transition maintains it; include the environmental actions that can affect that condition. Induction can then cover arbitrary finite assemblies or execution prefixes under those premises. It does not by itself prove eventual response or cover an omitted operation.

Check coverage separately. Can every required input or behavior be obtained with these constructors and operations? Restricting a unit to internally balanced fragments, for example, would exclude valid whole texts split inside a nested expression. An invariant can be perfectly preserved while that restriction makes the construction unsuitable. Broaden the unit, change the assembly or report the limitation.

The construction may depend on a supplied primitive. Keep that dependency visible and return to C.29.3 when its realization is unsettled. CMP.14 establishes the permitted interference and progress when an operation must remain indivisible or coordinate participants. An abstract operation is a useful design result before that realization is available, but it is not yet an executable promise in that environment.

CMP.16:4.5 - Relate the new level to its implementation

For a deterministic state abstraction, let I(c) state that a concrete state c is valid, and let alpha(c) give its abstract meaning. Explain how initialization obtains a state satisfying I. For each abstract operation, begin with a related state and an admitted argument, follow its concrete implementation, and show that the resulting state remains valid and represents a permitted abstract result. Include the observation returned to the caller. This argument can be ordinary prose and equations; a formal notation or proof assistant is chosen when it earns its cost.

For a pure summary h and a source composition *, a useful obligation is:

h(x * y) = combine(h(x), h(y)).

This equation explains why independently obtained summaries can replace the source parts at that join. It is a claim to derive from their meanings, not an instruction to assume a homomorphism. If it fails, identify the lost distinction, strengthen the summary or restrict the proposed use. A relation rather than a single function can be needed for nondeterminism or multiple acceptable implementations; CMP.12 develops behavior preservation and CMP.14 supplies the interaction conditions.

Also connect progress and resource claims. A lower-level operation can preserve every completed observation while looping forever before producing one. A correct response can miss the required deadline. A finite sequence of abstract operations can expand into unaffordable work. Do not transfer termination, responsiveness or unit cost merely because a value correspondence holds.

At the physical boundary, preparation, actual evolution and readout must supply the relation assumed here. A new physical unit may require an engineering change. Use C.29.3 to obtain that connection and carry any unresolved condition back to the promised whole.

CMP.16:4.6 - Compare the complete work and preserve the useful level

Count constructing and converting units, performing their operations, maintaining their invariants, communicating and obtaining the final observations. Include the information retained for later operations. CMP.10 compares concrete storage and access choices; CMP.3 handles shared subcomputations. A cheap abstract join can still require large construction or output work.

Choose a sufficient implementation without unnecessarily exposing it above the boundary. This permits a later replacement when it preserves the operations and observations on which clients rely. A change from a list to a tree can preserve a sequence interface while changing costs. Unordered delivery can reverse messages whose order a client relies on.

When no arrangement satisfies all demands, return the precise conflict: a missing observation, an unsupported operation, an unaffordable construction or an unavailable realization. CMP.1 and CMP.11 can establish relevant impossibility or lower-bound claims; a failed design alone does not establish them. A qualified weaker result is useful only when its receiver accepts the difference.

CMP.16:4.7 - Change a condition and reconstruct the affected whole

Vary an input family, required observation, operation, interaction or resource limit that could alter the design. Follow its effect through the abstraction and back to the whole. Ask whether the old unit still retains enough information, whether the allowed operations still preserve its meaning, and whether their implementation still meets the conditions of use.

Preserve unaffected constructions. A new query can require another summary while leaving the source composition intact. A concurrency requirement can preserve abstract operations while invalidating a sequential implementation. A changed subject interpretation can leave an algorithm correct for its earlier mathematical question but unsuitable for the receiving work.

Finish with the usable units and operations, their construction, the reason their permitted assembly obtains the required behavior, and the implementation and resource conditions on which that use depends. It must let the recipient perform the intended whole without privately inventing its missing join.