Recursive data structures in APL

ABSTRACT

A mathematical study of three approaches for defining nested arrays in APL is presented. Theorems exhibiting the relationships between the definitional systems are given and illustrated through graph representations. One of the approaches is used to define an APL array to be a recursive data structure equivalent to a tree structure in which all data is stored at the leaves as homogeneous arrays of numbers and characters. An extension of APL is proposed that includes new primitive functions to manipulate the nesting level of arrays and new operators to assist in the construction of data-driven algorithms.

REFERENCES

• 1: Philip S. Abrams, An interpreter for "Iverson notation", Stanford University, Stanford, CA, 1966
• 2: Philip S. Abrams, What's wrong with APL?, Proceedings of seventh international conference on APL, p.1-8, June 11-13, 1975, Pisa, Italy [doi>10.1145/800117.803777]
• 3: M. Alfonseca , M. L. Tavera, “Extension of APL to tree-structured information”, Proceedings of the eighth international conference on APL, p.1-23, September 22-24, 1976, Ottawa, Canada [doi>10.1145/800114.803655]
• 4: Braffort, P., and Michel, J. X\APL: An experimental extensible programming system. Tech. Rep., Mathrmatique, Universit6 Paris XI, Orsay, France, 1976.
• 5: Brown, J.A. A generalization of APE. Ph.D. Th., Dept. Syst. and Inform. Sci., Syracuse U., Syracuse, N.Y., 1971.
• 6: Edwards, E.M. Generalized arrays (lists) in APE. APL Congress 73, Copenhagen, Denmark, 1973, pp. 99-105.
• 7: Edwards, E.M. Private communication, 1976.
• 8: Falkoff, A.D., Iverson, K.E., and Sussenguth, E.H. A formal description of System 360. IBM Syst. J. 3 (1964), 198-263.
• 9: Falkoff, AD., and lverson, K.E. The design of APE. IBM J. Res. Develop. 17, 4 (1973), 324-334.
• 10: Ghandour, Z., and Mezei, J. Generalized arrays, operators and functions. IBM J. Res. Develop. 17, 4 (1973), 335-352.
• 11: Ziad Jamil Ghandour, A simple approach to the empty generalized APL arrays, Proceedings of the eighth international conference on APL, p.178-188, September 22-24, 1976, Ottawa, Canada [doi>10.1145/800114.803675]
• 12: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 13: W. E. Gull , M. A. Jenkins, Recursive data structures and related control mechanisms in APL, Proceedings of the eighth international conference on APL, p.201-210, September 22-24, 1976, Ottawa, Canada [doi>10.1145/800114.803678]
• 14: Haegi, H.R. Some questions and thoughts concerning arrays of arrays. Proc. SEAS-APL Working Committee, Jan. 1974.
• 15: Hans R. Haegi, The extension of APL to treelike data structures, ACM SIGAPL APL Quote Quad, v.7 n.2, Summer 1976 [doi>10.1145/585979.585982]
• 16: Hoare, C.A.R. Recursive data structures. Int. J. Comptrs. Syst. Sci. 4, 2 (1975), 105-132.
• 17: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 18: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 19: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 20: Mercer, R. Extensions of APL to include arrays of arrays: A comparison of three systems. Tech. Rep. Comptng. Ctr., U. of Mass., Amherst, Mass., 1976.
• 21: More, T. An extension of APL tO a theory of arrays. Abstract, 1968. Reprinted in Tech. Rep. 320-3016, IBM Scientific Ctr., Philadelphia, Pa., 1973.
• 22: More, T. An extension of APL to a theory of arrays. Class notes, Yale U., New Haven, Conn., 1970.
• 23: More, T. Axioms and theorems for a theory of arrays. IBM J. Res. Develop. 17, 3 (1973), 135-175.
• 24: More, T. Notes on the development of a theory of arrays. Tech. Rep. 320-3016, IBM Scientific Ctr., Philadelphia, Pa., 1973.
• 25: More, T. Notes on the axioms for a theory of arrays. Tech. Rep. 320-3017, IBM Scientific Ctr., Philadelphia, Pa., 1973.
• 26: More, T. A theory of arrays with applications to databases. Rep. G320-2106, IBM Scientific Ctr., Cambridge, Mass., 1975.
• 27: More, T. Types and prototypes in a theory of arrays. Rep. 320-2112, IBM Scientific Ctr., Cambridge, Mass., 1976.
• 28: More, T. On the composition of array-theoretic operations. Rep. 320-2113, IBM Scientific Ctr., Cambridge, Mass., 1976.
• 29: Murray, R.C. On tree structured extensions to the APL language. Proc. APL Congress 73, Copenhagen, Denmark, 1973, pp. 333-338.
• 30: Perlis, A.J. Steps towards an APL compiler--updated. Res. Rep. 24, Comptr. Sci. Dept. Yale U., New Haven, Conn., 1975.
• 31: Quine, W.V. Unification of universes in set theory. J. Symbolic Logic 21 (1956), 267-279.
• 32: Robichaud, L. Trees in APL. Presentation at Queen's APL Workshop, Queen's U., Kingston, Ontario, 1976.
• 33: Seeds, G. Private communication, 1976.
• 34: Smith, R.A. The semantics of split were suggested by Bob Smith at the Queen's APL Workshop, Queen's University, Kingston, Ontario, May 1976. One of the referees of the first draft made a similar suggestion.
• 35: Tennent, R.D. Language design methodologies based on semantic principles. Acta Informatica 8, (1977), 97-112.
• 36: Vasseur, J.P. Extensions of APL operators to tree-like data structures. Proc. APL Congress 73, Copenhagen, Denmark, 1973, pp. 457-464.
• 37: Wirth, N. On the design of programming languages. Inform. Processing 74, J.L. Rosenfeld, Ed., North-Holland Pub. Co., Amsterdam, 1974, pp. 386-393.

INDEX TERMS

Keywords:
APL arrays, data-driven algorithms, nested arrays, recursive data structures, theory of arrays, trees