Personal informationResearch areaTeaching and guiding studentsInteresting technologyLinks to interesting sites
Rick van Rein, PhD student:
[SELECT TOPIC]

Philosophy behind my Life Cycle Research

Summary

My Life cycles are process descriptions for object oriented analysis. Life cycles are like communicating state diagrams, and are intended as a replacement of state charts. Life cycles are sufficiently precise to allow verification and code generation. This page discusses my sources of inspiration, and evaluates them from my life cycle objectives.

Topics in this document are:

If you would like more information after reading this, please pick up the introduction to my PhD thesis.

Object analysis

Object oriented modelling usually comprises of three main phases, referred to as analysis, design and implementation. An important advantage of object technology is that design and programming can be done with local knowledge and without much overview over the whole design. To make this possible, the analysis phase is the phase in which the overview is addressed without considering design and programming details.

Unfortunately, this dream is sometimes disturbed because common implementation techniques can easily produce programs with problems:

False assumptions
One object may falsely assume certain behaviour from other objects. This effect gets stronger when multiple programmers work on the same design. This problem can be tracked back to imprecise analysis models. Often, analysis models are drawn as rectangles and arrows with more than one possible interpretation. Class diagrams suffer from this just as well as state charts.
Infinite recursion
Another problem is that implementations add details, such as a method invocation structure. If one object is designed to inform another object of its changes, and the other object responds to this with a change that is reported back, then infinite recursion can show up. This is probably due to the low-level details that programmers are forced to make up in models. Most design approaches resolve this problem by drawing method interaction charts.
Apparently, object modelling does not resolve all issues yet.

In my PhD work, I cannot resolve all issues, but I will try to cover the problems related to processes in object models, notably state diagramming models. Life cycles capture such models in a precise manner, making it possible to express communication between objects accurately. This precision facilitates both the automated generation of an implementation and the verification of the specified models.

The verification of process models is targeted at hiding effects of global cooperation of whole process systems, except of course in places where cooperation is intentional. For example, if the global cooperation would (or could) lead to a deadlock, then the verification software should raise an error.

Generating an implementation does not mean that design and implementation phases are removed from the object development process. Instead, the problems that occur at the design and implementation levels are solved generically; for example, generating SQL statements to update an attribute in a persistent database implementation of an object is similar for every object, given a certain mapping of objects to databases; it is a waste to write code for this manually for every attribute update when a meta-level treatment can solve this kind of problem once and for all. Note how this approach resembles that of design patterns, although in this case with an exhaustive (or complete) set of patterns.

Process Algebra

Process algebras express processes in a precise manner (it is a mathematical discipline), and therefore several verification approaches could be defined and implemented for them. Unfortunately, such approaches tend to ignore a few practical aspects that make them unusable for object systems.

Instantiation
Objects are usually instantiated from classes, and any number of instances can be made. The number of objects instantiated from a class is unlimited (but finite at any moment during a run). Since each object usually goes through a process of its own, unbounded object instantiation requires unbounded process instantiation.

Process algebras tend to have difficulties capturing this unbounded creation; it was not until the invention of the pi-calculus that this was resolved nicely. The pi-calculus however, has no usable automatic proof system because of this support for unbounded (process) instantiation. For example, tools such as Spin and SMV can only function for systems with a bounded number of process instances.

With my life cycle research, I will therefore incorporate a minimal set of techniques from theorem proving to allow automatic verification. This comes with problems and limitations, which I expect to resolve by employing the specific properties of this problem domain. The result should be a customised theorem checking approach that is usable in a pragmatic object oriented modelling setting. Notably, it should terminate and be fully automatic, and provide graspable feedback to the analyst.
Parameters
Process algebras work with quite primitive actions as elementary process steps. Usually, a set of such actions is defined as a set of labels like a and b. It is usually claimed that making a(1) as well as a(2) and so on actions deals with parameters. I think the problem is more subtle.

First of all, such extensions could easily blow up the set of actions to an infinite set, leading to all sorts of formal problems. Secondly, processes tend to synchronise (read: block if currently not capable to perform) all actions. So, an action a(x) blocks both a(1) and a(2), even if it is known that x=2. If another instance of that process with x=1 synchronises along with such a process, then together they would block all the a(..) actions! Clearly, this approach to parameters is unusable in practice.

In life cycle systems, we resolve these problems by making the set of known actions (also called the alphabet of a process) dependent of the process state and its variable bindings. We can map this back to plain process algebras, but the result is in no way as trivial as usually suggested!
Initiative

Process algebras express the cooperation on the same process step by multiple systems. In such cooperations, there is no process acting as the initiative-taker, at most there is a process which is only capable of performing one particular step. On the other hand, in imperative systems (and thus in most object implementations) there is always a client object sending a message to a server object, clearly a situation where one object (the client) takes the initiative in the cooperation between client and server.

This invocation structure is on one hand useful to model a hierarchy in operations but it is disadvantegeous when this hierarchy is an undesired side-effect. For life cycles, I model the hierarchy in a different way, employing refinement (discussed below), and for the rest I stick to the process algebraic approach of not modelling the initiative.

Refinement

This aspect has not become part of my thesis work due to time constraints -- nevertheless, it's been taken into account all along and can be "plugged in" if so desired.

Refinement is the gradual addition of knowledge to a model when it is considered in more detail. On a high level, a system looks like a workflow system with quite large process steps on them, while on a more detailed level the user interaction may be shown in detail. The technique of refinement keeps track of this added detailing.

Refinement is a well known relation in the formal language Z. It relates two updates by showing that a fine update has at least the same effect as the related coarser one (actually, a choice from several precise definitions of refinement is possible). The Catalysis method is a brave (and reasonably succesful) approach to apply these principles to object modelling.

A case tool which supports refinement (none currently exists as far as I know) would keep track of models at different levels of refinement, and either signal when the refinement relation is broken by editing a model at a certain level of refinement, or perhaps even propagate these edits to models at other levels of refinement to avoid such signals.

A life cycle model which is verified and found globally correct should, in some future, be refined and verified again, repeatedly until all interesting details are modelled. When refinement relations between models are broken, the life cycle system should at least signal such misconduct.

Databases

Although life cycles can be mapped to a multitude of implementations, there is one which deserves specific attention, namely the implementation on top of a database. This is important because databases are the most robust persistent storage mechanisms that we know.

It may seem smart to look into object databases as a life cycle implementation, but I do not think this is the best option. First of all, object databases are not in common use and the standards in this field are still evolving. But most importantly, the map of a life cycle system onto a relation database turns out to be quite natural. The patterns of access that a life cycle system does on a relational database are quite close to the queries and updates modelled by SQL, so a mapping from life cycles to relational database access in SQL is of practical as well as theoretical interest. The theoretical interest lies in the achievement of process-driven access onto relational databases, which have up to now always been accessed with pure data-driven language constructs.