Bibliothèque standard avec des objets

**InOCamlWeTrust** · 25/04/2009, 11h53

Envoyé par SpiceGuid

Une pile c'est la solution n°2 non ?
(une pile ça n'est guère plus qu'une liste où cons = push, head = top et tail = pop)

Je ne sais pas vraiment ce que tu entends par une liste des noeuds traversés. Veux-tu dire stocker tous les éléments parcourus ? Dans ce cas, la solution est mauvaise pour des arbres binaires, car elle est linéaire en espace mémoire, ce qui, pour une fonction de ce type, n'est pas acceptable. On n'imagine pas avoir à copier une structure de données potentiellement très importante. Concernant les petits tests des AVL, cela voudrait dire que tu aurais environ 200 Mo de données, plus 200 Mo copiés à cause d'une fonction de visite mal programmée !

Quand je dis pile, je veux dire une pile contenant des noeuds, mais exactement comme le ferait un appel récursif. Pour un arbre binaire AVL, on devrait stocker une structure logarithmique, chose qui est déjà beaucoup plus acceptable en termes de consommation mémoire, surtout lorsque l'on possède une borne supérieure de la hauteur d'un AVL de n noeuds.

Pour revenir aux éventuelles fonctionnalités de la bibliothèque, coder de vrais algorithmes de tri, efficaces, ne serait pas une option également. On peut ainsi penser à un vrai quicksort, un vrai mergesort, shellsort pour les petits vecteurs et même un tri compteur pour les vecteurs d'entiers.

**Alp** · 25/04/2009, 12h07

Au passage : http://caml.inria.fr/cgi-bin/hump.en.cgi?contrib=352

**InOCamlWeTrust** · 25/04/2009, 13h54

Ce sujet avait déjà été abordé au début de la discussion.

**SpiceGuid** · 25/04/2009, 15h49

@InOCamlWeTrust
Ce que tu décris a toujours été la solution n°2 dans mon énumération.
C'est exactement comme ça en OCaml-Reins. Malheureusement ton imagination arrive à te convaincre qu'en changeant de paradigme tu parviens à faire les choses de façon originale alors que tu ne fais qu'alourdir la notation en ajoutant un héritage purement bureaucratique là où une simple fonction fait très bien l'affaire.

**Cacophrene** · 25/04/2009, 17h47

Salut !

Envoyé par SpiceGuid

L'intérêt du visiteur réside dans la notion de curseur, dans un éditeur structuré (genre éditeur d'équations) l'utilisateur peut mettre le focus sur un certain conteneur et naviguer de façon hiérarchique pour éditer tel ou tel sous-conteneur.

Ne peut-on pas simuler ce comportement (au moins en partie, je n'ai pas creusé l'idée) avec quelque chose qui dériverait plus ou moins fortement d'une liste doublement chaînée circulaire ? La force de ce type de liste réside dans le fait qu'on peut la tourner dans tous les sens, et la "tête" de la liste peut alors être vue comme l'élément qui a le focus.

Cordialement,
Cacophrène

**gasche** · 25/04/2009, 20h50

C'est l'idée des zippers que l'on peut généraliser sur d'autres structures de données (arbres y compris), et donc SpiceGuid a déjà parlé.

**InOCamlWeTrust** · 25/04/2009, 22h52

Envoyé par SpiceGuid

@InOCamlWeTrust
Ce que tu décris a toujours été la solution n°2 dans mon énumération.
C'est exactement comme ça en OCaml-Reins. Malheureusement ton imagination arrive à te convaincre qu'en changeant de paradigme tu parviens à faire les choses de façon originale alors que tu ne fais qu'alourdir la notation en ajoutant un héritage purement bureaucratique là où une simple fonction fait très bien l'affaire.

Je n'ai jamais prétendu faire les choses de façon originale. Par contre, mettre des visiteurs dans la librairie standard, en POO ou non, c'est original parce qu'il n'y en a pas.

Je sais aussi que l'on peut faire exactement les mêmes choses dans d'autres paradigmes, et je sais aussi que ce genre de choses n'est pas particulier à la POO. Tu dois suffisament bien me connaître pour savoir que je gueule assez souvent sur le tout objet.

Face à une librairie standard qui est globalement bien foutue, mis à part Set, Map, Format et les fonctions de tri, mais qui n'exploite pas toutes les fonctionnalités de son propre langage, j'aime bien penser à quoi elle pourrait ressembler.

Si ce que tu n'as pas aimé, et je peux le comprendre, c'est ma remarque à propos de ton expérience, sache qu'il n'était aucunement dans mon intention te blesser, pour quelque motif que ce soit.

**Garulfo** · 26/04/2009, 05h51

Envoyé par InOCamlWeTrust

[...]
Face à une librairie standard qui est globalement bien foutue, mis à part Set, Map[...]

