Abstract
Functional programs often combine separate parts using intermediate data structures for communicating results. Programs so defined are modular, easier to understand and maintain, but suffer from inefficiencies due to the generation of those gluing data structures. To eliminate such redundant data structures, some program transformation techniques have been proposed. One such technique is shortcut fusion, and has been studied in the context of both pure and monadic functional programs.
In this paper, we study several shortcut fusion extensions, so that, alternatively, circular or higher-order programs are derived. These extensions are also provided for effect-free programs and monadic ones. Our work results in a set of generic calculation rules, that are widely applicable, and whose correctness is formally established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abramsky, S., Jung, A.: Domain theory. In: Handbook of Logic in Computer Science, pp. 1–168. Clarendon, Oxford (1994)
Baier, H., Kugler, D., Margraf, M.: Elliptic curve cryptography based on ISO 15946. Technical report, Federal Office for Information Security (2007)
Bird, R.: Using circular programs to eliminate multiple traversals of data. Acta Inform. 21, 239–250 (1984)
Bird, R., de Moor, O.: Algebra of Programming. Prentice-Hall International Series in Computer Science, vol. 100. Prentice Hall, New York (1997)
Chitil, O.: Type-inference based deforestation of functional programs. Ph.D. thesis, RWTH Aachen (October 2000)
Cockett, R., Spencer, D.: Strong categorical datatypes I. In: Seely, R.A.C. (ed.) International Meeting on Category Theory 1991. Canadian Mathematical Society Conference Proceedings, vol. 13, pp. 141–169 (1991)
Danielsson, N.A., Hughes, J., Jansson, P., Gibbons, J.: Fast and loose reasoning is morally correct. In: POPL’06: Proc. of the 33rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. ACM, New York (2006)
Danvy, O., Goldberg, M.: There and back again. In: ICFP’02: Proc. of the 7th ACM SIGPLAN Int. Conf. on Functional Programming. ACM, New York (2002)
de Moor, O., Peyton Jones, S.L., Van Wyk, E.: Aspect-oriented compilers. In: GCSE’99: Proc. of the 1st International Symposium on Generative and Component-Based Software Engineering, pp. 121–133. Springer, Berlin (2000)
Dijkstra, A., Swierstra, D.: Typing Haskell with an attribute grammar. Technical report, Inst. of Information and Computing Sciences, Utrecht University (2004)
Erkök, L., Launchbury, J.: A recursive do for Haskell. In: Haskell’02: Proceedings of the ACM SIGPLAN Haskell Workshop, pp. 29–37. ACM, New York (2002)
Fernandes, J.P.: Design, implementation and calculation of circular programs. Ph.D. thesis, Department of Informatics, University of Minho, Portugal (March 2009)
Fernandes, J.P., Saraiva, J.: Tools and libraries to model and manipulate circular programs. In: PEPM’07: Proc. of the ACM SIGPLAN 2007 Symposium on Partial Evaluation and Program Manipulation, pp. 102–111. ACM, New York (2007)
Fernandes, J.P., Pardo, A., Saraiva, J.: A shortcut fusion rule for circular program calculation. In: Proceedings of the ACM SIGPLAN Haskell Workshop, pp. 95–106. ACM, New York (2007)
Ghani, N., Johann, P.: Short cut fusion of recursive programs with computational effects. In: Symposium on Trends in Functional Programming (2008)
Gibbons, J.: Calculating functional programs. In: Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. LNCS, vol. 2297, pp. 148–203. Springer, Berlin (2002)
Gill, A.: Cheap deforestation for non-strict functional languages. Ph.D. thesis, Department of Computing Science, University of Glasgow, UK (1996)
Gill, A., Launchbury, J., Peyton Jones, S.L.: A short cut to deforestation. In: Conference on Functional Programming Languages and Computer Architecture, pp. 223–232 (1993)
Hinze, R., Jeuring, J.: Generic Haskell: practice and theory. In: Summer School on Generic Programming (2002)
Hutton, G., Meijer, E.: Monadic parsing in Haskell. J. Funct. Program. 8(4), 437–444 (1998)
Johann, P., Voigtländer, J.: Free theorems in the presence of seq. In: POPL’04: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 99–110. ACM, New York (2004)
Johnsson, T.: Attribute grammars as a functional programming paradigm. In: Functional Programming Languages and Computer Architecture (1987)
Jones, G., Gibbons, J.: Linear-time breadth-first tree algorithms an exercise in the arithmetic of folds and zips. Technical Report 71, Dept. of Computer Science, University of Auckland (1993)
Kastens, U., Pfahler, P., Jung, M.T.: The eli system. In: CC’98: Proceedings of the 7th International Conference on Compiler Construction, pp. 294–297. Springer, London (1998)
Kuiper, M., Swierstra, D.: Using attribute grammars to derive efficient functional programs. In: Computing Science in the Netherlands (1987)
Lawall, J.L.: Implementing circularity using partial evaluation. In: Proceedings of the Second Symposium on Programs as Data Objects (PADO). LNCS, vol. 2053. Springer, Berlin (2001)
Manzino, C., Pardo, A.: Shortcut fusion of monadic programs. J. Univers. Comput. Sci. 14(21), 3431–3446 (2008)
Marlow, S., Peyton Jones, S.: The new GHC/Hugs Runtime System (1999)
Ohori, A., Sasano, I.: Lightweight fusion by fixed point promotion. In: POPL’07: Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 143–154. ACM, New York (2007)
Okasaki, C.: Breadth-first numbering: lessons from a small exercise in algorithm design. ACM SIGPLAN Not. 35(9), 131–136 (2000)
Onoue, Y., Hu, Z., Iwasaki, H., Takeichi, M.: A calculational fusion system HYLO. In: IFIP TC 2 Working Conference on Algorithmic Languages and Calculi, Le Bischenberg, France, pp. 76–106. Chapman & Hall, London (1997)
Paakki, J.: Attribute grammar paradigms—a high-level methodology in language implementation. ACM Comput. Surv. 27(2), 196–255 (1995)
Pardo, A.: Generic accumulations. In: IFIP TC2/WG2.1 Working Conference on Generic Programming, pp. 49–78. Kluwer Academic, Dordrecht (2003)
Pardo, A.: A calculational approach to recursive programs with effects. Ph.D. thesis, Technische Universität Darmstadt (October 2001)
Pettorossi, A., Skowron, A.: The lambda abstraction strategy for program derivation. In: Fundamenta Informaticae XII, pp. 541–561 (1987)
Swierstra, D.: Tutorial on attribute grammars. In: Second International Conference on Generative Programming and Component Engineering (GPCE) (2003)
Swierstra, D., Chitil, O.: Linear, bounded, functional pretty-printing. J. Funct. Program. 19(01), 1–16 (2009)
Takano, A., Meijer, E.: Shortcut deforestation in calculational form. In: Proc. Conference on Functional Programming Languages and Computer Architecture, pp. 306–313. ACM, New York (1995)
Voigtländer, J.: Semantics and pragmatics of new shortcut fusion rules. In: Proc. of the 2008 International Symposium on Functional and Logic Programming, pp. 163–179. Springer, Berlin (2008)
Voigtländer, J.: Using circular programs to deforest in accumulating parameters. High.-Order Symb. Comput. 17, 129–163 (2004)
Wadler, P.: Theorems for free! In: 4th International Conference on Functional Programming and Computer Architecture. ACM, London (1989)
Wadler, P.: Deforestation: transforming programs to eliminate trees. Theor. Comput. Sci. 73, 231–248 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research conducted under the SSaaPP research project, PTDC/EIA-CCO/108613/2008.
J.P. Fernandes was supported by Fundação para a Ciência e Tecnologia, Grant No. SFRH/BPD/46987/2008.
Rights and permissions
About this article
Cite this article
Pardo, A., Fernandes, J.P. & Saraiva, J. Shortcut fusion rules for the derivation of circular and higher-order programs. Higher-Order Symb Comput 24, 115–149 (2011). https://doi.org/10.1007/s10990-011-9076-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10990-011-9076-x