Researchers
F.J. Ballesteros,
F. Bueno,
D. Cabeza,
M. Carro,
J. Cuena,
M.J. García de la Banda,
M. García Clemente,
J. García Martín,
A. García Serrano,
J.C. González-Moreno,
L. Gómez,
J.A. Jiménez,
L. Laita,
L. Ledesma,
P. López,
J. Mariño,
M. Molina,
J.J. Moreno-Navarro,
G. Puebla.
Areas
Parallelism and Implementation Technologies,
Constraint Logic Programming,
Program Development,
Knowledge Representation and Reasoning,
Programming Languages.
Cooperating Nodes
K. U. of Leuven,
U. of Aix-Marseilles II,
ECRC,
U. of Bristol,
INRIA,
U. of Pisa,
SICS,
U. of Aachen, and others.
Description of Research
Parallelism and Implementation Technologies:
The aim in this area is to develop efficient parallel and sequential
implementations of Logic, Constraint Logic, and Logic+Functional
Programming.
The traditional notions of ``independence'' used in the parallel execution of LP to ensure efficiency have been extended leading to new concepts in LP (Non-Strict Independence), as well as in CLP (Search and Solver Independence). Non-strict independence (NSI) is a more relaxed notion than the traditional notion of ``strict'' independence (SI) which still ensures efficient parallel execution. We have developed global analysis based program parallelization technology using SI and also now using NSI. In particular, we have been developing techniques for combined compile-time/run-time detection of parallelism using NSI, with novel run-time checks for this type of parallelism. Another issue under investigation is that of granularity: ensuring that the work represented by a parallel goal is not smaller than the overhead involved in creating a parallel task for it. We have applied an analysis that gives upper bounds on the amount of work that may be done at runtime. We perform as much of the analysis at compile time as possible, but since the work of a recursive predicate typically depends on the size of its input, we postpone the actual computation of granularity until runtime, when input data sizes are known. To this end programs are transformed to compute relevant data sizes on the fly. The above mentioned ideas are applied to the development of the &-Prolog system and language. &-Prolog is, essentially, Prolog with primitives to express synchronization and and-parallelism. The &-Prolog system comprises the run-time system and a parallelizing compiler. The run-time system consists essentially of an implementation of the PWAM as an extension of the SICStus Prolog engine, for which we study optimizations, scheduling, memory management, etc. Experiments show that the current implementation does not impose any slowdown on sequential execution, can achieve significant speedups, and fully preserves the semantics of sequential Prolog. We are also adding support for dependent and-parallelism and working on models, such as ACE, for efficiently combining and- and or-parallelism in the same system.
We are also implementing BABEL, a language which integrates the Logic and Functional paradigms. This work started by generating an innermost implementation using a graph-based abstract machine, the eager abstract machine, which has been then parallelized. The result is a programmed graph reduction machine which integrates unification, backtracking, and independent and-parallelism. From our point of view, lazy evaluation is a key feature for the integration of both paradigms, but the combination of laziness with LP may result in a conflict for a given strategy because of the interaction with backtracking. A first approach to the implementation of lazy narrowing was to use program transformation to obtain uniform programs that have no problems in evaluation. An abstract machine was designed to execute uniform programs. Next we studied the direct implementation of the strategy with the help of a new formalism: demand patterns. This strategy was tested by generating an efficient translation from BABEL to Prolog. Finally, we are studying the use of demandedness information to improve the strategy. The formalism of demand patterns is used to represent strictness information (in the functional programming sense) and also dependencies between the arguments without sacrificing laziness. This information could be extracted from the original program by an abstract interpreter that infers demandedness analysis. The experiments with this strategy show very good speedups. We are currently working to get more information from the abstract interpreter.
Constraint Logic Programming:
The concept of ``independence'' has been also studied in the context of
CLP. It has been shown that an extrapolation of available notions
of independence in LP is incorrect. First, because interaction
among variables through constraints is more complex. Second, because
in order to ensure the efficiency of several optimizations not only
must independence of the search space be considered (as
traditionally), but also an orthogonal issue - ``independence of
constraint solving.'' We have proposed various types of search
independence and constraint solver independence, and show how they can
be combined for allowing different optimizations: Sufficient
conditions for independence which are easier to detect at run-time
than the definitions are also proposed. Based on this work we are
developing parallelization technology for CLP programs. For
experimentation purposes we are incorporating constraint solving into
&-Prolog, resulting in the CIAO-Prolog system. This is done by
using attributed-variables, as in the DMCAI work. We treat an
attributed variable as a wait-variable so that as soon as it is
touched, a predicate is launched. The alternative approach of
including lower-level support a la CLP(R) is under study.
We have also incorporated disequality constraints into the BABEL language. Combining these constraints with lazy evaluation is a complicated task: due to the lazy nature of BABEL a disequality may hold between infinite objects which could implicitly represent infinite disjunctions of constraints. An operational semantics has been developed which is the basis for the extension of the lazy BABEL machine.
Program Development:
We are continuing the development of frameworks, domains and
techniques for the abstract interpretation based global analysis of LP
programs. In addition, abstract interpretation-based compile-time
analysis of CLP programs has also been studied, focusing on program
specialization and automatic parallelization. To this end an extension
the scheme of Bruynooghe for LP to CLP has been developed and
implemented as the ``PLAI'' system. We have also developed data-flow
analyses and program transformations enabling the execution of Prolog
on a number of parallel logic systems besides &-Prolog, like
Andorra-I and AKL. These transformations allow such systems to fully
exploit a form of parallelism (independent-and) which is originally
not exploited in one case or to avoid overhead in independence
(``stability'') detection in the other. Similar work is also being
carried out in the context of the Constraint versions of these
languages.
In the context of debugging and analysis tools for sequential and parallel logic programs we have developed several visualization paradigms for Independent And-parallelism (as in &-Prolog), Or-parallelism (as in Muse and Aurora) and Determinate Dependent And+Or-parallelism (as in Andorra-I). We have developed a tool, VisAndOr, which can represent the execution of parallel logic programs using the above mentioned paradigms and which has been interfaced with the above mentioned systems. This tool has shown to be quite useful in analyzing different characteristics and behaviors of parallel executions of logic programs.
Also, in order to cover the gap between the pure execution of a Prolog program and concrete formal descriptions based on the WAM specification, we have also developed an abstract view of the WAM using a formal description. Our specification treats each WAM component as abstract data types (ADTs). The WAM is derived from SLD-resolution in several refinement steps, including optimizations and implementation tricks, which in any case are delayed as much as possible. In addition, we have developed a visualizable implementation of the previous WAM specification which is able to run Prolog programs and show the user all the components of the machine and their evolution. Each element is displayed at the level of abstraction the user decides.
Knowledge Representation and Reasoning:
Research in this area has focused on the application of LP to the
modeling and verification of large knowledge based systems (KBS). Our
work in KBS modeling has been directed towards the creation of
software environments supporting advanced knowledge architectures, in
two different fashions: (a) organized by nested knowledge modules,
where every module has its own inference procedures using other
internal knowledge modules, and (b) organized by cooperating agents,
where every agent has its local knowledge representation and
inference. Development of a software environment, KSM (Knowledge
System Manager), is in progress. KSM is implemented in Prolog and is
the basis of several models for decision support, such as Flood
Emergency Management and Traffic Control in real time in three Spanish
cities (Sevilla, Barcelona and Madrid). The same approach is now
being applied to Intelligent Computer Support of Cooperative Work.
Other efforts in this area are in verification and validation of KBS.
Here the emphasis is on the detection of irregularities in their
construction. Our work in this field deals with the construction of
formal models of verification which are able to suggest actual
implementations.
Programming Languages:
As mentioned before, we have developed the language BABEL to achieve
an integration of Functional and Logic Programming in a flexible and
mathematically well founded way. It is a typed, higher order (only in
the functional part) language, based on a constructor discipline with
a flexible use of boolean connectives. BABEL uses a lazy version of
narrowing as evaluation mechanism which gives the language more
expressive power.
Collaborative work is in progress towards developing a true concurrent, maximally parallel semantics for CLP programs.
Contact Person:
Manuel Hermenegildo