Skip to content

Formally verified Literate Go programming: 0.2.1 - #1

Merged
tlehman merged 1 commit into
masterfrom
worktree-vego
Sep 22, 2026
Merged

tlehman merged 1 commit into
masterfrom
worktree-vego

Conversation

@tlehman

@tlehman tlehman commented Sep 20, 2026 •

Copy link
Copy Markdown
Owner

What

litgo now proves VeGo annotations: contracts, loop invariants and variants, measures for recursion, written as //@ comments in ordinary Go.

//@ Requires n >= 0 ^ d > 0
func Divide(n, d int) (q, r int) {
	r = n
	//@ Invariant n = q*d + r ^ r >= 0
	//@ Variant r
	for r >= d {
		q, r = q+1, r-d
	}
	return q, r
}
//@ Ensures n = q*d + r ^ 0 <= r < d

The paper's vegop is not published, so internal/vego is 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 check includes proofs.
  • litgo run: tangle, prove, compile, run. A failed proof stops the run like a compile error, at a line of the Markdown, with source vego. --no-prove runs anyway.
  • litgo lsp: proofs as you type, after the type check.
  • Neovim: //@ 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*hi reads 𝑙𝑜² ≤ 𝑛 ∧ 𝑛 < ℎ𝑖² until the cursor is on the line (render.proofs = false turns it off).
  • Seg.out / Seg.src carry the column arithmetic of Map, Locate and Exact, with src(out(col)) = col and out(src(col)) = col as proved contracts. The segment search stays tested, and "Two halves of one map" says which is which.
  • Examples: 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).
  • Annotations survive gofmt: // @ Requires in a doc comment and a blank line above Ensures are both read.
  • The pages workflow proves the document and the examples.

Notes

  • VERSION is 0.2.1, so merging publishes the release.
  • The run: directive names . ./internal/... instead of ./...: running the examples leaves several mains in examples/.

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.

@tlehman tlehman changed the title Formally verified Literate Go programming: 0.2.0 Formally verified Literate Go programming: 0.2.1 Sep 22, 2026
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 tlehman left a comment

Copy link
Copy Markdown
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@tlehman
tlehman merged commit c67c84c into master Sep 22, 2026
@tlehman
tlehman deleted the worktree-vego branch September 22, 2026 00:17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant