This repository contains the Haskell implementation of Detour: a small interactive proof assistant for first-order logic, together with a collection of example proofs. It is a research prototype built to explore an idea, not a general-purpose prover — see Research context below for what that idea is.
Detour is the research prototype behind the paper Don't Call Us, We'll Call You: Towards Mixed-Initiative Interactive Proof Assistants for Programming Language Theory (Jan Liam Verter and Tomas Petricek, HATRA at SPLASH 2024).
The point of the project is the interaction model, not prover strength. The usual way of working with a proof assistant is that the human builds the proof and calls automation to discharge the remaining goals. Detour inverts this: the tool opens with an automatic proof search based on a deliberately simple, hardcoded strategy, and pauses to ask the user for guidance wherever the search gets stuck — a setup known as mixed-initiative interaction. The assistant takes care of routine structure (induction over user-declared syntax, case splits, applying rules, lemmas, and local facts) while the human contributes insight at exactly the points that need it. The paper walks through this style of working using a proof of commutativity of addition on Peano naturals.
The vehicle for the experiment is a toy proof-checker for first-order predicate logic natural deduction with Fitch-style notation.
It supports a subset of first-order predicate logic and second-order propositional logic with custom definitions for terms and propositions.
You need GHC (9.8–9.12) and Cabal; the alex and happy build tools are fetched automatically.
cabal build all
cabal test
cabal run detour -- [flags] <file.dt>...
The checker reads a .dt module, then reports each theorem as checked (✅) or failed (❌).
The only flag is --lem / --no-lem (default --no-lem): it allows or disallows
the classical proof-by-contradiction rule. See examples/ and exs/
for sample inputs — e.g. cabal run detour -- examples/impl.dt.
The interaction is easier shown than described. Given a tiny theory of addition:
module demo
syntax N = Zero
| Suc(N)
judgment sum = Sum(N, N, N)
rule schema sum-zero for all objects (n : N) :
|
|-------------------------------------- sum-zero
| Sum(Zero, n, n)
rule schema sum-suc for all objects (m : N), (n : N), (o : N) :
| Sum(m, n, o)
|-------------------------------------- sum-suc
| Sum(Suc(m), n, Suc(o))
theorem zero-plus-one : Sum(Suc(Zero), Zero, Suc(Zero))
prove Sum(Suc(Zero), Zero, Suc(Zero))
asking for a proof starts a search that narrates itself — here it needs no help, so pressing Enter at each prompt (meaning "I don't know, carry on") is enough:
$ cabal run detour -- demo.dt
Checking module `demo'
I am solving a theorem `zero-plus-one'
| searching for a proof of `Sum(Suc(Zeroᶜ), Zeroᶜ, Suc(Zeroᶜ))'
[...]
I am solving a theorem `zero-plus-one'
using the rule sum-suc the matched goal = Sum(Suc(_1·?), _2·?, Suc(_3·?))
the new goals = Sum(Zeroᶜ, Zeroᶜ, Zeroᶜ)
[...]
I am solving a theorem `zero-plus-one'
I had a goal = Sum(Zeroᶜ, Zeroᶜ, Zeroᶜ) and I solved it using a rule sum-zero
and got to solve some sub-goals ([]) and those are done.
[...]
✅ theorem `zero-plus-one' checked successfully
On harder goals the search gets stuck and waits instead of guessing.
Running cabal run detour -- examples/sum-auto.dt in a terminal ends up here:
|| my goal `∃ (O : ℕᶜ) : Sum(Zeroᶜ, Suc(_3®), Oᵇ)' wasn't proved by any
local assert, I am going to try theorems
[...]
My current goal is: `Sum(Suc(_1®), Zeroᶜ, _28·?)'
At that prompt you can press Enter to let it continue on its own, type
list theorems or list locals to inspect what it has to work with, or paste
the missing proof steps (a blank line submits them) — and the search carries on
from there. That handoff, in either direction, is the whole idea.
(Transcripts trimmed; the prototype is chatty and also prints unification traces.)
You define axioms like so:
axiom nat-zero : ℕ(Zero)
axiom nat-suc : ∀ n : ℕ(n) ==> ℕ(Suc(n))
axiom sum-zero : ∀ n : ℕ(n) ==> Sum(Zero , n , n)
axiom sum-suc : ∀ n₁ n₂ n₃ : ℕ(n₁) ==>
ℕ(n₂) ==>
ℕ(n₃) ==>
Sum( n₁ , n₂ , n₃ ) ==> Sum( Suc(n₁) , n₂ , Suc(n₃) )
You can also define your relations more concisely using the syntax and judgment declarations.
Here's an example of the above in the new syntax:
syntax ℕ = Zero
| Suc(ℕ)
judgment sum = Sum(ℕ, ℕ, ℕ)
rule schema sum-zero for all objects (n : ℕ) :
|
|-------------------------------------- sum-zero
| Sum(Zero, n, n)
rule schema sum-suc for all objects (m : ℕ), (n : ℕ), (o : ℕ) :
| Sum(m, n, o)
|-------------------------------------- sum-suc
| Sum(Suc(m), n, Suc(o))
If you declare your relations (using syntax and judgment) as shown above, the tool supports proofs by induction and case analysis.
Here's an example of a theorem total for addition:
theorem total : ∀ (n₁ : ℕ) (n₂ : ℕ) : ∃ (n₃ : ℕ) : Sum( n₁ , n₂ , n₃ )
∀ (n₁ : ℕ) (n₂ : ℕ) : ∃ (n₃ : ℕ) : Sum( n₁ , n₂ , n₃ ) by induction :
case Zero ->
|
|--------------------------------------------------------------------------------------------
| uni-n2 : | for all (n2 : ℕ)
| |--------------------------------------------------------------------------------
| | sz : Sum( Zero , n2 , n3 ) by rule sum-zero
| | ∃ (n₃ : ℕ) : Sum( Zero , n2 , n₃ ) by rule ∃-intro on sz
|
| ∀ (n₂ : ℕ) : ∃ (n₃ : ℕ) : Sum( Zero , n₂ , n₃ ) by rule ∀-intro on uni-n2
case Suc(m) ->
| induction-hypothesis : ∀ (n₂ : ℕ) : ∃ (n₃ : ℕ) : Sum( m , n₂ , n₃ )
|--------------------------------------------------------------------------------------------
| uni-n2b : | for all (N2 : ℕ)
| |--------------------------------------------------------------------------------
| | d1 : ∃ (n₃ : ℕ) : Sum( m , N2 , n₃ ) by rule ∀-elim on induction-hypothesis
| | exn3 : | p5 : Sum( m , N2 , n3 ) for some (n3 : ℕ)
| | |----------------------------------------------------------------------
| | | sum-m+1 : Sum( Suc(m) , N2 , Suc(n3) ) by rule sum-suc on p5
| | | ∃ (n₃ : ℕ) : Sum( Suc(m) , N2 , n₃ ) by rule ∃-intro on sum-m+1
| |
| | ∃ (n₃ : ℕ) : Sum( Suc(m) , N2 , n₃ ) by rule ∃-elim on d1, exn3
|
| ∀ (n₂ : ℕ) : ∃ (n₃ : ℕ) : Sum( Suc(m) , n₂ , n₃ ) by rule ∀-intro on uni-n2b
A theorem is a statement followed by its proof.
theorem total : ∀ (n₁ : ℕ) (n₂ : ℕ) : ∃ (n₃ : ℕ) : Sum( n₁ , n₂ , n₃ )
We can have theorems parametrized by propositions. Here is an example:
theorem schema modus-ponens for all propositions P, K : P ==> K
, P
⊢ K
| p->k : P ==> K
| p : P
|--------------------
|
| K by rule ==>-elim on p->k, p
We can then use this theorem as normal.
theorem use-modus-ponens : A ==> B , A ⊢ B
| a->b : A ==> B
| a : A
|-------------------
|
| B by theorem modus-ponens on a->b, a
Note the difference!
PandKare parameters so they are not actual propositional constants whereasAandBare understood as specific propositions.
Proofs are the most visually involved part. You start by writing the vertical and horizontal lines:
|
|---------------------------
|
|
|
|
The lines above the long horizontal line are for premises while the space below the horizontal line is for deriving new information.
Here is a simple theorem in propositional logic:
theorem foo : A ==> B ==> C ⊢ B ==> A ==> C
| p : A ==> B ==> C
|----------------------------------------------------------
|
| 0 : | p0 : B
| |----------------------------------------------------
| |
| | 1 : | p1 : A
| | |----------------------------------------------
| | |
| | | b=>c : B ==> C by rule ==>-elim on p, p1
| | |
| | | C by rule ==>-elim on b=>c, p0
| |
| | A ==> C by rule ==>-intro on 1
|
| B ==> A ==> C by rule ==>-intro on 0
You have to name all your premises. You don't have to name all the asserted statements below the line. Only those you intend to refer to. The last one in a (sub-)proof is supposed to be proving the goal.
You can use whatever names you want. Almost all characters are allowed except some special symbols that have concrete meanings in detour.
See the ./examples directory for a few examples.
The tool now supports a somewhat automated proof search. The goal is to focus on very interactive proving. It is not a goal to build a powerful automated theorem prover. However, with the correct use of tactics (in the future) it maybe could be.
The theorem total from above now can be proved trivially:
theorem total : ∀ (N : ℕ) (M : ℕ) : ∃ (O : ℕ) : Sum(N, M, O)
prove ∀ (N : ℕ) (M : ℕ) : ∃ (O : ℕ) : Sum(N, M, O)