Guillaum a écrit 472 commentaires

Sauf que les parachutistes ont une vérification annuelle (ou bi-annuelle dans d'autres pays) de leur parachute de secours ;) Et c'est justement le point de la discussion, il faut tester ses sauvegardes.

Oups, désolé, je ne sais plus comment on a réussi à dériver d'une discussion qui par du compilateur Haskell pour finir par parler des langages objets. Toute mes excuses pour des propos qui auraient pu être interprétés comme blasphématoires dans ce fil de discussion de conviction plutôt fonctionnelle.

Aucune conviction ici, je ne sais toujours pas définir le fonctionnelle du "objet". Quand je présente Haskell, je ne parle pas d'un langage fonctionnel, parce que je ne sais toujours pas ce que cela veut dire. Même chose quand je parle de python.

Souvent les débats "fonctionel" versus "object" tournent autour de conneries sans nom à mon humble avis. J'entend souvent que python n'est pas objet parce que il y a le self explicite en premier argument ? C n'est pas objet parce qu'il n'y a pas de classes ? Haskell n'est pas objet parce qu'il y a des classes mais qu'elle n'ont rien à voir avec les classes en C++. Pour moi l'objet c'est avoir des "trucs" qui représentent des "bidules" métiers et pouvoir faire passer des "messages" entres les "trucs". En C++ on parlera de "méthodes" ou "fonctions membres" pour faire passer les messages, en Haskell on parlera de "fonctions". L'objet pousse aussi l'encapsulation, qui sera effectuée en C++ par le bias de public / private et en Haskell par le biais d'un module qui export une liste définie de fonction. Au final on exprime la même chose. Comparons le code haskell suivant permettant de définir un type Poulet :

module Poulet
     (Poulet, -- Export le type `Poulet`, mais pas son constructeur, on ne peut pas crée de poulet avec un age arbitraire, on ne peut pas non plus dépacker un poulet en dehors de ce module pour changer son nom ou son age
      cotcotcot, newPoulet, pouletAnniversaire)
where

data Poulet = Poulet Int String

-- | La fonction cot cot cot
-- fait faire cot au poulet autant de fois que son age.
-- Un poulet de 3 ans fera "cotcotcot"
cotcotcot :: Poulet -> String
cotcotcot (Poulet age _) = concat (replicate age "cot")

-- | Un poulet tout neuf, d'age 0, avec un nom de poulet
newPoulet :: String -> Poulet
newPoulet s = Poulet 0 s

pouletAnniversaire :: Poulet -> Poulet
pouletAnniversaire (Poulet age name) = Poulet (age + 1) name

Voici la version C++ :

class Poulet
{
private:
   int age;
   std::string name;

public:
   explicit Poulet(std::string newName):age(0), name(newName)
   {}

   std::string cotcotcot() const
   {
         std::string ret;

         for(int i = 0; i < age; ++i)
         {
             ret += "cot";
         }
         return ret;
   }

   void anniversaire()
   {
       age++;
   }
};

La seule différence ici c'est que pour la version Haskell j'ai fais le choix de faire un type non mutable et de renvoyer un nouveau Poulet lors de son anniversaire. La version C++ modifie le poulet en place. Note que on pourrait bien faire l'inverse cela ne poserait aucun problème à aucun des deux langages, c'est juste que Haskell est plus partisan de données non mutable alors que C++ est plus partisan des donnée mutable, mais c'est juste une orientation que donne le langage, rien d'obligatoire.

Bref, au final les différences entre les différents langages sont autres, par exemple, la présence ou non de pattern matching, que tu pourras trouver dans un langage objet ou dans un langage fonctionnel. Est-ce que le langage est plutôt orienté non mutable, ou mutable…

Le reste c'est juste des noms à la con mis sur des concepts mal défini. Je me rappel un étudiant qui dans un examen devait résoudre un problème en utilisant la programmation dynamique. Il m'a écrit :

Je ne sais pas ce qu'et la programmation dynamique parce que je ne suis pas venu en cours, mais je peux quand même résoudre votre problème avec une bonne complexité en utilisant un cache de résultat intermedaire, bla bla bla.

Sans le savoir, il avait fait de la programmation dynamique.

Tu ne sais pas ce qu'est un Functor, pas grave, tu l'a déjà utilisé sans le savoir. Pareil pour les Monad, Applicatives. Les opérateurs paresseux aussi. Le design pattern "visitor", c'est grosso modo du pattern matching.

Désolé pour ce petit coup de gueule ;)

