Transposer le typage algébrique des données en C++

Bonjour à tous.

Depuis quelques temps, je cherche à voir s'il serait possible d'exprimer le fonctionnement du typage utilisé par un langage fonctionnel puissant comme Haskell dans un langage impératif relativement proche de la machine, comme C++.

Alors voici ce à quoi je suis arrivé jusqu'à présent, et là où je bloque.

Types sommes

Le principe d'un type somme, c'est qu'un type peut prendre un nombre fini de valeurs. Par exemple, en Haskell, on pourra l'exprimer ainsi.

1

data FeuTricolore = Rouge | Orange | Vert

Pas vraiment de difficulté pour transposer ça en C++, ça correspond directement à une énumération.

1

enum FeuTricolore { Rouge, Orange, Vert };

Types produits

Un type produit consiste à « emballer » un ou plusieurs champs dans le nouveau type, comme dans l'exemple qui suit.

1

data Point = Point Double Double

Si je vous dit que le Point après le = est appelé un constructeur, je pense que vous conviendrez que la transposition en C++ tombe sous le sens.

1
2
3
4
5
6
7
8
9

class Point {
    protected:
    double _x, _y;

    public:
    Point(double x, double y)
        : _x(x), _y(y)
        {   }
};

Le Haskell offre également ce que l'on appelle la « syntaxe d'enregistrement », qui permet de donner un nom aux champs du type produit, et crée automatiquement des fonctions portant le même nom pour y accéder.

1

data Point = Point { x :: Double, y :: Double }

En Haskell, ces fonctions accesseurs sont dans l'espace de nom général, mais tout le monde s'accorde à dire que c'est plus une faiblesse qu'autre chose, donc on va plutôt en faire des méthodes en C++.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Point {
    protected:
    double _x, _y;

    public:
    Point(double x, double y)
        : _x(x), _y(y)
        {   }

    double x() { return _x; }
    double y() { return _y; }
};

Là où ça devient un peu plus tordu, c'est que le constructeur n'a pas nécessairement besoin de porter le même nom que son type. Par exemple, ce code est tout à fait valable en Haskell.

1
2

data DroitePoints = DPts Point Point
-- Une droite définie par deux points par lesquels elle passe.

C'est là qu'on commence à faire du C++ dégueulasse…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class DroitePoints {
    protected:
    Point& _a, _b

    DroitePoints(const Point& a, const Point& b)
        : _a(a), _b(b)
        {   }
};

class DPts : public DroitePoints {
    public:
    DPts(const Point& a, const Point& b)
        : DroitePoints(a, b)
        {   }
};

Types algébriques

On rentre dans le vraiment rigolo : un type algébrique est une somme de types produits et/ou de valeurs spécifiques. Voici un exemple.

1
2

data Quidonc = Personne | Quelquun String
-- Soit on n'est personne, soit on a un nom

On pourrait envisager de faire de Personne une variable globale pré-déclarée, instance de Quelquun, avec nullptr en guise de contenu, mais ça ne marcherait pas si le contenu doit être un int ou un char, par exemple. Du coup, on peut tenter ça à la place.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Quidonc {
    protected:
    Quidonc();
};

class Personne : public Quidonc {
    public:
    Personne() {
        // Insérer code pour en faire un singleton.
    }
};

class Quelquun : public Quidonc {
    private:
    std::string _nom;

    public:
    Quelquun(const std::string& nom)
        : _nom(nom)
        {   }
};

Types paramétrés

Ça commence à devenir puissant. Un type paramétré, c'est un type produit dont on ne définit pas à l'avance le type du contenu. Par exemple…

1

data Boite a = Boite a

Ce a peut-être n'importe quel autre type. Pour transposer ça en C++, j'ai évidemment pensé aux templates.

1
2
3
4
5
6
7
8
9

template <typename T>
class Boite {
    protected:
    T _a;

    public:
    Boite(T a) : _a(a)
        {   }
};

Mélangé aux types algébriques, ça peut devenir plus ardu. Voici l'exemple classique d'un type algébrique et paramétré en Haskell.

1

data Maybe a = Nothing | Just a

La meilleure transposition à laquelle j'arrive en C++, c'est la suivante.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

template <typename T>
class Maybe {
    protected:
    Maybe() {   }
};

template <typename T>
class Nothing : public Maybe {
    public:
    Nothing() {   }
};

