Shirka, 10 ans, c'est Tropes?

INRIA Rhône-Alpes - IMAG-LIFIA, 46, avenue Félix Viallet, 38031 Grenoble, France
Jerome.Euzenat@imag.fr,Francois.Rechenmann@imag.fr

Résumé

Sommaire

1. Contexte
2. Le modèle de Shirka
   1. Le noyau de représentation
   2. Interprétation
   3. Mécanismes d'inférence
3. Développements ultérieurs
   1. Règles
   2. Système de maintien du raisonnement
   3. Classification
   4. Langages de tâches
   5. Hypertexte
4. Applications
5. Tropes
6. Conclusion
7. Références

L'exposé suivant ne correspond pas à ce qui aurait été écrit il y a quelques années: la meilleure compréhension du système et le souci de faire partager cette compréhension là, et non celle de l'époque, interdisent de décrire Shirka dans les termes initiaux. Du reste, le manuel [ Rechenmann& 88] est toujours disponible.

Le contexte dans lequel Shirka a été créé est d'abord présenté. Puis, l'exposé porte sur le noyau initial de Shirka, ses extensions ultérieures et ses applications. Après cela les différents aspects conservés ou abandonnés dans Tropes sont abordés.

1. Contexte

• une quinzaine d'années après le début des langages de programmation à objets, alors que SmallTalk en était le seul représentant ayant une visibilité importante;
• une dizaine d'années après les écrits sur les "frames" de Marvin Minsky [Minsky 74];
• quelques années après les langages de représentation de connaissance FRL [Roberts& 77], KRL [Bobrow& 77], Loops [Bobrow& 81] ou SRL [Wright& 83];
• À la suite des premiers articles de Ronald Brachman sur la rationalisation de la représentation de connaissance [ Goodwin 79; Brachman 1979, 1983, 1985];
• Au même moment que les systèmes commerciaux Art [Williams 1984] et Kee [ Fikes& 85] et que les premiers articles sur KL-one [Brachman& 85];
• Au même moment qu'un foisonnement de systèmes développés en France et en Europe: Ceyx [Hulot 83], Mering [Ferber 83], Kool [ Albert 84], LRO2 [Roche 84], Smeci, Yafool [Ducournau& 86].

La conception et l'évolution de Shirka ne se sont cependant pas faits dans l'ignorance des autres efforts menés à la même époque. En particulier, le second parti-pris de Shirka, celui de pousser jusqu'au bout le <<tout est objet>>, n'est pas étranger aux travaux concernant les langages de programmation par objets.

La seconde version de Shirka, celle distribuée actuellement, a été implémentée en 1986 par François Rechenmann, Jose-Luis Aguirre et Didier Bloch. C'est elle qui est décrite dans la suite. Enfin, pour ce qui concerne l'environnement informatique, Shirka été développé en Le-Lisp [Chailloux 83] sur Apple Lisa, puis porté sur des stations Unix.

2. Le modèle de Shirka

2.1. Le noyau de représentation

{AutoDeSarah
	est-un			=	Auto;
	couleur			=	rouge;
	puissance-fiscale	=	9;
	moteur			=	{Moteur#172
						est-un		= Moteur;
						cylindrée	= 2000};
	puissance-réelle	=	[[iota]]}

Ainsi, la classe Auto peut-elle se définir comme une sous-classe de Véhicule dont les attributs couleur, puissance-fiscale et puissance-réelle sont respectivement réduits à un symbole parmi rouge, vert ou bleu, un entier entre 1 et 12 et un réel:

{Auto	est-un Classe
	sorte-de		=		Véhicule;
	couleur			$un		symbole
				$domaine	rouge vert bleu;
	puissance-fiscale	$un		entier
				$intervalle	[1 12];
	puissance-réelle	$un		réel
				$sib-exec
					{calc-puissance
						auto		$var<-	lui-même;
						puissance	$var->	puissance-réelle}}

