ARTIST2 - MOTIVES

Trento - Italy, February 19-23, 2007

Model Transformation and

Foundations of UML
Model
Transformation
Reiko Heckel
University of Leicester, UK

Motivation: Model-driven Engineering

Focus and primary artifacts are

models instead of programs

expressiveness and
complexity

execution and
optimisation

well-definedness

preservation of semantics

Core activities include

maintaining consistency

evolution

translation

execution

of transformations

of models

A math. foundation is
needed for studying

These are examples of model

transformations

Graph transformations can

be one such foundation

Outline

Graph Transformation

why it is fun

how it works

Semantics-preserving Model Transformation

Why it is fun: Programming By Example

StageCast ([Link]): a visual programming
environment for kids (from 8 years on), based on

behavioral rules associated to graphical objects

visual pattern matching

simple control structures (priorities, sequence, choice, ...)

external keyboard control

intuitive rule-based behavior modelling

Next: abstract from concrete visual presentation

States of the PacMan Game:

Graph-Based Presentation
:Ghost
:Field

:Field

:Field

:Field

:Field

:PacMan
marbles=3
:Marble

:Field

instance graph
(represents a
single state;
abstracts from
spatial layout)

typing

Ghost *

1 * PacMan
Field
marbles:int
1
*
Marble

type graph
(specifies legal
instance graphs)

Rules of the PacMan Game:

Graph-Based Presentation, PacMan
pm:PacMan
marbles=m

:Marble

f1:Field

f2:Field

pm:PacMan
f1:Field

pm:PacMan
marbles=m+1

collect
f1:Field

pm:PacMan

movePM
f2:Field

f2:Field

f1:Field

f2:Field

Rules of the PacMan Game:

Graph-Based Presentation, Ghost
g:Ghost

:PacMan

f1:Field

f2:Field

g:Ghost
f1:Field

g:Ghost

kill
f1:Field

g:Ghost

moveGhost
f2:Field

f2:Field

f1:Field

f2:Field

Outline

Graph Transformation

why it is fun

how it works

Semantics-preserving Model Transformation

A Basic Formalism: Typed Graphs

Directed graphs

multiple parallel edges

:Field

g:Ghost

:Field

undirected edges as
pairs of directed ones

:Field

:Field

f:Field

Graph homomorphism as
mappings preserving
source and target

:Field

Typed graphs given by

fixed type graph TG

instance graphs G
typed over TG by
homomorphism g

Ghost

Field
Marble

PacMan
marbles:int

TG

Rules
p: L R with L R well-defined, in different
presentations

like above (cf. PacMan example)

with L R explicit [DPO]: L K R

pm:PacMan
f1:Field

f2:Field

movePM:

pm:PacMan
f1:Field

f2:Field

Rules
p: L R with L R well-defined, in different
presentations

like above (cf. PacMan example)

with L R explicit [DPO]: L K R

with L, R integrated [UML, Fujaba]:

L R and marking

L - R as destroyed

R - L as new

movePM:

pm:PacMan

{destroyed}

f1:Field

{new}

f2:Field

Transformation Step
pm:PacMan
m1:Marble
marbles=m
f2:Field

f1:Field

pm:PacMan
marbles=m+1
f2:Field

oL

f1:Field

oR

f1:Field

m1:Marble

f2:Field

pm:PacMan
marbles=3

f2:Field

f3:Field

m2:Marble

f3:Field

f1:Field

pm:PacMan
marbles=4

m2:Marble

1.

select rule p: L R ; occurrence oL: L G

2.

remove from G the occurrence of L\ R

3.

add to result a copy of R \ L

Semantic Questions: Dangling Edges

a:A

a:A

conservative solution: application is forbidden

:B

invertible transformations, no side-effects

radical solution: delete dangling edges

more complex behavior, requires explicit control

A bit of History
Chomsky
Grammars

Term
Rewriting

Petri
Nets

Graph Transformation and Graph Grammars

Diagram
Languages

Models of
Computation

Behaviour
Modelling and
Visual Programming

Outline

Graph Transformation

why it is fun

how it works

Semantics-preserving
Model Transformation

operational

denotational

operational
semantics
transformation
Abstract
Syntax
denotational
semantics
Semantic
Domain

Example: Executable Business Process

refactoring of business
processes, replacing
centralised by distributed
execution

Warehouse

Receive
order

How to demonstrate
preservation of behaviour?
1.

specify operational
semantics of processes

2.

define transformations

3.

show that transformations

preserve semantics

Office

Shipment

Undo
order

operational
semantics

Operational Semantics: Idea

diagram syntax plus runtime state

GT rules to model state transitions

Abstract
Syntax

Operational Semantics: Formally

GTS = (TG, P) with start graph G0
defines transition system
LTS(GTS, G0) = (S, L, )
taking

as states S all graphs reachable from G0

observations on rules as labels

transformations as transitions

response

Type Graph: Metamodel

with runtime state
Elem

op: String
id: String

to

responsible

Basic

Structured

op: String

Invoke

request

Orch
name: String

src
corresponds Edge tar Node

Switch

Msg

from
current

Abstract
Syntax

Reply

partner

operational
semantics

Rules: Invoke another Service

Abstract
Syntax

e:Edge

