Skip to content
v0.6.11

LemmaScript — Dafny Backend Specification

This document covers what is unique to the Dafny backend. See Specification for the shared annotation language, translation rules, type mapping, and pipeline.


For each verified TS function foo.ts, there are two Dafny files:

FileWho writes itPurpose
foo.dfy.genlsc genGenerated from TS. Always regeneratable. Merge base.
foo.dfyLLM / UserStarts as copy of gen. Proof annotations added here. Source of truth.

The .dfy.gen extension prevents Dafny tooling from auto-verifying it.

The diff between gen and dfy must be additions only — the LLM may insert helper lemmas, ghost predicates, assert statements, and loop invariants, but may not modify generated lines.

Added lines may not contain assume statements or {:axiom} / @Axiom attributes; occurrences inside comments, strings, and character literals are ignored. Added lines also may not introduce an // lsc options: line, since verifier options are read from that header.

"proof-dir": "proofs" in lemmascript.json relocates the complete Dafny artifact set while preserving the pair: a source src/search/foo.ts under that config uses proofs/src/search/foo.dfy.gen and proofs/src/search/foo.dfy. Regen state (.dfy.base and .dfy.merged) lives there too. The path is relative to the config file, and source subdirectories are mirrored to prevent basename collisions. The source must be below the config directory. When enabling the option, move the hand-written .dfy; .dfy.gen can be regenerated. If lsc finds an existing beside-source proof but no mapped proof, it fails instead of silently seeding a new .dfy. Lean artifacts are not affected by this option.


Pure TS functions become Dafny function declarations (no wrapper, no namespace). requires and ensures are emitted directly. If the function has ensures, a companion lemma is generated as a proof target for the LLM:

function clamp(v: int, lo: int, hi: int): int
requires lo <= hi
{
if v < lo then lo
else if v > hi then hi
else v
}
lemma clamp_ensures(v: int, lo: int, hi: int)
requires lo <= hi
ensures clamp(v, lo, hi) >= lo
ensures clamp(v, lo, hi) <= hi
{
}

Non-pure functions become Dafny method declarations.


lsc regen --backend=dafny foo.ts:

  1. Read old foo.dfy.gen before overwriting
  2. Regenerate foo.dfy.gen
  3. If foo.dfy doesn’t exist → create from gen, verify unless --no-verify, done
  4. Choose the existing .dfy.base, or otherwise the old gen, as the anchor; merge (git merge-file) when the new gen differs
  5. Check additions-only invariant
  6. Verify merged foo.dfy unless --no-verify; if verification fails, advance .dfy.base to the new gen before exiting with failure
  7. On success, delete .dfy.base (gen is now the anchor), including when verification was explicitly skipped

On merge conflict, foo.dfy is left unchanged and the merged result is saved as foo.dfy.merged for manual inspection. Conflicts and additions-only failures retain the old anchor. A verifier failure after a clean additions-only merge instead retains the new anchor, because the proof already contains that generation; the next retry must not merge it a second time.

Merges use --diff-algorithm=minimal, matching the additions-only check so large proof additions do not cause spurious generated-line deletions in the diff. Git versions before 2.44 fall back to the default algorithm with a warning; upgrading avoids the resulting false conflicts. Git execution errors leave the proof unchanged and retain the old anchor, but do not create .dfy.merged or record a verification conflict.


The Dafny emitter auto-injects helper functions when needed. Each is emitted at most once, only when a construct that requires it appears (registry: PREAMBLE_CODE in dafny-emit.ts).

Core:

HelperWhenPurpose
Option<T>Map.get, optional typesdatatype Option<T> = None | Some(value: T)
SetToSeqfor (x of set), map/record iterationConvert set to sequence for iteration
SetFromSeqnew Set(arr)Build a deduplicated set from a sequence (set x | x in s)

Numeric:

HelperWhenPurpose
JSFloorDivMath.floor(a/b) (int args)JS-compatible floor division
FloorReal / CeilRealMath.floor(x) / Math.ceil(x) (real arg); Math.round(x) as FloorReal(x + 0.5)real → int via .Floor
JSTruncDivMath.trunc(a/b) (int/nat args), bigint /JS-compatible truncated division
TruncRealMath.trunc(x) (real arg)real → int toward zero
MathAbs / MathMin / MathMaxMath.abs/min/max (int args)Scalar integer abs/min/max
MathAbsReal / MathMinReal / MathMaxRealMath.abs/min/max (any real arg)Scalar real abs/min/max; int/nat operands coerced with as real
MaxOfSeq / MinOfSeqMath.max(...s) / Math.min(...s)Aggregate over a sequence (requires |s| > 0)
MaxOfSeqReal / MinOfSeqRealMath.max/min with a real spread or mixed real/integer segmentsReal extrema over a nonempty sequence; Concat lemmas transfer bounds through concatenation
SeqIntToRealInteger spread mixed with real operandsConvert elements to real, preserving length and each indexed value
Pow2 / BitAnd<< / >> / & on bigintBitwise ops as arithmetic
NatToString / IntToString`${n}` template literal (nat / signed int)Number-to-digit-string for interpolation (IntToString prefixes -)

