Taxonomy/0. Taxonomy of Computer Science

Abstract

This collection of definitions and examples tries to contribute to the understanding of the essence of information technology and computer science. Like all technologists, information technologists aim at the creation of artefacts with certain properties. To achieve this, they formalise the problem by abstracting the properties into a specification and then invent or develop a blueprint, i.e. an abstraction of the machine’s structure. Subsequently, it is their principal task to prove that the blueprint satisfies the specification. Computer scientists develop mathematical and physical means to support or even enable that task. From this, the principal research questions of computer science may be derived.

We propose a consistent set of notions and a consistent terminology which may clarify the relation of information technology and computer science to other scientific disciplines. Information technologists as well as teachers and students of computer science may find the concepts helpful to disentangle many complex achievements of computer science and re-use their constituents in other contexts, and to view their own activities in the light of other disciplines.

First we introduce a consistent set of notions, a diagram, a formula (with respect to which important aspects of the design process can be understood) and a consistent terminology. Subsequently, we provide formal definitions for basic concepts of formal methods and a mathematical foundation for our formula. They shall illustrate that the rôle of mathematics in development and verification is not limited to useful calculations. Ideally, designing is a creative mathematical activity, which comprises finding a theorem, if necessary strengthening its assumptions until it can be proven.

Although for good reasons most artefacts are designed without the use of formal methods it may be a source of useful insight to understand all design as an ‘approximation’ of such a mathematical activity. This gives rise to, for instance, a taxonomy of design decisions and of fault tolerance. And it may help to relate paradigms, theories, methods, languages, and tools from different areas of computer science to each other to make optimal use of them.

Authors

• Hanno Wupper
• Hans Meijer
• Angelika Mader
• Stijn Hoppenbrouwers
• Mieke Boon

Preface

In a first publication on this Taxonomy of Computer Science (1998) we wrote: "In computer science there is only limited terminological agreement. Already for its very name one has the alternatives ‘computing science’ and ‘informatics’. Fundamental terms like ‘state’ or ‘automaton’ or ‘specification’ or even ‘program’ may have different meanings in different contexts. Often such terms are not defined at all (but simply borrowed from common language) or defined in many different ways. This situation is an inevitable reflection of the fact that there is no common understanding of the core of this particular branch of science, let alone a basic understanding among the general public. In particular software engineering has produced an abundance of points of view, of terms and of notions which sometimes look all alike and all different. What is the difference, if any, between a program and an algorithm? What is a system? When is it appropriate to call something a module? One example is the so-called paradigm ‘object orientation.’ Its value is beyond doubt, but for many information technologists it is difficult to see what it is really about. It may be a specification method that can be useful in many contexts, a number of language issues in specification and programming languages or an amount of theory (abstract data types, inheritance, etc.) which can be useful even for someone who has to develop FORTRAN or COBOL programs."

In the meantime, the situation in software engineering has improved, while the focus of computer science shifted from programming to other areas, where the same confusion is arising. UML is now what object orientation was then. This shift of focus is mirrored in this version of our taxonomy, which is influenced by the developments in the areas modelling, specification and verification.

The first publication of this taxonomy was written mainly for computer scientists, with the hope to contribute to creating order in the Babylonic confusion. In the meantime, computer science has become more mature, and has developed theories, methods, languages, and tools that could be useful not only for information technologists but also for neighbouring disciplines. Hopefully this new version of our taxonomy not only is useful inside computer science but also helps to clarify the dialogue with professionals and scientists of other disciplines and to help them understand where the achievements of computer science might be useful for them.

Introduction

Scientific understanding is impossible without abstraction. Moreover, abstraction of the reality into mathematical models enables scientists to reason about the reality by mathematical means. However, one may need to be very careful about the appropriate level of abstraction. In many fields of computer science one may, for example, identify a machine with its program while in some other fields one may identify a program with its specification, but negligent use of such abstractions may be very confusing.

This observation is the root of our belief that one should always try to depart from the distinction between the mathematical description of the desired properties of an artefact (be it a computer program, a machine or a whole factory or aircraft) – the ‘specification’ –, the text representing that program or, more general, the structure of the artefact – the ‘blueprint’ – and the physical combination of hard- and software whilst executing – the ‘artefact’ itself in the physical reality –, which has certain observable effects in the physical world – the ‘properties’. Not separating these four aspects is, we believe, the main cause of the Babylonian confusion which pervades computer science and which has at least the following consequences:

• Technical terms may have (slightly) different meanings in different research areas, which does not favour communication among scientists.
• Computer scientists, particularly young ones—students, may have difficulties putting results of others in context.
• It may be unnecessarily difficult to relate the results of computer science to those in other disciplines.
• In examples, case studies and methodological discussion the focus of attention can be moving erratically.
• Finally it may be very hard to explain to the general public or the authorities what computer science is all about and which benefits may be expected from research programmes.

We try to answer the question what information technology is all about and what computer science has to do with it. More specifically we try to contribute to the understanding of the essence of rational system design and verification. In doing so, we propose a consistent collection of notions with respect to which all important aspects of the discipline can be understood, together with a clear and unambiguous terminology. Note that the notions are the important issues, not the terms: we try to establish a set of fundamental notions, for which we hope to find consistent terms. We hope that our set of notions may greatly clarify the relation of information technology and computer science to other scientific disciplines and also give rise to new ideas about computer science education. We do not claim to arrive at particular new results, but to an overall insight in the field. Information technologists and teachers and students of computer science may find the concepts presented here helpful to disentangle complex achievements of computer science and re-use their constituents in other contexts, but also to see what their activities have in common with other disciplines, especially with the art of mathematics. Vice versa, we hope that this approach helps other disciplines to understand where they can profit from the results of computer science.

Philosophy

The Rationality Square

The Correctness Theorem

Our method is to begin with a basic, abstract and general question, which is subsequently refined and detailed:

How can we make things (especially artefacts containing some IT) in such a way that we can be sure beyond reasonable doubt that they do what they are intended to do?

This question is inspired by a development cycle, which is related to the various forms of the ubiquitous software life cycle of software engineering, but tries to unify and normalise them. An important goal of our framework is the generalisation of the development cycle to the whole area of information technology. In fact we believe that every aspect of information technology and computer science has its place in our framework. Of course this very much depends on the understanding of the notions ‘computer science’ and ‘information technology’, and indeed we take these notions in the widest possible sense: it is the science of and technology of the use of computers and computer applications, the creation of such applications, the specification of customers’ desires, the proofs of correctness of applications, etc.

Going a step further, we are even convinced that our framework may be applied mutatis mutandis to a much larger segment of science and technology. The discovery and (experimental or theoretical) verification of laws of nature and the creation of technological products from that scientific knowledge may be described and classified in a totally analogous way. More established fields of science may not be in need of such a clarification. Nevertheless the first sub-question we investigate will be one that is shared with all sciences.

We shall employ three different frameworks:

1. a Rationality Square (the one inspired the software life cycle),
2. a Correctness Theorem, and
3. the tetrachotomy theories, methods, languages, and tools.

By this we hope to demonstrate that the rôle of mathematics in development and verification is not limited to calculations and computations: Ideally, designing is a creative mathematical activity, which comprises finding a theorem, if necessary strengthening its assumptions until it can be proven.

Overview

1. Quality
   1. Rationality. How can we be sure? How is physical reality related to mathematics? Things and theories must be made to fit.
   2. Models. Even if we have all the knowlegde and the necessary theory, things can be so complicated that we must take care not to get lost in complexity.
   3. Formal Methods. Rationality applied to the development of artefacts, in praticular IT-systems
   4. Correctness Theorems. Correctness made formal
   5. Software. The specific nature of programmable machines
   6. Development. How to make an artefact for a certain goal?
   7. Verification and validation. How to be sure?
   8. Fault tolerance. What, if nevertheless things go wrong?
   9. Quality criteria. The conclusion of the previous chapters
2. Methodology - See Methodology for a preliminary list of chapters.
3. Computer Science. Computer science is about building systems. What do computer scientists produce? How can computers help?
   1. theories
   2. methods
   3. languages
   4. tools
4. Specific areas
   1. Processes
   2. Production
   3. Fault tolerance
5. Specific articles under construction
6. Towards a Taxonomy for Architecture in the Digital World

Acknowledgements

• Henk Barendregt
• Raymond Boute
• Guy Debrock
• André van den Hoogenhof
• Adriaan de Groot
• Tom van Weert
• Toine Tax
• Huub van Thienen
• Erik Barendsen
• Frits Vaandrager
• Ed Brinksma
• Wouter Kuijper
• Jelena Marincic
• Roel Wieringa