Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 446 2009-10-2
446 Model-Based Design for Embedded Systems
These statements declare a unary function vertex and a binary function
edge. The argument to vertex must be an integer, while the arguments
to edge must be vertex terms. These typed functions are undefined when
applied to badly typed values, otherwise they behave exactly like uninter-
preted functions.
This enrichment of the term algebra semantics with types leads naturally
to an ordersorted-type system. We formalize this type system now. An order-
sorted alphabet Σ
⊆
is a structure:
Σ
⊆
=I, , (Σ
i
)
i∈I
 (14.5)
The set I, called the index set, is a set of sort names (alphabet names). Associ-
ated with each sort name i ∈ I is a set of constants Σ
i
called the carrier of i.An
order-sorted alphabet has the following properties:
Σ =

i∈I
Σ
i
,


i  j

⇔

Σ
i
⊆ Σ
j

(14.6)
In other words, Σ is the union of smaller alphabets and alphabets are ordered
by set inclusion; the sub-typing relation  is set inclusion. A type τ is a term
constructed from function symbols and elements of I or the special top-type
. Each type τ identifies a subset τ⊆ T
Υ
(Σ) according to
1. The top type is the entire term algebra:
= T
Υ
(Σ) (14.7)
2. A sort name τ ∈ I is just the carrier set Σ
τ
:
∀τ ∈ I, τ= Σ
τ
(14.8)
3. Otherwise τ = f(τ
1
, τ
2

, , τ
n
) where f is an n-ary function symbol:
τ=
⎧
⎨
⎩
v ∈ T
Υ
(Σ)






v = f(v
1
, v
2
, , v
n
)∧

1≤j≤n
v
j
∈ τ
j


⎫
⎬
⎭
(14.9)
The sub-typing relation  is extended to arbitrary types:
∀τ
p
, τ
q

τ
p
 τ
q

⇔

τ
p
⊆ τ
q


(14.10)
14.3.2.3 Expressive Constraints with Logic Programming
Structural semantics often contain complex conformance rules; these rules
cannot be captured by simple-type systems. One common solution to this
problem is to provide an additional constraint language for expressing syn-
tactic rules such as the Object Constraint Language (OCL) [33]. Unlike other
approaches, we choose LP to represent syntactic constraints because

Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 447 2009-10-2
Semantics of Domain-Specific Modeling Languages 447
1. LP extends our term algebra semantics while supporting declarative
rules.
2. The fragment of LP supported by
FORMULA is equivalent to full first-order
logic over term algebras thereby providing expressiveness [13].
3. Unlike purely algebraic specifications, there is a clear execution seman-
tics for logic programs making it possible to specify model transforma-
tions in the same framework.
4. Many analysis techniques are known for logic programs; we have
adapted these to analyze
FORMULA specifications [25].
FORMULA supports a class of logic programs with the following properties:
(1) expressions may contain uninterpreted function symbols, (2) the seman-
tics for negation is negation as finite failure, and (3) all logic programs must be
non-recursive and stratified. We summarize this class now.
Definitions. Let V be a countably infinite alphabet of variables disjoint from
basic constants: V ∩ Σ =∅. Let the term algebra T
v
be an extension of a
term algebra with these variables: T
Υ
(Σ ∪ V). For simplification, we write T
g
for T
Υ
(Σ). A term t is called a ground term if it does not contain any vari-
ables; T
g

is the set of all ground terms. A substitution φ replaces variables
with ground terms. Formally, φ is a homomorphism from terms (with vari-
ables) to ground terms that fixes constants. We write φ(t) for the ground term
formed by replacing every variable x in t with φ(x). Two terms s and t unify
if there exists a substitution φ such that φ(s) = φ(t).
Expressions. Logic programs are built from expressions of the form:
h ← t
1
, t
2
, , t
n
, ¬s
1
, ¬s
2
, , ¬s
m
.
where h ∈T
v
is a term called the head.Thesets{t
1
, , t
n
}⊆T
v
and
{s
1

, , s
m
}⊆T
v
are sets of terms collectively called the body. Each t
i
is called
a positive term and each s
j
is called a negative term.Inthek
th
expression an
implicit relation symbol R
k
surrounds each body term; an implicit relation
symbol R

k
surrounds the head term h.
R

