Discussion :

[NoIdea]

Bonjour,

Voici mon problème : J'essaie de faire une structure de proposition générique. C'est à dire qu'une définition usuelle de la structure de Proposition (en notation Ocaml approximatif) pourrait-être

Proposition =
|Variable(Chaine de caractere)
|AND(Proposition*Proposition)
|OR(Proposition*Proposition)
|FORALL(Variable * Proposition)
...

Mon idée est de ne pas fixer les constructeurs :
-Soit la liste des constructeurs possibles est passée en paramètre template à ma structure de Proposition (cas 1)
-Soit la liste des constructeurs possibles est passée à l'éxecution (cas 2)

Je ne sais pas encore si je veux être dans le cas 1 ou dans le cas 2 : le cas 1 apporte plus de sécurité au niveau du code et de meilleures performances (je ne sais pas encore si j'en ai besoin) mais ne permet pas à l'utilisateur de modifier les constructeurs.
Mon idée pour le cas 1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
template<typename S1, typename ...SN>
struct Prop
{
   S1* cons;//NULL if not this constructor
   Prop<...SN> othercases;
};

Avec le constructeur X qui deviendrait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
struct X
{
   std::string name = "X";
   Type1 parameter1;
   Type2 parameter2;
   ...
   TypeN parameterN;
};

Il me semble que ceci fonctionnerait mais serait très désagréable à utiliser. Avez-vous une autre solution à proposer (ou une raison pour laquelle ceci ne marcherait pas ?)

Pour le cas 2, je ne vois pas d'autre manière que de passer par des void* et de définir un int pour chacun des types utilisables... :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
enum TypeID
{
   INT, PROP, CHAR, STRING, VARIABLE, ...
}
 
struct Constructor
{
    std::vector<TypeID> parameters;
    std::string name;
};
 
std::vector<Constructor> constructorList;
 
struct Prop
{
   Constructor c;
   void*data;//Qu'on interprète à partir des types de c
};

Y a t-il une meilleur implémentation à laquelle vous pensez ?

Merci pour votre aide.

[Bousk]

Bonsoir,

es-tu cantonné au C++ ?
C'est typiquement un exercice des plus difficiles en C++, mais qui devient d'une trivialité incroyable en Python.

[NoIdea]

es-tu cantonné au C++ ?

A la fois oui et non : le langage que je maitrise le mieux est de loin le c++ et le projet devrait être assez conséquent (ceci n'est que le début d'un logiciel qui pourrait permettre d'entièrement choisir les connecteurs logique/quantificateurs et les règles de calcul des prédicats, puis de choisir un/des langages et une/des théories pour faire des preuves à partir des nouvelles règle de déduction, et enfin d'appliquer des algorithmes sur ces preuves). Je préfère donc avoir un langage robuste que je maitrise bien. Cependant, si un autre langage permettrait de faire tout cela de manière beaucoup plus simple, tout en étant adapté à des gros projets (ce qui n'est pas le cas de Python en "stand alone"), je suis preneur. Une autre solution serait de mélanger les langages, mais puisque ce morceaux de code fait partie du cœur du projet, il me semble qu'il devrait être dans le langage principal.

[Bousk]

adapté à des gros projets (ce qui n'est pas le cas de Python en "stand alone")

Ha bon

[ternel]

Puisque tu connais OCaml, tu pourrais l'utiliser, c'est un langage assez adapté aux arbres syntaxiques.
à la fac, j'avais eu un cours de compilation, où nous avons écris en OCaml un compilateur pour une variante complexifiée de pascal.

[NoIdea]

Suite à vos réponses, je vais réfléchir et peut être décider d'un autre langage. Je voudrai tout de même savoir si il n'y a pas de meilleur implémentation en c++.

[oodini]

Je connais mal ces sujets, mais n'est-ce pas le domaine auquel s'attaque Boost.Proto ?

[Trademark]

Salut,

Typiquement, la traduction d'un type somme en C++ donne un variant donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

boost::variant<Variable, LogicAnd, LogicOr, ForAll, ...>

Par contre, et il n'y a pas beaucoup de solution, c'est assez lourd de s'en servir car tu dois passer par un mécanisme de visiteur, donc en gros créer une classe pour chaque traitement que tu veux faire sur ta structure. Tu peux notamment regarder ce projet qui implémente un mini-langage (calculatrice + booléen + if) avec un arbre de syntaxe représenté via des variantes (voir fichier ast.hpp).

D'un autre côté, à moins que tu ais besoin de performances et que ça soit critique dans ton projet (bien sur tout programme à besoin de performance, mais généralement moins que ce qu'on obtient avec C++), je te conseille d'utiliser un langage fonctionnel qui sera très adapté pour ça, comme OCaml ou Haskell. Si tu es libre de ton choix tu peux même utiliser le nouveau langage de Mozilla, Rust, qui est, je trouve, très bien fait. Si tu as besoin d'une large librairie standard, tu peux utiliser Scala, par contre ça aura à peu près les mêmes avantages (large librairie, portabilité, ...) / désavantage (performance, ...) que Java vu que ce langage est basé sur la JVM.

@oodini : Boost.Proto permet de définir des EDSL, donc d'avoir un mini-langage dans C++ et ainsi que l'arbre syntaxique soit déjà défini à la compilation, ce qui ne convient pas ici car je crois que l'OP veut quelque chose de plus dynamique.

[NoIdea]

Typiquement, la traduction d'un type somme en C++ donne un variant donc :

Oui, c'est exactement ça.

je te conseille d'utiliser un langage fonctionnel qui sera très adapté pour ça

C'est ce que je pensais faire, cependant, plus je réfléchis, plus j'ai l'impression que je vais être dans le cas 2 (donc la liste des constructeurs est donnée au runtime) et je ne vois pas ce que le fonctionnel m'apporte dans ce cas là. Y a-t-il un langage adapté au cas 2 ? Pensez-vous qu'il y a une meilleur solution que celle que je propose en C++ ?

[Trademark]

Je pense qu'il vaut mieux éviter le terme de constructeur ici parce que ça prête à confusion. Pour le cas 2, je ne vois pas ce que ça change à ton raisonnement, une variante marchera aussi bien qu'un sum type. De toute façon tu construiras ton arbre de syntaxe à l'exécution.

[NoIdea]

Je pense qu'il vaut mieux éviter le terme de constructeur ici parce que ça prête à confusion

Je pense que je parle vraiment de constructeur.

Pour le cas 2, je ne vois pas ce que ça change à ton raisonnement, une variante marchera aussi bien qu'un sum type. De toute façon tu construiras ton arbre de syntaxe à l'exécution.

Le cas 2 change tout : dans le cas 1, l'idée était de définir dans le code plusieurs type de propositions : certaine où forall existe, d'autre où forall n'existe pas par exemple. Puis de permettre à l'utilisateur de choisir le type de proposition (dont la liste serait déjà prédéfinie) qu'il souhaite manipuler. L'avantage des template est alors de rajouter des type de propositions à la liste de manière extrêmement simple. Ce qui donne le code suivant pour la définition (ou S1, ...SN sont les constructeurs : forall, and, or, ... par exemple) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
template<typename S1, typename ...SN>
struct Prop

Dans le cas 2, je ne souhaite pas fournir une liste de type de proposition déjà prédéfinie, je veux le laisser faire ce qu'il souhaite.
Ainsi, il pourra définir à l'exécution
MaFormule =
|And(MaFormule*MaFormule)
|Exists(Variable*Formule)
|Not(Formule)
|EmptySet
|IsIn(Variable*Variable)
...

[Trademark]

Mouai. Bon je vois deux possibilités, la première c'est que tu proposes un nombre défini de combinateur (du style ForAll, Implique, Exist, ...) et l'utilisateur choisira ceux qu'il voudra mettre dans son système. Dans ce cas, ce n'est pas au niveau de l'arbre syntaxique qu'il faudra empêcher l'utilisation des combinateurs mais lors de l'analyse sémantique. Par conséquent, dans ton AST, il faut que tu représentes tous tes termes.

Dans l'autre cas, tu peux vouloir que l'utilisateur crée lui-même ses propres combinateurs, ce qui est bien plus dur vu que c'est pas que la syntaxe qu'il faudra ajouter mais aussi toute la sémantique. Tu as des systèmes de plus haut niveau pour faire ça, je pense notamment aux systèmes de réécriture, mais ça sera forcément plus complexe, à la fois pour toi, et aussi pour l'utilisateur.

[NoIdea]

Mouai. Bon je vois deux possibilités, la première c'est que tu proposes un nombre défini de combinateur (du style ForAll, Implique, Exist, ...) et l'utilisateur choisira ceux qu'il voudra mettre dans son système. Dans ce cas, ce n'est pas au niveau de l'arbre syntaxique qu'il faudra empêcher l'utilisation des combinateurs mais lors de l'analyse sémantique. Par conséquent, dans ton AST, il faut que tu représentes tous tes termes.

Si je comprend bien, ceci est ce que j'appelle le "cas 1". Malheureusement, j'aimerais bien que l'utilisateur puisse rajouter des symboles.

Dans l'autre cas, tu peux vouloir que l'utilisateur crée lui-même ses propres combinateurs, ce qui est bien plus dur vu que c'est pas que la syntaxe qu'il faudra ajouter mais aussi toute la sémantique. Tu as des systèmes de plus haut niveau pour faire ça, je pense notamment aux systèmes de réécriture, mais ça sera forcément plus complexe, à la fois pour toi, et aussi pour l'utilisateur.

Je suppose que ce que tu appelles les règles sémantiques sont les règles de calcul des prédicats ?
Mon objectif est aussi de permettre à l'utilisateur de définir ses propres règles de calcul des prédicats. Je ne vois cependant pas ce où les systèmes de réécriture vont intervenir.

[Trademark]

Les systèmes de réécritures de terme porte bien ce nom, mais passons. Dans tous les cas, comment veux-tu que l'utilisateur entre à la fois le symbole mais aussi toutes la logique associée ? Le seul moyen pour moi c'est qu'il développe une extension de ton programme... Admettons que ton programme ne propose rien, comment l'utilisateur peut-il ajouter les booléens et puis le and (si ce n'est pas déjà prévu dans le code) ?