Specification (fr)

* 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.