skip to main content
article
Open access

An algebraic array shape inference system for MATLAB®

Published: 01 September 2006 Publication History

Abstract

The problem of inferring array shapes ahead of time in languages that exhibit both implicit and dynamic typing is a critical one because the ramifications of its solution are the better organization of array storage through compaction and reuse, and the generation of high-performance code through specialization by shape. This article addresses the problem in a prototypical implicitly and dynamically typed array language called MATLAB. The approach involves modeling the language's shape semantics using an algebraic system, and applying term rewriting techniques to evaluate expressions under this algebra. Unlike prior efforts at array shape determination, this enables the deduction of valuable shape information even when array extents are compile-time unknowns. Furthermore, unlike some previous methods, our approach doesn't impose monotonicity requirements on an operator's shape semantics. The work also describes an inference methodology and reports measurements from a type inference engine called MAGICA. In a benchmark suite of 17 programs, the shape inference subsystem in MAGICA detected the equivalence of over 61% of the symbolic shapes in six programs, and over 57% and 37% of the symbolic shapes in two others. In the remaining nine programs, all array shapes were inferred to be compile-time constants.

References

[1]
Adams, J. C., Brainerd, W. S., Martin, J. T., Smith, B. T., and Wagener, J. L. 1992. FORTRAN 90 Handbook. McGraw-Hill, New York.]]
[2]
Almási, G. 2001. MaJIC: A MATLAB Just-In-Time Compiler. Ph.D. thesis, University of Illinois at Urbana-Champaign.]]
[3]
Almási, G. and Padua, D. A. 2002. MAJIC: Compiling MATLAB for speed and responsiveness. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 294--303.]]
[4]
Ancourt, C. and Nguyen, T. V. N. 2001. Array resizing for scientific code debugging, maintenance and reuse. In Proceedings of the ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. ACM, New York, 32--37.]]
[5]
Banerjee, U. 1993. Loop Transformations for Restructuring Compilers: The Foundations. Kluwer Academic, Norwell, MA.]]
[6]
Budd, T. 1988. An APL Compiler. Springer Verlag, New York City.]]
[7]
Chauveau, S. and Bodin, F. 1998. Menhir: An Environment for high performance MATLAB. In Proceedings of the 4th International Workshop on Languages, Compilers, and Runtime Systems. LNCS, vol. 1511. Springer Verlag, 27--40.]]
[8]
Ching, W.-M. 1986. Program analysis and code generation in an APL/370 compiler. IBM J. Res. Dev. 30, 6 (Nov.), 594--602.]]
[9]
Cytron, R., Ferrante, J., Rosen, B. K., and Wegman, M. N. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst. 13, 4 (Oct.), 451--490.]]
[10]
De Rose, L. A. 1996. Compiler techniques for MATLAB programs. Ph.D. thesis, University of Illinois at Urbana-Champaign.]]
[11]
De Rose, L. A. and Padua, D. A. 1999. Techniques for the translation of MATLAB programs into FORTRAN 90. ACM Trans. Program. Lang. Syst. 21, 2 (Mar.), 286--323.]]
[12]
Dershowitz, N. and Plaisted, D. A. 2001. Rewriting. In Handbook of Automated Reasoning, A. Robinson and A. Voronkov, eds. vol. 1. Elsevier, Amsterdam, The Netherlands.]]
[13]
Gupta, R. 1993. Optimizing array bounds checks using flow analysis. ACM Lett. Program. Lang. Syst. 2, 1--4, 135--150.]]
[14]
Hindley, J. R. 1969. The principal type-scheme of an object in combinatory logic. Trans. American Math. Society 146, 29--60.]]
[15]
Jay, B. C. and Steckler, P. A. 1998. The functional imperative: Shape! In Proceedings of the 7th European Symposium On Programming. LNCS, vol. 1381. Springer Verlag, 139--153.]]
[16]
Joisha, P. G. 2003. A type inference system for MATLAB with applications to code optimization. Ph.D. thesis, Northwestern University.]]
[17]
Joisha, P. G. and Banerjee, P. 2001a. Computing array shapes in MATLAB. In Proceedings of the 14th International Workshop on Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science, vol. 2624. Springer Verlag.]]
[18]
Joisha, P. G. and Banerjee, P. 2001b. Correctly detecting intrinsic type errors in typeless languages such as MATLAB. In Proceedings of the ACM SIGAPL Conference on Array Processing Languages. ACM, New York, 6--21.]]
[19]
Joisha, P. G. and Banerjee, P. 2002. Implementing an array shape inference system for MATLAB using Mathematica. Tech. Rep. CPDC--TR--2002--10--003, Northwestern University.]]
[20]
Joisha, P. G. and Banerjee, P. 2003a. Static array storage optimization in MATLAB. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 294--303.]]
[21]
Joisha, P. G. and Banerjee, P. 2003b. The MAGICA type inference engine for MATLAB. In Proceedings of the 12th International Conference on Compiler Construction. Lecture Notes in Computer Science, vol. 2622. Springer Verlag, 121--125.]]
[22]
Joisha, P. G., Shenoy, U. N., and Banerjee, P. 2000. An approach to array shape determination in MATLAB. Tech. Rep. CPDC--TR--2000--10--010, Northwestern University.]]
[23]
Kaplan, M. A. and Ullman, J. D. 1978. A general scheme for the automatic inference of variable types. In Proceedings of the 5th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, 60--75.]]
[24]
Knight, K. 1989. Unification: A multidisciplinary survey. ACM Comput. Surv. 21, 1, 93--124.]]
[25]
Malishevsky, A. 1998. Implementing a runtime library for a parallel MATLAB compiler. M.S. thesis, Oregon State University.]]
[26]
McCosh, C. 2003. Type-Based specialization in a telescoping compiler for MATLAB. Tech. Rep. TR03--412, Rice University.]]
[27]
Milner, R. 1978. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 3 (Dec.), 348--375.]]
[28]
Mitchell, J. C. 1996. Foundations for Programming Languages. The MIT Press, Cambridge, MA.]]
[29]
Muchnick, S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA.]]
[30]
Quinn, M. J., Malishevsky, A., Seelam, N., and Zhao, Y. 1998. Preliminary results from a parallel MATLAB compiler. In Proceedings of the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, S. Sahni, Ed. IEEE Computer Society Press, 81--87.]]
[31]
Robinson, J. A. 1965. A machine-oriented logic based on the resolution principle. J. Association Comput. Mach. 12, 1 (Jan.), 23--41.]]
[32]
Tenenbaum, A. M. 1974. Type determination in very high-level languages. Ph.D. thesis, Rep. NSO-3, New York University.]]
[33]
The MathWorks, Inc. 1997. MATLAB: The Language of Technical Computing. The MathWorks, Inc. Using MATLAB (Version 5).]]
[34]
The MathWorks, Inc. 2002a. Accelerating MATLAB: The MATLAB JIT-Accelerator. At http://www.mathworks.com/company/newsletters/digest/sept02/accel_matlab.pdf.]]
[35]
The MathWorks, Inc. 2002b. The MathWorks announces release 13 with major new versions of MATLAB and Simulink. At http://www.mathworks.com/company/pressroom/index.shtml/article/332.]]
[36]
Tremblay, J. P. and Manohar, R. 1975. Discrete Mathematical Structures with Applications to Computer Science. Computer Science Series. McGraw-Hill, New York.]]
[37]
Walther, C. 1988. Many-Sorted unification. J. Assoc. Comput. Mach. 35, 1, 1--17.]]
[38]
Weisstein, E. W. 2005. Hilbert matrix; From MathWorld---A Wolfram web resource. At http://mathworld.wolfram.com/HilbertMatrix.html.]]
[39]
Wiedmann, C. 1979. Steps toward an APL compiler. In Proceedings of the ACM SIGAPL Conference on Array Processing Languages, A. Anger, Ed. ACM, New York, 321--328.]]
[40]
Wolfram, S. 1999. The Mathematica Book, 4th ed. Wolfram Media, Champaign, IL.]]
[41]
Xi, H. and Pfenning, F. 1998. Eliminating array bound checking through dependent types. In Proceedings of the ACM SIGPLAN Conference on Programming Language, Design, and Implementation. ACM, New York, 249--257.]]

