Institutional Repository of Vilnius University
Programų korektiškumo įrodymai „Coq“ teoremų įrodymo aplinkoje /
Abstract
dc:descriptionDuring the software development process, when the extent and complexity of programs grows, the probability of bugs becomes very high. In practice, there are a lot of methods which are applied to make the developed software more robust. Methods developed for mathematically precise specification and verification of programs based on the formal proofs of their respective properties can be seen as separate field of study. As such methods have mathematical and logical foundations, the guarantees for program correctness provided by these methods are much stronger. However, the application of such methods is not trivial. The aim of this work is to present and study the basic elements of the refinement calculus. Instead of proving that the piece of software written in specific language has necessary properties, the refinement of programs is based on the idea to derive the executable program from specifications which are the precise high level mathematical description of software requirements. During all transformations, when the determinism increases and the required pieces of software are implemented, the correctness of program with respect to specification is preserved. If the initial specification is correct, then the derived program should also be correct. Ralph Back described mathematical foundations of the refinement calculus in his thesis. The basis for his work was Dijkstra’s language of guarded commands. The refinement calculus was also studied in other works by this and other authors. The theory studied in this work is mostly taken from the book “Refinement Calculus: A Systematic Introduction” by Ralph Back and Joakim von Wright. On the other hand, when one has well founded mathematical theory, the need for tool which would allow to prove the theorems related with that theory and to apply the theory for refinement of programs in practice, becomes apparent. Such tool should be reliable itself, expressive enough to describe the theory and should desirably offer means for automation of process. The proof assistant Coq was chosen for this work. It is popular tool for applications related with machine-checked theorem proving. In the first chapter of this work, several popular proof assistants are mentioned, some basic facts from the history of proof assistants are presented and key features of proof assistants are discussed. The focus here is on Coq proof assistant as this specific environment is used for the purposes of this work. The theory of program refinement calculus is shortly presented in the second chapter of this work. While studying the theory of the refinement calculus and trying to transfer the concepts from it, the specification language was developed, and some theorems related with its semantics were proved. Furthermore, possibilities of shallow and deep embedding of the refinement calculus specification language in the logical environment of the Coq proof assistant were studied.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Saulius, Mantas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD146237109&prefLang=en_US