chased@rbbb.Eng.Sun.COM (David Chase) (03/02/91)
thomson@hub.toronto.edu (Brian Thomson) writes: >I seem to remember running across a reference, about 10 years ago >(that's when I saw it, not necessarily when it was published), >that dealt with recognizing common sequences of operations in APL >and compiling them into particularly efficient code. >I think they called it "recognition of programming idioms" or something >of the sort. Does this ring a bell with anyone? Ding. AUTHOR = "Feng Cheng and Scott Omdahl and George Strawn", TITLE = "Idiom matching: An optimization technique for an {APL} compiler", INSTITUTION = "Iowa State University", YEAR = 1982 (good luck getting a copy) The used 50 idioms, derived from work by (1) Perlis and Rugaber, (2) Brown, and (3) Miller. I was under the impression that these idioms covered a large portion (90-95%?) of most programs written in APL, but I couldn't find that in a quick scan of the tech report. Cheng et al give an example of an idiom that could be compiled to run 50 times faster, if recognized. The difficulty in their work is the time and space needed to construct and compress the bottom-up matching tables. Since 1982, there has been nice progress made in that area, and instead of taking 1000 seconds on a "NAS AS/6" (an IBM-clone mainframe) they can be computed in about 4 seconds on a Sun 3, or about .3 second a Sparcstation 2. For APL, this may now be irrelevant -- I don't know much about other improvements in APL implementation. For pattern matching, Cai, Paige & Tarjan have come up with even further more improvements to speed up the algorithm (n.b. I don't know if they handle "regular" tree patterns yet). Note that this belongs comp.lang.misc, and followups will go there. David Chase Sun