Abstract
Programs in languages such as Haskell are often datatype-centric and make extensive use of folds on that datatype. Incrementalization of such a program can significantly improve its performance by transforming monolithic atomic folds into incremental computations. Functional incrementalization separates the recursion from the application of the algebra in order to reduce redundant computations and reuse intermediate results. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. Our benchmarks show that incrementalized computations using the library are nearly as fast as handwritten atomic functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chakravarty, M.M.T., Keller, G., Peyton Jones, S.L., Marlow, S.: Associated Types with Class. In: POPL, pp. 1–13 (2005)
Hinze, R., Jeuring, J., Löh, A.: Type-indexed data types. Science of Computer Programming 51(1-2), 117–151 (2004)
Sheard, T., Peyton Jones, S.L.: Template Meta-programming for Haskell. In: Haskell, pp. 1–16 (2002)
Liu, Y.A.: Efficiency by Incrementalization: An Introduction. Higher-Order and Symbolic Computation 13(4), 289–313 (2000)
Adams, S.: Functional Pearls: Efficient sets – a balancing act. J. of Functional Programming 3(04), 553–561 (1993)
Claessen, K., Hughes, J.: QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In: ICFP, pp. 268–279 (2000)
Knuth, D.E.: Semantics of context-free languages. Theory of Computing Systems 2(2), 127–145 (1968)
Gibbons, J.: Upwards and downwards accumulations on trees. In: Bird, R.S., Woodcock, J.C.P., Morgan, C.C. (eds.) MPC 1992. LNCS, vol. 669, pp. 122–138. Springer, Heidelberg (1993)
Huet, G.: The Zipper. J. of Functional Programming 7(05), 549–554 (1997)
Bird, R.S.: Using Circular Programs to Eliminate Multiple Traversals of Data. Acta Informatica 21(3), 239–250 (1984)
Swierstra, W.: Why Attribute Grammars Matter. The Monad .Reader 4 (2005)
Peyton Jones, S.L., Marlow, S., Elliott, C.: Stretching the storage manager: weak pointers and stable names in Haskell. In: Mohnen, M., Koopman, P. (eds.) IFL 2000. LNCS, vol. 2011, pp. 37–58. Springer, Heidelberg (2001)
Hinze, R.: Memo functions, polytypically! In: Jeuring, J. (ed.) WGP (2000)
van Noort, T., Rodriguez Yakushev, A., Holdermans, S., Jeuring, J., Heeren, B.: A lightweight approach to datatype-generic rewriting. In: WGP, pp. 13–24 (2008)
Rodriguez Yakushev, A., Holdermans, S., Löh, A., Jeuring, J.: Generic Programming with Fixed Points for Mutually Recursive Datatypes. In: ICFP, pp. 233–244 (2009)
Leather, S., Löh, A., Jeuring, J.: Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization. Technical Report UU-CS-2009-024, Dept. of Information and Computing Sciences, Utrecht University (November 2009)
Fokkinga, M.M., Jeuring, J., Meertens, L., Meijer, E.: A Translation from Attribute Grammars to Catamorphisms. The Squiggolist 2(1), 20–26 (1991)
Saraiva, J., Swierstra, S.D., Kuiper, M.: Functional Incremental Attribute Evaluation. In: Watt, D.A. (ed.) CC 2000. LNCS, vol. 1781, pp. 279–294. Springer, Heidelberg (2000)
Viera, M., Swierstra, S.D., Swierstra, W.: Attribute Grammars Fly First-Class: How to do Aspect Oriented Programming in Haskell. In: ICFP, pp. 245–256 (2009)
Jeuring, J.: Incremental algorithms on lists. In: van Leeuwen, J. (ed.) SION Conference on Computer Science in the Netherlands, pp. 315–335 (1991)
Carlsson, M.: Monads for incremental computing. In: ICFP, pp. 26–35 (2002)
Acar, U.A., Blelloch, G.E., Harper, R.: Adaptive functional programming. In: POPL, pp. 247–259 (2002)
Bernardy, J.P.: Lazy Functional Incremental Parsing. In: Haskell, pp. 49–60 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Leather, S., Löh, A., Jeuring, J. (2010). Pull-Ups, Push-Downs, and Passing It Around. In: Morazán, M.T., Scholz, SB. (eds) Implementation and Application of Functional Languages. IFL 2009. Lecture Notes in Computer Science, vol 6041. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16478-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-16478-1_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16477-4
Online ISBN: 978-3-642-16478-1
eBook Packages: Computer ScienceComputer Science (R0)