Back to search

Institutional Repository of Vilnius University

Programų korektiškumo įrodymai „Coq“ teoremų įrodymo aplinkoje /

Abstract

dc:description

During 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.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Saulius, Mantas,. Programų korektiškumo įrodymai „Coq“ teoremų įrodymo aplinkoje /. Institutional Repository of Vilnius University, 2022. https://repository.vu.lt/VU:ELABAETD146237109&prefLang=en_US