Discussion :

[coyotte507]

Bonjour

Je voudrais voir si une expression est d'un certain type, par exemple du type Feuille

Bien sûr, je pourrais faire comme ça

Code :

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

1
2
3
match a with
 Feuille(b) -> ...
 | _ -> ....

Mais est-ce qu'il existerait quelque chose du type:

Code :

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

1
2
if (typeof(a) == Feuille) then ...
else ...

en caml Light standard?

Merci!

[Cacophrene]

Salut !

J'ai bien peur qu'une fonction telle que typeof n'existe pas en caml... car la plupart des informations de typage sont perdues après la compilation (c'est la même raison qui fait que les fonctions print polymorphes que l'on peut écrire en caml ne sont jamais qu'un pis-aller). En clair, la seule chose que l'on puisse faire, c'est aller voir la représentation interne du type avec le module Obj (je ne sais pas s'il y a un équivalent en caml-light). Mais ce ne sera jamais parfait, puisque on ne pourra pas distinguer 0, false, (), [] et None qui ont tous la même représentation interne (ce qui se reflète d'ailleurs dans l'interfaçage C/OCaml : Val_unit, Val_false, Val_emptylist sont des macros qui ont pour synonyme Val_int(0) !)

Quelques pistes : les valeurs possèdent des étiquettes (tags). On obtient l'étiquette d'une valeur OCaml avec

Code OCaml :

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

let get_tag x = Obj.tag (Obj.repr x)

Par exemple get_tag "exemple" renvoie 252 qui est égal à Obj.string_tag. De la même façon, get_tag 3.1416 renvoie 253 qui correspoind à Obj.double_tag. Mais comme je le disais plus haut get_tag () = get_tag None = get_tag [] = get_tag 0 = 1000 = Obj.int_tag.

En clair si tu veux vraiment avoir une idée précise du type de données,tu peux encapsuler tous les types qui t'intéressent avec un type somme :

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
type t =
  | Unit
  | Int of int
  | Flo of float
  | Str of string
  | Ref of t ref
  | Bln of bool
  | Opt of t option
  | Lst of t list
  | Vec of t array
  | Htb of (t, t) Hashtbl.t

Le filtrage te permettra alors de simuler efficacement la fonction typeof. Ce n'est qu'une manière de faire parmi d'autres. On peut aussi attacher à chaque valeur une chaîne qui indique son type, etc...

Cordialement,
Cacophrène

[Garulfo]

Cette question est régulièrement posée. La réponse est donc dans ce forum de nombreuses fois.

Bonjour
Je voudrais voir si une expression est d'un certain type, par exemple du type Feuille[...]

Salut !
[...]
Le filtrage te permettra alors de simuler efficacement la fonction typeof. Ce n'est qu'une manière de faire parmi d'autres. On peut aussi attacher à chaque valeur une chaîne qui indique son type, etc...

On ne simule pas en fait. Coyotte, et peut-être Cacophrene, confond constructeur et type. Le pattern-matching s'applique sur des constructeurs et non sur des types. Dans ton exemple, Feuille n'est pas un type mais un constructeur (probablement d'un arbre). Si celui-ci ne demande pas de paramètre tu peux faire

Code :

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

if (element = ConstructeurSansParametre) then … else …

sinon tu ne pourras pas. Si tu veux à tout prix avoir un prédicat, construit le toi

Code :

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

1
2
let est_une_feuille x = match x with Feuille _ -> true | _ -> false ;;
if (est_une_feuille element) then … else …

Oublie Obj, qui montrera, si tu l'utilises pour ça, que tu n'as rien compris au paradigme d'ocaml.

[Cacophrene]

Salut !

On ne simule pas en fait. Coyotte, et peut-être Cacophrene, confond constructeur et type. Le pattern-matching s'applique sur des constructeurs et non sur des types

Aucune confusion de ma part. Je souhaitais montrer que les informations de type (j'entends bien int, float, string etc.) ne sont plus accessibles qu'à travers la représentation interne des données (et le module Obj ou l'interfaçage C/OCaml), ce qui pose problème dès lors que des types différents ont une même représentation (j'évoquais à ce propos le cas d'unit, bool, int et la liste vide).

Une solution de contournement (workaround) consisterait à utiliser un type t dont les constructeurs (Int, Flo, Str, etc...) encapsulent les types OCaml et permettent, grâce au pattern matching, de conserver l'information de type des valeurs manipulées. C'est en ce sens que je parlais de simuler le comportement de typeof, par exemple comme ceci :

Code :

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

1
2
3
4
5
6
7
 
let rec typeof = function
  | Int _ -> "int"
  | Flo _ -> "float"
  | Str _ -> "string"
  | Cpl (t1, t2) -> Printf.sprintf "%s * %s" (typeof t1) (typeof t2)
  | ...

Mais, en effet, je m'aperçois maintenant que coyotte507 parlait de "type Feuille", ce qui n'a aucun sens puisque la casse de Feuille indique qu'il s'agit d'un constructeur (et vu le nom choisi, je pense comme toi qu'il s'agit probablement d'un arbre). Si c'est bien ça, bah il n'y a vraiment aucun problème pour manipuler tout ça...

Oublie Obj, qui montrera, si tu l'utilises pour ça, que tu n'as rien compris au paradigme d'ocaml.

Et dans ces conditions, évidemment, je suis bien d'accord avec ça ! Obj ne sert que dans des cas bien précis, lorsqu'on ne peut pas faire autrement (je pense notamment à la tentation d'utiliser Obj.magic à tort et à travers) et sûrement pas dans les situations courantes, surtout s'il est juste question de faire du filtrage...

Cordialement,
Cacophrène

[Alp]

Bonjour

Je voudrais voir si une expression est d'un certain type, par exemple du type Feuille

Bien sûr, je pourrais faire comme ça

Code :

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

1
2
3
match a with
 Feuille(b) -> ...
 | _ -> ....

Mais est-ce qu'il existerait quelque chose du type:

Code :

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

1
2
if (typeof(a) == Feuille) then ...
else ...

en caml Light standard?

Merci!

Personnellement, j'aimerais savoir pourquoi tu as besoin de faire une telle chose ?
C'est typiquement une mauvaise utilisation du polymorphisme d'héritage dans des langages comme Java ou C++ qui entraine ce genre de besoins... Mais alors en Caml je me demande pourquoi tu veux faire ça

[LLB]

C'est typiquement une mauvaise utilisation du polymorphisme d'héritage dans des langages comme Java ou C++ qui entraine ce genre de besoins...

Note que la hiérarchie de classes est en gros l'équivalent de nos types somme (les types somme de F# sont d'ailleurs compilés comme ça). Bien sûr, c'est beaucoup plus moche, mais les développeurs C++/Java/C# n'ont pas toujours d'autre alternative.

P.S. : les parenthèses autour de la condition du if sont inutiles. En général, il vaut mieux utiliser = plutôt que ==.

[Alp]

Note que la hiérarchie de classes est en gros l'équivalent de nos types somme (les types somme de F# sont d'ailleurs compilés comme ça). Bien sûr, c'est beaucoup plus moche, mais les développeurs C++/Java/C# n'ont pas toujours d'autre alternative.

En C++ on a des alternatives... En Java et C# c'est une autre histoire
Enfin j'invite quiconque à consulter de bonnes ressources sur le C++... Même le forum C++ de Developpez regorge de conseils de ce genre

Bref, tout ça pour dire que le ``pourquoi'' m'intrigue

[coyotte507]

C'était juste parce que faire un match avec deux éléments, je trouvais ça pas terrible, surtout que je n'avais pas besoin de la valeur de la variable, juste savoir si c'était une feuille ou pas de l'arbre.

Enfin, c'est pas si terrible que ça

Merci

[Alp]

Pourtant le match convient très bien.
Il te permet justement d'effectuer la projection d'une valeur d'un type somme sur l'un de ses "sous-types", quoique tu en fasse.

[LLB]

Enfin j'invite quiconque à consulter de bonnes ressources sur le C++... Même le forum C++ de Developpez regorge de conseils de ce genre

Tu as un lien précis (ou au moins un mot-clé à rechercher) ?
Pour moi, quand on a besoin de faire quelque chose de complexe (par exemple, un AST), il est conseillé de passer par de l'héritage, pour avoir un résultat extensible et relativement sûr.

coyotte507, regarde la réponse de Garulfo. Tu peux trouver que le style est un peu lourd, et je suis tout à fait d'accord avec toi. Il me semble que Bluestorm avait parlé d'une extension Camlp4 pour tester ce genre de prédicat plus facilement.

[coyotte507]

Tu as un lien précis (ou au moins un mot-clé à rechercher) ?

Je crois que c'est en utilisant des templates: on peut dire à une fonction de faire telle ou telle chose si elle reçoit tel ou tel type, ou alors autre chose si le type est différent.

Dans la méta-programmation ce concept est beaucoup utilisé.

Voilà deux mot-clefs

Concernant ma question, vu le contexte dans lequel je fais du caml, je vais me cantonner au match (ou à la fonction proposée par garulfo si je suis amené à répéter ce genre de tests)

[Garulfo]

C'était juste parce que faire un match avec deux éléments, je trouvais ça pas terrible, surtout que je n'avais pas besoin de la valeur de la variable, juste savoir si c'était une feuille ou pas de l'arbre.

Enfin, c'est pas si terrible que ça

Merci

C'est dans l'utilité d'une indirection que de cacher une syntaxe inutilement lourde aussi. Donc défini un petit prédicat et hop, le tour est joué. Par contre, c'est vrai qu'à chaque constructeur, il te faudra un prédicat.

[LLB]

Concernant ma question, vu le contexte dans lequel je fais du caml, je vais me cantonner au match (ou à la fonction proposée par garulfo si je suis amené à répéter ce genre de tests)

Oui, c'est la solution habituelle.

Je crois que c'est en utilisant des templates: on peut dire à une fonction de faire telle ou telle chose si elle reçoit tel ou tel type, ou alors autre chose si le type est différent.

Dans la méta-programmation ce concept est beaucoup utilisé.

Merci, mais je connaissais déjà ces mots-clés (j'ai beaucoup joué avec la métaprogrammation il y a quelques années). Le type somme correspond à un type qui peut prendre plusieurs valeurs. Ca fait penser à l'union du C avec un tag, mais de plus haut-niveau (c'est fortement typé et ça se manipule plus simplement).

Pour les cas de base, on peut facilement se passer de l'héritage. Mais dans le cas général, ça me semble l'approche la plus propre.

Par exemple, comment représenter le type suivant en C++ ?

Code :

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

1
2
3
4
type 'a ast =
  | Value of 'a
  | IfThenElse of 'a ast * 'a ast * 'a ast
  | Call of string * 'a ast list

Une classe avec un tag et les 3 champs me semble assez moche. On veut aussi s'assurer qu'il n'y aura pas de problème à l'exécution.

[gorgonite]

Par exemple, comment représenter le type suivant en C++ ?

Code :

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

1
2
3
4
type 'a ast =
  | Value of 'a
  | IfThenElse of 'a ast * 'a ast * 'a ast
  | Call of string * 'a ast list

Une classe avec un tag et les 3 champs me semble assez moche. On veut aussi s'assurer qu'il n'y aura pas de problème à l'exécution.

ayant déjà du faire ce genre de choses en C++, je dirais qu'il va quand même falloir un peu d'héritage, mais que ça aura l'avantage de rendre le tout plus facile à étendre par la suite (si l'on a pris la peine de bien faire sa conception)

Code c++ :

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
20
21
22
23
24
25
26
27
 
class VirtualInstruction {
  protected:
    VirtualInstruction* _previous;
    VirtualInstruction* _next;
};
 
class VirtualExpression {
};
 
class BooleanExpression : public VirtualExpression {
};
 
class GotoInstruction : public VirtualInstruction {
};
 
class LabelInstruction : public VirtualInstruction {
};
 
class IfInstruction : public VirtualInstruction {
   protected:
      BooleanExpression expr;
      LabelInstruction* _then;
      LabelInstruction* _else;
};
 
...

nb : là, j'ai fait à la "Java"... mais avec quelques templates, on peut avoir plus subtil que de simples pointeurs C (ou références Java/C#). mais je ne pense pas qu'on puisse réellement faire propre et beaucoup plus simple

après si l'on était juste avec le code avant AST (token du lexer/parser) ou après AST (bytecode & cie), on pourrait se contenter d'un simple enum

[Alp]

@LLB : boost::variant devrait faire l'affaire.
Par contre, je concède à 100% que c'est bien plus pratique en OCaml, c'est pas pour rien que c'est mon nouveau langage privilégié

[gorgonite]

@LLB : boost::variant devrait faire l'affaire.

mouais... tu peux nous faire une "démo" ?
perso, j'ai un doute sur la propreté d'utilisation comparé à un AST "à la main" bien conçu


dans un compilo, je vois bien boost::tokenizer, mais pas beaucoup plus

[HanLee]

Voilà un exemple.

Avantages de cette solution :

• On a là un vrai système de types sommes. Les fonctions sur ces types boost::variant sont implémentés sous forme de visiteurs. Totalement typesafe : si l'on oublie de traiter un sous-type, il y a une erreur dès la compilation.
• gestion automatique de la mémoire (idiome RAII)
• pas de risque de référence cyclique non voulue (mais c'est une liberté en moins aussi)

Les moins :

• aussi verbeux qu'une hiérarchie de classes
• empreinte mémoire non optimale
• Le pattern matching est limité : on ne peut que discriminer selon les types de base, en surchargeant l'opérateur () sur les bons types (exemple eval_IntAST).
  On ne peut pas faire l'équivalent OCaml de "IfThenElse(Value(0), _, e) ->".
• Si on avait les "template typedef" de C++0x, ce serait un peu moins verbeux.

Code c++ :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <string>
#include <list>
#include <cmath>
#include <boost/variant.hpp>
 
using boost::variant;
using boost::recursive_wrapper;
using boost::apply_visitor;
 
template <typename T> struct IfThenElse;
template <typename T> struct Call;
 
template <typename T>
struct AST
{
    typedef variant
    <
        T,
        recursive_wrapper< IfThenElse<T> >,
        recursive_wrapper< Call<T> >
    > type;
 
    type contents;
 
    AST() { }
    AST(typename AST<T>::type const& rhs) : contents(rhs) { }
};
 
 
template <typename T>
struct IfThenElse
{
    AST<T> condition_expr;
    AST<T> then_expr;
    AST<T> else_expr;
 
    IfThenElse(typename AST<T>::type const& c,
               typename AST<T>::type const& t,
               typename AST<T>::type const& e) :
        condition_expr(c),
        then_expr(t),
        else_expr(e)
    { }
};
 
 
template <typename T>
struct Call
{
    std::string         function_name;
    std::list< AST<T> > parameters;
 
    Call(std::string const& f, std::list< AST<T> > const& p) :
        function_name(f), parameters(p)
    { }
};
 
 
class eval_IntAST : public boost::static_visitor<int>
{
public:
    int operator()(int x) const
    {
        return x;
    }
 
    int operator()(IfThenElse<int> const& expr) const
    {
        if ( apply_visitor(*this, expr.condition_expr.contents) != 0 )
            return apply_visitor(*this, expr.then_expr.contents);
        else
            return apply_visitor(*this, expr.else_expr.contents);
    }
 
    int operator()(Call<int> const& expr) const
    {
        if (expr.function_name == "square")
        {
            int res = apply_visitor(*this, expr.parameters.front().contents);
            return res * res;
        }
        else
            throw std::runtime_error("Unknown function");
    }
};
 
 
int main()
{
    // AST d'entiers
    typedef AST<int> IntAST;
 
    std::list<IntAST> paramètres;
    paramètres.push_back( IntAST(30) );
 
    IntAST test( IfThenElse<int>(1,
                                 Call<int>("square", paramètres),
                                 0) );
 
    std::cout << apply_visitor(eval_IntAST(), test.contents) << std::endl;
 
    return 0;
}

Sortie :

Code :

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

900

[gorgonite]

et en plus ça marche...


toujours est-il que je ne vois pas bien l'intérêt dans le cas d'un AST d'utiliser cela ?
c'est tout aussi lourd qu'une hiérarchie de classes, et j'ai quand même l'impression que c'est la même chose avec un peu de sucre syntaxique (enfin un peu plus puisque ceux sont des templates)

[HanLee]

Ben, pas de new-delete à faire c'est bien non?

Avec une hiérarchie de classes, pour être rigoureux et avoir une bonne souplesse d'utilisation, il faudrait des pointeurs intelligents, et c'est lourd (et comme j'ai dit, tu peux avoir des références cycliques si tu fais pas gaffe).

Problème avec une hiérarchie de classes, tu fais comment pour rajouter des nouvelles fonctions?
Une hiérarchie de classe est ouvert pour l'espace des types, mais fermé pour les algorithmes.

L'interface d'une classe mère, c'est quelque chose de fermé. La solution c'est de faire un visiteur, et du coup on bloque l'espace des types.

Et ça revient à faire Boost.Variant en moins bien.

[Alp]

C'est la solution la plus pratique que je connaisse. Merci HanLee de m'avoir évité de taper un exemple

Mais je le répète, ça ne sera jamais aussi élégant que l'équivalent OCaml, ni aussi court.

Par contre, il s'agissait bien de vous montrer que le C++ est un chouilla sous-estimé et ramené au niveau de Java/C# pour beaucoup de choses, à tort