Verified Functional Programming in Agda

Verified Functional Programming in Agda

Aaron Stump
ISBN: 9781970001242 | PDF ISBN: 9781970001259
Hardcover ISBN:9781970001273
Copyright © 2016 | 285 Pages | Publication Date: March, 2016

BEFORE YOU ORDER: You may have Academic or Corporate access to this title. Click here to find out: 10.1145/2841316

Published by the Association for Computing Machinery and Morgan & Claypool.

READ SAMPLE CHAPTER

Ordering Options: Paperback $79.95   E-book $63.96   Paperback & E-book Combo $99.94
Hardcover $109.95   Hardcover & E-book Combo $137.44


Why pay full price? Members receive 15% off all orders.
Learn More Here

Read Our Digital Content License Agreement (pop-up)

Purchasing Options:



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.

Table of Contents

Preface
Functional Programming with the Booleans
Introduction to Constructive Proof
Natural Numbers
Lists
Internal Verification
Type-level Computation
Generating Agda Parsers with gratr
A Case Study: Huffman Encoding and Decoding
Reasoning about Termination
Intuitionistic Logic and Kripke Semantics
Quick Guide to Symbols
Commonly Used Keyboard Commands
Some Extra Emacs Definitions
References
Index

About the Author(s)

Aaron Stump, The University of Iowa
Aaron Stump is a professor of Computer Science at The University of Iowa. His research interests are in Computational Logic and Programming Languages, especially Type Theory. He received a Bachelor's degree in Computer Science and Philosophy from Cornell University in 1997, and a PhD in Computer Science from Stanford University in 2002. Aaron is co-director with Cesare Tinelli of the University of Iowa Computational Logic Center, and he leads StarExec, a cross-community logic solving web service. He is the author of the textbook Programming Language Foundations (2013). Aaron was the best paper award winner in 2011 at the The 22nd International Conference on Term Rewriting and Applications (RTA), and winner also of the Haifa Verification Conference Award, 2010, with co-awardees Clark Barrett, Leonardo da Moura, Silvio Ranise, and Cesare Tinelli, Aaron was winner of a National Science Foundation Young Investigator award.

Reviews

Verified Functional Programming in Agda is an excellent introduction to the field of dependently typed programming. Stump does a great job of making the subject accessible to beginners without shying away from the more advanced topics.
Ulf Norell, Chalmers University of Technology, Sweden

Reviews (1)
Browse by Subject
Case Studies in Engineering
ACM Books
IOP Concise Physics
SEM Books


0 items
LATEST NEWS

Newsletter
Note: Registered customers go to: Your Account to subscribe.

E-Mail Address:

Your Name: