Operators and algebraic structures

ABSTRACT

Operators in functional languages such as APL and FFP are a useful programming concept. However, this concept cannot be fully exploited in these languages because of certain constraints. It is proposed that an operator should be associated with a structure having the algebraic properties on which the operator's behavior depends. This is illustrated by introducing a language that provides mechanisms for defining structures and operators on them. Using this language, it is possible to describe algorithms abstractly, thus emphasizing the algebraic properties on which the algorithms depend. The role that formal representation of mathematical knowledge can play in the development of programs is illustrated through an example. An approach for associating complexity measures with a structure and operators is also suggested. This approach is useful in analyzing the complexity of algorithms in an abstract setting.

REFERENCES

• 1: Bourbaki, N., Theory of Sets, Chapter IV, "Structures" and Summary of Results, Section 8, "Scales of Sets. Structures," Addison-Wesley, 1968.
• 2: 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]
• 3: Burstall, R.M., Goguen, J.A., "Putting Theories Together to Make Specifications," Fifth International Joint Conference on Artificial Intelligence, Cambridge, MA, August 1977.
• 4: Falkoff, A.D. and Orth, D.L., "Development of an APL Standard," RC 7542, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, February 1979.
• 5: Goguen, J.A., Thatcher, J.W., Wagner, E.W., "Initial Algebra Approach to the Specification, Correctness, and Implementation of Abstract Data Types" in Current Trends in Programming Methodology, Vol. IV, Data Structuring (R.T. Yeh, ed.), Prentice Hall, Englewood Cliffs, NJ, 1978.
• 6: John Guttag, Abstract data types and the development of data structures, Communications of the ACM, v.20 n.6, p.396-404, June 1977 [doi>10.1145/359605.359618]
• 7: 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]
• 8: Richard D. Jenks , Barry M. Trager, A language for computational algebra, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.6-13, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806363]
• 9: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 10: Musser, D.R., "Abstract Data Types in the AFFIRM System," IEEE TSE 1(6), January 1980.
• 11: Nakajima, R., Nakahara, H., Honda, M., "Hierarchical Program Specification and Verification - A Many Sorted Logical Approach," preprint RIMS 256, November 1978.
• 12: Winkler, F., "A Language for Specifying Algebraic Structures," unpublished manuscript, Fall 1979.
• 13: Zilles, S.N., "An Introduction to Data Algebra," Draft Working Paper, IBM San Jose Research Laboratory, September 1975.
• 14: Zippel, R., private communication, March 1981.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Algebraic approaches to semantics

General Terms:
Algorithms, Languages, Performance, Theory