Repository navigation
Formally verified Literate Go programming: 0.2.1 - #1
Merged
Merged
Conversation
tlehman
force-pushed
the
worktree-vego
branch
from
September 20, 2026 22:30
5c5470f to
7cb03bc
Compare
tlehman
force-pushed
the
worktree-vego
branch
from
September 22, 2026 00:14
76ed558 to
4d596e3
Compare
litgo now checks VeGo (arXiv:2608.22630) //@ annotations: Requires, Ensures, Exsures, Invariant, Variant, Measure, BaseCase, InductionHypothesis, Assert, Axiom, Preserves, Predicate, quantifiers, slice ranges and primed variables. The paper's vegop is not published, so internal/vego is a verifier of litgo's own: symbolic execution of a Go fragment, and a pure-Go prover (quantifier instantiation, cheap first and deeper on failure, polynomial normalisation, Fourier-Motzkin elimination). It is sound and incomplete, and reports what it cannot follow as not verified. - litgo prove, and a proof stage in litgo run (--no-prove), check and lsp - Neovim: //@ annotations and failed proofs in violet, :Prove; formulas typeset like $...$ math (^ as ∧, <= as ≤, Forall as ∀, x*x as x²) - Seg.out and Seg.src carry the Map/Locate round trip as a proved contract - examples: isqrt, vego-tutorial, and a proved heap and ring buffer - annotations survive gofmt (// @ in doc comments, blank line above Ensures)
tlehman
force-pushed
the
worktree-vego
branch
from
September 22, 2026 00:16
4d596e3 to
ba08877
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
What
litgo now proves VeGo annotations: contracts, loop invariants and variants, measures for recursion, written as
//@comments in ordinary Go.The paper's
vegopis not published, sointernal/vegois a verifier of litgo's own, in pure Go with no solver: symbolic execution of a Go fragment, loops cut at their invariants, and a prover built on quantifier instantiation, polynomial normalisation and Fourier-Motzkin elimination. It is sound and incomplete, and an annotated function that steps outside the fragment is reported as not verified rather than passed. Integers are mathematical; overflow is not modelled.Where it shows up
litgo prove [--json] FILE..., new.litgo checkincludes proofs.litgo run: tangle, prove, compile, run. A failed proof stops the run like a compile error, at a line of the Markdown, with sourcevego.--no-proveruns anyway.litgo lsp: proofs as you type, after the type check.//@annotations and failed proofs in violet (LitgoProof*groups,lua/litgo/proof.lua),:Prove/\p. The formulas are typeset the way$...$math is:lo*lo <= n ^ n < hi*hireads𝑙𝑜² ≤ 𝑛 ∧ 𝑛 < ℎ𝑖²until the cursor is on the line (render.proofs = falseturns it off).Seg.out/Seg.srccarry the column arithmetic ofMap,LocateandExact, withsrc(out(col)) = colandout(src(col)) = colas proved contracts. The segment search stays tested, and "Two halves of one map" says which is which.isqrt.lit.md(a proved integer square root),vego-tutorial.lit.md(every annotation, 15 proved functions, ending in binary search),heap.lit.md(a binary heap's numbering is a tree, its root is its maximum, a ring buffer keeps its invariant).// @ Requiresin a doc comment and a blank line aboveEnsuresare both read.Notes
VERSIONis0.2.1, so merging publishes the release.run:directive names. ./internal/...instead of./...: running the examples leaves severalmains inexamples/.Tested
bin/litgo run litgo.lit.md(prove, vet, test, rebuild), re-tangling is a fixed point,nvim --headless -u NONE -l test/plugin.lua, HTML and PDF weave of the document and the examples.