Présentation de la programmation logique avec Castor

Les faits sont essentiellement la forme la plus élémentaire d'assertions vérifiées relatives au domaine du problème. Les faits sont aussi connus en tant que données. Prenons une famille de quatre personnes (le fils : Sam, la fille : Denise, le père : Franck, la mère : Mary et le grand-père : Garry) Voici comment on peut décrire les faits afférents à cette famille de façon plus exacte :

1. Sam est un enfant de Mary ;
2. Denise est un enfant de Mary ;
3. Sam est un enfant de Franck ;
4. Denise est un enfant de Franck ;
5. Franck est un enfant de Garry.
6. Franck est un homme ;
7. Sam est un homme ;
8. Mary est une femme ;
9. Denise est une femme.

Les faits présentés au-dessus peuvent être utilisés afin de répondre à des questions simples comme Estce que Sam est un homme ? Cette question basique dont la réponse est oui ou non peut être résolue en regardant les faits portants sur les genres. Étant donné que nous avons une correspondance exacte avec le fait 2 de la seconde liste, la réponse est oui ou encore vrai. Cependant, la question Est-ce que Sam est une femme ? retourne non ou faux. Ceci s'explique, car nous n'avons aucune donnée disant que Sam est une femme. Ainsi la réponse par défaut à une requête est non, à moins qu'une correspondance exacte se fasse.

Un type de question légèrement différent est « Quel est le genre de Sam ? ». Cette question n'appelle pas une réponse du type vrai/faux, mais on peut y répondre en regardant le fait 2 de la seconde liste. Une autre question pourrait être « Qui est l'enfant de Franck ? » De même, ce n'est pas une réponse vrai/faux, cependant elle est un petit plus intéressante, car il n'y a pas une seule réponse, mais deux (Sam and Denise). Ceci nous montre qu'on ne peut pas s'arrêter d'examiner les faits dès qu'une réponse est trouvée : on doit continuer les recherches tant que tous les faits intéressants n'ont pas été regardés. Quand il y a de multiples réponses à une question, la personne qui demande peut être intéressée par une réponse, plusieurs ou encore la totalité des réponses.

Une question à laquelle on ne peut pas répondre en regardant juste les faits est « Est-ce que Mary est un parent de Sam ? ». On ne peut pas y répondre, car nous n'avons pas encore défini ce que signifie être parent. Il n'y a aucun fait direct portant sur un quelconque type de relation parent/enfant. Pour résoudre ce problème, nous pouvons ajouter un fait de la nature « X est un parent Y » pour chaque fait du type « Y est un enfant de X » présent au-dessus. Cette approche est encombrante et sujette aux erreurs en particulier quand la base de faits est grande. Une meilleure approche est d'utiliser des règles pour inférer ces nouveaux faits.

Les règles sont des déclarations utilisées pour inférer des nouveaux faits (ou donnés) à partir d'un ensemble de faits existants. Voici quelques règles simples pour décrire le lien de parenté dans la famille :

1) X est un parent de Y si : Y est un enfant de X ;
2) X est le père de Y si : X est un homme ET Y est un enfant de X ;
3) X est la mère de Y si : X est une femme ET X est un parent de Y.

Ici, X et Y sont des paramètres et non des constantes comme « Sam » ou « Franck ». La règle parent fournit la possibilité de répondre à une question du type: « Est-ce que Mary est un parent de Sam ? » ou « Qui est un parent de Sam ? ». Il faut noter que les règles parent et père sont uniquement définies en termes de faits. De l'autre côté, la règle mère est spécifiée en utilisant un mélange de faits et de règles bien qu'elle aurait pu être spécifiée d'une manière similaire à la règle père.

II-B-1. Les règles récursives▲

Maintenant que nous disposons de la base de connaissance, nous sommes prêts à poser des questions. Les problèmes spécifiques à résoudre le sont en posant des questions. Nous avons vu précédemment des requêtes à propos des liens familiaux. D'autres exemples de requêtes peuvent être par exemple lorsqu'on manipule un graphe « Quel est le chemin le plus court entre deux nœuds A et B ? » ou encore « Est-ce que le graphe G est un graphe cyclique ? ».

Les requêtes peuvent se classifier en deux catégories. La première est un simple test pour déterminer si une affirmation est vraie : « Est-ce que Sam est un enfant de Garry ? ». Ce sont des assertions étant donné que le travail principal est de vérifier si la phrase est vraie ou non. Le second type de question amène une ou plusieurs réponses. Par exemple : « Qui est l'enfant de Franck ? », nous ne vérifions pas si un fait est vrai, mais nous demandons au système de déterminer les enfants de Franck. Dorénavant, nous parlerons de ces requêtes en termes de requêtes génératives, car elles demandent de générer des solutions.

Jusque là, nous n'avons pas été très précis sur la méthode qui permet de trouver (on utilise aussi inférer) les réponses. Étant donné les faits et les règles décrits avant, il est facile pour n'importe quel individu d'inférer mentalement les réponses aux questions qu'on a posées. Le principe fondamental qui se cache derrière est nommé en logique formelle modus ponens.

Si A est vrai et que A implique B alors B est vrai (A et B étant des énoncés arbitraires).

Ce principe est le cœur du modèle de calcul utilisé en programmation logique. Une version intuitive, mais plutôt rude de l'algorithme utilisé pour répondre à des requêtes dans un système tel que Prolog est le suivant.

• Construire une liste de faits et de règles pertinentes.
• Prendre un fait pertinent et regarder s'il répond à la question. Recommencez tant que la liste des faits pertinents n'est pas vide.
• Prendre une règle pertinente qui peut être appliquée pour dériver de nouveaux faits (en utilisant le modus ponens). Recommencez jusqu'à tant que la liste des faits et des règles pertinentes soit épuisée.

À chacune des étapes de l'algorithme d'inférence, on peut choisir plus d'un fait ou d'une règle pour continuer l'exécution. Chaque choix mène à un chemin d'inférence différent et tous les chemins ne mènent pas forcément à une solution. Les chemins qui ne mènent pas une solution sont abandonnés et le processus d'inférence reprend depuis le point le plus récent où des faits et/ou règles étaient disponibles pour l'inférence. Abandonner le chemin courant et reprendre l'exécution depuis un endroit précédemment exploré afin de faire un choix différent est appelé backtracking. Le backtracking continue tant que tous les chemins d'inférence n'ont pas été examinés. Ainsi, le calcul est réduit à parcourir des chemins d'inférence déterminés par les faits et les règles disponibles.

Ceci est similaire à effectuer une recherche profonde dans un arbre binaire où les feuilles représentent les résultats finals possibles et les nœuds internes les résultats intermédiaires. Dans une logique formelle pure, l'ordre de sélection des faits et des règles est non déterminé. Ceci implique que l'ordre dans lequel on va obtenir les réponses est non déterminé aussi. Étant donné que certains chemins peuvent mener plus rapidement à une solution que d'autres, en pratique l'ordre d'exécution est fixé (le même que l'ordre de déclaration) pour permettre un contrôle sur l'efficacité (i.e. pour améliorer l'efficacité de la recherche). Fixer l'ordre d'application des règles simplifie aussi le raisonnement à propos de l'exécution des programmes logiques ce qui est aussi un point important pour le débogage.

Dans cette section nous avons décrit les faits, règles, requêtes, assertions et l'inférence. Les faits sont simplement des énoncés. Les règles peuvent être utilisées pour dériver de nouveaux faits. Elles peuvent être construites à partir de faits, d'autres règles ou elles-mêmes (exemple des règles récursives). Un ensemble de règles et de faits peut être utilisé pour répondre à des questions pertinentes. Les questions peuvent de façon générale être classées en d'un côté celles qui demandent une réponse oui/non et de l'autre celles pour lesquelles on doit générer la réponse. Les premières questions sont des assertions et les secondes des requêtes génératives. Les assertions ne peuvent avoir qu'une seule réponse (vrai ou faux). Les requêtes génératives peuvent avoir zéro ou plusieurs solutions. « Est-ce que Sam est un homme ? » est une assertion. « Qui est un enfant de Mary ? » est une requête générative. L'inférence logique est utilisée pour répondre aux questions. Elle implique un examen des faits et l'application des règles. De nouveaux faits émergent depuis une application des règles qui deviennent à leur tour candidat pour un examen futur durant le processus d'inférence.

En programmation logique, il est commun de nommer les faits et les règles en tant que prédicats et relations. Le terme relation trouve son origine dans la théorie des ensembles où il implique une association entre des ensembles. Ainsi, genre est une relation binaire entre un ensemble d'individus et un ensemble de genres. Généralement, une distinction stricte entre règles et faits n'est pas nécessaire lorsqu'on programme avec Castor étant donné qu'ils peuvent être mélangés librement avec la même fonction/expression.

