Inférence à chaînage avant avec variables¶

""" Fonctions utilitaires pour gérer des propositions sans ou avec variables\
    dans un moteur d'inférence.
"""

def est_atomique(proposition):
    """ Vérifie si la proposition courante est un atome (c'est le cas s'il\
        s'agit d'un string).

        :param proposition: une proposition.
        :return: ``True`` si la proposition est de type string.
    """
    return type(proposition) == type('')

def est_une_variable(proposition, marqueur='?'):
    """ Vérifie si la proposition courante est une variable (c'est le cas s'il\
        s'agit d'un atome dont la description commence par le marqueur de\
        variables).

        :param proposition: une proposition.
        :param marqueur: marqueur de variable avec valeur par défaut : ``'?'``.
        :return: ``True`` si l'argument est un atome et commence par le marqueur\
        de variables.
    """
    return est_atomique(proposition) and proposition[0] == marqueur

def tete(proposition):
    """ Coupe la proposition courante et retourne son premier élément.

        A noter que dans le cas d'une proposition atomique, la méthode soulève\
        une exception.

        :param proposition: une proposition.
        :return: la tête de la proposition composée.
    """

    if est_atomique(proposition):
        raise Exception("Proposition atomique: Impossible de la segmenter.")
    elif len(proposition) > 0:
        return proposition[0]
    else:
        raise Exception("Proposition vide: Impossible de la segmenter.")

def corps(proposition):
    """ Coupe la proposition courante et retourne la portion située après le\
        premier élément.

        A noter que dans le cas d'une proposition atomique, la méthode soulève\
        une exception.

        :param proposition: une proposition.
        :return: le corps de la proposition composée.
    """

    if est_atomique(proposition):
        raise Exception("Proposition atomique: Impossible de la segmenter.")
    elif len(proposition) > 0:
        return proposition[1:]
    else:
        raise Exception("Proposition vide: Impossible de la segmenter.")

def lister_variables(proposition):
    """ Retourne un ensemble (de type ``set``) contenant les variables\
        mentionnées dans la proposition courante.

        :param proposition: une proposition.
        :return: la liste des variables apparaissant dans la proposition.
    """

    variables = set()
    if est_atomique(proposition):
        if est_une_variable(proposition):
            variables.add(proposition)
    else:
        for sous_prop in proposition:
            variables.update(lister_variables(sous_prop))
    return variables

class RegleAvecVariables:
    """ Représentation d'une règle d'inférence pour le chaînage avec\
        variables.
    """

    def __init__(self, conditions, conclusion):
        """ Construit une règle étant donné une liste de conditions et une\
            conclusion.

            :param list conditions: une collection de propositions (pouvant\
            contenir des variables) nécessaires à déclencher la règle.
            :param conclusion: la proposition (pouvant contenir des variables)\
            résultant du déclenchement de la règle.
        """

        self.conditions = conditions
        self.conclusion = conclusion

    def depend_de(self, fait, methode):
        """ Vérifie qu'un fait fait partie, sous réserve de substitution,\
            des conditions de la règle.

            :param fait: un fait qui doit faire partie des conditions de\
            déclenchement.
            :param methode: ``Filtre`` ou ``Unificateur``, détermine le type\
             de pattern match à appliquer.
            :return: un dictionnaire qui attribue un environnement à chaque\
            condition qui peut être satisfaite par le fait pasée en paramètre.\
            ``False`` si aucune condition n'est satisfaite par le fait.
        """
        envs = {}

        for condition in self.conditions:
            # Si au moins une des conditions retourne un environnement,
            # nous savons que la proposition satisfait une des conditions.
            env = methode.pattern_match(fait, condition, {})
            if env != methode.echec:
                envs[condition] = env

        return envs

    def satisfaite_par(self, faits, cond, env, methode):
        """ Vérifie que des faits suffisent, sous réserve de substitution,\
            à déclencher la règle.

            :param list faits: une liste de faits.
            :param cond: la condition qui a donné lieu à ``env`` par le\
            pattern match.
            :param dict env: un environnement de départ déjà établi par\
            ``depend_de``.
            :param methode: ``Filtre`` ou ``Unificateur``, détermine le type\
             de pattern match à appliquer.
            :return: une liste d'environnements qui correspondent à toutes les\
            substitutions possibles entre les conditions de la règle et les\
            propositions. On retourne une liste vide si au moins une condition\
            ne peut être satisfaite.
        """
        envs = [env]

        # On n'a pas besoin de tester ``cond`` car cela a été fait dans l'appel
        # à ``depend_de`` qui précède l'appel à cette méthode.
        conditions_a_tester = [cond1 for cond1 in self.conditions if cond1 != cond]

        # Pour chaque condition dans la liste des conditions, si la liste
        # des environnements n'est pas vide, on y ajoute les environnements
        # qui permettent de satisfaire une des conditions.
        for cond1 in conditions_a_tester:
            envs_nouveaux = []

            for fait in faits:
                for env1 in envs:
                    env1 = methode.pattern_match(fait, cond1, env1)
                    if env1 != methode.echec:
                        envs_nouveaux.append(env1)

            # Si au moins une condition n'est pas satisfaite, la règle ne l'est pas non plus.
            if len(envs_nouveaux) == 0:
                return []

            envs = envs_nouveaux

        return envs

    def __repr__(self):
        """ Représentation d'une règle sous forme de string. """

        return '{} => {}'.format(str(self.conditions), str(self.conclusion))

