# Applications and libraries/Theorem provers

### From HaskellWiki

< Applications and libraries(Difference between revisions)

DonStewart (Talk | contribs) (A couple more theorem provers written in Haskell) |
(→Applications: Cayenne reappeared on the web => link updated) |
||

(20 intermediate revisions by 11 users not shown) | |||

Line 1: | Line 1: | ||

− | |||

− | |||

Tools for formal reasoning, written in Haskell. | Tools for formal reasoning, written in Haskell. | ||

− | ;[http:// | + | == Applications == |

+ | |||

+ | ;[http://wiki.portal.chalmers.se/agda/agda.php Agda] | ||

:Agda is a system for incrementally developing proofs and programs. Agda is also a functional language with [[Dependent type]]s. This language is very similar to cayenne and agda is intended to be a (almost) full implementation of it in the future. | :Agda is a system for incrementally developing proofs and programs. Agda is also a functional language with [[Dependent type]]s. This language is very similar to cayenne and agda is intended to be a (almost) full implementation of it in the future. | ||

+ | ;[http://citeseer.ist.psu.edu/29367.html A resolution-based theorem prover for FOL] | ||

+ | :Haskell implementation of a resolution based theorem prover for first order logic. | ||

+ | |||

+ | ;[http://www-ps.iai.uni-bonn.de/cgi-bin/free-theorems-webui.cgi Automatic generation of free theorems] | ||

+ | :Web interface for generating theorems from Haskell types. | ||

+ | |||

+ | ;[http://wiki.di.uminho.pt/wiki/bin/view/PURe/Camila Camila] | ||

+ | :Camila is a system for software development using formal methods. Other materials on formal methods can be found also on the [[Analysis and design|analysis and design]] page. | ||

+ | |||

+ | ;[http://www.augustsson.net/Darcs/Cayenne/html/ Cayenne] | ||

+ | :Cayenne is a functional language with a powerful [[Dependent type|dependent type system]]. The basic types are functions, products, and sums. Functions and products use dependent types to gain additional power. As with Epigram, a dependently typed language may be used to encode strong proofs in the type system. The language is no longer supportd; the link points to a page stored in the Web Archive. | ||

+ | |||

+ | ;[http://www.lix.polytechnique.fr/dedukti Dedukti] | ||

+ | :Dedukti is a proof checker for the λΠ-modulo calculus, a dependently typed λ-calculus with the addition of typed rewrite rules, capable of expressing proofs in Deduction Modulo. | ||

+ | |||

+ | ;[http://www.cwi.nl/~jve/demo/ DEMO] | ||

+ | :Model checking for dynamic epistemic logic. DEMO is a tool for modelling change in epistemic logic (the logic of knowledge). Among other things, DEMO allows modeling epistemic updates, graphical display of update results, graphical display of action models, formula evaluation in epistemic models, translation of dynamic epistemic formulas to PDL (propositional dynamic logic) formulas. More materials and other Haskell resources on dynamic epistemic modelling (and more generally on logic and [[linguistics]]) can be found on [http://homepages.cwi.nl/~jve/index.html Jan van Eijck's page]. | ||

;[http://darcs.augustsson.net/Darcs/Djinn Djinn] | ;[http://darcs.augustsson.net/Darcs/Djinn Djinn] | ||

:Djinn generates Haskell code from a type declaration, using a decision procedure from intuitionistic propositional calculus. | :Djinn generates Haskell code from a type declaration, using a decision procedure from intuitionistic propositional calculus. | ||

− | |||

− | |||

− | |||

;[http://www.haskell.org/dumatel/ Dumatel] | ;[http://www.haskell.org/dumatel/ Dumatel] | ||

: Dumatel is a prover based on many-sorted term rewriting (TRW) and equational reasoning | : Dumatel is a prover based on many-sorted term rewriting (TRW) and equational reasoning | ||

− | |||

− | |||

− | |||

;[http://www.e-pig.org/ Epigram] | ;[http://www.e-pig.org/ Epigram] | ||

:Epigram is a prototype [[Dependent type|dependently typed]] functional programming language, equipped with an interactive editing and typechecking environment. High-level Epigram source code elaborates into a dependent type theory based on Zhaohui Luo's UTT. Programming with evidence lies at the heart of Epigram's design. | :Epigram is a prototype [[Dependent type|dependently typed]] functional programming language, equipped with an interactive editing and typechecking environment. High-level Epigram source code elaborates into a dependent type theory based on Zhaohui Luo's UTT. Programming with evidence lies at the heart of Epigram's design. | ||

− | ;[http://www.cs.chalmers.se/~ | + | ;[http://www.cs.chalmers.se/~koen/folkung/ Equinox] |

− | : | + | :Equinox is a new theorem prover for pure first-order logic with equality. It finds ground proofs of the input theory, by solving successive ground instantiations of the theory using an incremental SAT-solver. Equality is dealt with using a Nelson-Oppen framework. |

− | ;[http://www. | + | ;[http://fldit-www.cs.uni-dortmund.de/~peter/ExpNeu/Welcome.html Expander2] |

− | : | + | :Expander2 is a flexible multi-purpose workbench for rewriting, verification, constraint solving, flow graph analysis and related procedures that build up proofs or computation sequences. Moreover, tailor-made interpreters display terms as 2D structures ranging from trees and rooted graphs to tables, fractals and other turtle-system-generated pictures. |

+ | |||

+ | ;[http://www.cs.yale.edu/homes/cc392/report.html FOL Resolution Theorem Prover] | ||

+ | :An implementation of a simple theorem prover in first-order logic using Haskell. | ||

+ | |||

+ | ;[http://taz.cs.wcupa.edu/~dmead/code/prover/ Halp] | ||

+ | :Haskell Logic Prover is written in Haskell supports first order logic with plans to add predicates. Also included is a simple frontend written with gtk2hs | ||

+ | |||

+ | ;[http://isabelle.in.tum.de/haskabelle.html Haskabelle] | ||

+ | :Haskabelle is a converter from Haskell source files to Isabelle/HOL theories implemented in Haskell itself | ||

+ | |||

+ | ;[http://www.informatik.uni-bremen.de/agbkb/forschung/formal_methods/CoFI/hets/ Hets] | ||

+ | :The Heterogeneous Tool Set (Hets) is a parsing, static analysis and proof management tool combining various tools for different specification languages, thus providing a tool for heterogeneous specifications. It supports HasCASL for specification of Haskell programs, and uses Isabelle for proving | ||

+ | |||

+ | ;[http://www.math.chalmers.se/~koen/paradox/ Paradox] | ||

+ | :Paradox processes first-order logic problems and tries to find finite-domain models for them. | ||

;[http://proofgeneral.inf.ed.ac.uk/Kit Proof General Kit] | ;[http://proofgeneral.inf.ed.ac.uk/Kit Proof General Kit] | ||

:The Proof General Kit designs and implements a component-based framework for interactive theorem proving. The central middleware of the toolkit is implemented in Haskell. The project is the sucessor of the highly successful Emacs-based Proof General interface. | :The Proof General Kit designs and implements a component-based framework for interactive theorem proving. The central middleware of the toolkit is implemented in Haskell. The project is the sucessor of the highly successful Emacs-based Proof General interface. | ||

− | ;[http:// | + | ;[http://www.haskell.org/yarrow/ Yarrow] |

− | : | + | :Yarrow is a proof-assistant for Pure Type Systems (PTSs) with several extensions. In Yarrow you can experiment with various pure type systems, representing different logics and programming languages. |

− | ;[ | + | ;[[Zeno]] |

− | : | + | :Zeno is an automated proof system for Haskell program properties; developed at Imperial College London by William Sonnex, Sophia Drossopoulou and Susan Eisenbach. It aims to solve the general problem of equality between two Haskell terms, for any input value. Proofs and programs are output as [http://www.cl.cam.ac.uk/research/hvg/Isabelle/ Isabelle/HOL] theories which are then automatically verified by said tool. |

− | + | == Libraries == | |

− | + | ||

− | ;[http://www. | + | ;[http://www.dcs.st-and.ac.uk/~eb/ivor.php Ivor] |

− | : | + | :is type theory based theorem proving library -- written by [http://www.dcs.st-and.ac.uk/~eb/index.php Edwin Brady] (see also the author's homepage, there are a lot of materials concerning [[dependent type]] theory there). |

− | + | {{LibrariesPage}} | |

− | + |

## Revision as of 20:22, 8 August 2012

Tools for formal reasoning, written in Haskell.

## 1 Applications

- Agda
- Agda is a system for incrementally developing proofs and programs. Agda is also a functional language with Dependent types. This language is very similar to cayenne and agda is intended to be a (almost) full implementation of it in the future.

- A resolution-based theorem prover for FOL
- Haskell implementation of a resolution based theorem prover for first order logic.

- Automatic generation of free theorems
- Web interface for generating theorems from Haskell types.

- Camila
- Camila is a system for software development using formal methods. Other materials on formal methods can be found also on the analysis and design page.

- Cayenne
- Cayenne is a functional language with a powerful dependent type system. The basic types are functions, products, and sums. Functions and products use dependent types to gain additional power. As with Epigram, a dependently typed language may be used to encode strong proofs in the type system. The language is no longer supportd; the link points to a page stored in the Web Archive.

- Dedukti
- Dedukti is a proof checker for the λΠ-modulo calculus, a dependently typed λ-calculus with the addition of typed rewrite rules, capable of expressing proofs in Deduction Modulo.

- DEMO
- Model checking for dynamic epistemic logic. DEMO is a tool for modelling change in epistemic logic (the logic of knowledge). Among other things, DEMO allows modeling epistemic updates, graphical display of update results, graphical display of action models, formula evaluation in epistemic models, translation of dynamic epistemic formulas to PDL (propositional dynamic logic) formulas. More materials and other Haskell resources on dynamic epistemic modelling (and more generally on logic and linguistics) can be found on Jan van Eijck's page.
- Djinn
- Djinn generates Haskell code from a type declaration, using a decision procedure from intuitionistic propositional calculus.

- Dumatel
- Dumatel is a prover based on many-sorted term rewriting (TRW) and equational reasoning

- Epigram
- Epigram is a prototype dependently typed functional programming language, equipped with an interactive editing and typechecking environment. High-level Epigram source code elaborates into a dependent type theory based on Zhaohui Luo's UTT. Programming with evidence lies at the heart of Epigram's design.

- Equinox
- Equinox is a new theorem prover for pure first-order logic with equality. It finds ground proofs of the input theory, by solving successive ground instantiations of the theory using an incremental SAT-solver. Equality is dealt with using a Nelson-Oppen framework.

- Expander2
- Expander2 is a flexible multi-purpose workbench for rewriting, verification, constraint solving, flow graph analysis and related procedures that build up proofs or computation sequences. Moreover, tailor-made interpreters display terms as 2D structures ranging from trees and rooted graphs to tables, fractals and other turtle-system-generated pictures.

- FOL Resolution Theorem Prover
- An implementation of a simple theorem prover in first-order logic using Haskell.

- Halp
- Haskell Logic Prover is written in Haskell supports first order logic with plans to add predicates. Also included is a simple frontend written with gtk2hs

- Haskabelle
- Haskabelle is a converter from Haskell source files to Isabelle/HOL theories implemented in Haskell itself

- Hets
- The Heterogeneous Tool Set (Hets) is a parsing, static analysis and proof management tool combining various tools for different specification languages, thus providing a tool for heterogeneous specifications. It supports HasCASL for specification of Haskell programs, and uses Isabelle for proving

- Paradox
- Paradox processes first-order logic problems and tries to find finite-domain models for them.

- Proof General Kit
- The Proof General Kit designs and implements a component-based framework for interactive theorem proving. The central middleware of the toolkit is implemented in Haskell. The project is the sucessor of the highly successful Emacs-based Proof General interface.

- Yarrow
- Yarrow is a proof-assistant for Pure Type Systems (PTSs) with several extensions. In Yarrow you can experiment with various pure type systems, representing different logics and programming languages.

- Zeno
- Zeno is an automated proof system for Haskell program properties; developed at Imperial College London by William Sonnex, Sophia Drossopoulou and Susan Eisenbach. It aims to solve the general problem of equality between two Haskell terms, for any input value. Proofs and programs are output as Isabelle/HOL theories which are then automatically verified by said tool.

## 2 Libraries

- Ivor
- is type theory based theorem proving library -- written by Edwin Brady (see also the author's homepage, there are a lot of materials concerning dependent type theory there).

*This page contains a list of libraries and tools in a certain category. For a comprehensive list of such pages, see Applications and libraries.*