Correctly detecting intrinsic type errors in typeless languages such as MATLAB

ABSTRACT

Among the main impediments that languages such as MATLAB and APL present to a compiler is the lack of an explicit declaration for a variable's type, The determination of this important attribute could allow a compiler to generate more efficient code, and is a problem that has been extensively studied in the past. This paper revisits this problem but unlike prior efforts, the objective is a uniform approach to type estimation that also accommodates type incorrect programs in a way that facilitates stronger type error detection through the exact localization of the type error at run time. We also show how our methodology makes it possible to further reduce the run-time overhead due to type conformability checking. The techniques are clearly demonstrated by applying them to deduce the intrinsic types of program variables in the MATLAB language.

REFERENCES

• 1: A. M. Bauer and H. J. Saal. "Does APL Really Need Run-Time Checking?". Software---Practice and Experience, 4:129-138, 1974.
• 2: P. Banerjee, U. N. Shenoy, A. Choudhary, S. Hauck, C. Bachmann, M. Chang, M. Haldar, P. G. Joisha, A. Jones, A. Kanhere, A. Nayak, S. Periyacheri, and M. Walkden. "A MATLAB Compiler for Configurable Computing Systems". Technical Report CPDC--TR--9906--013, Center for Parallel and Distributed Computing, Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208--3118, USA, September 1999.
• 3: Timothy Budd, An APL compiler, Springer-Verlag New York, Inc., New York, NY, 1988
• 4: Stéphane Chauveau , François Bodin, Menhir: An Environment for High Performance Matlab, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.27-40, May 28-30, 1998
• 5: W-M Ching, Program analysis and code generation in an APL/370 compiler, IBM Journal of Research and Development, v.30 n.6, p.594-602, Nov. 1986
• 6: Luiz Antonio De Rose , David Padua, Compiler techniques for matlab programs, 1996
• 7: http://www.csrd.uiuc.edu/falcon/falcon.html, The FALCON Project Home Page.
• 8: P. G. Joisha, U. N. Shenoy, and P. Banerjee. ".An Approach to Array Shape Determination in MATLAB". Technical Report CPDC--TR--2000--10--010, Center for Parallel and Distributed Computing, Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208--3118, USA, October 2000.
• 9: Marc A. Kaplan , Jeffrey D. Ullman, A Scheme for the Automatic Inference of Variable Types, Journal of the ACM (JACM), v.27 n.1, p.128-145, Jan. 1980 [doi>10.1145/322169.322181]
• 10: The MathWorks, Inc., 24 Prime Park Way, Natick, MA 01760--1500, USA. MATLAB---The Language of Technical Computing, January 1997. Using MATLAB (Version 5).
• 11: The MathWorks, Inc., 3 Apple Hill Drive, Natick, MA 01760--2098, USA. Image Processing Toolbox: For Use with MATLAB, September 2000. User's Guide (Version 2).
• 12: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 13: Results from a Parallel MATLAB Compiler, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.81, March 30-April 03, 1998
• 14: Aaron Melvin Tenenbaum, Type determination for very high level languages., 1974
• 15: Jean Paul Tremblay , R. Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw-Hill, Inc., New York, NY, 1975

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

      Nouns: MATLAB

General Terms:
Algorithms, Languages