template <typename T>
class Just : public Maybe {
    protected:
    T _a;

    public:
    Just(T a) : _a(a)
        {   }
};

La limite de ce système, c'est qu'en Haskell, il n'y a qu'un seul Nothing, qui sera reconnu comme étant de n'importe quel type Maybe queqchose. Alors qu'avec le code que j'ai là, il faudra spécifier Nothing<int> ou Nothing<MyClass>.

Classes de types

Attention à la confusion de sens ! Une classe de types en Haskell, c'est ce que l'on appellerait une interface en POO : un type appartient à une classe donnée s'il implémente les fonctions que cette classe définit. C'est le seul moyen existant en Haskell de surcharger des fonctions existantes.

1
2
3
4
5
6

class Show a where
    show :: a -> String

instance Show Bool where
    show True  = "True"
    show False = "False"

Une des classes de base du langage : si un type l'implémente, il est possible d'afficher des variables de ce type dans la console. La transposition logique en C++ serait une classe virtuelle pure.

1
2
3
4

class Show {
    public:
    virtual std::string show() = 0;
};

Cependant, je vois un problème par rapport au comportement du Haskell. En effet, ce langage permet d'implémenter un comportement générique pour la fonction, ce qui fait qu'il n'est pas nécessaire que toutes les instances de la classe définissent elles-mêmes le comportement. On peut par exemple faire plutôt ce qui suit.

1

data Bool = True | False deriving (Show)

Vous allez me dire, il suffit que la class Show ne soit pas purement virtuelle. J'acquiesce. Cependant, le Haskell permet d'écrire des comportement génériques, qui sont interdépendants. Voyez par exemple la classe qui définit des relations d'égalité ou non.

1
2
3

class Eq a where
    (==) v1 v2 = if v1 /= v2 then False else True
    (/=) v1 v2 = if v1 == v2 then False else True

De cette manière, les types instances de cette classe peuvent ne définir qu'une seule des deux fonctions, et la seconde fonctionnera quand même, mais il faut quand même en définir au moins une.

Contraintes de classe

C'est là le deuxième intérêt majeur des classes de types en Haskell : à tout moment, quand on manipule un type paramétré, on peut mettre des contraintes sur les types qui peuvent être passés en paramètre. Voyez plutôt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Bits a where
    xor b1 b2 :: a -> a -> a
-- On va faire simple, en vrai, elle est beaucoup plus fournie

data MaybeBits a where
    NothingBits :: Bits a => MaybeBits a
    JustBits    :: Bits a => a -> MaybeBits a
-- Le type Char n'étant pas membre de la classe Bits, on
-- ne pourra pas créer de MaybeBits Char, alors qu'on pouvait
-- faire Maybe Char

Conclusion

Il y a aussi les types récursifs, mais ils ne posent pas de difficulté à implémenter en C++. À priori, j'ai fait le tour de ce que je cherche à obtenir. Évidemment, j'ai mis en lumière les endroits où je bloque, mais que cela ne vous empêche pas de faire des remarques sur le reste, si vous pensez que je m'y suis mal pris quelque part.

Et pour être sûr que vous n'avez pas oublié depuis le début de ce message…

Plusieurs remarques, je connais pas le haskell en dehors du fait que c'est un langage plutôt orienté fonctionnel :

Pour les enum, utilise des enum class, afin qu'elles soient fortement typées.

Pour ton problème de

1
2

data DroitePoints = DPts Point Point
-- Une droite définie par deux points par lesquels elle passe.

Utilise un using :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class DroitePoints {
    protected:
    Point const& _a, _b;

    public:
    DroitePoints(const Point& a, const Point& b)
        : _a(a), _b(b)
        {   }
};

class DPts : public DroitePoints {
    public:
    using DroitePoints::DroitePoints;
};

Déjà ça pourra t'aider. Je vais lire la suite, peut-être que j'aurai autre chose à rajouter.

Lu'!

Pour ce qui est du constructeur avec des noms différents, on peut se contenter de fonction utilitaires qui ne font que renvoyer un objet construit. En fait l'héritage ne me semble pas adapté ici.

Pour le nothing, je ne pense pas que tu puisses faire autrement, mais à l'usage ça doit pouvoir assez aisément se contourner.