En cohérence avec la programmation logique, nous désignerons dorénavant les fonctions qui représentent les faits ou les règles comme relations. Ainsi, les fonctions retournant un type relation sont aussi appelées relations.

En interne, le type relation représente une fonction ou un foncteur ne prenant aucun argument et qui retourne un booléen. Ainsi, enfant, genre et pere retournent un foncteur qui peut être évalué de manière paresseuse.

Le type template lref est une abréviation pour référence logique (logic reference en anglais) et fournit un moyen simple pour faire entrer ou sortir des valeurs d'une relation sous forme d'arguments, de manière similaire aux références du C++. À l'inverse des références du C++, une référence logique ne doit pas forcément être initialisée et fournit la fonction membre defined afin de vérifier si elle a été initialisée. L'opérateur de déférencement * et l'opérateur flèche -> peuvent être appliqués à une référence afin d'obtenir la valeur de la référence logique.

Maintenant, regardons la sémantique d'une référence logique lors de son initialisation. Quand une référence logique est initialisée (comprendre construite) ou assignée avec une valeur de type T (ou un type convertible en T), la référence stocke en interne une copie de la valeur. Quand une référence est initialisée avec une autre référence (via le constructeur de copie), on dit que les deux références sont liées ensemble. Des références liées ensemble pointent sur la même valeur sous-jacente (s'il y en a une). Ainsi, quand il y le moindre changement à la valeur pointée par l'une des références, ce changement est observé par toutes les références liées ensemble. Une liaison entre des références logiques ne peut être brisée. Cela signifie que si A et B sont des références logiques liées ensemble et que C et D le sont aussi alors on ne peut pas casser la liaison de C vers D pour ensuite la lier à A et B. C continuera à faire partie de la liaison pour toute sa durée de vie. Les références logiques peuvent seulement être liées par initialisation (construction par copie), mais pas par affectation. Une liaison peut seulement être formée durant la construction de la référence et sera cassée lorsque la référence sera détruite. Quand la dernière référence logique dans une liaison est détruite, la valeur sous-jacente est désallouée.

NDT Depuis Castor 1.1, des pointeurs peuvent être utilisés afin d'initialiser une lref. Quand on utilise des pointeurs, on doit spécifier si la lref doit gérer ou non la durée de vie du l'objet référencé par le pointeur. Par exemple :

//La durée de vie de "Roshan" sera gérée.
lref<std::string> s(new std::string("Roshan"), true);

//La durée de vie de name ne sera pas gérée.
string name="Naik";
lref<std::string> s2(&name, false);

L'affectation de pointeur se fait avec la fonction membre set_ptr'

std::string str="Castor";
s.set_ptr(&str, false); // désalloue la chaîne "Roshan" précédemment allouée et ne gère pas la durée de vie de str

Alors qu'utiliser des pointeurs est très utile pour assigner des objets aux lref (spécialement quand on mélange plusieurs paradigmes) et efficaces, cela peut aussi être très dangereux si on ne les utilise pas avec attention. On doit faire attention à bien spécifier la politique de gestion de durée de vie. Par exemple, si on pointe sur un objet qui est alloué sur la pile, la lref ne doit pas gérer la vie du pointeur, sous peine d'erreur. De façon similaire, si deux lref indépendantes se réfèrent au même objet en utilisant l'initialisation/affectation d'un pointeur, aucune des deux ne doit gérer la durée de vie de l'objet. C'est au programmeur de s'assurer que les objets utilisés par les pointeurs des lref sont toujours valides tant qu'elles peuvent tenter d'y accéder. Spécifier accidentellement la politique de gestion de vie à faux à la place de vrai provoquera une fuite de mémoire.

La fonction eq est la fonction d'unification et prend deux arguments. Les arguments peuvent être des références logiques ou des valeurs classiques. eq retourne une expression (comprendre un foncteur) qui, lorsqu'il est évalué, tente d'unifier les deux arguments. Si l'unification réussit, la fonction renvoie true, false sinon. L'unification effectuée par eq est définie comme il suit :

• si les deux arguments sont initialisés, leurs valeurs sont comparées et le résultat de la comparaison retourné ;
• si seulement un argument est initialisé, l'argument non initialisé se verra modifié et prendra la valeur de l'autre argument ;
• si aucun des deux arguments n'est initialisé, une exception est lancée.

Ainsi, l'unification va générer une valeur pour l'argument non initialisé pour les rendre égaux ou elle va comparer ses arguments s'ils sont tous les deux initialisés. Il est possible d'implémenter d'autres variations de l'unification, mais ce n'est en général pas nécessaire.

Les expressions retournées par les divers appels à eq à l'intérieur de la relation genre par exemple sont rassemblées pour former une composante d'expression plus grosse à l'aide des opérateurs && et ||. Il est important de noter que le composant de l'expression est retourné sans être évalué. Ces expressions sont évaluées de manière paresseuse. En d'autres mots, ces expressions sont sauvegardées dans un objet de type relation et seront sujettes à une future évaluation quand il sera nécessaire de la faire. La section suivante examine l'évaluation de ces expressions en détail.

Étant donné les relations au-dessus, on peut formuler la requête qui vérifie « Est-ce que Sam est un homme ? » et enregistre le résultat dans variable samIsMal tel qu'il suit :

relation samIsMale = genre("Sam","homme");

L'appel genre(« Sam »,« homme »); ne réalise en fait aucun vrai calcul, il retourne tout simplement un foncteur qui peut être évalué plus tard afin de vérifier si Sam est un homme. L'appel à une relation ne l'évalue pas. Cette découpe entre appel et évaluation est appelée évaluation paresseuse (lazy evaluation en anglais). Pour exécuter l'évaluation de l'expression, on applique tout simplement l'opérateur () sur la variable qui contient l'expression.

if (samIsMale())
  std::cout<<"Le genre de Sam est: "<<*g;
else
  std::cout<<"Le genre de Sam est inconnu";

La relation genre a été définie précédemment comme il suit :

//le genre de p est enregistre dans g
relation genre(lref<std::string> p, lref<std::string> g)
{
  return eq(p,"Franck") && eq (g,"homme")
   || eq(p,"Sam") && eq (g,"homme") 
   || eq(p,"Mary") && eq (g,"femme") 
   || eq(p,"Denise") && eq (g,"femme") 
  ;
}

Après que « Sam » et « homme » ont été passés en tant qu'arguments à genre, l'expression retournée ressemble à ce qui suit avec les arguments substitués :

   eq("Sam","Franck") && eq ("homme","homme")
   || eq("Sam","Sam") && eq ("homme","homme") 
   || eq("Sam","Mary") && eq ("homme","femme") 
   || eq("Sam","Denise") && eq ("homme","femme")

Cette expression contient quatre expressions && joints par trois opérateurs ||. Si une seule des expressions && retourne vrai, toute l'expression a été résolue et l'évaluation s'arrête afin de signifier la réussite. Regardons pas à pas l'exécution qui se produit lorsque l'opérateur () est appliqué à samIsMale. La première expression eq(« Sam »,« Franck ») && eq (« homme »,« homme ») est choisie pour être évaluée. On tente d'unifier « Sam » avec « Franck » lorsqu’on évalue eq(« Sam »,« Franck ») ce qui échoue étant donné que « Sam » n'est pas égal à « Franck ». Les règles de la logique nous permettent de dire que le reste cette expression && n'a pas besoin d'être évalué. Ainsi, ce chemin d'évaluation est immédiatement abandonné le backtracking reprend l'exécution à la prochaine expression && qui est eq(« Sam »,« Sam ») && eq (« homme »,« homme ») . Cette fois, chaque moitié de l'expression unifie avec succès leurs arguments, car ils sont égaux. Une solution a été trouvée et on renvoie vrai à l'appelant qui se trouve être dans l'instruction if.

Si on refait un appel de l'opérateur () sur la variable samIsMale, l'exécution reprend où elle s'était arrêtée précédemment. Dans ce cas, il s'agit de la troisième expression && qui échoue sur l'unification de « Sam » et « Mary ». Ceci mène à l'évaluation de la quatrième expression && qui échoue aussi pour des raisons similaires et faux sera retourné à l'appelant. Toutes les expressions && ont maintenant été évaluées et appliquer l'opérateur () à samIsMale retournera faux immédiatement, et ceci de manière immédiate.

