Abstract
Performance of generic array programs crucially relies on program specialisation wrt. shape information. Traditionally, this is done in a rather ad hoc fashion by propagating all shape information that is available. When striving for a compositional programming style that adheres to good software engineering principles this approach turns out to be insufficient. Instead, static value information needs to be propagated as well which introduces all the well known problems of partial evaluation in general.
In this paper, we propose a static analysis that identifies to what extent specialisation needs to be employed in order to achieve a certain level of shape information. This narrows the scope of specialisation far enough to make specialisation for shape information feasible despite a compositional programming style. Some examples to this effect are presented.
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
Alimarine, A.: Generic Functional Programming. PhD thesis, Radboud University of Nijmegen, Netherlands (2005)
Alimarine, A., Smetsers, S.: Optimizing generic functions. In: Kozen, D. (ed.) MPC 2004. LNCS, vol. 3125, pp. 16–31. Springer, Heidelberg (2004)
Cann, D.C.: Compilation Techniques for High Performance Applicative Computation. Technical Report CS-89-108, Lawrence Livermore National Laboratory, LLNL, Livermore California (1989)
Clarke, D., Hinze, R., Jeuring, J., Löh, A., de Witt, J.: The Generic Haskell User’s Guide (2001)
Grelck, C., Scholz, S.B.: Accelerating APL Programs with SAC. SIGAPL Quote Quad 29(2), 50–58 (1999)
Grelck, C., Trojahner, K.: Implicit Memory Management for SaC. In: Grelck, C., Huch, F., Michaelson, G.J., Trinder, P. (eds.) IFL 2004. LNCS, vol. 3474, pp. 335–348. Springer, Heidelberg (2005)
Hinze, R., Peyton Jones, S.: Derivable type classes. In: Hutton, G. (ed.) Proceedings of the 4th Haskell Workshop (2000)
Hui, R.: Rank and Uniformity. APL Quote Quad 25(4), 83–90 (1995)
Jones, N.D., Gomard, C.K., Sestoft, P.: Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs (1993)
Jay, C.B., Moggi, E., Bellè, G.: Functors, Types and Shapes. In: Backhouse, R., Sheard, T. (eds.) Workshop on Generic Programming: Marstrand, Sweden, Chalmers University of Technology, June 18, 1998, pp. 21–24 (1998)
Jones, N.D.: An Introduction to Partial Evaluation. ACM Computing Surveys 28(3) (1996)
Jay, C.B., Steckler, P.A.: The functional imperative: Shape! In: Hankin, C. (ed.) ESOP 1998. LNCS, vol. 1381, pp. 139–153. Springer, Heidelberg (1998)
Kreye, D.J.: A Compiler Backend for Generic Programming with Arrays. PhD thesis, Institut für Informatik und Praktische Mathematik, Universität Kiel (2003)
Lewis, E.C., Lin, C., Snyder, L.: The Implementation and Evaluation of Fusion and Contraction in Array Languages. In: Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation. ACM, New York (1998)
Pierce, B.C.: Types and Programming Languages. MIT Press, Cambridge (2002)
Scholz, S.-B.: Single Assignment C — efficient support for high-level array operations in a functional setting. Journal of Functional Programming 13(6), 1005–1059 (2003)
Veldhuizen, T.L.: Arrays in blitz++. In: Caromel, D., Oldehoeft, R.R., Tholburn, M. (eds.) ISCOPE 1998. LNCS, vol. 1505, pp. 223–230. Springer, Heidelberg (1998)
Veldhuizen, T.L.: C++ Templates as Partial Evaluation. In: Danvy, O. (ed.) Proceedings of PEPM 1999, The ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, University of Aarhus, Dept. of Computer Science, pp. 13–18 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grelck, C., Scholz, SB., Shafarenko, A. (2006). A Binding Scope Analysis for Generic Programs on Arrays. In: Butterfield, A., Grelck, C., Huch, F. (eds) Implementation and Application of Functional Languages. IFL 2005. Lecture Notes in Computer Science, vol 4015. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11964681_13
Download citation
DOI: https://doi.org/10.1007/11964681_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69174-7
Online ISBN: 978-3-540-69175-4
eBook Packages: Computer ScienceComputer Science (R0)