WLPE on Wednesday, August 16th
(K.U.Leuven -- Dept. of Computer Science)
(DTAI group, Computer Science Dept., Katholieke Universiteit Leuven)
A Delta Debugger for ILP Query Execution
Because query execution is the most crucial part of Inductive
Logic Programming (ILP) algorithms, a lot of effort is invested in
developing faster execution mechanisms. These execution mechanisms
typically have a low-level implementation, making them hard to debug.
Moreover, other factors such as the complexity of the problems handled
by ILP algorithms and size of the code base of ILP data mining systems
make debugging at this level a very difficult job. In this work, we present
the trace-based debugging approach currently used in the development
of new execution mechanisms in hipP, the engine underlying the ACE
Data Mining system. This debugger uses the delta debugging algorithm
to automatically reduce the total time needed to expose bugs in ILP
execution, thus making manual debugging step much lighter.
On using Tracer Driver for External Dynamic Process Observation (extended abstract)
One is interested here in the observation of dynamic processes starting from the traces which they leave or those that one makes them produce. It is considered here that the observations must be able to be made using a large variety of analyzers developed in the most independent possible way.
When one wants to observe a process, the practice is to instrument it for each type of observation which one wants to make on it. One thus implements a new “ad hoc” tracer for each analyzer, or one adapts and completes an existing tracer. Such a work can be largely avoided if one adopts from the start a general approach which consists to instrument it to make it produce what we call a “integral trace”. This unique trace will be useful then for all the later observations which one can plan to make. Each analyzer can then find in the integral trace the data elements which it needs. This approach uses what was called a “tracer driver” which completes the tracer and drives it to answer the requests of the analyzers.
This approach is particularly tempting in practice as the integral trace never needs to be completely expressed (the exchanges of information remain limited) and the work of the tracer implementation and of its driver is made once for all. The evaluation in terms of feasibility and performance remains however problematic.
In this work, we try to specify what is the integral trace, the nature of the work of the tracer and the driver, and the distribution of the functions between the tracer and its driver on the one hand, and the analyzers on the other hand. This enables us to evaluate the respective advantages of the various “ad hoc” or “driven” approaches of the tracer.
To illustrate this study, we use the example of the observation of the resolution of constraints systems (proof-tree, search-tree and propagation) using sophisticated tools of visualization, as developed in the project OADymPPaC (2001-2004).
The processes considered here are computer programs, but the approach can extend to many other kinds of processes.
On s’intéresse ici à l’observation de processus dynamiques à partir des traces qu’ils laissent ou celles qu’on leur fait produire. On considère ici que les observations doivent pouvoir être faites à l’aide d’une grande variété d’analyseurs développés de la manière la plus indépendante possible.
Quand on veut observer un processus, l’habitude est de l’instrumenter pour chaque type d’observation que l’on veut faire sur lui. On produit donc un nouveau traceur « ad-hoc » pour chaque analyseur, ou on adapte et complète un traceur existant. Un tel travail peut être largement évité si l’on adopte d’emblée une démarche globale qui consiste à l’instrumenter pour lui faire produire ce que nous appelons une « trace intégrale ». Cette trace servira alors pour toutes les observations ultérieures que l’on peut envisager de faire. Chaque analyseur peut alors trouver dans la trace intégrale les éléments d’information dont il a besoin. Cette approche utilise ce qui a été appelé un « pilote de traceur » qui complète le traceur et le guide pour répondre aux demandes des analyseurs.
Cette approche est particulièrement séduisante car en pratique la trace intégrale n’a pas jamais besoin d’être totalement exprimée (les échanges d’information restent limités) et le travail d’implantation du traceur et de son pilote est fait une fois pour toute. L’évaluation en terme de faisabilité et de performance reste toutefois délicate.
Dans ce travail, nous essayons de préciser ce qu’est une trace intégrale, la nature du travail du traceur et du pilote, et la répartition des fonctions entre le traceur et son pilote d’une part et les analyseurs d’autre part. Ceci nous permet d’évaluer les avantages respectifs des différentes approches « ad-hoc » ou pilotées du traceur.
Pour illustrer cette approche on prendra l’exemple de l’observation de la résolution de systèmes de contraintes (arbre de preuve, de recherche et propagation) à l’aide d’outils sophistiqués de visualisation, tels que développés dans le projet OADymPPaC (2001-2004).
Les processus considérés ici sont des programmes d’ordinateur, mais la problématique peut s’étendre à bien d’autres type de processus.
(University at Buffalo, the State University of New York)
A Logic-based Debugger for Java
This paper presents a logic based approach to debugging Java programs. In contrast with traditional debugging we propose a debugging methodology for Java programs using logical queries on individual execution states and also over the history of execution. These queries were arrived at by a systematic study of errors in object-oriented programs in our earlier research. We represent the salient events during the execution of a Java program by a logic database, and implement the queries as logic programs. Such an approach allows us to answer a number of useful and interesting queries about a Java program, such as the calling sequence that results in a certain outcome, the state of an object at a particular execution point, etc. Our system also provides the ability to compose new queries during a debugging session. We believe that logic programming offers a significant contribution to the art of object-oriented programs debugging.
(Universidad Politécnica de Madrid)
Combining Static Analysis and Profiling for Estimating Execution Times in Logic Programs
E®ective static analyses have been proposed which allow inferring
functions which bound the number of resolutions or reductions.
These have the advantage of being independent from the platform on
which the programs are executed and such bounds have been shown
useful in a number of applications, such as granularity control in parallel
execution. On the other hand, in certain distributed computation
scenarios where di®erent platforms come into play, with each platform
having di®erent capabilities, it is more interesting to express costs in
metrics that include the characteristics of the platform. In particular,
it is specially interesting to be able to infer upper and lower bounds on
actual execution time. With this objective in mind, we propose a method
which allows inferring upper and lower bounds on the execution times
of procedures of a program in a given execution platform. The approach
combines compile-time cost bounds analysis with a one-time pro¯ling of
the platform in order to determine the values of certain constants for that
platform. These constants calibrate a cost model which from then on is
able to compute statically time bound functions for procedures and to
predict with a signi¯cant degree of accuracy the execution times of such
procedures in the given platform. The approach has been implemented
and integrated in the CiaoPP system.
(Christian-Albrechts-Universität zu Kiel)
CurryBrowser: A Generic Analysis Environment for Curry Programs
We present CurryBrowser, a generic analysis environment for
the declarative multi-paradigm language Curry. CurryBrowser supports
browsing through the program code of an application written in Curry,
i.e., the main module and all directly or indirectly imported modules. Each
module can be shown in different formats (e.g., source code, interface, intermediate
code) and, inside each module, various properties of functions
defined in this module can be analyzed. In order to support the integration
of various program analyses, CurryBrowser has a generic interface to
connect local and global analyses implemented in Curry. CurryBrowser is
completely implemented in Curry using libraries for GUI programming and
(Complutense University of Madrid)
(Complutense University of Madrid)
(Technical University of Madrid)
Some Issues on Incremental Abstraction-Carrying Code
Abstraction-Carrying Code (ACC) has recently been proposed as
a framework for proof-carrying code (PCC) in which the code supplier
provides a program together with an abstraction (or abstract
model of the program) whose validity entails compliance with a
predefined safety policy. The abstraction thus plays the role of
safety certificate and its generation (and validation) is carried
out automatically by a fixed-point analyzer. Existing
approaches for PCC are developed under the assumption that the
consumer reads and validates the entire program w.r.t. the
full certificate at once, in a non incremental way. In this
abstract, we overview the main issues on incremental ACC. In
particular, in the context of logic programming, we discuss both the
generation of incremental certificates and the design of an
incremental checking algorithm for untrusted updates of a
(trusted) program, i.e., when a producer provides a modified version
of a previously validated program. By update, we refer to any
arbitrary change on a program, i.e., the extension of the program
with new predicates, the deletion of existing predicates and the
replacement of existing predicates by new versions for them. We also
discuss how each kind of update affects the incremental extension in
terms of accuracy and correctness.
Fingerprinting Logic Programs
In this work we present work in progress on functionality duplication detection in logic programs. Eliminating duplicated functionality recently became prominent in context of refactoring. We describe a quantitative approach that allows to measure the ``similarity'' between two predicate definitions. Moreover, we show how to compute a so-called ``fingerprint'' for every predicate. Fingerprints capture those characteristics of the predicate that are significant when searching for duplicated functionality. Since reasoning on fingerprints is much easier than reasoning on predicate definitions, comparing the fingerprints is a promising direction in automated code duplication in logic programs.
||Siddharth Chitnis (The University of Texas at Dallas, Computer Science)
(University of Texas at Dallas)
ExSched: Solving Constraint Satisfaction Problems with the Spreadsheet Paradigm
We propose a generalized tool called ExSched, implemented as a plug-in for Microsoft Excel, for solving a class of constraint satisfaction problems. The traditional spreadsheet paradigm is based on attaching arithmetic expressions to individual cells and then evaluating them. The ExSched interface generalizes the spreadsheet paradigm that allows finite domain constraints to be attached to the individual cells that are then solved to get a solution. This extension provides user-friendly interface for solving constraint satisfaction problems that can be modeled as 2D tables, like scheduling problems, timetabling problems, product configuration, etc. Constraint based languages like SICStus have good optimization techniques to solve such complex NP-Hard problems. ExSched acts as an interface between Microsoft Excel and SICStus that hides the syntactic complexity of SICStus and enables novice users to solve many scheduling and timetabling problems interactively.
A Web-based Tool Combining Different Type Analyses
There are various kinds of type analysis of logic programs. These include
for example inference of types that describe an over-approximation of the
success set of a program, inference of well-typings, and abstractions based on given
types. Analyses can be descriptive or prescriptive or a mixture of both, and they
can be goal-dependent or goal-independent. We describe a prototype tool that can
be accessed from a web browser, allowing various type analyses to be run. The
first goal of the tool is to allow the analysis results to be examined conveniently by
clicking on points in the original program clauses, and to highlight ill-typed program
constructs, empty types or other type anomalies. Secondly the tool allows
combination of the various styles of analysis. For example, a descriptive regular
type can be automatically inferred for a given program, and then that type can be
used to generate the minimal “domain model” of the program with respect to the
corresponding pre-interpretation, which can give more precise information than
the original descriptive type.