LRDE Seminar: 28 May 2003, EPITA

Task graphs and data dependencies -- Benoît Perrot^?

Keywords Graph dependency, frame based reasoning, F-Logic, dataflow analysis, hidden dragon.

Abstract The task system used in the Tiger Compiler is actually based on handwritten task dependencies: for instance the developer, who knows that the "parse" task must be done before the "type-check" one, explicitly wrote a dependency between "parse" and "type-check".

A clever way to express these dependencies would be to inform the tasks of what they need and what they produce, in terms of instanciated, allocated or realized objects. This concept is well illustrated in the "make" utility, where a binary program depends on its objects, and these objects depend on their sources. Building such a graph would allow dynamical data analysis, particularly detection of dead objects, i.e. objects that could be safely destroyed after use, to avoid dummy memory consumption or leak.

The challenge here is to express tasks and dependencies in terms of "resources" and "products" of "process", considering class hierarchies as manipulated entities. Indeed, a simple abstract syntax tree is a resource of the "ast-display" task and also of the "type-check" one, but not of "hir-compute"; the product of "type-check", which is a decorated (or a derivated?) abstract syntax tree is always a valid resource of "ast-display" and becomes a resource of "hir-compute".

Generic Visitors in C++ -- Nicolas Tisserand^?

Keywords: visitors, visitor combinators, C++, meta-programming, expression templates

Abstract: The Visitor design pattern is a well-known software engineering technique that solves the double dispatch problem and allows decoupling of two inter-dependent hierarchies. Unfortunately, when used on hierarchies of Composites, such as abstract syntax trees, it presents two major drawbacks : target hierarchy dependence and mixing of traversal and behavioral code.

CWI's visitor combinators are a seducing solution to these problems. However, their use is limited to specific 'combinators aware' hierarchies.

We present here Visitors, our attempt to build a generic, efficient C++ visitor combinators library that can be used on any standard 'visitable' target hierarchies, without being intrusive on their codes.

First, we present the existing designs and then state our goals. We next show several C++ meta-programming techniques that address the problems encountered. We finish by a presentation of the existing implementation, and an example use case in the LRDE Tiger compiler.

Theory of Evidence -- David Lesage^? and Nicolas Burrus^?

Keywords: Decision under uncertainty, Dempster-Shafer theory, evidence theory, belief functions theory

Abstract: Today's research and applications in the field of quantitative reasoning and decision under uncertainty are dominated by Bayesian networks and their variants. This is somewhat surprising, since many situations involving uncertainty cannot be represented properly within the classical probability framework. There is, for example, no adequate way of representing total ignorance.

One of the most promising alternatives is the theory of evidence, also known as Dempster-Shafer theory, or belief functions theory. This theory has been introduced in the late seventies by Glenn Shafer as a way of representing epistemic or uncertain knowledge, starting from a sequence of seminal works of Arthur Dempster, Shafer's advisor. Dempster-Shafer theoretical bases have raised passionate discussions between researchers. Several approaches exist and lead to several justifications that still have some controversial aspects. But the truly remarkable representation power of this theory should not hide the practical difficulties. Indeed, computation time and memory load are critical problems, since the core mechanism, Shafer's fusion, hides a #P-complete problem.

First, we will present the theoretical background of this framework, trying to expose the current interpretations of this theory.

We will then describe, through examples, the mechanisms that lead to powerful uncertain information fusion and decision. We will make a comparison between Dempster-Shafer theory and other theories, such as Bayesian inference and fuzzy logic. Similarities and differences between the representation capabilities will be explained.

Finally, we will get back to reality, pointing out the critical implementation aspects of a decision engine based on this theory. We will present the first results obtained with our engine, Evidenz, and then conclude with implementation and application perspectives.

Séminaire LRDE : le 28 Mai 2003, EPITA

Graphes de tâches et dépendances de données -- Benoît Perrot^?

Mots-clés: Graphe de dépendance, analyse de flot, F-Logic, logique orientée objet.

Résumé: De plus en plus modulaire, l'architecture désormais dynamique des logiciels soulève d'évidents problèmes d'ordonnancement de tâches : pour une entrée, il s'agit de créer à la volée une chaîne de modules, dont l'exécution aboutira à la sortie souhaitée.

L'expression des dépendances entre ces modules s'avère ici critique, car déterminante dans la construction de tels enchaînements.

Décrire une tâche comme un processus qui a besoin de "réactifs" pour déclencher la création de "produits", présente l'avantage de ne pas masquer les flux de données mis en jeu.