k
(h) ← R
k
(t
1
), R
k
(t
2

), , R
k
(t
n
), ¬R
k
(s
1
), ¬R
k
(s
2
), , ¬R
k
(s
m
).
Intuitively, this expression means the following: If there exists a substitution
φ so that each φ(t
i
) is in relation R
k
and for each s
j
there is no substitution φ

that places φ

(s
j

) in R
k
, then add φ(h) to the relation R

k
[1].
The semantics of LP languages vary on how this intuition is formalized.
The formalization must take into account the generality of allowed expres-
sions and the mechanism by which the implicit relations are calculated. The
fragment we utilize is a well-behaved fragment called non-recursive and
stratified LP with negation as finite failure. Logic programs of this frag-
ment always terminate and have expressive power equivalent to first-order
logic.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 448 2009-10-2
448 Model-Based Design for Embedded Systems
Semantics. Let ≺ be a relation on expressions. Expressions e
i
and e
j
are
related (e
i
≺ e
j
) if the head h of e
i
unifies with some term in the body of
expression e
j
, regardless of whether the body term is positive or negative. A

finite collection of expressions (e
i
)
i∈E
is non-recursive and stratified if ≺is an
acyclic relation.
Let o : E → Z
+
∪{0}be an ordering of non-recursive and stratified expres-
sions that respects ≺:
∀i, j,∈ E, (e
i
≺ e
j
) ⇒ o(i)<o(j). (14.11)
Using this ordering, the k
th
expression tests for the presence and absence of
body terms in a relation R
o(k)
. Whenever these tests succeed for some substi-
tution φ, then the substituted head term φ(h) is added to the relation R
o(k)+1
.
R
o(k)+1
(h) ← R
o(k)
(t
1

), , ¬R
o(k)
(s
1
), (14.12)
This rule is used in conjunction with the general rule: Whatever can be found
in relation R
i
can also be found in relation R
i+1
.
∀i ≥ 0, (t ∈ R
i
) ⇒ (t ∈ R
i+1
). (14.13)
Additionally, LP uses the closed world assumption: t ∈ R
i
if and only if it is in
R
0
or it is placed in R
i
by the application of rules (14.12) or (14.13). The input
to a logic program is the initial relation R
0
. The program executes by working
from smallest-to-largest expressions, as ordered by o, building the contents
of the relations along the way. Note that for non-recursive and stratified pro-
grams the choice of o does not affect the results of the logic program.

Negation as Failure. Negation as failure (NAF) allows an expression e
k
to test
for the absence of some terms in the relation R
o(k)
. Developing a semantics for
NAF in arbitrary logic programs has been one of the biggest challenges for
the LP community. Fortunately NAF is well behaved in our fragment. The
only question is how to interpret variables appearing in negative terms. For
example:
f(x) ← g(x); ¬h(x,y). (14.14)
We use the interpretation consistent with the SLDNF-resolution (Selective
Linear Definite clause resolution with NAF) procedure found in standard
PROLOG: The variable y is effectively a wild card, so the body succeeds if
there exists a substitution φ such that φ(g(x)) ∈ R
o(k)
and for all other substi-
tutions φ

, φ