Maintenant, considérons comment spécifier une requête générative telle que « Quel est le genre de Sam ? ». Une telle question est construite en appelant genre avec le premier argument initialisé à « Sam » et en laissant le second non initialisé.

lref<std::string> g;
relation samsGender = genre("Sam",g);
if (samGender())
  std::cout<<"Le genre de Sam est: "<<*g;

Notons comment il est possible d'utiliser la même relation genre pour à la fois vérifier si quelqu'un est un homme ou une femme et de trouver le genre d'une personne. Quand une solution sera trouvée, g sera initialisé à « homme ». L'expression retournée par genre(« Sam »,g) ressemble à cela après substitution des arguments.

eq("Sam","Franck") && eq (g,"homme") 
   || eq("Sam","Sam") && eq (g,"homme") 
   || eq("Sam","Mary") && eq (g,"femme") 
   || eq("Sam","Denise") && eq (g,"femme")

Quand l'opérateur est appliqué à samsGender pour la première fois, l'évaluation de la première expression && échoue, car on ne peut unifier « Sam » et « Franck ». Le processus de backtracking arrive à la seconde expression eq(« Sam »,« Sam ») && eq (g,« homme »). L'unification de « Sam » avec « Sam » réussit et ensuite eq(g,« homme ») est évalué. Étant donné que g est non défini, eq va assigner la valeur « homme » à g et ainsi l'unification réussit. L'évaluation de l'expression entière s'arrête et renvoie vrai au if. Si l'opérateur() est à nouveau appliqué sur samsGender, l'exécution reprend au point où elle s'était arrêtée. Cependant une chose très intéressante se produit avant que l'exécution ne reprenne. Il est critique pour la poursuite de l'évaluation que les différents effets de bord qui ont lieu dans la branche abandonnée soient annulés avant de reprendre l'exécution. En effet, si ces effets de bord ne sont pas annulés avant la reprise de l'exécution, ils peuvent affecter les futures évaluations et mener à des résultats faux. Ainsi, l'unification de g avec homme doit être annulé restaurant ainsi g à son état original de non-initialisation. Cette fonction de désunification est automatiquement fournie par la fonction d'unification eq.

La requête ci-dessus n'a qu'une seule solution, mais nous avons observé précédemment que des requêtes peuvent avoir plusieurs solutions. Par exemple, on peut vouloir trouver tous les hommes du système. Une fois de plus, on va utiliser la relation genre, mais on va laisser le premier argument non initialisé et le second argument à homme.

lref<std::string> person;
relation males = genre(person,"homme");
while(males())
   std::cout<<*person<< " est un homme"<<std::endl;

Cette fois, on appelle males() jusqu'a tant qu'elle retourne faux. Chaque appel à males déclenche la recherche de la prochaine solution, c'est-à-dire une valeur acceptable pour la référence person. À chaque tour de boucle, on assigne à person une valeur différente qui représente une solution. Quand toutes les solutions ont été trouvées, males retourne faux, la boucle s’arrête et le processus de backtracking restaure person à son état original de non-initialisation. Étant donné que person ne se refère à plus rien après que la boucle soit finie, tenter d'accéder à sa valeur par le biais de l'opérateur * ou de l'opérateur -> lancera une exception.

La récursion est souvent quelque chose d'essentiel quand on déclare des règles dans le paradigme logique. Dans notre exemple des relations familiales, considérons la définition d'une règle portant sur la relation « ancêtre ». Notez qu'il peut y avoir un nombre quelconque de niveaux parent-enfant entre l'ancêtre et le descendant. On peut définir cette règle de façon récursive :

À est un ancêtre de D si :
D est un enfant de A OU
D est un enfant de P ET A un ancêtre de P.

Le code suivant est la traduction naïve de la règle ci-dessus.

//Version défectueuse
relation ancetre(lref<std::string> A, lref<std::string> D)
{
   lref<std::string> P;
   return enfant(D,A) || enfant(D,P) && ancetre (A,P); 
}

Cependant, cette définition contient une récursion infinie. L'instruction return contient un appel récursif à ancêtre. Afin de briser la récursion, on a besoin de repousser l'appel récursif de telle sorte qu'il n'ait lieu que seulement lorsqu'on en a vraiment besoin. Castor fournit une relation aidant à cela avec recurse qui sert à définir des règles récursives. recurse prend en premier paramètre la relation qui doit subir un appel récursif et ensuite les paramètres de cette relation qui sont nécessaires à son appel. La relation retourne un foncteur qui lorsqu'il est évalué mène à l'actuel appel récursif d'ancetre. La problématique appel ancetre(A,P) est tout simplement réécrit en recurse(ancetre,A,P) :

relation ancetre(lref<std::string> A, lref<std::string> D)
{
   lref<std::string> P;
   return enfant(D,A) || enfant(D,P) && recurse(ancetre,A,P); 
}

Dans l'exemple au-dessus, la récursion a lieu sur la relation ancetre qui est définie en tant que fonction libre. L'usage de recurse pour des fonctions membres statiques est exactement le même. Pour utiliser recurse sur des fonctions membres, il faut passer en plus le pointeur this comme il suit :

recurse(this,&Type::fonction, ...arguments...);

Les définitions de toutes les relations décrites jusqu'ici ont été fixées à la compilation. La relation genre par exemple fournit une liste définie de paires nom/genre qui ne change pas au moment de l'exécution du programme. Mais quand les informations ne sont disponibles que dynamiquement (depuis un fichier ou une base de données), nous avons besoin d'un mécanisme alternatif pour construire les clauses de notre relation. Ici, nous avons la relation genre de la partie II qui définit de façon statique les informations.

// realtion definie statiquement
relation genre(lref<string> p, lref<string> g) 
{
return eq(p,"Frank") && eq(g,"male") 
  || eq(p,"Sam") && eq(g,"male") 
  || eq(p,"Mary") && eq(g,"female") 
  || eq(p,"Denise") && eq(g,"female"); 
}

Supposons que les informations sur le genre d'une personne ait été lues depuis un fichier ou une base de données et qu'elles se trouvent une std::list<pair<string,string> > appelée genderList. Le premier champ de la paire contient le nom de la personne et le second son genre. Maintenant, nous pouvons définir une relation gender_dyn sur genderList tel qu'il suit :

list<pair<string,string> > genderList = ...;

// dynamically building a relation
Disjunctions genre_dyn(lref<string> p
                       , lref<string> g) 
{
  Disjunctions result;
  list<pair<string,string> >::iterator i;
  for( i=genderList.begin();
                     i!=genderList.end(); ++i)
    result.push_back( 
            eq(p,i->first) && eq(g,i->second) );
  return result;
}

Ici, nous utilisons le type Disjunctions afin de construire dynamiquement un ensemble de clauses OU pour la relation. Le type Disjunctions est lui-même une relation qui supporte l'addition dynamique de clauses. Ainsi, on peut déclencher l'évaluation en utilisant l'opérateur (). Le type de retour de genre_dyn a été changé de relation à Disjunctions. Ceci est optionnel, mais utile, car il porte implicitement le caractère dynamique de la relation genre_dyn aux utilisateurs. Conceptuellement, le type Disjunctions est simplement une collection de relations. Quand une Disjunctions est évaluée, les relations sont traitées comme s'il existait un opérateur || entre chaque paire de relations. Des relations peuvent être ajoutées au début ou à la fin de la Disjunctions en utilisant les fonctions membres push_front et push_back. Durant l'évaluation, les relations contenues sont évaluées du début vers la fin. Notons comment une expression entière ( eq(p,i->first) && eq(g,i->second) ) est ajoutée à la Disjunctions.

Les relations Conjunctions et ExDisjunctions sont aussi fournies afin de construire des relations dynamiques. Elles correspondent respectivement aux opérateurs && et ^. La relation genre est redéfinie ci-dessous en utilisant Conjunctions et Disjunctions.

Disjunctions gender_dyn(lref<string> p
                  , lref<string> g) {
  Disjunctions result;
  Conjunctions conj1 = eq(p,"Frank");
  conj1.push_back( eq(g,"male") );

  Conjunctions conj2 = eq(p,"Sam");
  conj2.push_back( eq(g,"male") );

  Conjunctions conj3 = eq(p,"Mary");
  conj3.push_back( eq(g,"female") );

  Conjunctions conj4 = eq(p,"Denise");
  conj4.push_back( eq(g,"female") );

  result.push_back( conj1 );
  result.push_back( conj2 );
  result.push_back( conj3 );
  result.push_back( conj4 );

  return result;
}