Merci, je ne connaissais pas ce module. Après la complexité est cachée dans le module, on pourrait tout aussi bien mettre mon implémentation de Range dans un module et la complexité ne serait plus aussi visible.

Ton approche avec un Maybe est clairement préférable à la mienne qui est basée sur des exceptions. Par contre, lire la ligne de putStrLn m'a demandé un effort du fait des priorités des opérateurs. Pour ceux qui ont du mal, cela se lit putStrLn (show ((launchMissile'' . F) <$> [10, 0, 7, negate 11, 17])). Généralement quand j'ai plus d'un opérateur infix non trivial dans la même ligne, je met des parenthèses explicites.

J'ai pas trop de souci avec la verbosité d'ADA (Que je découvre en lisant ton code). Je suis plus embêté par le concept de devoir fournir un cas par défaut pour un type comme tu le laisse supposer en commentaire. Cela veut dire qu'ADA, si tu n'initialise pas explicitement ta valeur, va prendre le choix par défaut ? Je n'aime pas ;)

On a droit également à une exception si on tente d'accéder ou de modifier un champ alors que le discriminant n'est pas le bon :

MaPolitique := (Politique => CasParticulier);
MaPolitique.NombreThread := 5;—CONSTRAINT_ERROR : discriminant check failed

Il n'y a pas de garantie statique sur ce genre de chose ? Ça c'est dommage.

Les range, c'est sympa que le langage propose cela de façon native, mais au final cela s'émule assez bien dans n'importe quel autre langage avec un peu de typage dépendant.

Par exemple, en Haskell :

