Р.В. Душкин1

1Национальный исследовательский ядерный университет «МИФИ» (Москва, Россия)

1rvdushkin@mephi.ru

Постановка проблемы. Тема комбинаторной логики имеет большое значение в теоретической информатике и математике. Это раздел математической логики, изучающий структуру аппликативных объектов, используемых для представления комбинаторной структуры формальных систем. Комбинаторная логика имеет важные приложения в теоретической информатике, математике и языках программирования

Цель. Провести всесторонний обзор и сравнительный анализ существующих методов конструирования определений аппликативных объектов в комбинаторной логике.

Результаты. Проведен всесторонний обзор существующих методов построения термов в комбинаторной логике с указанием их сильных и слабых сторон. Предложен новый подход к построению терминов, который оказался более эффективным и выразительным, чем существующие методы – аксиоматический метод.

Практическая значимость. Работа будет интересна исследователям и студентам в области теоретической информатики, математики и логики, а также специалистам-практикам в области языков программирования, которые сочтут результаты этой статьи применимыми к разработке и реализации языков программирования. Статья обладает новизной в своем всестороннем обзоре существующих методов и предложении нового подхода к построению комбинаторных термов.

Душкин Р.В. Обзор и сравнительный анализ методов конструирования термов в комбинаторной логике // Информационно-измерительные и управляющие системы. 2024. Т. 22. № 5. С. 31−38. DOI: https://doi.org/10.18127/j20700814-202405-04

1. Вольфенгаген В.Э. (2000) Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. М.: Институт Актуального Образования «ЮрИнфоР-МГУ». 2000. 208 с.
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.