from moteur_sans_variables.chainage import Chainage
from .filtre import Filtre

class ChainageAvantAvecVariables(Chainage):
    """ Un moteur d'inférence à chaînage avant avec variables. """

    def __init__(self, connaissances, methode=None):
        """
            :param methode: ``Filtre`` ou ``Unificateur``, détermine le type de\
            pattern match à appliquer. ``Filtre`` par défaut.
        """

        Chainage.__init__(self, connaissances)

        if methode is None:
            self.methode = Filtre()
        else:
            self.methode = methode

    def instancie_conclusion(self, regle, envs):
        """ Instancie la conclusion d'une règle pour tous les environnements.

            :param regle: la règle dont la conclusion doit être instanciée.
            :param list envs: les environnements servant à instancier la\
            conclusion.
            :return: une liste de propositions correspondant aux différentes\
            instanciations de la conclusion.
        """
        return [self.methode.substitue(regle.conclusion, env) for env in envs]

    def chaine(self):
        """ Effectue le chaînage avant sur les faits et les règles contenus\
            dans la base de connaissances.
        """
        queue = self.connaissances.faits[:]
        self.reinitialise()

        while len(queue) > 0:
            fait = queue.pop(0)

            if fait not in self.solutions:
                self.trace.append(fait)
                self.solutions.append(fait)

                # Vérifie si des règles sont déclenchées par le nouveau fait.
                for regle in self.connaissances.regles:
                    cond_envs = regle.depend_de(fait, self.methode)
                    for cond, env in cond_envs.items():
                        # Remplace l'environnement par ceux qui satisfont
                        # toutes les conditions de la règle et pas seulement la
                        # première condition.
                        envs = regle.satisfaite_par(self.solutions, cond, env, self.methode)

                        # Ajoute la conclusion de la règle instanciée pour tous
                        # les environnements possibles.
                        if len(envs) > 0:
                            queue.extend(self.instancie_conclusion(regle, envs))
                            self.trace.append(regle)

        return self.solutions

from .proposition_avec_variables import est_atomique, est_une_variable, tete, corps

class Filtre:
    """ Classe implémentant les méthodes de filtrage de propositions avec\
        variables.
    """

    echec = 'échec'

    def substitue(self, pattern, env):
        """ Effectue des substitutions de variables par leurs valeurs dans un\
            pattern.

            :param pattern: une proposition dont les variables doivent être\
            remplacées par des valeurs.\
            Une proposition est soit un atome, soit une liste contenant des\
            atomes et / ou d'autre listes.
            :param dict env: un environnment, c'est-à-dire un dictionnaire de\
            substitutions ``{variable : valeur}``.
            :return: le pattern dont les variables ont été remplacées par leurs\
            valeurs dans l'environnment.
        """
        if est_atomique(pattern):
            if pattern in env:
                return env[pattern]
            else:
                return pattern

        pattern_subst = ()

        for sous_pattern in pattern:
            sous_pattern_subst = self.substitue(sous_pattern, env)
            pattern_subst = pattern_subst + (sous_pattern_subst,)

        return pattern_subst

    def filtre(self, datum, pattern):
        """ Effectue le filtrage entre un datum et un pattern.

            :param datum: une proposition sans variables.
            :param pattern: une proposition pouvant contenir des variables.
            :return: un environnment c'est-à-dire un dictionnaire de\
            substitutions ``{variable : valeur}``, ou ``'échec'`` si le filtrage\
            échoue.
        """
        if len(pattern) == 0 and len(datum) == 0:
            return {}

        if len(pattern) == 0 or len(datum) == 0:
            return Filtre.echec

        if est_atomique(pattern):
            if datum == pattern:
                return {}
            if est_une_variable(pattern):
                return {pattern: datum}

            return Filtre.echec

        if est_atomique(datum):
            return Filtre.echec

        datum_tete = tete(datum)
        pattern_tete = tete(pattern)
        datum_reste = corps(datum)
        pattern_reste = corps(pattern)

        tete_env = self.filtre(datum_tete, pattern_tete)

        if tete_env == Filtre.echec:
            return Filtre.echec

        pattern_reste = self.substitue(pattern_reste, tete_env)
        reste_env = self.filtre(datum_reste, pattern_reste)

        if reste_env == Filtre.echec:
            return Filtre.echec

        tete_env.update(reste_env)

        return tete_env

    def pattern_match(self, datum, pattern, env=None):
        """ Effectue le filtrage en tenant compte d'un environnement initial.

            :param datum: une proposition sans variables.
            :param pattern: une proposition pouvant contenir des variables.
            :param dict env: l'environnement initial à prendre en compte.
            :return: un nouvel environnment ou ``'échec'``.
        """
        if env is not None:
            env = env.copy()
        else:
            env = {}

        pattern = self.substitue(pattern, env)
        resultat = self.filtre(datum, pattern)
        if resultat == Filtre.echec:
            return Filtre.echec

        env.update(resultat)
        return env