{-# LANGUAGE KindSignatures, DataKinds, TypeApplications, ScopedTypeVariables #-}
import GHC.TypeLits
import Control.Exception (assert)
import Data.Proxy

newtype Range (a :: Nat) (b :: Nat) = RangeVal Integer deriving (Show)

newValInRange :: forall a b. (KnownNat a, KnownNat b) => Integer -> Range a b
newValInRange i = assert (i >= bMin && i <= bMax) (RangeVal i)
  where bMin = natVal @a Proxy
        bMax = natVal @b Proxy

C'est assez verbeux et incompréhensible pour l’œil non habitué, donc en gros, si on passe les import et LANGUAGE nécessaires. On a une définition de type Range, paramétrée par deux types "phantoms", bMin et bMax qui représentent les borne du range, mais ces valeurs sont stockées au niveau du type. Cependant la valeur stockée ne peut pas être contrainte, donc on stock un Integer dedans.

Tous le problème se résume maintenant à empêcher la création d'un Range sans passer par une procédure de vérification. Pour cela on n'exportera pas le constructeur RangeVal, à la place, on va exporter la fonction newValInRange. Son type est assez barbare, newValInRange :: forall a b. (KnownNat a, KnownNat b) => Integer -> Range a b, mais en gros elle prend un Integer et renvoie un Range a b. Le truc c'est que on va se servir du a et b attendus (au niveau du type) pour déduire la vérification au niveau valeur.

La ligne assert (i >= bMin && i <= bMax) (RangeVal i) se contente de renvoyer notre Integer bien encapsulé dans un RangeVal, mais après avoir testé qu'il est bien dans les bornes, en se servant de bMin = natVal @a Proxy pour transformer le type a, Integer au niveau du type, vers la valeur bMin, integer au niveau valeur.

Après cela s'utilise comme cela. Imaginons la fonction suivante qui accepte un Range 0 10 :

launchMissile :: Range 0 10 -> IO ()
launchMissile r = case getValInRange r of
  0 -> putStrLn "Paix et harmonie"
  n -> putStrLn (unwords (replicate (fromInteger n) "EXTERMINATE!"))

qui se sert entre autre de la fonction utilitaire getValInRange (RangeVal i) = i qui permet d'extraire l'Integer du range.

Alors, nous obtenons :

*Main GHC.TypeLits> launchMissile (newValInRange 0)
Paix et harmonie

*Main GHC.TypeLits> launchMissile (newValInRange 10)
EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE! EXTERMINATE!

*Main GHC.TypeLits> launchMissile (newValInRange 11)
*** Exception: Assertion failed
CallStack (from HasCallStack):
  assert, called at range.hs:9:19 in main:Main

On note que l’inférence de type fait son boulot et déduit tout seul que le résultat de newValInRange doit être un Range 0 10.

Mais bon, c'est une usine à gaz de typage dépendant pour au final avoir une erreur au runtime, donc c'est assez inutile, on pourrait remplacer la même chose par un bête check dans la fonction launchMissile.

Ce qui est par contre intéressant c'est quand on peut faire tout ce processus à la compilation. Par exemple, une fonction launchMissile qui connait son nombre de missile à la compilation et peut faire des vérifications statiques dessus :

launchMissile' :: forall (n :: Nat). (KnownNat n, 0 <= n, n <= 10) => IO ()
launchMissile' = case natVal @n Proxy of
  0 -> putStrLn "Paix et harmonie"
  n -> putStrLn (unwords (replicate (fromInteger n) "EXTERMINATE!"))

(Cette solution demande les extensions TypeOperators, ConstraintKinds, TypeFamilies, AllowAmbiguousTypes, rien que ça, et aussi le package typelits-witnesses et l'import de 'GHC.TypeLits.CompareetData.Type.Bool.) IcilaunchMissile'est une fonction qui est paramétrée parnà la compilation, donc c'est à la compilation que l'erreur surn` pétera.

Bon, çà c'est vachement plus simple en C++, qui gère super bien le typage dépendant sur les entiers et vivent les constexpr :

template<int n>
void launchMissile2()
{
    static_assert(n >= 0 && n <= 10, "WTF!");

    if(n == 0)
        std::cout << "Paix et harmonie\n" << std::endl;
    else
        for(auto i = 0u; i < n; ++i)
        {
            std::cout << "EXTERMINATE!\n";
        }
}

constexpr int fact(const int n)
{
    int res = 1;
    for(int i = 1; i <= n; i++)
    {
        res *= i;
    }

    return res;
}

int main()
{
    launchMissile2<fact(3)>(); // lance 3! == 6 missiles
}

(Bon, le c++ c'est bon des fois, constexpr déchire très souvent, jusqu'à ce que tu veuilles créer des valeurs plus poussées au niveau du type. ;)

Aller, dodo.

Je ne vais pas te dire que l'héritage c'est débile et que les ADT sont mieux, c'est juste des cas d'usage différents et des débats d'opinion ;) Personnellement j'ai plus souvent besoin d'un ADT que d'un héritage.

Le débat "héritage" versus "ADT" est souvent proche du problème du couplage et de la notion de comment les choses peuvent évoluer, notamment l'ajout de cas où de comportement.

L'héritage est une hiérarchie ouverte et à ce titre, n'importe qui peut rajouter un enfant avec son propre comportement. Ce n'est pas forcement souhaitable dans un cas où justement le but de ton type est de restreindre la liste des options. Rajouter un cas dans un ADT n'est pas coûteux, mais on ne peut pas le faire sans que tu sois au courant.

Entre les deux, le couplage est différent. L'héritage regroupe ensemble des comportements (parfois sans relation). Les ADT regroupent ensemble des cas de figures, et pour chaque comportement, le traitement de chaque cas de figure.

Dans le cas de l'héritage, si tu veux rajouter un comportement (une méthode), tu dois modifier ta classe de base et chercher toutes les classes enfant pour ajouter ce comportement. Dans le cas d'un ADT, si tu veux rajouter un comportement, tu l'écris où tu veux en listant tous les cas.

Technique

Si on veut parler technique, l'ADT, avec sa liste de cas qui est fixée, peut être optimisé par le compilateur. (Je ne dis pas que c'est fait, mais c'est le cas du std::variant). Par exemple, dans le cas du carré et du réctangle, la solution à base d'héritage et de polymorphisme vas te coûter, en ignorant le coût de la vtable, vas te coûter entre 20 et 24 octet par objet:

• 16 octets alloués sur la pile, le pointeur d’objet et le pointeur de vtable
• 8 octets pour le rectangle et 4 pour le carré, alloué sur le tas.

L'appel à la méthode "surface" vas te coûter, en gros, entre 20 et 32 octets à lire (il faudra aller lire la vtable), et cela à trois endroits différents en mémoire, donc tu consommes 3 lignes de cache pour faire ce traitement.

Maintenant regardons comment peut être layouté un ADT en mémoire, en gros, simplifié, boost::variant ressemblera à :

struct
{
  union
  {
     Carre carre;
     Rectangle rectangle;
  };
  int which;
}

Ce qui donne une taille de 12 bytes, sur la pile, versus entre 20 et 24 bytes, avec une allocation sur le tas. L'appel de la méthode surface te coûtera la lecture de ces 12 bytes (contigus en mémoire) et un branchement sur which.

Les compilateurs actuels implémentent une méthode de devirtualization pour améliorer cette situation, mais le virtuel garde un coût non négligeable.

Tout cela n'est pas comparable à Haskell pour lequel chaque objet est alloué sur le tas et avec un énorme overhead ;)

Tu as tout loisir de faire ce qui t'arrange. Rien ne te limite et tu prix le faire évoluer comme heu le souhaite savez péter le code utilisateur. Ça dépend vraiment de l'utilisation que tu as. Par défaut j'aurais envi que ce ne soit pas des valeurs, mais un comportement.

Dans ce contexte qu'appelles-tu un comportement ? Comment l'implementes-tu ?

Pour le coté évolution, rien ne t’empêche de d'avoir un type différent en interne que celui que tu présentes à l'utilisateur. Autant cela peut commencer par deux types totalement équivalent, et cela peut évoluer en interne. Force de la solution par ADT c'est que si tu ajoutes un constructeur, ton utilisateur aura des warnings de compilation lui indiquant qu'il n'a pas traité tous les cas.

Je ne suis pas sûr d'avoir saisie l'objectif de l'exemple du dessus. Par contre pour le cas du journal c'est évident: ce sont des stratégies. Les implémenter comme tel ne dois pas être dénué d'intérêt.

Tu pourrais donner un exemple de ta solution ? À mon sens, l'implementation que j'ai proposée est clairement une implémentation du pattern strategie, en se servant de boost::variant pour stocker les différentes stratégies. Je trouve que cette approche est plus simple, plus compact et surtout elle apporte un découplage entre la donnée et les opérations que tu peux faire dessus comparé à une implémentation de la même idée utilisant de l'héritage virtuel.

Je sais que c'est moins hype que de décrire des typages sophistiqués, mais des factories font ça très bien.

J'essaye de ne vraiment pas être hype et de régler des vrais problème avec des vrais solutions, les moins complexes possible.

Le soucis de ton approche, comme je le disais en réponse du même commentaire, c'est comment tu stockes l'information à l’intérieur de Test. Si c'est pour réintroduire des valeurs sentinelles, tu as réglé le problème en terme d'interface avec l'utilisateur, et c'est déjà pas mal, mais tu n'as pas réglé le problème à l'intérieur de la classe, où si la valeur doit ressortir.

Et oui en principe derrière si tu as besoin de véritablement récupérer le truc, tu fait du polymorphisme à la place du pattern matching si nécessaire.

Quelle solution à base de polymorphisme proposes-tu ?

Je connaissais pas boost::hana::overload, merci. En effet, c'est pas mal. Merci.

Ta proposition est intéressante pour ne pas se planter lors de l'appel, mais elle ne protège pas dans l'interne de la classe Test car finalement on y retrouve les valeurs sentinelles (1 et 255). Note que dans l'exemple que je donne, 1 thread n'est pas la même chose que pas de parallélisme et 255 threads (possible bientôt avec l'arrivée des puces intel) n'est pas la même chose que "Maximum système".

Un développeur pourra d'ailleurs facilement se tromper en créant 255 threads au lieu des 8 qui ma machine peut largement supporter.

Cette solution ne permet pas non plus de récupérer de façon exploitable facilement le réglage, tu ne peut pas faire de fonction qui renvoie l'un des tags.

Une solution serait l'utilisation de variant tel que :

#include <iostream>
#include <boost/variant.hpp>

struct Fixed { const int _n; };
struct Max {};
struct NoMultithread {};

using Setting = boost::variant<Fixed, Max, NoMultithread>;

struct Test {
    explicit Test(Setting s): setting(s) {}

    Setting setting;
};

int main()
{
    Test t1{Fixed{10}};
    Test t2{Max{}};
    Test t3{NoMultithread{}};
    Test t4{Fixed{-10}};

    struct visitor : boost::static_visitor<std::string>
    {
        std::string operator()(const Fixed &) const
        {
            return "C'est fixé";
        }

        std::string operator()(const Max &) const
        {
            return "Max";
        }

        std::string operator()(const NoMultithread &) const
        {
            return "c'est un NoMultiThread";
        }
    };

    std::cout << boost::apply_visitor(visitor(), t1.setting) << std::endl;
    std::cout << boost::apply_visitor(visitor(), t2.setting) << std::endl;
    std::cout << boost::apply_visitor(visitor(), t3.setting) << std::endl;
    std::cout << boost::apply_visitor(visitor(), t4.setting) << std::endl;

    return 0;
}

Cette solution apporte la même souplesse et la même sécurité que les ADT, mais dieu que c'est verbeux ;)

C'est cool ça.

En Haskell, le newtype est un type équivalent, mais non compatible :

    newtype MyInt = MyInt Int

Après on peut convertir un Int en MyInt de plusieurs manière, en utilisant le constructeur, par pattern matching ou via des casts sécurisés.

Dans d'autres langages, ce serait contraignant car il faudrait écrire toutes les méthodes / fonctions associées. En haskell, on peut lui demander de dériver automatiquement tout comportement (class) implementée par le sous type.

Exemple, si on veut faire un sous type qui se comporte comme un String (au moins pour certaines opérations) mais qui n'est pas compatible avec une String:

newtype MyString = MyString String deriving (Show, Monoid, Eq, Ord)

Monoid fournissant la concaténation de chaîne via (<>), Show fournissant l'affichage. Eq et Ord fournissant respectivement les relations d'égalité et d'ordre. Cet exemple utilise l'extension GeneralizedNewtypeDeriving.

> MyString "hello" <> MyString "you"
MyString "helloyou"
> MyString "hello" == MyString "you"
False
> sort [MyString "hello", MyString "you", MyString "world"]
[MyString "hello",MyString "world",MyString "you"]

Ce genre de chose est malheureusement difficile à réaliser dans d'autre langage, et souvent il faut réaliser une classe englobante et propager toutes les méthodes intéressantes, c'est beaucoup de code lourd pour pas grande chose.

En C++ on peut s'en sortir avec des types phantoms :

struct TagColor
{};

struct TagPosition
{};

struct TagDirection
{};

template<typename Tag>
struct Point3
{
    float x, y, z;

    Point3<Tag> operator+(Point3<Tag> &other)
    {
        return {x + other.x, y + other.y, z + other.z};
    };
};

using Color = Point3<TagColor>;
using Position = Point3<TagPosition>;
using Direction = Point3<TagDirection>;

int main()
{
    Color c{1, 1, 0};
    Color c2{0, 0, 1};

    Color c3 = c + c2;

    Position p{0, 0, 0};

    // Erreur de compilation, on ne peut pas additionner un point et une couleur
    Position p2 = p + c;
}

Mais cette solution devient vite embêtante quand on veut pouvoir définir un sous ensemble d'opération pour chaque type. Par exemple, l'addition entre deux couleurs peut avoir du sens, alors qu'entre deux positions ?

À ce niveau, la meilleur solution que je connaisse c'est de faire une classe Point qui contient toutes les opérations nécessaires, et des classes Position, Direction, Couleur qui encapsulent un Point de manière privée et qui n'exposent que les fonctions nécessaires.

En ce moment, il y a 70,332 paquets sur nuget.org

Tu as de l’expérience avec nuget ? C'est utilisable, stable ?

Je suis vraiment à la recherche d'un moyen d'obtenir facilement la quantité infâme de dépendances nécessaires à notre logiciel sous windows. Pour l'instant c'est tout compilé avec des scripts persos, non maintenable et qui cassent tous les mois.

Par contre, je trouve cela dingue qu'avec 70 332 paquets il n'y en ai que 10% des dépendances du produit que je veux packager, là où arch linux avec 15000 packets couvre 100% de mes besoins. Et je ne triche pas, ce n'est que des dépendances cross plateformes utilisées dans une industrie qui vise principalement Windows.

Bon, je vais quand même regarder nugget et je crois que je vais créer les packets qu'il me manque.

Ne plus avoir de voiture personnelle. Actuellement, il y a la louche une voiture par personne en état de conduire. (Wikipedia : ~38 Millions de voiture dans le parc Français, pour 68 Millions de Français, si on enlève les enfants et les vieux qui ne conduisent plus, cela doit le faire). Je n'ai aucun chiffre, mais j'imagines que ces véhicules ne tournent pas plus d'une heure par jour en moyenne.

J'aimerais remplacer le parc de voiture individuelles par un parc de voiture collectives. Tu aurais un outil pour réserver un trajet entre deux points et la voiture viendrait te chercher et t'y emmènerais, en prenant sans doute sur le chemin quelques co-voitureurs.

Au final, le réseau serait totalement débloqué et le problème du parking serait réglé, car le parc de voiture autonomes serait réduit.

Le service de presse de l'état nous apprend, anecdote amusante que "La petite bande est tombée le jour ou [l'éditeur Romulien] s’est fait passer pour un client et a fait livrer la commande chez un huissier de justice." Quels petits filous !

C'est pas interdit ça ?

Sur http://www.police-nationale.interieur.gouv.fr/Organisation/Direction-Centrale-de-la-Police-Judiciaire/Les-actes-d-enquete on peut lire :

Les actes d’infiltration
L’agent infiltré est autorisé à faire usage d’une identité d’emprunt, à opérer sur l’ensemble du territoire national et, sans être pénalement responsable, à effectuer certains actes dont la liste est fixée par le code de procédure pénale (par exemple : acquisition, détention, transport et livraison de substances ou informations tirées de la commission des infractions ou mise à disposition des personnes se livrant à ces infractions de moyens juridiques, financiers, de transport ou d’hébergement). Les actes de l’agent infiltré ne doivent pas constituer une incitation à commettre l’infraction.

Ha, c'est pas con, les JDLL. (Après, j'ai pas dis non plus que j'avais des vrais trucs à raconter).

Que des trucs de gens qui font du web et de l'agile ;) Moi je suis plutôt pas web du tout et pas agile du tout, ou alors sur mon temps libre où je joue avec Haskell et Nix(OS).

Ça donne envie d'y aller, pour une fois qu'il se passe des choses à Lyon, je me motiverais bien pour raconter un truc tient…

De quoi vas-tu parler ?

En fait je pense que j'ai fais une erreur dans mon énoncé, mais comme Luke, je pense qu'il y a encore du bon quelque part ;)

