Chapter 3
Machines for Computations

La machine, qui semblait d’abord l’en écarter, […] soumet [l’homme] avec plus de rigueur encore aux grands problèmes naturels.
Antoine de Saint-Exupéry

The main stream computing machines we employ today operate in an imperative fashion. The commands are realized using physical principles. The most common physical representation today makes use of electronic circuitry, however, alternative representations have also been employed in the past such as mechanical systems [6][7] and are explored for future developments ranging from optical to quantum systems. An outline of abstraction in a digital computer is illustrated in Figure 3.1.


Figure 3.1: Abstraction.

A logical layer is built on the foundations of the physical representation of choice. While again several choices of logic, such as ternary, are available binary logic is used exclusively in the main stream. While various physical representations may yield themselves to varying degrees to different logical representations, it seems clear that any deviation is considered exotic and is measured with respect to the standard binary system.

Once the simplest of logic operations are made available, it is possible to construct operations of increasing complexity and expressivity leading to the appearance of machine code and the assembly language, which itself is the firm foundation on which tools such as compilers [8] rely. The case of interpreted languages only adds an intermediate layer of a run time environment. Any and all additionally available abstractions in higher level programming languages must lead to a form expressible on this level.

This also reveals that, while a projection from a high level to a lower level must exist for a computer program, it is, in general, not a bijection. This is easily apparent by considering that different expressions even in different programming languages may result in similar or even exactly the same machine code, as can be illustrated using the following, arguably trivial example:

: Simple program in C.
int main() 
   float sum = 0; 
   int i = 0; 
   for (i =0; i < 10; ++i) 
     sum = sum + i; 

: Simple program in Fortran.
  REAL SUM = 0 
  INTEGER I = 0 
  DO I = 0, 9, 1 
     SUM = SUM + I 

The central part of the two trivial implementations in Fortran [9][10] and C [11][12], sum = sum + i, results in this machine code using a gcc 4.3.4 compiler [13] on an Amd64 architecture without optimizations.

: Assembly from C.
sum = sum + i; 
  cvtsi2ss 0x4(%rbp),%xmm0 
  movss  0x8(%rbp),%xmm1 
  addss  %xmm1,%xmm0 
  movss  %xmm0,0x8(%rbp)

: Assembly from Fortran.
SUM = SUM + I 
  cvtsi2ss 0x10(%rbp),%xmm1 
  movss  0x4(%rbp),%xmm0 
  addss  %xmm1,%xmm0 
  movss  %xmm0,0x4(%rbp)

As can be observed the stream of instructions is identical, only the memory addresses do not agree. This should demonstrate that the projection to a lower level of abstraction from several points of origin may produce the same result. However, it also follows from this that simply examining the low level representation it is not possible to reliably reconstruct the source. Although assembly code may contain patterns and peculiarities, which may be connected to a certain compiler or language, the reconstruction of higher abstraction levels is a quite tedious task. This is especially so, as while it may be reliably discerned what is happening, the semantics, as for example, expressed by the naming of variables, is lost. Therefore the reconstruction of an algorithm from a bottom up method, especially once an optimizing compiler is employed, may be deemed an endeavour doomed to fail. Any information lost by a projection downwards is irrecoverable.

When the generated resulting assembly instructions are identical, which of course greatly depends on the quality of the translation mechanism used, it indicates that the choice of programming language and paradigm does not necessarily affect the generated result. It does, however, very strongly affect how easily and safely different tasks may be expressed and performed. As an example, the same task as above is performed in the following snippet of C++ code.

: Sample program in C++.
int main() 
   float sum; 
            ref(sum) += _1); 

Therefore, the choice of programming language should take into account, how easily a chosen paradigm can be expressed, while also being mindful of the availability and quality of the associated tools such as compilers or interpreters. However, finally, all technical facts aside, the choice usually depends most heavily on a programmer’s preference.


Figure 3.2: From programming languages to execution.

The notion is shown in Figure 3.2 using a by far not complete set of programming languages.

Now that it has been established that all programming abstractions require some form of low level representation, several of the major programming paradigms which embody these abstractions are presented.

 3.1 Paradigms
  3.1.1 Imperative Programming
  3.1.2 Object-Oriented Programming
  3.1.3 Functional Programming
  3.1.4 Generic Programming
  3.1.5 Programming Language for Scientific Computing
 3.2 Mathematics and Algorithms
 3.3 Example of Generic Programming
  3.3.1 Mathematical Description
  3.3.2 Compile Time Structure
  3.3.3 Compile Time Meta Program
  3.3.4 Run Time Adaption