Logika pro vypočítatelné funkce - Logic for Computable Functions
Logika pro vypočítatelné funkce (LCF) je interaktivní automatizovaný testovací teorém vyvinut v Stanford a Edinburgh podle Robin Milner a spolupracovníky počátkem 70. let na základě teoretického základu logika z vypočítatelné funkce dříve navrhl Dana Scott. Práce na systému LCF zavedly obecné účely programovací jazyk ML umožnit uživatelům psát taktiky dokazující věty a podporovat je algebraické datové typy, parametrický polymorfismus, abstraktní datové typy, a výjimky.
Základní myšlenka
Věty v systému jsou výrazy speciální „věty“ abstraktní datový typ. Obecný mechanismus abstraktních datových typů ML zajišťuje, že věty jsou odvozeny pouze pomocí odvozovací pravidla dané operacemi věty abstraktního typu. Uživatelé mohou k výpočtu vět psát libovolně složité programy ML; platnost vět nezávisí na složitosti takových programů, ale vyplývá ze spolehlivosti implementace abstraktního datového typu a správnosti kompilátoru ML.
Výhody
Přístup LCF poskytuje podobnou důvěryhodnost jako systémy, které generují explicitní kontrolní certifikáty, ale bez nutnosti ukládat kontrolní objekty do paměti. Datový typ věty lze snadno implementovat do volitelně ukládat kontrolní objekty, v závislosti na konfiguraci běhového systému systému, takže zobecňuje základní přístup generování zkušební verze. Rozhodnutí o návrhu použít pro vývoj teorémů univerzální programovací jazyk znamená, že v závislosti na složitosti psaných programů je možné použít stejný jazyk k psaní podrobných důkazů, rozhodovacích postupů nebo testovacích vět.
Nevýhody
Důvěryhodná výpočetní základna
Implementace podkladového kompilátoru ML přidává do důvěryhodná výpočetní základna. Práce na CakeML[1] vedlo k formálně ověřenému kompilátoru ML, který zmírnil některé z těchto obav.
Účinnost a složitost důkazních postupů
Dokazování věty často těží z rozhodovacích postupů a algoritmů prokazování věty, jejichž správnost byla rozsáhle analyzována. Přímý způsob implementace těchto postupů v přístupu LCF vyžaduje, aby takové postupy vždy odvodily výsledky z axiomů, lemmat a odvozovacích pravidel systému, na rozdíl od přímého výpočtu výsledku. Potenciálně efektivnějším přístupem je použití reflexe k prokázání, že funkce pracující na vzorcích vždy poskytuje správný výsledek.[2]
Vlivy
Mezi další implementace patří Cambridge LCF. Pozdější systémy zjednodušily logiku, aby místo částečných funkcí používaly totální, což vedlo k HOL, HOL Light, a Isabelle proof assistant který podporuje různé logiky. Od roku 2019 Isabelle proof assistant stále obsahuje implementaci logiky LCF, Isabelle / LCF.
Poznámky
- ^ „CakeML“. Citováno 2. listopadu 2019.
- ^ Boyer, Robert S; Moore, J Strother. Metafunkce: Prokazovat je správně a efektivně je používat jako nové kontrolní postupy (PDF) (Zpráva). Technická zpráva CSL-108, SRI Projects 8527/4079. s. 1–111. Citováno 2. listopadu 2019.
Reference
- Gordon, Michael J.; Milner, Arthur J .; Wadsworth, Christopher P. (1979). Edinburgh LCF: Mechanizovaná logika výpočtu. Přednášky z informatiky. 78. Berlin Heidelberg: Springer. doi:10.1007/3-540-09724-4. ISBN 978-3-540-09724-2.
- Gordon, Michael J. C. (2000). "Od LCF k HOL: krátká historie". Důkaz, jazyk a interakce. Cambridge, MA: MIT Press. 169–185. ISBN 0-262-16188-5. Citováno 2007-10-11.
- Loeckx, Jacques; Sieber, Kurt (1987). Základy ověřování programu (2. vyd.). Vieweg + Teubner Verlag. doi:10.1007/978-3-322-96753-4. ISBN 978-3-322-96754-1.
- Milner, Robin (květen 1972). Logika pro vypočítatelné funkce: popis implementace stroje (PDF). Stanfordská Univerzita.
- Milner, Robin (1979). "LCF: Způsob provádění důkazů se strojem". In Bečvář, Jiří (ed.). Matematické základy informatiky 1979. Přednášky z informatiky. 74. Berlin Heidelberg: Springer. s. 146–159. doi:10.1007/3-540-09526-8_11. ISBN 978-3-540-09526-2.
 | Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |