ACL2 (A Computational Logic for Applicative Common Lisp) is a
software
Software consists of computer programs that instruct the Execution (computing), execution of a computer. Software also includes design documents and specifications.
The history of software is closely tied to the development of digital comput ...
system consisting of a
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
, an extensible theory in a
first-order logic, and an
automated theorem prover. ACL2 is designed to support
automated reasoning in inductive logical theories, mostly for software and
hardware verification. The input language and implementation of ACL2 are written in
Common Lisp
Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ''ANSI INCITS 226-1994 (S2018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperli ...
. ACL2 is
free and open-source software
Free and open-source software (FOSS) is software available under a license that grants users the right to use, modify, and distribute the software modified or not to everyone free of charge. FOSS is an inclusive umbrella term encompassing free ...
.
Overview
The ACL2 programming language is an
applicative (
side-effect free) variant of Common Lisp. ACL2 is untyped. All ACL2
functions are
total — that is, every function maps each object in the ACL2
universe
The universe is all of space and time and their contents. It comprises all of existence, any fundamental interaction, physical process and physical constant, and therefore all forms of matter and energy, and the structures they form, from s ...
to another object in its universe.
ACL2's base theory
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
atizes the
semantics
Semantics is the study of linguistic Meaning (philosophy), meaning. It examines what meaning is, how words get their meaning, and how the meaning of a complex expression depends on its parts. Part of this process involves the distinction betwee ...
of its programming language and its built-in functions. User definitions in the programming language that satisfy a ''definitional principle'' extend the theory in a way that maintains the theory's
logical consistency.
The core of ACL2's theorem prover is based on
term rewriting, and this core is extensible in that user-discovered
theorem
In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
s can be used as ad hoc
proof techniques for subsequent
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
s.
ACL2 is intended to be an "industrial strength" version of the Boyer–Moore theorem prover,
NQTHM. Toward this goal, ACL2 has many features to support clean engineering of interesting mathematical and computational theories. ACL2 also derives efficiency from being built on Common Lisp; for example, the same specification that is the basis for inductive verification can be
compiled and run
natively.
In 2005, the authors of the Boyer-Moore family of provers, which includes ACL2, received the
ACM Software System Award "for pioneering and engineering a most effective theorem prover (...) as a formal methods tool for verifying safety-critical hardware and software."
Proofs
ACL2 has had numerous industrial applications. In 1995,
J Strother Moore
J Strother Moore (his first name is the alphabetic character "J" – not an abbreviated "J.") is an American computer scientist. He is a co-developer of the Boyer–Moore string-search algorithm, Boyer–Moore majority vote algorithm, and the Boy ...
,
Matt Kaufmann
Matt Kaufmann is a senior research scientist in the department of computer sciences at the University of Texas at Austin, United States. He was a recipient of the 2005 ACM Software System Award along with Robert S. Boyer and J Strother Moore, for ...
and Tom Lynch used ACL2 to prove the correctness of the floating point division operation of the
AMD K5 microprocessor in the wake of the
Pentium FDIV bug.
Industrial users of ACL2 include AMD, Arm, Centaur Technology, IBM, Intel, Oracle, and Collins Aerospace.
See also
*
List of proof assistants
References
External links
ACL2 websiteACL2s - ACL2 Sedan - An Eclipse-based interface developed by Peter Dillinger and Pete Manolios that includes powerful features to provide users with more automation and support for specifying conjectures and proving theorems with ACL2.
{{DEFAULTSORT:Acl2
Lisp (programming language)
Common Lisp (programming language) software
Proof assistants
Free theorem provers
Lisp programming language family
Software using the BSD license