R.V. Dushkin1

1 National Research Nuclear University MEPhI (Moscow, Russia)

1 rvdushkin@mephi.ru

This paper presents a review and comparative analysis of methods of constructing terms in combinatory logic. The topic of combinatory logic is of great importance in theoretical computer science and mathematics. It is a section of mathematical logic that studies the structure of applicative objects used to represent the combinatory structure of formal systems. The paper presents a comprehensive review of existing methods for constructing terms in combinatory logic, indicating their strengths and weaknesses. The paper also presents a new approach to term construction, which proved to be more efficient and expressive than the existing methods – the axiomatic method. This work will be of interest to researchers and students in theoretical computer science, mathematics and logic. It will also be of interest to practitioners of programming languages who will find the results of this paper applicable to the design and implementation of programming languages. The paper possesses novelty in its comprehensive review of existing methods and proposing a new approach to the construction of combinatory terms. It is expected to make a significant contribution to the field of combinatory logic and to be a useful guide for researchers and practitioners in related fields.

Dushkin R.V. Review and comparative analysis of methods of constructing terms in combinatory logic. Information-measuring and Control Systems. 2024. V. 22. № 5. P. 31−38. DOI: https://doi.org/10.18127/j20700814-202405-04 (in Russian)

1. Volfengagen V.E. (2000) Kombinatornaya logika v programmirovanii. Vychisleniya s ob'ektami v primerakh i zadachakh. M.: Institut Aktualnogo Obrazovaniya "YurInfoR-MGU". 2000. 208 s. (in Russian)
2. Bimbo K. (2011) Combinatory Logic: Pure, Applied and Typed. NY: Chapman and Hall/CRC. Edition 1st. 2011. 357 p. DOI: 10.1201/b11046.
3. Garciadiego A.R. (2002) History of Mathematics, an Intuitive Approach. Humanistic Mathematics Network Journal. 2002. № 26. Article 5.
4. Charguéraud A. (2010) The Optimal Fixed Point Combinator. Interactive Theorem Proving (eds Kaufmann M., Paulson L.C.). ITP 2010. Lecture Notes in Computer Science. V. 6172. Springer, Berlin. Heidelberg. DOI: 10.1007/978-3-642-14052-5_15.
5. Barendregt H.P. (1984) The Lambda Calculus, Its Syntax and Semantics. Studies in Logic and the Foundations of Mathematics. 1984. V. 103. North Holland. ISBN 0-444-87508-5.
6. Curry H.B., Feys R. (1958) Combinatory Logic. Vol. I. Amsterdam: North Holland. 1958. ISBN 0-7204-2208-6.
7. Hindley J.R., Seldin J.P. (2008) λ-calculus and Combinators: An Introduction. Cambridge University Press. 2008.
8. Fokker J. (1992) The systematic construction of a one-combinator basis for Lambda-Terms. Formal Aspects of Computing 4 (Suppl. 1). 1992. 776−780. DOI: 10.1007/BF03180572.
9. Bunder M.W. (1988) Arithmetic based on the Church numerals in illative combinatory logic. Stud Logica. 1988. 47. 129−143. DOI: 10.1007/BF00370287.
10. Jansen J.M. (2013) Programming in the λ-Calculus: From Church to Scott and Back. The Beauty of Functional Code Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday (eds P. Achten, P. Koopman). Lecture Notes in Computer Science (Springer). 2013. V. 8106. P. 168−180. DOI: 10.1007/978-3-642-40355-2_12.