facette            valeur        interprétation     restriction          
                                 [I(d)]                                  
                   [[tau]]       [[tau]], [[tau]]*  [[tau]]=entier,      
                                                    chaîne...            
$un, $liste-de     f             E(f), E(f)*        f est un filtre      
                   c             I(c), I(c)*        c est une classe     
$domaine           v1... vn      t[[intersection]]  t est le type        
                                 {v1... vn }        initial de           
$sauf              v1... vn      t--{v1... vn }     l'attribut           
$valeur            v             t[[intersection]]                       
                                 {v}                                     
$card              n             {v[[propersubset]  (pour $liste-de)     
                                 ]t; |v|=n}                              
$intervalle        [n1 n2]       {v[[propersubset]  (pour entier ou      
                                 ]t; n1<=v<=n2}     réel)                
$a-verifier        p                                                     

2.2. Interprétation

Les objets s'interprètent comme des éléments du domaine (D), les classes comme des parties de ce domaine, les attributs comme des fonctions partielles d'un élément du domaine vers une valeur et les contraintes (ou prédicats) comme des n-uplets de valeurs (un élément de D"). La fonction d'interprétation I est alors telle que:

• (I(o)=I(o') => o=o')
• pour toute classe c, I(c)ÍD
• pour tout attribut f, I(f):D->D'

• pour toute sous-classe c' de c (noté c'<=c), I(c')ÍI(c)
• pour toute instance o de c, I(o)[[propersubset]]I(c)

Le premier terme correspond à ce qui est réalisé en terme opérationnel par le mécanisme d'héritage (l'inclusion de l'interprétation d'une classe dans l'intersection de celle de ses sur-classes), le second à la prise en compte de toutes les restrictions sur les attributs de la classe et le dernier à la restriction aux objets satisfaisant les prédicats (utilisés par les facettes $a-verifier). Le caractère particulier de cette présentation par rapport à d'autres présentations plus classiques (telles que celles des logiques terminologiques) provient de la présence de relations d'inclusion au lieu d'égalité entre les termes. Ceci correspond à l'interprétation descriptive (et non définitionnelle) des classes qui ne sont décrites que par des conditions nécessaires à leur appartenance mais pas forcément suffisantes.

Shirka travaille donc constamment avec deux termes: I(c) représentant l'interprétation réelle des classes qui ne lui est connue qu'au travers des instances et E(c) qui représente l'extension maximale de cette interprétation, c'est-à-dire le second terme de l'inéquation ci-dessus. Elle se simplifie donc en I(c)ÍE(c).

2.3. Mécanismes d'inférence

facette                    valeur                     
$sib-exec                  méthode                    
$sib-filtre                filtre                     
$var<- ($var-liste<-)      nom-d'attribut             
$defaut                    valeur                     

Les mécanismes d'inférence mis en oeuvre par Shirka se distinguent par leur intégration profonde dans le langage de description de classes. Ainsi, même le mécanisme le plus étranger, l'attachement procédural, fait l'objet d'une présentation toute Shirkaïenne (inspirée de SRL). Plus surprenant, l'exécution de cet attachement est aussi très intégrée: un attachement procédural est décrit par une classe (sous-classe de méthode) dont les attributs sont les entrées/sortie et un attribut particulier (fonction) contient le nom de la fonction Lisp associée à l'attachement procédural. Lorsque cet attachement apparaît dans la description d'une classe (par exemple, pour l'attribut puissance-réelle de la classe Auto, plus haut) une sous-classe est créée enregistrant comment sont obtenues les entrées/sortie (ici l'objet lui-même est l'entrée et la sortie sera la valeur de l'attribut puissance-réelle). Enfin, l'exécution de l'attachement se passe comme suit: lorsque la valeur de l'attribut puissance-réelle est demandée, le système instancie cette sous-classe, renseigne les attributs d'entrée à l'aide des méthodes correspondantes, applique la fonction désignée à l'instance, récupère le résultat dans l'attribut de sortie (s'il s'y trouve) et le retourne.

Un autre mécanisme encore plus intégré est le filtrage. Il permet de chercher des instances ayant certaines caractéristiques. Un filtre est en fait défini exactement comme une classe. Ainsi, on peut implémenter la règle <<L'ensemble des fils d'un homme est l'ensemble des hommes qui l'ont pour père>> par le filtre suivant la facette $sib-filtre:

{Homme
	est-un		=		Classe;
	sorte-de	=		Personne;
	lui-même	$var		lui;
	père		$un		Homme;
	fils		$liste-de	Homme
			$sib-filtre
				{Homme
					père		$var<-	lui;
					lui-même	$var->	fils}}

3. Développements ultérieurs

3.1. Règles

3.2. Système de maintien du raisonnement

3.3. Classification

• Possibles: si toutes les valeurs d'attributs de l'instance satisfont les contraintes de la classe: [[universal]]f[[propersubset]]attributs(c), valeur?(i, f)[[propersubset]][[tau]]f,c,
• Inconnues: si aucune valeur d'attribut de l'instance ne viole une contrainte de la classe mais certaines valeurs d'attributs sont inconnues: [[universal]]f[[propersubset]]attributs(c), valeur?(i, f)[[propersubset]][[tau]]f,c[[union]]{[[iota]]},
• Impossibles: s'il existe une valeur d'attribut de l'instance qui viole une contrainte de la classe: [[existential]]f[[propersubset]]attributs(c), valeur?(i, f)[[reflexsubset]][[tau]]f,c[[union]]{[[iota]]}.

La classification de Shirka -- que l'on pourrait nommer identification -- possède un certain nombre d'originalités (sans égal à l'époque à notre connaissance pour la classification symbolique, on peut en trouver un équivalent dans CLASSIC [ Granger, 1988]):

• Elle prend en compte l'incomplétude des objets (le classement d'instances incomplètes apparaît dans l'ensemble Inconnues).
• Parallèlement aux langages terminologiques qui ne s'autorisent pas à classifier dans les concepts primitifs (correspondant à l'interprétation descriptive des classes), Shirka dispose d'un mécanisme de classification agissant uniquement dans des concepts primitifs. Cependant, par rapport aux langages terminologiques, la classification est plus simple puisqu'elle ne classe que des individus (l'extension aux classes a été conçue et implémentée [Capponi 94b], mais non distribuée).
• L'algorithme prend récursivement en compte la <<classifiabilité>> des objets placés en valeurs d'attributs dans la classe caractérisant le type de l'attribut. Un utilisateur demandant une classification dans Shirka peut la voir se dérouler en temps réel et examiner les trois ensembles sur le graphe de spécialisation lui-même.

3.4. Langages de tâches

• représentation d'une classe de problèmes [ Wielinga& 86],
• élément de contrôle dans les systèmes à base de connaissance [Chandrasekaran 86],
• généralisation d'une fonctionnalité [Rousseau 88].

FIG. 1 (d'après [ Willamowski& 94]) - L'organisation des entités dans un environnement de résolution de problèmes. Les tâches sont reliées entre elles par la spécialisation et la décomposition. Elles prennent en entrée et produisent en sortie des objets du domaine (représentés par des objets Shirka). Elles se résolvent finalement en tâches élémentaires exécutables prenant les mêmes entrées/sorties.

Une tâche définit un problème à résoudre. Pour cela elle utilise une représentation qui se partage en:

• ses entrées (les données à traiter) qui sont exprimées sous formes d'objets ou de valeurs;
• ses sorties (le résultat à obtenir) qui sont exprimées sous formes d'objets ou de valeurs;
• une stratégie de résolution (les tâches sans stratégie étant inapplicables).

• un programme exécutable (la tâche est alors qualifiée de méthode) qui résout le problème; ces tâches permettent en particulier d'intégrer des bibliothèques de programmes externes [ Prevosto& 89a, b, 91; Bassot 94a, b];
• une décomposition en fonction d'autres tâches construites à l'aide d'opérateurs classiques de programmation (séquence, itération, choix, parallélisme...) et des flots de données entre les entrées et sorties des tâches impliquées.

FIG. 2 (d'après [Willamowski 94]) - L'interface de Scarp. On y voit en haut les entrées/sorties de la tâche en cours d'exécution, en bas l'arbre de décomposition des tâches et par dessus un interacteur demandant son avis à l'utilisateur.

L'<<exécution>> d'une tâche s'accomplit comme suit:

• une instance de la classe représentant la tâche est créée;
• les entrées sont d'abord obtenues, soit par le flot de données, soit par la définition de la tâche (à l'aide des mécanismes d'inférence);
• la classification est utilisée pour déterminer, en fonction des entrées, les tâches applicables;
• les entrées manquantes sont obtenues par demande à l'utilisateur;
• si la tâche est une méthode, elle est exécutée, sinon la décomposition est exécutée en revenant en (1) pour chaque sous-tâche;
• les sorties sont obtenues grâce au flot de données et validées par l'utilisateur.

La sémantique opérationnelle de ce système a été étudiée dans [ Crampé 94], elle s'apparente clairement à celle de Prolog... qui se retrouve donc intégré plus naturellement (que par des règles) au sein des objets.

3.5. Hypertexte

FIG. 3 (d'après [Euzenat 95a]) - Liaison Shirka-hypertexte permettant de passer du texte aux objets et vice versa.

Mais l'expression de la connaissance sous un formalisme particulier, si elle permet sa manipulation par un ordinateur, a ses limites. En particulier, elle ne permet pas de tout exprimer et n'est pas forcément intelligible à un utilisateur qui n'a pas participé à l'élaboration de la base. Ceci a justifié l'adjonction à Shirka d'un système d'hypertexte permettant d'exprimer informellement des informations [Grivaud& 92]. L'aspect original du système -- qui a profité de l'intérêt porté aux hypertextes dans les années 80 -- est non seulement de pouvoir accéder au texte à partir des éléments de connaissance (classes, attributs...), mais aussi de pouvoir revenir aux éléments de connaissance à partir de l'hypertexte (voir figure 3).

4.Applications

Une telle utilisation d'un logiciel développé en laboratoire est encourageante. Au delà du nombre, on peut cependant noter deux aspects concernant ces applications:

• elles ont principalement été réalisées dans des laboratoires de recherche, par des spécialistes du domaine: elles n'ont donc pas bénéficié du support d'un intermédiaire informaticien ou <<cogniticien>>, mais au contraire du lien direct avec le <<producteur de connaissance>>.
• le choix de Shirka a pu être influencé par le fait qu'il était distribué gratuitement (bien que des formalités devaient être initialement remplies pour utiliser le système).

5.Tropes

• La distinction classe/instance est renforcée par un troisième niveau, le concept, qui permet de partitionner l'univers du discours de manière étanche: ceci a des incidences sur la signification et l'implémentation des objets.
• Le typage fort des attributs se voit renforcé par une disparition des types primitifs (décrits au travers de types abstraits et par conséquent extensibles) et par un système de normalisation de types permettant de faire une classification de classes correcte [Capponi 95].
• La connexion avec un système hypertexte repose simplement sur HTML. En plus de ce qui a été présenté plus haut, Tropes est capable de présenter la connaissance sous forme de documents HTML à la volée (c'est-à-dire que Tropes se transforme en serveur et engendre les pages à la demande au lieu de les stocker au préalable).

• la représentation des taxonomies de classes sous plusieurs points de vue (inspirée de [Carré 89]), qui rend compte de la multiplicité des approches possibles lorsqu'il s'agit de structurer un ensemble d'objets [Mariño 93];
• l'utilisation d'un système de résolution de contraintes, en remplacement des anciennes contraintes de Shirka, mais aussi en prolongement du système de types [Gensel 95b].

• le maintien du raisonnement et la gestion d'hypothèses qui permettent de traiter un raisonnement disjonctif [ Gensel 90; Gensel& 93] (le système de maintien du raisonnement présenté plus haut constitue une expérience à reconduire mais en reconsidérant son intégration au sein du système de satisfaction de contraintes);
• la construction automatique de taxonomies par diverses méthodes d'analyse de données [ Euzenat 93c] ou d'apprentissage symbolique [Aguirre 89; Valtchev& 95; Bisson 95];
• l'intégration d'équations qualitatives sur le comportement des objets;
• l'intégration de connaissances linguistiques sur la connaissance afin de traiter la déconnexion entre le langage courant et le langage standardisé dans une base de connaissance [ Lemaire 95c] (ceci permet aussi de traiter le multi-linguisme);
• la conception de mécanismes de construction coopérative de bases de connaissance [Euzenat 95a].

6. Conclusion

Le parti-pris de déclarativité va dans le sens de l'histoire et s'est révélé payant en terme d'utilisabilité par les applications. Celui du <<tout objet>> a montré ses limites (réflexivité, règles, TMS) mais aussi ses avantages (filtres, classification, tâches). Ce dernier point est donc à évaluer de manière très précise avant de le réutiliser. On peut dire que plus une notion (ici objet) a d'utilisations différentes et variées, moins elle a de signification propre. Ainsi, l'exploitation tout azimut d'un concept -- perçu comme un gage de sa généralité -- n'est pas forcément si positive. Par exemple, l'interprétation des objets donnée ci-dessus autorise la classification telle qu'elle a été présentée mais devrait interdire l'utilisation des objets Shirka en tant que dépendances dans le TMS (voire même en tant que tâches). Mais pour s'en rendre compte, il est nécessaire de s'entendre au préalable sur la sémantique des notions utilisées. C'est pourquoi il est apparu petit à petit (nous ne sommes pas les premiers à nous en rendre compte, voir par exemple [Levesque& 87]) que la notion de déclarativité utilisée initialement devait être remplacée par celle d'interprétation. D'une manière générale, ces principes se sont donc dégagés au cours de ces dix ans comme antagonistes. Mais dix ans, c'est à la fois trop -- en tout cas suffisant pour se rendre compte de cet antagonisme -- et trop peu -- car le développement d'une sémantique englobant la totalité du monde objet (y compris la programmation) n'a pas eu le temps de voir le jour.

Au delà des aspects conceptuels, les utilisations d'un système comme Shirka montrent qu'il y a réellement un besoin. Mais ces outils sont principalement utilisés par des ingénieurs ou des chercheurs non informaticiens: ils doivent donc bénéficier d'une simplicité d'utilisation (uniformité) et d'une sémantique claire.

Remerciements

Références

[Aikins 83]

J. Aikins. Prototypical knowledge for expert systems. Artificial intelligence 20:163-210 83

[Albert 84]

P. Albert. KOOL at a glance. Actes 6th ECAI, Pisa, IT, p345 84

[Bobrow& 81]

D. Bobrow et M. Stefik. The LOOPS manual. Memo KB-VLSI-81-13, Xerox PARC, Palo Alto, CA US 81

[Bobrow& 77]

D. Bobrow et T. Winograd. An overview of KRL: knowledge representation language. Cognitive science 1(1):3-45 77

[Brachman& 85a]

R. Brachman et J. Schmolze. An overview of the KL-one knowledge representation system. Cognitive science 9(2):171-216 85

[Brachman 79]

R. Brachman. On the epistemological status of semantic networks. Dans N. Findler (éd.). Associatives networks: representation and use of knowledge by computers. Academic Press, New-York, NY US, pages 3-50 79

[Brachman 83]

R. Brachman. What is-a is and isn't: an analysis of semantics links in semantic networks. IEEE Computer 16(10):30-36 83

[Brachman 85]

R. Brachman. "I lied about the trees" or, defaults and definitions in knowledge representation. AI magazine 6(3):80-93 85

[Carré 89]

B. Carré, Méthodologie orientée-objet pour la représentation des connaissances: concepts de points de vue, de représentation multiple et évolutive, Thèse d'informatique, université de Lille, FR 89

[Chailloux 83]

J. Chailloux. Le_Lisp 80, version 12: le manuel de référence. Rapport technique 27, INRIA Rocquencourt, FR 83

[Chandrasekaran 86]

B. Chandrasekaran. Generic tasks in knowledge-based reasoning: high-level building tools for expert-system design. IEEE Expert 1(4):23-30 86

[Cointe 85]

P. Cointe. Le modèle objVlisp: une plate-forme pour l'expérimentation des formalismes objets. Actes 5ième RFIA, Grenoble, FR, pages 737-754 85

[Doyle 79]

J. Doyle. A truth maintenance system. Artificial intelligence 12(3):231-272 79

[Ducournau& 86]

R. Ducournau et J. Quinqueton. YAFOOL: encore un langage objet à base de frames! version 2.1. Rapport technique 72, INRIA, Rocquencourt, FR 88

[Ferber 83]

J. Ferber. MERING: un langage d'acteurs pour la représentation et la manipulation des connaissances. Thèse d'informatique, université Pierre et Marie Curie, Paris, FR 83

[Fikes& 85]

R. Fikes et T. Kehler. The role of frame-based representation in reasoning. Communication of the ACM 28(9):904-920 85

[Granger 88]

C. Granger, An application of possibility theory to object recognition, Fuzzy sets and systems 28(3):351-362 88

[Goodwin 79]

J. Goodwin. Taxonomic programming with KLONE. Rapport de recherche LITH-MAT-R-79-5, Linköping university, Linköping, SE 79

[Haton& 91]

J.-P. Haton, N. Bouzid, F. Charpillet, M.-C. Haton, B. Lâasri, H. Lâasri, P. Marquis, T. Mondot et A. Napoli. Le raisonnement en intelligence artificielle. InterÉditions, Paris, FR 91

[Hulot 83]

J.-M. Hulot. Ceyx: a multi-formalism programming environment. Rapport de recherche 210, INRIA, Rocquencourt, FR 83

[INRA88]

Le projet CHIMENE, document ronéoté, INRA, Jouy-en-Josas (FR) 88

[Laurière 82]

J.-L. Laurière. Représentation et utilisation des connaissances. Techniques et science informatique 1(1):25-42 & 1(2):109-133 82

[Levesque& 87]

H. Levesque et R. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational intelligence/intelligence informatique 3(2):78-93 87

[Minsky 74]

M. Minsky. A framework for representing knowledge. Rapport technique AI-memo 306, MIT, Cambridge, MA US, (rep. dans P. Winston (éd.). The psychology of computer vision. Mac Graw-Hill, New York, NY US, pages 211-277 75) 74

[Roberts& 77]

R. Roberts et I. Goldstein. The FRL manual. Rapport de recherche AIM-409, MIT, Cambridge, MA US 77

[Roche 84]

C. Roche. LRO: génération de systèmes experts. Thèse d'informatique, INPG, Grenoble, FR 84.

[Wielinga& 86]

B. Wielinga et J. Breuker. A model of expertise. Actes 7th ECAI, Brighton, GB, pages 306-318 86

[Williams 84]

C. Williams. ART: The advanced reasoning tool, conceptual overview. Inference Corporation, Los Angeles, CA US 84

[Winston& 81]

P. Winston et B. Horn. Lisp. Addison-Wesley, Reading, MA US 81

[Wright& 83]

J. Wright et M. Fox. SRL/1.5 user manual. Carnegie-Mellon university, Pittsburg, PA US 83