Second-Order Functions and Theorems in ACL2

Alessandro Coglio

SOFT ('Second-Order Functions and Theorems') is a tool to mimic second-order functions and theorems in the first-order logic of ACL2. Second-order functions are mimicked by first-order functions that reference explicitly designated uninterpreted functions that mimic function variables. First-order theorems over these second-order functions mimic second-order theorems universally quantified over function variables. Instances of second-order functions and theorems are systematically generated by replacing function variables with functions. SOFT can be used to carry out program refinement inside ACL2, by constructing a sequence of increasingly stronger second-order predicates over one or more target functions: the sequence starts with a predicate that specifies requirements for the target functions, and ends with a predicate that provides executable definitions for the target functions.

In Matt Kaufmann and David L. Rager: Proceedings Thirteenth International Workshop on the ACL2 Theorem Prover and Its Applications (ACL2 2015), Austin, Texas, USA, 1-2 October 2015, Electronic Proceedings in Theoretical Computer Science 192, pp. 17–33.
Published: 18th September 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.192.3 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org