CMP.16:5 - Archetypal Grounding
CMP.16:5.1 - Construct a fragment meaning that makes concatenation usable
A text is a finite sequence of opening and closing parentheses. The required answer is whether its parentheses are balanced: every prefix has at least as many openings as closings, and the totals agree at the end. The text arrives as independently obtained fragments, which must be combined in their original order.
The first proposal records only whether each fragment is balanced. It fails on the fragments (() and ()): neither is balanced alone, while their concatenation (()()) is balanced. Requiring every fragment to be balanced would change the admitted splits rather than solve the original problem.
Recover what the whole needs from a fragment. Treat an opening as +1 and a closing as -1. Let d be the total change in balance and m the minimum of all prefix balances, including the empty prefix with balance zero. The pair says both where the fragment leaves a caller’s balance and how far below that starting balance it can go. For a caller entering with balance b, the fragment never becomes negative exactly when b + m >= 0; its ending balance is b + d.
If fragment A is followed by B, each prefix lies inside A or consists of all of A followed by a prefix of B. Therefore:
combine((dA,mA),(dB,mB)) = (dA+dB, min(mA, dA+mB))
empty = (0,0)
open = (1,0)
close = (-1,-1)
The formula follows from the prefix calculation above. It gives the summary of concatenation. Consequently it is associative on summaries of fragments: either grouping describes the same ordered text and the same prefix minimum. It is not commutative. Combining open with close gives (0,0); reversing them gives (0,-1). The identity empty follows from including the empty prefix.
For ((), the summary is (1,0); for ()), it is (-1,-1). Their join is (0,0), so the whole is balanced. A whole summary is balanced exactly when its total is zero and its prefix minimum is nonnegative. A possible implementation is:
def combine(left, right):
dl, ml = left
dr, mr = right
return dl + dr, min(ml, dl + mr)
def summarize(text):
result = (0, 0)
for char in text:
if char == "(":
piece = (1, 0)
elif char == ")":
piece = (-1, -1)
else:
raise ValueError("unsupported character")
result = combine(result, piece)
return result
def is_balanced(summary):
total, minimum = summary
return total == 0 and minimum >= 0
Character summaries provide the constructors; combine supplies the effective join. Its arguments must be summaries of admitted fragments; an arbitrary supplied pair has not acquired that meaning merely by having two integer fields. The semantic equation connects this small computational algebra to arbitrary finite texts. CMP.2 can organize recursive construction, and CMP.10 can choose an aggregate tree when later edits matter. In a word model with sufficiently wide counters, scanning takes linear work and a join takes constant work. Unbounded text length needs a corresponding account of growing counters; the pair is not literally constant storage in every bit model.
Changed observation. Now return the position of the first negative prefix, if one exists. The two texts )()( and ())( have the same length four and the same summary (0,-1), but their first negative positions are one and three. The existing pair cannot answer this query. No faster decoding of the pair recovers the lost distinction.
One remedy retains the composition tree, each child’s length and pair, and the leaf characters. Enter the root with balance zero. If a left child’s minimum plus the incoming balance is negative, descend left. Otherwise add its total to the balance, skip its length and descend right. At a negative leaf, the accumulated position identifies the first offending character. If the root minimum is nonnegative, there is no negative prefix; a positive final total instead reports unmatched openings. A balanced tree gives a descent proportional to its height after the summaries have been maintained. The storage and update obligations belong to the remedy, not to the old two-number claim.
The original balance decision remains valid. The stronger observation changes the retained unit and its operations. This distinguishes generality over all finite admitted fragments from adequacy for every possible later query.
CMP.16:5.2 - Construct an operation boundary for a continuing capacity condition
A service grants permission to use at most K resource slots at once, where K is a fixed nonnegative integer. Its computational responsibility is to track outstanding grants and refuse another when K are active. The relation between a grant and resource use is a further requirement: cooperating clients begin use under their own grant and release it only after use ends. Authentication against a caller trying to release another caller’s grant is a separate requirement. The computation alone cannot prevent an uncooperative client from using a physical resource.
Exposing read_count and write_count leaves each client to reconstruct admission and release. A more useful unit is the grant service itself, with acquire and release(ticket) operations. In an initially sequential model, retain a set active and a monotonically increasing ticket number. acquire returns Busy if len(active) == K; otherwise it obtains a fresh ticket, adds it to active and returns it. release removes a ticket only if it is active, otherwise reports that no active grant matches it. The ticket, rather than an unqualified decrement, identifies what can be released.
Initialization establishes active = {}. An admitted acquisition changes its size from a number below K to at most K; release cannot increase it. Thus every permitted sequence preserves 0 <= len(active) <= K. Fresh tickets ensure that a delayed second release of an old grant cannot release a later grant. The sequence acquire -> 0, release(0), acquire -> 1, release(0) leaves ticket 1 active: the final release reports no matching active grant.
This is a safety argument for the stated operations. It does not establish that a waiting caller eventually receives permission; that requires available releases and a selection policy. Nor does it settle retry after a lost acquisition reply. If the required behavior gives one grant per logical request, request identity and the retry protocol must be added through CMP.14. The old operations still explain their narrower behavior but not that stronger service.
Changed execution condition. Two callers now execute the acquisition body concurrently. With K = 1, both can observe an empty set before either inserts a ticket, then insert different tickets. The concurrent implementation no longer supplies the atomic transition required by the invariant argument. One remedy serializes the check and insertion through an available exclusive mechanism. CMP.14 develops its permitted histories and progress conditions; C.29.3 establishes whether the chosen executor supplies the required operation.
The ticket implementation also has conditions. A bounded counter can wrap, and a restart can forget active grants. Restricting the lifetime, preserving state or changing the ticket construction needs an argument covering the actual use. Those conditions can select another representation without changing the abstract service, or reveal that its former promise cannot be maintained. This is a continuing computational abstraction, not a terminating calculation whose final count alone defines success.