Compositional refinement of interactive systems.
We introduce a method to describe systems and their components by functional specification techniques. We define notions of interface and interaction refinement for interactive systems and their components. These notions of refinement allow us to change both the syntactic (the number of channels and sorts of messages at the channels) and the semantic interface (causality flow between messages and interaction granularity) of an interactive system component. We prove that these notions of refinement are compositional with respect to sequential and parallel composition of system components, communication feedback and recursive declarations of system components. According to these proofs, refinements of networks can be accomplished in a modular way by refining their compponents. We  generalize the notions of refinement to refining contexts. Finally, full abstraction for specifications is defined, and compositionality with respect to this abstraction is shown, too.
Introduction
A distributed interactive system consists of a family of interacting components.
For reducing the complexity of the development of distributed interactive systems
they are developed by a number of successive development steps. By each
step the system is described in more detail and closer to an implementation
level. We speak of levels of abstraction and of stepwise refinement in system
development.
When describing the behavior of system components by logical specification
techniques a simple concept of stepwise refinement is logical implication. Then
a system component specification is a refinement of a component specification,
if it exhibits all specified properties and possibly more. In fact, then refinement
allows the replacement of system specifications by more refined ones exhibiting
more specific properties.
More sophisticated notions of refinement allow to refine a system component
to one exhibiting quite different properties than the original one. In this case,
however, we need a concept relating the behaviors of the refined system component
to behaviors of the original one such that behaviors of the refined system
component can be understood to represent behaviors of the original one. The
behavior of interactive system components is basically given by their interaction
with their environment. Therefore the refinement of system components
basically has to deal with the refinement of their interaction. Such a notion of
interaction refinement is introduced in the following.
Concepts of refinement for software systems have been investigated since
the early 1970s. One of the origins of refinement concepts is data structure
refinement as treated in Hoare's pioneering paper [Hoare 72]. The ideas of
data structure refinement given there were further explored and developed (see,
for instance, [Jones 86], [Broy et al. 86], [Sannella 88], see [Coenen et al. 91]
for a survey). Also the idea of refining interacting systems has been treated
in numerous papers (see, for instance, [Lamport 83], [Abadi, Lamport 90], and
[Back 90]).
Typically distributed interactive systems are composed of a number of components
that interact for instance by exchanging messages or by updating shared
memory. Forms of composition allow to compose systems from smaller ones.
Basic forms of composition for systems are parallel and sequential composition,
communication feedback and recursion.
For a set of forms of composition a method for specifying system components
is called compositional (sometimes also the word modular is used), if the specification
of composed systems can be derived from the specifications of the constituent
components. We call a refinement concept compositional, if refinements
of a composed system are obtained by giving refinements for the components.
Traditionally, compositional notions of specification and refinement for concurrent
systems are considered hard to obtain. For instance, the elegant approach
of [Chandy, Misra 88] is not compositional with respect to liveness properties
and does not provide a compositional notion of refinement. Note, it makes only
sense to talk about compositionality with respect to a set of forms of composi-
tion. Forms of composition of system components define an algebra of systems,
also called a process algebra. Not all approaches to system specifications emphasise
forms of composition for systems. For instance, in state machine oriented
system specifications systems are modelled by state transitions. No particular
forms of composition of system components are used. As a consequence compositionality
is rated less significant there. Approaches being in favor of describing
systems using forms of composition are called "algebraic". A discussion of the
advantages and disadvantages of algebraic versus nonalgebraic approaches can
be found, for instance, in [Janssen et al. 91].
Finding compositional specification methods and compositional interaction
refinement concepts is considered a difficult issue. Compositional refinement
seems especially difficult to achieve for programming languages with tightly
coupled parallelism as it is the case in a "rendezvous" concept (like in CCS
and CSP). In tightly coupled parallelism the actions are directly used for the
synchronization of parallel activities. Therefore the granularity of the actions
cannot be refined, in general, without changing the synchronization structure
(see, for instance, [Aceto, Hennessy 91] and [Vogler 91]).
The presentation of a compositional notion of refinement where the granularity
of interaction can be refined is the overall objective of the following
sections. We use functional, purely descriptive, "nonoperational" specification
techniques. The behavior of distributed systems interacting by communication
over channels is represented by functions processing streams of messages.
Streams of messages represent communication histories on channels. System
component specifications are predicates characterizing sets of stream processing
functions. System components described that way can be composed and decomposed
using the above mentioned forms of composition such as sequential
and parallel composition as well as communication feedback. With these forms
of composition all kinds of finite data processing nets can be described. Allowing
in addition recursive declarations even infinite data processing nets can be
described.
In the following concepts of refinement for interactive system components
are defined that allow one to change both the number of channels of a component
as well as the granularity of the messages sent by it. In particular,
basic theorems are proved that show that the introduced notion of refinement is
compositional for the basic compositional forms as well as for recursive declara-
tions. Accordingly for an arbitrary net of interacting components a refinement
is schematically obtained by giving refinements for its components. The correctness
of such a refinement follows according to the proved theorems schematically
from the correctness proofs for the refinements of the components.
We give examples for illustrating the compositionality of refinement. We
deliberately have chosen very simple examples to keep their specifications small
such that we can concentrate on the refinement aspects. The simplicity of these
examples does not mean that much more complex examples cannot be treated.
Finally we generalize our notion of refinement to refining contexts. Refining
contexts allow refinements of components where the refined presentation of the
input history may depend on the output history. This allows in particular
to understand unreliable components as refinements of reliable components as
long as the refining context takes care of the unreliability. Refining contexts are
represented by predicate transformers with special properties. We give examples
for refining contexts.
In an appendix full abstraction of functional specifications for the considered
composing forms is treated.
Specification
In this section we introduce the basic notions for functional system models and
functional system specifications. In the following we study system components
that exchange messages asynchronously via channels. A stream represents a
communication history for a channel. A stream of messages over a given message
set M is a finite or infinite sequence of messages. We define
We briefly repeat the basic concepts from the theory of streams that we shall
use later. More comprehensive explanations can be found in [Broy 90].
ffl By x - y we denote the result of concatenating two streams x and y. We
assume that x -
ffl By hi we denote the empty stream.
ffl If a stream x is a prefix of a stream y, we write x v y. The relation v is
called prefix order. It is formally specified by
ffl By (M ! ) n we denote tuples of n streams. The prefix ordering on streams
as well as the concatenation of streams is extended to tuples of streams
by elementwise application.
A tuple of finite streams represents a partial communication history for a tuple
of channels. A tuple of infinite streams represents a total communication history
for a tuple of channels.
The behavior of deterministic interactive systems with n input channels and
output channels is modeled by (n; m)-ary stream processing functions
A stream processing function determines the output history for a given communication
history for the input channels in terms of tuples of streams.
Example 1 Stream processing function
Let a set D of data elements be given and let the set of messages M be specified
by:
Here the symbol ? is a signal representing a request. For data elements
a stream processing function
is specified by
The function (c:d) describes the behavior of a simple storage cell that can store
exactly one data element. Initially d is stored. The behavior of the component
modeled by (c:d) can be illustrated by an example input
The function (c:d) is a simple example of a stream processing function where
every input message triggers exactly one output message.
End of example
In the following we use some notions from domain and fixed point theory that
are briefly listed:
ffl A stream processing function is called prefix monotonic, if for all tuples of
streams
We denote the function application f(x) by f:x to avoid brackets.
ffl By tS we denote a least upper bound of a set S, if it exists.
ffl A set S is called directed, if for any pair of elements x and y in S there
exists an upper bound of x and y in S.
ffl A partially ordered set is called complete, if every directed subset has a
least upper bound.
ffl A stream processing function f is called prefix continuous, if f is prefix
monotonic and for every directed set S ' M ! we have:
The set of streams as well as the set of tuples of streams are complete. For
every directed set of streams there exists a least upper bound.
We model the behavior of interactive system components by sets of continuous
(and therefore by definition also monotonic) stream processing functions.
Monotonicity models causality between input and output. Continuity models
the fact that for every behavior the system's reaction to infinite input can be
predicted from the component's reactions to all finite prefixes of this input 1 .
Monotonicity takes care of the fact that in an interactive system output already
produced cannot be changed when further input arrives. The empty stream is to
be seen as representing the information "further communication unspecified".
Note, in the example above by the preimposed monotonicity of the function
(c:d) we conclude otherwise, we could construct a contradiction.
A specification describes a set of stream processing functions that represent
the behaviors of the specified systems. If this set is empty, the specification is
called inconsistent , otherwise it is called consistent . If the set contains exactly
one element, then the specification is called determined. If this set has more
then one element, then the specification is called underdetermined and we also
speak of underspecification. As we shall see, an underdetermined specification
may be refined into a determined one. An underdetermined specification can
also be used to describe hardware or software units that are nondeterministic.
An executable system is called nondeterministic, if it is underdetermined. Then
the underspecification in the description of the behaviors of a nondeterministic
system allows nondeterministic choices carried out during the execution of the
system. In the descriptive modeling of interactive systems there is no difference
in principle between underspecification und the operational notion of nondeter-
minism. In particular, it does not make any difference in such a framework,
whether these nondeterministic choices are taken before the execution starts or
step by step during the execution.
The set of all (n,m)-ary prefix continuous stream processing functions is
denoted by
The number and sorts of input channels as well as output channels of a specification
are called the component's syntactic interface. The behavior, represented
by the set of functions that fulfill a specification, is called the component's semantic
interface. The semantic interface includes in particular the granularity
of the interaction and the causality between input and output. For simplicity
we do not consider specific sort information for the individual channels of components
in the following and just assume M to be a set of messages. However,
all our results carry over straightforwardly to stream processing functions where
more specific sorts are attached to the individual channels.
This does not exclude the specification of more elaborate liveness properties including
fairness. Note, fairness is, in general, a property that has to do with "fair" choices between
an infinite number of behaviors.

