Discussion :

[Kalith]

Bonjour,

Je souhaiterais vous présenter un projet que j'ai commencé il y a peu.
On pourrait dire qu'il ne s'agit d'une simple calculatrice en ligne de commande : ça ne serait pas faux en soit, juste incomplet.

En effet, il s'agit d'un interpréteur extrêmement simple (la classe "State", moins de 900 lignes de code pour le moment, header inclus) qui permet de gérer des opérations entre des symboles. Il est, dans sa conception, relativement générique et permet l'ajout de nouveaux types sans modifier le code de base de l’interpréteur.

Ainsi, il est muni par défaut de trois types fondamentaux :

• "Symbol" : la classe de base dont doit hériter tout type. Utilisée seule, cette classe ne sert à rien pour le moment, mis à part à déclarer des symboles sans les définir.
• "Scalar" : contient un nombre réel (double précision), muni des opérateurs mathématiques habituels : multiplication (*), division (/), addition (+) et soustraction (-).
• "Reference" : contient une chaine de caractère qui est évaluée à chaque fois que la référence apparait dans une expression. C'est en gros un raccourcis vers une expression plus compliquée.

Le support du type "Scalar" par défaut pourrait être retiré, l'interpréteur n'en dépendant pas explicitement (mais une calculette sans nombre, je trouve ça quand même dommage).

Pour montrer que l'ajout de nouveaux types est possible simplement, j'ai mis également à disposition un type supplémentaire : Vector.
Ressemblant beaucoup au std::vector du C++, le type Vector est un conteneur unidimensionnel homogène (il contient N valeurs de types identiques). Il n'y a strictement aucune restriction sur le type de valeur contenue, ainsi il est possible de créer des Vector de Vector, et toute autre combinaison qui vous passe par la tête.
Il possède deux opérateurs généraux : l'addition (+) et la soustraction (-), plus la multiplication par un "Scalar" (commutative). Les 3-Vectors (vectors à 3 composantes) disposent également, pour le fun, du produit vectoriel (^).
Enfin, on peut utiliser l'opérateur '[]' pour accéder aux composantes du vector, en utilisant soit la notation "canonique" vector[]index, soit la notation C++ vector[index].
La syntaxe de construction d'un vector est la suivante : <elt1, elt2, ...> (l'utilisation des parenthèses étant réservée à leur sens mathématique premier, qui permet de grouper les expressions).

L'interpréteur peut fonctionner soit en ligne de commande, soit en lisant les commandes directement à partir d'un fichier.
Voici donc une suite d'exemples d'utilisation commentés, qui valent mieux qu'on long discours.
Vous trouverez les binaires pour Windows, ainsi que les sources (tout à fait portables), à la fin du message.

On commence par créer deux symboles 'a' et 'b' en une seule commande. Le symbole ';' permet, comme en C++, de signaler à l'interpréteur la fin d'une instruction.

Code :

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

1
2
3
> a;b
        Defining Symbol : a
        Defining Symbol : b

Le type Symbol est assez peu utile, on ne peut faire aucune opération dessus :

Code :

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

1
2
3
> a*b
        Error : No match for operator 'Symbol * Symbol' in :
                              a * b

On peut en revanche, même si l'intérêt est limité, créer un vecteur à partir de ces deux symboles :

Code :

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

1
2
> v = <a,b>
        Defining Vector : v = <a, b>

Attention cependant, l'interpréteur est tatillon, et ne supporte pas qu'un symbole soit non déclaré :

Code :

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

1
2
> w = <a,b,c>
        Error : Unknown symbol 'c'

On va maintenant passer aux nombres. Pour recommencer une nouvelle session sans fermer le programme, on peut utiliser la commande '~'. Utilisée seule, elle supprime tous les symboles précédemment définis, et utilisée devant le nom d'un symbole, elle détruit celui-ci.

Code :

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

1
2
3
4
5
6
> ~v
        Vector 'v' erased