from .proposition_avec_variables import est_atomique, est_une_variable, tete, corps

class Unificateur:
    """ Classe implémentant les méthodes de l'unification de propositions avec\
        variables. """

    echec = 'échec'

    def substitue(self, pattern, env):
        """ Effectue des substitutions de variables dans un pattern.

            :param pattern: une proposition dont les variables doivent être\
            remplacées par d'autres propositions.
            :param dict env: un environnment, c'est-à-dire un dictionnaire de\
            substitutions ``{variable : proposition}``.
            :return: le pattern dont les variables ont été remplacées les\
            propositions qui leur sont associées dans l'environnement.
        """
        if est_atomique(pattern):
            if pattern in env:
                return self.substitue(env[pattern], env)
            else:
                return pattern

        pattern_subst = ()

        for sous_pattern in pattern:
            sous_pattern_subst = self.substitue(sous_pattern, env)
            pattern_subst = pattern_subst + (sous_pattern_subst, )

        return pattern_subst

    def unifie(self, prop1, prop2):
        """ Effectue l'unification entre deux propositions.

            :param prop1: une proposition pouvant contenir des variables.
            :param prop2: une proposition pouvant contenir des variables.
            :return: un environnment, c'est-à-dire un dictionnaire de\
            substitutions ``{variable : proposition}``, ou ``'échec'`` si\
            l'unification a échoué.
        """
        if len(prop1) == 0 and len(prop2) == 0:
            return {}
        if len(prop1) == 0 or len(prop2) == 0:
            return Unificateur.echec

        # Une des deux propositions est un atome => on essaie de le matcher.
        if est_atomique(prop1) or est_atomique(prop2):
            if prop1 == prop2:
                return {}

            if not est_atomique(prop1):
                prop1, prop2 = prop2, prop1

            if est_une_variable(prop1):
                if prop1 in prop2:
                    return Unificateur.echec
                else:
                    return {prop1: prop2}

            if est_une_variable(prop2):
                return {prop2: prop1}

            # Dans les autres cas, l'unification est un échec.
            return Unificateur.echec

        # Aucune des propositions n'est atomique : on unifie récursivement.
        prop1_tete = tete(prop1)
        prop2_tete = tete(prop2)
        prop1_reste = corps(prop1)
        prop2_reste = corps(prop2)
        tete_env = self.unifie(prop1_tete, prop2_tete)
        if tete_env == Unificateur.echec:
            return Unificateur.echec

        prop1_reste = self.substitue(prop1_reste, tete_env)
        prop2_reste = self.substitue(prop2_reste, tete_env)
        reste_env = self.unifie(prop1_reste, prop2_reste)
        if reste_env == Unificateur.echec:
            return Unificateur.echec

        tete_env.update(reste_env)
        return tete_env

    def pattern_match(self, prop1, prop2, env=None):
        """ Effectue l'unification en tenant compte d'un environnement initial.

            :param prop1: une proposition pouvant contenir des variables.
            :param prop2: une proposition pouvant contenir des variables.
            :param dict env: l'environnement initial à prendre en compte.
            :return: un nouvel environnment ou ``'échec'``.
        """
        if env is not None:
            prop1 = self.substitue(prop1, env)
            prop2 = self.substitue(prop2, env)
            env = env.copy()
        else:
            env = {}

        resultat = self.unifie(prop1, prop2)
        if resultat == Unificateur.echec:
            return Unificateur.echec

        env.update(resultat)
        return env