## Abstract

Reversible computation studies computations which exhibit both forward and backward determinism. Among others, it has been studied for half a century for its applications in low-power computing, and forms the basis for quantum computing. Though certified program equivalence is useful for a number of applications (e.g., certified compilation and optimization), little work on this topic has been carried out for reversible programming languages. As a notable exception, Carette and Sabry have studied the equivalences of the finitary fragment of a reversible combinator calculus, yielding a two-level calculus of type isomorphisms and equivalences between them. In this paper, we extend the two-level calculus of finitary to one for full (i.e., with both recursive types and iteration by means of a trace combinator) using the delay monad, which can be regarded as a “computability-aware” analogue of the usual maybe monad for partiality. This yields a calculus of iterative (and possibly non-terminating) reversible programs acting on user-defined dynamic data structures together with a calculus of certified program equivalences between these programs.

Originalsprog | Engelsk |
---|---|

Titel | Mathematics of Program Construction- 13th International Conference, MPC 2019, Proceedings |

Redaktører | Graham Hutton |

Publikationsdato | 2019 |

Sider | 366-384 |

ISBN (Trykt) | 9783030336356 |

DOI | |

Status | Udgivet - 2019 |