This article describes how array predicates were used to reduce the computational complexity of four APL primitive functions when one of their arguments is a permutation vector. The search primitives, indexof and set membership, and the sorting primitives, upgrade and downgrade, execute in linear time on such arguments. Our contribution, a method for static determination of array properties, lets us generate code that is optimized for special cases of primitives. Our approach eliminates runtime checks which would otherwise slow down the execution of all cases of the effected primitives. We use the same analysis technique to reduce the type complexity of certain array primitives.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Abr70	PHFclP ABRAMS. An {APL} Mach/r~ PhD thesis, Stanford University, 1970. SLAC Report No. 114.
	Ber73	ROBERT BERNECKY. "Speeding tip dyadic iota and dyadic epsilon'. In APL C~gress 73, pages 479--482. North-Holland Publishing Company, 1973. Second priming.
	Ber93	Robert Bernecky, Array morphology, ACM SIGAPL APL Quote Quad, v.24 n.1, p.6-16, Aug. 1993
	Ber97a	ROBERT BERNECKY. "APEX.. 77~ APL paralM exavaz~', Master's thesis, University of Toronto, 1997.
	Ber97b	ROBERT BERNECKY. "An ov.endav of the APEX a~er", Technical Report 305/97, Department of Computer Science, University of Toronto, 1997.
	Bud88	TIMOTHY BUDD. An APL Cor~. Springer- Verlag, 1988.
	GJ79	M~~I. R. G_aRE~ and DAVID S. JOHNSON. and Intr~ity: A Guide to the ~ of NP. ~s. W.H. Freeman, 1979.
	Ive73	EtuC B. IVI~RSON. "APL/4004 implementation". In APL Congress 73, pages 231--236. North-Holland Publishing Company, 1973.
	Jor79	Kevin E. Jordan, Is APL really processing arrays?, ACM SIGAPL APL Quote Quad, v.10 n.1, September 1979  [doi>10.1145/602312.602314]
	Wie86	Clark Wiedmann, Field results with the APL compiler, ACM SIGAPL APL Quote Quad, v.16 n.4, p.187-196, 1986
	Wil91	R. G. Willhoft, Parallel expression in the APL2 language, IBM Systems Journal, v.30 n.4, p.498-512, 1991

• International Conference on APL
  Proceedings of the APL98 conference on Array processing language
  
  1998 , Rome, Italy