×

zbMATH — the first resource for mathematics

Shortcut fusion rules for the derivation of circular and higher-order programs. (English) Zbl 1256.68034
Summary: 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.
MSC:
68N18 Functional programming and lambda calculus
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramsky, S., Jung, A.: Domain theory. In: Handbook of Logic in Computer Science, pp. 1–168. Clarendon, Oxford (1994)
[2] Baier, H., Kugler, D., Margraf, M.: Elliptic curve cryptography based on ISO 15946. Technical report, Federal Office for Information Security (2007)
[3] Bird, R.: Using circular programs to eliminate multiple traversals of data. Acta Inform. 21, 239–250 (1984) · Zbl 0551.68017 · doi:10.1007/BF00264249
[4] Bird, R., de Moor, O.: Algebra of Programming. Prentice-Hall International Series in Computer Science, vol. 100. Prentice Hall, New York (1997) · Zbl 0867.68042
[5] Chitil, O.: Type-inference based deforestation of functional programs. Ph.D. thesis, RWTH Aachen (October 2000)
[6] 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) · Zbl 0792.18008
[7] 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) · Zbl 1370.68042
[8] 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) · Zbl 1098.68021
[9] 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)
[10] Dijkstra, A., Swierstra, D.: Typing Haskell with an attribute grammar. Technical report, Inst. of Information and Computing Sciences, Utrecht University (2004) · Zbl 1158.68354
[11] 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) · Zbl 1011.68017
[12] Fernandes, J.P.: Design, implementation and calculation of circular programs. Ph.D. thesis, Department of Informatics, University of Minho, Portugal (March 2009)
[13] 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)
[14] 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)
[15] Ghani, N., Johann, P.: Short cut fusion of recursive programs with computational effects. In: Symposium on Trends in Functional Programming (2008) · Zbl 1295.68151
[16] 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) · Zbl 1065.68034
[17] Gill, A.: Cheap deforestation for non-strict functional languages. Ph.D. thesis, Department of Computing Science, University of Glasgow, UK (1996)
[18] 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)
[19] Hinze, R., Jeuring, J.: Generic Haskell: practice and theory. In: Summer School on Generic Programming (2002) · Zbl 1274.68049
[20] Hutton, G., Meijer, E.: Monadic parsing in Haskell. J. Funct. Program. 8(4), 437–444 (1998) · Zbl 0917.68039 · doi:10.1017/S0956796898003050
[21] 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) · Zbl 1325.68047
[22] Johnsson, T.: Attribute grammars as a functional programming paradigm. In: Functional Programming Languages and Computer Architecture (1987) · Zbl 0633.68072
[23] 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)
[24] 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)
[25] Kuiper, M., Swierstra, D.: Using attribute grammars to derive efficient functional programs. In: Computing Science in the Netherlands (1987)
[26] 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) · Zbl 0984.68503
[27] Manzino, C., Pardo, A.: Shortcut fusion of monadic programs. J. Univers. Comput. Sci. 14(21), 3431–3446 (2008) · Zbl 1217.68053
[28] Marlow, S., Peyton Jones, S.: The new GHC/Hugs Runtime System (1999)
[29] 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) · Zbl 1295.68067
[30] Okasaki, C.: Breadth-first numbering: lessons from a small exercise in algorithm design. ACM SIGPLAN Not. 35(9), 131–136 (2000) · doi:10.1145/357766.351253
[31] 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)
[32] Paakki, J.: Attribute grammar paradigms–a high-level methodology in language implementation. ACM Comput. Surv. 27(2), 196–255 (1995) · doi:10.1145/210376.197409
[33] Pardo, A.: Generic accumulations. In: IFIP TC2/WG2.1 Working Conference on Generic Programming, pp. 49–78. Kluwer Academic, Dordrecht (2003) · Zbl 1089.68521
[34] Pardo, A.: A calculational approach to recursive programs with effects. Ph.D. thesis, Technische Universität Darmstadt (October 2001)
[35] Pettorossi, A., Skowron, A.: The lambda abstraction strategy for program derivation. In: Fundamenta Informaticae XII, pp. 541–561 (1987) · Zbl 0686.68014
[36] Swierstra, D.: Tutorial on attribute grammars. In: Second International Conference on Generative Programming and Component Engineering (GPCE) (2003)
[37] Swierstra, D., Chitil, O.: Linear, bounded, functional pretty-printing. J. Funct. Program. 19(01), 1–16 (2009) · Zbl 1181.68307 · doi:10.1017/S0956796808006990
[38] 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) · Zbl 0939.68556
[39] 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) · Zbl 1137.68347
[40] Voigtländer, J.: Using circular programs to deforest in accumulating parameters. High.-Order Symb. Comput. 17, 129–163 (2004) · Zbl 1075.68013 · doi:10.1023/B:LISP.0000029450.36668.cb
[41] Wadler, P.: Theorems for free! In: 4th International Conference on Functional Programming and Computer Architecture. ACM, London (1989)
[42] Wadler, P.: Deforestation: transforming programs to eliminate trees. Theor. Comput. Sci. 73, 231–248 (1990) · Zbl 0701.68013 · doi:10.1016/0304-3975(90)90147-A
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.