Mais ces modules ont au moins la particularité d'être prouvé fiable de façon formelle. C'est quand même intéressant. Maintenant rien n'empêcherait de rajouter des fonctionnalités et de reprouver la fiabilité je suppose.

**InOCamlWeTrust** · 26/04/2009, 12h09

Ah oui ? Tu savais que jusqu'à la version 3.07 ces deux modules bugaient et pouvaient, dans certains cas, produire des arbres de hauteur linéaire en le nombre de noeuds... C'est un bug qui a été corrigé il y a seulement 2 ou 3 ans. Avant d'en avoir la preuve formelle sur le site (je ne me souviens plus si le bug avait été posté sur le fil de discussion ou sur le bug-tracker), je m'en doutais déjà, car certains de mes programmes prenaient beaucoup moins de temps à s'exécuter avec de simples arbres binaires qu'avec Set et Map.

Ca pour du solide...

De plus, l'implantation, au regard de la qualité générale du langage et du compilateur qui est très élevée, est plutôt faiblarde.

Comme je l'ai déjà dit ici et dans d'autres discussions, la librairie standard est globalement bien foutue, mais pêche sur certains points. Format en est, pour moi, un autre exemple. Concernant ce module, faire une interface qui soit plus dirigée par les données que par des traitements purement impératifs serait un plus. Expliciter la structure de données pourrait être trop complexe à utiliser. C'est pourquoi je pense qu'introduire des objets dans ce module permettrait de trouver un bon équilibre entre traitements et données. Et quand je dis objets, j'inclus aussi et surtout les objets fonctionnels.

**SpiceGuid** · 26/04/2009, 16h28

Envoyé par Cacophrene

Ne peut-on pas simuler ce comportement (au moins en partie, je n'ai pas creusé l'idée) avec quelque chose qui dériverait plus ou moins fortement d'une liste doublement chaînée circulaire ? La force de ce type de liste réside dans le fait qu'on peut la tourner dans tous les sens, et la "tête" de la liste peut alors être vue comme l'élément qui a le focus.

Pour effectuer la remontée (pattern iterator) il faut en effet, d'une manière ou d'une autre, inverser le chemin parcouru depuis la racine. On peut le faire de façon mutable (par inversion des pointeurs) ou immutable (n'importe quel TAD du genre LIFO fait l'affaire). Une autre façon consiste à ajouter un champ parent, qui effectivement transforme la liste des noeuds depuis la racine en une liste doublement chainée. À ma connaissance on le fait dans les éditeurs d'équations parce que les contraintes graphiques inter-boîtes peuvent se propager dans les deux sens. Dans un arbre binaire de recherche on préfère un zipper parce qu'ajouter un champ ça a un proportionnel au nombre de noeuds qui se chiffre en Mo quand le nombre de noeuds dépasse les centaines de milliers.

OCaml a ceci de remarquable qu'on peut adopter le style qu'on veut. J'ai fait de la POO suffisamment longtemps pour trouver ce style "naturel" avant d'avoir envie de passer à autre chose. OCaml est un langage riche avec peu d'utilisateurs par conséquent il est inévitable que certains aspects restent sous-exploités. C'est le cas de la POO que pour ma part je trouve très bien conçue, certes un peu déroutante au début mais c'est le prix à payer pour l'innovation.

Envoyé par InOCamlWeTrust

mettre des visiteurs dans la librairie standard, en POO ou non, c'est original parce qu'il n'y en a pas

Abondance de biens ne nuit pas si l'interface est modulaire.
Une conception que j'aime bien consiste à composer l'interface en assemblant les aspects souhaités.
Pour moi ça donne (dictionnaire avec opérations ensemblistes et folds):

Code :

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

1
2
3
4
5
6
7
8
  functor (Ord: Property.Ordered) ->
  sig
    include Map.Pure
    include Map.PureSet
       with type 'a set = 'a map and type set_key = key
    include Property.OrderedMapFoldable
       with type 'a foldable = 'a map and type fold_key = key
  end

Pour toi ça pourrait donner (dictionnaire visitable):

Code :

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

1
2
3
4
5
6
  functor (Ord: Property.Ordered) ->
  sig
    include Map.Pure
    include Property.Visitable
       with type 'a visitable = 'a map and type visitor_key = key
  end

Je trouve ça astucieux parce que ça dépasionne le débat sur ce qui a sa place et ce qui n'a pas sa place. Tout devrait avoir sa place pourvu qu'on fournisse la signature correspondante.

**InOCamlWeTrust** · 26/04/2009, 23h31

A mon humble avis, une FIFO suffit pour pouvoir parcourir l'arbre dans un sens comme dans l'autre. On n'a pas nécessairement besoin d'une LIFO.

**Garulfo** · 27/04/2009, 06h08

Envoyé par InOCamlWeTrust