L'objectif est ici de formaliser l'expression orientée donnée des dépendances inter-modules, afin de construire un schéma puissant, efficace et réutilisable d'ordonnancement de tâches.

Visiteurs générique en C++ -- Nicolas Tisserand^?

Mots-clés:

Keywords: visiteurs, combinateurs de visiteurs, C++, meta-programmation, expression templates

Résumé: Le modèle de conception visiteur est une technique de génie logiciel répandue qui permet de résoudre élégamment le problème des multi-méthodes, et permet de découpler deux hiérarchies inter-dépendantes. Dans son cas d'utilisation le plus courant : la visite d'arbres de syntaxe abstraite, il présente deux désavantages majeurs : la dépendance vis-à-vis de la hiérarchie cible, et le mélange du code de traversée et du code spécifique.

Les combinateurs de visiteurs apportent une solution séduisante à ces problèmes. Cependant, leur applicabilité est limitée à des hiérarchies spécialement équipées.

Nous présentons ici Visitors, un prototype de bibliothèque C++ de combinateurs de visiteurs génériques qui peut être utilisée avec n'importe quelle hiérarchie visitable, de manière non intrusive.

Après un état de l'art des concepts existants, nous présenterons nos buts et motivations. Seront ensuite exposées les techniques de méta-programmation C++ utilisées lors du développement de Visitors. Enfin, une présentation de l'implémentation existante et un exemple d'application au compilateur Tiger du LRDE seront effectuées.

Théorie de l'évidence -- David Lesage^? et Nicolas Burrus^?

Mots-clés: Décision sous incertitude, théorie de Dempster-Shafer, théorie de l'évidence, théorie des fonctions de croyance

Résumé: Nous nous intéressons ici au raisonnement avec incertitude en intelligence artificielle. La plupart des recherches et des applications actuelles s'articulent autour des probabilités classiques, qui s'avèrent pourtant relativement inadaptées à de nombreuses situations. La théorie de l'évidence, également appelée théorie de Dempster-Shafer ou théorie des croyances, est une des alternatives les plus prometteuses. Elle permet de raisonner avec précision même lorsqu'on ne dispose à priori d'aucune information sur certains éléments d'un système. De nombreuses approches, souvent très controversées, ont été proposées pour expliquer et justifier ses bases théoriques. Si son pouvoir d'expression est très intéressant, il ne doit pas cacher les difficultés pratiques pour la mettre en oeuvre. En effet, les calculs impliqués par la théorie de l'évidence sont de complexité exponentielle.

Dans la première partie de l'exposé, nous nous focaliserons sur les aspects théoriques de la théorie des croyances. En s'appuyant sur des exemples simples, nous retracerons le chemin qui a mené des probabilités vers cette théorie. Puis nous présenterons le Transferable Belief Model, le formalisme qui apparaît aujourd'hui comme le plus clair et le mieux justifié. Enfin, nous essaierons de caractériser le cadre d'application de la théorie de l'évidence, en montrant les cas d'utilisation les plus courants.

Dans la seconde partie de l'exposé, nous aborderons une vision plus pragmatique de la théorie de l'évidence. A travers différents exemples, nous étudierons les considérations essentielles quant à la modélisation et la résolution d'un problème par cette théorie. Nous exposerons ensuite les points clefs de l'implémentation d'un moteur de fusion et de décision basé sur la théorie de Dempster-Shafer. Nous expliquerons ainsi combien l'implémentation peut avoir une influence cruciale sur les temps de calcul et la charge mémoire. Au point que certains problèmes semblent, à première vue, pratiquement insolvables. Finalement, nous présenterons notre moteur, Evidenz, en abordant son design et les premiers résultats obtenus. Nous détaillerons les perspectives en terme d'optimisation et d'extension du moteur, mais également en termes d'application: classification d'images satellites et aide à la détection de cellules cancéreuses (projet Adhoc du LRDE).

Reports and Slides

Reports and Slides are available from their own pages.

Reports

Nicolas Tisserand. Generic Visitors in C++. CSI Seminar 0312 September 2003

Benoit Perrot. Tasks graphs and data dependencies. CSI Seminar 0311 May 2003

Slides

Nicolas Tisserand. Generic Visitors in C++ (Slides). CSI Seminar May 2003

Nicolas Burrus. Evidence Theory (part 1): Theoretical aspects. CSI Seminar

David Lesage. Evidence Theory (part 2): Implementation Issues and Applications. CSI Seminar

Benoit Perrot. Task graph and data dependencies. CSI Seminar
to top