(φ(h(x, y)) /∈ R
o(k)
. Substitutions fix constants, so this is equiva-
lent to the condition that ∃φ,∀φ

, f(φ(x)) ∈ R
o(k)
∧h(φ(x), φ


(y)) /∈ R
o(k)
.More
generally, let P be the set of all positive terms and N be the set of all negative
terms in an expression. We write φ(T) for the application of a substitution to
each term t ∈ T. The body of an expression succeeds if
∃φ, ∀φ

, φ(P) ⊆ R
o(k)
∧φ

(φ(N)) ∩R
o(k)
=∅. (14.15)
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 449 2009-10-2
Semantics of Domain-Specific Modeling Languages 449
We are interested in finite relations R
k
, so we require that the variables in the
head term h appear in some positive term t ∈ P.
Queries. A query is just an expression that does not add new terms to any
relation. In
FORMULA each query q has a name, which is a boolean variable that
is true whenever the body of the query is satisfied, otherwise it is false:
qname :? t
1
, t
2
, , t

n
, ¬s
1
, ¬s
2
, , ¬s
n
. (14.16)
Queries are identified by the special operator “:?”. Since queries do not mod-
ify any relations, it is never the case that q
i
≺ e
j
. Otherwise, queries are
ordered like clauses for the purpose of execution. For the sake of conve-
nience, queries can be composed with standard boolean operators into new
queries, but this is only syntactic sugar.
Domain Constraints. We use LP to capture the complex rules of DSML
structural semantics. This is done by writing a special query called
conforms, which evaluates to true exactly when a syntactic instance satisfies
all the rules. The process for testing whether a syntactic instance X conforms
to the syntax is
1. Set R
0
= X
2. Run the logic program
3. Check if conforms evaluates to true
14.3.3 An Introduction to Domains and Models
LP provides the basis for capturing structural semantics. However, in its raw
form it lacks the concepts of encapsulation and composition required by a

formal modeling framework.
FORMULA also provides these key encapsulation
and composition concepts. In the following sections, we present these key
concepts through examples.
FORMULA specifications are separated into logical units called domains.A
domain encapsulates a set of function symbols, LP expressions, and queries
all used to describe a structural semantics. Declarations within a domain are
scoped to that domain and are not visible to other parts of the specifica-
tion. Structuring the specification into domains is not optional. A model is
a a finite set of ground terms built from the uninterpreted functions of some
domain. A model is well-formed if its set of terms satisfies the constraints of
the domain used to construct it. Intuitively, a domain represents a family of
models by providing functions and constraints.
In this introduction we will develop a
FORMULA specification for the struc-
tural semantics of a finite state machine (FSM) DSML. The FSM abstraction
is a well-studied formalism that abstracts away from the idiosyncrasies of
programming languages. Using FSMs we can view a computation as a pro-
gression through a finite sequence of states. This progression is triggered by
external stimuli called events. The FSM abstraction is still important to many
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 450 2009-10-2
450 Model-Based Design for Embedded Systems
S
1
S
2
f
e
FIGURE 14.2
Example of a

FSM.
engineering communities because of the verification and
optimization techniques known for FSMs.
Figure 14.2 shows a sample FSM with two states S
1
and S
2
. The small black circle indicates that S
1
is the ini-
tial (starting) state for the FSM. The arrow from S
1
to S
2
is a transition that is taken if the FSM is in state S
1
and
receives event e. The transition from S
2
to S
1
is triggered
by the event f.
We begin by (partially) specifying the non-deterministic
version of the FSM abstraction, called the non-deterministic
finite automaton (NFA) abstraction. NFAs may have states with many transi-
tions triggered by the same event. In this case, the NFA non-deterministically
chooses which transition to take. Figure 14.3 shows the partial
FORMULA spec-
ification. Line 2 declares a domain called NFA, which acts as a container

for the NFA abstraction. The building blocks of an NFA are the functions
declared in Lines 4–7. Line 4 defines the Event function, which takes one
argument providing the name of the event. The form of data used to repre-
sent this name is irrelevant, so we give it the type Any. The argument for the
State function is also the name of the state. Lines 6 and 7 give functions
for transitions and initial states. Finally, Line 11 closes the NFA domain; the
code appearing after Line 11 does not belong to the NFA specification.
/// Non-deterministic Finite Automaton Domain
2. domain NFA {
/// Constructors for NFAs
4. Event : ( name : Any ).
5. State : ( name : Any ).
6. Transition : ( current : State, trigger : Event, next : State ).
7. Initial : ( state : State ).
/// More to come later

11. }
13. model ExampleNFA1 : NFA {
14. ///
∗∗∗∗∗
Events
∗∗∗∗∗
15. Event(“e”),
16. Event(“f”),
17. ///
∗∗∗∗∗
States
∗∗∗∗∗
18. State(“S1”),
19. State(“S2”),

20. ///
∗∗∗∗∗
Initial States
∗∗∗∗∗
21. Initial(State(“S1”)),
22. ///
∗∗∗∗∗
Initial States
∗∗∗∗∗
23. Transition(State(“S1”), Event(“e”), State(“S2”)),
24. Transition(State(“S2”), Event(“f”), State(“S1”))
}
FIGURE 14.3
Specifying the non-deterministic finite automaton (NFA) abstraction.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 451 2009-10-2
Semantics of Domain-Specific Modeling Languages 451
A model is simply a set of ground terms built using the functions of a
domain. The syntax for declaring a model is
model ModelName : DomainName { } (14.17)
Line 13 declares a model equivalent to the FSM in Figure 14.2. The contents of
the model is a comma-delimited list of NFA functions applied to some basic
values. It is illegal to use any other functions than those of the NFA domain.
Also, it is illegal to use basic values that do not appear inside of a function.
14.3.3.1 The Type of a Domain
A domain D also has an associated type τ
D
, which is the set of all finite mod-
els (term sets) that belong to the domain D. There is a minimum requirement
for a model to belong to a domain: Every term in the model must be built
from functions of the domain. Typically, a domain has more complex con-

straints limiting which term sets are legal models of the domain. We call
these rules domain constraints, and discuss them shortly. Right now our NFA
domain only imposes the minimum domain constraint.
The notation:
model ModelName : DomainName { }
is making the assertion that the data inside of the model belongs to the
domain.
FORMULA will type-check the model against the definition of the
domain to ensure the accuracy of this assertion. From this perspective,
the order-sorted type system also extends to domains. Two domains are sub-
type related if the sets of conforming models are subset related.
14.3.4 Examining the Contents of Models
Models contain important information that must be extracted. This is accom-
plished by adding rules to a domain that locate key information within a
model. For example, we might want to know which states are the initial states
of a FSM. Such questions are called queries; this query finds the initial states
of an FSM:
hasInit :? Initial(x). (14.18)
A query is evaluated over a model; it is satisfied if there exists some
assignment of variables to values such that each item in the body exists in
R
∞
. For example, if this query is evaluated against the model ExampleNFA1
in Figure 14.3 and variable x is assigned as follows:
x = State(“S1”) (14.19)
then the query is satisfied because the term Initial(State(“S1”)) exists in the
model.
FORMULA will find all assignments of variables satisfying the query, or
report that no such assignment exists.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 452 2009-10-2

452 Model-Based Design for Embedded Systems
On the other hand, the query
hasInit2:?Initial(State(“S2”)). (14.20)
fails, because S2 is not an initial state. Queries can contain more than one
pattern in the body; each pattern must be satisfied in order for the query to
be satisfied:
hasTrans :? Initial(x), Transition(x, e,y). (14.21)
This query is satisfied whenever there exists a transition from an initial
state x to another state y triggered by event e. Evaluating this query on
ExampleNFA1 yields success for the following assignment of variables:
x = State(“S1”) (14.22)
y = State(“S2”) (14.23)
e = Event(“e”) (14.24)
Note that the order in which items occur in the body does not affect the
results of a query.
FORMULA also allows the arguments of functions to be labeled. Terms built
using functions with labeled arguments can be accessed like a record struc-
ture. For example, query 14.21 can be rewritten to:
hasInit2:?x is Initial, t is Transition, t.current = x.state. (14.25)
In order to access data through the argument labels of function S, a variable
x must first be “cast” to type S using the is operator. Note that this syntax is
not an extension of the language.
14.3.4.1 Examples of Negation as Failure
Queries with only positive body terms cannot express all interesting queries.
For example, we might want to know if there are two states x and y such that
there are no transitions from x to y. Expressing this query requires the use of
NAF. Intuitively, a negative term forces the absence of certain terms in the
input model. Here is an example:
noTrans :? x is State, y is State, e is Event, fail Transition(x, e,y). (14.26)
The first three terms find two states and an event. The last terms uses the

keyword fail to indicate NAF:
fail Transition(x, e,y)
This part of the query succeeds if the logic program does not include a
Transition from x to y triggered by event e in R
∞
. It is important to under-
stand that variables occurring in positive terms are bound first. The values
that satisfy the positive terms constrain the negative terms. For example,
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 453 2009-10-2
Semantics of Domain-Specific Modeling Languages 453
when evaluating the query on ExampleNFA1, the positive part of the query
is satisfied by
x = State(“S1”)
y = State(“S2”)
e = Event(“e”)
These values constrain the negative pattern, resulting in a test for
Transition(State(“S1”), Event(“e”), State(“S2”))
This test determines that there is a transition from S
1
to S
2
so the negative
pattern fails and the overall query fails for this assignment of variables. How-
ever, there are more assignments of variables to try before deciding that the
query completely fails. For example, here is another assignment:
x = State(“S1”)
e = Event(“f”),
y = State(“S2”)
Now, the event is f. In this case, there is a test for
Transition(State(“S1”), Event(“f”), State(“S2”))

Indeed, the model does not contain this transition, so the query succeeds for
this assignment of variables.
Figures 14.4 through 14.6 show some examples of NAF. The dashed lines
in the figures represent tests for the absence of terms. Note that every occur-
rence of an underscore (_) stands for a uniquely named variable that does not
appear anywhere else in the query. Each example shows several equivalent
ways of writing the query.
/// Queries testing if there is the absence of
/// a transition between states x and y triggered by e.
4. ?: State(x1,x2), State(y1,y2), Event(e),
5. fail Transition(State(x1,x2), Event(e), State(y1,y2)).
7. ?: x is State, y is State, e is Event, fail Transition(x,e,y).
9. ?: x is State, y is State, e is Event, fail t is Transition,
10. t.current = x, t.event = e, t.next = y.
e
x
y
FIGURE 14.4
Find states x and y without a transition triggered by event e.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 454 2009-10-2
454 Model-Based Design for Embedded Systems
/// Queries testing if there are states x and y
/// such that there are no transitions from x to y.
4. ?: State(x1,x2), State(y1,y2),
5. fail Transition(State(x1,x2), e, State(y1,y2)).
7. ?: x is State, y is State, fail Transition(x,_,y).
9. ?: x is State, y is State, fail t is Transition,
10. t.current = x, t.next = y.
e
1

e
n
e
i
xy
FIGURE 14.5
Find states x and y without any transitions from x to y.
/// Queries testing if there are blocking states, i.e.
/// states with no outgoing transitions.
4. ?: State(x1,x2), fail Transition(State(x1,x2), e, y).
6. ?: x is State, fail Transition(x,_,_).
8. ?: x is State, fail t is Transition, t.current = x.
e
1
e
i
e
n
e
1
e
i
e
n
e
n
e
1
e
i

X
y
1
y
m
y
i
FIGURE 14.6
Find blocking states x, that is, states without any outgoing transitions.
14.3.4.2 Boolean Composition of Queries
A query is either satisfied (i.e., true) or not satisfied (i.e., false) when
evaluated against a model. Therefore, queries return boolean values, so new
queries can be built from old ones using standard boolean operators: & (and),
| (or), and ! (not).
queryC :? queryA |!queryB. (14.27)
There are some strict rules that apply when composing queries with boolean
operators:
1. A query must be given a name before it can be used in a composition.
2. A query cannot be defined in terms of itself, as in: queryC :? queryC
& queryB.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 455 2009-10-2
Semantics of Domain-Specific Modeling Languages 455
3. The body of a query is either a list of terms or a boolean composition of
queries, but never both. This is illegal: queryC :? State(x), queryB.
Note that a boolean composition of queries does not allow information to be
passed between subqueries. Each subquery is evaluated independently from
the others, and then the results are aggregated.
14.3.5 Adding Domain Constraints
Domains contains rules for distinguishing the data sets that are legal mod-
els from those that are not. Earlier, we explained that there is a minimum

requirement for a model M to belong to a domain D: Each term in M must
be built from functions of D. Typically that requirement does not capture all
the rules of a particular abstraction level. For example, the rule
Every NFA must have at least one initial state
is not captured by this minimum requirement.
FORMULA supports additional domain constraints through a special query
called conforms. If this query is defined, then a data set must satisfy the
query to be a valid model of the domain. For example:
conforms :? Initial(x). (14.28)
captures the rule that every NFA must have at least one start state. Figure
14.7 shows the domain constraints needed for the NFA abstraction. Lines 10
and 11 defines queries that are satisfied whenever there is a dangling tran-
sition to a state not in the model. The query at Line 12 finds transition that
are triggered by undefined events and the query at Line 14 identifies unde-
fined initial states. Line 16 declares the hasInitial query that guarantees
the presence of an initial state. Finally, Line 18 defines the conforms query
as a boolean combination of these queries.

/// Domain constraints for NFA models
10. missingSrc :? t is Transition, fail s is State, s = t.current.
11. missingDst :? t is Transition, fail s is State, s = t.next.
12. missingTrig :? t is Transition, fail e is Event, e = t.event.
14. missingInit :? x is Initial, fail s is State, s = x.state.
16. hasInitial :? x is Initial.
18. conforms :? hasInitial & !(missingSrc | missingDst |
missingTrig | missingInit).

FIGURE 14.7
Domain constraints for NFAs; continued from Figure 14.3.