Pure functions in APL and J

ABSTRACT

Any expression in combinatory logic made up of combinators and variables can be abstracted into a pure combinator expression applied to a sequence of variables. Because there are great similarities between combinators and certain APL operators, a similar result obtains in many APL dialects. However, rewriting arbitrary APL expressions as pure functions requires new operators, not provided as primitives by any dialect. This paper defines functional completeness, gives a construction for achieving it, proves a conjecture of Kenneth Iverson that J is functionally complete, and shows how closely the major APL dialects have approached these conditions.

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: J. Philip Benkard, Nonce functions, ACM SIGAPL APL Quote Quad, v.20 n.4, p.27-39, July 1990
• 3: Edward Cherlin, APL trivia, ACM SIGAPL APL Quote Quad, v.20 n.4, p.71-75, July 1990
• 4: Alonzo Church, The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies), Princeton University Press, Princeton, NJ, 1985
• 5: Haskell B~ Curry and Richard Feys, Combinatory Logic, North-Holland, (1958).
• 6: Kurt G0del, "Uber formal unentscheidbare Satze der Principia Mathematica und verwandter S ysteme I", Monatshefte fiir Mathematik und Physik, Vol. 37, pp. 349-360, (1931). Translated into English as "On Formally Undecidable Propositions of the Principia Mathematica and Related Systems I", in Davis, The Undecidable, Raven Press, (1965).
• 7: A. Graham, APLO: a simple modern APL, ACM SIGAPL APL Quote Quad, v.19 n.4, p.178-183, Aug. 1989
• 8: Paul Hudak, Conception, evolution, and application of functional programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.359-411, Sep. 1989 [doi>10.1145/72551.72554]
• 9: Roger K. W. Hui , Kenneth E. Iverson , E. E. McDonnell , Arthur T. Whitney, APL\?, ACM SIGAPL APL Quote Quad, v.20 n.4, p.192-200, July 1990
• 10: international Standards Organisation, Programming Language APL, ISO standard 8485, (1989).
• 11: International Standards Organisation. Programming Language APL, Extended, Draft Proposal, Eugene McDonnell, Editor, (October 1990).
• 12: Kenneth E. Iverson, Operators, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.161-176, Oct. 1979 [doi>10.1145/357073.357074]
• 13: Kenneth E. Iverson, A dictionary of APL, ACM SIGAPL APL Quote Quad, v.18 n.1, p.5-40, September 1, 1987 [doi>10.1145/36983.36984]
• 14: E. E. McDonnell , K. E. Iverson, Phrasal forms, Conference proceedings on APL as a tool of thought, p.197-199, July 1989, New York City, New York, United States
• 15: Kenneth Iverson, personal communication, (1990).
• 16: A. A. Markov, "Teoria Algorifmov" (Theory of Algorithms), Trudy Mat. Inst. Steklov , 38, pp. 176-189.
• 17: Eugene McDonnell, The Four Cube Problem, APL Press, Weed, CA, (1981).
• 18: Eugene McDonnell, oral presentation, APL90, (Aug. 1990).
• 19: 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
• 20: Emil Post, "Formal Reduction of the General Combinatorial Decision Problem", American Journal of Mathematics, 65, pp. 197-215, (1943).
• 21: Reuter:file, Inc., SAX Language, Edition 1.2, (March 30, 1989).
• 22: M. SchOnfinkel, "f, Jber die Bausteine der mathematischen Logik", Mathematischen Annalen, 92, pp. 305--584, (1924).
• 23: Hai-Chen Tu, FAC: Functional Array Calculator and its Application to APL and Functional Programming, YALEU/DCS/TR-468, Yale University, New Haven, CT, (Apr. 1986).
• 24: Alan Turing, "On Computable Numbers with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 42, pp. 230-265, (1936).

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  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