Compiling APL for parallel and vector execution

ABSTRACT

The inherent parallelism of applicative languages such as APL and functional languages such as FP present a little-exploited and somewhat unorthodox means of parallel programming. Here we summarize our investigation of a new approach to compiling such programs for execution on various types of parallel hardware. Our method centers around an intermediate form that is an extension of the lambda calculus. We present evidence that APL programs are easily translated into this intermediate form, and that this intermediate representation lends itself readily to code generation for a variety of parallel hardware.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: 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
• 3: Alan J. Perlis , Spencer Rugaber, Programming with idioms in APL, ACM SIGAPL APL Quote Quad, v.9 n.4, p.232-235, June 1979
• 4: H. P. Barendregt. The Lambda Calculus. North- Holland, (1984).
• 5: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 6: Antoni Diller, Compiling functional languages, John Wiley & Sons, Inc., New York, NY, 1988
• 7: D. S. Friedman and D. S. Wise. CONS should not evaluate its arguments. In S. Michaelson and R. Milner, editors, Automata, Languages, and Programming: Third Iniernatzonal Colloquium, pages 257-284. (1976).
• 8: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 9: Budd Timothy A., A New Approach to Vector Code Generation for Applicative Languages, Oregon State University, Corvallis, OR, 1988
• 10: Budd Timothy A., A Parallel Intermediate Representation based on Lambda Expressions, Oregon State University, Corvallis, OR, 1989
• 11: Budd Timothy A., Composition and Compilation in Functional Programming Languages, Oregon State University, Corvallis, OR, 1988
• 12: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 13: Anita Osterhaug, Guide to parallel programming on Sequent computer systems: 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 14: Edsger W. Dijkstra, The humble programmer, Communications of the ACM, v.15 n.10, p.859-866, Oct. 1972 [doi>10.1145/355604.361591]

INDEX TERMS

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

          Nouns: APL

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Algorithms, Languages