This is the companion piece for the paper "Poster: Testing Complex Event Patterns", Paweł Maślanka, Bartosz Zieliński (in press)
The code was tested only with SWI Prolog (it is possible it may not work with other Prolog environments as it uses some non-standard libraries. Also module systems differ between Prolog interpreters).
The execution of the code should not depend on the operating system (it was tested on MacOS X and Windows 10) as it does not use any operating system specific libraries.
The module event_types defines two important functors: def_event_type/1 and
def_event_types/1 which accept as a single argument either, respectively, a single declaration of an event type or a list of
such declarations. The functors assert associated
definitions of ref/3 and event_type/2 functors (also exported by the module)
The role of the generated functors is explained below. Finally the module also defines
functors event_time/2 (returning timestamp of an event),
and update_time/4 which is used by generated automaton and not by the user.
Recall that events are represented as prolog terms of the form
⟨event type⟩(⟨attr_value₁⟩, ⟨attr_value₂⟩, …)
where ⟨event type⟩ plays the role of functor, and arguments are the event’s attributes.
Event schema is a list of terms of the form
⟨event_type⟩(⟨attr_name₁⟩, ⟨attr_name₂⟩, …)
with no two terms with the same functor. Declaration such as the one above means that events of type ⟨event_type⟩ have attributes with names
⟨attr_name₁⟩, ⟨attr_name₂⟩, ….. Event
⟨event type⟩(⟨attr_value₁⟩, ⟨attr_value₂⟩, …)
has type ⟨event type⟩ and its argument of name ⟨attr_nameᵢ⟩ has value ⟨attr_nameᵢ⟩ for i∈{1, 2, …}.
If X is an event with an attribute a then our pattern language we refer to the value of this attribute as ref(X, a). During compilation of patterns such terms are replaced by fresh variables (say Y for the sake of example) and additional goals of the form ref(X, a, Y) are added. The goal ref(X, a, Y) is satisfied when the attribute a of event X has value Y.
To check the type of an event one can use predicate event_type/2: The goal
event_type(⟨event⟩, ⟨type⟩)
is satisfied when ⟨event⟩ has type ⟨type⟩.
This module defines a runtime for an automaton recognizing "skipping" patterns on lists. To define an automaton (or rather a family of automatons) itself, a user needs to provide definition for the following five predicates ( the first argument of the first predicate is an identifier which distinguishes between distinct, simultanously defined automatons):
initial(Id, I) : I is an initial state for automaton Idfinal(F) : F is a final statetrans(S0, E, S1) : automaton can move, after consuming
an event E from state S0 to state S1.eps(S0, S1) : automaton can do an ϵ-move from S1 to S2,skip(S, E) : automaton can skip event E when in state S.To run the automaton use match_list/3 which is the sole functor
exported by module so_automaton.
More precisely, the goal
match_list(Id, L, Out)
is satisfied iff the automaton identified by Id recognizes a list
L and Out is a bitmap (a list of 0's and 1's) of the same
length as L and such that it has 1's at the positions corresponding to the positions in L of events actually matched by the automaton (consumed in ordinary transitions) and 0's at positions corresponding to events which were skipped.
Module skip_pattern_syntax exports, aside from binary operators or and then which are used in the patterns (the pattern language is almost the same as described in the paper, the main difference is that instead X.a in order to refer to an attribute a of an event X we write Ref(X, a)), also some predicates which check the properties of patterns and convert patterns. Below we give a list:
pattern_binds/2: Given a pattern P a goal
pattern_binds(P, V) binds to V the (ordered) list of all variables bound by Pclosed/2: Given a pattern P a goal
closed(P, V) is satisfied iff P is closed and
V is the ordered list of variables bound by P
(i.e., the same set as pattern_binds/2 binds).is_unique_pattern/1: The goal is_unique_pattern(P)
is satisfied iff a pattern P has a unique variable property.make_pattern_unique/2: Given a pattern P0 the
goal make_pattern_unique(P0, P) binds to a variable P
the pattern equivalent to P0, but with fresh variables and satisfying the unique variable property.Note that while predicates pattern_binds/2, closed/2,
and is_unique_pattern/1 do not make any assumptions about how the event variables are represented in the pattern passed as an argument (actual Prolog variables or any other terms, it does not matter), but make_pattern_unique/2 requires for correct execution that the pattern passed as a first argument has event variables represented by actual Prolog variables (and the resulting pattern bound to the second argument represents event variables as Prolog variables as well). This is not checked in the goal, so it may lead to difficult to find errors.
skip_pattern_compiler defines predicates which compile patterns into
automatons (described earlier). The module exports two predicates:
compile_query_pure/3: Using it directly is for testing purposes
mostly (though of course it is called by the next predicate on the list).
Given a closed pattern P with unique variable property
and with event variables represented as Prolog variables (none of those properties is verified),
and a pattern identifier Id (we can compile simultanously several patterns
into disjoint parts of an automaton, where state names contain this Id)
a goal
compile_query_pure(Id, P, A) binds a variable A
to the record (dict) representing the automaton recognizing
the pattern P. This dict is of the following form:
auto{
transitions: [trans(V, Type, S0, S1):-G, ...],
epses: [eps(S0, S1), ...],
skips: [skip(S, V1, event_specs)],
initial: S,
final: [S, ...],
states: [S, ...]
}
where
transitions is a list of terms (representing transitions) of the
form trans(V, Type, S0, S1) :- G, where V is an event variable bound to an event
of type Type consumed in the
transition.
S0 is the source state of transition and S1 is the target state of
the transition. Finally, G are additional constraints of the transitionepse is a list of terms of the form eps(S0, S1):-G,
where G is a condition under which an automaton can ϵ-move from
S0 to S1initial is the initial state of the automaton,final is the list of the final states of the automaton,skips is the list of terms of the form
skip(state, variable, event_specs) with at most one such term for
each state state, where event_specs
is a list of pairs of the form type-condition.
An event E is skippable in the state state iff its type T is either not on the list skips or skips
contains the pair T-C and then the condition C is satisfied.
The variable variable is used to refer to event under consideration
in all the conditions in skipsassert_regular/2: This is the main predicate of this module. Given an
identifier Id (which can be any term) and a pattern P the
goal assert_regular(Id, P) asserts (into the user module)
the predicates initial/2, final/2, trans/4
and skip/3 with Id as the first argument.This file contains examples from the paper related to RFID augmented shop. To run the examples (as it is explained in the next section) one needs to simply consult this file into Prolog interpreter (it loads all the other files as modules), and then give appropriate commands which answer questions about aspects of the system.
The file first defines all used event types. Next, it defines predicate
pattern/2
which stores some predefined patterns to try out. The first argument is the identifier,
the second is the pattern.
In order to run the examples from the paper first cd into the folder
with Prolog files and run the interpreter with the command (it also loads shop_example.pl
file):
swipl shop_example.pl
First, let us check if the predicates ref/3 and event_type/2
associated with event types declarations provided in shop_example.pl
were correctly asserted:
event_type(out(1, 10), T).
should bind T=out.
ref(out(1, 10),time,X).
should bind X=10.
Let us now symbollically execute the pattern similar to the one in Equation 1 in the pape.
This pattern is available as
pattern(1, P).
We first compile it with
pattern(1, P), assert_regular(1, P).
Then we can explore (on backtracking) various strings of events matched by this pattern with the following command:
length(L, N), match_list(1, L, B).