* Stage Paul Blouet
** Nouvelle implémentation
deux objectifs
- intégration
- efficacité
*** Organisation
agents
- Channel^*
- Relation^*
- Rule^*
- Solution
Rule = Var<T>^* -> (Premise x (Valuation -> (Guard x Conclusion)))
Premise ::= Reagent^* OR Reagent^* x VarSolution
Reagent ::= Message<T> OR State<T>
Message<T> = Channel x Pattern<T>
State<T> = Relation x Pattern<T>
Pattern<T> ::= LeftF Pattern<T'>^* OR Var<T>
match(T) : Valuation
implicit conversion: T -> Pattern<T>
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<Var>> OR Atom<Pattern<Var>> & Premise
- Atom<T> ::= Message<T> OR State<T>
- Message<T> ::= Channel * T
- State<T> ::= Relation * T
- Pattern<X> ::= 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<Any> OR Atom<Any> & Conclusion // Contraintes à ajouter
- Any contient : Pattern<Any> // s(Var) ie s.apply(Var) : Any
OR Pattern<Any> op Pattern<Any>
firewall
interpretation
*** Version 12/03
**** Agent ::= ChannelSymbol^* 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
}
**** Rule ::= Variable[T]^* x Premise x (Valuation -> (Guard x Conclusion))
***** 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) = { ... }
// alternative :
override val rhs = (s : Valuation) => { ... }
}
TODO syntaxe avec object compagnon à prévoir
TODO rapport avec les gardes de présence - a priori : trait parent de Rule
**** Relation[T] ::= RelationSymbol { apply : Pattern[T] -> OpenAtom, apply : T -> ClosedAtom}
Résolution de la surchage avant usage de toute conversion implicite (ce
qui est logique)
Conséquences
1. Il n'est pas possible d'utiliser une conversion implicite
à gauche de T vers Pattern[T].
R(x : T) deviendrait R(x : Pattern[T]).
Avec la définition de Relation, on a :
R(x : T) devient R.apply(x : T) qui produit un ClosedAtom (à droite).
2. On utilise un opérateur unaire pour plonger T dans Pattern[T].
TODO Utiliser ~ pour le plongement.
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.
***** Usage
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.
**** Alternative (choix abandonné) : RelationGenerator[T] ::= (Relation, PatternRelation[T], TermRelation[T])
TODO Abandon : problème d'enchaînement des conversions
Retour à un opérateur explicite tilde pour les constructeurs (mais pas
pour les constantes)
Mieux : opérateurs pour les patterns intégrant la conversion
Exemple : les listes, les couples à faire, autres types à faire
PatternRelation[T] ::= { apply : Pattern[T] -> OpenAtom }
TermRelation[T] ::= { apply : T -> ClosedAtom }
Dans Premise:
conversion implicite de RelationGenerator[T] vers PatternRelation[T]
Dans Conclusion et Solution :
conversion implicite de RelationGenerator[T] vers TermRelation[T]
***** Usage
// Notation utilisant des objets compagnons et des opérateurs surchargés (&)
val r = Rule {
val x = Var[T] // Astuce : Var est une méthode générique privée renvoyant
une variable
override val lhs = Premise(R(x) & R(y))
override def rhs(s : Valuation) : (Guard, Conclusion) = { ... }
}
R(x) interprété en R.apply(x)
pas de apply dans Relation
donc recherche d'une conversion implicite :
comment la trouver ? Solution ci-dessous
***** Conversion implicite
(snippet à placer sur Githuh)
class Pattern
class Term
class OpenReactant
class ClosedReactant
class Valuation
class PatternRelation {
def apply(p : Pattern) : OpenReactant = new OpenReactant
}
class TermRelation {
def apply(t : Term) : ClosedReactant = new ClosedReactant
}
class Relation(val pR : PatternRelation, val tR : TermRelation){
}
object conversions {
implicit def relationToPatternRelation(r : Relation) : PatternRelation = r.pR
implicit def relationToTermRelation(r : Relation) : TermRelation = r.tR
implicit def termToPattern(t : Term) : Pattern = new Pattern
}
class Premise(val opR : OpenReactant){}
class Conclusion(val cR : ClosedReactant) {}
class Rule {
val r = new Relation (new PatternRelation,
new TermRelation)
val lhs : Premise = {
import conversions.relationToPatternRelation
import conversions.termToPattern
//new Premise(r(new Pattern)) //ok
new Premise(r(new Term)) //ok
}
def rhs(x : Valuation) : Conclusion = {
import conversions.relationToTermRelation
new Conclusion(r(new Term)) // ok
//new Conclusion(r(new Pattern)) // ko
}
}
**** Atomes, messages, réactifs, patterns
Atom ::= OpenAtom | ClosedAtom
Message ::= OpenMessage | ClosedMessage
OpenReactant ::= OpenMessage | OpenAtom
ClosedReactant ::= ClosedMessage | ClosedAtom
OpenAtom ::= (RelationSymbol, Pattern[Any])
ClosedAtom ::= (RelationSymbol, Any)
OpenMessage ::= (Channelsymbol, Pattern[Any])
ClosedMessage ::= (ChannelSymbol, 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])
TODO Attention à l'implémentation du filtrage qui doit prendre en compte des surtypes.
***** 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)
C(0) pour Zero
****** Usage
Fonction S(p: Pattern[Int]) = new Successor(p)
***** Cons < Pattern[TraversableOnce]
(TraversableOnce est le super-type de tous les itérables, de List à String en passant par Map)
Fonction K(t: TraversableOnce[Pattern[T]]): Pattern[TraversableOnce[T]]
Pour Empty, utiliser C(Nil) (Itérable vide de scala)
Pas de RCons, utiliser simplement l'itérable normal (par ex: List(!x, 0))
***** Cons < Pattern[(A, B)]
Fonction K(t: (A, B)): Pattern[(A, B)]
Pour arité 0: Unit
Pour arité 1: ne pas utiliser un tuple, juste le type
Pour arité > 2: utiliser (T1, (T2, .. (Tn-1, Tn) .. ))
***** 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.