The `internal_add`

perform tries to effectively insert a brand new vary of integers into an current listing of sorted and disjoint integer ranges. For instance, if we began with `[101..=102, 400..=402, 404..=405]`

and added `402..=404`

, we anticipate a results of `[101..=102, 400..=405]`

.

Ideally, I’d formally confirm this algorithm with Rust-specific instruments [1,2]. These instruments, nonetheless, appear arduous to make use of. As a substitute, I selected Dafny. Dafny is a language and verification system. It’s taught to undergraduates at universities world wide. It’s utilized in trade. I discover it to be addictively interactive and programmer pleasant.

Apart: Dafny creator, Dr. Rustan Leino has a connection to Rust past the coincidence of his first identify. He helped create Spec#, the primary language to make use of a sort system to keep away from null pointers. Rust, after all, adopted this concept to nice success.

This text covers guidelines 1 to six. Half 2 will cowl guidelines 7 to 9.

Earlier than making an attempt to show the mathematical correctness of your algorithm, resolve if the hassle is well worth the profit.

Dafny will not be Rust. Utilizing Dafny requires porting algorithms of curiosity from Rust to Dafny. This port can miss particulars and introduce errors. Given this threat, ought to *you *use Dafny to confirm Rust algorithms? I boldly declare that “it relies upon”.

- How necessary is your algorithm’s correctness? In case you are printing a report and it appears to be like proper, it most likely is true. The
`internal_add`

algorithm relates to a knowledge construction that I’d like others to make use of with confidence, giving me further motivation to confirm it. - Perhaps all formal verification, with present instruments, is just too arduous. I consider, nonetheless, that Dafny makes formal verification as straightforward as at the moment attainable. You can see formally verifying code simpler if you’re already accustomed to varieties (for instance, from Rust) and recursion/induction (used occasionally in Rust). You possibly can learn this text and resolve for your self if/when formal verification is simple sufficient to be helpful to you.
- Perhaps fuzzing (resembling
`cargo-fuzz`

) and property-based testing (resembling`QuickCheck`

) are ok. Though these strategies don’t present mathematical certainty, they’re intelligent, helpful, and simple to make use of. (The`range-set-blaze`

crate already makes use of`QuickCheck. See`

Rule 9.5 in a earlier article for particulars). - Perhaps formal verification is and can at all times be doomed as a result of writing a specification is as arduous as writing code. I disagree. Take into consideration refactoring. I usually begin coding by writing one thing easy. I then refactor this straightforward code for effectivity. For
`internal_add`

, I discovered the specification to be less complicated than any code. (You possibly can choose this for your self in Rule 4.)

Apart: Verification then turns into a computer-checked refactoring from a easy specification to a ultimate, environment friendly algorithm.

- Perhaps formal verification is and can at all times be doomed as a result of the halting downside tells us formally that formality isn’t typically attainable. The halting downside doesn’t doom us. Whereas we will’t at all times perceive
*arbitrary*code, we don’t have to. We solely want to know our personal code, which we (hopefully) wrote to be comprehensible. Beginning in Rule 2, we’ll see how Dafny simply verifies that*particular*loops and recursions halt. - Perhaps porting to Dafny is just too arduous. This has not been my expertise. Like Rust, Dafny mixes and matches crucial and useful programming. I discovered porting my algorithm to be easy.

Assuming you continue to wish to confirm your algorithm with Dafny, the next step is to be taught Dafny.

Dafny is each a programming language and an interactive verification system. I like to recommend you put in it as a VS Code extension.

To be taught it, begin at https://dafny.org/. Of particular curiosity is the On-line Tutorial and the Reference Guide. I additionally discovered the Verification Nook movies on YouTube useful. (Of attainable curiosity is the faculty textbook, *Program Proofs, *$49 for the Kindle Version). I discovered the programming language a part of Dafny simpler to be taught than Rust, maybe comparable in issue to C#.

Dafny, like Rust, is absolutely typed. Dafny, like Python, is rubbish collected. Here’s a “Whats up World”:

`// hey.dfy`

technique Most important()

{

var s := "Whats up World";

print s, "n";

}

Dafny, additionally like Python, gives integers of arbitrary measurement. Here’s a program that *provably *provides two pure numbers by repeatedly incrementing.

Some factors of curiosity:

- Dafny coding pointers observe C#, not Rust. So, we identify the perform
`SlowAdd`

not`slow_add`

(though both will run). - Dafny helps subtypes. For instance, any
`int`

that may be proven to be non-negative can be a`nat`

. - Task is
`:=`

and equality is`==`

. (There isn’t a`=`

.) - Operate parameters, for instance,
`x`

