Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-18T19:02:42.464Z Has data issue: false hasContentIssue false
  • English
  • Français

The worker/wrapper transformation

Part of: JFP Research Articles

Published online by Cambridge University Press:  01 March 2009

ANDY GILL  and
GRAHAM HUTTON
ANDY GILL
Affiliation:
University of Kansas, USA (e-mail: andygill@ku.edu)
GRAHAM HUTTON
Affiliation:
University of Nottingham, UK (e-mail: gmh@cs.nott.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The worker/wrapper transformation is a technique for changing the type of a computation, usually with the aim of improving its performance. It has been used by compiler writers for many years, but the technique is little known in the wider functional programming community, and has never been described precisely. In this article we explain, formalise and explore the generality of the worker/wrapper transformation. We also provide a systematic recipe for its use as an equational reasoning technique for improving the performance of programs, and illustrate the power of this recipe using a range of examples.

Type
Articles
Information
Journal of Functional Programming , Volume 19 , Issue 2 , March 2009 , pp. 227 - 251
Copyright
Copyright © Cambridge University Press 2009

References

Ager, Mads Sig, Biernacki, Dariusz, Danvy, Olivier & Midtgaard, Jan (2003) A functional correspondence between evaluators and abstract machines. In Proceedings of the Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming Uppsala, Sweden.Google Scholar
Altenkirch, Thorsten (2001) Representations of first-order function types as terminal coalgebras. In Typed Lambda Calculi and Applications. LNCS, no. 2044. Berlin: Springer.Google Scholar
Backhouse, Roland (2002) Galois connections and fixed point calculus. In Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. LNCS Tutorial, vol. 2297. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Backhouse, Roland, Bijsterveld, Marcel, van Geldrop, Rik & van der Woude, Jaap (1995) Categorical fixed point calculus. In Proceedings of the Sixth International Conference on Category Theory and Computer Science. Berlin: Springer-Verlag.Google Scholar
Bird, Richard (1998) Introduction to Functional Programming using Haskell, second edition. New York: Prentice Hall.Google Scholar
Burstall, Rod & Darlington, John (1977) A transformational system for developing recursive programs. J. ACM 24, 44–67.CrossRefGoogle Scholar
Chitil, Olaf (2000a) Type-Inference Based Deforestation of Functional Programs. Ph.D. thesis, RWTH Aachen.Google Scholar
Chitil, Olaf (2000b) Type-inference based short cut deforestation (nearly) without inlining. In Proceedings of 11th International Workshop on Implementation of Functional Languages, Clack, Chris and Koopman, Pieter (eds). LNCS, no. 1868. Berlin: Springer.Google Scholar
Coutts, Duncan, Leshchinskiy, Roman & Stewart, Don (2007) Stream fusion: From lists to streams to nothing at all. In Proceedings of the 2007 ACM SIGPLAN International Conference on Functional Programming. New York: ACM Press.Google Scholar
Gamma, Erich, Helm, Richard, Johnson, Ralph & Vlissides, John (1995) Design Patterns. Reading, Mass: Addison-Wesley Professional.Google Scholar
Gibbons, Jeremy & Jones, Geraint (1998). The under-appreciated unfold. In Proceedings of the Third ACM SIGPLAN International Conference on Functional Programming Baltimore, Maryland.Google Scholar
Gill, Andy (1996) Cheap Deforestation for Non-Strict Functional Languages. Ph.D. thesis, University of Glasgow.Google Scholar
Gill, Andy (2006) Introducing the haskell equational reasoning assistant. In Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell. New York: ACM Press.Google Scholar
Gill, Andy, Launchbury, John & Peyton Jones, Simon (1993) A short cut to deforestation. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture. New York: ACM Press.Google Scholar
Hinze, Ralf (2008) Functional pearl: Streams and unique fixed points. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming Victoria, British Columbia.Google Scholar
Hoare, Tony (1972) Proof of correctness of data representations. Acta Informatica 1 (4), 271–281.CrossRefGoogle Scholar
Hughes, John (1986) A novel representation of lists and its application to the function reverse. Info. Process. Lett. 22 (3), pp 141–144.CrossRefGoogle Scholar
Hutton, Graham (1999) A tutorial on the universality and expressiveness of fold. J. Funct. Prog. 9 (4), pp 355–372.CrossRefGoogle Scholar
Hutton, Graham (2007) Programming in Haskell, Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Hutton, Graham & Wright, Joel (2004) Compiling exceptions correctly. In Proceedings of the Seventh International Conference on Mathematics of Program Construction. LNCS, vol. 3125. Stirling, Scotland: Springer.Google Scholar
Hutton, Graham & Wright, Joel (2006) Calculating an exceptional machine. Selected papers from the Fifth Symposium on Trends in Functional Programming, Munich, vol. 5, November 2004 UK: Intellect.Google Scholar
Hutton, Graham & Wright, Joel (2007) What is the meaning of these constant interruptions? J. Funct. Prog. 17 (6), pp 777–792.CrossRefGoogle Scholar
Launchbury, John & Sheard, Tim (1995) Warm fusion: Deriving build-catas from recursive definitions. In Proceedings of the Seventh ACM SIGPLAN/SIGARCH International Conference on Functional Programming Languages and Computer Architecture. New York: ACM Press.Google Scholar
McBride, Conor & Paterson, Ross (2008) Applicative programming with effects. J. Funct. Prog. 18 (1), pp 1–13.CrossRefGoogle Scholar
Meijer, Erik, Fokkinga, Maarten & Paterson, Ross (1991) Functional programming with bananas, lenses, envelopes and barbed wire. In Proceedings of the Conference on Functional Programming and Computer Architecture, Hughes, John (ed). LNCS, no. 523. Springer-Verlag.Google Scholar
Michie, Donald (1968) Memo functions and machine learning. Nature, 218, pp 19–22.CrossRefGoogle Scholar
Peyton Jones, Simon (2003) Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press. Also available on www.haskell.org/definition.Google Scholar
Peyton Jones, Simon & Launchbury, John (1991) Unboxed values as first class citizens in a non-strict functional language. In Proceedings of the Conference on Functional Programming and Computer Architecture. Cambridge, MA: Springer-Verlag.Google Scholar
Peyton Jones, Simon & Partain, Will (1993) Measuring the effectiveness of a simple strictness analyser. In Proceedings of the 1993 Glasgow Workshop on Functional Programming, Hammond, Kevin & O'Donnell, John (eds). Ayr, Scotland: Springer-Verlag.Google Scholar
Peyton Jones, Simon, Tolmach, Andrew & Hoare, Tony (2001) Playing by the rules: Rewriting as a practical optimisation technique in GHC. In Proceedings of the 2001 ACM SIGPLAN Workshop on Haskell. ACM Press.Google Scholar
Reynolds, John C. (1972) Definitional interpreters for higher-order programming languages. In Proceedings of the ACM Annual Conference. ACM Press.Google Scholar
Sands, David (1998) Improvement theory and its applications. In Higher Order Operational Techniques in Semantics, Gordon, Andrew & Pitts, Andrew (eds). Cambridge, UK: Cambridge University Press.Google Scholar
Santos, Andre (1995) Compilation by Transformation in Non-strict Functional Languages. Ph.D. thesis, University of Glasgow.Google Scholar
Schmidt, David (1986) Denotational Semantics: A Methodology for Language Development. Allyn and Bacon, Inc.Google Scholar
Spivey, Mike (1990) A functional theory of exceptions. Sci. Comput. Prog. 14 (1), pp 25–42.CrossRefGoogle Scholar
Thielecke, Hayo (2002) Comparing control constructs by double-barrelled CPS. Higher-Order Symbol. Comput. 15 (2/3), pp 141–160.CrossRefGoogle Scholar
Turner, David A. (1995) Elementary strong functional programming. In Proceedings of the First International Symposium on Functional Programming Languages in Education. LNCS, no. 1022. Springer-Verlag.Google Scholar
Wadler, Philip (1992a) Monads for functional programming. In Proceedings of the Marktoberdorf Summer School on Program Design Calculi, Broy, Manfred (ed). Springer–Verlag.Google Scholar
Wadler, Philip (1992b) The essence of functional programming. Proc. Principles Prog. Lang. New York: ACM Press, pp 1–14.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.