Ah oui ? Tu savais que jusqu'à la version 3.07 ces deux modules bugaient et pouvaient, dans certains cas, produire des arbres de hauteur linéaire en le nombre de noeuds... C'est un bug qui a été corrigé il y a seulement 2 ou 3 ans. Avant d'en avoir la preuve formelle sur le site (je ne me souviens plus si le bug avait été posté sur le fil de discussion ou sur le bug-tracker), je m'en doutais déjà, car certains de mes programmes prenaient beaucoup moins de temps à s'exécuter avec de simples arbres binaires qu'avec Set et Map.[...]

Mais ça a changé. La preuve a été faite en Coq avec génération de code.
Voici la preuve pour Set... je ne suis plus sûr à 100% que l'autre soit Map mais c'est ce qui me semble le plus probable.
http://www.lri.fr/~filliatr/fsets/index.en.html

alex_pi · 27/04/2009, 07h57

Envoyé par Garulfo

Mais ça a changé. La preuve a été faite en Coq avec génération de code.

Euh...
"Quelqu'un a formalisé une librairie de Set en Coq" != "La librairie actuelle de OCaml est dans une version formalisée"

**InOCamlWeTrust** · 27/04/2009, 20h23

Le problème n'est pas là, Garulfo.

Prouver qu'une fonction ou une librairie respecte les contraintes de l'interface ne veut pas dire qu'elle ne bugue pas !

OCaml était déjà prouvé, me semble-t-il, lorsque le bug avait été corrigé. Et pour cause, la librairie remplissait exactement son contrat... à ceci près qu'elle était lente parce que dans certains cas la hauteur de l'arbre pouvait croître trop rapidement. Clairement, on avait dû oublier de prouver que la différence de hauteur était au plus 2, ou un tout autre invariant non critique. Par contre, les fonctions d'insertion et de suppression faisaient ce qu'on leur demandait, mais pas de la façon que l'on croyait.

C'est là une des limites, me semble-t-il, de la preuve à tout-va. On peut prouver qu'une fonction assume son rôle, mais ce n'est pas pour autant que l'on prouve qu'elle fonctionne exactement comme on le souhaite. Prouver les invariants critiques ne veut pas dire que l'on prouve tous les invariants. Je peux prouver que ma fonction trie un tableau, par contre, prouver qu'elle le trie tel que je le conçois... c'est un autre problème.

De toute façon, prouvée ou non, je trouve que l'implantation de Xavier Leroy est beaucoup trop mauvaise pour un langage et un compilateur de cette qualité. Ces deux modules font tout simplement tâche dans la librairie, comme si ils témoignaient d'un certain laxisme.

**Alp** · 27/04/2009, 20h42

Jane St n'a pas implémenté ses propres versions par hasard d'ailleurs ?

**InOCamlWeTrust** · 28/04/2009, 18h38

Très certainement. De mémoire, je crois qu'il était fait mention dans le forum du développement, en interne, d'un remplaçant de la librairie standard... et ils ont bien raison !

Pour info, on trouve Set et Map dans le compilateur en lui-même, afin de coder les tables de symboles, entre autres. Donc jusqu'à la version 3.07, le noyau du compilateur, qui était certifié, contenait un bug... mais il fonctionnait parfaitement !

**Garulfo** · 28/04/2009, 19h31

Envoyé par alex_pi

Euh...
"Quelqu'un a formalisé une librairie de Set en Coq" != "La librairie actuelle de OCaml est dans une version formalisée"

Si je ne me trompe, la version actuelle de Set est celle générée par Coq.
Mais je me trompe peut-être.

alex_pi · 28/04/2009, 19h35

Mais euh, vous voyez tous de la certification partout ??

@Garulfo
Regarde la date de la dernière modif de set.ml, c'est bien avant la formalisation de Jean-Chrisophe.

@IOWT
Et depuis quand le noyau est "certifié" ? enfin surtout, qu'entends tu par là ?

**Garulfo** · 28/04/2009, 19h35

Envoyé par InOCamlWeTrust

Le problème n'est pas là, Garulfo.

Prouver qu'une fonction ou une librairie respecte les contraintes de l'interface ne veut pas dire qu'elle ne bugue pas ![...]

Il n'y a pas que l'interface externe. Si tu spécifies un comportement de manière formelle celui-ci peut être vérifié. Ainsi si la propriété mise en défaut est spécifiée clairement, le fait que la preuve de fiabilité ait été faite empêche cette erreur d'apparaître. Cependant si bien sûr tu ne l'as pas spécifié alors elle peut être présente. Vu qu'on ne pense jamais à toutes les propriétés voulues, il est toujours possible d'avoir un comportement non voulue sur un point. Le terme « bug » est très imprécis. Dans le cas que tu mentionnes le comportement n'était pas désiré, mais savait-on exactement que ce comportement était problématique avant de l'implémenter ? Si oui alors c'est une erreur du développeur sinon c'est plutôt une erreur dans l'analyse des besoins.