"""Differential tester: check a submitted Bernoulli routine against the oracle. This is the tool at the centre of the course. You give it a Python file — one you wrote, or one an AI generated for you — and it compares that file's ``bernoulli`` function against :mod:`reference_bernoulli`, reports the **first** index where the two disagree, and names the failure mode. Usage:: python3 check.py my_bernoulli.py python3 check.py examples/wrong_b1_sign.py python3 check.py my_bernoulli.py --max-n 40 --verbose Interface contract ------------------ A submitted file must define:: bernoulli(n: int) -> fractions.Fraction defined for every ``n >= 0``, using the first-Bernoulli convention ``B1 = -1/2``, returning exact :class:`~fractions.Fraction` values (including ``Fraction(0)`` for odd ``n > 1``). Values are compared exactly. A returned float is reported as ``not-fraction`` and is also compared as the rational it actually stores, ``Fraction(x)``: ``1.0`` matches ``B0``, and ``-1.1102230246251565e-16`` at ``B3`` is not zero. This contract is quoted verbatim in the Unit 10 precise prompt. That is the point: a specification precise enough to test against is a specification precise enough to prompt with. SAFETY ------ This tool **executes** the file you give it, because there is no way to check what a routine returns without running it. Generated code is code from a source you cannot vouch for, so it does not run here: ``sandbox.py`` runs it in a separate process with a timeout, resource limits and a stripped environment, and only data comes back. That reduces the blast radius and turns hangs and runaway memory into named findings. It is **not** a security boundary: the child still runs as you and can read what you can read. For code you have not read, from a source you have no reason to trust, run the lab inside a container or a virtual machine, or use the table route, which executes nothing. ``README.md`` states the threat model. """ from __future__ import annotations import argparse import sys import textwrap from dataclasses import dataclass, field from fractions import Fraction from pathlib import Path import reference_bernoulli as oracle import sandbox #: How far the differential test goes by default. Small enough to stay fast, #: large enough that float-based and recurrence-order bugs actually surface. DEFAULT_MAX_N = 30 @dataclass class Finding: """One problem found in a submitted implementation.""" code: str summary: str detail: str = "" unit: str = "" def render(self) -> str: lines = [f"[{self.code}] {self.summary}"] if self.detail: lines.extend(f" {line}" for line in self.detail.splitlines()) if self.unit: lines.append(f" See: {self.unit}") return "\n".join(lines) @dataclass class Report: """The result of checking one submitted file.""" path: str findings: list[Finding] = field(default_factory=list) checked_up_to: int = 0 @property def passed(self) -> bool: return not self.findings def add(self, code: str, summary: str, detail: str = "", unit: str = "") -> None: self.findings.append(Finding(code, summary, detail, unit)) def load_submission(path: str | Path, max_n: int = None): """Run a submitted file in the sandbox and return what its routine produced. Named as it always was, because the lab documentation and the units refer to it, but it no longer imports anything into this process: see ``sandbox.py``. """ return sandbox.run_candidate(path, max_n if max_n is not None else DEFAULT_MAX_N) def _diagnose_pattern(func, max_n: int, show=None) -> list[Finding]: """Recognise well-known wrong answers and name them. A bare "expected -1/30, got 1/30" tells a learner that something is wrong. Naming the failure mode tells them *what kind* of mistake it is, which is the skill the course is actually teaching. ``func(n)`` gives the value as an exact Fraction (a float arrives as the rational it stores, so ``-1.1e-16`` is not zero here). ``show(n)``, when given, is how that value is printed: the routine's own output, not the converted fraction. """ findings: list[Finding] = [] def safe(n: int): try: return func(n) except Exception: return None if show is None: show = safe # 1. Second-convention B1 = +1/2. Everything else agrees. b1 = safe(1) if b1 is not None and b1 == Fraction(1, 2): # Say "the second convention" only of a routine that agrees with it # everywhere tested; +1/2 at B1 alone does not make a routine correct. rest_agrees = all( safe(n) == oracle.bernoulli(n) for n in range(max_n + 1) if n != 1 ) findings.append( Finding( code="b1-sign", summary="B1 has the wrong sign for this course's convention.", detail=( "Your routine returns B1 = +1/2. That is the *second* Bernoulli\n" "convention, and it is not wrong mathematically -- but this course\n" "fixes the *first* convention, B1 = -1/2. The conventions differ\n" "only at B1, but leaving that choice unstated is still a\n" "specification failure, not an arithmetic failure." if rest_agrees else "Your routine returns B1 = +1/2, which matches the *second*\n" "Bernoulli convention at B1. This course fixes the *first*\n" "convention, B1 = -1/2. Other results must be checked separately:\n" "this routine does not agree with either convention everywhere." ), unit="Unit 6 (the convention trap), Unit 10 (state it in the prompt)", ) ) # 2. Odd terms not zero: a property, checked at every odd index above 1 # up to max_n, and exactly -- a float a hair away from zero is not zero. nonzero_odd = [n for n in range(3, max_n + 1, 2) if (v := safe(n)) not in (None, 0)] if nonzero_odd: shown = ", ".join(f"B{n}={show(n)}" for n in nonzero_odd[:3]) found = textwrap.fill( f"Non-zero odd terms found: {shown}.", width=64, break_long_words=False, break_on_hyphens=False, ) findings.append( Finding( code="odd-terms", summary="Odd-index Bernoulli numbers above B1 must be exactly zero.", detail=( f"{found}\n" "Every B_(2k+1) for k >= 1 is zero. A routine that only computes\n" "the even terms and then mis-indexes them will fail here, and so\n" "will one that skips the odd terms instead of returning zero." ), unit="Unit 6 (which terms vanish), Unit 8 (property checks)", ) ) # 3. Note G indexing: submitted(k) matches Lovelace's B at odd k. # She numbers only the non-zero terms and numbers them with the odd # integers -- her B1, B3, B5, B7 are the modern B2, B4, B6, B8, and there # is no Note G B2. So her scheme puts a value at every odd index, which # is exactly where the modern convention puts a zero. ada_style = [ k for k in range(1, 10, 2) if (v := safe(k)) is not None and v == oracle.ada_bernoulli(k) ] if len(ada_style) >= 3: findings.append( Finding( code="ada-indexing", summary="The routine uses Lovelace's Note G labels, not modern ones.", detail=( "Your B1, B3, B5 are the modern B2, B4, B6. Those are Note G's\n" "labels: Lovelace numbers only the non-zero terms, and numbers\n" "them with the odd integers, so she has no B2 at all. Against\n" "the modern convention this is inverted -- your odd indices\n" "carry the numbers and your even ones are empty, where the\n" "specification asks for the reverse. Every value is a real\n" "Bernoulli number filed under another century's label, so the\n" "same symbol means two different numbers." ), unit="Unit 6 (index mapping), Unit 16 (reading Note G honestly)", ) ) # 4. Plain off-by-one shift. # # These last two findings are the same observation almost everywhere, and # saying so is more honest than picking one. Lovelace's B_n at odd n is # the modern B_(n+1); at even n she has no label and the modern B_(n+1) # is an odd index, which is zero. So "shift every index by one" and "use # Note G's labels" produce identical output at every index except B0, # where a shift gives the modern B1 = -1/2 and Note G's table, which # starts at B1, leaves B0 = 1 alone. # # B0 is therefore the whole of the evidence separating them, and one # value is a thin thing to diagnose from. The checker reports what it # sees and says what would settle it, rather than inventing a confidence # it does not have -- which is the same move the course asks of a learner. shifted = [ n for n in range(0, 8) if (v := safe(n)) is not None and v == oracle.bernoulli(n + 1) ] if len(shifted) >= 4: findings.append( Finding( code="off-by-one", summary="Every value is shifted by one index.", detail=( "Your B_n equals the oracle's B_(n+1). The arithmetic is right and\n" "the indexing is wrong -- the classic off-by-one, and the reason\n" "'it looks correct' is not a test." ), unit="Unit 7 (plausible but wrong), Unit 8 (differential testing)", ) ) if len(ada_style) >= 3 and len(shifted) >= 4: b0 = safe(0) if b0 == oracle.bernoulli(0): reading = ( "B0 came back as 1, the modern B0, which a wholesale shift would\n" "have moved to -1/2. That points at Note G's labels rather than at\n" "a shift -- her table starts at B1 and leaves B0 alone." ) elif b0 == oracle.bernoulli(1): reading = ( "B0 came back as -1/2, the modern B1, so every index including the\n" "first has moved. That points at a shift rather than at Note G's\n" "labels." ) else: reading = ( "B0 settles nothing here, so on this evidence the two readings are\n" "indistinguishable." ) findings.append( Finding( code="one-observation", summary="ada-indexing and off-by-one describe the same evidence here.", detail=( "Both matched, and that is not two faults. Lovelace's B_n at odd\n" "n is the modern B_(n+1), and at even n she has no label while\n" "the modern B_(n+1) is zero -- so her scheme and a one-place\n" "shift agree at every index except B0.\n\n" f"{reading}\n\n" "One value is thin evidence. To settle it, read the source: a\n" "routine written to Note G's labels says so, and a shift is\n" "usually an arithmetic slip in a range or a loop. The repairs\n" "differ, which is why the distinction is worth making." ), unit="Unit 6 (index mapping), Unit 8 (what a comparison establishes)", ) ) return findings def _shown(outcome, n: int) -> str: """A returned value the way a learner would see it. A Fraction or int prints as the fraction; anything else -- a float, which was compared as the exact rational it stores, or something that is not a number at all -- prints as the routine's own repr. """ got = outcome.fractions.get(n) if got is not None and outcome.types.get(n) in ("Fraction", "int"): return str(got) return outcome.values.get(n, "?") def check_submission(path: str | Path, max_n: int = DEFAULT_MAX_N) -> Report: """Check one submitted file and return a :class:`Report`.""" if max_n < 0: # An empty range checks nothing, and nothing checked must never read as a PASS. raise ValueError(f"max_n must be 0 or more, not {max_n}") report = Report(path=str(path)) # --- Run it, in its own process --------------------------------------- # Not imported here: see sandbox.py for what that protects and what it does # not. Everything below works from the data the child process returned. outcome = sandbox.run_candidate(path, max_n) if not outcome.ok: if outcome.failure_kind == "no-function": available = ", ".join(outcome.names) or "(none)" report.add( "no-function", "The file does not define a function called 'bernoulli'.", detail=( f"Names found in the file: {available}\n" "The contract is: bernoulli(n: int) -> fractions.Fraction" ), unit="Unit 10 (state the interface in the prompt)", ) elif outcome.failure_kind == "not-callable": report.add( "not-callable", "'bernoulli' exists but is not a function.", detail="The contract is: bernoulli(n: int) -> fractions.Fraction", ) elif outcome.failure_kind == "no-file": report.add("no-file", outcome.failure) elif outcome.failure_kind == "timeout": report.add( "timeout", outcome.failure, detail=outcome.detail, unit="Unit 8 (a routine that never returns is a defect, not a pass)", ) elif outcome.failure_kind == "no-output": report.add( "no-result", "The routine produced no result: it ended abruptly.", detail=outcome.detail, unit="Unit 8 (read generated code before running it)", ) else: report.add( "import-error", f"The file failed while being loaded: {outcome.failure}", detail=outcome.detail, unit="Unit 8 (read generated code before running it)", ) return report # --- Differential test: first divergence ------------------------------ first_divergence: tuple[int, object, Fraction] | None = None type_offenders: list[tuple[int, str]] = [] for n in range(max_n + 1): expected = oracle.bernoulli(n) if n in outcome.raised: kind, _, message = outcome.raised[n].partition(": ") report.add( "raises", f"The routine raised {kind} at n={n}.", detail=( f"{message}\n" "The contract says bernoulli(n) is defined for every n >= 0.\n" "A routine that works for 2..12 but not 0 or 1 is a range bug." ), unit="Unit 10 (specify the valid range)", ) break if n not in outcome.values: break report.checked_up_to = n if outcome.types.get(n) != "Fraction": type_offenders.append((n, outcome.types.get(n, "?"))) got = outcome.fractions.get(n) same = got is not None and got == expected if not same and first_divergence is None: first_divergence = (n, _shown(outcome, n), expected) # --- Exact-arithmetic check ------------------------------------------ if type_offenders: n, typename = type_offenders[0] report.add( "not-fraction", f"The routine returns {typename}, not fractions.Fraction.", detail=( f"First seen at n={n}. Bernoulli numbers have large numerators and\n" "denominators; binary floating point cannot represent them exactly.\n" "A float can look right at every index and still be inexact: what\n" "grows is the size of the error, so compare exactly, not within a\n" "tolerance." if typename == "float" else f"First seen at n={n}. The contract is: bernoulli(n: int) -> fractions.Fraction." ), unit="Unit 6 (exact rational arithmetic), Unit 8 (why we compare exactly)", ) # --- First divergence ------------------------------------------------- if first_divergence is not None: n, got, expected = first_divergence report.add( "divergence", f"First divergence at n={n}: expected {expected}, got {got}.", detail=( "Everything below this index matched. The first divergence is the\n" "best place to start debugging. It does not prove that later\n" "differences have the same cause." ), unit="Unit 8 (differential testing against an oracle)", ) # --- Named failure modes --------------------------------------------- report.findings.extend( _diagnose_pattern( outcome.fractions.get, max_n, show=lambda n: _shown(outcome, n) ) ) return report def render_report(report: Report, verbose: bool = False) -> str: """Format a report for a learner reading a terminal.""" lines: list[str] = [] lines.append("=" * 68) lines.append(f"Checking: {report.path}") lines.append(f"Oracle convention: {oracle.CONVENTION}") lines.append("=" * 68) if report.passed: lines.append("") lines.append(f"PASS - agrees with the oracle for every n from 0 to {report.checked_up_to},") lines.append(" returns exact Fractions, and odd terms above B1 are zero.") lines.append("") lines.append("Passing is not the end of the job. You still have to be able to say") lines.append("*why* it is correct. That is the Unit 17 defence.") if verbose: lines.append("") lines.append(f"(Indices compared: 0 to {report.checked_up_to})") return "\n".join(lines) lines.append("") lines.append(f"FAIL - {len(report.findings)} problem(s) found.") lines.append("") for finding in report.findings: lines.append(finding.render()) lines.append("") if verbose: lines.append(f"(Indices compared: 0 to {report.checked_up_to})") lines.append("Fix the specification or the code, then run this check again.") return "\n".join(lines) def _main(argv: list[str] | None = None) -> int: parser = argparse.ArgumentParser( description="Check a Bernoulli implementation against the trusted oracle.", epilog="This tool runs the file you give it, in a separate process. Read it first.", ) parser.add_argument("submission", help="path to the Python file to check") parser.add_argument( "--max-n", type=int, default=DEFAULT_MAX_N, help=f"highest index to compare (default: {DEFAULT_MAX_N})", ) parser.add_argument("--verbose", action="store_true", help="show extra detail") args = parser.parse_args(argv) if args.max_n < 0: parser.error(f"--max-n must be 0 or more, not {args.max_n}: a negative range checks nothing") report = check_submission(args.submission, max_n=args.max_n) print(render_report(report, verbose=args.verbose)) return 0 if report.passed else 1 if __name__ == "__main__": sys.path.insert(0, str(Path(__file__).resolve().parent)) raise SystemExit(_main())