En résumé, Conjunctions, Disjunctions et ExDisjunctions offrent des moyens de construire des relations dynamiquement. Cette capacité fait d'elles un moyen de faciliter la métaprogrammation à l'exécution dans le paradigme logique [NDT : du code qui se génère lui-même, mais à l'exécution].

On rencontre souvent des cas où les relations sont de simples opérations faites sur les références logiques avec une application des opérateurs standards comme +, -, etc. Par exemple, supposons l'existence d'une relation multiply qui calcule le produit de deux nombres. On peut obtenir le cube d'un nombre de la façon suivante :

lref<int> n=2, sq, cu;
multiply(sq,n,n) && multiply(cu,sq,n)( );
cout << *cu ;

En utilisant multiply, le carré du nombre est généré et en réutilisant ce carré, on obtient le cube. À quoi ressemblerait le code ci-dessus pour une expression du type n*5-n/2+5 ? Il est évident qu'écrire simplement les expressions arithmétiques comprenant plus d'un couple d'opérateurs devient verbeux et vite illisible. Castor autorise la spécification d'expressions logiques de manière inline. L'exemple du cube au-dessus peut être réécrit de la manière suivante :

lref<int> cu, n =2;
eq_f(cu, n*n*n)();
cout << *cu;

La relation eq_f unifie son premier argument avec le résultat de l'évaluation de son second argument qui est un foncteur. Il est important de noter que la valeur de n*n*n n'est pas calculée lorsqu'elle est passée en argument à eq_f. Étant donné que l'expression est composée en utilisant une lref, elle est transformée en un foncteur qui est passé à eq_f. La fonction objet suit l'évaluation quand l'évaluation de eq_f commence. Au moment de l'évaluation, n doit être initialisé, car l'accès à une référence logique non initialisée se solde par une exception. Des expressions arbitraires telles que n*5-n/2+5, composées de lref et des opérateurs communs surchargés peuvent être utilisées afin de construire un foncteur facilement :

eq_f(cu, n*5-n/2+5)();

De telles spécifications d'expression inline impliquant des références logiques sont appelées ILE pour « Inline Logic reference Expression » Les ILE sont très utiles dans un grand nombre de situations. Afficher à la console avec la relation write_f est un autre exemple où elles peuvent être utilisées. Le code suivant montre comment utiliser des ILE afin d'afficher deux chaînes de caractères séparées par une virgule :

lref<std::string> ls="Hello"; std::string s="world";
write_f(ls + std::string(",") + s)();

La relation write_f prend une fonction ou un foncteur en tant qu'argument et affiche le résultat de l'évaluation sur stdout. On utilise une ILE dans l'exemple ci-dessus pour instancier un foncteur et le passer à write_f. Les ILE peuvent être utilisées en tant qu'argument pour n'importe quelle relation fournie par Castor est suffixée avec _f.

Si T est le résultat d'une ILE, alors tous les opérateurs définis sur T comme l'opérateur virgule, l'opérateur de déférencement* l'opérateur & et -> peuvent être utilisés sur une lref<T> pour produire une ILE. Les ILE en l'état actuel des choses manquent d'un support pour le mélange avec un type T2 même si les opérateurs entre T et T2 sont définis. Ainsi

write_f(ls + ",")(); // erreur à la compilation

va échouer à la compilation même si operator+ est défini entre std::string et const char*.

Jusqu'ici, nous avons utilisé les ILE pour passer facilement des expressions à d'autres relations. Les ILE produisent aussi des booléens qui peuvent être utilisés pour créer de simples relations à la volée. Considérons la relation suivante qui affiche le résultat de la comparaison de ses arguments :

relation greaterLessEq(lref<int> n
                    , lref<int> cmpVal) {
  return write(n) && write(" is ") &&
   (   predicate(n<cmpVal) && write("lesser") 
    || predicate(n>cmpVal) && write("greater")
    || write("equal")  );
}

Ici, les expressions predicate(n>cmpVal) et predicate(n<cmpVal) sont utilisées pour définir de façon pratique des relations de comparaison directement dans le code au lieu de passer par des relations globales telles que less ou greater qui feraient le même travail. De façon similaire, predicate(n%2==0) peut être utilisé afin de créer une relation dans le code qui teste si un nombre est pair ou on peut même concevoir des expressions plus complexes comme predicate(n*2 >= cmpVal*n/2). Il est important de noter que les relations définies à l'aide d'ILE ne sont pas capables de générer des solutions. Elles vont seulement vérifier si une condition est vraie ou fausse. Ainsi, predicate(n>cmpVal) ne va pas générer les valeurs possibles de n de telle sorte que la relation soit vraie. Toutes les références logiques utilisées dans une relation doivent être initialisées au moment où l'évaluation de l'ILE a lieu ce sans quoi une exception sera lancée. L'exception sera lancée directement par la référence logique non initialisée lorsque l'ILE tentera de la déférencer pour l'évaluation. Une présentation plus détaillée des ILE a lieu dans la section V.

Castor fournit des moyens pour travailler avec les conteneurs standards et les itérateurs dans une tendance fonctionnelle. Les tâches associées avec les conteneurs peuvent être regroupées de façon générale avec d'un côté le remplissage des conteneurs et de l'autre le parcours. Souvent, dans la programmation logique classique (de la même manière qu'en programmation fonctionnelle ou en métaprogrammation en C++), les opérations qui demandent une modification d'une séquence sont faites en créant une nouvelle séquence qui intègre les modifications. La suppression d'un élément se fait en recopiant tous les éléments sauf celui à supprimer. Ainsi, la suppression d'un élément est une combinaison entre parcours d'une séquence et création d'une nouvelle. L'ajout d'un nouvel élément peut aussi être fait de manière similaire. La modification d'un élément est considérée comme une opération sur l'élément et non la séquence elle-même.

Alors qu'il est possible d'écrire une relation où la suppression et l'ajout de nouveaux éléments se feraient directement sur la séquence originale, nous nous bornerons ici aux techniques classiques dans le style logique. Les sections suivantes décrivent les tâches courantes sur les séquences.

III-H-1. Génération des séquences▲

lref<list<int> > le;
relation evens = sequence(le)(2)(4)(6);
// see what it generates 
if(evens())
  copy(le->begin(), le->end()
       , ostream_iterator<int>(cout, " "));

string s = "One";
lref<string> lrs = "Two";

vector<string> ls;
ls.push_back("Three"); ls.push_back("Four");

vector<string> lsTemp; 
lsTemp.push_back("Five"); lsTemp.push_back("Six");

lref<vector<string> > lrls = lsTemp;

// on crée la séquence dans ln
lref<vector<string> > ln;
relation numbers = 
  sequence(ln)("Zero")(s)(lrs)(ls)(lrls);

//regardons ce qui a été produit.
if(numbers())
  copy(ln->begin(), ln->end(), ostream_iterator<string>(cout," "));

vector<int> vi;
vector<int>::iterator b1, e1;
lref<list<int> > lrli1;
// généré en utilisant les itérateurs de vi
relation r = sequence(lrli1)(vi.begin(), vi.end());


lref<vector<int> > lrvi;
lref<list<int> > lrli2;
lref<vector<int>::iterator> b2, e2;

relation r = begin(b2, lrvi) && end(e2, lrvi) 
              && sequence(lrli)(b2,e2);

III-H-2. Itération dans une séquence▲

relation printList(lref<list<int> > li) {
  lref<int> h; 
  lref<list<int> > t;
  return head(li, h) && write(h) && write(",")
              && tail(li, t) 
              && recurse(printList,t);
}
list<int> li; 
// .. on ajoute des nombres à la liste.
printList(li)();//on affiche les éléments

return head_tail(li,h,t) 
          && write(h) && write(",") 
          && recurse(printList,t);

int a[] = { 1,2,3,4 };
vector<int> v (a+0, a+4);

lref<vector<int> > h;
lref<vector<int> > t;

head_n(v, 2, h)(); 
//  h contient {1,2}
tail_n(v, 2, t)(); 
// t contient {3,4}

lref<int> s;
next(2,s)();
cout << *n;

lref<int> p;
next(p,2)();
cout << *p;

relation printAll( lref<int*> beg_
                   , lref<int*> end_ ) {
  lref<int> val; // for storing **beg_
  lref<int*> n;
  return predicate(beg_==end_)
        ^ ( dereference(beg_, val)
           && write(val)  
            && next(beg_,n) 
            && recurse(&printAll,n,end_) );
}

int ai[]={1, 2, 3};
printAll(ai+0, ai+3)();

int ai[]  = { 1, 2, 3, 4 };
vector<int> vi(ai+0, ai+4);
lref<int> val;

//on itere avec des itérateurs classiques
relation r = item(vi.begin(), vi.end(), val);
while(r())
   cout << *val << ",";

// 2 - itération avec des références logiques sur des itérateurs.
lref<vector<int>::iterator> lBeg = vi.begin()
                          , lEnd = vi.end();
r = item(lBeg, lEnd, val);
while(r())
    cout << *val << ",";

if( item(vi.begin(),vi.end(),4)() )
    cout << "found!";

III-H-3. Unification d'ensemble▲

// produit une séquence
int a[] = { 1,2,3,4 };
vector<int> v (a+0, a+4);
lref<vector<int> > lrv;
eq(lrv,v)();
assert(*lrv==v);

//compare les objets
lref<list<int> > lrl= list<int>(a+0,a+4);
if(eq(lrl,v)())

int a[] = {1,2,3};
lref<list<int> > lrl= list<int>(a+0,a+3);
lref<int> lri=1;
vector<int> v; v.push_back(2);
relation r = sequence(lrl)(lri)(v.begin(), v.end())(3);
assert(r()); // l'évaluation échoue.

III-H-4. Résumé▲

Il est parfois très utile d'éliminer des chemins qui ne produiront pas se solutions ou alors le double d'une solution existante quand le processus de backtracking se produit. De tels élagages explicites sont souvent faits pour des raisons de performance. Il n'y a pas de raison de perdre du temps dans la poursuite d'un chemin qui est connu pour ne mener à rien d'intéressant. Considérons la relation suivante qui cherche une valeur à travers un arbre binaire :

// Binary search tree
struct BST {
  BST* l;    // sous-arbre gauche
  BST* r;    // sous-arbre droit
  int value; // noeud courant
   ...
};

relation b_search(lref<int> val 
                  , const BST* tree) {
return
    predicate(val==tree->value) 
 || predicate(val<tree->value) 
       && recurse(b_search, val, tree->l)
 || predicate(val>tree->val) 
       && recurse(b_search, val, tree->r)
    ;
}

La relation b_search est constituée de trois clauses. La première vérifie que la valeur du nœud courant n'est pas celle qu'on cherche. Les deux clauses restantes vont chercher récursivement dans les sous-arbres gauche et droit en fonction du résultat de la comparaison entre val et le nœud courant. Si la première égalité est vraie, il est évident que les autres clauses peuvent être éliminées. Une fois que la valeur aura été trouvée, nous voudrions que le processus de backtracking reste à la clause courante et ignore les autres options possibles. Cette capacité à éliminer des chemins alternatifs est appelée une coupe en programmation logique. La classe cut et la relation cutexpr fournissent un support pour les coupes dans Castor. On peut réécrire le code au-dessus en utilisant les coupes tel qu'il suit :

return cutexpr(
   predicate(val==tree->val) && cut()
|| predicate(val<tree->val)  && cut() 
        && recurse(b_search, val, tree->l)
|| predicate(val>tree->val) 
        && recurse(b_search, val, tree->r)
  );
}

Chaque occurrence de cut marque le point sur lequel nous décidons de commit à la clause courante. La place de cut est appelée un point de coupe (cut point en anglais). Une cutexpr marque seulement les frontières à l'intérieur desquelles a lieu l'élagage supplémentaire. Dans ce cas, cutexpr englobe les trois clauses dans la relation. Une fois que l'exécution atteint la fin d'un point de coupe, le retour commencera à l'endroit où la cutexpr apparaît et ira jusqu'au point de coupe. Ainsi, toutes les autres alternatives disponibles après cutexpr seront retirées des chemins disponibles pour le processus de backtracking. Les coupes n'affectent pas les alternatives qui existent avant la cutexpr ou les alternatives qui existent après le point de coupe. La cutexpr elle-même ne fait que simplement fournir la portée à l'intérieur de laquelle la coupe peut avoir lieu.

Une coupe non entourée d'une cutexpr ou une cutexpr sans aucune coupe sont toutes les deux des non-sens. De telles choses peuvent apparaître accidentellement lorsqu'on retire des coupes qui font usage de nombreuses coupes. Par le design de Castor, de telles erreurs ne passeront pas à la compilation. Les usages suivants de coupes où une cutexpr apparaît dans l'appelant et cut dans l'appelé ne sont pas autorisés.

// Error: cannot dynamically nest cuts
relation outer(...) {
   return cutexpr( inner(..) || ... );
}

relation inner() {
   return  ... && cut() ...  
}

Un usage excessif de coupes dans un programme logique est généralement déconseillé, car cela tend à rendre le programme moins lisible. Aussi, quand elles ne sont pas utilisées avec parcimonie, les coupes peuvent supprimer des chemins valides. L'usage des coupes devrait premièrement être réservé à des cas où le gain de performance est significatif. Il est préférable qu'une relation qui utilise une coupe produise le même résultat que sa version sans coupe. Des coupes qui n'interfèrent pas dans les résultats sont appelées coupes vertes. Les coupes qui ne sont pas vertes sont rouges. Beaucoup de coupes peuvent être remplacées de manière plus élégante par la relation de l'opérateur ou-exclusif.

Nous avons vu les opérateurs && et || pour définir des relations. Castor fournit aussi un moyen pour définir des relations de choix exclusifs entre des clauses à l'aide de l'opérateur ^. Cette expression est très utile, car elle permet d'évaluer la seconde clause si seulement la première échoue. Regardons de nouveau l'exemple de greaterLessEq

relation greaterLessEq(lref<int> n
                    , lref<int> cmpVal) {
 return predicate(n<cmpVal) && write("n<cmpVal") 
     || predicate(n>cmpVal) && write("n>cmpVal")
     || write("n==cmpVal");
}

L'utilisation de la relation ci-dessus expose à un problème :

relation r = greaterLessEq(2,3);
while(r());

va produire la sortie suivante : n<cmpVal
n==cmpVal

Ceci est dû à l'utilisation de while qui oblige le processus de backtracking à se produire même si la première clause correspond. La seconde clause échoue à cause de la comparaison au début et mène à l'évaluation de la troisième clause. Étant donné que la troisième clause n'a pas la protection (n==cmpVal), elle réussit et on observe la sortie ci-dessus. Une solution simple est d'introduire des coupes dans l'expression. Cependant une solution plus simple est de réécrire la relation avec l'opérateur ^ tel qu'il suit :

relation greaterLessEq(lref<int> n
                    , lref<int> cmpVal) {
return ( predicate(n<cmpVal)
                    && write("n<cmpVal") )
     ^ ( predicate(n>cmpVal)
                    && write("n>cmpVal") )
     ^ ( write("n==cmpVal") );
}

Ici, nous sommes explicites sur le fait que les trois clauses sont mutuellement exclusives. Ce n'est pas seulement plus explicite, mais aussi plus lisible et efficace. Une fois qu'une clause de la relation a réussi, la relation réussit aussi. Le backtracking va ignorer toutes les autres clauses qui n'ont pas été évaluées. Ainsi, toute tentative pour chercher plus de solutions depuis la relation échouera. Il est important de noter la paire supplémentaire de parenthèses autour de chaque clause. En effet, la priorité de l'opérateur ^ est plus élevée que celle des opérateurs && et || d'où le besoin de parenthèses en plus pour garder une associativité correcte.

La plupart, mais pas toutes, des usages de coupes peuvent être remplacés par l'opérateur ou-exclusif. Le support l'opérateur ^ pour les relations est quelque chose d'unique à castor.

Il y a trois moyens de passer une référence logique à une relation

• par valeur lref<T> ;
• par référence lref<T>& ;
• par référence constante: const lref<T>& .

III-K-1. Par valeur▲

relation foo(lref<int> i) {
    return True();
}

lref<int> li=2;
foo(1);  // OK! passes a copy of 1
foo(li); // OK!

III-K-2. Par référence▲

relation foo(lref<int>& i) {
    return True();
}

lref<int> li=2;
foo(1);  // Error!
foo(li); // OK!

III-K-3. Par référence constante▲

relation bar(lref<int>& j) {
    return  ...
}

relation foo(const lref<int>& i) {
    return bar(i); // Error!
}

relation foo(const lref<int>& i) {
    i=2; // Error!
    return bar(i); 
}

Malheureusement, dans un contexte impératif, déboguer du code déclaratif n'est pas aussi simple que de débogueurs du code impératif. Les débogueurs C++ sont faits pour observer du code impératif. En principe, étant donné que nous laissons à l'ordinateur le soin de trouver la solution, nous ne devrions pas être concernés par la manière dont il s'y prend. En pratique, il est très utile de regarder l'évaluation progresser. C'est important pour vérifier la correction des relations, en particulier quand les résultats ne sont pas conformes à ce qui est attendu.

Pour corriger un programme écrit dans le paradigme logique, une certaine façon de penser est nécessaire. Étant donné que les relations sont évaluées de manière paresseuse, il n'est pas très utile de placer un breakpoint dans le code. En fait, certaines références logiques des relations peuvent ne pas être initialisées à l'endroit où la relation est appelée, mais au moment où la relation commence l'évaluation. Alors que la majorité des exécutions survient à l'intérieur des foncteurs retournés par les opérateurs &&, || et la relation eq, l'usage de breakpoint pour déboguer demande la compréhension des détails d'implémentation de castor.

Une technique simple (primitive même) est d'insérer des instructions pour tracer la progression du code. Castor fournit la relation write pour écrire sur stdout selon une manière relationnelle. Dans l'exemple suivant, nous ajoutons des instructions de trace à la relation ancetre afin de voir la solution se générer au fur et à mesure.

relation ancetre_dbg(lref<string> A 
                  , lref<string> D) {
  lref<string> P;
  return enfant(D,A) 
     ||  enfant(D,P) && write(P) && write(",") 
           && recurse(ancestor, A, P);
}

Le code suivant tente de trouver tous les ancêtres de Sam.

lref<string> X;
relation a = ancestor_dbg(X,"Sam");
while(a())
   cout << " :" << *X << " est un parent de de Sam \n";

Et va produire la sortie suivante :

:Mary est un parent de de Sam
:Frank est un parent de de Sam
Mary,Frank, :Gary est un parent de de Sam
Gary,
On peut voir en regardant la sortie que les ancêtres directs (Frank et Mary) sont découverts sans avoir recours à la récursion. Une fois que les deux parents de Sam ont été trouvés, la sortie montre que le processus de backtracking procède à une évaluation de la clause récursive et recherche les parents de Mary.

Une relation test est une relation qui ne modifie aucun de ses arguments et donc qui n'introduit aucun effet de bord dans le système, chose qui pourrait interférer dans le processus de backtracking. Une telle relation est très utile pour tester si une condition est vraie. Généralement, à cause de leur nature profonde, les relations tests réussissent au moins une fois. La relation predicate est très utile pour définir de telle relation. La relation test peut être empaquetée dans une fonction classique qui renvoie un booléen et ensuite appelée à l'aide de la relation predicate. Considérons la relation suivante pour vérifier si un fichier existe :

bool fileExists_pred(string fileName) {
    if(/* fichier existant */)
        return true;
    return false;
}

relation file_exists (lref<string> fileName_) {
  return predicate(fileExists_pred,fileName_);
}

Le processus est en deux étapes distinctes. Premièrement, la fonction-prédicat fileExists_pred contient le code impératif pour vérifier si un fichier existe. Deuxièmement, la relation file_exists fournit un wrapper à la fonction-prédicat fileExists_pred en utilisant la relation predicate pour l'appeler. Noter que la relation prend une référence logique alors que la fonction-prédicat prend une std::string. Alors que les deux paramètres pourraient être une référence logique de std::string, il est plus naturel qu'une relation prenne une référence logique et une fonction-prédicat un type classique. La relation predicate suppose que la fonction cible ne prend pas une référence logique en argument. En conséquence, si filename_ est une référence logique, elle est automatiquement déférencée lors de l'appel de la fonction. Si filename_ n'est pas une référence logique, il sera passé directement.

Il faut aussi noter l'utilisation de '_' à la fin du nom du paramètre. Ceci permet de spécifier que l'argument n'est pas bidirectionnel. Ainsi, sa valeur doit être définie au moment de l'évaluation de la relation. Si elle n'est pas définie à ce moment, une exception du type InvalidDeref est lancée lorsque la relation predicate tente de déférencer filename_

Chaque relation est en vérité l'instance d'un foncteur. Jusqu'ici, nous avons défini les relations en tant fonctions et expressions. Étant donné que cette approche syntaxique constitue un moyen déclaratif de spécifier les détails des opérations du foncteur sous-jacent, le nom de son type et les définitions impératives nous sont cachés. Dans cette section, nous verrons comment créer ces foncteurs directement. Ceci a l'avantage de nous donner un contrôle total sur les étapes de résolution et ainsi la relation est plus facilement débogable. Cependant, le mauvais côté est que cela demande d'écrire plus de code et de faire plus attention.

Nous avons vu que l'évaluation paresseuse est une partie intégrante du fonctionnement des relations. À chaque fois qu'une valeur est calculée, elle immédiatement retournée à l'appelant. Au prochain appel de la relation, elle recommence où elle s'est arrêtée, génère une autre valeur à renvoyer à l'appelant. Ce mode de fonctionnement est à l'opposé des fonctions qui calculent toutes les valeurs avant de les renvoyer. Les fonctions qui supportent le mécanisme d'arrêt-reprise sont appelées coroutines.

Nativement, le C++ ne supporte pas les coroutines. Castor fournit la classe Coroutine et quatre macros (co_begin, co_end, co_yield, co_return) pour cette tâche. Bien que ces utilitaires soient faits pour créer des relations en tant que classes, on peut les utiliser en dehors du contexte de la programmation logique.

Dans Castor, une coroutine est un foncteur. Pour définir notre classe, nous la dérivons depuis la classe Corountime et implémentons la fonction bool operator()(void) tel qu'il suit :

// Une relation pour générer ou vérifier si une valeur est dans un certain intervalle 
template<typename T>
class Range_r : public Coroutine {
    lref<T> val, min_, max_;
public:
    Range_r(lref<T> val, lref<T> min_, lref<T> max_) 
         : min_(min_), max_(max_), val(val)
    { }

    bool operator() () {
      co_begin();
    ...
      co_end();
    }
};

Notez l'usage de la macro co_begin pour démarrer le corps de l'opérateur et co_end pour terminer le corps. Aucune instruction ne doit suivre ou précéder ces deux macros dans le corps de l'opérateur. Ces deux macros définissent simplement une instruction switch qui s'étend sur tout l'opérateur. La définition complète de l'opérateur est la suivante.

bool operator() () {
  co_begin();
  if(val.defined())
     co_return( (*min_<*val && *val<*max_) 
            || (*min_==*val) || (*max_==*val) );
  for(val=min_; (*val<*max_)||(*val==*max_)
              ; ++val.get())
    co_yield(true);
  val.reset(); // Important pour le backtracking
  co_end();
}

Notez l'absence d'instructions return. Elles sont remplacées par co_return et co_yield. Les deux macros retournent à l'appelant la valeur qui résulte de l'évaluation de leurs arguments.

La macro co_yield indique un point où l'exécution est suspendue temporairement et une valeur true/false est retournée à l'appelant. Au prochain appel, l'opérateur () va reprendre son exécution directement à l'intérieur de la méthode, directement à ce yield point. Utiliser cette macro impose à la coroutine de se rappeler quel point a atteint l'exécution précédente. D'un autre côté, utiliser co_return indique qu'aucune autre reprise d'exécution n’est nécessaire et la valeur true/false produite par la relation est renvoyée à l'appelant. Tous les autres appels à l'opérateur () renverront faux immédiatement.

Conceptuellement, co_yield indique un arrêt temporaire de l'exécution et co_return une exécution qui est finie. Étant donné qu'en programmation logique, renvoyer faux est aussi un moyen pour signaler que l'exécution est finie, co_yield(false) indique aussi que l'exécution est finie. Quand l'argument de co_yield est évalué à faux, tous les futurs appels à l'opérateur () retourneront faux immédiatement. Ce comportement est similaire à co_return(false).

La définition de l'opérateur() vérifie tout d'abord si val est initialisé afin de déterminer si la relation doit générer une valeur ou simplement vérifier si elle est dans l'intervalle. Si val est initialisé, on doit seulement réaliser un test, sinon on doit générer des valeurs pour val. Le corps de l'instruction if compare val aux bornes et renvoie le résultat à l'appelant. Étant donné qu'après les tests, il n'y a rien plus à faire, co_return est utilisé afin de retourner le résultat de l'opération.

Dans le cas où val n'est pas initialisée, la boucle est exécutée. Le haut de la boucle génère des valeurs pour val allant de min à max. 0 chaque itération, le corps de la boucle renvoie vrai à l'appelant. À chaque nouvel appel de l'opérateur, l'exécution reprend là où elle s'était arrêtée et réalise ainsi une itération de plus. À chaque fois, val est incrémenté et on retourne vrai à l'appelant. Une fois que val dépasse la valeur maximale, la boucle prend fin et val est remise dans on état de départ. Faire cette remise à zéro est important, car le processus de backtracking demande que toutes les relations annulent les effets de bord qu'elles ont pu avoir avant de signaler l'achèvement. Déléguer la réversion des effets de bord aux relations permet au processus de backtracking d'être simple et efficace.

Quand le foncteur est générique (à l'aide de template), il est courant de fournir une fonction d'aide afin de permettre une déduction automatique du type comme il suit :

template<typename T>
Range_r range(lref<T> val, lref<T> min_
                         , lref<T> max_) { 
    return Range_r<T>(val,min,max);
}

Une chose importante de garder à l'esprit est que lorsqu'on implémente des coroutines, il faut mieux éviter de définir des variables non statiques à l'intérieur de l'opérateur (), car les valeurs ne peuvent pas persister entre deux appels. Ces variables devraient plutôt être promues en tant que variables membres.

À l'origine, les ILE ont été conçues en tant que moyen facile et rapide pour créer des relations anonymes depuis une simple expression au lieu de créer une relation nommée. Les ILE qui retournent un booléen peuvent devenir une relation à l'aide de la relation predicate. La relation predicate est un adaptateur qui permet aux fonctions ou aux foncteurs (qui ont jusqu'à six arguments maximum) d'être utilisés comme une relation. Une relation créée en passant une ILE à predicate est appelée relation-ILE.

L'exemple suivant montre l'usage des ILE pour générer les nombres pairs.

//Print all even numbers in the inclusive range 1...20
lref<int> x;
relation evens = range<int>(x,1,20) 
                  && predicate(x%2==0);
while(evens())
   cout << *x << " ";

au-dessus, la relation-ILE predicate(x%2==0) teste si x est pair. On commence avec x qui n'est pas initialisé. la relation range génère des valeurs pour x et comme est dans la closure de l'ILE, tous les changements sur x seront visibles dans l'ILE. Ceci permet à la relation-ILe de tester les valeurs une par une. Ceci est un exemple du pattern classique généré et testé utilisé en programmation logique. Dans les deux exemples, la relation range sert à générer des valeurs et la relation-ILE à filtrer les valeurs qui ne correspondent pas.

L'exemple suivant montre l'utilisation d'ILE pour générer des triplets de Pythagore.

// Affiche tous les triplets de Pythagore inférieur à 30.
lref<int> x,y,z; int max=30;
relation pythTriplets = 
      range<int>(x,1,max)
   && range<int>(y,1,max) 
   && range<int>(z,1,max) 
   && (   predicate(x*x+y*y==z*z) 
       || predicate(z*z+y*y==x*x) );

while(pythTriplets())
    cout << *x << "," << *y<< ","<< *z << "\n";

Ici, les trois utilisations de range génèrent des valeurs pour x, y et z qui sont comprises entre 1 et 30 et les deux relations-ILE vérifient si x, y et z forment un triplet de Pythagore.

Un autre usage courant des ILE est lié à la relation eq_f qui prend une fonction ou un foncteur en tant que second argument. Elle unifie son premier argument avec la valeur obtenue après évaluation de son second argument. Ainsi, si x et y sont des références logiques, alors eq_f(x, y*3) unifie x avec la valeur obtenue en évaluant y*3.

Les ILE impures ne devraient pas être utilisées pour créer des relations-ILE. Si de telles relations produisent des effets de bord, alors ils ne seront pas inversés durant le processus de backtracking et conduiront à des résultats étonnants. Considérons predicate(++x<5) qui incrémente la valeur de x à chaque évaluation. Ici, l'ILE est impure, car elle modifie la valeur de x à chaque évaluation. Le backtracking compte sur la réversibilité des effets de bord. Quand de tels effets de bord sont voulus, ils devraient être regroupés dans une relation qui s'assure d'annuler les effets de bord. La relation predicate(++x<5) peut être réécrite en inc(x) && predicate(x<5) ou next(x,y) && predicate(y<5). Ainsi, on incrémente x et on l'unifie plus tard y avec la valeur incrémentée de x (sans affecter la valeur de x). C'est ce style qu'on préfère en général.

L'avantage d'une relation-ILE est sa brièveté, le mauvais côté est qu'elle ne peut pas faire autant de choses qu'une relation classique. Les relations-ILE peuvent seulement réaliser des tests sur des valeurs produites par d'autres relations, elles sont incapables de générer des solutions par elles-mêmes. Ainsi, toutes les références logiques impliquées dans une ILE doivent être initialisées au moment de l'évaluation.

Il existe des limitations aux ILE dont les utilisateurs doivent être conscients. La première est due au langage, la seconde au design.

Une question qui peut sembler dénuée de sens si quelqu'un la pose est : « Quel est le type du résultat produit pas l'évaluation d'une ILE ? ». La réponse est bien sûr : « Cela dépend de l'expression représentée par l'ILE ». Une réponse plus précise pourrait être : « Le même type que l'expression qui résulterait d'une réécriture en remplaçant les références logiques avec leurs types effectifs ». Ainsi, l'expression x*y devra retourner un objet du même type et de même valeur que x ou y, soit des références logiques ou des variables classiques. Malheureusement, ceci n'est pas toujours vrai étant donné qu'il n'est pas toujours possible de calculer le type de retour d'une expression arbitraire ou d'un appel de fonction en C++. On infère le type de retour de l'expression à l'aide des règles suivantes :

• tous les opérateurs de comparaison ainsi que &&, || et ! retourne un booléen ;
• le type de retour de de la version préfixée de ++ et de -- est T& où T est le type de l'argument ;
• on suppose que tous les autres opérateurs (unaire ou binaire) ont un type de retour identique à celui de leur premier argument.

Un moyen facile pour déterminer le type de retour d'une ILE est d'observer si dans son ensemble elle représente ou non une comparaison. Si oui, elle renvoie un booléen, sinon le type de retour est déterminé par le premier argument de l'opérateur qui est évalué en dernier dans l'ILE. Voici quelques exemples :

    lref<int> x=3; 
    double y=1;
    2.0 * x;    // double
    x * 2.0;    // int
    y*x;        // double
    x*y;        // int
    2*x + 3.1;  // int
    3.1 + 2*x;  // double
    5 < x;      // bool
    x == x;     // bool
    x < 3*x+5;  // bool
    3*x+5 < x;  // bool
    ++x;        // int&

Pour les opérateurs, tous les opérateurs surchargeables sauf les suivants sont supportés pour la création d'ILE :

• l'opérateur & pour l'obtention d'adresse ;
• l'opérateur * pour déférencer ;
• l'opérateur -< pour accéder aux membres' ;
• l'opérateur [] ;
• l'opérateur virgule ;
• tous les opérateurs d'assignation (=, +=, *=…).

Comme l'assignation est utilisée pour assigner une nouvelle valeur à une référence logique, il est évident que ses opérateurs ne peuvent pas être utilisés pour produire une ILE. De façon similaire, l'opérateur de déférencement et l'opérateur -< sont utilisés pour accéder aux valeurs sous-jacentes et cela les évince des ILE. L'opérateur de prise d'adresse et l'opérateur virgule prennent la sémantique par défaut du C++ quand ils sont utilisés sur des lref. Finalement, il n'y a aucun moyen de connaître le résultat de l'opérateur d'indexage, il reste ainsi non supporté.

La liste suivante est le résumé essentiel des différents points couverts dans cette section sur les ILE :

• les ILE sont des expressions pouvant être traitées comme des foncteurs ;
• chaque ILE possède sa propre closure, ainsi elle peut être évaluée en toute sécurité même après la sortie de porté de certaines variables ;
• les ILE sont soit pures soit impures ;
• seules les ILE pures devraient être utilisées pour créer des relations-ILE ;
• les relations-ILE ne peuvent pas produire de valeurs, elles peuvent juste tester les valeurs produites par d'autres relations ;
• le type de retour d'une ILE est déterminé par les règles présentées avant ;
• la plupart des opérateurs surchargeables sur une référence logique sont supportés pour créer une ILE.

Typiquement, les références logiques en tant que paramètre d'une relation sont bidirectionnelles. Une relation génère une valeur pour une référence logique passée en paramètre si celle-ci n'est pas initialisée. Cependant, ce n'est pas toujours faisable ou sensé pour une relation de générer des valeurs que pour certains de ses paramètres. La valeur de ces références doit être définie au moment où la relation est évaluée. De telles références sont appelées paramètres d'entrée.

Considérons la relation not_eq qui réussit si ses deux paramètres ne sont pas égaux.

relation not_eq( lref<int> lhs_, lref<int> rhs_)
{
    return ...
}

Dans ce cas, c'est évident de comparer les deux arguments pour vérifier s'ils sont égaux ou non. Mais si un des deux arguments n'est pas initialisé, sur quelles bases pouvons-nous générer une valeur pour qu'elle soit différence de l'autre ? Il y a plusieurs possibilités et aucune approche ne peut être facilement proclamée meilleure qu'une autre. Par exemple, on peut commencer à 0 et aller jusqu'a numeric_limits<int>::max(). Ou démarrer de numeric_limits<int>::min() et aller à numeric_limits<int>::max(). Ou encore aller à l'envers en partant de numeric_limits<int>::max().

Tenter de générer des valeurs dans un intervalle aussi grand est rarement un moyen très productif pour résoudre les problèmes. La futilité d'une telle approche est encore plus évidente si on considère la même relation sur une std::string. Ceci fait de lhs_ et de rhs_ des paramètres d'entrée. Par convention, de tels paramètres sont suffixés par '_' alors que les paramètres classiques ne le sont pas.

Un autre exemple est la relation size fournie par Castor.

relation size(lref<Cont>& cont_
        , lref<typename Cont::size_type> sz) {
  return ...
}

Le premier argument est un conteneur et le second la taille du conteneur. Il est simple de tester la taille du conteneur est bien sz et aussi facile de remplir le conteneur de sz objets. Mais que se passe-t-il si les deux arguments ne sont pas initialisés ? C'est un non-sens total de remplir le conteneur d'un nombre arbitraire d'éléments. Ainsi, on spécifie cont_ comme étant un paramètre d'entrée.

Dans chacun de ces cas, c'est au consommateur de la relation de décider comment les valeurs des paramètres d'entrées doivent être générées.

Le processus de backtracking est par sa nature profonde très dépendant de la capacité d'annuler les effets de bord quand il poursuit de nouveaux chemins. D'un autre côté, les entrées/sorties sont quelque chose que l'on peut rarement annuler. Une fois que quelque chose a été écrit dans un socket ou un document imprimé, il n'y a pas de retour en arrière. Ainsi, entrées/sorties et backtracking sont brouillés. Il y a deux moyens de les faire coexister. La première option est de demander la réversibilité de toutes les entrées/sorties. C'est clairement impossible à faire. La seconde option est de ne pas prendre en compte les entrées/sorties qui ont lieu lors de l'évaluation d'une relation. C'est le seul moyen réaliste pour qu'ils coexistent. Cependant, c'est au consommateur de la relation de vérifier que de tels effets de bord n'affectent pas avec les choix faits par le backtracking. Les effets de bord devraient être utilisés de façon à ne pas interférer avec le backtracking.

Les relations write et read sont des exemples de relations d'entrés/sorties dans Castor. Considérons la (mauvaise) utilisation de read pour vérifier si le mot lu depuis stdin est « Hello » ou « Word ».

relation r = read("Hello") ^ read("World");

Alors que la première lecture du code peut être « lire soit Hello soit World », la réalité fait que le code suppose que si la première lecture échoue, ses effets de bord seront annulés de telle sorte que la seconde lecture puisse relire les données. La bonne façon de faire est la suivante :

lref<string> w;
relation r = read(w) && 
       (eq(w,"Hello") ^ eq(w,"World"));

Ici, nous lisons la valeur (quelle qu'elle soit) et on vérifie si elle vaut soit « Hello » soit « World ».

Ici, nous allons nous intéresser à la recherche de chemin dans un graphe acyclique direct de cinq nœuds. Ce graphe peut facilement être décrit en termes d'arêtes. Dans la relation edge suivante, chaque ligne représente une arête directe du graphe. Les paramètres n1 et n2 représentent respectivement le point de départ et celui d'arrivée.

// représentation du graphe de la figure au-dessus.
relation edge(lref<int> n1, lref<int> n2) {
  return eq(n1,1) && eq(n2,2) 
      || eq(n1,2) && eq(n2,3) 
      || eq(n1,3) && eq(n2,4) 
      || eq(n1,5) && eq(n2,4) 
      || eq(n1,5) && eq(n2,2) 
  ;
}

Avec la définition de la relation ci-dessus, on peut dire qu'un chemin existe entre deux nœuds si :

une arête directe existe en Start et End OU

une arête directe existe entre Start et un nœud X ET un chemin existe entre X et End

relation path(lref<int> start, lref<int> end) {
  lref<int> nodeX;
  return edge(start, end)
      || edge(start, nodeX)
           && recurse(path, nodeX, end);
}

Avec les définitions présentées, nous sommes capables de poser des requêtes à propos du graphe. Une question simple est de voir si un chemin existe entre deux nœuds.

relation p1_4 = path(1, 4);
if(p1_4())
  cout << "Un chemin existe entre 1 et 4";

Un problème typique dans la théorie des graphes est de trouver tous les nœuds atteignables depuis un nœud donné. Le code suivant montre tous les nœuds qu'on peut atteindre depuis le nœud 5.

lref<int> node;
relation p5 = path(5, node);
while(p5())
 cout<< *node <<" est atteignable depuis le noeud 5\n";

En laissant la variable node non initialisée, on laisse l'ordinateur générer des valeurs pour nous. Il est intéressant de noter que le nœud 4 apparaît deux fois. Ceci est dû au fait que le nœud 4 est accessible par deux chemins distincts depuis le nœud 5. De façon similaire, en laissant le premier argument non initialisé et en spécifiant 5 en tant que second argument, on va obtenir la liste des nœuds qui peuvent atteindre le nœud 5.

Il est aussi possible de lister toutes les arêtes existantes en laissant les deux arguments non initialisés.

lref<int> n1, n2;
relation p = path(n1, n2);
cout<< "Path found between these nodes\n"
while(p())
  cout << "(" << *n1 <<","<< *n2 << ") ";

Le code au-dessus va afficher les paires dans l'ordre suivant: (1,2) (2,3) (3,4) (5,4) (5,2) (1,3) (1,4) (2,4) (5,3) (5,4). Une fois encore, la paire (5,4) est présente deux fois, car il existe deux chemins pour aller de 5 à 4.

Un automate à états finis peut être représenté comme un ensemble de transitions et d'états final. La classe Nfa ci-dessous exprime le non-déterminisme de automate fini présent en figure 2 qui est équivalent à l'expression régulière ((ab)*ba) | b. La classe possède deux fonctions membres statiques transition et final. La relation transition décrit chaque transition en termes de couple d'états et le caractère d'entrée permet de réaliser la transition. La relation finale donne l'état final de l'automate.

Une relation libre run définit la règle pour que l'exécution d'un automate soit réussie en fonction d'une chaîne d'entrée. L'automate sur lequel elle opère est spécifié en tant que paramètre template. L'exécution est une réussite si :
la chaîne est vide ET l'état final est atteint OU

Il existe une transition entre l'état courant st1 et un autre état st2 déclenchée par le premier caractère de la chaîne ET l'exécution est réussie en partant depuis l'état st2.

La fonction statique transition de la classe NFA décrit l'état de transition et la fonction statique finale l'état final. La relation libre run prend l'automate en entrée en tant que paramètre template et l'exécute.

class Nfa { // => ((ab)*ba)|b
  static const char a = 'a', b = 'b';
public:
  // tranistions NFA 
  static relation transition( lref<int> st1
                            , lref<char> ch
                            , lref<int> st2) {
    return 
       eq(st1,0) && eq(ch,a) && eq(st2,1)
    || eq(st1,0) && eq(ch,b) && eq(st2,2)
    || eq(st1,0) && eq(ch,b) && eq(st2,4)
    || eq(st1,1) && eq(ch,b) && eq(st2,0)
    || eq(st1,2) && eq(ch,a) && eq(st2,3)
    ;
  }

  // tous les états finals de l'automate'
  static relation final(lref<int> state) {
    return eq(state,3) || eq(state,4);
  }
};
// détermine la réussite d'un automate
template<typename FA> 
relation run(lref<string> input
                , lref<int> currSt=0) {
  lref<char>   firstCh;
  lref<string> rest;
  lref<int>    nextSt;

 return 
   eq(input,"") && FA::final(startSt)
|| head(input,firstCh) && tail(input,rest)
      && FA::transition(currSt,firstCh,nextSt)
      && recurse(run<FA>, rest, nextSt)
   ;
}

Avec la relation au-dessus, n'importe quelle chaîne de caractères peut être testée avec l'automate.

if( run<Nfa>("aabba")() )
    cout << "Correspondance";
else
    cout << "Pas de correspondance";