Combinatory foundation of functional programming

ABSTRACT

A proposal is described for embedding FP and a part of FFP into a system C(IN)V of Combinatory Logic generated by the 6-tuple of combinators (A,B,C*,O,L,D) under the operation of application. At the same time C(IN)V is viewed as an algebraic extension of elementary arithmetic, including addition multiplication and exponentiation, leading to a non commutative semi-ring with an infinity of zero (infinite)-like elements. Two interesting submonoids have been selected: Lº able to represent the set of FP-Sequences and L+ able to represent the set of FP-Constructions. All basic objects forming operators like Composition, Apply To All Condition and Insert Right are then efficiently expressed inside C(IN)V. The same is done for some operators belonging to FFP as Lifting and the APPLY of LISP establishing a basis for a future reduction (operational) semantics of FP.

REFERENCES

• 1: Michael A. Arbib , Ernest G. Manes, The Pattern-of-Calls Expansion Is the Canonical Fixpoint for Recursive Definitions, Journal of the ACM (JACM), v.29 n.2, p.577-602, April 1982 [doi>10.1145/322307.322325]
• 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: John Backus, Function level programs as mathematical objects, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.1-10, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806757]
• 4: Böhm, C. (1979) Un modèle arithmétique des termes de la Logique Combinatoire in: Lambda calculet sémantique formelle des languages de Programmation, Actes de la Sixième Ecole de Printemps d'Informatique Theorique, La Châtre, 1978, ed. B. Robinet, LITP and ENSTA, Paris, pp. 97-108.
• 5: Böhm, C. (1980) An abstract approach to (hereditary) finite sequences of Combinators, in: To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pp. 231-242 J.P. Seldin & J.R.Hindley, Academic Press, London, etc.
• 6: Böhm, C. (1981) Logic and Computers: Combinatory Logic as Extension of Elementary Number Theory, in: Modern logic - a survey ed. E. Agazzi, Reidel, Dordrecht, pp. 297-309.
• 7: Böhm, C. and Dezani-Ciancaglini, M. (198@@@@) Combinatory Logic as Monoids (in preparation, announced 1977).
• 8: A. Chiarini, On FP languages combining forms, ACM SIGPLAN Notices, v.15 n.9, p.25-27, September 1980 [doi>10.1145/947706.947709]
• 9: Church, A. (1937) Combinatory logic as a semigroup (abstract), Bull. Amer. Math. Soc. 44, p. 333.
• 10: Curry, H.B., Feys, R. and Craig, W. (1958) Combinatory Logic. Volume I North Holland, Amsterdam, etc.
• 11: N. Islam , T. J. Myers , P. Broome, A simple optimizer for FP-like languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.33-40, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806760]
• 12: Robinson, R. (1947) Primitive recursive functions, Bull. Amer. Math. Soc., Vol. 53, pp. 925-942.
• 13: Scott, D. (1970) Outline of a mathematical theory of Computation, Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, Princeton, pp. 169-176.
• 14: Wadsworth, C. (1975) The relation between computational and denotational properties for Scott's D@@@@-models of the lambda-calculus, SIAM J. Comput. 5, pp. 488-521.
• 15: Williams, J. (1980) On the development of the algebra of functional programs, Report RJ2983, IBM Research Laboratory, San Jose, 24 pp.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

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

          Nouns: FP

General Terms:
Languages