Isabelle (proof assistant)

Template:Short description {{#invoke:Infobox|infobox}}Template:Template other{{#invoke:Check for unknown parameters | check | showblankpositional=1 | unknown = Template:Main other | preview = Page using Template:Infobox software with unknown parameter "_VALUE_"|ignoreblank=y | AsOf | author | background | bodystyle | caption | collapsetext | collapsible | developer | discontinued | engine | engines | genre | included with | language | language count | language footnote | latest preview date | latest preview version | latest release date | latest release version | latest_preview_date | latest_preview_version | latest_release_date | latest_release_version | licence | license | logo | logo alt | logo caption | logo upright | logo size | logo title | logo_alt | logo_caption | logo_upright | logo_size | logo_title | middleware | module | name | operating system | operating_system | other_names | platform | programming language | programming_language | released | replaced_by | replaces | repo | screenshot | screenshot alt | screenshot upright | screenshot size | screenshot title | screenshot_alt | screenshot_upright | screenshot_size | screenshot_title | service_name | size | standard | title | ver layout | website | qid }}Template:Main other

The IsabelleTemplate:Efn automated theorem prover is a higher-order logic (HOL) theorem prover, written in Standard ML and Scala. As a Logic for Computable Functions (LCF) style theorem prover, it is based on a small logical core (kernel) to increase the trustworthiness of proofs without requiring, yet supporting, explicit proof objects.

Isabelle is available inside a flexible system framework allowing for logically safe extensions, which comprise both theories and implementations for code-generating, documenting, and specific support for a variety of formal methods. It can be seen as an integrated development environment (IDE) for formal methods. In recent years, a substantial number of theories and system extensions have been collected in the Isabelle Archive of Formal Proofs (Isabelle AFP).<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Isabelle was named by Lawrence Paulson after Gérard Huet's daughter.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

The Isabelle theorem prover is free software, released under the revised BSD license.

FeaturesEdit

Isabelle is generic: it provides a meta-logic (a weak type theory), which is used to encode object logics like first-order logic (FOL), higher-order logic (HOL) or Zermelo–Fraenkel set theory (ZFC). The most widely used object logic is Isabelle/HOL, although significant set theory developments were completed in Isabelle/ZF. Isabelle's main proof method is a higher-order version of resolution, based on higher-order unification.

Though interactive, Isabelle features efficient automatic reasoning tools, such as a term rewriting engine and a tableaux prover, various decision procedures, and, through the Sledgehammer proof-automation interface, external satisfiability modulo theories (SMT) solvers (including CVC4) and resolution-based automated theorem provers (ATPs), including E, SPASS, and Vampire (the MetisTemplate:Efn proof method reconstructs resolution proofs generated by these ATPs).<ref>Jasmin Christian Blanchette, Lukas Bulwahn, Tobias Nipkow, "Automatic Proof and Disproof in Isabelle/HOL", in: Cesare Tinelli, Viorica Sofronie-Stokkermans (eds.), International Symposium on Frontiers of Combining Systems – FroCoS 2011, Springer, 2011.</ref> It also features two model finders (counterexample generators): Nitpick<ref name=:0>Jasmin Christian Blanchette, Mathias Fleury, Peter Lammich & Christoph Weidenbach, "A Verified SAT Solver Framework with Learn, Forget, Restart, and Incrementality", Journal of Automated Reasoning 61:333–365 (2018).</ref> and Nunchaku.<ref>Andrew Reynolds, Jasmin Christian Blanchette, Simon Cruanes, Cesare Tinelli, "Model Finding for Recursive Functions in SMT", in: Nicola Olivetti, Ashish Tiwari (eds.), 8th International Joint Conference on Automated Reasoning, Springer, 2016.</ref>

Isabelle features locales which are modules that structure large proofs. A locale fixes types, constants, and assumptions within a specified scope<ref name=:0/> so that they do not have to be repeated for every lemma.

Isar ("intelligible semi-automated reasoning") is Isabelle's formal proof language. It is inspired by the Mizar system.<ref name=:0/>

Example proofEdit

Isabelle allows proofs to be written in two different styles, the procedural and the declarative. Procedural proofs specify a series of tactics (theorem proving functions/procedures) to apply. While reflecting the procedure that a human mathematician might apply to proving a result, they are typically hard to read as they do not describe the outcome of these steps. Declarative proofs (supported by Isabelle's proof language, Isar), on the other hand, specify the actual mathematical operations to be performed, and are therefore more easily read and checked by humans.

The procedural style has been deprecated in recent versions of Isabelle.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }} Page 148: "Arbitrary goal refinement via tactics is considered harmful". See also section 7.3, "Tactics: improper proof methods", pp. 172–175.</ref>

For example, a declarative proof by contradiction in Isar that the square root of two is not rational can be written as follows.

Template:Ifsubst style="color:darkblue">theorem sqrt2_not_rational:
  Template:Olive
Template:Ifsubst style="color:darkblue">proof
  Template:Ifsubst style="color:darkblue">let ?x = Template:Olive
  assume Template:Olive
  Template:Ifsubst style="color:darkblue">then obtain m n :: nat where
    sqrt_rat: Template:Olive and lowest_terms: Template:Olive
    Template:Ifsubst style="color:darkblue">by (rule Rats_abs_nat_div_natE)
  Template:Ifsubst style="color:darkblue">hence Template:Olive Template:Ifsubst style="color:darkblue">by (auto simp add: power2_eq_square)
  Template:Ifsubst style="color:darkblue">hence eq: Template:Olive Template:Ifsubst style="color:darkblue">using of_nat_eq_iff power2_eq_square Template:Ifsubst style="color:darkblue">by fastforce
  Template:Ifsubst style="color:darkblue">hence Template:Olive Template:Ifsubst style="color:darkblue">by simp
  Template:Ifsubst style="color:darkblue">hence Template:Olive Template:Ifsubst style="color:darkblue">by simp
  Template:Ifsubst style="color:darkblue">have Template:Olive Template:Ifsubst style="color:darkblue">proof -
    Template:Ifsubst style="color:darkblue">from Template:Olive obtain k where Template:Ifsubst style="color:olive">"m = 2 * k" ..
    Template:Ifsubst style="color:darkblue">with eq Template:Ifsubst style="color:darkblue">have Template:Olive Template:Ifsubst style="color:darkblue">by simp
    Template:Ifsubst style="color:darkblue">hence Template:Olive Template:Ifsubst style="color:darkblue">by simp
    thus Template:Olive Template:Ifsubst style="color:darkblue">by simp
  Template:Ifsubst style="color:darkblue">qed
  Template:Ifsubst style="color:darkblue">with Template:Olive Template:Ifsubst style="color:darkblue">have Template:Olive Template:Ifsubst style="color:darkblue">by (rule gcd_greatest)
  Template:Ifsubst style="color:darkblue">with lowest_terms Template:Ifsubst style="color:darkblue">have Template:Olive Template:Ifsubst style="color:darkblue">by simp
  thus False Template:Ifsubst style="color:darkblue">using odd_one Template:Ifsubst style="color:darkblue">by blast
Template:Ifsubst style="color:darkblue">qed

ApplicationsEdit

Isabelle has been used to aid formal methods for the specification, development and verification of software and hardware systems.

Isabelle has been used to formalize numerous theorems from mathematics and computer science, like Gödel's completeness theorem, Gödel's theorem about the consistency of the axiom of choice, the prime number theorem, correctness of security protocols, and properties of programming language semantics. Many of the formal proofs are, as mentioned, maintained in the Archive of Formal Proofs, which contains (as of 2019) at least 500 articles with over 2 million lines of proof in total.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

In 2009, the L4.verified project at NICTA produced the first formal proof of functional correctness of a general-purpose operating system kernel:<ref Name="Klein_EHACDEEKNSTW_09">

Template:Cite conference</ref> the seL4 (secure embedded L4) microkernel. The proof is constructed and checked in Isabelle/HOL and comprises over 200,000 lines of proof script to verify 7,500 lines of C. The verification covers code, design, and implementation, and the main theorem states that the C code correctly implements the formal specification of the kernel. The proof uncovered 144 bugs in an early version of the C code of the seL4 kernel, and about 150 issues in each of design and specification.

The definition of the programming language Lightweight Java was proven type-sound in Isabelle.<ref>Template:Cite journal</ref>

AlternativesEdit

Template:Further Several languages and systems provide similar functions:

Agda, written in Haskell
Rocq (previously known as Coq), written in OCaml
Lean, written in Lean itself and C++
LEGO, written in Standard ML of New Jersey
Mizar system, written in Free Pascal
Metamath, written in ANSI C
Prover9, written in C, with a GUI written in Python
Twelf, written in Standard ML

NotesEdit

Template:Notelist

ReferencesEdit

Template:Reflist

External linksEdit

Template:Portal

Template:ML programming