Subject: Regular Path Queries
From: Karl Lieberherr (lieber@ccs.neu.edu)
Date: Wed Jul 24 2002 - 16:04:15 EDT
Hi Annie:
I saw your interesting abstract in the NEPLS symposium announcement
on regular path queries (attached below).
We work on related problems as summarized here:
The object structure concern is about how objects are structured and it is
typically expressed by a class graph (e.g., a UML class diagram). A suitable
abstraction of a class graph for programming is a non-deterministic finite
state automaton (NFA) that induces traversals in the objects belonging to the
class graph. We write our programs with respect to a NFA. The NFA
describes the important properties of the structural concern that are relevant
to the current concern that is about implementing a specific behavior. How
can we program against the NFA? A natural way is to annotate the NFA
with code that is executed before entering a state and before leaving a state
and before and after state transitions. The code defined in the NFA is
executed as the objects of the class graph are traversed. It is useful to keep
the code annotations defined in the NFA separate from the NFA itself
because they address different concerns that might be separately reusable.
Therefore, programming in this style uses a triple: (CLASS GRAPH, NFA,
NFA ANNOTATION). Sometimes, this triple is called: (CLASS GRAPH,
TRAVERSAL SPECIFICATION, VISITOR).
Relevant papers are:
TOPLAS 1:
http://www.ccs.neu.edu/research/demeter/biblio/compile-ap.html
TOPLAS 2:
http://www.ccs.neu.edu/home/dougo/papers/strategies/*.pdf
With Mitch Wand:
http://www.ccs.neu.edu/research/demeter/papers/new-strategy-semantics/
Can your algorithm derivation techniques als be applied to
our three layer scenario?
How can we compute the traversal graph incrementally?
Do your techniques apply?
One of our favorite regular expressions is:
A any* B meaining: Given an A-object, find all B-objects the A-object contains.
any is the set of all nodes in the graph.
Best regards,
-- Karl
==============
Annie's abstract:
Regular path queries are a way of declaratively specifying program
analyses as a kind of regular expressions that are matched against
paths in graph representations of programs. These and similar queries
are useful for other path analysis problems, such as model checking,
as well. This talk describes the precise specification, derivation,
and analysis of an efficient algorithm and implementation for solving
regular path queries. We start with a specification that corresponds
rather directly to the English description of the problem, apply rules
that capture some common knowledge at a high level, and then apply
program transformations that are centered around Paige's finite
differencing (i.e., incremental computation) techniques. This formal
derivation allows us to analyze the time and space complexity of the
implementation precisely in terms of size parameters of the graph and
the deterministic finite automaton that corresponds to the regular
expression. In particular, the time and space complexity is linear in
the size of the graph. We also prove that the problem is
PSPACE-complete in terms of the size of the regular expression. In
applications such as program analysis, the size of the graph may be
very large, but the size of the regular expression is small and can be
considered a constant.
This archive was generated by hypermail 2b28 : Wed Jul 24 2002 - 16:04:20 EDT