J'ai défini une relation d'ordre entre mes éléments tel que compare (_, a) (_, a') = compare a a' qui implique autant <= que ==. J'ai donc une relation d'ordre totale définie en se servant du second élément du tuple.

Mais dans mon énoncé, et je me sert à tort de l'égalité entre tuple. En effet, quand j'écris :

>>> min(l, key=key) == list(sorted(l, key=key))[0]
True
>>> max(l, key=key) == list(sorted(l, key=key))[-1]
False

je triche, car j'utilise le == défini sur les tuples et non pas le == de ma relation d'ordre. Si j'avais utilisé le bon == j'aurais obtenu True.

Et c'est là que je me suis planté.

Maintenant, je pense que tout cela n'invalide en rien ma conclusion, qui est qu'il faut faire attention avec certaines supposition et que on peut se planter facilement. Mais j'aurais pu l'écrire en moins de caractère, c'est vrai ;)

Bref dans le cas d'une liste dont tous les éléments sont égaux, que min ou max me renvoient un élément aléatoire de la liste ne me choquerait pas;

Moi non plus, mais c'est un peu tout le point de l'étude de cas présentée, on peut écrire cet algorithme de cette façon que si on a des certitudes sur le comportement de la fonction max. Sinon il faut l'écrire autrement.

On s'est tous les deux emmêler les pinceaux ;)

le soucis c'est que tu prends quand même un postulat de départ qui n'a pas de base mathématique, que le min ou le max te renvoient le premier ou le dernier élément d'une liste triée n'est vrai que lorsque tu as un ordre absolu. Que chaque langage ait sont propre comportement me semble logique.

L'ordre absolu c'est dire que quel que soit x et y dans un ensemble, on peut montrer que x <= y ou y <= x, bref on peut mettre une relation d'ordre entre deux éléments de ton ensemble, c'est le cas de mon ensemble de tuple (string, int) que j'ai présenté. La particularité de cet ensemble c'est que on peut distinguer les éléments qui sont égaux. Ainsi, une permutation de deux éléments égaux ne change rien au niveau de la relation d'ordre mais change le résultat. Et c'est là que on s'attend à un tri stable pour ne pas changer ce résultat.

Mais bon, au final, le but de mon article écrit ce matin dans un moment de procrastination^W compilation était de discuter comment un petit détail aussi insignifiant que l’implémentation d'une fonction max peut totalement bouleverser un algorithme.

En effet, le tri doit être stable pour que l’égalité max(l) = last(sort(l)) soit vérifiée, mais ce n'est pas la seule condition, il faut aussi que max a b key == b si key a == key b.

Ton approche m'a faite rejouer avec les GADTs et les l'approche tagless finale et je viens enfin de résoudre un problème vieux comme le monde pour moi.

Je veux representer des expressions, genre "1 + 2 * x", qui peuvent contenir une "variable". Cela nous donne un ADT assez simple (Je le fais en Haskell, ce sera plus lisible que si je le faisais en OCaml, principalement parce que le Haskell est plus lisible, mais surtout parce que je ne maîtrise pas du tout l'écriture du OCaml et donc je ferais des erreurs ;):

data Expr = Add Expr Expr | Lit Int | Variable

L'expression "1 + x" précédente étant représentée par Add (Lit 1) Variable.

Je veux pouvoir évaluer mon expression :

eval :: Expr -> Int
eval (Lit i) = i
eval (Add e e') = eval e + eval e'
eval Variable = error "cannot evaluate a variable"

Suivez mon regard, j'aimerais dégager ce cas particulier. On va passer aux GADT pour représenter tout cela :

data Expr useVariable where
    Add :: Expr aUseVariable -> Expr bUseVariable -> Expr (FOr aUseVariable bUseVariable)
    Lit :: Int -> Expr SansVariable
    Variable :: Expr AvecVariable

Derrière se cache une fonction au niveau du type FOr :

type family FOr a b where
   FOr AvecVariable _ = AvecVariable
   For _ AvecVariable = AvecVariable
   For _ _ = SansVariable

Et ça cela marche, le type de Variable est bien Expr AvecVariable, le type de Add (Lit 1) (Lit 2) est bien Expr SansVariable et le type de Add Variable (Lit 4) est bien Expr AvecVariable.

Revenons à notre fonction eval :

eval :: Expr SansVariable -> Int
eval (Lit i) = i
eval (Add e e') = eval e + eval e'

Le type marque clairement que on ne peut évaluer qu'une expression SansVariable. Et le cas Variable n'est plus à écrire puisque il n'existe plus. Cependant cela ne marche pas. Pourquoi ?

Parce que Haskell (GHC 8.0) n'est pas capable de prouver que si (Add e e') est Expr SansVariable, alors e et e' le sont aussi. La preuve est triviale pour nous en regardant la fonction FOr, mais pas pour GHC.

Est-ce que OCaml sait faire ça ?

Comment feriez vous sinon ?

Note: la méthode TagLess final marche bien ici puisqu'il suffit de ne pas écrire d’implémentation d'eval pour Variable et le compilateur refusera de compiler un appel à eval sur un type qui contient des Variable. C'est cool ;)

Merci pour cet article pour le moins étendu et détaillé.

Petite coquille ? "Lorsque l'on a supprimé les littéraux nuls, on a au fond transformer" J'ai un doute sur "transformer" qui me semblerait plus judicieux en "transformé".

J'avais lu l'article de Oleg Kiselyov à ce propos et je trouve l'approche tagless très élégante.

Maintenant j'aurais deux questions, une plus générique et une plus orientée OCaml.

a) Hormis dans le cas d'un arbre syntaxique pour évaluer des expression pour faire un compilateur, est-ce que tu vois un autre usage des GADTs ? Cela fait partie des fonctionnalités qui me frustrent car elles apparaissent très puissantes mais au final je ne trouve jamais l'occasion de m'en servir.

b) Est-ce que les modules OCaml peuvent être vu comme un sur-ensemble ou un sous-ensemble (ou rien à voir) des typeclasses d'Haskell.

J'adore tes réponses ! Complètes, avec des liens, super. Déjà que je trouve que les réponses que j'écris sont souvent longue à écrire, tu dois y passer un temps non négligeable, merci.

Cependant j'ai maintenant une question. Tu dis qu'en OCaml, il faut changer d'opérateur entre les float et les int. Mais qu'en est-t-il entre les différentes représentations de ceux-ci. Genre si tu as des int16, des int32, des int64, des int de taille infinie ? C'est chaque fois un autre opérateur où il y a une solution intermédiaire ?

Yahoo, je suis enfin reconnu par mes pairs ;)

