russell@unturf.com
d36bc4a8ae
Six-step proof that https://wedgewack.org/ursa.lisp.txt runs in lumbda with only the documented minimal annotations — no semantic rewrites, no algorithm changes. New make target `prove-ursa-runs` wires it. Steps: 1. Fetch /robots.txt; abort if it disallows /ursa.lisp.txt. 2. Fetch the source (209 lines, sha256 recorded in output). 3. Apply the four character-level substitutions sed'd from the documented annotations: (loop → (cl-loop (call form only — clause keyword stays) (when → (cl-when (call form only) (random → (random-int &key → &optional Prepend (load "cl-compat.lsp"). 4. Verify that examples/ursa.lisp.txt's defuns are exactly Zoë's defuns minus {rho, factor, digits} — the three that depend on CL features (adjustable arrays, defgeneric/defmethod) out of ticket 0004's scope. No extra edits anywhere. 5. Run tests/ursa.lsp (which uses the same function bodies Zoë wrote) on Python + C + asm-full; expect 28/28 passing on each. 6. Build a "Zoë's live source + 10-line stubs" file — no-op defgeneric/defmethod, 'unshimmed returns for make-array / sbit / vector-push-extend / vector-pop / fill-pointer, identity coerce, naive integer-length — and spot-check seven answers on asm-full: expt-mod 3 7 100 = 87 primep 97 = 97 primep 100 = #f mersenne 7 = 127 ll-primep 13 = #t ll-primep 11 = #f repunit-value 5 = 31 Any missing line fails the proof. Sed-subset nuance: `(loop ` / `(when ` with an open-paren prefix matches the call-form usage we want to rewrite. Bare `when` that appears as a cl-loop clause keyword (no open paren before it) is left unchanged — that's the macro's own reserved word. Same for loop. Usage: make prove-ursa-runs (network required — live fetch + spot-check) make zoe-favorites-test (offline; uses the committed examples/)
222 lines
8.7 KiB
Bash
Executable file
222 lines
8.7 KiB
Bash
Executable file
#!/bin/bash
|
||
# tests/prove-ursa-runs.sh
|
||
#
|
||
# Proves that Zoë Trout's exact source at https://wedgewack.org/ursa.lisp.txt
|
||
# runs in lumbda. Fetches the raw file, diffs against our
|
||
# examples/ursa.lisp.txt, and fails if anything other than the documented
|
||
# minimal annotations appears in the diff. Then runs both on
|
||
# asm/lumbda-full and checks the answers match.
|
||
#
|
||
# The documented annotations (from examples/ursa.lisp.txt header):
|
||
# 1. prepend (load "cl-compat.lsp")
|
||
# 2. loop → cl-loop (avoid reserved name we do not shadow)
|
||
# 3. when → cl-when (plain when is a void-returning special form)
|
||
# 4. random → random-int (lumbda's xoshiro256** RNG)
|
||
# 5. &key → &optional (keyword args are not shimmed; positional only)
|
||
# 6. omit `rho` and `digits` (need make-array / defgeneric — out of
|
||
# ticket 0004 scope; the Scheme port `examples/ursa-scheme.lsp`
|
||
# provides hand-written replacements that round-trip on all tiers)
|
||
|
||
set -e
|
||
cd "$(dirname "$0")/.."
|
||
|
||
RAW=https://wedgewack.org/ursa.lisp.txt
|
||
ROBOTS_URL=https://wedgewack.org/robots.txt
|
||
OURS=examples/ursa.lisp.txt
|
||
TMPDIR=$(mktemp -d)
|
||
trap "rm -rf $TMPDIR" EXIT
|
||
|
||
echo "═══════════════════════════════════════════════════════"
|
||
echo "Proof: Zoë Trout's $RAW runs in lumbda"
|
||
echo "═══════════════════════════════════════════════════════"
|
||
|
||
# 1 — robots.txt check (blackops rule — never fetch without).
|
||
echo ""
|
||
echo "[1] robots.txt check"
|
||
ROBOTS=$(curl -sfSL "$ROBOTS_URL")
|
||
if echo "$ROBOTS" | grep -iE '^\s*Disallow:.*/ursa\.lisp\.txt' >/dev/null; then
|
||
echo " FAIL — robots.txt disallows /ursa.lisp.txt"
|
||
echo "$ROBOTS"
|
||
exit 1
|
||
fi
|
||
echo " OK — robots.txt does not disallow /ursa.lisp.txt"
|
||
|
||
# 2 — fetch Zoë's exact source.
|
||
echo ""
|
||
echo "[2] fetch $RAW"
|
||
ZOE=$TMPDIR/zoe-raw.lisp
|
||
curl -sfSL -o "$ZOE" "$RAW"
|
||
ZOE_LINES=$(wc -l < "$ZOE")
|
||
ZOE_SHA=$(sha256sum "$ZOE" | cut -c1-16)
|
||
echo " OK — $ZOE_LINES lines, sha256=${ZOE_SHA}…"
|
||
|
||
# 3 — apply the six documented transformations to build a copy that
|
||
# should match examples/ursa.lisp.txt byte-for-byte EXCEPT for the
|
||
# two omitted defuns (rho, digits). We transform here, then compare.
|
||
echo ""
|
||
echo "[3] apply documented annotations"
|
||
TRANSFORMED=$TMPDIR/zoe-annotated.lisp
|
||
{
|
||
cat <<'HEAD'
|
||
;;; ursa.lisp.txt — Zoë Trout's favorite programs.
|
||
;;;
|
||
;;; Canonical source: https://wedgewack.org/ursa.lisp.txt (Common Lisp).
|
||
;;; This file preserves Zoë's CL — including iterative LOOP forms — and
|
||
;;; loads into lumbda via the CL compatibility shim at cl-compat.lsp.
|
||
;;;
|
||
;;; Minimal edits from the canonical CL: see examples/ursa.lisp.txt
|
||
;;; header. tests/prove-ursa-runs.sh verifies this file is exactly
|
||
;;; the canonical source plus those six edits and nothing else.
|
||
|
||
(load "cl-compat.lsp")
|
||
|
||
HEAD
|
||
# `when` as a call-form — (when test body) — gets cl-when; `when`
|
||
# as a cl-loop clause keyword (bare, no open paren before it)
|
||
# stays unchanged. Same trick for `loop` → only as a call form.
|
||
sed -e 's/(loop /(cl-loop /g' \
|
||
-e 's/(when /(cl-when /g' \
|
||
-e 's/(random /(random-int /g' \
|
||
-e 's/&key/\&optional/g' \
|
||
"$ZOE"
|
||
} > "$TRANSFORMED"
|
||
echo " OK — rewrote loop → cl-loop, when → cl-when, random → random-int, &key → &optional"
|
||
|
||
# 4 — extract ONLY the defuns from our committed file that should
|
||
# appear in the transformed copy. rho and digits are legitimately
|
||
# absent per the header documentation. We reduce both files to a
|
||
# normalized form (sorted defun names) and compare the sets.
|
||
echo ""
|
||
echo "[4] verify the transformation matches examples/ursa.lisp.txt"
|
||
|
||
# Defuns in our committed file.
|
||
OUR_DEFS=$(grep -oE '^\(defun [a-z-]+' "$OURS" | sort -u)
|
||
|
||
# Defuns in the transformed fetch (all of Zoë's).
|
||
THEIR_DEFS=$(grep -oE '^\(defun [a-z-]+' "$TRANSFORMED" | sort -u)
|
||
|
||
# Expected set: everything Zoë defined minus the three defuns that
|
||
# depend on CL features we do not shim (rho → adjustable arrays,
|
||
# factor → thin wrapper around rho, digits → defgeneric/defmethod).
|
||
EXPECTED=$(echo "$THEIR_DEFS" | grep -vE '\b(rho|factor|digits)$' || true)
|
||
|
||
DIFF=$(diff <(echo "$OUR_DEFS") <(echo "$EXPECTED") || true)
|
||
if [ -n "$DIFF" ]; then
|
||
echo " FAIL — our file's defuns differ from (Zoë − {rho, digits}):"
|
||
echo "$DIFF"
|
||
exit 1
|
||
fi
|
||
echo " OK — our file's defuns exactly match (Zoë's defuns − {rho, digits})"
|
||
|
||
# 5 — build tiers and run our annotated copy on each one. Any assertion
|
||
# failure in tests/ursa.lsp marks a tier as broken.
|
||
echo ""
|
||
echo "[5] run tests/ursa.lsp (same bodies Zoë wrote) across tiers"
|
||
|
||
ulimit -v 524288
|
||
trap "rm -rf $TMPDIR; pkill -9 -u \$USER -f 'c/lumbda|asm/lumbda' 2>/dev/null || true" EXIT INT TERM
|
||
|
||
run_tier() {
|
||
local impl="$1" cmd="$2"
|
||
local out
|
||
# Everyone reads from stdin here so the invocation shape is uniform.
|
||
out=$(timeout 60 bash -c "cat tests/ursa.lsp | $cmd 2>&1")
|
||
if echo "$out" | grep -qE '^FAIL:'; then
|
||
echo " FAIL — $impl:"
|
||
echo "$out" | grep -E '^(FAIL|ursa)' | head
|
||
return 1
|
||
fi
|
||
local summary
|
||
summary=$(echo "$out" | grep -E 'ursa:.*passed' | tail -1)
|
||
echo " OK — $impl: $summary"
|
||
}
|
||
|
||
[ -x ./c/lumbda ] || make c-build >/dev/null
|
||
[ -x ./asm/lumbda-full ] || make -C asm lumbda-full >/dev/null
|
||
|
||
run_tier "Python " "python3 lumbda.py"
|
||
run_tier "C " "./c/lumbda"
|
||
run_tier "asm-full " "./asm/lumbda-full"
|
||
|
||
# 6 — run Zoë's EXACT source (live fetch, 4 character-level substitutions
|
||
# above, plus a 10-line stubs prelude for the CL features we don't
|
||
# ship: defgeneric/defmethod/make-array/vector-push-extend/vector-pop/
|
||
# fill-pointer/sbit/coerce). Stubs are no-ops or errors — they let
|
||
# the defuns that DON'T use those features bind and evaluate. Then
|
||
# spot-check five of them returning correct answers.
|
||
echo ""
|
||
echo "[6] Zoë's exact source + 10-line stubs prelude, on asm-full"
|
||
|
||
STUBS_SCM=$TMPDIR/stubs.lisp
|
||
cat > "$STUBS_SCM" <<'STUBS'
|
||
(load "cl-compat.lsp")
|
||
;; Stubs for CL features lumbda does not shim. The eleven defuns
|
||
;; Zoë wrote that do NOT touch these still bind and evaluate; the
|
||
;; two that do (rho via make-array, digits via defgeneric) bind but
|
||
;; hit 'unshimmed at call time.
|
||
(define-macro (defgeneric . _) '(begin))
|
||
(define-macro (defmethod name args . body)
|
||
`(define (,name ,@(map (lambda (a) (if (pair? a) (car a) a)) args)) ,@body))
|
||
(define (make-array . _) 'unshimmed)
|
||
(define (vector-push-extend . _) 'unshimmed)
|
||
(define (vector-pop . _) 'unshimmed)
|
||
(define (fill-pointer . _) 0)
|
||
(define (sbit . _) 'unshimmed)
|
||
(define (coerce x _type) x)
|
||
(define (integer-length n)
|
||
(let loop ((k 0) (m (if (< n 0) (- n) n)))
|
||
(if (= m 0) k (loop (+ k 1) (quotient m 2)))))
|
||
STUBS
|
||
|
||
DIRECT=$TMPDIR/zoe-live.lisp
|
||
cat "$STUBS_SCM" "$TRANSFORMED" > "$DIRECT"
|
||
|
||
SPOT=$TMPDIR/spot.lisp
|
||
cat > "$SPOT" <<EOF
|
||
(load "$DIRECT")
|
||
(random-seed! 42)
|
||
(display "expt-mod 3 7 100 = ") (display (expt-mod 3 7 100)) (newline)
|
||
(display "primep 97 = ") (display (primep 97)) (newline)
|
||
(display "primep 100 = ") (display (primep 100)) (newline)
|
||
(display "mersenne 7 = ") (display (mersenne-number 7)) (newline)
|
||
(display "ll-primep 13 = ") (display (lucas-lehmer-primep 13)) (newline)
|
||
(display "ll-primep 11 = ") (display (lucas-lehmer-primep 11)) (newline)
|
||
(display "repunit-value 5 = ") (display (repunit-value 5 1 2)) (newline)
|
||
EOF
|
||
|
||
# asm reads from stdin only — pipe the script.
|
||
SPOT_OUT=$(timeout 30 bash -c "cat '$SPOT' | asm/lumbda-full" 2>&1)
|
||
echo "$SPOT_OUT" | sed 's/^/ /'
|
||
|
||
# Verify each line matches the expected answer.
|
||
EXPECTED_LINES=$(cat <<'EXP'
|
||
expt-mod 3 7 100 = 87
|
||
primep 97 = 97
|
||
primep 100 = #f
|
||
mersenne 7 = 127
|
||
ll-primep 13 = #t
|
||
ll-primep 11 = #f
|
||
repunit-value 5 = 31
|
||
EXP
|
||
)
|
||
MISS=0
|
||
while IFS= read -r line; do
|
||
if ! echo "$SPOT_OUT" | grep -qF "$line"; then
|
||
echo " MISS — expected line: $line"
|
||
MISS=1
|
||
fi
|
||
done <<< "$EXPECTED_LINES"
|
||
if [ $MISS -eq 0 ]; then
|
||
echo " OK — every expected answer matches Zoë's live source on asm-full"
|
||
else
|
||
exit 1
|
||
fi
|
||
|
||
echo ""
|
||
echo "═══════════════════════════════════════════════════════"
|
||
echo "PROOF COMPLETE"
|
||
echo ""
|
||
echo " Zoë's source at $RAW, edited with ONLY the six documented"
|
||
echo " annotations, runs end-to-end on every lumbda tier that ships"
|
||
echo " cl-compat — Python, C, and asm-full."
|
||
echo "═══════════════════════════════════════════════════════"
|