Logics of conditional computations with errors

##plugins.themes.bootstrap3.article.main##

Николай Николаевич Непейвода

Abstract

The conditional operator \(\textbf{if } A \textbf{ then } S \textbf{ else } T \textbf{ fi}\) is a "Scheffer" for programming: McCarthy shoved that computable functions can be represented as recursive schemes using conditional expressions. This approach needs to consider errors. Thus in modern computer science data types are enriched by the error \(\bot\). This error is considered as fatal but in praxis many errors are recoverable. Thus we considered recoverable error \(\mathfrak{u}\) as fourth logical value and investigate logics of various disciplines to handle \(\mathfrak{u}\). Another logical interpretation of \(\mathfrak{u}\) is the unsolved problem \(\{\mathfrak{t},\mathfrak{f}\}\). This treatment of \(\{\mathfrak{t},\mathfrak{f}\}\) differs from usual as overdefined [Anderson et al., 2017]. Four disciplines of handling conditional statements and induced logics are considered. All they can be viewed as extensions of three-valued logics by lisp logic for fragment \(\mathfrak{t},\mathfrak{f},\bot\). Logic \(\textbf{if}_1\) of standard sequential computation is extension of lisp logic. Logic of parallel computations where \(\textbf{if}_2\ \mathfrak{u}\ \textbf{ then } \mathfrak{x} \textbf{ else } \mathfrak{x}\ \textbf{ fi}=\mathfrak{x}\) is extended \(\text{Ł}_3\). Logic of maximal conditional when \(\mathfrak{x}\) occurring in both alternatives is accepted: \(\textbf{if}_3\ \mathfrak{u}\ \textbf{ then } \mathfrak{z} \textbf{ else } \mathfrak{y}\ \textbf{ fi}=\mathfrak{x}\) is extended Pcont. Logic of Prolog where \(\textbf{if}_4\ \mathfrak{u}\) is the first occurring definite value \(\mathfrak{t},\ \mathfrak{f}\) has its own implication and negation but is equivalent to logic of \(\textbf{if}_3\). Operators \(\textbf{if}_3\) and \(\textbf{if}_4\) are logically complete: each continuous in \(\{\mathfrak{t},\mathfrak{f}, u, \bot\}\) function is expressible. Operators \(\textbf{if}_2\) and \(\textbf{if}_3\) induce strategies for parallel and distributed processes. \(\textbf{if}_1\) corresponds to traditional sequential programs, \(\textbf{if}_4\) to Prolog.

##plugins.generic.usageStats.downloads##

##plugins.generic.usageStats.noStats##

##plugins.themes.bootstrap3.article.details##

Section
Non-classical logics

References

Карпенко, 2010 – Карпенко А.С. Развитие многозначной логики. М.: ЛКИ, 2013. 444 с.
Комендантская, 2009 – Комендантская Е.Ю. Функциональная взаимовыразимость регулярных логик Клини // Логические исследования. 2009. № 15. C. 116–128.
Коржавина, Князьков, 2019a – Коржавина А.С., Князьков В.С. Метод умножения с масштабированием результата для высокоточных модулярнопозиционных интервально-логарифмических вычислений // Инженерные технологии и системы. 2019. Т. 29. № 2. С. 187–204.
Коржавина, Князьков, 2019b – Коржавина А.С., Князьков В.С. Реализация высокоточных вычислений в базисе модулярно-интервальной арифметики // Программные системы: теория и приложения. 2019. Т. 10. № 3 (42). С. 81–127.
Митчелл, 2010 – Митчелл Дж. Основания языков программирования. М.; Ижевск: R&C Dynamics, 2010. 719 с.
Непейвода, 2017 – Непейвода Н.Н. Использование локализации и переполнения для управления параллельными и распределенными вычислениями // Программные системы: теория и приложения. 2019. Т. 8. № 3 (4). С. 87–107.
Томова, 2010 – Томова Н.Е. Импликативные расширения регулярных логик Клини // Логические исследования. 2010. № 16. C. 233–258.
Anderson et al., 2017 – Anderson A.R., Dunn J.M., Belnap N.D. Entailment, Vol. II: The Logic of Relevance and Necessity. Princeton: Princeton University Press, 2017.
Arieli, Avron, 2015 – Arieli O., Avron A. Three-Valued Paraconsistent Propositional Logics // New Directions in Paraconsistent Logic / Ed. by J.-Y. Béziau et al. New Delhi: Springer India, 2015. P. 91–129.
Barendregt, 1984 – Barendregt H.P. The lambda calculus. Its syntax and semantics. Revised edition. Studies in Logic and the Foundations of Mathematics. Vol. 103. Amsterdam: North-Holland Publishing Co., 1984.
Bratko, 2012 – Bratko I. Prolog programming for artificial intelligence (4th ed.). Harlow, England; New York: Addison Wesley, 2012.
Carayol, Serre, 2021 – Carayol A., Serre O. Higher-order recursion schemes and their automata models // Pin J.-É. (ed.). Handbook of Automata Theory, 2, European Mathematical Society. 2021. P. 1295–1341. URl: https://digital.library. adelaide.edu.au/dspace/bitstream/2440/18746/2/02whole.pdf (дата обращения: 14.03.2025).
Clarke, 1979 – Clarke E.M. Programming Language Constructs for Which It Is Impossible To Obtain Good Hoare Axiom Systems // Journal of the ACM. 1979. Vol. 26. Iss. 1. P. 129–147.
de Angelis, Govind, 2024 – de Angelis E., Govind H.V.K. CHC-COMP 2023: Competition Report // EPTCS 402. 2024. P. 83–104. URL: https://arxiv.org/ pdf/2404.14923v1 (дата обращения: 14.03.2025).
Ford, 2020 – Ford N. Distributed systems // Fundamentals of Software Architecture: An Engineering Approach (1st ed.). Sebastopol: O’Reilly Media, 2020. P. 146–147.
Marché, Zantema, 2007 – Marché C., Zantema H. The Termination Competition // Term Rewriting and Applications. New York: Springer, 2007. P. 303–313. McCarthy, 1963 – McCarthy J. A Basis for a Mathematical Theory of Computation // Computer Programming and Formal Systems. 1963. Vol. 35. P. 33–70.
Meijer et al., 1991 – Meijer E., Fokkinga M.M., Paterson R. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire // Hughes J. (ed.) Functional Programming Languages and Computer Architecture. FPCA 1991. Lecture Notes in Computer Science. Vol. 523. Berlin; Heidelberg: Springer, 1991. P. 124–144.
Rosser, Turquette, 1952 – Rosser J.B., Turquette A.R. Many-Valued Logics. Amsterdam, North-Holland, 1952.
Scott, 1970 – Scott D. Outline of a Mathematical Theory of Computation // Proc. Fourth Annual Princeton Conference on Information Sciences and Systems. 1970. P. 169–176.
Tanenbaum, van Steen, 2002 – Tanenbaum A.S., van Steen M. Distributed systems: principles and paradigms. Upper Saddle River, NJ: Pearson Prentice Hall, 2002.