Basis uses LLMs to formalize language semantics, Lean-verified interpreter down to RISC-V machine code
patrickmineault · x · 2026-10-17
Basis published "Ship Your Interpreter": they had LLMs write precise formal semantics for a small programming language, then used Lean to prove the interpreter follows those rules even after compilation to low-level RISC-V machine instructions.
Key points:
- Program verification needs a program, a specification, and semantics. Most languages (Python, Ruby, Lua…) lack formal semantics because writing them by hand is painful.
- Naively asking an LLM to write semantics yields mistakes — but interpreters/compilers serve as ground truth to check against.
- The team argues the bottleneck in verifying the world's software is shifting from theorem proving to specifications and semantics, and their approach can scale across all programming languages.
- Context: in April their agents built a JS-to-WebAssembly compiler they couldn't prove behavior-preserving; later they verified Linux's nftables compiler; in September MIT researchers verified the xv6 kernel down to machine code with AI agents.
- Goal: critical infrastructure secure by design, keeping pace with AI-assisted attackers.
More from coding & agent
- Backend migration from Python to Go now takes one engineer just one week — rakyll · 2026-10-17
- Audio founder says Claude one-shot decompiled rival algorithms, moat gone — ChrisGPT · 2026-10-17
- Google's playbook for agent evals: four layers of checks beyond the vibe check — rseroter · 2026-10-17
- AgentForesight: a 7B online auditor that catches multi-agent failures mid-run — jiqizhixin · 2026-10-17
- Qwen3.8-27B shows a weird write-delete loop in /tmp before every web research task — Training-Respect8066 · 2026-10-17
- Dev gives his agent an alarm tool to wake him during overnight /goal runs — zack_overflow · 2026-10-17