Idiom matching: an optimization technique for an APL compiler

This thesis describes the design of an idiom matching technique in a compiler for APL. Idioms are programming language constructs used by programmers for the logical primitive operations for which no language primitives exist. Due to APL\u27s richness of operators, idioms tend to appear at the expression level. APL users have to pay a very high price to execute their APL programs with operator-by-operator execution in conventional translators. However, each idiom can be treated as a unit. It has been shown (2) that the saving from optimizing such idioms can be very impressive. Other researchers (1,3) have collected lists of idioms for APL;Idiom matching consists of two problems, recognition and selection, which are dealt with in this work. The idiom recognition problem is solved by a finite tree automaton. This approach constructs an automaton directly from a regular tree expression for a set of idioms. A practical automaton minimization algorithm is developed that obtains a time bound of O(n(\u272)(.)log n) for any binary tree automaton with n states. The selection problem, locating the best non-overlapping idioms in an expression tree, is solved in O(n) time;1. Brown, W. E. Toward an Optimizing Compiler for a Very HighLevel Language. Ph.D. dissertation, Iowa State University, 1979;2. Miller, T. C. Tentative Compilation: A Design for an APLCompiler. Ph.D. dissertation, Yale University, 1978;3. Perlis, A. J. and Rugaber, S. The APL Idiom List. ResearchReport #87, Department of Computer Science, Yale University,April, 1977