The Computational Models project tries to describe how constructs for expressing behaviour of systems can be computed on different levels of abstraction. The goal of this project is to have a computational model for each level of abstraction that we use in the software development process and relate these models to allow reasoning over the development process. Also, the models have to allow forms of concurrency.
Results sofar:
- A Unified Computational Model for the concurrent execution of programming entities, such as functions, objects, distributed components.
- The sequential execution of functions is a special case of this unified computational model.
To execute a program written in a particular programming language, it is compiled into executable code for a particular machine. The machine is actually a machine model representing physical hardware, operation system, etc, or possibly a virtual machine. The compilation is done according to an execution model specific for the machine model. An execution model is an implementation of a computational model which gives the essential rules for performing computations. The computational model must at least be adequate for expressing the operational semantics of the programming language.
Overview of program execution related affairs
With the introduction of support for concurrency in machine models, whether or not based on hardware capabilities, concurrency became available to be incorporated in programs. There are several forms in which support can be given for the use of concurrency. One of these forms is by using an add-on library that implements a set of primitives build on top of the concurrency capabilities provided by the machine model. A typical example of this is multi-threading. A problem with the use of such libraries is that they may vary on different platform making the programs less portable. This problem can be solved by using a standard such as Posix, or Pthreads. A more important problem is that the programming language is still based on a computational model for sequential execution of instructions, and compilation is still based on a model for sequential execution of instructions. Compilers may generate efficient code that is correct for sequential execution, but incorrent for concurrent execution. This is caused amongst other things by communications between threads through shared memory. The approach above results in the writing of a program, even if it clearly has independent parts that can be executed concurrently, based on a sequential execution model to which carefully concurrency is added, instead of onto a model that directly allows for concurrent execution transparently to the user. Furthermore, one has to keep control over the concurrent execution in order to avoid problems as race conditions, deadlocks, consistency of data, etc. So there is no transparency whatsoever concerning concurrency, making it very hard to write reliable software.
We focus on computational models for the execution of functions. From the standard sequential execution model we derive a framework of computational models by abstracting from the details of function call implementation. This framework contains computational models that allow for the concurrent execution of functions.
We extend this framework with communications between concurrent functions. Thereby identifying problems that can occur with the communications and presenting solutions for these problems.
We use the framework of computational models for function execution as base for the development of computational models that allow for the concurrent execution of objects.
The compational model for object execution complies with the fundamentals of object-orientation.
We use the term object here in the broadest sense possible, abstracting from every possible implementation detail. The same applies to the communication between objects, which we only see as a form of message passing. Now, we can easily extend our framework of computational models for the concurrent execution of objects to a framework of computational models for distributed computing. We only have to abstract from the location in which each of the objects resides.
By doing this, we established a Unified Computational Model for the concurrent execution of programming entities (functions, objects, and distributed components).