Cited By

View all
  • (2024)CoolerSpace: A Language for Physically Correct and Computationally Efficient Color ProgrammingProceedings of the ACM on Programming Languages10.1145/36897418:OOPSLA2(846-875)Online publication date: 8-Oct-2024
  • (2018)Profile-based vectorization for MATLABProceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3219753.3219756(18-23)Online publication date: 19-Jun-2018
  • (2017)A MATLAB subset to C compiler targeting embedded systemsSoftware—Practice & Experience10.1002/spe.240847:2(249-272)Online publication date: 1-Feb-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems
ACM Transactions on Programming Languages and Systems  Volume 28, Issue 5
September 2006
171 pages
ISSN:0164-0925
EISSN:1558-4593
DOI:10.1145/1152649
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2006
Published in TOPLAS Volume 28, Issue 5

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Typeless array languages
  2. shape algebras
  3. term rewriting

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)84
  • Downloads (Last 6 weeks)14
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)CoolerSpace: A Language for Physically Correct and Computationally Efficient Color ProgrammingProceedings of the ACM on Programming Languages10.1145/36897418:OOPSLA2(846-875)Online publication date: 8-Oct-2024
  • (2018)Profile-based vectorization for MATLABProceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3219753.3219756(18-23)Online publication date: 19-Jun-2018
  • (2017)A MATLAB subset to C compiler targeting embedded systemsSoftware—Practice & Experience10.1002/spe.240847:2(249-272)Online publication date: 1-Feb-2017
  • (2016)Contract-based verification of MATLAB-style matrix programsFormal Aspects of Computing10.1007/s00165-015-0353-z28:1(79-107)Online publication date: 1-Mar-2016
  • (2015)Type inference for array programming with dimensioned vector spacesProceedings of the 27th Symposium on the Implementation and Application of Functional Programming Languages10.1145/2897336.2897341(1-12)Online publication date: 14-Sep-2015
  • (2015)Techniques for efficient MATLAB-to-C compilationProceedings of the 2nd ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/2774959.2774961(7-12)Online publication date: 13-Jun-2015
  • (2015)C and OpenCL generation from MATLABProceedings of the 30th Annual ACM Symposium on Applied Computing10.1145/2695664.2695911(1315-1320)Online publication date: 13-Apr-2015
  • (2014)Multi-Target C Code Generation from MATLABProceedings of ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/2627373.2627389(95-100)Online publication date: 9-Jun-2014
  • (2014)Array Operators Using Multiple DispatchProceedings of ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/2627373.2627383(56-61)Online publication date: 9-Jun-2014
  • (2014)Just-in-time shape inference for array-based languagesProceedings of ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/2627373.2627382(50-55)Online publication date: 9-Jun-2014
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media