5 Computer Science Ninja Arts

I am not a computer scientist. Or to be accurate, I am a computer scientist by adoption. I adopted the discipline, having as a background systems engineering, and the discipline adopted me. Of course, the result is that shamefully, I miss large parts of the proper formation of a computer scientist and have had to acquire the requisite knowledge, at least sufficient to 'pass' as a computer scientist, subsequently. Perhaps however, this has given me a more sensitive appreciation of the elegance of computer science and of its  'ninja arts'. Here are my selected five, which exemplify the intellectual and technical tools that computer scientists are able to bring to bear on complex problems. I commend them to occasional programmers and to those interested in scientific thinking more generally.

Query optimisation. Databases generally are an amazing and unsung technological achievement. They underpin almost every part of computing, certainly most interactive information services, and are the technology of choice when we want data to persist (stick about) and still remain readily accessible. Databases possess both power and simplicity achieved through a combination of mathematical representation and engineering pragmatism. This is best illustrated by database queries, intended to extract the desired information from a database. These queries are usually answered rapidly, regardless of the manner in which the query is formulated. This is achieved by transforming the query into a mathematically equivalent form that is capable of being answered quickly (that does not require, for example, the computation of large intermediate results) this in turn requires leveraging statistical knowledge about database queries, trading off the costs of the process of optimisation against the benefits to be achieved, and knowing how and where the information is physically stored. It works so well, you do not notice it.

Meta-modelling. Modelling, that is systematic abstract representation to support analysis and understanding, is what engineers do. Computer scientists go one step further, actually several steps further. We model models and we model those models, and so on. This is meta-modelling and meta-meta-modelling, though we tend to stick with the term meta-modelling because otherwise, frankly, it gets a bit ridiculous. Why is this clever or interesting? Well obviously if you want to use computers to support modelling and the analysis of models you need to represent the models somehow so you need a model of the models, a meta-model. Now imagine you want to represent a class or family of different sorts of models, well you might need a meta-meta-model. Once we are working at this level some new possibilities open up. We can reason about the relationships amongst modelling languages , we can build our own modelling languages, or mix and match features of different languages, we have a common basis for communication between models. Here we see how computer scientists use abstraction flexibly as a powerful means of addressing complex problems and building new tools.

Analysis of algorithms. It is, I think, well known that some tasks in computing can be performed by many different algorithms (problem-solving strategies given as rules). The classic examples of this are searching and sorting tasks that can be accomplished many different ways. Considerable creativity has been deployed in devising different algorithms for these and other purposes. Much of the innovation in computing is driven by the creation of novel algorithms, pagerank that underpins Google search being a case in point. The challenge is that different algorithms possess different properties specifically in terms of the resources, such as space and time, required to execute them. A science of the analysis of algorithms independent of the particulars of their implementation, that is how well they are coded, has arisen. This rests upon establishing the (computational) complexity of the underlying problem which bounds what the algorithm can achieve. Here mathematics combines with abstract models of computing machines. Far however, from being a purely esoteric matter this piece of science is critical to selecting algorithms and understanding the determining constraints for software design.

Concurrency. We tend to think of computing as being about sequential processing. This is the so-called von Neumann paradigm (or architecture) that provides our framework for thinking about practical computation. Of course this paradigm only holds true of a single computer, or more accurately, of a single computing unit (a different thing, as we shall see). Most computing is distributed that is dependent on many networked and communicating computers operating essentially independently. Computation in this setting is thus concurrent. Most computers in fact comprise multiple computing units (for instance cores) that process concurrently and most programming environments provide an abstract model of concurrent processing to the developer. Now, the really interesting part of this is not the independent concurrent operations but the collaboration required to complete joint tasks. This in turn requires coordination and shared resources (such as memory, data storage or network access). Achieving this coordination without imposing a significant overhead on collaboration and without failures such as deadlock in which two concurrent operations each wait for the other to release a shared resource necessary to proceed, is very tricky requiring significant programmer skill. It has proved possible to provide support for this by way of intermediate software layers that simplify the task and increasingly by analysis techniques that can identify concurrency problems at the point a program is specified. Thus, rather than concurrency adding complexity it ultimately delivers a framework for directly addressing the great variety of problems that are naturally concurrently, that is exhibit inherent parallelism.

Compiler construction. The use of a high level programming language that provides the expressive capability to support problem solving is one of the characterising contributions of computer science. It depends however on our ability to transform programs in that language into efficient machine instructions. This is, in general, is the role of the compiler, and it has been brought to a high art, leveraging a deep understanding of language syntax and semantics, which itself might justify its selection here. Though, for the most part, programmers use 'general purpose' programming languages, it is often necessary to solve particular classes of problem that exhibit both a high degree of complexity and openness, and in these cases to define a special purpose programming language. Such a language is commonly small or fragmentary, targeted narrowly. We are then able to use a range of compiler construction tools and to generate from an abstract definition of the language the required elements of a compiler. Literally, and rather mind-bendingly, using a compiler-compiler. This form of 'language engineering' demonstrates a number of the themes evident in my previous examples, elegant engineering and the power of controlled abstraction.

I welcome your suggestions.