verify_balanced_context.py

#!/usr/bin/env python3
"""Finite semantic checks. Host tuple costs do not verify record resource bounds."""
from dataclasses import dataclass
from pathlib import Path
from collections import deque
import hashlib
import json
import verify_counter_free_real_time_queue as fifo


@dataclass(frozen=True, eq=False)
class Value:
    constructor: str
    chain: bool
    bit: bool
    queue: object = None
    left: object = None
    right: object = None


q0, _ = fifo.enqueue(fifo.EMPTY_QUEUE, 'A')
q0, _ = fifo.enqueue(q0, '#')
EMPTY = Value('E', True, False, q0)


def wrap(value):
    if not value.chain:
        return Value('W', False, False, left=value), 1
    symbol = value.queue[0][0]
    queue, cost = fifo.dequeue(value.queue)
    for payload in ('A', 'A') if symbol == 'A' else ('#',):
        queue, c = fifo.enqueue(queue, payload)
        cost += c
    return Value('W', True, symbol == '#', queue, value), cost + 1


def join(left, right):
    if left.constructor == 'E':
        return right
    if right.constructor == 'E':
        return left
    return Value('C', False, False, left=left, right=right)


def decode(value):
    # Independent, unbounded audit traversal; never called by the operations.
    todo, result = [value], []
    while todo:
        item = todo.pop()
        if isinstance(item, str):
            result.append(item)
        elif item.constructor == 'W':
            todo.extend(['r', item.left, 'c'])
        elif item.constructor == 'C':
            todo.extend([item.right, item.left])
    return ''.join(result)


def reference(word):
    n = len(word) // 2
    if word != 'c' * n + 'r' * n:
        return False
    k = 0
    while 2 ** (k + 1) + k <= n:
        if 2 ** (k + 1) + k == n:
            return True
        k += 1
    return False


def check(value, word):
    assert decode(value) == word
    assert value.bit == reference(word)
    assert value.chain == (word == 'c' * (len(word)//2) + 'r' * (len(word)//2))


def run():
    levels = [{'': EMPTY}]
    joins = wraps = 0
    max_conceptual = 0
    for n in range(1, 8):
        level = {}
        for word, value in levels[n-1].items():
            out, cost = wrap(value)
            target = 'c' + word + 'r'
            check(out, target)
            level[target] = out
            max_conceptual = max(max_conceptual, cost)
            wraps += 1
        for i in range(1, n):
            for x, hx in levels[i].items():
                for y, hy in levels[n-i].items():
                    out = join(hx, hy)
                    check(out, x+y)
                    level.setdefault(x+y, out)
                    joins += 1
        for word, value in level.items():
            check(join(EMPTY, value), word)
            check(join(value, EMPTY), word)
            check(value, word)  # operands remain valid
        levels.append(level)

    # Independent FIFO clock and arithmetic event formula.
    queue = deque('A#')
    value = EMPTY
    events, retained = [], [(0, EMPTY)]
    for n in range(1, 4097):
        symbol = queue.popleft()
        queue.extend('AA' if symbol == 'A' else '#')
        value, cost = wrap(value)
        assert value.bit == (symbol == '#')
        fifo.audit(value.queue, ''.join(queue))
        max_conceptual = max(max_conceptual, cost)
        if value.bit:
            events.append(n)
        if n <= 64 or n in (255, 511, 1023, 2047, 4096):
            retained.append((n, value))
    expected = [2 ** (k+1)+k for k in range(13) if 2 ** (k+1)+k <= 4096]
    assert events == expected

    forks = 0
    for n, old in retained:
        snapshot = old.queue
        branch, _ = wrap(join(EMPTY, join(old, EMPTY)))
        check(branch, 'c' * (n+1) + 'r' * (n+1))
        assert old.queue == snapshot
        check(old, 'c' * n + 'r' * n)
        if n:
            other = join(old, old)
            for _ in range(3):
                other, _ = wrap(other)
            check(other, 'ccc' + ('c'*n+'r'*n)*2 + 'rrr')
        forks += 1

    # Actual reachable App state: count the old token successors removed by
    # invalidation and two exec steps. This witnesses why copying targets
    # must be included in a resource proof. No radius is inferred by sampling.
    q = fifo.EMPTY_QUEUE
    app_witness = None
    for n in range(1, 200):
        q, _ = fifo.enqueue(q, 'A')
        status = q[2]
        if status[0] == 'App' and len(status[1]) >= 4:
            after, _ = fifo.dequeue(q)
            assert after[2][0] == 'App'
            assert len(after[2][1]) == len(status[1])-3
            app_witness = {'enqueues': n, 'tokens_before': len(status[1]),
                           'tokens_after': len(after[2][1]),
                           'old_status_token_path_with_three_tails': 5}
            break
    assert app_witness is not None

    return {
        'scope': 'Finite semantic model only. Tuple slicing is not constant-time record execution. No proof-assistant verification, arbitrary-heap enumeration, or measured universal radius bound.',
        'balanced_words_by_pairs_0_to_7': [len(level) for level in levels],
        'nonempty_join_cases': joins,
        'wrap_cases': wraps,
        'clock_ticks': 4096,
        'clock_accepting_depths': events,
        'retained_branch_checks': forks,
        'maximum_conceptual_fresh_records_from_model': max_conceptual,
        'reachable_App_control': app_witness,
        'fifo_model_sha256': hashlib.sha256(Path(fifo.__file__).read_bytes()).hexdigest(),
        'written_bounds': {'queue_radius_used': 6, 'wrap_radius': 19,
                           'wrap_allocation': 37, 'arity': 6},
        'universal_proofs': 'Written separately: invariant/history induction, non-VPL argument and uniform context application iff VPL. Positive theorem is not mechanically verified by this checker.'
    }


if __name__ == '__main__':
    print(json.dumps(run(), indent=2))