Agda is an advanced programming language based on Type Theory. Agda’s type system is expressive
enough to support full functional verification of programs, in two styles. In external verification, we write
pure functional programs and then write proofs of properties about them. The proofs are separate external
artifacts, typically using structural induction. In internal verification, we specify properties of programs
through rich types for the programs themselves. This often necessitates including proofs inside code, to show
the type checker that the specified properties hold. The power to prove properties of programs in these two
styles is a profound addition to the practice of programming, giving programmers the power to guarantee the
absence of bugs, and thus improve the quality of software more than previously possible.
Verified Functional Programming in Agda is the first book to provide a systematic exposition of external and
internal verification in Agda, suitable for undergraduate students of Computer Science. No familiarity with
functional programming or computer-checked proofs is presupposed.
The book begins with an introduction to functional programming through familiar examples like booleans,
natural numbers, and lists, and techniques for external verification. Internal verification is considered
through the examples of vectors, binary search trees, and Braun trees. More advanced material on type-level
computation, explicit reasoning about termination, and normalization by evaluation is also included. The
book also includes a medium-sized case study on Huffman encoding and decoding.
Agda is an advanced programming language based on Type Theory. Agda’s type system is expressive
enough to support full functional verification of programs, in two styles. In external verification, we write
pure functional programs and then write proofs of properties about them. The proofs are separate external
artifacts, typically using structural induction. In internal verification, we specify properties of programs
through rich types for the programs themselves. This often necessitates including proofs inside code, to show
the type checker that the specified properties hold. The power to prove properties of programs in these two
styles is a profound addition to the practice of programming, giving programmers the power to guarantee the
absence of bugs, and thus improve the quality of software more than previously possible.
Verified Functional Programming in Agda is the first book to provide a systematic exposition of external and
internal verification in Agda, suitable for undergraduate students of Computer Science. No familiarity with
functional programming or computer-checked proofs is presupposed.
The book begins with an introduction to functional programming through familiar examples like booleans,
natural numbers, and lists, and techniques for external verification. Internal verification is considered
through the examples of vectors, binary search trees, and Braun trees. More advanced material on type-level
computation, explicit reasoning about termination, and normalization by evaluation is also included. The
book also includes a medium-sized case study on Huffman encoding and decoding.