To put it otherwise, this book concerns instruction sequences, the behaviours produced by instruction sequences under execution, the interaction between these behaviours and components of the execution environment concerning the processing of instructions, the expressiveness of instruction sequences, and various issues relating to well-known subjects from computer science where we found that the notion of an instruction sequence is relevant. Most of the issues in question are of a computation-theoretic or computer-architectural kind. They relate to subjects such as the halting problem, non-uniform computational complexity, instruction sequence performance and instruction set architecture. Some of the issues considered are somehow related to process algebra, namely remote instruction processing and instruction sequence producible processes. Some variations on instruction sequences of the usual kind, such as instruction sequences without a directional bias and probabilistic instruction sequences, are also considered.
This book is primarily intended for researchers in computer science interested in instruction sequences as a theme in computer science. It is also meant to be suitable as supplementary reading in courses for graduate students and advanced undergraduate students in computer science. Chapters 5 and 6 may as much appeal to those who are primarily interested in the subjects from the theory of computation and the area of computer architecture, respectively, that come up in these chapters. Chapter 7 may as much appeal to those who are primarily interested in process algebra.
Throughout the book, some familiarity with equational logic, universal algebra, and elementary set theory is assumed. In Sect. 5.2, some familiarity with non-uniform computational complexity is assumed. In Sect. 5.1, Sect. 6.2 and Chap. 7, some familiarity with computability, instruction set architectures and process algebra, respectively, would be helpful. Chapter 2 is a prerequisite for Chap. 3, and both chapters are prerequisites for all subsequent chapters.
Chapter 2 introduces an algebraic theory SPISA of single-pass instruction sequences and an algebraic theory BTA of mathematical objects that represent in a direct way the behaviours produced by instruction sequences under execution. The objects concerned are called threads. It is made precise in the setting of the latter theory which behaviours are produced by the instruction sequences considered in the former theory. The instruction sequences in question include both finite and infinite ones, but the theory provides a notation by means of which all of them can be represented finitely. This chapter also introduces alternative notations ISNR and ISNA by means of which all these instruction sequences can be represented finitely as well, but which are closer to existing assembly languages.
Chapter 3 introduces so-called services, which represent the behaviours exhibited by the components of an execution environment that are capable of processing particular instructions and doing so independently, and extends BTA with an operator meant for the composition of families of named services and operators that have a direct bearing on the processing of instructions by services from such service families. In addition, the concept of a functional unit, which is an abstract model of a machine, is introduced. In the frequently occurring case that the behaviours represented by services can be viewed as the behaviours of a machine in its different states, the services concerned are completely determined by a functional unit. Some extensions of ISNR and ISNA with additional instructions are explained with the help of some simple functional units.
Chapter 4 gives answers to basic expressiveness issues regarding SPISA. In this case, expressiveness is basically about which behaviours can be produced by instruction sequences under execution, which instructions can be removed without reducing the class of behaviours that can be produced by instruction sequences under execution, how to enlarge the class of behaviours that can be produced by instruction sequences under execution, et cetera. This chapter is also concerned with some issues that arise from the investigation of expressiveness issues regarding SPISA. For example, it is shown that a finite-state execution mechanism for a set of instruction sequences that by itself can produce each finite-state behaviour from an instruction sequence belonging to the set of instruction sequences in question is unfeasible.
Chapter 5 concerns two subjects from the theory of computation, namely the halting problem and non-uniform computational complexity. Positioning Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines, and taking single-pass instruction sequences as considered in SPISA as programs, the autosolvability requirement that a program of a certain kind must solve the halting problem for all programs of that kind is analysed. Thinking in terms of single-pass instruction sequences as considered in SPISA, counterparts of the classical non-uniform complexity classes P/poly and NP/poly are defined, a notion of completeness for the counterpart of NP/poly is introduced, several complexity hypotheses are formulated, and it is shown that a problem closely related to 3SAT is NP-complete as well as complete for the counterpart of NP/poly.
Chapter 6 concerns two subjects from the area of computer architecture, namely instruction sequence performance and instruction set architectures. We study the effect of eliminating indirect jump instructions from instruction sequences with direct and indirect jump instructions on the interactive performance of instruction sequences. A strict version of the concept of a load/store instruction set architecture is proposed for theoretical work relevant to the design of instruction set architectures, and it is studied how the transformations on the states of the main memory of a strict load/store instruction set architecture that can be achieved by executing instruction sequences on it depend on the parameters involved.
Chapter 7 concerns two subjects related to process algebra, namely protocols to deal with remote instruction processing and instruction sequence producible processes. If instruction processing takes place remotely, this means that a stream of instructions to be processed arises at one place and the processing of that stream of instructions is handled at another place. Process algebra is used to describe two protocols to deal with this phenomenon. Because process algebra is considered relevant to computer science, there must be programmed systems whose behaviours are taken for processes as considered in process algebra. It is shown that all finite-state processes can be produced by single-pass instruction sequences as considered in SPISA, provided that the cluster fair abstraction rule known from the algebraic theory of processes called ACP is valid.
Chapter 8 introduces three variations of instruction sequences as considered in SPISA, namely polyadic instruction sequences, instruction sequences without a directional bias, and probabilistic instruction sequences. A polyadic instruction sequence is a possibly parameterized instruction sequence fragment that can produce a joint behaviour together with other such fragments because the fragment being executed can switch over execution to another. Instruction sequences without a directional bias require that for each instruction whose effect involves that execution proceeds in the forward direction, there is a counterpart whose effect involves that execution proceeds in the backward direction. Probabilistic instruction sequences are instruction sequences that contain instructions that are themselves probabilistic by nature.
There are also four appendices. In Appendix A, five challenges for the point of view from which the approach to semantics followed in Chaps. 2 and 3 originates are sketched. In Appendix B, some results about functional units for natural numbers are given, which are except one computability results that are not directly related to existing results that we know of. In Appendix C, the usefulness of the dynamically instantiated instructions introduced in Chap. 3 is illustrated by means of an example. In Appendix D, a model of a hypothetical execution environment for instruction sequences, designed for the purpose of explaining how instruction sequences as considered in SPISA may be executed, is discussed.
A glossary of the notations introduced in this book and the general mathematical notations used in this book is available as well. At this point, one further remark about notation may be useful: bold-faced italic letters, with or without decorations, will be used as syntactical variables in this book.