En effet, en C++ tous les types numériques sont implicitement castables en un autre type numérique, et comme les enums et les bools sont des types numériques, cela devient vite comique. Tu peux cependant activer des warnings quand ces conversions font de la perte d'information, mais c'est simplement un warning et surtout il dépend du compilateur :

void add(float, int, int){}

int main()
{
    if(3.5)
    {
        add(2, false, 3.5);
    }
}

La compilation avec clang nous donne :

λ skyskolem ~ → clang++ test_conv.cpp -Wall -Wextra -Wall -Wconversion
test_conv.cpp:5:5: warning: implicit conversion from 'double' to 'bool' changes value from 3.5 to true
      [-Wliteral-conversion]
        if(3.5)
        ~~ ^~~
test_conv.cpp:7:17: warning: implicit conversion from 'double' to 'int' changes value from 3.5 to 3
      [-Wliteral-conversion]
                add(2, false, 3.5);
                ~~~           ^~~
2 warnings generated.

(note: j'avoue que je n'ai pas cherché si il existe un ensemble de flags pour en trouver plus).

À cela j'ajoute un piège dans lequel beaucoup de développeurs C++ tombent facilement c'est que par définition en C++ un constructeur à un argument est un opérateur de cast implicite :

struct Test
{
    Test();
    Test(int);
    Test(bool);
};

