MATHEMATICAL ENGINEERING TECHNICAL REPORTS Reversing Iterations: IO Swapping Leads You There And Back Again
Akimasa Morihata, Kazuhiko Kakehi, Zhenjiang Hu, Masato Takeichi · 2005
TABA (There And Back Again) [DG02], proposed by Danvy and Goldberg, is a special but powerful programming pattern where a recursive function traverses lists at return time. They showed the TABA programs, but neither derivation nor manipulation of the TABA programs were presented. We propose a novel program transformation rule called IO swapping. The rule swaps input and output values of functions and introduces iteration at return times. Using this rule three stories of TABA are played out in this paper: systematic derivation of a basic TABA program; manipulation of TABA programs including palindrome through function fusion; and extension of the rule to deal with circular dependency of inputs and outputs like repmin function, introduced by Bird [Bir84], and with structures other than lists like binary trees.