Figure

1: Graphical representation of a component Q
A specification of a possibly underdetermined interactive system component
with n input channels and m output channels is modeled by a predicate
characterizing prefix continuous stream processing functions. Q is called an
(n; m)-ary system's specification. A graphical representation of an (n; m)-ary
system component Q is given in Figure 1. The set of specifications of this form
is denoted by
Example 2 Specification
A component called C (for storage Cell) with just one input channel and one
output channel is specified by the predicate C. The component C can be seen
as a simple store that can store exactly one data element. C specifies functions
f of the functionality:
Let the sets D and M be specified as in example 1. If C receives a data element
it sends a copy on its output channels. If it receives a request represented by
the signal ?, it repeats its last data output followed by the signal ? to indicate
that this is repeated output. The signal ? is this way used for indicating a "read
storage content request". The signal ? triggers the read operation. A data
element in the input stream changes the content of the store. The message d
triggers the write operation. Initially the cell carries an arbitrary data element.
This behavior is formalized by the following specification for C:
where the auxiliary function (c:d) is specified as in example 1. Notice that the
data element stored initially is not specified and thus component C is underdetermined

End of example
For a deterministic specification Q where for exactly one function q the predicate
Q is fulfilled, in other words where we have
we often write (by misuse of notation) simply q instead of Q. This way we
identify determined specifications and their behaviors.
m we denote the identity function; that is we assume
We shall drop the index m for I m whenever it can be avoided without confusion.
m we denote the function that produces for every input just
the empty stream as output on all its output channels; that is we define
Similarly we write y m for the unique function in SPF m
other words the
function with m input channels, but with no output channels.
By / L n
m we denote the logically weakest specification, which is the
specification that is fulfilled by all stream processing functions. It is defined by
By n
\Upsilon we denote the function that produces two copies of its input. We have
2n and
\Upsilon
By
n+m we denote the function that permutes its input streams as
Again we shall drop the index n as well as m
\Upsilon whenever it
can be avoided without confusion.
Composition
In this section we introduce the basic forms of composition namely sequential
composition, parallel composition and feedback. These compositional forms are
introduced for functions first and then extended to component specifications.
3.1 Composition of Functions
Given functions
we write
for the sequential composition of the functions f and g which yields a function
in SPF n
Given functions
we write
fkg
for the parallel composition of the functions f and g which yields a function in
We assume that " ; " has higher priority than "k". Given a function
we write
-f
for the feedback of the output streams of function f to its input channels which
yields a function in SPF n
Here fix denotes the fixed point operator associating with any monotonic function
f its least fixed point fix:f . Thus means that y is with respect
the prefix ordering the least solution of the equation We assume
that "-" has higher priority than the binary operators ";" and "k". A graphical
representation for feedback is given in Figure 2.
We obtain a number of useful rules by the fixed point definition of -f . As a
simple consequence of the fixed point characterization, we get the unfold rules:
A graphical representation of the unfold rules for feedback is given in Figure 3.
-f

