Primitive Programing Algebra of Computable Functions at Records

Тарас Леонідович Захарченко, Дмитро Ігорович Редько, Ігор Володимирович Редько, Петро Олексійович Яганов


Background. The research is conducted in the context of compositional approach to programming. Problematic of the research is development of scientific foundations of programmer’s problems solution genesis. Its basis is concept of composition.

Objective. The objective of the research is general method development for function classes’ algebraic characteristics obtaining and application of the method for description of pragmatically important class of partially recursive functions on records.

Methods. Creations made in the paper are based on software analysis algebraic methods and compositional programming methodic. Problems of computable functions’ characteristics obtaining, problems of generative sets and bases finding, which are one of the most important questions in programmer’s problematic, are strictly stated and solved in the context of so called “program algebras”.

Results. In the paper method of mentioned problems solution was proposed in context of primitive program algebras (PPA) on different classes of computable functions. Received results are stated as sequence of original statements, lemmas, and theorems. They can be used for different classes of computable functions algebraic characteristics exploration in problems of programming languages semantics formalization.

Conclusions. Received results are foundations of adaptive programming environments development. Next steps in this direction will be connected with exploration of general concept of composition and development of related reduction methods of function exploration as environments of pragmatic depended programmer’s problems decomposition.


Fullness of calculable functions; Fullness problem in PPA; Complete system; Pairs of natural numbers; Pr-functions; Pr-predicates


E. Hehner, A Practical Theory of Programming.New York: Springer, 2012, 247 p.

B.E. Panchenko and V.N. Gajdabrus, “A relational framework and case shells of a new type”, Cybernetica i Sistemnyj Analiz, vol. 49, no. 3, pp. 475–486, 2013 (in Ukrainian).

D.J. Armstrong, “The quarks of object-oriented development”, Communications of the ACM, vol. 49, no. 2, pp. 123–128, 2006.

A.M. Grubiy, “Automaton implementations of the process of generating a Collatz sequence”, Cybernetica i Sistemnyj Analiz, vol. 48, no. 1, pp. 108–116, 2012, (in Ukrainian).

E. Dijkstra, A Discipline of Programming. Moscow, Russia: Mir, 1978, 275 p. (in Russian).

B. Stroustrup, Programming: Principles and Practice Using C++, 2nd ed. Moscow, Russia: Williams, 2011, p. 1248 (in Russian).

A. Tang et al., “What makes software design effective?”, Design Studies, vol. 31, no. 6, pp. 614–640, 2010.

D. Batory et al., “Dark knowledge and graph grammars in automated software design”, in Proc. 6th Int. Conf. Software Language Eng., Indianapolis, Oct. 26–28, 2013, vol. 8225, pp. 1–18.

N.S. Kovalenko et al., “Asynchronous distributed computations with a limited number of copies of a structured program resource”, Cybernetica i Sistemnyj Analiz, vol. 48, no. 1, pp. 86–98, 2012 (in Ukrainian).

F.P.Brooks, The Design of Design: Essays from a Computer Scientist. Moscow, Russia: Williams, 2012, 464 p. (in Russian).

I.A. Basarab et al., Compositional Databases. Kyiv, Ukraine: Lybid, 1992, 192 p. (in Russian).

V.N. Redko and I.V. Redko, “Existential foundations of the composition paradigm”, Cybernetica i Sistemnyj Analiz, vol. 44, no. 2, pp. 153–160, 2008 (in Russian).

D.B. Bui and I.V. Redko, “Primitive program algebras of functions, which preserve denotates”, Doklad AN USSR, no. 9, pp. 66–68, 1988 (in Russian).

Y.O. Bogatyryova, “Computability on finite sets and multi-sets”, Visnyk KNU im. Tarasa Shevchenka, no. 4, pp. 88–96, 2010 (in Ukrainian).