and`y`

above, are immutable. - Dafny makes use of
`ensures`

and`invariant`

statements to confirm the code at compile-type. It then removes these statements to complete compiling. - The inexperienced examine mark exhibits that this code verifies. Dafny’s VS Code extension will, by default, constantly attempt to validate every technique. This provides an virtually gambling-like pleasure to working with Dafny. Within the instance above, if I make
`y`

an`int`

fairly than a`nat`

, then validation ought to and can fail. (Can you determine why?) Dafny will mark my perform with a pink X and inform me “`This postcondition won't maintain: r == x + y`

”. - Dafny is aware of a few of the arithmetic of integers, arrays, units, maps, sequences, and so on. This usually permits it to complete the final particulars of validation by itself.

Now that you realize about Dafny, you need to let it learn about your algorithm.

The `range-set-blaze`

crate represents units of integers as sorted, disjoint ranges. For instance, this listing of three ranges:

`100..=2_393,`

20_303..=30_239_000,

501_000_013..=501_000_016

represents a set of 30,220,996 integers.

In Rust, the `RangeSetBlaze`

struct represents this information construction internally with a typical `BTreeMap.`

Recall {that a} `BTreeMap`

represents a listing of key/worth pairs, sorted by key. Right here, our keys are the ranges’ begins (for instance, `100`

, `20_303`

, `501_000_013`

) and the values are the ranges’ inclusive ends (for instance, `2_393`

, `30_239_000, 501_000_016`

. `RangeSetBlaze`

shops the listing with a `BTreeMap`

fairly than a `vec`

to make key lookup extra cache pleasant.

`RangeSetBlaze`

relies on `BTreeMap`

, so should we implement `BTreeMap`

in Dafny? Fortunately, no. We are able to, as a substitute, use Dafny’s `vec`

-like `seq`

information sort. This substitution works as a result of `BTreeMap`

, `vec`

, and `seq`

can all characterize sorted lists — simply with completely different efficiencies. For the aim of formal verification, we solely care about correctness and may ignore effectivity.

`RangeSetBlaze`

requires the listing of ranges be sorted and disjoint. How do we are saying “sorted and disjoint” in Dafny? We are able to say it by way of this *ghost predicate* (and associated code):

`ghost predicate ValidSeq(sequence: seq<NeIntRange>) i < j < `sort IntRange = (int, int)

sort NeIntRange = x: IntRange | !IsEmpty(x) witness (0,0)

perform IsEmpty(r: IntRange): bool

{

r.0 > r.1

}

A *predicate* is one other identify for a technique that returns `bool`

. A *ghost* technique (or predicate) is one that may solely be used for validation, not for operating the ultimate code.

At a excessive degree, the `ValidSeq`

predicate takes as enter a sequence of non-empty integer ranges. It then exams that the beginning values are sorted and that the ranges don’t contact. Particularly,

- An
`IntRange`

is a tuple of two`int`

values. - An
`IntRange`

`IsEmpty`

precisely when its begin is larger than its finish. (This follows Rust’s conference.) - A
`NeIntRange`

(non-empty integer vary) is an`IntRange`

that’s not empty, for instance,`(0,0)`

. [All our ranges are end inclusive.] - This expression exams that the beginning values are sorted:

`forall i:nat, j:nat | i < j < |sequence| :: sequence[i].0 < sequence[j].0`

It may be learn as “for all pure numbers *i* and *j* — such that *i* is lower than *j *and *j* is lower than the size of the sequence — take a look at that the beginning worth at index *i* is lower than the beginning worth as index *j*”.

Apart: Observe {that a} Rust

`BTreeMap`

doesn’t assist (random-access) indexing however right here we’re utilizing such indexing. That is OK as a result of`is a ghost predicate and so will solely be used for validation.`

ValidSeq

- This expression exams that the ranges are disjoint:

`forall i:nat, j:nat | i < j < |sequence| :: !Contact(sequence[i], sequence[j])`

It may be learn as “for all pure numbers *i* and *j* — such that *i* is lower than *j *and *j* is lower than the size of the sequence — take a look at that the vary at index *i* doesn’t contact the vary at index *j*. However what’s `Contact`

?

We’ll outline `Contact`

on two-levels. On a mathematical degree, a variety *i* is alleged to the touch a variety *j* if there exists an integer *i0* in vary *i* and an integer *j0* in vary *j* such that *i0* and *j0* are inside a distance of one in every of one another. On an environment friendly programming degree, we wish to keep away from definitions relying on “there exists”. Here’s a Dafny predicate that’s each mathematical and environment friendly:

`predicate Contact(i: NeIntRange, j: NeIntRange)`

ensures Contact(i, j) == exists i0, j0 ::

Accommodates(i, i0) && Accommodates(j, j0) && -1 <= i0 - j0 <= 1

{

assert Accommodates(i, i.0) && Accommodates(i, i.1) && Accommodates(j, j.0) && Accommodates(j, j.1);

if i.1 < j.0 then

assert (-1 <= i.1 - j.0 <= 1) == (i.1+1 == j.0);

i.1+1 == j.0

else if j.1 < i.0 then

assert (-1 <= j.1 - i.0 <= 1) == (j.1+1 == i.0);

j.1+1 == i.0

else

var k0 := Max(i.0, j.0);

assert Accommodates(i, k0) && Accommodates(j, k0);

true

}perform Accommodates(r: IntRange, i: int): bool

{

r.0 <= i && i <= r.1

}

perform Max(a: int, b: int): int

{

if a < b then b else a

}

Some factors of curiosity:

`Contact`

will not be a ghost. In different phrases, we will use it in each common code and validation code.- The
`assert`

statements assist Dafny show that the common code meets the mathematical`ensures`

assertion. - For effectivity, the Dafny prover validates the within of a
`technique`

individually from its outdoors. Solely the`ensures`

(and the yet-to-be-seen,`requires`

) statements cross this border. In distinction to a`technique`

, a Dafny`perform`

is clear to the validator. (I consider it as inlining code with respect to validation.)

With ideas resembling `ValidSeq`

and `Contact`

outlined, we subsequent transfer onto specifying what our algorithm is meant to do.

In the end, I wish to show that my particular Rust algorithm for inserting a brand new vary right into a `RangeSetBlaze`

is right. Earlier than we do this, nonetheless, let’s outline what “right” vary insertion is.

`technique InternalAdd(xs: seq<NeIntRange>, a: IntRange) returns (rs: seq<NeIntRange>)`

requires ValidSeq(xs)

ensures ValidSeq(rs)

ensures SeqToSet(rs) == SeqToSet(xs) + RangeToSet(a)

{

if IsEmpty(a)

{

rs := xs;

}

else

{

assume false; // cheat for now

}

}

This says that `InternalAdd`

is a technique that takes `xs`

, a sequence of non-empty integer ranges, and `a`

, an integer vary (that might be empty). The tactic outputs `rs`

, a brand new sequence of non-empty integer ranges.

We have to say that `xs`

and `rs`

have to be sorted and disjoint. That’s simply completed with the `ValidSeq`

’s within the `requires`

and first `ensures`

.

We additionally have to say that `rs`

comprises the appropriate stuff. Is this difficult? It’s not. We simply say that the set of integers in `rs`

should equal the set of integers in `xs`

unioned with the integers in `a`

.

Apart: In Dafny, “+” when utilized to units is “union”.

The set of integers in a variety is:

`ghost perform RangeToSet(pair: IntRange): set<int>`

{

set i {:autotriggers false} | pair.0 <= i <= pair.1 :: i

}

And the set of integers in a sequence of non-empty ranges may be outline inductively (that’s, recursively):

`ghost perform SeqToSet(sequence: seq<NeIntRange>): set<int>`

decreases |sequence|

requires ValidSeq(sequence)

{

if |sequence| == 0 then {}

else if |sequence| == 1 then RangeToSet(sequence[0])

else RangeToSet(sequence[0]) + SeqToSet(sequence[1..])

}

Some factors of curiosity:

- The road:
`assume false; // cheat for now`

makes validation work even when it actually shouldn’t. We use it as a short lived placeholder. - We make
`RangeToSet`

and`SeqToSet`

*ghosts*to cease us from utilizing them in common code. We make them*capabilities*(as a substitute of*strategies*) - As a result of Dafny is aware of lots about creating and manipulating units and sequences, we regularly revenue by utilizing units and sequences in our specification.
- Even when our common code makes use of loops as a substitute of recursion, our validation code will usually use recursive-like induction.
- The
`{:autotriggers false}`

pertains to avoiding a warning message. For extra info see this Stack Overflow reply by Prof. James Wilcox.

We now have a proper specification of `InternalAdd`

. I discover this specification quick and intuitive. However what if you happen to need assistance determining a specification or different Dafny code?

The principle discussion board for Dafny questions is Stack Overflow. To my shock, I truly obtained a lot helpful assist there.

I like to recommend beginning your query’s title with “Dafny:”. Additionally, remember to tag your query with `dafny`

and, maybe, `formal-verification`

.

Apart: On the location, you may see my 11 questions and Divyanshu Ranjan’s 48 Dafny-related solutions.

As an open-source challenge on GitHub, Dafny additionally hosts GitHub Discussions and Points.

The Dafny neighborhood is small however appears keen about serving to customers and enhancing the challenge.

With assist at hand, we should subsequent discover an algorithm that meets the specification.

As a novice to formal verification, I made a decision to postpone work on the actual `internal_add`

utilized in my Rust code. As a substitute, I began work on an `InternalAdd`

algorithm that I hoped could be simpler to validate. I ended up with this:

`technique InternalAdd(xs: seq<NeIntRange>, a: IntRange) returns (rs: seq<NeIntRange>)`

requires ValidSeq(xs)

ensures ValidSeq(rs)

ensures SeqToSet(rs) == SeqToSet(xs) + RangeToSet(a)

{

if IsEmpty(a)

{

rs := xs;

}

else

{

var notTouching, merged := PartitionAndMerge(xs, a);

var indexAfter := NoTouchIndexAfter(notTouching, merged);

rs := InsertAt(notTouching, [merged], indexAfter);

}

}

The concept is that if vary `a`

is empty, we return the enter sequence unchanged. In any other case, we divide the work into three steps, which we will validate independently. Step one, `PartitionAndMerge,`

returns:

`notTouching`

, a sequence of ranges that don’t contact vary`a`

, and`merged`

, a single vary created from`a`

and every little thing it touches.

Right here is an instance enter and output:

`InternalAdd`

subsequent finds the place to insert `merged`

and, lastly, inserts it.

Right here is the code for `PartitionAndMerge:`

`technique PartitionAndMerge(xs: seq<NeIntRange>, a: NeIntRange) returns (notTouching: seq<NeIntRange>, merged: NeIntRange)`

requires ValidSeq(xs)ensures ValidSeq(notTouching)

ensures RangeToSet(merged) >= RangeToSet(a)

ensures forall vary | vary in notTouching :: !Contact(vary, merged)

ensures SeqToSet(xs) + RangeToSet(a) == SeqToSet(notTouching) + RangeToSet(merged)

{

// Break up into touching and never touching seqs

var touching: seq<NeIntRange>;

touching, notTouching := Partition(a, xs);

// Merge the touching seq into one vary with our unique vary

merged := UnionSeq(a, touching);

}

This says that `PartitionAndMerge`

`requires`

that `xs`

be a sound sequence of non-empty integer ranges and that `a`

be a non-empty integer vary. It ensures that `nonTouching`

is one other legitimate sequence of non-empty integer ranges. It ensures that the integers in vary `merged`

are a superset of these in vary `a`

. It ensures that no vary in `notTouching`

touches vary `merged`

. And eventually, it ensures that the integers in `xs`

and `a`

are precisely the identical because the integers in `notTouching`

and `merged`

.

`PartitionAndMerge`

additionally divides the work, this time into two steps (`Partition `

and `UnionSeq`

) that may be validated independently. These steps proceed to subdivide their work. The place does it finish? Let’s take a look at one instance.

The tactic `UnionSeq`

calls `UnionRange`

which merges two ranges:

`perform UnionRange(x: IntRange, y: IntRange): IntRange`

requires IsEmpty(x) || IsEmpty(y) || Contact(x, y)

ensures RangeToSet(x) + RangeToSet(y) == RangeToSet(UnionRange(x,y))

{

if IsEmpty(x) then y

else if IsEmpty(y) then x

else (Min(x.0, y.0), Max(x.1, y.1))

}

The `UnionRange`

code handles the empty circumstances after which returns the minimal bounding vary. (The minimal bounding vary is the vary from the smaller of the 2 begins to the bigger of the 2 ends.) However how can this be right? Typically, a minimal bounding vary of two ranges may embody further integers. We’d get one thing larger than the union of the inputs, like so:

The code is right as a result of it `requires`

that the 2 enter ranges contact or are empty. This `ensures`

that the union of the integers in vary `x`

with the integers in vary `y`

are precisely the integers within the output vary.

At compile time, Dafny proves this perform right. Past that, it proves that every little thing that calls this perform gives inputs which are empty or touching.

I consider this as a generalization of Rust’s borrow checker. At compile-time Rust checks that we’re protected from many reminiscence errors. At compile time, verification techniques, resembling Dafny, can show virtually arbitrary properties. In fact, as we’re seeing, this capability comes at the price of complexity.

The total code for this verified algorithm is about 200 traces, organized into a couple of dozen strategies and capabilities.

This rule exhibits that we will confirm *an* algorithm for `InternalAdd`

, however it isn’t the algorithm I utilized in Rust. We are going to flip to that subsequent.