Skip to content
This repository has been archived by the owner on Jun 28, 2020. It is now read-only.

Specification (fr)

Jump to bottom
Geogi edited this page Mar 13, 2013 · 8 revisions
  • Stage Paul Blouet

** Nouvelle implémentation

deux objectifs

  • intégration
  • efficacité

*** Organisation

agents

  • Channel^*
  • Relation^*
  • Rule^*
  • Solution

Rule = Var^* -> (Premise x (Valuation -> (Guard x Conclusion))) Premise ::= Reagent^* OR Reagent^* x VarSolution Reagent ::= Message OR State Message = Channel x Pattern State = Relation x Pattern

Pattern ::= LeftF Pattern<T'>^* OR Var match(T) : Valuation implicit conversion: T -> Pattern

distinguer LeftF et RightF

Guard ::= True OR False OR Guard or Guard OR Guard and Guard OR not Guard OR (Premise | Guard) OR NativeGuard

ancienne version ci dessous

  • Premise ::= Empty OR SolutionVar OR Atom<Pattern> OR Atom<Pattern> & Premise

  • Atom ::= Message OR State

  • Message ::= Channel * T

  • State ::= Relation * T

  • Pattern ::= X OR F * Pattern ... Pattern (F : user-defined) Pattern.match(Any) : Option Valuation

  • Var ::= FreeVar OR BoundVar Var.as(Any) // Permet "A(z) -> lambda s. not (A(y as (s(z)+1))|True)"

  • Valuation ::= Map<Var, Any>

  • Guard ::= True OR False OR Guard or Guard OR Guard and Guard OR not Guard OR (Premise | Guard)

  • Conclusion ::= EmptyConclusion OR SolutionVarConclusion OR Atom OR Atom & Conclusion // Contraintes à ajouter

  • Any contient : Pattern // s(Var) ie s.apply(Var) : Any OR Pattern op Pattern

    firewall

interpretation

*** Version 12/03

**** Agent ::= Channel^* x Relation^* x Rule^* x Solution ***** Trait ou classe? Le trait Agent n’a (actuellement) pas de classe d’implémentation. On l’utilise en faisant une classe anonyme avec la syntaxe: val agent = new Agent { ... } Ceci a été choisi pour permettre la définition de ses attributs dans son bloc d’implémentation, pour une meilleure lisibilité et un contrôle fin de la portée des variables. Il est cependant possible de transformer Agent en classe.