Math.trunc and Math.round are the identity on int/nat arguments. Math.round rounds halfway ties toward +Infinity (Math.round(-2.5) == -2). These lowerings use exact reals, so there is no -0, NaN, or Infinity. JS Math.round returns the nearest integer without rounding x + 0.5, so it agrees with FloorReal(x + 0.5) on every finite double (Math.round(0.49999999999999994) is 0 in both). A bigint argument is a compile error.

Sequence:

HelperWhenPurpose
SeqIndexOfarr.indexOf(x)First-index search (-1 if absent)
CallbackIndicesArray callbacks (other than map) that use index or source-array argumentsOrdered positions [0, ..., n-1], with proved length, indexing, and membership contracts
SeqFilter / SeqAll / SeqFoldLeftfilter / every / reduce with dafny-library: localLocal recursive collection helpers (no Dafny standard-library dependency)
SeqFindIndexarr.findIndex(f)Predicate first-index search
SeqFindarr.find(f)Predicate first-match search
SeqFindLastarr.findLast(f)Predicate last-match search
SeqFilterSomefilterMap pattern (§3.7)Drop Nones and unwrap to seq<T>
SeqFlattenarr.flat()Flatten one level
SeqJoinarr.join(sep)Join into a string
SafeSlicearr.slice(lo, hi) with effective safe-slice: trueBounds-clamping slice
Permperm(a, b) (spec-only)predicate Perm<T(==)>(a, b) { multiset(a) == multiset(b) }

String:

HelperWhenPurpose
StringIndexOfs.indexOf(sub), s.indexOf(sub, from), s.includes(sub)Recursive string search (also provides StringIndexOfFrom)
StringSearchPositionExplicit positions in indexOf, includes, startsWith, endsWithClamp integer positions to the string length
StringStartsWithAt / StringEndsWithAtExplicit positions in startsWith / endsWith, respectivelyTest a prefix or suffix at the clamped position
StringSplits.split(d)Axiomatic split (1 <= |res| <= |s| + 1)
StringTrims.trim() / s.trimEnd() / s.trimStart()Trim (also provides StringTrimRight / StringTrimLeft); strips the full ECMAScript whitespace set via IsJSWhitespace, not just ' '
StringToLower / StringToUppers.toLowerCase() / s.toUpperCase()Axiomatic case conversion: equals AsciiToLower(s) / AsciiToUpper(s) when StringIsAscii(s), otherwise unconstrained

String semantics. Set string-semantics in lemmascript.json or a file’s //@ option directive (SPEC.md §7.6). Proofs depend on the selected model:

SettingMeaning
"unicode-scalar" (default)Strings are Unicode scalar sequences. .length, indexing, slice, charCodeAt, and indexOf can differ from JavaScript for characters such as emoji. Unpaired surrogates are unsupported.
"javascript-utf16"Strings are UTF-16 code-unit sequences. .length, indexing, slice, and charCodeAt use JavaScript code-unit positions and values; indexing and slicing retain the fragment’s bounds obligations. Requires "dafny-library": "local".

In both profiles, case conversion is specified only for ASCII input. String.fromCharCode requires a Unicode scalar in the default profile, or 0 <= n < 0x10000 in UTF-16 mode. Generated files record every UTF-16 selection in their header; the default profile adds no string-semantics setting.

Collection helpers. dafny-library selects standard-library helpers (stdlib, the default) or generated helpers (local) for filter, every, and reduce. Unicode-scalar mode supports either; UTF-16 mode requires an explicit local setting.

This choice does not change string semantics or control handwritten proof imports. Those imports must still be compatible with the selected string model (see §5). Both settings support file directives; see examples/utf16.ts.

Indexed callbacks. In either library mode, CallbackIndices(n) constructs [0, ..., n-1] as a seq<int>:

function CallbackIndices(n: nat): (r: seq<int>)
ensures |r| == n
ensures forall i :: 0 <= i < n ==> r[i] == i
ensures forall i :: i in r <==> 0 <= i < n
{
if n == 0 then [] else CallbackIndices(n - 1) + [n - 1]
}

Callers get the length, order, and membership facts without unfolding it. The adapter binds the receiver once and iterates these positions, passing (source[i], i, source) (after the accumulator for reduce); filter and find map selected positions back to elements, and map skips the helper, since its seq comprehension already has the position in hand. An existential some proof may need a witness such as assert 1 in CallbackIndices(2); — see examples/callbackArguments.dfy.


lsc check --backend=dafny foo.ts:

  1. Generate foo.dfy.gen + seed foo.dfy
  2. Check additions-only invariant
  3. Run dafny verify foo.dfy

Standard libraries are auto-detected: if foo.dfy contains import Std., the --standard-libraries flag is added.

lsc verifies each .dfy using the string semantics recorded in its generated header, even if the project configuration has changed. A file without a string-semantics header uses unicode-scalar.

Proof additions must preserve the generated file’s string model. Conflicting or duplicate model settings are errors, including when verification is skipped.

Proofs using javascript-utf16 cannot import Dafny’s precompiled standard library (Std.*); verification reports an error if they do. Proofs using unicode-scalar can use that library.

The shared --time-limit=<seconds> flag (SPEC.md §7) maps to Dafny’s --verification-time-limit; --extra-flags=<string> is forwarded verbatim to dafny verify.