check_count_class_actions.py

"""Finite semantic audits. Mutable histogram and exact arithmetic oracles, not a native implementation."""
from itertools import product
from random import Random
import json

stats = dict(histogram_sequences=0, histogram_prefixes=0, max_update_primitives=0,
             orbit_transitions=0, stale_alias_witnesses=0)

class Bucket:
    def __init__(self):
        self.prev = self.next = None
        self.gap = self.pop = None
        self.residue = 0

class Histogram:
    def __init__(self, modulus=3):
        self.head = None
        self.rows = {}
        self.distinct = None
        self.by_residue = [None] * modulus
        self.modulus = modulus
        self.work = 0
    def put(self, node, field, value):
        self.work += 1
        setattr(node, field, value)
    def push(self, stack):
        self.work += 1
        return (stack,)
    def pop(self, stack):
        self.work += 1
        assert stack is not None
        return stack[0]
    def create(self, prev, nxt, residue):
        self.work += 1
        b = Bucket()
        b.prev, b.next, b.residue = prev, nxt, residue
        b.gap = self.push(None)
        if prev is None:
            self.head = b
        else:
            self.put(prev, 'next', b)
        if nxt is not None:
            self.put(nxt, 'prev', b)
            self.put(nxt, 'gap', self.pop(nxt.gap))
        self.distinct = self.push(self.distinct)
        self.by_residue[residue] = self.push(self.by_residue[residue])
        return b
    def increment(self, row):
        self.work = 0
        old = self.rows.get(row)
        nxt = self.head if old is None else old.next
        if nxt is not None and nxt.gap[0] is None:
            dest = nxt
        else:
            residue = 1 % self.modulus if old is None else (old.residue + 1) % self.modulus
            dest = self.create(old, nxt, residue)
        self.put(dest, 'pop', self.push(dest.pop))
        if old is not None:
            self.put(old, 'pop', self.pop(old.pop))
            if old.pop is None:
                prev = old.prev
                self.put(dest, 'gap', self.push(old.gap))
                self.put(dest, 'prev', prev)
                if prev is None:
                    self.head = dest
                else:
                    self.put(prev, 'next', dest)
                self.distinct = self.pop(self.distinct)
                self.by_residue[old.residue] = self.pop(self.by_residue[old.residue])
        self.rows[row] = dest
        stats['max_update_primitives'] = max(stats['max_update_primitives'], self.work)
        assert self.work <= 24

# Full traversals and integer values occur only in the independent oracle audit.
def length(stack):
    n = 0
    while stack is not None:
        n += 1
        stack = stack[0]
    return n

def audit(h, counts):
    seen = {}
    b = h.head
    prev = None
    count = 0
    residues = [0] * h.modulus
    while b is not None:
        assert b.prev is prev
        gap = length(b.gap)
        assert gap > 0
        count += gap
        assert count not in seen
        seen[count] = length(b.pop)
        assert b.residue == count % h.modulus
        residues[b.residue] += 1
        assert seen[count] > 0
        for row, value in counts.items():
            if h.rows[row] is b:
                assert value == count
        prev, b = b, b.next
    expected = {c: list(counts.values()).count(c) for c in set(counts.values())}
    assert seen == expected
    assert length(h.distinct) == len(expected)
    assert [length(s) for s in h.by_residue] == residues
    # Histogram agreement exactly matches the variance-zero predicate.
    variance = 0
    for r in range(h.modulus):
        vals = [c for c in counts.values() if c % h.modulus == r]
        variance += len(vals)*sum(c*c for c in vals)-sum(vals)**2
    assert (variance == 0) == all(d <= 1 for d in residues)
    stats['histogram_prefixes'] += 1

for size in range(6):
    for seq in product(range(6), repeat=size):
        h = Histogram(); pairs = set(); counts = {}
        for event in seq:
            row, target = divmod(event, 2)
            if (row, target) not in pairs:
                pairs.add((row, target)); h.increment(row)
                counts[row] = counts.get(row, 0) + 1
            audit(h, counts)
        stats['histogram_sequences'] += 1
rng = Random(175)
for trial in range(100):
    h = Histogram((1, 3, 5)[trial % 3]); counts = {}
    for step in range(300):
        row = rng.randrange(12)
        h.increment(row); counts[row] = counts.get(row, 0) + 1
        audit(h, counts)
    stats['histogram_sequences'] += 1
# Large gap, head insertion, hole closing and source deletion without arbitrary gap addition.
h = Histogram(); counts = {}
for row in [0]*1000 + [1]*997 + [2, 2, 2] + [1]*3 + [2]*997:
    h.increment(row); counts[row] = counts.get(row, 0) + 1; audit(h, counts)
stats['histogram_sequences'] += 1

# Finite observation closure for all coordinate selections on three registers.
d = 3
forms = sorted(set(tuple(int(k == i)-int(k == j) for k in range(d))
                   for i in range(d) for j in range(d)))
index = {ell: i for i, ell in enumerate(forms)}
def dot(a, b): return sum(x*y for x, y in zip(a, b))
for x in product(range(-2, 3), repeat=d):
    y = tuple(dot(ell, x) for ell in forms)
    for selection in product(range(d), repeat=d):
        for delta in ((0, 0, 0), (1, -1, 1), (-1, 0, 1)):
            newx = tuple(x[selection[i]]+delta[i] for i in range(d))
            newy = []
            for ell in forms:
                pulled = tuple(sum(ell[i] for i in range(d) if selection[i] == k) for k in range(d))
                newy.append(y[index[pulled]]+dot(ell, delta))
            assert tuple(newy) == tuple(dot(ell, newx) for ell in forms)
            assert y == tuple(dot(ell, x) for ell in forms)  # retained snapshot
            stats['orbit_transitions'] += 1

# The shallow-copy alias counterexample is a deliberate failed representation.
old_one = {'count': 1, 'next': None, 'population': 2}
row_b_reference = old_one
new_two = {'count': 2, 'next': None, 'population': 1}
current_one = dict(old_one, next=new_two, population=1)
assert current_one['next']['count'] == 2
assert row_b_reference['next'] is None
assert row_b_reference['population'] != current_one['population']
stats['stale_alias_witnesses'] = 1
stats['native_histogram_claim'] = False
print(json.dumps(stats, sort_keys=True))