Tail Recursion Transformation for Invertible Functions

Joachim Tilsted Kristensen*, Robin Kaarsgaard, Michael Kirkedal Thomsen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Tail recursive functions allow for a wider range of optimisations than general recursive functions. For this reason, much research has gone into the transformation and optimisation of this family of functions, in particular those written in continuation passing style (CPS).

Though the CPS transformation, capable of transforming any recursive function to an equivalent tail recursive one, is deeply problematic in the context of reversible programming (as it relies on troublesome features such as higher-order functions), we argue that relaxing (local) reversibility to (global) invertibility drastically improves the situation. On this basis, we present an algorithm for tail recursion conversion specifically for invertible functions. The key insight is that functions introduced by program transformations that preserve invertibility, need only be invertible in the context in which the functions subject of transformation calls them. We show how a bespoke data type, corresponding to such a context, can be used to transform invertible recursive functions into a pair of tail recursive function acting on this context, in a way where calls are highlighted, and from which a tail recursive inverse can be straightforwardly extracted.
Original languageEnglish
Title of host publicationReversible Computation : 15th International Conference, RC 2023, Giessen, Germany, July 18–19, 2023, Proceedings
EditorsMartin Kutrib, Uwe Meyer
PublisherSpringer
Publication date2023
Pages73-88
ISBN (Print)9783031380990
ISBN (Electronic)978-3-031-38100-3
DOIs
Publication statusPublished - 2023
Event15th International Conference Reversible Computation - Giessen, Germany
Duration: 19. Jun 202319. Jul 2023

Conference

Conference15th International Conference Reversible Computation
Country/TerritoryGermany
CityGiessen
Period19/06/202319/07/2023
SeriesLecture Notes in Computer Science
Volume13960
ISSN0302-9743

Keywords

  • CPS transformation
  • program inversion
  • program transformation
  • tail recursion

Cite this