Algebra of programming in Agda: dependent types for relational program derivation. Relational program derivation is the technique of stepwise refining a relational specification to a program by algebraic rules. The program thus obtained is correct by construction. Meanwhile, dependent type theory is rich enough to express various correctness properties to be verified by the type checker. We have developed a library, AoPA (Algebra of Programming in Agda), to encode relational derivations in the dependently typed programming language Agda. A program is coupled with an algebraic derivation whose correctness is guaranteed by the type system. Two non-trivial examples are presented: an optimisation problem and a derivation of quicksort in which well-founded recursion is used to model terminating hylomorphisms in a language with inductive types.
Keywords for this software
References in zbMATH (referenced in 7 articles )
Showing results 1 to 7 of 7.
- Botta, Nicola; Jansson, Patrik; Ionescu, Cezar; Christiansen, David R.; Brady, Edwin: Sequential decision problems, dependent types and generic solutions (2017)
- Chiang, Yu-Hsi; Mu, Shin-Cheng: Formal derivation of greedy algorithms from relational specifications: a tutorial (2016)
- Curtis, Sharon; Mu, Shin-Cheng: Calculating a linear-time solution to the densest-segment problem (2015)
- Kahl, Wolfram: Towards certifiable implementation of graph transformation via relation categories (2012)
- Tesson, Julien; Hashimoto, Hideki; Hu, Zhenjiang; Loulergue, Frédéric; Takeichi, Masato: Program calculation in Coq (2011)
- Achten, Peter; van Eekelen, Marko; Koopman, Pieter; Morazán, Marco T.: Trends in trends in functional programming 1999/2000 versus 2007/2008 (2010)
- Mu, Shin-Cheng; Ko, Hsiang-Shang; Jansson, Patrik: Algebra of programming in Agda: dependent types for relational program derivation (2009)