Y.O. Bogatyryova, “Concept of multi-set. Structure of multi-sets family”, in Proc 13th Academician M. Kravchuk Int. Sci. Conf, Kyiv, Ukraine, May 13–15, 2010, p. 60 (in Ukrainian).

A.I. Maltsev, Algorithms and Recursive Functions.Moscow,Russia: Nauka, 1965, 391 p. (in Russian).

A.I. Maltsev, Algorythmic Systems. Moscow, Russia: Nauka, 1970, 392 p. (in Russian).

A.I. Maltsev, “Constructive algebras. 1”, Uspekhi Mat. Nauk, no. 3, vol. 16, pp. 3–60, 1961 (in Russian).

A.V. Gorielov et al., “Compositional foundations of programming activity”, Visnyk KNUTD, no. 4, pp. 25–34, 2014 (in Russian).

GOST Style Citations

  1. Hehner E. A Practical Theory of Programming. – New York: Springer, 2012. – 247 p.

  2. Панченко Б.Є., Гайдабрус В.М. Реляційний каркас та модель CASE-оболонки нового // Кибернетика и системный анализ. – 2013. – № 3. – С. 172–186.

  3. Armstrong D.J. The quarks of object-oriented development // Communications of the ACM. – 2006. – 49, № 2. – P. 123–128.

  4. Грубій А.М. Автоматні реалізації процесу породження послідовності Коллаца // Кибернетика и системный анализ. – 2012. – № 1. – С. 129–138.

  5. Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978. – 275 с.

  6. Страуструп Б. Программирование: принципы и практика использования C++. – 2-е изд., испр. – М.: Вильямс, 2011. – С. 1248.

  7. What makes software design effective? / A. Tang, A. Aleti, J. Burge, H. Vliet // Design Studies. – 2010. –  31, № 6. – P. 614–640.

  8. Batory D., Gonçalves R., Marker B. Dark Knowledge and Graph Grammars in Automated Software Design // Software Language Eng.: Proc. 6th Int. Conf., October 26–28, 2013, Indianapolis, USA. – Springer Intl. Publishing, 2013. – 8225. – P. 1–18.

  9. Коваленко М.С, Павлов П.О., Овсєєць М.І. Асинхронні розподілені обчислення з обмеженною кількістю копій структурованого програмного ресурсу // Кибернетика и системный анализ. – 2012. – № 1. – С. 105–117.

  10. Брукс Ф.П. Проектирование процесса проектирования: записки компьютерного эксперта. – М.: Вильямс, 2012. – 464 с.

  11. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы даннях. – К.: Либідь, 1992. – 192 с.

  12. Редько В.Н., Редько И.В. Экзистенциальные основания композиционной парадигмы // Кибернетика и системный анализ. – 2008. – № 2.– С. 3–12.

  13. Буй Д.Б., Редько И.В. Примитивные программные алгебры функций, сохраняющих денотаты // Докл. АН УССР. – 1988. – № 9. – С. 66–68.

  14. Богатирьова Ю.О. Обчислюваність на скінченних множинах та мультимножинах // Вісник КНУ ім. Т. Шевченка. Сер. Фіз.-мат. науки. – 2010. – № 4. – С. 88–96.

  15. Богатирьова Ю.О. Поняття мультимножини. Структура сімейства мультимножин // Матер. ХІІІ Міжнар. наукової конф. ім. акад. М. Кравчука, 13–15 травня 2010 р., Київ. – К.: НТУ “КПІ”, 2009. – C. 60.

  16. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 391 с.

  17. Мальцев А.И. Алгоритмические системы. – М.: Наука, 1970. – 392 с.

  18. Мальцев А.И. Конструктивные алгебры. 1 // Успехи мат. наук. – 1961. – 16, № 3. – С. 3–60.

  19. Горєлов А.В., Редько І.В., Яганов П.О. Композиційні засади програмістської діяльності // Вісник КНУТД. – № 4. – 2014. – С. 25–34.


Copyright (c) 2017 NTUU KPI