Article

Recycle Your Arrays!

Author:

Roman LeshchinskiyAuthors Info & Claims

PADL '09: Proceedings of the 11th International Symposium on Practical Aspects of Declarative Languages

Pages 209 - 223

https://doi.org/10.1007/978-3-540-92995-6_15

Published: 10 January 2009 Publication History

Abstract

Purely functional arrays are notoriously difficult to implement and use efficiently due to the absence of destructive updates and the resultant frequent copying. Deforestation frameworks such as stream fusion achieve signficant improvements here but fail for a number of important operations which can nevertheless benefit from elimination of temporaries. To mitigate this problem, we extend stream fusion with support for in-place execution of array operations. This optimisation, which we call <em>recycling</em>, is easy to implement and can significantly reduce array allocation and copying in purely functional array algorithms.

References

[1]

Wadler, P.: Deforestation: transforming programs to eliminate trees. Theoretical Computer Science (Special issue of selected papers from 2nd European Symposium on Programming) 73(2), 231-248 (1990)

[2]

Gill, A., Launchbury, J., Peyton Jones, S.: A short cut to deforestation. In: Conference on Functional Programming Languages and Computer Architecture, pp. 223-232 (1993)

[3]

Johann, P.: Short cut fusion: Proved and improved. In: Taha, W. (ed.) SAIG 2001. LNCS, vol. 2196, pp. 47-71. Springer, Heidelberg (2001)

[4]

Svenningsson, J.: Shortcut fusion for accumulating parameters & zip-like functions. In: Proceedings of the 7th ACM SIGPLAN International Conference on Functional programming, pp. 124-132. ACM Press, New York (2002)

[5]

Chakravarty, M.M.T., Keller, G.: Functional array fusion. In: Leroy, X. (ed.) Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming, pp. 205-216. ACM Press, New York (2001)

[6]

Chakravarty, M.M.T., Leshchinskiy, R., Peyton Jones, S., Keller, G., Marlow, S.: Data Parallel Haskell: a status report. In: DAMP 2007: Proceedings of the 2007 workshop on Declarative aspects of multicore programming, pp. 10-18. ACM, New York (2007)

[7]

Coutts, D., Leshchinskiy, R., Stewart, D.: Stream fusion: from lists to streams to nothing at all. In: Proceedings of the 2007 ACM SIGPLAN International Conference on Functional programming, pp. 315-326. ACM Press, New York (2007)

[8]

Coutts, D., Stewart, D., Leshchinskiy, R.: Rewriting Haskell strings. In: Hanus, M. (ed.) PADL 2007. LNCS, vol. 4354, pp. 50-64. Springer, Heidelberg (2006)

[9]

Bloss, A.: Update analysis and the efficient implementation of functional aggregates. In: Proceedings of the 4th international conference on Functional programming languages and computer architecture, pp. 26-38. ACM, New York (1989)

[10]

Odersky, M.: How to make destructive updates less destructive. In: Proc. 18th ACM Symp. on Principles of Programming Languages, pp. 25-36. ACM Press, New York (1991)

[11]

Sastry, A.V.S., Clinger, W., Ariola, Z.: Order-of-evaluation analysis for destructive updates in strict functional languages with flat aggregates. In: Conference on Functional Programming Languages and Computer Architecture, pp. 266-275. ACM Press, New York (1993)

[12]

Wadler, P.: Linear types can change the world. In: Programming Concepts and Methods, North, 347-359 (1990)

[13]

Launchbury, J., Peyton Jones, S.L.: Lazy functional state threads. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 24-35 (1994)

[14]

Peyton Jones, S.: Call-pattern specialisation for Haskell programs. In: Proceedings of the 2007 ACM SIGPLAN International Conference on Functional programming, pp. 327-337. ACM, New York (2007)

[15]

Peyton Jones, S., Santos, A.L.M.: A transformation-based optimiser for Haskell. Sci. Comput. Program. 32(1-3), 3-47 (1998)

[16]

Peyton Jones, S., Tolmach, A., Hoare, T.: Playing by the rules: rewriting as a practical optimisation technique in GHC. In: Hinze, R. (ed.) 2001 Haskell Workshop. ACM, New York (2001)

[17]

Leiserson, C.E., Maggs, B.M.: Communication-efficient parallel algorithms for distributed random-access machines. Algorithmica 3, 53-77 (1988)

Cited By

Claessen KPałka M(2013)Splittable pseudorandom number generators using cryptographic hashingACM SIGPLAN Notices10.1145/2578854.250378448:12(47-58)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2578854.2503784
Petersen LOrchard DGlew N(2013)Automatic SIMD vectorization for HaskellACM SIGPLAN Notices10.1145/2544174.250060548:9(25-36)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2544174.2500605
Claessen KPałka MShan C(2013)Splittable pseudorandom number generators using cryptographic hashingProceedings of the 2013 ACM SIGPLAN symposium on Haskell10.1145/2503778.2503784(47-58)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2503778.2503784
Show More Cited By

Recommendations

Extensible sparse functional arrays with circuit parallelism
PPDP '13: Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming

A longstanding open question in algorithms and data structures is the time and space complexity of pure functional arrays. Imperative arrays provide update and lookup operations that require constant time in the RAM theoretical model, but it is ...
Extensible sparse functional arrays with circuit parallelism

A longstanding open question in algorithms and data structures is the time and space complexity of pure functional arrays. Imperative arrays provide update and lookup operations that require constant time in the Random Access Machine (RAM) theoretical ...
MultiArray: a C++ library for generic programming with arrays
Research Articles

In C++, multi-dimensional arrays are often used but the language provides limited native support for them. The language, in its Standard Library, supplies sophisticated interfaces for manipulating sequential data, but relies on its bare-bones C heritage ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PADL '09: Proceedings of the 11th International Symposium on Practical Aspects of Declarative Languages

January 2009

283 pages

ISBN:9783540929949

Editors:
Andy Gill
University of Kansas, Lawrence, USA KS 66045-7621
,
Terrance Swift
Universidade Nova de Lisboa, CENTRIA, Sheperdstown, USA WV 25443

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 January 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Claessen KPałka M(2013)Splittable pseudorandom number generators using cryptographic hashingACM SIGPLAN Notices10.1145/2578854.250378448:12(47-58)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2578854.2503784
Petersen LOrchard DGlew N(2013)Automatic SIMD vectorization for HaskellACM SIGPLAN Notices10.1145/2544174.250060548:9(25-36)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2544174.2500605
Claessen KPałka MShan C(2013)Splittable pseudorandom number generators using cryptographic hashingProceedings of the 2013 ACM SIGPLAN symposium on Haskell10.1145/2503778.2503784(47-58)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2503778.2503784
Petersen LOrchard DGlew NMorrisett GUustalu T(2013)Automatic SIMD vectorization for HaskellProceedings of the 18th ACM SIGPLAN international conference on Functional programming10.1145/2500365.2500605(25-36)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2500365.2500605
Höner zu Siederdissen C(2012)Sneaking around concatMapACM SIGPLAN Notices10.1145/2398856.236455947:9(215-226)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2398856.2364559
Höner zu Siederdissen CThiemann PFindler R(2012)Sneaking around concatMapProceedings of the 17th ACM SIGPLAN international conference on Functional programming10.1145/2364527.2364559(215-226)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2364527.2364559
Schilling T(2011)Challenges for a trace-based just-in-time compiler for haskellProceedings of the 23rd international conference on Implementation and Application of Functional Languages10.1007/978-3-642-34407-7_4(51-68)Online publication date: 3-Oct-2011
https://dl.acm.org/doi/10.1007/978-3-642-34407-7_4

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents