Top

Published in:

2018 | OriginalPaper | Chapter

Memoized Flat Closures for CPS

or Taming Memory Allocation for in CPS

Authors : Marco T. Morazán, Lindsey M. Reams, Nicholas R. Olson, Shamil Dzhatdoyev

Published in: Trends in Functional Programming

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Compilers for functional languages are judged, in part, on how well they handle \(\lambda \)-expressions. The evaluation of \(\lambda \)-expressions traditionally requires closure allocations which can be intensive and can interact poorly with a garbage collector. Work on closure representation and garbage collection has successfully improved this interaction. This work, however, does not address the actual allocation of closures in the first place. This is important, because the only closures that do not have to be garbage collected are the closures that are never allocated. This article explores a novel mechanism to reduce flat-closure allocations based on memoization. To test this new mechanism, a compiler has been developed that uses continuation-passing style as an intermediate representation–which makes closure allocation ubiquitous. Empirical results strongly suggest that flat-closure memoization is an important optimization that significantly reduces running time as well as memory and closure allocation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Maintaining Separation of Concerns Through Task Oriented Software Development

This study, however, was performed using the imperative C language.

The use of bold type signals a reserved word.

Patterson, D.A., Hennessy, J.L.: Computer Organization and Design: The Hardware/Software Interface, 5th edn. Morgan Kaufmann Publishers Inc., San Francisco (2013)MATH

Wilson, P.R.: Uniprocessor garbage collection techniques. In: Bekkers, Y., Cohen, J. (eds.) IWMM 1992. LNCS, vol. 637, pp. 1–42. Springer, Heidelberg (1992). https://doi.org/10.1007/BFb0017182CrossRef

Serrano, M., Boehm, H.J.: Understanding memory allocation of scheme programs. In: Odersky, M., Wadler, P. (eds.) Proceedings of the Fifth International Conference on Functional Programming, pp. 245–256. ACM (2000)

Zorn, B.: The measured cost of conservative garbage collection. Softw. Pract. Exp. 23(7), 733–756 (1993)CrossRef

Henderson, P.: Functional Programming: Application and Implementation. Prentice-Hall International, Englewood (1980)MATH

Landin, P.J.: The mechanical evaluation of expressions. Comput. J. 6(4), 308–320 (1964)CrossRef

Kent Dybvig, R.: The development of Chez Scheme. In: Proceedings of the Eleventh ACM SIGPLAN International Conference on Functional Programming, pp. 1–12, September 2006

Cardelli, L.: Compiling a functional language. In: Proceedings of the 1984 ACM Conference on LISP and Functional Programming, pp. 208–217 (1984)

Shao, Z., Appel, A.W.: Space-efficient closure representations. Technical report CS-TR-454-94, Department of Computer Science, Princeton University, Princeton (1994)

10.

Shivers, O.: Control-flow analysis of higher-order languages of taming lambda. Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, May 1991

11.

Steele Jr., G.L.: Rabbit: a compiler for scheme. Technical report, Massachusetts Institute of Technology, Cambridge (1978)

12.

Adams, N., Kranz, D., Kelsey, R., Rees, J., Hudak, P., Philbin, J.: ORBIT: an optimizing compiler for scheme. In: Proceedings of the 1986 SIGPLAN Symposium on Compiler Construction, SIGPLAN 1986, pp. 219–233. ACM, New York (1986)

13.

Kelsey, R., Hudak, P.: Realistic compilation by program transformation (detailed summary). In: Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1989, pp. 281–292. ACM, New York (1989)

14.

Appel, A.W.: Compiling with Continuations. Cambridge University Press, New York (2007)

15.

Flanagan, C., Sabry, A., Duba, B.F., Felleisen, M.: The essence of compiling with continuations. In: Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, PLDI 1993, pp. 237–247. ACM, New York (1993)

16.

Flanagan, C., Sabry, A., Duba, B.F., Felleisen, M.: The essence of compiling with continuations. SIGPLAN Not. 39(4), 502–514 (2004)CrossRef

17.

Kennedy, A.: Compiling with continuations, continued. In: Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, pp. 177–190. ACM, New York (2007)

18.

Fluet, M., Weeks, S.: Contification using dominators. In: Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming, ICFP 2001, pp. 2–13. ACM, New York (2001)

19.

Acar, U.A., Blelloch, G.E., Harper, R.: Selective memoization. In: Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages, pp. 14–25. ACM Press (2003)

20.

Krishnamurthi, S.: Desugaring in practice: opportunities and challenges. In: Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation, PEPM 2015, pp. 1–2. ACM, New York (2015)

21.

Johnsson, T.: Lambda lifting: transforming programs to recursive equations. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 190–203. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-15975-4_37CrossRef

22.

Morazán, M.T., Schultz, U.P.: Optimal lambda lifting in quadratic time. In: Chitil, O., Horváth, Z., Zsók, V. (eds.) IFL 2007. LNCS, vol. 5083, pp. 37–56. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85373-2_3CrossRef

23.

Venit, S., Bishop, W.: Elementary Linear Algebra, 2nd edn. Prindle, Weber & Schmidt, Boston (1985)MATH

24.

Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation, 2nd edn. Prentice Hall PTR, Upper Saddle River (1997)

25.

Köbler, J., Schöning, U., Torán, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser Verlag, Basel (1993)CrossRef

26.

Morazán, M.T.: Bytecode and memoized closure performance. In: McCarthy, J. (ed.) TFP 2013. LNCS, vol. 8322, pp. 58–75. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-45340-3_4CrossRef

27.

Goldstein, D.L.: Richard P. Feynman, teacher. Phys. Today 42(2), 70–75 (1989)CrossRef

Title: Memoized Flat Closures for CPS
Authors: Marco T. Morazán
Lindsey M. Reams
Nicholas R. Olson
Shamil Dzhatdoyev
Publisher: Springer International Publishing
Book: Trends in Functional Programming
Print ISBN: 978-3-319-89718-9

Electronic ISBN: 978-3-319-89719-6

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-89719-6_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner