Tail recursion transformation for invertible functions
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Tail recursion transformation for invertible functions. / Tilsted Kristensen, Joachim; Kaarsgaard, Robin; Thomsen, Michael Kirkedal.
Reversible Computation: 15th International Conference, RC 2023, Giessen, Germany, July 18–19, 2023, Proceedings. Springer, 2023. p. 73–88 (Lecture Notes in Computer Science, Vol. 13960).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Tail recursion transformation for invertible functions
AU - Tilsted Kristensen, Joachim
AU - Kaarsgaard, Robin
AU - Thomsen, Michael Kirkedal
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-031-38100-3_6
DO - 10.1007/978-3-031-38100-3_6
M3 - Article in proceedings
SN - 978-3-031-38099-0
T3 - Lecture Notes in Computer Science
SP - 73
EP - 88
BT - Reversible Computation
PB - Springer
T2 - 15th International Conference on Reversible Computation, RC 2023
Y2 - 18 July 2023 through 19 July 2023
ER -
ID: 359598632