agent = new Agent { val k = Channel[T] // Astuce val R = Relation[T] // Astuce

// Rule : cf. infra }

TODO : implémenter Solution dans Agent

**** Rule ::= Variable[T]^* x Premise x (Valuation -> (Guard x Conclusion))

TODO mettre à jour la définition TODO définir correctement l'abstraction

***** Abstraction sur Variable Il était prévu Rule ::= Variable[T]^* -> (Premise x (Valuation -> (Guard x Conclusion)) L’idée était de fournir des variables fraîches à chaque évaluation de la règle. Ceci doit être implémenté de la manière suivante: Rule ::= Variable[T]^* -> RuleBody RuleBody ::= Premise x (Valuation -> (Guard x Conclusion)) Bien que cette structure de données soit correcte, rappelons qu’il est nécessaire d’utiliser des collections uniformément typées. Cependant, la collection de Agent référençant les règles aurait dans ce cas un type de la forme: Collection[(Variable[T1], .. Variable[Tn]) -> RuleBody] (il n'y a pas de supertype commun pertinent) Plusieurs solutions ont été explorées, par exemple décomposer l’abstraction: Rule ::= Variable[T1] -> .. Variable[Tn] -> RuleBody Toutefois, la difficulté d’implémentation reste présente, aussi la solution adoptée dans Mainline (pas d'abstraction sur Variable, abstraction sur Valuation) a été retenue. Ceci fonctionne en ne considérant Variable que comme un nom (à la manière de Relation).

***** Usage

val r = new Rule { val x = Var[T] // Astuce : Var est une méthode générique privée renvoyant une variable override val premise = new Premise(List(R(x), R(y)))
override def rhs(s : Valuation) : (Guard, Conclusion) { ... } }

TODO syntaxe avec object compagnon à prévoir

TODO rapport avec les gardes de présence - a priori : trait parent de Rule

**** Relation[T] ::= { apply : Pattern[T] -> OpenAtom, apply : T -> ClosedAtom}

Résolution de la surchage avant usage de toute conversion implicite (ce qui est logique)

***** Usage Relation est un sous-type de EntitySymbol, utilisé pour comparer les relations (ou messages) par référence. Le type ne contient aucune donnée.

val R = Relation[T] // Astuce val p : Pattern[T] = ... "R(p)" équivalent à "R.apply(p)" résolu en "apply : Pattern[T] -> OpenAtom"

Remarque : déclaration possible apply[T : Pattern] ("... bound")

val v : T = ... "R(v)" équivalent à "R.apply(v)" résolu en "apply : T -> ClosedAtom"

TODO Garantir si possible que les méthodes apply sont les seuls constructeurs de OpenAtom et ClosedAtom

Conclusion : on vérifie ainsi que les atomes sont bien typés.

**** Atomes, messages, réactifs, patterns

TODO Mettre à jour la terminologie

Atom ::= OpenAtom | ClosedAtom Message ::= OpenMessage | ClosedMessage OpenReactant ::= OpenMessage | OpenAtom ClosedReactant ::= ClosedMessage | ClosedAtom

OpenAtom ::= (Relation, Pattern[Any]) ClosedAtom ::= (Relation, Any) OpenMessage ::= (Channel, Pattern[Any]) ClosedMessage ::= (Channel, Any)

Pattern : termes ouverts à l'intérieur d'un pattern Term (non présent) : en fait Any - termes fermés Value (non présent) : en fait Any - forme normale des termes fermés

**** Solution ::= ClosedReactant^*

Structure immutable définissant l'état initial

Remarque : les réactifs contiennent des valeurs.

**** Patterns

***** Pattern[+T] ::= { abstract matching : (T, Valuation) => (Boolean, Valuation) }

Trait complètement abstrait Valuations immutables Covariance (raison : Pattern[T] < Pattern[Any])

***** Variable[+T] < Pattern[T]

A priori, des noms purs Covariance

Implémentation facile de matching

Extension : unary_!(implicit s: Valuation): T = (s(this) getOrElse (throw new NoSuchException("impossible !"))).asInstanceOf[T] (utilisé à droite)

***** Const[T] < Pattern[T]

****** Définition

Enveloppe d'un T

Implémentation facile de matching

****** Usage

c(1) pour 1 où c est une méthode d'un objet dont le nom est le paquet et est importé avec le paquet.

TODO Peut-on se passer de c ? Peut-on envisager une notation comme # ?

***** Succ, Zero < Pattern[Int]

****** Définition

Implémentation facile de matching

class Succ(pred : Pattern[Int]) extends Pattern[Int] override def matching(x : Int, v : Valuation) = (x <= 0)? (false, v) : pred.matching(x - 1, v)

class Zero extends Pattern[Int] override def matching(x : Int, v : Valuation) = (x != 0)? (false, v) : (true, v)

****** Usage

TODO prévoir une notation simplifiée

***** Cons, Empty, RCons < Pattern[String]

TODO à implémenter

***** Cons, Empty, RCons < Pattern[List]

TODO à implémenter

***** Types Criojo

types algébriques

TODO définir un petit outil permettant de les engendrer à partir d'une description

**** Premise ::= OpenReactant^*

Structure immutable définissant la prémisse de la règle

TODO syntaxe agréable

TODO Comment vérifier que les variables utilisées sont déclarées dans la règle ? Peut-être prévoir un visiteur pour chaque pattern.

**** TODO Premise ::= Pattern^* x State^* ***** Automates Une prémisse est créée avec une liste de Pattern (parent de AtomPattern et MessagePattern). Elle génère alors un seul état dans sa collection: l’état initial (s := valuation vide, left := tous les Pattern, right := vide). Lorsqu’une Instance est proposée à la prémisse, elle parcourt l’ensemble de ses états. Si l’instance match avec un Pattern de gauche d’un état, celui-ci renvoie le nouvel état correspondant. L’ensemble des états de la prémisse est alors mis à jour, et elle renvoie la liste de ceux qui sont terminés (left vide). Lorsque la prémisse est notifiée qu’une Instance a été supprimée, elle parcourt ses états et supprime tous ceux qui l’utilisaient (right contient instance).

**** TODO Valuation ::= (Variable -> Any)^* ***** Variable libre ou liée Valuation référence toutes les variables liées d’un State, ainsi que la valeur associée. Lorsque la méthode get d’une variable est utilisée, la valuation cherche la variable dans son dictionnaire. Si elle ne la trouve pas, elle lève une exception (NoSuchElementException). Sinon elle renvoie la valeur. Lorsque la méthode set d’une variable est utilisée, l’entrée correspondante est ajoutée au dictionnaire de la valuation. ***** Pourrait être immutable Dans l’état actuel, Valuation utilise un dictionnaire mutable. Cependant, Valuation est nécessairement clonée à son utilisation (puisque les états doivent être conservés, donc sont immutables par nécessité). Il pourrait donc être envisagé d’utiliser un type immutable à la place.

**** TODO Guard ::= TrueGuard | FalseGuard | AndGuard Guard Guard | OrGuard Guard Guard | NativeGuard | WhereGuard Premise Guard | IntrospectionGuard ***** Utilisation Guard est une ébauche. Elles ne sont pour l’instant pas évaluées. Actuellement, elle contient uniquement une methode evaluate qui renvoie un booléen. Pour les trois dernières gardes, l’idée est la suivante:

  • NativeGuard: renvoie un booléen calculé par Scala
  • WhereGuard: lier d’une manière ou une autre la prémisse d’une règle à l’ensemble des prémisses de ses WhereGuard (par exemple en réécrivant les WhereGuard comme des couples gauche/droite dans prémisse/conclusion), puis évaluer la sous-garde.
  • IntrospectionGuard: demander la spécialisation d’un Inspector qui aurait une gestion spéciale dans la Solution (il faudrait rajouter un Inspector^* dans celle-ci). Celui-ci est chargé de mettre à jour son evaluate en fonction des modifications des Instance dans la Solution. ***** Pourquoi pas juste un booléen? Le schéma proposé (TrueGuard, AndGuard, etc) paraît redondant avec la définition du booléen. Pourquoi ne pas considérer une garde simplement comme un booléen, avec les commodités WhereGuard et IntrospectionGuard présentées ci-dessus?

**** TODO Instance ::= Symbol x (AtomInstance | MessageInstance) Représente soit un atome soit un message. Le symbole est une référence à une classe d’implémentation de EntitySymbol et sert au matching (e.g. Relation). ***** AtomInstance ::= Any^* Créé avec Relation.apply(Any^) (méthode surchargée). C’est pour cette raison qu’il n’est pas possible de faire une conversion implicite d’une constante vers un Pattern: la constante est un Any, et la surcharge est prioritaire sur la conversion implicite, donc R(0, x) est vu comme AtomInstance(Any (ici Int), Any (ici Variable[T])) tandis que R(C(0), x) est vu comme AtomPattern(Pattern[Any] (ici Const[Int]), Pattern[Any] (ici Variable[T])) Le symbole est fourni par la Relation. ***** MessageInstance ::= Channel x Any^ Comme AtomInstance, mais avec un Channel en plus. Il s’agit d’une ébauche. On fait Channel.apply(Any^*) pour créer un MessageInstance. Le symbole est le singleton Message.

**** TODO Pattern ::= Symbol x (AtomPattern | MessagePattern) Identique à Instance, mais accepte des Pattern[Any] au lieu de Any. Utilisé à gauche dans les règles.

Clone this wiki locally