[Agda] AoPA -- Algebra of Programming in Agda (updated 2016)

Shin-Cheng Mu scm at iis.sinica.edu.tw
Wed May 18 11:14:40 CEST 2016


Hi all,

This is a notification that the library Algebra of Programming
in Agda (AoPA) has been updated and now works with Agda 2.5.1.

AoPA allows one to encode Algebra of Programming (BdM97) style 
program derivation, both functional and relational, in Agda.

New additions include the use of universe polymorphism, 
generic datatypes with polymorphic base functors, and theories 
for developing algorithms from Galois connections (MO11, CM15). 

Development of AoPA is still being continued. For more info,
see the Git Repository:

  https://github.com/scmu/aopa

====

The program derivation community has been exploring a relational 
theory of program calculation. A problem is specified as a relation 
that maps inputs to outputs, which allows us not to be over 
specific about which output to choose when they are equally good, 
leaving the choices to implementations. The task is to refine the 
specification into a functional implementation, using algebraic 
properties.

AoPA allows us to to develop relational proofs, in Agda, in the 
style of Bird and de Moor. Elements of the relational theory of 
programs are modelled in the type system of Agda. Calculations 
are expressed as program terms that, if type-checked, is guaranteed 
to be correct. In the end of a calculation one may extract a 
functional program that is proved to respect the relational 
specification.

sincerely, 
Shin
scm at iis.sinica.edu.tw

(BdM97) Richard Bird and Oege de Moor, Algebra of Programming. 
Prentice Hall, 1997.

(MO11) Shin-Cheng Mu and José Nuno Oliveira, Programming from 
Galois connections. The Journal of Logic and Algebraic Programming, 
Volume 81, Issue 6, August 2012, pp 680–704. doi>10.1016/j.jlap.2012.05.003.

(CM15) Yu-Hsi Chiang and Shin-Cheng Mu, Formal derivation of 
greedy algorithms from relational specifications: A tutorial. 
Journal of Logical and Algebraic Methods in Programming. In Press.



More information about the Agda mailing list