Figure

2: Graphical representation of feedback
f
f
-f
f
f

Figure

3: Graphical representation of the unfold rules for feedback
f

Figure

4: Graphical representation of semiunfold
A useful rule for feedback is semiunfold that allows one to move components
outside or inside the feedback loop (let g 2 SPF m
A graphical representation for semiunfold is given in Figure 4.
For reasoning about feedback loops and fixed points the following special
case of semiunfold is often useful:
The rule is an instance of semiunfold with y. The correctness of
this rule can also be seen by the following argument: if y is the least fixed point
of
and e y is the least fixed point of
then e
Semiunfold is a powerful rule when reasoning about results of feedback loops.
3.2 Composition of Specifications
We want to compose specifications of components to networks. The forms of
composition introduced for functions can be extended to component specifications
in a straightforward way. Given component specifications
we write
for the predicate in SPEC n
Trivially we have for all specifications Q 2 SPEC n
m the following equations:
Given specifications
we write
QkR
for the predicate in SPEC n1+n2
m1+m2 where
Given specification
we write
for the predicate in SPEC n
For feedback over underdetermined specifications we get the following rules
2 For determined system specifications Q we get the stronger rules
and which do not hold for underdetermined systems, in general. The
erroneous assumption that these rules are valid also for underdetermined systems is the source
for the merge anomaly (see [Brock, Ackermann 81]).
A useful rule for feedback is fusion that allows one to move components that are
not affected by the feedback outside or inside the feedback operator application.
With the help of the basic functions and the forms of composition introduced
so far we can represent all kinds of finite networks of systems (data flow nets) 3 .
The introduced composing forms lead to an algebra of system descriptions.
4 Refinement, Representation, Abstraction
In this section we introduce concepts of refinement for system components both
with respect to the properties of their behaviors as well as with respect to their
syntactic interface and granularity of interaction.
We start by defining a straightforward notion of property refinement for
system component specifications. Then we introduce a notion of refinement
for communication histories. Based on this notion we define the concept of
interaction refinement for interactive components. This notion allows to refine
a component by changing the number of input and output channels as well as
the granularity of the exchanged messages.
4.1 Property Refinement
Specifications are predicates characterizing functions. This leads to a simple
notion of refinement of component specifications by adding logical properties.
Given specifications
e
Q is called a (property) refinement of Q
if for all f 2 SPF n
e
Then we write
e
If e
Q is a property refinement for Q, then e
Q has all the properties Q has and
may be some more. Every behavior that e
Q shows is also a possible behavior of
Q.
3 Of course, the introduced combinatorial style for defining networks is not always very
useful, in practice, since the combinatorial formulas are hard to read. However, we prefer
throughout this report to work with these combinatorial formulas, since this puts emphasis
on the compositional forms and the structure of composition. For practical purposesa notation
with named channels is often more adequate.
All considered composing forms are monotonic for the refinement relation as
indicated by the following theorem.
Theorem 1 (Compositionality of Refinement)
Proof: Straightforward, since all operators for specifications are defined point-wise
on the sets of functions that are specified. 2
A simple example of a property refinement is obtained for the component C as
described in Example 2 on page 8 if we add properties about the data element
initially stored in the cell. A property refinement does not allow one to change
the syntactic interface of a component, however.
4.2 Interaction Refinement
Recall from section 2 that streams model communication histories on channels.
In more sophisticated development steps for a component the number of channels
and the sorts of messages on channels are changed. Such steps do not
represent property refinements. Therefore we introduce a more general notion
of refinement. To be able to do this we study concepts of representation of
communication histories on n channels modeled by a tuple of n streams by
communication histories on m channels modeled by a tuple of m streams.
Tuples of streams y can be seen as representations of tuples of
streams we introduce a mapping ae 2 SPF n
m that associates
with every x its representation. ae is called a representation function. If ae is
injective then it is called a definite representation function. Note, a mapping ae
is injective, if and only if:
If a specification R 2 SPEC n
m is used for the specification of a set of representation
functions, R is called a representation specification.
Example 3 Representation Specification
We specify a representation specification R allowing the representation of streams
of data elements and requests by two separate streams, one of which carries the
requests and the other of which carries the data elements. The representation
functions are mappings ae of the following functionality:
Here
p is used as a separator signal. It can be understood as a time tick that
separates messages. Given streams x and y let [x; y] denote a pair of streams and
the elementwise concatenation of pairs of streams, in other words:
Let T icks be defined by the set of pairs of streams of ticks that have equal
We specify the representation specification R explicitly as follows:
Note, by the monotonicity of the specified functions:
The computation of a representation is illustrated by the following example:
The example demonstrates how the time ticks are used to indicate in the streams
ae(x) the order of the requests relatively to the data messages in the original
stream x.
End of example
The elements in the images of the functions ae with R:ae are called representations.
representation specification) A representation
specification R is called definite, if
In other words R is definite, if different streams x are always differently represented

