Formalisation in higher-order logic and code generation to functional languages of the Gauss-Jordan algorithm
-
1
Universidad de La Rioja
info
ISSN: 0956-7968
Año de publicación: 2015
Volumen: 25
Número: 1
Páginas: 1-21
Tipo: Artículo
Otras publicaciones en: Journal of Functional Programming
Proyectos relacionados
Resumen
In this paper, we present a formalisation in a proof assistant, Isabelle/HOL, of a naive version of the Gauss-Jordan algorithm, with explicit proofs of some of its applications; and, additionally, a process to obtain versions of this algorithm in two different functional languages (SML and Haskell) by means of code generation techniques from the verified algorithm. The aim of this research is not to compete with specialised numerical implementations of Gauss-like algorithms, but to show that formal proofs in this area can be used to generate usable functional programs. The obtained programs show compelling performance in comparison to some other verified and functional versions, and accomplish some challenging tasks, such as the computation of determinants of matrices of big integers and the computation of the homology of matrices representing digital images