Primitive Programing Algebra of Computable Functions at Records
Keywords:Fullness of calculable functions, Fullness problem in PPA, Complete system, Pairs of natural numbers, Pr-functions, Pr-predicates
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.
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).
LicenseCopyright (c) 2017 NTUU KPI Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work