Aderhold, Markus Axel (2009)
Verification of Second-Order Functional Programs.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication
Abstract
Functional programming languages such as Haskell or ML allow the programmer to implement and to use higher-order procedures. A higher-order procedure gets a function as argument and applies this function to some values. For instance, procedure 'map' applies a function to all elements of a list and returns the list of the result values. Verifying that a higher-order program satisfies a certain property is particularly challenging, because it involves reasoning about indirect function calls; for instance, a call 'map(f, l)' directly calls procedure 'map' and indirectly calls function 'f' if list 'l' is non-empty. Using a higher-order procedure 'g', a procedure 'f' can be defined by higher-order recursion; i. e., procedure 'f' (directly) calls 'g' and passes itself as an argument to 'g', which leads to indirect recursive calls. These indirect recursive calls make reasoning about higher-order programs difficult. In this thesis we show how the verification of second-order functional programs can be supported by semi-automated theorem provers. 'Second-order' means that a procedure such as 'map' may only be applied to a first-order function, not to a higher-order function. This suffices for most examples that occur in practice and has advantages concerning the semantics of programs. Our goal is to verify the total correctness of programs. This requires a proof that the program terminates and that the result of the computation satisfies a user-defined property. Consequently, we investigate two main problems: termination analysis and inductive theorem proving. The general contribution of this thesis is the automated analysis of the dynamic call structure in second-order programs (introduced by indirect function calls). Specifically, we describe a technique that automatically analyzes and proves termination of many procedures that occur in practice and a technique that automatically synthesizes induction axioms that are suitable to prove properties of these procedures by induction. Finally, we show how the proof of the base and step cases can be supported by an automated theorem prover. The techniques have been implemented in the verification tool VeriFun. Several case studies confirm that they work well in practice and provide a significantly higher degree of automation than other inductive theorem provers.
Item Type: | Ph.D. Thesis | ||||
---|---|---|---|---|---|
Erschienen: | 2009 | ||||
Creators: | Aderhold, Markus Axel | ||||
Type of entry: | Primary publication | ||||
Title: | Verification of Second-Order Functional Programs | ||||
Language: | English | ||||
Referees: | Walther, Prof. Dr. Christoph ; Mantel, Prof. Dr. Heiko | ||||
Date: | 31 July 2009 | ||||
Place of Publication: | Darmstadt | ||||
Publisher: | Technische Universität | ||||
Refereed: | 14 July 2009 | ||||
URL / URN: | urn:nbn:de:tuda-tuprints-18652 | ||||
Abstract: | Functional programming languages such as Haskell or ML allow the programmer to implement and to use higher-order procedures. A higher-order procedure gets a function as argument and applies this function to some values. For instance, procedure 'map' applies a function to all elements of a list and returns the list of the result values. Verifying that a higher-order program satisfies a certain property is particularly challenging, because it involves reasoning about indirect function calls; for instance, a call 'map(f, l)' directly calls procedure 'map' and indirectly calls function 'f' if list 'l' is non-empty. Using a higher-order procedure 'g', a procedure 'f' can be defined by higher-order recursion; i. e., procedure 'f' (directly) calls 'g' and passes itself as an argument to 'g', which leads to indirect recursive calls. These indirect recursive calls make reasoning about higher-order programs difficult. In this thesis we show how the verification of second-order functional programs can be supported by semi-automated theorem provers. 'Second-order' means that a procedure such as 'map' may only be applied to a first-order function, not to a higher-order function. This suffices for most examples that occur in practice and has advantages concerning the semantics of programs. Our goal is to verify the total correctness of programs. This requires a proof that the program terminates and that the result of the computation satisfies a user-defined property. Consequently, we investigate two main problems: termination analysis and inductive theorem proving. The general contribution of this thesis is the automated analysis of the dynamic call structure in second-order programs (introduced by indirect function calls). Specifically, we describe a technique that automatically analyzes and proves termination of many procedures that occur in practice and a technique that automatically synthesizes induction axioms that are suitable to prove properties of these procedures by induction. Finally, we show how the proof of the base and step cases can be supported by an automated theorem prover. The techniques have been implemented in the verification tool VeriFun. Several case studies confirm that they work well in practice and provide a significantly higher degree of automation than other inductive theorem provers. |
||||
Alternative Abstract: |
|
||||
Uncontrolled Keywords: | verification, functional programs, second-order, higher-order, deduction, induction, automated theorem proving, termination, correctness, automated reasoning | ||||
Classification DDC: | 000 Generalities, computers, information > 004 Computer science | ||||
Divisions: | 20 Department of Computer Science 20 Department of Computer Science > Programming Methodology |
||||
Date Deposited: | 03 Sep 2009 08:24 | ||||
Last Modified: | 26 Aug 2018 21:25 | ||||
PPN: | |||||
Referees: | Walther, Prof. Dr. Christoph ; Mantel, Prof. Dr. Heiko | ||||
Refereed / Verteidigung / mdl. Prüfung: | 14 July 2009 | ||||
Export: | |||||
Suche nach Titel in: | TUfind oder in Google |
Send an inquiry |
Options (only for editors)
Show editorial Details |