Journal of Functional Programming

Table of Contents - May 2012 - Volume 22, Issue 03  

Articles

Manipulating accumulative functions by swapping call-time and return-time computations*

AKIMASA MORIHATAa1, KAZUHIKO KAKEHIa2, ZHENJIANG HUa3 and MASATO TAKEICHIa4

a1 Tohoku University, Sendai, Japan (e-mail: morihata@riec.tohoku.ac.jp)

a2 University of Tokyo, Tokyo, Japan

a3 National Institute of Informatics, Chiyoda, Tokyo, Japan

a4 National Institution for Academic Degrees and University Evaluation, Kodaira-shi, Tokyo, Japan

Abstract

Functional languages are suitable for transformational developments of programs. However, accumulative functions, or in particular tail-recursive functions, are known to be less suitable for manipulation. In this paper, we propose a program transformation named “IO swapping” that swaps call-time and return-time computations. It moves computations in accumulative parameters to results and thereby enables interesting transformations. We demonstrate effectiveness of IO swapping by several applications: deforestation, higher order removal, program inversion, and manipulation of circular programs.

(Online publication May 08 2012)

Footnotes

* A preliminary report of this work was published in Morihata, A., Kakehi, K., Hu, Z. & Takeichi, M. (2006) Swapping arguments and results of recursive functions. In Proceedings of the 8th International Conference on Mathematics of Program Construction (MPC 2006), Kuressaare, Estonia. Lecture Notes in Computer Science, vol. 4014. New York, USA: Springer-Verlag, pp. 379–396.