> ~
        Warning : This command will erase all symbols.
                  Are you sure ? ([y|Enter]/n) y
        All symbols erased

Pour vérifier que tout s'est bien passé, on peut demander à l'interpréteur d'afficher le contenu de la variable 'a' :

Code :

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

1
2
> ?a
        'a' is undefined

Tout est ok ! On peut alors commencer sereinement. On affecte d'abord quelques valeurs numériques :

Code :

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

1
2
3
> a=1; b=2
        Defining Scalar : a = 1
        Defining Scalar : b = 2

Puis on peut évaluer une expression compliquée :

Code :

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

1
2
> (9+7)*(3-a)/(10-(4-b))
        Scalar : 4

Il est possible de rappeler le dernier résultat avec la commande '_' :

Code :

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

1
2
3
4
> _*_
        Scalar : 16
> _*_
        Scalar : 256

On peut également mélanger joyeusement scalaires et vecteurs, ou manipuler les composantes (l'indice dans les crochet est cyclique : pour un vecteur de taille N, v[N+i] = v[i] et v[-i] = v[N-i]). En cas d’ambiguïté d'ordre d'opérateurs (comme pour la 2nde ligne), l'expression est lue de gauche à droite séquentiellement :

Code :

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

1
2
3
4
> v = (0.5*_/b)*<1, 2*a, 3*b-2*a>
        Defining Vector : v = <64, 128, 256>
> v[4]/v[-1]/v[0]
        Scalar : 0.0078125

Pour compléter ce tour d'horizon, il ne nous reste plus qu'à présenter l'usage des références :

Code :

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

1
2
> r &= b*c
        Defining Reference : r = b*c

Les références étant évaluées seulement lorsqu'on en fait usage, il est autorisé d'y faire figurer des symboles non définis. Elles ne pourront alors être complètement évaluées que lorsque tous les symboles qu'elles contiennent sont définis :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
> r
        Reference : b*c
> c = <1,2,3>
        Defining Vector : c = <1, 2, 3>
> r
        Vector : <2, 4, 6>
> ~c
        Vector 'c' erased
> r
        Reference : b*c
> 4*r
        No match for operator 'Scalar * Reference' in :
                   4 * b*c

Cette dernière ligne montre ce qu'il me reste à implémenter pour que le système de référence soit plus ou moins complet. L'expression '4*r' devrait retourner une nouvelle référence...

Si vous avez envie de crier à l'arnaque, vous en avez le droit : pour le moment, pas de calcul formel au menu... Mais c'est bien entendu sur la ToDo list !

Le but principal de ce programme n'est pas de concurrencer Mathematica/Mapple/etc, mais de proposer une solution gratuite, open source et légère permettant de faire de l'algèbre linéaire de base (pas de matrices pour le moment, mais rien ne m'en empêche) et du calcul tensoriel formel (et accessoirement, numérique).
Comme vous pouvez le voir sur mon profil, je suis étudiant en physique (Master 2 actuellement), et il m'arrive bien souvent d'avoir à calculer des expressions tensorielles relativement pénibles, dont j'aimerais vérifier le résultat rapidement par ordinateur. C'est de là qu'est partie l'envie de programmer ce petit bout de programme (plus ma passion un peu malsaine de ré-inventage de roue).

Voici donc comme promis les binaires :
Note : L'édition des messages anciens de plus de 3 jours est désactivée sur Developpez. Il est donc presque certain que les versions ci-dessous ne soient pas les plus récentes. Merci de visiter cette page pour être sûr d'avoir la dernière version : [click].

• Windows XP (32bit) v001 : [7z] (100Ko), [zip] (155Ko) (01h00, 24/09/2011)
• Ubuntu 11.10 (32bit) v001 : pas tout de suite !

... et les sources :

• Sources (multiplateforme) : [7z] (51Ko), [zip] (87Ko) (01h00, 24/09/2011)

Le tout sous licence GNU GPL.

Pour compiler, vous devrez d'abord compiler la bibliothèque "Utils" qui se trouve dans le sous dossier du même nom. Elle n'a aucune dépendance ni configuration, et est donc très facile à compiler (les projets Code::Block sont fournis et prêts à l'emploi, d'ailleurs). La documentation Doxygen de cette bibliothèque est fournie ici : [7z] (262 Ko), [zip] (1329 Ko).

[Kalith]

Le programme peut maintenant faire se propager les références :

Code :

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

1
2
3
4
> r &= a*b
        Defining Reference : r = a*b
> 5 + (2*r - 3*2)
        Reference : (5)+(((2)*(a*b))-(6))

L'excès de parenthèse sera traité par la suite.

La prochaine étape pour le calcul formel sera donc de proposer des fonctions pour modifier le contenu d'une référence (développement, factorisation, etc).

Dans cette optique, la version 002 apporte également le support des fonctions, qui peuvent avoir un nombre arbitraire d'arguments. La recherche se fait d'abord par le nom de la fonction, puis si celle-ci existe, on évalue les arguments un par uns pour voir si un prototype correspond aux arguments fournis :

Code :

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

1
2
3
4
5
6
7
8
9
10
> rand(4,6)
        Scalar : 5.61748100222785
> rand(1,2,3)
        Error : No matching function call to :
                  rand(Scalar, Scalar, Scalar)
                Possible candidates :
                  rand()
                  rand(Scalar, Scalar)
> rund(4,6)
        Error : Undefined function 'rund'

Les appels de fonction peuvent avoir lieu n'importe où :

Code :

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

1
2
3
4
> round(rand())
        Scalar : 1
> <min(1,2), max(3,4), min(rand(),rand())>
        Vector : <1, 4, 0.00125125888851588>

L'ajout d'une nouvelle fonction est relativement simple. Comme dans la quasi totalité des langages interprétés, la fonction C++ doit avoir un prototype bien défini, qui permet de recevoir un nombre indéterminé d'argument, et d'en retourner également un nombre indéterminé (même si pour l'instant seules les fonctions à une seule valeur de retour sont supportées)).
Ainsi on aura par exemple :

Code c++ :

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

1
2
3
4
5
6
7
8
9
mState.RegisterFunction<Scalar,Scalar>("rand",
    [] (State& s, const s_ctnr<s_refptr<Symbol>>& args, s_ctnr<s_refptr<Symbol>>& res, s_str& e) -> s_bool
    {
        s_refptr<Scalar> sa = s_refptr<Scalar>::StaticCast(args[0]);
        s_refptr<Scalar> sb = s_refptr<Scalar>::StaticCast(args[1]);
        res = {s_refptr<Symbol>(new Scalar("", s_double::Random(sa->v, sb->v)))};
        return true;
    }
);

... où les deux arguments templates sont les types des paramètres de la fonction. Le premier argument est le nom de la fonction dans le programme, et le second : la fonction en elle même. J'utilise ici les lambdas du C++11 pour plus de concision.
On voit alors que celles-ci doivent avoir le prototype suivant :

Code :

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

s_bool (State& s, const s_ctnr<s_refptr<Symbol>>& args, s_ctnr<s_refptr<Symbol>>& res, s_str& e)

La valeur de retour indique si tout s'est bien passé, et la chaine de caractère 'e' (dernier argument) contient les éventuelles erreurs/warnings. Les deux autres arguments sont respectivement les arguments de la fonction et ses valeurs de retour.
L'emploi de 'static_cast' n'est pas problématique, car la classe State s'assure déjà en amont que les types sont corrects.

Binaires :
Note : L'édition des messages anciens de plus de 3 jours est désactivée sur Developpez. Il est donc presque certain que les versions ci-dessous ne soient pas les plus récentes. Merci de visiter cette page pour être sûr d'avoir la dernière version : [click].

• Windows XP (32bit) v002 : [7z] (109Ko), [zip] (165Ko) (12h00, 25/09/2011)
• Ubuntu 11.10 (32bit) v002 : [7z] (133Ko), [zip] (171Ko) (14h00, 25/09/2011)

... et sources :

• Sources (multiplateforme) : [7z] (57Ko), [zip] (95Ko) (15h30, 25/09/2011)

[Kalith]

Voici la version 003, qui contient quelques ajouts mineurs :

• nouvelles fonctions : exp, log, cos, acos, sin, asin, tan, atan, abs et pi (sans argument, qui renvoie la valeur du nombre pi),
• support d'une syntaxe allégée pour les fonctions sans arguments : on peut oublier les parenthèses (et ainsi se servir de la fonction pi() comme d'une variable standard, qu'on ne peut juste pas modifier)
• ajout des opérateurs puissance '^' et modulo '%' pour le type Scalar
• diverses petites corrections dont je ne me souviens plus

Petits exemples de code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
> exp(log(2))
        Scalar : 2
> cos(2*pi)
        Scalar : 1
> rand
        Scalar : 0.00125125888851588
> pi = 2
        Error : Cannot assign a value to the function 'pi'
> 2^8
        Scalar : 256
> 11911 % 777
        Scalar : 256

Binaires :
Note : L'édition des messages anciens de plus de 3 jours est désactivée sur Developpez. Il est donc presque certain que les versions ci-dessous ne soient pas les plus récentes. Merci de visiter cette page pour être sûr d'avoir la dernière version : [click].

• Windows XP (32bit) v003 : [7z] (114Ko), [zip] (175Ko) (19h00, 19/10/2011)
• Ubuntu 11.10 (32bit) v003 : [7z] (140Ko), [zip] (181Ko) (19h00, 19/10/2011)

... et sources :

• Sources (multiplateforme) : [7z] (58Ko), [zip] (95Ko) (19h00, 19/10/2011)

[Kalith]

Et voilà tranquillement la version 004 qui arrive :

• support des nombres complexes,
• ajout de la fonction 'machine_epsilon' qui donne la précision des nombres affichés,
• on peut maintenant donner plusieurs noms à une même fonction (pour les abréviations par exemple : 'cosh' et 'ch'),
• ajout des fonctions cosh (ch), sinh (sh), et tanh (th)
• correction d'un petit bug qui empêchait l'emploi de la notation abrégée pour les fonctions contenant un underscore '_'.

Et maintenant quelques exemples pour étayer le tout.
On a l'algèbre de base des nombres complexes :

Code :

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

1
2
3
4
5
6
7
8
9
10
> a = 1 + 2*i
        Scalar : a = 1 + 2 i
> b = a^2
        Scalar : b = -3 + 4 i
> abs(b)
        Scalar : 5
> a*conj(a)
        Scalar : 5
> <re(a), im(a)>
        Vector : <1, 2>

... avec les fonctions 'abs' (donne la norme), 'conj' (ou 'conjugate', donne le complexe conjugué), 're' (ou 'real', donne la partie réelle) et 'im' (ou 'imaginary', donne la partie imaginaire).

Les fonctions usuelles ont été étendues sur l'ensemble des complexes (quand c'est possible) :

Code :

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

1
2
3
4
5
6
7
8
> exp(i*pi)
        Scalar : -1
> cos(a)
        Scalar : 2.03272300701967 - 3.0518977991518 i
> round(_)
        Scalar : 2 - 3 i
> acos(a)
        Error : 'acos' is only defined for real numbers

A noter que j'aurais pu définir le logarithme complexe également, mais je n'en vois pas l'utilité (sachant surtout que sa généralisation sur C n'est pas triviale).

Binaires :
Note : L'édition des messages anciens de plus de 3 jours est désactivée sur Developpez. Il est donc presque certain que les versions ci-dessous ne soient pas les plus récentes. Merci de visiter cette page pour être sûr d'avoir la dernière version : [click].

• Windows XP (32bit) v004 : [7z] (120Ko), [zip] (186Ko) (23h00, 30/11/2011)
• Ubuntu 11.10 (32bit) v004 : à venir...

... et sources :

• Sources (multiplateforme) : [7z] (59Ko), [zip] (96Ko) (23h00, 30/11/2011)

[Kalith]

Après pas mal d'inactivité sur ce projet, j'ai décidé de le reprendre à zéro sur de meilleures bases. Le précédent code était relativement stable (je l'utilise depuis le début comme calculatrice sur tout mes PCs !), mais j'avais du mal à le faire évoluer, tant le parser était fouillis et la conception parfois bancale.

Je vous présente donc la toute neuve v005, avec au menu (en vrac) :

• le parsing se fait via boost::spirit,
• on peut choisir (au runtime grâce à l'option -high-precision=true, activé par défaut) de manipuler des nombres haute précision grâce à MPFR et son binding C++ mpfr::real (ceux-ci sont codés en virgule flottante sur 128 bits, et ce n'est modifiable qu'à la compilation),
• le nombre de chiffres affichés est configurable au runtime avec l'option -digits=10 (NB : ça n'affecte en rien la précision du calcul, juste l'affichage),
• on peut choisir de ne pas tolérer de variables ou fonctions non définies (au runtime aussi avec l'option -allow-undefined=false, toléré par défaut),
• on peut également désactiver le support des nombres complexes (au runtime également grâce à l'option -allow-complex=false, ils sont activés par défaut),
• si les nombres complexes sont activés, le type scalaire (i.e. un réel pur) reste actif, et si un calcul sur des nombres complexes donne une partie imaginaire nulle, le résultat est automatiquement considéré comme étant de type réel (on ne perd pas de mémoire à stocker une partie imaginaire nulle, et les opérateurs entres complexes et réels sont définis explicitement, de sorte que 2*(1+i) ne génère effectivement qu'une addition et une multiplication réelles, et non le double comme c'était le cas avant),
• le parsing des nombres complexes est amélioré : on peut écrire directement 1+2i au lieu de 1+2*i,
• la syntaxe pour les vecteurs est modifiée : (a, b, c) au lieu de <a, b, c>,
• les vecteurs ne sont plus contraints à être homogènes (ils peuvent contenir des données de différents types),
• le type vecteur est maintenant complètement indépendant du type scalaire : on peut multiplier/diviser, additionner/soustraire un vecteur avec n'importe quoi pourvu que cette même opération soit définie pour chaque objet stocké dans le vecteur,
• les références (qui contenaient une chaîne de caractère ré-évaluée à chaque fois) disparaissent au profit des expressions (qui contiennent un arbre d'opérateur, donc des données pré-parsées pour de meilleures performances et une manipulation plus aisée),
• les identifiers (noms de variable ou de fonction) suivent maintenant les mêmes règles qu'en C++ (à savoir : ne peuvent commencer par un chiffre, mais sinon n'importe quel caractère alphanumérique (ASCII seulement) ou un underscore '_'),
• il est possible de donner le même nom à une variable et à une fonction (en cas d’ambiguïté, l'interpréteur considère en priorité la variable),
• la fin d'une instruction est signalée par un simple espace (à condition que celui-ci ne soit pas situé entre deux opérateurs, i.e. : a=2 b=3 est valide et correspond à l'ancienne syntaxe a=2;b=3;, mais a=2 +b correspond à a=2+b; et non a=2;+b;).

Je pense avoir fait le tour !

La compilation est un peu plus ardue que précédemment, vu qu'il faut avoir boost d'installé (j'utilise la version 1.50), ainsi que MPFR (mpfr::real est header only et fourni avec mes sources) qui lui-même dépend de GMP. Autant boost::spirit est header only (rien à compiler donc), autant ce n'est pas le cas de GMP et MPFR qui sont des bibliothèques C. Ceci dit, elles compilent très facilement sous Windows avec MSYS et MinGW (./configure, make, un café, et c'est plié). Sous linux, je pense qu'il existe des paquets pré-compilés pour votre distribution (il faut au minimum MPFR 3).
La bibliothèque "Utils" a quant à elle disparu.

Ce qu'il reste à faire :

• Je dois encore nettoyer un peu le code (j'ai laissé le corps de plusieurs fonctions dans les headers pour m'éviter des allers-retours entre .cpp et .hpp, mais maintenant que l'API est à peu près stable je dois les ranger proprement),
• Lors de la sérialisation d'une expression, j'ai trop de parenthèses inutiles (j'avais ce soucis dans la version précédente, mais là ce sera bien plus simple à régler),
• Dans une expression, les calculs n'impliquant que des littéraux (i.e. des symboles dont le contenu est fixe : un réel, un complexe, ou un vecteur ne contenant que des littéraux, mais pas une variable ou une fonction, fussent-elles définies) peuvent être effectués une fois pour toute à l'affectation. J'ai déjà implémenté partiellement la chose dans les cas les plus simples : 1+2+a produit (1+2)+a que je simplifie facilement en (3+a), en revanche a+1+2 produit (a+1)+2 (la simplification n'est plus évidente : il faut jouer avec l'associativité et/ou la réorganisation des opérations),
• Je suis passé aux fonctions mathématiques de la bibliothèque standard pour les complexes (cf. #include <complex>). Cependant, il est écrit dans le standard que l'instanciation de std::complex<T> avec T différent de float, double ou long double est non défini... Sauf que j'utilise std::complex<mpfr::real<128>> dans mon code. J'ai pu vérifier que les implémentations fournies par gcc et VC++ étaient purement templates, donc a priori ça fonctionne mais j'aurai aimé avoir un peu plus de certitude... Et je n'ai pas envie de ré-écrire toutes ces fonctions mathématiques dans mon coin.

J'ai un peu laissé tombé le côté tenseur pour le moment. À voir si ça reviendra au devant de la scène plus tard En attendant...

Binaires :
Note : L'édition des messages anciens de plus de 3 jours est désactivée sur Developpez. Il est donc presque certain que les versions ci-dessous ne soient pas les plus récentes. Merci de visiter cette page pour être sûr d'avoir la dernière version : [click].

• Windows XP (32bit) v005 : [7z] (322Ko), [zip] (445Ko) (00h00, 02/10/2012)
• *buntu 12.04 (32bit) v005 : à venir...

... et sources :

• Sources (multiplateforme) : [7z] (37Ko), [zip] (49Ko) (00h00, 02/10/2012)

[CyaNnOrangehead]

Rhaaa les nombres complexes et tout ça, je ne suis pas allez assez loin dans mes études générales pour connaitre.

En revanche, les parseurs, tout ça, je suis un peu plus à l'aise.

Concernant ton problème d'optimisation (1+2) a vs (a+1) +2 tu devrais utiliser les AST (Abstract Syntax Tree)
Le principe est le suivant, tu pré-compile ton source dans un arbre.
Ensuite pour résoudre ton arbre, il te suffit de faire un parcour en profondeur.
Regarde du coté du design pattern Interpreter du GoF.
Sinon un très bon bouquin sur le parsing et la compilation :
http://pragprog.com/book/tpdsl/langu...ation-patterns

Autre petit point, j'ai cru comprendre en lisant tes exemples que ton programme ne respecte pas la précédence des opérateurs.
http://en.wikipedia.org/wiki/Order_of_operations (cf partie "programming languages")
Ce qui sous entend que 1 + 2 * 3 = 1 + (2 * 3) <> (1 + 2) * 3
La précédende insique que le signe * est traité "avant" le signe +, et du coup respecte l'ecriture arithmétique que nous connaissons.
Mais je peu me tromper, tu l'a peu-t-être fait.

Derniere chose, c'est dommage de ne pas avoir écrit ton parseur toi même. C'est un domaine vraiment très intéréssant. Mais ça demande ennormément de temps.

En tous cas bonne continuation.