Название: Structures of Computing: A Guide to Practice-Oriented Theory
Автор: Egon Börger, Vincenzo Gervasi
Издательство: Springer
Год: 2024
Страниц: 286
Язык: английский
Формат: pdf (true)
Размер: 10.1 MB

”Structures of Computing” aims to explain the behavioural meaning of fundamental concepts of computing without referring to any specific computing device or programming language. By defining these concepts in more general and at the same time simpler mathematical terms the book is focused on cooperating agents that process dynamic structures where the data—stored in abstract memory forming abstract states—are arguments and values of arbitrary functions and relations between objects. These computational structures are dynamic, subject to change due to rule-based actions that are performed on the data by algorithm-equipped agents under various forms of cooperation control, including in particular the reaction to environmental stimuli.

The book uses the conceptual computational framework of Abstract State Machines (ASMs)—an intuitive form of pseudo-code that operates directly in abstract states (computational structures) and comes with a precise easily defined rule-based meaning—but it does not assume knowledge of ASMs. We explain the small number of basic abstract but operational terms of that framework which suffice to explain the common core of a great multitude of operational concepts and constructs of computing in a uniform way, facilitating their understanding and analysis.

Part I of the book defines the conceptual constituents of interactive processes: (i) data, i.e. structured objects with associated properties, relations and functions the algorithmic processes operate upon, (ii) basic operations that affect the data in single execution steps, and (iii) control mechanisms that determine the combination of single steps in multi-agent computations where the interaction happens via communication or other forms of data sharing.

Part II analyses these constituents concerning (i) methods to achieve process correctness (inspection, experimental validation, reasoning), (ii) principal computational paradigms (architectures, programming styles, communication structures, control patterns from sequential and reflective to concurrent, mixed synchronous/asynchronous and data flow control), and (iii) complexity (power and limits of computing structures).

Target Audience:
The book is addressed to persons who want to understand the conceptual foundation of computing. It does not assume any specific programming experience but only a basic understanding of what are mechanically executable processes and their descriptions. Think of system-control mechanisms, automated service procedures, administrative or business processes and the like which accompany our daily life. To make the book also accessible for non-experts of the theory of computing we avoid any unnecessary formalism and formulate our definitions as much as possible in natural language, using common mathematical notation only where needed to avoid ambiguities. Examples and exercises (coming with solutions in the Appendix) serve as comprehension checkpoints; we insert references to the literature for the reader who is interested in further developments.

The book has been written for self-study but can also be used in teaching, in particular to accompany undergraduate courses or seminars for students who want to understand how the many concepts they learn are intimately linked to each other by a common foundation.