A language for computational algebra

ABSTRACT

This paper reports ongoing research at the IBM Research Center on the development of a language with extensible parameterized types and generic operators for computational algebra. The language provides an abstract data type mechanism for defining algorithms which work in as general a setting as possible. The language is based on the notions of domains and categories. Domains represent algebraic structures. Categories designate collections of domains having common operations with stated mathematical properties. Domains and categories are computed objects which may be dynamically assigned to variables, passed as arguments, and returned by functions. Although the language has been carefully tailored for the application of algebraic computation, it actually provides a very general abstract data type mechanism. Our notion of a category to group domains with common properties appears novel among programming languages (cf. image functor of RUSSELL) and leads to a very powerful notion of abstract algorithms missing from other work on data types known to the authors.

REFERENCES

• 1: Reference Manual for the Ada Programming Language, U.S. Dept. of Defense, July 1980, (reprinted November 1980).
• 2: James W. Thatcher , Eric G. Wagner , Jesse B. Wright, Data type specification: Parameterization and the power of specification techniques, Proceedings of the tenth annual ACM symposium on Theory of computing, p.119-132, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804340]
• 3: Burstall, R. M. and Goguen, J. A., "Putting Theories Together to Make Specifications", Proceedings of the 5th International Joint Conference on Artificial Intelligence, pp. 1045-1056, August, 1977.
• 4: Giorgio Ausiello , Giovanni Mascari, Design of algebraic data structures with the approach of abstract data types, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.514-530, June 01, 1979
• 5: Cohn, P. M., Universal Algebra, Harper and Row, New York, 1965
• 6: Davenport, J. H. and Jenks, R. D., "SCRATCHPAD/370: Modes and Domains" (privately circulated).
• 7: James H. Davenport , Richard D. Jenks, MODLISP, Proceedings of the 1980 ACM conference on LISP and functional programming, p.65-74, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802791]
• 8: Demers, A., and Donahue, J., Revised Report on Russell, TR 79-389 Dept. of Computer Science, Cornell U., September 1979.
• 9: Martin L. Griss, The definition and use of data structures in REDUCE, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.53-59, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806323]
• 10: R. D. Jenks, The SCRATCHPAD language, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.101-111, March 28-29, 1974, Santa Monica, California, United States
• 11: Richard D. Jenks, MODLISP -- an introduction (invited), Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.466-480, June 01, 1979
• 12: B Liskov , E Moss , A Snyder , R Atkinson , J C. Schaffert , T Bloom , R Scheifler, CLU reference manual, Springer-Verlag New York, Inc., New York, NY, 1984
• 13: Ruediger G. K. Loos, Toward a formal implementation of computer algebra, ACM SIGSAM Bulletin, v.8 n.3, p.9-16, August 1974 [doi>10.1145/1086837.1086839]
• 14: Wulf, W.A., London, R.L., and Shaw, M., "An introduction to the construction and verification of Alphard programs", IEEE Trans. on Software Eng. SE-2,4, pp. 253-265, Dec. 1976.
• 15: Ben Wegbreit, The treatment of data types in EL1, Communications of the ACM, v.17 n.5, p.251-264, May 1974 [doi>10.1145/360980.360992]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Languages, Theory