Coq - Coq - Wikipedia

Koenzym a doplněk stravy viz Koenzym Q10. Zkrácený název místa viz Coquihalla. Kohoutek viz Kohout.
Coq (software)
Logo Coq.png
VývojářiVývojový tým Coq
První vydání1. května 1989; Před 31 lety (1989-05-01) (verze 4.10)
Stabilní uvolnění
8.12.2[1] / 11. prosince 2020; 4 dny zpátky (2020-12-11)
Náhled verze
8.13 + beta1[2] / 7. prosince 2020; Před 8 dny (2020-12-07)
Úložištěgithub.com/ koq/ koq
NapsánoOCaml
Operační systémCross-platform
K dispozici vAngličtina
TypDůkaz asistent
LicenceLGPLv2.1
webová stránkakoq.inria.fr
Interaktivní zkušební relace v CoqIDE, zobrazující kontrolní skript vlevo a kontrolní stav vpravo.

Coq je interaktivní věta prover poprvé vydáno v roce 1989. Umožňuje vyjádření matematický tvrzení, mechanicky kontroluje důkazy těchto tvrzení, pomáhá najít formální důkazy a extrahuje certifikovaný program z konstruktivní důkaz jeho formální specifikace. Coq pracuje v rámci teorie počet indukčních konstrukcí, derivát počet konstrukcí. Coq není automatizovaný testovací teorém ale zahrnuje automatické dokazování věty taktika (postupy ) a různé rozhodnutí postupy.

The Sdružení pro výpočetní techniku udělena Thierry Coquand, Gérard Huet, Christine Paulin-Mohring Bruno Barras, Jean-Christophe Filliâtre, Hugo Herbelin, Chetan Murthy, Yves Bertot a Pierre Castéran Cena softwarového systému ACM pro Coq.

Coq je pojmenován po svém hlavním vývojáři Thierry Coquandovi.[Citace je zapotřebí ]

Přehled

Při pohledu na programovací jazyk Coq implementuje a závisle napsané funkční programovací jazyk;[3] při pohledu na logický systém implementuje a vyšší řád teorie typů. Vývoj společnosti Coq podporuje od roku 1984 společnost INRIA, nyní ve spolupráci s École Polytechnique, University of Paris-Sud, Paris Diderot University, a CNRS. V 90. letech ENS Lyon byla také součástí projektu. Vývoj Coq iniciovali Gérard Huet a Thierry Coquand a více než 40 lidí, zejména výzkumných pracovníků, přispělo k vlastnostem základního systému od jeho založení. Implementační tým postupně koordinovali Gérard Huet, Christine Paulin-Mohring, Hugo Herbelin a Matthieu Sozeau. Coq je implementován hlavně v OCaml s trochou C. Jádrový systém lze rozšířit pomocí a zapojit mechanismus.[4]

Název koq znamená „kohout " v francouzština a vychází z francouzské tradice pojmenování nástrojů pro vývoj výzkumu podle zvířat.[5] Až do roku 1991 implementoval Coquand jazyk zvaný Počet konstrukcí a v tuto chvíli se to jednoduše nazývalo CoC. V roce 1991 došlo k nové implementaci založené na rozšířené Počet indukčních konstrukcí byl zahájen a název byl změněn z CoC na Coq v nepřímém odkazu na Coquanda, který spolu s Gérardem Huetem vyvinuli Calculus of Constructions a spolu s Christine Paulin-Mohringovou přispěli do Calculus of Inductive Constructions.[6]

Coq poskytuje specifikační jazyk s názvem Gallina[7] ("slepice "v latině, španělštině, italštině a katalánštině). Programy napsané v Gallině mají slabá normalizace vlastnost, z čehož vyplývá, že vždy končí. Toto je charakteristická vlastnost jazyka, protože nekonečné smyčky (nekončící programy) jsou běžné v jiných programovacích jazycích,[8]a je jedním ze způsobů, jak vyhněte se problému se zastavením.

Čtyřbarevná věta a rozšíření SSReflect

Georges Gonthier z Microsoft Research v Cambridge, Anglie a Benjamin Werner z INRIA používá Coq k vytvoření ověřitelný důkaz z čtyřbarevná věta, který byl dokončen v roce 2005.[9] Jejich práce vedla k vývoji balíčku SSReflect („Small Scale Reflection“), který byl významným rozšířením Coq.[10] Navzdory svému názvu je většina funkcí přidaných do Coq SSReflectem funkcí pro obecné účely a neomezuje se na výpočetní reflexní styl důkazu. Mezi tyto funkce patří:

  • Další pohodlné notace pro nevyvratitelné a vyvratitelné porovnávání vzorů, na indukční typy s jedním nebo dvěma konstruktory
  • Implicitní argumenty pro funkce aplikované na nulové argumenty, což je užitečné při programování pomocí funkce vyššího řádu
  • Stručné anonymní argumenty
  • Vylepšený soubor taktika s výkonnějším párováním
  • Podpora reflexe

SSReflect 1.11 je volně dostupný, má dvojitou licenci pod otevřeným zdrojovým kódem CeCILL-B nebo CeCILL-2.0 licence a kompatibilní s Coq 8.11.[11]

Aplikace

Viz také

Reference

  1. ^ „Coq 8.12.2 is out“. 2020-12-11.
  2. ^ „Coq 8.13 + beta1 je venku“. 2020-12-07.
  3. ^ Krátký úvod do Coq
  4. ^ Avigad, Jeremy; Mahboubi, Assia (3. července 2018). Prokazování interaktivních vět: 9. mezinárodní konference, ITP 2018, konané jako ... Knihy Google. ISBN  9783319948218. Citováno 21. října 2018.
  5. ^ "Často kladené otázky". Citováno 2019-05-08.
  6. ^ "Úvod do počtu indukčních konstrukcí". Citováno 21. května 2019.
  7. ^ Adam Chlipala. „Certifikované programování se závislými typy“:"Knihovní vesmíry".
  8. ^ Adam Chlipala. „Certifikované programování se závislými typy“:"Library GeneralRec"."Knihovna InductiveTypes".
  9. ^ A b Gonthier, Georges (2008), „Formální důkaz - čtyřbarevná věta“ (PDF), Oznámení Americké matematické společnosti, 55 (11), s. 1382–1393, PAN  2463991
  10. ^ Georges Gonthier, Assia Mahboubi. „Úvod do malé reflexe v Coq“:„Žurnál formalizovaného uvažování“.
  11. ^ „Knihovna matematických komponent 1.11.0“.
  12. ^ Conchon, Sylvain; Filliâtre, Jean-Christophe (říjen 2007), „Persistentní datová struktura Unie-Find“, Workshop ACM SIGPLAN o ML, Freiburg, Německo
  13. ^ „Věta Feit-Thompsona byla v Coq úplně zkontrolována“. Msr-inria.inria.fr. 20. 9. 2012. Archivovány od originál dne 19. 11. 2016. Citováno 2012-09-25.

externí odkazy

Učebnice
Návody