Janis Voigtländer
ABSTRACT
We introduce a new transformation method to eliminate intermediate data structures occurring in functional programs due to repeated list concatenations and other data manipulations (additionally exemplified with list reversal and mapping of functions over lists).The general idea is to uniformly abstract from data constructors and manipulating operations by means of rank-2 polymorphic combinators that exploit algebraic properties of these operations to provide an optimized implementation. The correctness of transformations is proved by using the free theorems derivable from parametric polymorphic types.
- http://wwwtcs.inf.tu-dresden.de/~voigt/Vanish.lhs.]]Google Scholar
- The Haskell 98 Report. http://haskell.org/onlinereport.]]Google Scholar
- E. Albert, C. Ferri, F. Steiner, and G. Vidal. Improving functional logic programs by difference-lists. In Advances in Computing Science, Penang, Malaysia, Proceedings, volume 1961 of LNCS, pages 237--254. Springer-Verlag, 2000.]] Google ScholarDigital Library
- R. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. on Prog. Lang. and Systems, 6:487--504, 1984. Addendum Ibid., 7:490--492, 1985.]] Google ScholarDigital Library
- E. Boiten. The many disguises of accumulation. Technical Report 91-26, Dept. of Informatics, University of Nijmegen, 1991.]]Google Scholar
- O. Chitil. Type inference builds a short cut to deforestation. In International Conference on Functional Programming, Paris, France, Proceedings, pages 249--260. ACM Press, 1999.]] Google ScholarDigital Library
- O. Chitil. Type-Inference Based Deforestation of Functional Programs. PhD thesis, RWTH Aachen, 2000.]]Google Scholar
- O. Chitil. Compositional explanation of types and algorithmic debugging of type errors. In International Conference on Functional Programming, Florence, Italy, Proceedings, pages 193--204. ACM Press, 2001.]] Google ScholarDigital Library
- A. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, University of Glasgow, 1996.]]Google Scholar
- A. Gill, J. Launchbury, and S. Peyton Jones. A short cut to deforestation. In Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, Proceedings, pages 223--232. ACM Press, 1993.]] Google ScholarDigital Library
- Z. Hu, H. Iwasaki, and M. Takeichi. Calculating accumulations. New Generation Computing, 17:153--173, 1999.]] Google ScholarDigital Library
- J. Hughes. A novel representation of lists and its application to the function "reverse". Information Processing Letters, 22:141--144, 1986.]] Google ScholarDigital Library
- J. Hughes. The design of a pretty-printing library. In Advanced Functional Programming, volume 925 of LNCS, pages 53--96. Springer-Verlag, 1995.]] Google ScholarDigital Library
- P. Johann. Short cut fusion: Proved and improved. In Semantics, Applications, and Implementation of Program Generation, Florence, Italy, Proceedings, volume 2196 of LNCS, pages 47--71. Springer-Verlag, 2001.]]Google ScholarDigital Library
- A. Kühnemann, R. Glück, and K. Kakehi. Relating accumulative and non-accumulative functional programs. In Rewriting Techniques and Applications, Utrecht, The Netherlands, Proceedings, volume 2051 of LNCS, pages 154--168. Springer-Verlag, 2001.]] Google ScholarDigital Library
- J. Launchbury and R. Paterson. Parametricity and unboxing with unpointed types. In European Symposium on Programming, Linköping, Sweden, Proceedings, volume 1058 of LNCS, pages 204--218. Springer-Verlag, 1996.]] Google ScholarDigital Library
- D. Leivant. Polymorphic type inference. In Principles of Programming Languages, Austin, Texas, Proceedings, pages 88--98. ACM Press, 1983.]] Google ScholarDigital Library
- B. McAdam. Repairing Type Errors in Functional Programs. PhD thesis, University of Edinburgh, 2002.]]Google Scholar
- A. Moran and D. Sands. Improvement in a lazy context: An operational theory for call-by-need. In Principles of Programming Languages, San Antonio, Texas, Proceedings, pages 43--56. ACM Press, 1999.]] Google ScholarDigital Library
- S. Peyton Jones, W. Partain, and A. Santos. Let-floating: Moving bindings to give faster programs. In International Conference on Functional Programming, Philadelphia, Pennsylvania, Proceedings, pages 1--12. ACM Press, 1996.]] Google ScholarDigital Library
- S. Peyton Jones and A. Santos. A transformation-based optimiser for Haskell. Sci. of Comput. Prog., 32:3--47, 1998.]] Google ScholarDigital Library
- A. Pitts. Parametric polymorphism and operational equivalence. Math. Struct. Comput. Sci., 10:321--359, 2000.]] Google ScholarDigital Library
- J. Reynolds. Types, abstraction and parametric polymorphism. In Information Processing, Paris, France, Proceedings, pages 513--523. Elsevier Science Publishers B.V., 1983.]]Google Scholar
- D. Schmidt. Denotational Semantics: A Methodology for Language Development. Allyn and Bacon, 1986.]] Google ScholarDigital Library
- T. Sheard, Z. Benaissa, and M. Martel. Introduction to multi-stage programming using MetaML. http://cse.ogi.edu/~sheard/papers/manual.ps.]]Google Scholar
- J. Svenningsson. Shortcut fusion for accumulating parameters and zip-like functions. In International Conference on Functional Programming, Pittsburgh, Pennsylvania, Proceedings. ACM Press, 2002.]] Google ScholarDigital Library
- P. Wadler. The concatenate vanishes. Note, University of Glasgow, 1987 (revised, 1989).]]Google Scholar
- P. Wadler. Theorems for free! In Functional Programming Languages and Computer Architecture, London, England, Proceedings, pages 347--359. ACM Press, 1989.]] Google ScholarDigital Library
- J. Yang, G. Michaelson, P. Trinder, and J. Wells. Improved type error reporting. In Implementation of Functional Languages, Aachen, Germany, Draft Proceedings, pages 71--86, 2000.]]Google Scholar
Index Terms
- Concatenate, reverse and map vanish for free
Recommendations
Concatenate, reverse and map vanish for free
We introduce a new transformation method to eliminate intermediate data structures occurring in functional programs due to repeated list concatenations and other data manipulations (additionally exemplified with list reversal and mapping of functions ...
The Impact of seq on Free Theorems-Based Program Transformations
Program Transformation: Theoretical Foundations and Basic Techniques. Part 2Parametric polymorphism constrains the behavior of pure functional programs in a way that allows the derivation of interesting theorems about them solely from their types, i.e., virtually for free. Unfortunately, standard parametricity results - ...
The Impact of seq on Free Theorems-Based Program Transformations
Program Transformation: Theoretical Foundations and Basic Techniques. Part 2Parametric polymorphism constrains the behavior of pure functional programs in a way that allows the derivation of interesting theorems about them solely from their types, i.e., virtually for free. Unfortunately, standard parametricity results - ...
Comments