1 - Survey and History of LCF
Published online by Cambridge University Press: 17 September 2009
Summary
Cambridge LCF is an interactive theorem prover for reasoning about computable functions. The terms of its logic, PPλ, constitute a tiny functional programming language. Cambridge LCF can be used for experimenting with first order proof; studying abstract constructions in domain theory; comparing the denotational semantics of programming languages; and verifying functional programs. It can reason about both strict and lazy evaluation.
There are many theorem provers in the LCF family. Each is descended from Edinburgh LCF and retains its fundamental ideas:
The user interacts with the prover through a programmable meta language, ML.
Logical formulae, theorems, rules, and proof strategies are ML data.
The prover guarantees soundness: it checks each inference and records each assumption.
Edinburgh LCF was developed in order to experiment with Scott's Logic of Computable Functions [41]. It performed many proofs involving denotational semantics and functional programming.
Cambridge LCF extended the logic of Edinburgh LCF with ∨, ∃, ⇔, and predicates, improved the efficiency, and added several inference mechanisms. It has been used in proofs about functional programming and several other theorem provers have been built from it.
LCF_LSM was developed for reasoning about digital circuits in a formalism related to CCS [32]. It verified some realistic devices [39], but is now obsolete.
HOL supports Church's Higher Order Logic [37], a general mathematical formalism. It is mainly used to prove digital circuits correct.
Another system supports a higher order Calculus of Constructions that can represent many other calculi.
- Type
- Chapter
- Information
- Logic and ComputationInteractive Proof with Cambridge LCF, pp. 3 - 12Publisher: Cambridge University PressPrint publication year: 1987