Skip to content

Quod 0.5.0

Choose a tag to compare

@github-actions github-actions released this 12 Nov 10:34
· 11 commits to main since this release

Quod 0.5.0: maps and sets. map<K, V> and set<T> are finite and immutable, proved by the solver, and generated for Python and C#. Nothing changes for a program that does not use them.

Install

As for 0.1.0: download the package for
your system, unpack it, and run quod from that folder (z3 4.12.1 is inside). On macOS, run
xattr -d com.apple.quarantine quod z3 in the folder first. The MCP server:
claude mcp add quod -- /path/to/quod mcp, or see
docs/mcp.md. Quod.Build, attached, is a NuGet package:
see its README.

A program

fn bump(m: map<int, nat>, k: int) -> map<int, nat>
  ensures k in result
  ensures result[k] == (if k in m { m[k] + 1 } else { 1 })
  ensures forall j in keys(result): j == k || j in m
  ensures forall j in keys(m): j != k ==> j in result && result[j] == m[j]
{
  put(m, k, if k in m { m[k] + 1 } else { 1 })
}

Added

  • map<K, V> and set<T>, equal by their entries whatever the order they were built in. Keys and elements are of an ordered type: the integers, char, bool, string, and the tuples, structs and enums made of those. Values are of any type. Design note (in French) and the reference.
  • Operations as functions, no new syntax but two: map_of([(k, v), ...]) and set_of([...]) (a list written in place), put, remove, add, keys, union, inter, diff, subset, len. m[k] reads, with the proof obligation k in m; k in m and x in s are booleans.
  • forall x in s and exists x in s in contracts, over a set (for a map, keys(m)). Until now a quantifier ran over an interval a..b only.
  • sorted(s) and sorted_keys(m), the one way to walk a collection in code: a sequence in ascending order, which a while loop reads by index. No result depends on the order of insertion or of a hash. For numbers and chars the solver knows the order. An enum can be a key but is not sorted.
  • The completeness check works on maps: a contract on a map result that leaves two results possible is refused, with the two maps as the witness.
  • import maps: get_or, count_up and merge, written in Quod and proved with the program.
  • Linear loops: m = put(m, k, v) and s = add(s, x) on a local that nothing else sees change it in place, in Python and in C#.
  • Python: a dict and a frozenset. C#: IReadOnlyDictionary<K, V> and HashSet<T>; a string key is a C# string.
  • quod_run takes a map as an array of [key, value] pairs and a set as an array.
  • The search for counterexamples is bounded in work (review of 0.5.0). The check runs each function on small inputs, and tries each integer constant of the program as the value of each integer parameter; a constant such as 2147483647, written anywhere, made a loop elsewhere run for a million statements, again and again, and with a map in the loop the check lasted minutes. A run is now cut after 100,000 statements (a change to a map or a set counts for one statement in eight of its entries), the constants may spend 600,000 in all, and the other inputs 1,400,000. These are counts, not seconds: the same file gets the same verdict. A program of nine lines that took 62 s takes 2 s.
  • Two messages: a in s == true says that in does not chain, and a function of the program named like an operation on maps (put, sorted...) says that it hides the operation. A null map or set given to a C# method raises ArgumentNullException.

Known

Those of 0.4.2.

  • In C#, keys and elements are integers, booleans, strings, tuples of numbers and booleans, structs and enums. Values are integers, booleans, tuples of numbers and booleans, structs, enums, maps and sets: not strings, char or sequences. Anything else, and a struct or an enum that holds a map or a set, is refused by Quod when it generates the C#. sorted is generated for numbers, booleans, strings and tuples of numbers and booleans, not yet for structs.
  • In C#, a set is a HashSet<T>, which is changeable, and a set or a map a caller passes is used as it is, not copied: a method that keeps a HashSet of the caller's in the dictionary it returns shares it with the caller. A caller must not change a map or a set it passed, nor one it received.
  • remove(m, k) and k in m need k to be of the key type: on a map<nat, V>, a key of -1 is an error, where removing an absent key would have a meaning.
  • The size of a collection built in a loop is where proofs are hard: a counting loop whose invariant compares with a recursive occurrences(words[..i], w) did not prove within the limit. A loop that builds a map or a set with simple invariants proves in a fraction of a second.
  • The completeness of a contract that spells out the order of sorted is not decided within the limit (a warning, not an error).
  • No traversal in order of insertion, no iteration over a map other than by its sorted keys, no enum order: by design.

Measured

  • All 271 tests of the compiler pass.

  • The mutant benches, on a Release build: the 64 mutants of the reference programs give the verdicts of 0.3 (57 refuted with a counterexample, 7 survivors, all equivalent mutants), and the 31 of the quantified requires give 29 refuted, 1 rejected without a hint and 1 survivor (30 mutants and 28 refuted in 0.3). A new bench of 22 mutants of a program on maps, sets and sorted: 22 refuted with a counterexample (the slowest in 25 s). The slowest check of the reference programs took 80 s (68 s in 0.3; 126 s before the search for counterexamples was bounded in work).

  • No agent trial, and no comparison with other tools, was done for maps and sets.

  • Not run: macOS and Linux binaries (built by CI only).