Obviously, if R is a definite representation specification, then all functions ae
with R:ae are definite. For definite representation specifications for elements x
and x with x 6= x the sets of representation elements
are disjoint. Note, the representation specification given in the example above
is definite.
For every injective function, and thus for every definite representation function
ae, there exists a function ff 2 SPF m
n such that:
The function ff is an inverse to ae on the image of ae. The function ff is called
an abstraction for ae. Notice that ff is not uniquely determined as long as ae is
not surjective. In other words, as long as not all elements in (M are used
as representations of elements in (M ! ) n there may be several functions ff with
A:ff.
The concept of abstractions for definite representation functions can be extended
to definite representation specifications.
m be a definite representation
specification; a function ff 2 SPF m
n with
is called an abstraction function for R.
The existence of abstractions follows from the definition of definite representation
specification. again for definite representation specifications the abstraction
functions ff are uniquely determined only on the image of R, that is on the
union of the images of functions ae with R:ae.
Definition 3 (Abstraction for a definite representation specification)
n be the specification with
Then A is called the abstraction for R.
For consistent definite representation specifications R with abstraction A we
have
If ae; contains all possible choices of representation functions
for the abstraction A.
Example 4 Abstraction
For the representation specification R described in example 3 the abstraction
functions ff are mappings of the functionality:
The specification of A reads as follows.
It is a straightforward rewriting proof that indeed:
The specification A shows a considerable amount of underspecification, since
not all pairs of streams in f?;
are used as representations.
End of example
Parallel and sequential composition of definite representations leads to definite
representations again.
Theorem 2 Let R
be definite representation specifications for
(assuming in the second formula) are definite representation specifications

Proof: Sequential and parallel composition of injective functions leads to injective
functions. 2
Trivially we can obtain the abstractions of the composed representations by
composing the abstractions.
For many applications, representation specifications are neither required to
be determined nor even definite. For an indefinite representation specification
sets of representation elements for different elements are not necessarily disjoint.
Certain representation elements y do occur in several sets of representations for
elements. They ambiguously stand for ("represent") different elements. Such
an element may represent the streams x as well as x, if ae:x = ae:x for functions
ae and ae with R:ae and R:ae. For indefinite representation specifications the represented
elements are not uniquely determined by the representation elements.
A representation element y stands for the set
For a definite representation specification R this set contains exactly one element
while for an indefinite representation specification R this set may contain more
than one element. In the latter case, of course, abstraction functions ff with
I do not exist.
However, even for certain indefinite representations we can introduce the
concept of an abstraction.
Definition 4 (Uniform representation specifications) A consistent specification
m is called a uniform representation specification, if there
exists a specification A 2 SPEC m
n such that for all ae:
The specification A is called again the abstraction for R.
The formula expresses that (R; A) is a left-neutral element for every representation
function in R. Essentially the existence of an abstraction expresses the
following property of R: if for different elements x and x the same representations
are possible, then every representation function maps these elements onto
equal representations. More formally stated, if there exist functions e
ae and ae
with R:eae and R:ae such that
e
then for all functions ae with R:ae:
Thus if elements are identified by some representation functions, this identification
is present in all representation functions. The same amount of information
is "forgotten" by all the representations. The representation functions then are
indefinite in a uniform way. Definite representations are always uniform.
A function is injective, if for all x and x we have:
A function that is not injective ae defines a nontrivial partition on its domain.
A representation specification is uniform if and only if all functions ae with R:ae
define the same partition.
For a uniform representation specification R with abstraction A the product
(R; reflects the underspecification in the choices of the representations provided
by R. If for a function fl with (R; A):fl we have
have the same representations.
Definition 5 (Adequate representation) A uniform representation specification
R with abstraction A is called adequate for a specification Q, if:
Adequacy means that the underspecification in (R; A) does not introduce more
underspecification into Q; R; A than already present in Q. Note, definite representations
are adequate for all specifications Q.
Definition 6 (Interaction refinement) Given representations R 2 SPEC n
m and specifications b
m we say that b
Q is an
interaction refinement of Q for the representation specifications R and R, if
R
R

Figure

5: Commuting diagram of interaction refinement
This definition indicates that we can replace via an interaction refinement a
system of the form Q; R by a refined system of the form R; b
Q. We may think
about the relationship between Q and b
Q as follows: the specification Q specifies
a component on a more abstract level while Q 0 gives a specification for the
component at a more concrete level. Instead of computing at the abstract level
with Q and then translating the output via R onto the output representation
level, we may translate the input by R onto the input representation level and
compute with b
Q. We obtain one of these famous commuting diagrams as shown
in

Figure

5.
Definition 7 (Adequate interaction refinement) The interaction refinement
of Q for the representation specifications R and R is called adequate for
a specification Q, if R is adequate for Q.
For adequate interaction refinements using uniform representation specifications
R with abstraction A 2 SPEC m
since from the interaction refinement property we get
and by the adequacy of R for Q
which shows that R; b
Q; A is a (property) refinement of Q. A graphical illustration
of adequate interaction refinement is shown in Figure 6.
R
Figure

Commuting diagram of interaction refinement
The following table summarizes the most important definitions introduced
so far.
Table of definitions
e
property refinement of Q e
R consistent, definite with abstr. A R;
R uniform with abstraction A R:ae ) R;
R adequate for Q with abs. A Q; R; A ) Q
Inter. refinement b
Q of Q for R; R R; b
Adequate inter. refinement R uniform and adequate for Q
The notion of interaction refinement allows one to change both the syntactic
and the semantic interface. The syntactic interface is determined by the number
and sorts of channels; the semantic interface is determined by the behavior of
the component represented by the causality between input and output and by
the granularity of the interaction.
Example 5 Interaction Refinement
We refine the component C as given in Example 2 into a component b
C that has
instead of one input and one output channel two input and two output channels.
The refinement b
C uses one of its channels carrying the signal ? as a read channel
and one of its channels carrying data as a write channel. Let R and A be given
as specified in the examples above
We specify the interaction refinement b
C of C explicitly. b
C specifies functions
of functionality:
We specify:
where the auxiliary function h is specified by:
It is a straightforward proof to show:
Assume ae with R:ae and h such that there exist f and d with b
C:f and
we prove by induction on the length of the stream x that there exist e ae with R:eae
and c:d as specified in example 1 such that:
ae:(c:d):x
For we obtain: there exists t 2 T icks such that:
e
e
ae:(c:d):x
Now assume the hypothesis holds for x; there exists t 2 T icks:
There exists t 2 T icks:
This concludes the proof for finite streams x. By the continuity of h and ae the
proof is extended to infinite x.
End of example
Continuing with the system development after an adequate interaction refinement
of a component we may decide to leave R and A unchanged and carry on
by just further refining b
Q.
5 Compositionality of Interaction Refinement
Large nets of interacting components can be constructed by the introduced
forms of composition. When refining such large nets it is decisive for keeping
the work manageable that interaction refinements of the components lead to
interaction refinements of the composed system.
In the following we prove that interaction refinement is indeed compositional
for the introduced composing forms that is sequential and parallel composition,
and communication feedback.
5.1 Sequential and Parallel Composition
For systems composed by sequential compositions, refinements can be constructed
by refining their components.
Theorem 3 (Compositionality of refinement, seq. composition) Assume
is an interaction refinement of Q i for the representations R i\Gamma1 and R i
is an interaction refinement of Q for the representations
R 0 and R 2 .
Proof: A straightforward derivation shows the theorem:
interaction refinement of Q 1 g
interaction refinement of Q 2 g
Example 6 Compositionality of Refinement for Sequential Composition
Let C and b
C be specified as in the example above. Of course, we may compose
C as well as b
C sequentially. We define the components CC and d
CC by:
Note, CC is a cell that repeats its last input twice on a signal ?. It is a straight-forward
application of our theorem of the compositionality of refinement that
d
CC is a refinement of CC :
Of course, since R; A = I we also have that R; d
CC;A is a property refinement
of CC.
End of example
Refinement is compositional for parallel composition, too.
Theorem 4 (Compositionality of refinement for parallel composition)
Assume b
is an interaction refinement of Q i for the representations R i and R i
is an interaction refinement of Q 1 kQ 2 for the representations
Proof: A straightforward derivation shows the theorem:
(R
sequential and parallel compositiong
(R
interaction refinement for
sequential and parallel compositiong
(R 1 kR 2 )For sequential and parallel composition compositionality of refinement is quite
straightforward. This can be seen from the simplicity of the proofs.
5.2 Feedback
For the feedback operator, refinement is not immediately compositional. We
do not obtain, in general, that - b
Q is an interaction refinement of -Q for the
representations R and R provided b
Q is an interaction refinement of Q for the
representations RkR and R. This is true, however, if I ) (A; R) (see below).
The reason is as follows. In the feedback loops of - b
Q we cannot be sure that
only representations of streams (i.e. streams in the images of some of the functions
characterized by R) occur. Therefore, we have to give a slightly more
complicated scheme of refinement for feedback.
Theorem 5 (Compositionality of refinement, feedback) Assume b
Q is an
interaction refinement of Q for the representation specifications RkR and R
where R is uniform; then -((IkA; R); b
Q) is an interaction refinement of -Q for
the representations R and R.
Proof: We prove:
(R; -((IkA; R); b
From
(R; -((IkA; R); b
we conclude that there exist functions ae, b
q, ae, and ff such that R:ae, b
Q:bq, R:ae,
and A:ff and furthermore
Q is an interaction refinement of Q for the representations RkR and R
for functions ae with R:ae and ae with R:ae and -
q with b
Q:q there exist functions q
and e ae such that Q:q and R:eae hold and furthermore
ae
Given x, because of the continuity of ae, b
q, ae, and ff, we may define -((Ikff; ae); b q):ae:x
by tby i where
Moreover, because of the continuity of q, we may define ~
ae:(-q):x by ~
ae: ty i where
We prove:
e
ae: t y
by computational induction. We prove by induction on i the following proposition

ae:y
is the least elementg
e
fy 0 is the least elementg
e
fy 0 is the least elementg
fdefinition of b
Assume now the proposition holds for i; then we obtain:
fdefinition of b y
finduction hypothesisg
e
fdefinition of y
e
ae:y
Furthermore we get:
e
fdefinition of y
e
finduction hypothesisg
fdefinition of b y i+2 g
b y i+2
?From this we conclude by the continuity of e
ae that:
and thus
and finally
q))Assuming an adequate refinement allows us to obtain immediately the following
corollary.
Theorem 6 (Compositionality of adequate refinement, feedback) Assume
Q is an adequate interaction refinement of Q for the representations RkR
and R with abstraction A then -( b
Q; A; R) is an interaction refinement of -Q
for the representations R and R.
Proof: Let all the definitions be as in the proof of the previous theorem. Since
the interaction refinement is assumed to be adequate there exists a function e
with Q:q such that
Carrying out the proof of the previous theorem with e q instead of q and ae instead
of e ae we get:
By straightforward computational induction we may prove
This concludes the proof. 2
Assuming that A; R contains the identity as a refinement we can simplify the
refinement of feedback loops.
Theorem 7 Assume b
Q is an interaction refinement of Q for the representations
RkR and R with abstraction A and assume furthermore
I ) A; R
Q is an interaction refinement of -Q for the representations R and R.
Proof: Straightforward deduction shows:
-Q; RNote, even if I is not a refinement of A; R, in other words even if I ) A; R
does not hold, other refinements of A; R may be used to simplify and refine the
term A; R in -((IkA; R); b
Q). By the fusion rule for feedback as introduced in
section 3 we obtain:
This may allow further refinements for b
Example 7 Compositionality of Refinement for Feedback
Let us introduce the component F with two input channels and one output
channel. It specifies functions of the following functionality:
F is specified as follows:
where the auxiliary function g is specified by
It is a straightforward proof that for the specification C as defined in Example
1:
We carry out this proof by induction on the length of the input streams x. We
show that -f fulfills the defining equations for functions c:d in the definition
of C in Example 2. Let f be a function with F:f and g be a function as
specified above in the definition of F . We have to consider just two cases: by
the definition of f there exists g as defined above such that: there exists d:
Induction on the length of x and the continuity of the function g conclude the
proof.
The refinement b
F of F according to the representation specification R from
example 3 specifies functions of the functionality:
It reads as follows:
where the auxiliary function g is specified by
We have (again, this can be proved by a straightforward rewrite proof):
Moreover, we have according to Theorem 5:
and therefore
Note, the refinement is definite and therefore adequate for F . Therefore we may
replace -((IkA; R); b
F ) by -( b
The component -( b
can be further refined by refining A; R. Let us,
therefore, look for a simplification for A; R. We do not have
I ) A; R
since by the monotonicity of all ff with A:ff we have:
(otherwise we obtain a contradiction, since by monotonicity the first elements
of ff(x; d - y) have to coincide for all x and y). Therefore for all ae with R:ae:
This indicates that there are no functions ae and ff with R:ae and A:ff such that
is valid for all x. We therefore cannot simply refine A; R into I.
We continue the refinement by refining p. We take into account properties
of b
F . A simple rewriting proof shows:
Summarizing our refinements we obtain:
This concludes our example of refinement for feedback.
End of example
Recall that every finite network can be represented by an expression that is
built by the introduced forms of composition. The theorems show that a network
can be refined by defining representation specifications for the channels and by
refining all its components. This provides a modular method of refinement for
networks.
6 Recursively defined Specifications
Often the behavior of interactive components is specified by recursion. Given a
function
a recursive declaration of a component specification Q is given by a declaration
based on - :
Recursive specifications are restricted in the following to functions - that exhibit
certain properties.
6.1 Semantics of Recursively Defined Specifications
A function - where
is monotonic with respect to implication, if:
A set of specifications is called a chain, if for all i 2 IN and for all
functions f 2 SPF n
A function - is continuous with respect to implication, if for every chain
Note, the set of all specifications forms a complete lattice.
Definition 8 (Predicate transformer) A predicate transformer is a func-
tion
that is monotonic and continuous with respect to implication (refinement).
Note, if - is defined by - Net(X) is a finite network composed
of basic component specifications by the introduced forms of composition,
then - is a predicate transformer.
A recursive declaration of a component specification Q is given by a defining
equation (often called the fixed point equation) based on a predicate transformer
A predicate Q is called a fixed point of - if:
In general, for a function - there exist several predicates Q that are fixed points
of - . In fixed point theory a partial order on the domain of - is established
such that every monotonic function - has a least fixed point. This fixed point is
associated with the identifier f by a recursive declaration of the form
For defining the semantics of programming languages the choice of the ordering,
which determines the notion of the least fixed point, has to take into account
operational considerations. There the ordering used in the fixed point construction
has to reflect the stepwise approximation of a result by the execution. For
specifications such operational constraints are less significant.
Therefore we choose a very liberal interpretation for recursive declarations
of specifications in the following. For doing so we define the concept of an upper
closure of a specification. The upper closure is again a predicate transformer:
It is defined by the following equation:
Notice that \Xi is a classical closure operator, since it has the following characteristic
properties:
A predicate Q is called upward closed, if by \Xi the least
element\Omega is mapped onto the specification / L that is fulfilled by every function,
that is
From a methodological point of view it is sufficient to restrict
our attention to specifications that are upward closed 4 . This methodological
consideration and the considerable simplification of the formal interpretation
of recursive declarations are the reasons for considering only upward closed
solutions of recursive equations.
A predicate transformer - is called upward closed, if for all predicates Q we
By the recursive declaration
4 Taking the upper closure for a specification may change its safety properties. However,
only safety properties for those behaviors may be changed where the further output, independent
of further input, is empty. A system with such a behavior does not produce a specific
message on an output channel, even, if we increase the streams of the messages on the input
channels. Then what output is produced on that channel obviously is not relevant at all.
we associate with Q the predicate that fulfills the following equation:
where the predicates Q i are specified by:
According to this definition we associate with a recursive declaration the logically
weakest 5 predicate Q such that
The predicate Q is then denoted by fix:- .
6.2 Refinement of Recursively Specified Components
A uniform representation specification R with abstraction A is called adequate
for the predicate transformer - , if for all predicates X:
Adequacy implies that specifications for which R is adequate are mapped by -
onto specifications by for which R is adequate again.
Uniform interaction refinement is compositional for recursive definitions based
on predicate transformers for which the refinement is adequate. again definite
representations are always adequate.
Theorem 8 (Compositionality of refinement for recursion) Let representation
specifications R and R be given, where R is uniform with abstraction
A and adequate for the predicate transformer
For a predicate transformer
where
and for all predicates X; b
(R; b
we have
5 True is considered weaker than false.
Proof: Without loss of generality assume that the predicate transformers - and
are upward closed. Define
We prove:
This proposition is obtained by a straightforward induction proof on i. For
we have to show:
which is trivially true, since /
L holds for all functions. The induction step reads
as follows: from
we conclude by the adequacy of - :
fdefinition of Q
induction hypothesisg
fdefinition of Q
We prove by induction on i:
For we have to prove:
This is part of our premises. Now assume the induction hypothesis holds for
trivially
Therefore, with
by our premise we have:
By the induction hypothesis and by the fact
as can be seen by the derivation
We obtain:
- with
representations R the premise
is always valid as the following straightforward derivation shows:
fdefinition of / Lg
We immediately obtain the following theorem as corollary. It can be useful for
simplifying the refinement of recursion.
Theorem 9 Given the premisses of the theorem above and in addition
I ) A; R
we have
Proof: The theorem is proved by a straightforward deduction:
even if I is not a refinement of A; R, that is even if I ) A; R does not
hold, other refinements of A; R may be used to simplify the term A; R in the
specification.
Example 8 Compositionality of Refinement for Recursion
Of course, instead of giving a feedback loop as in example 7 above we may also
define an infinite network recursively by 6 :
where
again we obtain (as a straightforward proof along the lines of the proof above
for
It is also a straightforward proof to show that
(R; b
where
F
Therefore we have
where
by our compositionality results. again A; R can be replaced by its refinement
as shown above.
End of example
Using recursion we may define even infinite nets. The theorem above shows
that a refinement of an infinite net that is described by a recursive equation is
obtained by refinement of the components of the net.
7 Predicate Transformers as Refinements
So far we have considered the refinement of components by refining on one hand
their tuples of input and on the other hand their tuples of output streams. A
more general notion of refinement is obtained by considering predicate transformers
themselves as refinements.
Definition 9 (Refining context) A predicate transformer
6 The predicate transformer - is obtained by the unfold rule for feedback
is called a refining context, if there exists a mapping
called abstracting context such that for all predicates X we have:
Refining contexts can be used to define a quite general notion of refinement.
(Refinement by refining contexts) Let R be a refining context
with abstracting context A. A specification b
Q is then called a refinement for
the abstracting context A of the specification Q, if:
Note, R:Q is a refinement of the specification Q for the abstracting context A.
Refining contexts may be defined by the compositional forms introduced in the
previous sections.
Example 9 Refining Contexts
For component specifications Y with one input channel and two output channels
we define a predicate transformer
1by the equation:
where the component P specifies functions
A graphical representation of A:Y is given in Figure 7. Let P be specified by:
For a component specification X with one input channel and one output
channel we define a predicate transformer:
where the component Q specifies functions
Y
A:Y

Figure

7: Graphical representation of A:Y
Let Q be specified by:
stand for the finite stream of length k containing just copies of the
message m. To show that A and R define a refining context we show that:
which is equivalent to showing that for all specifications X:
This is equivalent to:
which is equivalent to the formula:
which can be shown by a proof based on the specifications of P and Q. Let
. stand for (I 2 ky) and & stand for the function (ykI 1 ). For functions p and q
with P:p and Q:q there exists k 2 IN such that 8i 2 IN with i - k:
This can be shown by a straightforward proof of induction on i. By this we
obtain for
Furthermore:
We obtain
By induction on the length on x and the continuity of the involved functions
the proposition above is proved.
End of example
Context refinement is indeed a generalization of interaction refinement. Given
two pairs of definite representation and abstraction specifications R; A and R; A
by
a refining context and an abstracting context is defined, since
Refining contexts lead to a more general notion of refinement than interaction
refinement. There are specifications Q and b
Q such that there do not exist
consistent specifications R and A where
but there may exist refining contexts R and A such that
Refining contexts may support the usage of sophisticated feedback loops between
the refined system and the refining context. This way a dependency between
the representation of the input history and the output history can be achieved.
QbHe

Figure

8: Graphical representation of the master/slave system
A very general form of a refining context is obtained by a special operator
for forming networks called master/slave systems. For notational convenience
we introduce a special notation for master/slave systems. A graphical representation
of master/slave systems is given in Figure 8. A master/slave system is
denoted by QbHe. It consists of two components Q and H called the master
k+n and the slave H 2 SPEC n
m . Then QbHe 2 SPEC i
. All the
input of the slave is comes via the master and all the output of the slave goes
to the master. The master/slave system is defined as follows:
or in a more readable notation:
where 8x;
We can define a refining context and an abstracting context based on the mas-
ter/slave system concept: we look for predicate transformers
with abstracting context
and for specifications V 2 SPEC i+m
k+n and W 2 SPEC n+k
m+i where the refining
context and the abstracting context are specified as follows:
y
z

Figure

9: Graphical representation of the cooperator
and the following requirement is fulfilled:
We give an analysis of this requirement based on further form of composition
called a cooperator. The cooperator is denoted by
. For
specifications
m+k the cooperator is defined as
follows:
m+m
where
A graphical presentation of the cooperator is given in Figure 9.
A straightforward rewriting shows that the cooperator is indeed a generalization
of the master/slave. For H 2 SPEC k
In particular we obtain:
and therefore the condition:
reads as follows:
The following theorem gives an analysis for the component W
Theorem 10 The implication
implies
Recall,
just swaps its input streams.
Proof: By the definition of cooperation we may conclude that for every function
i and every function - such that W:i and V:- and for every f where X:f there
exists a function e
f where X: e
f such that:
f:x
this formula is true for all specifications X and therefore also for definite
specifications, the formula holds for all functions f where in addition
f .
We obtain for the constant function f with z = f:x for all x and for all z:
The equation above therefore simplifies to
Now we prove that from this formula we can conclude:
We do the proof by contradiction. Assume there exists x such
and x 6= z. Then we can choose a function f such that f:x 6= f:z. This concludes
the proof of the theorem. 2
By the concept of refining contexts we then may consider the refined system
QbW bV bHeee
The refinement of this refined network can then be continued by refining V bHe
and leaving its environment QbW b:::ee as it is.
There is a remarkable relationship between master/slave systems and the
system structures studied in rely/guarantee specification techniques as advocated
among others in [Abadi, Lamport 90]. The master can be seen as the
environment and the slave as the system. This indicates that the master/slave
situation models a very general form of composition. Every net with a subnet
H can be understood as a master/slave system QbHe where Q denotes the surrounding
net, the environment, of H. This form of networks is generalized by
the cooperator as a composing form, where in contrast to master/slave systems
the situation is fully symmetric.
The cooperating components Q and Q in Q
can be seen as their
mutual environments. The concept of cooperation is the most general notion of
a composing form for components. All composing forms considered so far are
just special cases of cooperation; for
k we obtain:
Let a net N be given with the set \Gamma of components. Every partition of \Gamma into
two disjoint sets of components leads to a partition of the net into two disjoint
subnets say Q and Q such that the net is equal to Q
the number of channels in N leading from Q to Q and k denotes the number
of channels leading from Q to Q. Then both subnets can be further refined
independently.
8 Conclusion
The notion of compositional refinement depends on the operators, the composing
forms, considered for composing a system. Compositionality is not a goal per
se. It is helpful for performing global refinements by local refinements. Refining
contexts, master slave systems and the cooperator are of additional help for
structuring and restructuring a system for allowing local refinements.
The previous sections have demonstrated that using functional techniques a
compositional notion of interaction refinement is achieved. The refinement of
the components of a large net can be mechanically transformed into a refinement
of the entire net.
Throughout this paper only notions of refinement have been treated that can
be expressed by continuous representation and abstraction functions. This is
very much along the lines of [CIP 84] and [Broy et al. 86] where it is considered
as an important methodological simplification, if the abstraction and representation
functions can be used at the level of specified functions. There are interesting
examples of refinement, however, where the representation functions are
not monotonic (see the representation functions obtained by the introduction
of time in [Broy 90]). A compositional treatment of the refinement of feedback
loops in these cases remains as an open problem.

Acknowledgement

This work has been carried out during my stay at DIGITAL
Equipment Corporation Systems Research Center. The excellent working
environment and stimulating discussions with the colleagues at SRC, in particular
Jim Horning, Leslie Lamport, and Mart'in Abadi are gratefully acknowledged.
I thank Claus Dendorfer, Leslie Lamport, and Cynthia Hibbard for their careful
reading of a version of the manuscript and their most useful comments.
A

Appendix

Full Abstraction
Looking at functional specifications one may realize that sometimes they specify
more properties than one might be interested in and that one may observe
under the considered compositional forms. Basically we are interested in two
observations for a given specification Q for a function f with Q:f and input
streams x. The first one is straightforward: we are interested in the output
streams y where
But, in addition, for controlling the behavior of components especially within
feedback loops we are interested in causality. Given just a finite prefix. e
x of the
considered input streams x, causality of input with respect to output determines
how much output (which by monotonicity of f is a prefix of y) is guaranteed by
f .
More technically, we may represent the behavior of a system component by
all observations about the system represented by pairs of chains of input and
corresponding output streams.
A set fx is called a chain, if for all i 2 IN we have
Given a specification Q 2 SPEC n
m , a pair of chains
is called an observation about Q, if there exists a function f with Q:f such that
for all
and
The behavior of a system component specified by Q then can be represented
by all observations about Q. Unfortunately, there exist functional specifications
which show the same set of observations, but, nevertheless, characterize different
sets of functions. For an example we refer to [Broy 90].
Fortunately such functional specifications can be mapped easily onto functional
specifications where the set of specified functions is exactly the one characterized
by its set of observations. For this reason we introduce a predicate
transformer
that maps a specification on its abstract counterpart. This predicate transformer
basically constructs for a given predicate Q a predicate \Delta:Q that is fulfilled
exactly for those continuous functions that can be obtained by a combination
of the graphs of functions from the set of functions specified by Q. We define
where
By this definition we obtain immediately the monotonicity and the closure property
of the predicate transformer \Delta.
Theorem 11 (Closure property of the predicate transformer \Delta)
Proof: Straightforward, since Q:f occurs positively in the definition of \Delta:Q,
specification Q is called fully abstract, if
We may redefine our compositional forms such that the operators deliver always
fully abstract specifications:
All the results obtained so far carry over to the abstract view by the monotonicity
of \Delta, and by the fact that we have
Furthermore, given an upward closed predicate transformer - we have: if Q is
the least solution of
then \Delta:Q is the least solution of
The proof is straightforward. Note, by this concept of abstraction we may obtain
I
in cases where I ) A; R does not hold. This allows additional simplifications
of network refinements.
Note, full abstraction is a relative notion. It is determined by the basic
concept of observability and the composing forms. In the presence of refinement
it is unclear whether full abstraction as defined above is appropriate. We have:
However, if a component Q is used twice in a network - [Q], then we do not have,
in general, that for (determined) refinements e
Q of \Delta:Q there exist (determined)
refinements b
Q of Q such that:
Therefore, when using more sophisticated forms of refinement the introduced
notion of full abstraction might not always be adequate.


--R

Adding Action Refinement to a Finite Process Algebra.
Composing Specifications.
Refinement Calculus
Refinement Calculus
Stepwise Refinement of Distributed Systems.
Scenarios: A Model of Nondeterminate Computation.
Algebraic implementations preserve program correctness.
Functional Specification of Time Sensitive Communicating Systems.
Algebraic methods for program construc- tion: The project CIP
Parallel Program Design: A Foundation.
Assertional Data Reification Proofs: Survey and Perspective.
Action Systems and Action Refinement in the Development of Parallel Systems - An Algebraic Approach
Specifying concurrent program modules.
Proofs of Correctness of Data Repre- sentations
Systematic Program Development Using VDM.
A Survey of Formal Software Development Methods.
Bisimulation and Action Refinement.
--TR
Algebraic implementations preserve program correctness
Systematic software development using VDM
Parallel program design: a foundation
Refinement calculus, part I: sequential nondeterministic programs
Refinement calculus, part II: parallel and reactive programs
Functional specification of time sensitive communicating systems
A logical view of composition and refinement
Adding action refinement to a finite process algebra
Bisimulation and action refinement
Composing specifications
Specifying Concurrent Program Modules
Scenarios

--CTR
Bernhard Thalheim, Component development and construction for database design, Data & Knowledge Engineering, v.54 n.1, p.77-95, July 2005
Manfred Broy, Object-oriented programming and software development: a critical assessment, Programming methodology, Springer-Verlag New York, Inc., New York, NY,
Bernhard Thalheim, Database component ware, Proceedings of the fourteenth Australasian database conference, p.13-26, February 01, 2003, Adelaide, Australia
Antje Dsterhft , Bernhard Thalheim, Linguistic based search facilities in snowflake-like database schemes, Data & Knowledge Engineering, v.48 n.2, p.177-198, February 2004
Einar Broch Johnsen , Christoph Lth, Abstracting refinements for transformation, Nordic Journal of Computing, v.10 n.4, p.313-336, December
Manfred Broy, Toward a Mathematical Foundation of Software Engineering Methods, IEEE Transactions on Software Engineering, v.27 n.1, p.42-57, January 2001
Rimvydas Rukenas, A rigorous environment for development of concurrent systems, Nordic Journal of Computing, v.11 n.2, p.165-193, Summer 2004
Marco Antonio Barbosa, A refinement calculus for software components and architectures, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
specification;interactive systems;refinement