Pour les class types, je n'ai pas compris ton soucis avec la définition non virtuelle pure, si tu as deux fonctions virtuelles, tu n'es pas obligé de surcharger les deux, tu ne peux très bien en surcharger qu'une.

Pour les contraintes de type, c'est du côté des traits, des concepts, et des static_assert qu'il faut regarder.

Bon après, je ne comprends pas vraiment quel est ton but mais c'est assez rigolo. D'un autre côté il est évident que tu ne pourras pas reproduire tous les comportements possibles et imaginables de Haskell en C++ avec une forme semblable : plus on s'éloigne de la partie fonctionnelle supportée par C++, plus c'est complexe, mais d'un autre côté il y a des trucs qu'on ne voudra écrire en C++ pour rien au monde.

Ton post m'a fait penser aux articles de Bartosz Milewski qui écrit beaucoup sur le fonctionnel, la théorie des catégories et C++. il a un article sur une implémentation de monade en C++ par exemple.

Bonsoir,

Pour les constructeurs ayant un nom différent du type : Fonction de création externe (tu mets le constructeur en private et un fonction avec le nom que tu veux en friend).

Pour les types algébriques : boost::variant (où une autre implémentation de la même idée). Ce qui corrige ton problème avec Nothing.

Pour les classes de types : Les concepts de la prochaine norme. Pour les instanciation par défaut, je jouerais surement avec du tag dispatching.

De manière générale, j'éviterais l'héritage directe comme tu le fais ici, ça inverse la dépendance entre tes types. En Haskell tu définis A en fonction de B et C quand tu écris data A = B | C, si pour faire un équivalent C++ tu utilises l'héritage tu te retrouves à écrire B et C en fonction de A. C'est la raison de ton problème avec Nothing.

J'y avais pensé, et puis je les avais écartées, car les éléments d'un enum class appartiennent à un espace de nom, alors qu'elles appartiennent à l'espace de nom général en Haskell. Du coup, je suppose que je peux obtenir le même comportement en faisant ça ?

1
2

enum class FeuTricolore { Rouge, Orange, Vert };
using namespace FeuTricolore;

