Techniques for using decision procedures in Idris

This post is a literate Idris file, so first let’s get some bureaucracy out of the way:

When writing Idris code, we sometimes need a proof as an argument to a function. In many cases, these proofs can be constructed automatically by a decision procedure. Here, I’m using the term "decision procedure" for some property p to refer to a function that returns something in the type Dec p.

An instance of Dec p is either a proof of p or a proof that p is an absurdity. The datatype is defined as follows:

As an example, take the following type from the Idris library that represents a proof that one natural number is less than or equal to another:

The first constructor, lteZero, should be interpreted as an assertion that zero is less than or equal to any natural number. The second, lteSucc, is an assertion that if n≤m, then n+1 ≤ m+1. It happens to be the case that, for any two natural numbers, it is decidable whether the first is less than or equal to the second.

To prove this, we start with two simple lemmas. The first states that it is not the case that the successor of any number is less than or equal to zero:

Additionally, we show that, if k≰j, then k+1 ≰ j+1:

We are now in a position to write the decision procedure, by examining each case and using our lemmas to produce the appropriate contents for the No constructor. If the details don’t make sense, then please fire up Idris, replace some right-hand sides with metavariables, and examine the proof context.

Now that these details are out of the way, we can get to the main point of this blog post: demonstrating various techniques for getting Idris to fill out these proofs for us.

The most straightforward way is to use the interactive editing features to get Idris to construct the proof term directly. For example, if we want to show that 3 ≤ 5, then we need only create a definition with type 3 ‘LTE‘ 5:

We can then use C-c C-s in idris-mode to cause it to become

Using the proof search command C-c C-a on the metavariable gives us

and the decision procedure simply isn’t necessary. This approach can make our programs ugly, but it is straightforward and direct. We need not actually show the resulting term, however. In Idris, tactic scripts are allowed as the right-hand side of definitions. So we can simply invoke the search tactic explicitly, rather than using it through the compiler’s editor interface, and the resulting term does not need to occur in the source file. This can also be more robust in the face of changes to the definition of LTE. The tactic-based definition is:

Here, proof begins a tactic script, and search is the tactic to be invoked.

One non-solution is to have the right-hand side of the definition perform a case analysis on the result of a call to decLTE, and then return the contents of the Yes case. Because we know that three is, in fact, less than five, we will never need the No case:

Unfortunately, the Idris compiler needs to be convinced of the fact that No cannot occur. We do this by showing that the No case could cause the empty type to be inhabited, and then use FalseElim. Unfortunately, doing this requires actually proving the property again:

The next method is to cause the solver for implicit arguments to execute the decision procedure while filling out an implicit argument for the proof, and then return this implicit argument. The definition okImplicit demonstrates this technique:

All of the work happens in getProof, which is in a where block to keep the type signature of okImplicit clean. In the definition of getProof, the implicit argument prf is the one that will be filled out with the proof, and then returned. The argument yep is an implicit proof that the result of executing the decision procedure will be Yes prf – in other words, that it will succeed, and the thing it succeeds with will unify with prf. The auto keyword causes Idris to fill out the argument with refl, the constructor of proofs of equality.

While the okImplicit technique leads to noisy boilerplate in type signatures, it also tends to cause error messages that are easy to understand. I’ve had a lot of luck using it for embedded DSLs with some kind of side condition (like "these queries must have disjoint schemas").

The final technique that I’d like to demonstrate uses a dependently-typed extractor of proofs from Dec. The type of the function getYes does case-analysis on the result of a decision procedure. If the result was Yes, then getYes will return the contents – an instance of p. Otherwise, it returns unit, which contains no interesting information. Note that the result of the case expression is a type — either the type parameter to Dec or the unit type.

getYes : (res : Dec p) -> case res of { Yes _ => p ; No _ => () }

The body of getYes performs a case analysis on the result of the decision, either returning a proof or a trivial value, in accordance with the type. Note that Idris’s interactive editing features were able to write this code entirely – the only thing I needed to do was tell it to case split on the argument. Agda, which has more advanced interactive editing features, could probably write the entire body by passing Agsy the -c option, which enables case splitting.

Now, getYes can be used on the right-hand side of our definition to extract the proof:

While this approach is clean, the error messages can be somewhat unpleasant if Idris is asked to prove a falsehood. The following code:

results in this unification error:

whereas the error message from

was

You have now seen a few ways of getting Idris to find proofs. Hopefully, you’ve also gotten a bit more understanding of how Idris works while compiling your source file.

This post sprang out of a discussion on a Github issue with Nicola Botta. The discussion of error messages is improved as the result of a suggestion from Anthony Cowley. Thanks, Nicola and Anthony!