tar

i:Invoke

partner

current

o1:Orch

o2:Orch

e:Edge

tar

i:Invoke

current

req([Link], [Link])

partner

request

from m:Msg
to

o1:Orch

id=new()
op=[Link]

o2:Orch

operational
semantics

Rules: Answer the Invocation

e:Edge

tar

r:Reply

src

Abstract
Syntax

e:Edge

current

o1:Orch

to m1:Msg from
op=[Link]

o2:Orch
e:Edge

tar

r:Reply

src

e:Edge

current
reply([Link], [Link], [Link])

o1:Orch
from

to m1:Msgfrom
op=[Link]

response

m2:Msg
id=new()
op=[Link]

o2:Orch
to

operational
semantics

Rules: Receive the Response

current

i:Invoke

src

request
from

o1:Orch
to

Abstract
Syntax

e:Edge

partner
to

m1:Msg

o2:Orch

response
from

m2:Msg

i:Invoke
resp([Link], [Link])

current

o1:Orch

src

e:Edge

partner

o2:Orch

Simulation

o1:Orch

current

:Edge

tar

tar

i:Invoke

request
from

:Edge
partner

o2:Orch

current

r:Reply

src

src

:Edge

:Edge

to

to

m1:Msg

m2:Msg

op=[Link]

from

op=[Link]

response
Observations:req([Link], [Link]);
reply([Link], [Link], [Link]);
resp([Link], [Link])

Refactoring Executable Processes

Orch 1

Orch1

Orch 2

delegate

Orch 2
<<receive>>
op

<<invoke>>
[Link]

<<reply>>
op

replace local control flow by message passing

Semantic Compatibility
Processes P1 and P2 are semantically compatible if they are
weakly bisimilar after hiding labels not in alph(P1) alph(P2)
Show for trafo P1 P2 that P2 simulates P1, i.e.

P1obs Q1 implies P2 obs Q2

Q2 simulates Q1

and vice versa.

P1

obs

Q1

Approach:

mixed (local) confluence

critical pair analysis

P2

obs

Q2

Critical Pairs and Local Confluence

a pair of rules (p1, p2) in a minimal conflict

situation
constructed by overlapping their left-hand sides
so that they intersect in items to be deleted
system is locally confluent
if all critical pairs are

p1

G1

p2

G2

* H *

Critical Pair Analysis in AGG

delegate vs operational rules

Critical Pair
LHS of
invoke vs delegate

delete-use-conflict

Outline

Graph Transformation

why it is fun

how it works

Semantics-preserving
Model Transformation

operational
denotational

operational
semantics
transformation
Abstract
Syntax
denotational
semantics
Semantic
Domain

Process Improvement
Motivation:

transform process to
increase flexibility,
performance, ...

preserve behaviour!

Aim: rule-level
verification

Rule-level Verification
L

r/o
G
s(L)

s(G)

semantic domain

Approach:

check for each rule r if s(L) R s(R)

make sure that s(L) R s(R) implies s(G) R s(H)

H
s(R)
s(H)

Works if

we select semantic domain SD where relation R is

compositional

trace or failures equivalence or refinement in CSP is

closed under context

we can show that semantic mapping

s: AS SD is compositional

maps union of graphs to composition of CSP processes

use GT to define mapping s

Context-Free Graph Grammar

Abstract
Syntax

Concrete syntax of well-structured activity diagrams

Start graph:

Act

Productions in EBNF-like notation:

in

in

in
[not c]

[c]

in

Act
Act

Act

::=

Act

do something

Act
out

ou
t

out

out

Analysis

0
receive order

check availability

[product available]

[product not
available]

calculate prize
notify client

8
send receipt

2
5

Pair Grammar

Abstract
Syntax

Source: wellstructured
activity
diagrams
Target: CSP

denotational
semantics
Semantic
Domain

in

in

in
[not c]

[c]

A:Act

Proc(A)
in

A1:Act
A:Act

A1:Act

::=

A2:Act

do something

A2:Act
out

Proc(A)

ou
t
Proc(A1) ;
::=
Proc(A2)

out
if [c] then Proc(A1)
else Proc(A2)

out

do something

Synthesis

0
receive order

Proc(A0)

Proc(A1) ; Proc(A2)

Proc(A3) ;
Proc (A4) ;
if [product available]
then Proc(A5)
else Proc(A8)

check availability

[product available]

[product not
available]

calculate prize

receive order ;
check availability ;
if [product available]
then calculate prize ;
send receipt
else notify client

notify client

8
send receipt

2
5

Good Enough ?

Visual

abstract syntax or
concrete syntax templates

Bi-directional

swap source and target

grammars

Declarative

Expressive ?

Traceable ?

context-free graph
languages only

through naming
conventions

Efficient ?

NP complete parsing
problem

Triple Graph Grammars (see Andys lecture)

Challenge: verify compositionality for more complex mappings

Relevant Theory
Chomsky
Grammars

Term
Rewriting

Petri
Nets

Graph Transformation and Graph Grammars

Formal language Well-definedness Concurrency theory

Causality and conflict
Termination
theory of graphs;
Confluence

Diagram compiler Semantics of

process calculi
generators

Processes, unfoldings
Event-structures
Stochastic concepts
Verification,