void foo(Test, Test, Test);

int main()
{
    Test a;
    foo(5, true, a);
}

Ce problème se règle en préfixant les constructeur du mot clé explicit, mais l'oubli est facile.

Pour finir ce message, je voudrais expliquer comment cela fonctionne dans Haskell. C'est la même situation qu'en OCaml au sens que les conversions implicites n'existent pas. Cependant en ce qui concerne les literaux numériques c'est un peu particulier, ceux-ci sont polymorphiques, ce qui veut dire que 2 est potentiellement un Float/Double/Int/Integer/Int32/Word16 et cela ne sera décidé que par le biais de l’inférence de type, en gros c'est la fonction qui prendra notre literal en paramètre qui décidera de son sort.

Notons cependant que ce choix est fait en fonction du literal. En gros, 3 peut être un Double, mais 3.2 ne peut pas être un Int, exemples, avec deux fonctions:

f :: Int -> Int
f x = 2 * x

g :: Float -> Float
g x = 2 * x

Prelude> g 2
4.0
Prelude> f 2
4
Prelude> g 2.3
4.6
Prelude> f 2.3

<interactive>:20:3: error:
    • No instance for (Fractional Int) arising from the literal ‘2.3’
    • In the first argument of ‘f’, namely ‘2.3’
      In the expression: f 2.3
      In an equation for ‘it’: it = f 2.3

C'est un beau compromis dans le sens où il n'est pas nécessaire de typer explicitement ses literaux, mais aucun cast implicite n'est effectué. En contrepartie il faut de temps à autre être explicite sur le type car l'inférence de type s'y perd.

C'est aussi pratique quand on commence à implémenter ses propres types numériques pour différents cas de figure (calcul vectoriel, auto differentiation, …) et où il est agréable de profiter de l'écriture de litéreaux. Exemple non complet, soit une fonction f :

f v = 2 * (v * v)

Le type inferé par Haskell est f :: Num a => a -> a. En gros, une fonction qui prend un Num et retourne un Num.

Cela fonctionne pour les littéraux "classiques" :

Prelude> f 2
8
Prelude> f 2.3
10.579999999999998

Mais j'ai aussi définis mon type numérique maison Expr Float qui représente un arbre d'expression et je peux utiliser f dessus :

> (f 5) :: Expr Float
Mul (Constant 2.0) (Mul (Constant 5.0) (Constant 5.0))

Bon, je me suis encore lâché et j'ai expliqué pleins de trucs au lieu de regarder le meilleur pâtissier ;) Bonne soirée.