Abstract
Compilers for polymorphic languages are required to treat values in programs in an abstract and generic way at the source level. The challenges of optimizing the boxing of raw values, flattening of argument tuples, and raising the arity of functions that handle complex structures to reduce memory usage are old ones, but take on newfound import with processors that have twice as many registers. We present a novel strategy that uses both control-flow and type information to provide an arity raising implementation addressing these problems. This strategy is conservative — no matter the execution path, the transformed program will not perform extra operations.
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
Tarditi, D., Diwan, A.: Measuring the cost of storage management. In: LASC, pp. 323–342 (1994)
Serrano, M.: Control flow analysis: a functional languages compilation paradigm. In: SAC 1995, pp. 118–122. ACM, New York (1995)
Fluet, M., Rainey, M., Reppy, J., Shaw, A., Xiao, Y.: Manticore: A heterogeneous parallel language. In: DAMP 2007, pp. 37–44. ACM, New York (January 2007)
Barnes, J., Hut, P.: A hierarchical o(n log n) force calculation algorithm. Nature 324, 446–449 (1986)
GHC: Barnes Hut benchmark written in Haskell, http://darcs.haskell.org/packages/ndp/examples/barnesHut/
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software 22(4), 469–483 (1996)
Nikhil, R.S.: ID Language Reference Manual. Laboratory for Computer Science. MIT, Cambridge (July 1991)
Leroy, X.: Unboxed objects and polymorphic typing. In: POPL 1992, pp. 177–188. ACM, New York (1992)
Peyton Jones, S.L., Launchbury, J.: Unboxed values as first class citizens in a non-strict functional language. In: Hughes, J. (ed.) FPCA 1991. LNCS, vol. 523, pp. 636–666. Springer, Heidelberg (1991)
Henglein, F., Jørgensen, J.: Formally optimal boxing. In: POPL 1994, pp. 213–226. ACM, New York (1994)
Thiemann, P.J.: Unboxed values and polymorphic typing revisited. In: FPCA 1995, pp. 24–35. ACM, New York (1995)
Goubault, J.: Generalized boxings, congruences and partial inlining. In: First International Static Analysis Symposium, Namur, Belgium (September 1994)
Serrano, M., Feeley, M.: Storage use analysis and its applications. In: ICFP 1996, pp. 50–61. ACM Press, New York (1996)
Faxén, K.F.: Representation analysis for coercion placement. In: Hermenegildo, M.V., Puebla, G. (eds.) SAS 2002. LNCS, vol. 2477, pp. 499–503. Springer, Heidelberg (2002)
Leroy, X.: The effectiveness of type-based unboxing. In: Workshop on Types in Compilation, Amsterdam. ACM SIGPLAN, Boston College Computer Science Dept. Technical Report BCCS-97-03 (June 1997)
Ashley, J.M., Dybvig, R.K.: A practical and flexible flow analysis for higher-order languages. ACM Trans. Program. Lang. Syst. 20(4), 845–868 (1998)
Tarditi, D., Morrisett, G., Cheng, P., Stone, C., Harper, R., Lee, P.: TIL: a type-directed optimizing compiler for ML. In: PLDI 1996, pp. 181–192. ACM, New York (1996)
Tarditi, D., Morrisett, G., Cheng, P., Stone, C., Harper, R., Lee, P.: TIL: a type-directed, optimizing compiler for ML. SIGPLAN Not. 39(4), 554–567 (2004)
Hannan, J., Hicks, P.: Higher-order arity raising. In: ICFP 1998, pp. 27–38. ACM, New York (1998)
Ziarek, L., Weeks, S., Jagannathan, S.: Flattening tuples in an SSA intermediate representation. Higher-Order and Symbolic Computation 21(3), 845–868 (2008)
Bolingbroke, M.C., Peyton Jones, S.L.: Types are calling conventions. In: HASKELL 2009, pp. 1–12. ACM, New York (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
Bergstrom, L., Reppy, J. (2010). Arity Raising in Manticore. 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_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-16478-1_6
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)