Pour le coup, je préfère la solution proposée par Ksass`Peuk et Freedom.

Ça permet de mieux séparer la manière d'implémenter un type, et la manière d'implémenter un simple constructeur. Et du coup, ça donne des trucs moins moches pour implémenter des types algébriques pas trop compliqués (où il n'y a pas de mélanges entre constructeurs paramétrés et non paramétrés).

Mon problème, c'est que rien n'interdit de n'en surcharger aucune des deux, ce qui aurait un effet désastreux. Par exemple, un truc comme ça.

 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 Eq {
    public:

    virtual bool egal(const Eq& param)   {
        return ! this->non_egal(param);
    }

    virtual bool non_egal(const Eq& param)   {
        return ! this->egal(param);
    }
};

class MaClasse : public Eq {
    private:
    int _blablabla;

    public:
    MaClasse(int a) : _blablabla(a) {   }
    // Ni egal, ni non_egal ne sont surchargées.
};

int main()  {
    MaClasse toto(1);
    MaClasse tata(2);

    return toto.egal(tata);
};

Ça compile parfaitement, mais ça balance un Segfault quand on essaye de l'exécuter.

En effet, les concepts correspondent tout à fait à ce que je recherche. Bon, ce n'est pas étonnant : le Bartosz Milewski mentionné par Grimur à écrit un article sur le sujet, où il dit « The C++ concept proposal is based on the Haskell's notion of type classes. ». Du coup, je doute qu'on puisse trouver mieux.

Seul souci, le gcc de ma distrib a deux ans d'âge, et les concepts n'ont été intégrés dans gcc qu'en août de cette année… Je vais devoir patienter un peu… Mais en attendant, je pense que des traits + des static_assert doivent permettre de parvenir au même résultat. Faudra que j'essaye un peu.

Considère ça comme un jeu. Berdes avait réussi à faire de la programmation impérative en Haskell ; là, c'est le contraire : est-il possible d'imiter le Haskell en programmation impérative ?

J'ai pas mal retourné la question, et j'en suis arrivé à la conclusion que le nœud du problème, c'est le système de types, qui lui-même commande le filtrage par motifs : si on arrive à mettre ça en place, le reste du langage est assez bateau (c'est beaucoup de sucre syntaxique sur quelques fonctionnalités très basiques).

Cela dit, on arrive quand même à bien s'en rapprocher, c'en est presque surprenant ! Mais on dirait qu'il y a parmi les gourous du C++ plusieurs personnes qui aiment beaucoup la prog fonctionnelle, ça doit expliquer.

Pour les types algébriques : boost::variant (où une autre implémentation de la même idée). Ce qui corrige ton problème avec Nothing.

J'ai regardé hier soir, et il semblerait bien, en effet, que ça résolve le problème (même si visiblement, c'est assez compliqué de créer des types récursifs avec cette bête-là, et que Haskell adooore les types récursifs).

Après, ça oblige à passer par des classes « visiteur » et la fonction boost::apply_visitor pour faire la moindre application de fonction (ce qui fait méchamment penser à un binding de monade, cela dit…) sur ces types-là, donc faudrait voir si à l'usage, ce n'est pas plus simple d'avoir un Nothing paramétré.

Bon, me reste plus qu'à essayer de comprendre comment ils ont créé un monstre pareil…

J'avoue ne pas comprendre en quoi cela permet de résoudre le problème que j'évoque. Tu pourrais m'expliquer plus précisément ce que tu as en tête ?

Oui, syntaxiquement, tu seras obligé de préfixer, mais tu interdis le cast direct vers int, donc faut pas s'en priver .

Pour les class-types j'avais pas percuté le fonctionnement du code Haskell. Du coup, non tu n'auras effectivement pas d'équivalent.

Oui, d'autant que même si des travaux sont proposés pour le multiple-dispatch en C++, la résolution du simple dispatch en C++ par l'usage de pattern-matching serait malgré tout une erreur.

Sur le plan fonctionnel, la majorité des ajouts fait à C++ sont inspirés d'Haskell.

Il y a en effet pas de mal de personnes qui bossent sur le fonctionnel en C++. Mais je ne suis pas sur de ton approche, on dirait que tu essaies d'imiter une syntaxe, pas forcement ce qui fait la puissance du fonctionnel.

C'est un peu comme les devs Java, qui transposent leurs classes en C++… et s'étonnent que cela merde.

Par exemple, ton enum, rien n'interdit d'écrire :

1

FeuTricolore x = static_cast<FeuTricolore>(5);

Toutes tes définitions de types en Haskell, cela me fait penser à de la définition de DSL. Et très clairement, ton équivalent C++ ne permettra pas de créer un DSL (ou alors très pauvre).

Je te conseille de voir les videos sur le fonctionnel de CppCon (https://www.youtube.com/user/CppCon/videos) par exemple celle de Niebler, Falcou, Shulman. Et pour faire ce que tu veux faire, je pense qu'il ne faut pas regarder simplement les syntaxes, mais également ce qu'elles apportent, les cas d'utilisation, etc.

Bonjour,

Même si ce n'est certainement pas directement en rapport avec la demande du PO, je suis étonné de ne pas avoir vu de référence à Functional C++, une série d'articles techniques sur l'émulation de fonctionnalités issues du paradigme fonctionnel.

En vrac, on y retrouve des function traits, function composition (de n'importe quel ordre), type classes, continuation passing style, foldable, filtrable, mappable, zipper, etc.

Je vous laisse vous faire une idée : Functional C++.

Remarque à 2 balles. Évitez les noms de champs ou de variables commençant pas _, je crois que c'est réservé à l'usage des implémenteurs des librairies standards.

Pour les types algébriques, je trouve que l'utilisation de pointeurs nus ferait l'affaire. Et nullptr peut être associé à toute classe de pointeurs nus.

Et pour avoir une implémentation par défaut d'une interface, pourquoi pas une classe de base implémentant cette implémentation par défaut ?

En C++, il est possible de vérifier qu'une fonction membre existe, le choix de la fonction de la fonction d'implémentation peut s'implémenter avec tel mécanisme. Par contre, il faut propager le type réel de la classe dans Eq, donc ajouter une classe de base pour définir l'interface virtuelle.

Tu as d'autres exemples pratiques que les opérateurs ==/!= ?

Merci à tous pour vos réponses. J'ai continué à faire joujou pour expérimenter (et j'ai passé des heures à m'arracher les cheveux sur les messages d'erreurs cryptiques de g++), et finalement, ce qui semble marcher le mieux, c'est de se rapprocher encore plus de la syntaxe du Haskell. Comme quoi…