IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Bibliothèque standard avec des objets


Sujet :

Caml

  1. #1
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut Bibliothèque standard avec des objets
    Bonjour à tous !

    Suite à une suggestion de InOCamlWeTrust sur un autre fil de discussion, j'ai commencé dans mon coin un embryon de bibliothèque standard avec des objets. Je dis que c'est un embryon parce qu'il n'y a pour l'instant que le module String... je tiens à vous faire part d'emblée de la chose avant d'aller plus loin, comme ça je pourrais prendre en compte les remarques dès le début. Bien évidemment le but est que tous les modules passent petit à petit à la moulinette à objets .

    Fichier d'implémentation (oString.ml) :
    Code : 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
    class ostring ?(init = "") () =
      object(self : 'a)
        val me = init
        method get = String.get me
        method set = String.set me
        method copy = {< me = String.copy me >}
        method fill = String.fill me
        method length = String.length me
        (* non tail-rec à cause de List.map... bien ou mal ? *)
        method concat (l : 'a list) =
          {< me = String.concat me (List.map (fun obj -> obj#to_string) l) >}
        method sub ~pos ~len = String.sub me pos len
        method iter f = String.iter f me
        method escaped = {< me = String.escaped me >}
        method index = String.index me
        method rindex = String.rindex me
        method index_from = String.index_from me
        method rindex_from = String.rindex_from me
        method contains = String.contains me
        method contains_from = String.contains_from me
        method rcontains_from = String.rcontains_from me
        method uppercase = {< me = String.uppercase me >}
        method lowercase = {< me = String.lowercase me >}
        method capitalize = {< me = String.capitalize me >}
        method uncapitalize = {< me = String.uncapitalize me >}
        method compare (o1 : 'a) (o2 : 'a) = 
          String.compare o1#to_string o2#to_string
        method to_string = me
        method of_string x = {< me = x >}    
      end
    
    let create n = new ostring ~init:(String.create n) ()
    let make n c = new ostring ~init:(String.make n c) ()
    let of_string init = new ostring ~init ()
    Fichier d'interface (oString.mli) :
    Code : 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
    class ostring :
      ?init:String.t ->
      unit ->
      object ('a)
        method capitalize : 'a
        method compare : 'a -> 'a -> int
        method concat : 'a list -> 'a
        method contains : char -> bool
        method contains_from : int -> char -> bool
        method copy : 'a
        method escaped : 'a
        method fill : int -> int -> char -> unit
        method get : int -> char
        method index : char -> int
        method index_from : int -> char -> int
        method iter : (char -> unit) -> unit
        method length : int
        method lowercase : 'a
        method of_string : String.t -> 'a
        method rcontains_from : int -> char -> bool
        method rindex : char -> int
        method rindex_from : int -> char -> int
        method set : int -> char -> unit
        method sub : pos:int -> len:int -> string
        method to_string : String.t
        method uncapitalize : 'a
        method uppercase : 'a
      end
    
    val create : int -> ostring
    val make : int -> char -> ostring
    val of_string : String.t -> ostring
    Voilà. Je posterai prochainement d'autres modules, afin que nous puissions voir ce qu'il convient le mieux de faire pour les faire cohabiter dans la joie et la bonne humeur

    Cordialement,
    Cacophrène

  2. #2
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Je ne suis pas sûr que String soit le module le plus aisé à transformer.

    Concernant l'implantation, tout envelopper dans une classe, étant donné que l'on a déjà les fonctions de base de la librairie standard, c'est pas franchement intéressant, ni intellectuelement ni en matière de programmation. C'est un travail mécanique.

    Je pensais à une librairie standard orientée objet, totalement indépendante de celle existant (donc recodée depuis 0, sauf Magic, et avec laquelle il serait possible d'utiliser l'option -nostdlib), possédant globalement les mêmes fonctionnalités, mais pas nécessairement la même interface à la fonction près. Entre autres, pour un projet comme celui-ci, il faudrait penser aux fonctions à ajouter pour que l'héritage par une sous-classe devienne possible ou intéressant. On peut penser, par exemple, à l'implantation d'un patron visiteur pour les structures telles Map et Set et qui permettrait à d'autres structures d'hériter facilement, sans pour autant être obsédé d'implanter à tout prix des Design Patterns.

    Voilà, à mon avis le challenge réside là.

    Array, List et String ne méritent pas nécessairement, à mes yeux, une transformation en objet. Il s'agit là de structures de données de base du langage, et sont traitées en tant que tel par le compilateur. 'a option de même.

  3. #3
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Citation Envoyé par InOCamlWeTrust
    Je pensais à une librairie standard orientée objet, totalement indépendante de celle existant (donc recodée depuis 0, sauf Magic, et avec laquelle il serait possible d'utiliser l'option -nostdlib)
    C'est effectivement plus intéressant si on repart de zéro, même si le temps nécessaire est assez conséquent. Je vais essayer de faire quelque chose dans ce sens, au moins dans un premier temps pour String, histoire de me faire la main, même si par la suite ce ne sera pas utilisé. Ça évitera de faire le premier jet sur un module à conserver.

    Cordialement,
    Cacophrène

  4. #4
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Ma question : à quoi ça sert ? Vous avez des exemples concrets où la POO est utile, ou au moins des explications compréhensibles ?

    Je ne dis pas que ce n'est pas le cas, je me pose juste franchement la question. En tout cas je doute que ça vienne du module String en effet.

    Dans Camlp4 il y a de la POO très sympa à utiliser, ce que produisent les FoldGenerator, par exemple Ast.map et Ast.fold.

  5. #5
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Mouarf plus j'y pense et plus je me dis que ce n'est pas tout à fait compatible avec mon temps libre du moment... mais je crois qu'une motivation forte serait de montrer qu'on peut aussi faire de la POO en OCaml sans perdre pour autant ce qui fait l'intérêt des langages fonctionnels.

    Cordialement,
    Cacophrène

  6. #6
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Ben il y a les objets fonctionnels pour ça !

    La plus grande utilité de la POO est l'extension des fonctionnalités. Syntaxiquement, aussi, je trouve plus logique de faire set#cardinal plutôt que cardinal set. Ca permet aussi d'économiser des parenthèses.

    Concernant l'exemple concret, je pense qu'il(s) viendra(ont) au fur et à mesure que la bibliothèque se construit... si elle devait se construire.

  7. #7
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 59
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par InOCamlWeTrust Voir le message
    [...]Syntaxiquement, aussi, je trouve plus logique de faire set#cardinal plutôt que cardinal set. Ca permet aussi d'économiser des parenthèses.[...]
    Ton exemple n'est pas très convaincant. En premier lieu je ne vois pas en quoi c'est plus logique. Bien sûr si tu réfléchis en OO c'est plus logique, mais si tu réfléchis d'un point de vue mathématique, il est plus « logique » ou « naturel » d'écrire cardinal set. Et puis, en second lieu, dire que ça économise des parenthèses alors que tu n'en mets pas dans ton exemple, mais qu'en plus tu utilises un symbole supplémentaire semble aussi un peu mal habile

    Plus rationnellement, pour la syntaxe c'est affaire d'habitude et de culture plus que de logique et de naturel. Et pour la réduction du nombre de parenthèses, il faudrait peut-être juste trouver un autre exemple non ? Mais je ne pense pas que ça fait vraiment un bon argument. On peut aussi trouver que les parenthèses aident parfois à la lecture.

  8. #8
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Imaginons ce qu'un non-camélien peut penser d'Objective Caml. Il découvre un langage qui permet de programmer de façon impérative, fonctionnelle et avec des objets. S'il consulte la bibliothèque standard (car il veut trouver des exemples, c'est bien normal), il trouvera son bonheur pour la prog impérative (ar ex. dans array.ml), la prog fonctionnelle... épuicétou ! Il verra certes aussi l'intérêt de structurer son code avec des modules... mais aucune trace de prog avec objets. Pourtant, des projets comme LablGTK, pour ne citer que lui, exploitent à fond cette possibilité. Il me semble donc intéressant, avec InOCamlWeTrust, de rêver d'une bibliothèque tout objet, qui s'intègrerait bien dans l'esprit de la POO sans perdre pour autant son arrière-plan fonctionnel (d'où les objets fonctionnels). Ça me semble donc tout à fait défendable... après faut-il préférer l'une ou l'autre... ça dépendra beaucoup du programmeur, du projet, du côté « naturel » de telle ou telle approche, et aussi et surtout de la qualité de la version tout objet, parce que la barre est déjà assez haute étant donné que la lib standard d'OCaml est plutôt bien foutue !

    Reste à trouver le temps pour s'y mettre sérieusement, car il en faut beaucoup (surtout si on repart de zéro, ce qui, après réflexion, est la seule idée raisonnable). Quant à moi j'ai peur d'en manquer pour le moment.

    Cordialement,
    Cacophrène

  9. #9
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par Cacophrene Voir le message
    Reste à trouver le temps pour s'y mettre sérieusement
    En même temps, si tu veux trouver de la main d'oeuvre, je pense qu'il va falloir trouver un argument plus vendeur que "ça permet aux newbies de regarder le code"

  10. #10
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    InOcamlWeTrust : fais toi plaisir !
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # let cardinal, set = List.length, [];;
    val cardinal : 'a list -> int = <fun>
    val set : 'a list = []
    # let ($) x f = f x;;
    val ( $ ) : 'a -> ('a -> 'b) -> 'b = <fun>
    # set$cardinal;;
    - : int = 0
    # set$cardinal$succ;;
    - : int = 1
    InOcamlWeTrust parle d'extension des fonctionnalités, mais je me demande toujours dans quelle situation cela aide vraiment. Je ne crois pas à l'idée selon laquelle "oui il suffit d'hériter et pouf tu peux extendre comme tu veux"; attention, je ne dis pas que vous dites ça, mais on entend un peu les POOistes dire ça (quand ils ne sont pas occupé à dire "non il faut favoriser la composition plutôt que l'héritage, l'héritage c'est le mal").

    Ce que j'aimerais voir c'est des exemples concrets où les objets améliorent substantiellement une situation que peut rencontrer un programmeur OCaml, avec une discussion des caractéristiques de la POO qui entrent en jeu (protection de l'état interne, récursion ouverte, sous-typage, autre chose ?).

    Je sais que ça existe, je l'ai vu dans Camlp4 (même si je ne connais pas assez la POO pour pouvoir naturellement dire précisément ce qui était profitable dans ce cas), mais je ne sais pas si c'est très courant (c'est quand même une situation très particulière) et si ce serait le cas dans une lib équivalente en fonctionnalités à la lib standard actuelle.

    Tu as parlé de "patterns" pour Map/Set, pourrais-tu élaborer un peu ?

  11. #11
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Citation Envoyé par alex_pi
    En même temps, si tu veux trouver de la main d'oeuvre, je pense qu'il va falloir trouver un argument plus vendeur que "ça permet aux newbies de regarder le code"
    Si je voulais trouver de la main d'œuvre, je trouverais une tournure plus explicite pour le dire.

    Cordialement,
    Cacophrène

  12. #12
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    La gestion des erreurs est un cas flagrant où l'extension ferait des merveilles. Si on fait des erreurs une classe abstraite, ou une interface, dont on pourrait hériter, on pourrait définir des erreurs différentes dans tous les modules d'un projet, et les utiliser comme des valeurs appartenant toutes au même type de données.

    Concrètement, on pourrait penser à définir une classe Error avec quelques erreurs prédéfinies, qui seraient donc des valeurs différentes. En pseudo-code...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    Classe Error
      methode identifier
      methode to_string

    @identifier : utiliser le type polymorphe, car tous les type ne peuvent pas être définis à ce niveau. On peut penser aux valeurs prédéfinies et incluses de base dans la librairie telles `Invalid_argument, `Exit ou `Fatal. L'utilisateur peut, après héritage/implantation de l'interface, expliciter comme identifiant, par exemple dans un compilateur, `Syntax_error ou `Lexical_error.

    @to_string : méthode utile pour afficher des commentaires explicatifs du genre "')' expected on line 2, column 34" ou encore "Invalid argument", pour les erreurs plus simples. Cela laisse le choix à l'utilisateur de customiser son erreur et l'adapter à l'utilisation qui en est faite.

    On peut penser à l'exception générique Error of error, à laquelle est donc attachée une valeur de type error. Un exemple de fonction de récupération d'erreur à intégrer dans la librairie et de traitement dans du code utilisateur pourrait être le suivant...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    (* code librairie *)
    let get_error f exp =
      try (f exp) with
        | Error error -> error
     
    (* code utilisateur *)
    let _ =
      let error = get_error f exp in
      match error#identifier with
        | `Syntax_error -> print_endline error#to_string
        | `Exit -> exit 1
    Je suis toujours surpris de voir à quel point la gestion des erreurs est mal faite dans OCaml, surtout au niveau du compilateur. L'approche module impose de définir dans un module à part, dédié, toutes les erreurs possibles et imaginables. Tous les autres modules dépendent donc, potentiellement ou de fait, du même module Error. Clairement, l'approche objet et extension permet d'assouplir cette approche en supprimant définitivement ce genre de dépendances. De plus, les erreurs doivent être définies au niveau des modules, là où il est pertinent de les définir, et non à un niveau supérieur.

    En ce qui concerne les patrons de conception pour Set et Map, je pensais au patron visiteur. Une simple méthode à ajouter à la classe pour pouvoir visiter et parcourir la structure sans nécessairement avoir accès à sa décomposition et son implantation. Les types privés ne permettent pas de s'en sortir, puisque si l'implantation change, le code utilisateur utilisant le parcours doit changer aussi... et ceci casse le principe de compatibilité ascendante.

    Voilà pour quelques premières pistes de réflexion.

  13. #13
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Je suis toujours surpris de voir à quel point la gestion des erreurs est mal faite dans OCaml, surtout au niveau du compilateur. L'approche module impose de définir dans un module à part, dédié, toutes les erreurs possibles et imaginables. Tous les autres modules dépendent donc, potentiellement ou de fait, du même module Error.
    Comment cela ? J'utilise souvent la déclaration des exceptions dans les modules adaptés, et n'ai pas rencontré (ou alors pas compris) le problème dont tu parles.

    Pour la gestion des exceptions, tu as regardé Catch me if you can ? C'est un papier sur un méchanisme d'exceptions en OCaml, qui n'utilise pas d'objets mais effectivement des variantes polymorphes pour "casser la dépendance" (et des monades, ce que tu ne vas peut-être pas apprécier, mais on pourrait sans doute retirer cet aspect en sacrifiant l'apparition des exceptions dans le typage).

    Pour le visitor pattern, j'essaierai de me renseigner, mais de loin je ne vois pas ce que ça peut apporter de plus au problèmes de compatibilité que les usuels fold/iter (je vois mal en quoi l'approche POO permettrait de réveler moins de détails d'implémentation).

  14. #14
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Concernant la gestion des erreurs, ton papier est tout de même compliqué. Honnêtement, je pense que le système que je propose est beaucoup plus simple et raisonnablement extensible. Il n'est pas arrêté et il ne s'agit là que d'une piste de réflexion. Tout commentaire constructif est le bien venu.

    On cherche surtout ici à faire plus extensible, dans la directe philosophie objet, tout en rejettant le tout objet. Certes, on peut tout faire avec ce que l'on a déjà, mais tous les moyens ne sont pas nécessairement aussi clairs et simples d'utilisation.

    N'oublions pas non plus l'une des caractéristiques de la POO OCaml, le sous-typage sans héritage, l'inverse étant possible aussi mais fondamentalement inutile.

    Le patron visiteur est meilleur, plus souple, que le fold/iter car il permet de stopper la visite et la reprendre à son gré en fonction des éléments qui sont rencontrés. C'est en cela que l'idée est intéressante. La POO n'est qu'un moyen, commode, de parvenir à cette fin.

    L'exemple de code ci-dessus n'est qu'indicatif. Il n'est pas typable, mais permet d'éclaircir l'idée directrice.

  15. #15
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    Citation Envoyé par bluestorm
    Pour le visitor pattern, j'essaierai de me renseigner, mais de loin je ne vois pas ce que ça peut apporter de plus au problèmes de compatibilité que les usuels fold/iter (je vois mal en quoi l'approche POO permettrait de réveler moins de détails d'implémentation).
    Je te fais un résumé accéléré.
    Le fold est un itérateur interne, il cache l'implantation mais il cache aussi la définition du parcours.
    Le visiteur est un itérateur externe, il cache l'implantation mais il laisse la responsabilité du parcours à l'utilisateur qui doit (ou peut) lui-même faire progresser le curseur.
    Le visiteur peut être dirigé par le contenu alors que le fold est forcément dirigé par le conteneur.
    Les deux ont leur utilité bien distincte, d'ailleurs OCaml-Reins a les deux, sans utiliser de POO, parce que c'est évidemment plus confortable de passer une fonction que de sous-classer un machin qu'il faudra instancier pour amorcer la machine.

    Sur le même sujet il y a aussi les zippers de Gérard Huet :
    http://en.wikipedia.org/wiki/Zipper_(data_structure)

  16. #16
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Citation Envoyé par SpiceGuid Voir le message
    Le fold est un itérateur interne, il cache l'implantation mais il cache aussi la définition du parcours.
    Le visiteur est un itérateur externe, il cache l'implantation mais il laisse la responsabilité du parcours à l'utilisateur qui doit (ou peut) lui-même faire progresser le curseur.
    Le visiteur peut être dirigé par le contenu alors que le fold est forcément dirigé par le conteneur.
    Ok, je vois ce que tu veux dire. Peut-être que la formulation POO est utile pour ça, et effectivement les zippers sont aussi une bonne solution.

    Cependant, peut faire ça aussi avec des folds. Et, pour le challenge, voici un petit proof of concept.
    Définition du fold sur les arbres par point fixe :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    type ('a, 'b) node = ('b * 'a * 'b) option
     
    let map f : ('a, 'b) node -> ('a, 'c) node = function
    | None -> None
    | Some (b, a, b') -> Some (f b, a, f b')
     
    type 'a tree = Tree of ('a, 'a tree) node (* fixpoint *)
    let leaf = Tree None
    let node t x t' = Tree (Some (t, x, t'))
     
    let rec fold f (Tree tree) = f (map (fold f) tree)
     
    let test_tree = node (node leaf 1 leaf) 2 (node leaf 3 leaf)
    let length t = fold (function None -> 0 | Some (b, _, b') -> 1 + b + b') t
    let height t = fold (function None -> 0 | Some (b, _, b') -> 1 + max b b') t
    Utilisation du fold pour définir, en utilisant une dose suffisante de paresse, un fold "dirigeable" :
    Code : 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
    let left, right = true, false
     
    let direct t =
      let run = function
      | None -> (fun () -> ())
      | Some (b, (x, dir), b') ->
          fun () ->
            x ();
            (if dir = left then b else b') () in
      fold run t ()
     
    let test_tree () =
      let (!) str = ((fun () -> print_endline str), Random.bool ()) in
      node 
        (node
           (node leaf !"left left" leaf)
           !"left"
           (node leaf !"left right" leaf))
        !"center"
        (node
           (node leaf !"right left" leaf)
           !"right"
           (node leaf !"right right" leaf))
    J'ai testé et ça marche : les choix sont dynamiques, et seuls les noeuds "choisis" sont explorés.

    Cependant, même si seuls les noeuds "choisis" sont explorés, le fold parcours quand même toute la structure de l'arbre (en lazyfiant chaque noeud); pour avoir un fold qui attend les choix avant de parcourir, il faut modifier un peu la définition :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    let rec delay_fold f (Tree tree) =
      f (map (fun t -> fun () -> delay_fold f t) tree)
     
    let delayed_direct t =
      let run = function
      | None -> ()
      | Some (b, (x, dir), b') ->
          x ();
          (if dir = left then b else b') () in
      delay_fold run t
    Je pense qu'on peut généraliser ça, avec des continuations, à des passages de valeurs plus complexes (ici c'est plutôt un "iter" dirigé qu'autre chose).

    Cependant, ça reste un parcours "descendant" : on ne peut pas, comme avec des zippers, "remonter" dans l'arbre. Ça peut peut-être s'adapter pour cela, mais je n'ai pas essayé.

  17. #17
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Je viens de lire (en vitesse) le papier A Type-theoretic Reconstruction of the Visitor Pattern, et ils en arrivent essentiellement à la même conclusion : un visitor pattern, c'est un fold ("Internal visitors are essentially F-algebras").

    Il y a par contre au début du paper une remarque qui me semble tout à fait intéressante :
    Citation Envoyé par page 3
    The standard object-oriented implementation of binary trees is based around the Composite pattern. The datatype signature (sometimes called “element”) is represented as an interface and the constructor for each variant of the datatype becomes a class (sometimes called “concrete element”) which implements the interface. The interface includes method headers that specify the signatures of all operations on the data. This forces each constructor class to provide a method to handle the appropriate case of the operation.
    This approach permits new datatype variants to be added without modifying existing code, something that is not possible in ML. The disadvantage is that adding new operations is difficult as every existing class has to be amended. The Visitor pattern turns the situation around. It becomes easy to add new operations but difficult to add new variants.
    Ils semblent bien dire que Visitor, c'est la même chose que ce qu'on peut déjà faire facilement avec du pattern-matching en ML, mais que par contre Composite c'est différent. Je ne connais pas le pattern Composite, mais peut-être que c'est une voie qui permettrait de faire des choses vraiment différentes de ce qu'on a actuellement ?

  18. #18
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    Typiquement en POO, on veut à la fois pouvoir ajouter des variants et ajouter des opérations, et donc on colle un visiteur sur un composite. Le résultat c'est qu'on ne peut plus rien ajouter du tout. À ce stade les variants polymorphes deviennent inévitables.

    Je ne pense pas que IOCWT parle de fold au sens de F-algebra (style Yacc/Menhir), il parle de l'utilisation "aplatie" plus commune que sont les itérateurs (pattern Iterator) où on accumule que sur une séquence.
    À mon avis Iterator ne s'applique pas vraiment à un arbre binaire de recherche. Sinon on ne pourrait pas le remplacer par une table de hachage, ça invaliderait tous les parcours.
    OCaml-Reins le fait, à l'aide d'un zipper, mais j'avoue ne pas bien comprendre la motivation.

    Algorithmiquement parlant, je pense qu'on a beaucoup plus besoin d'itérations dirigées par le conteneur (y compris des versions qui ne parcourrent qu'un sous-ensemble défini soit par une contrainte sur les données soit par le résultat de la dernière opération sur le conteneur).
    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. Là c'est très spécialisé puisque le curseur doit posséder un accès en écriture.
    Cependant il y a sans doute d'autres applications qui ne necessitent qu'un accès en lecture, mais mon "manque cruel d'expérience" ne me permet pas de dire lesquelles pourraient éventuellement bénéficier d'une conception POO.


    Pour la remontée il n'y a que 3 solutions :
    1. avoir un pointeur parent
    2. OCaml-Reins mémorise une liste des noeuds traversés
    3. inversion des pointeurs: les pointeurs sont mutables, chaque fois qu'on descend par un pointeur on le fait pointer sur son noeud père plutôt que son noeud fils, chaque fois qu'on remonte par un pointeur on le fait pointer sur son noeud fils plutôt que son noeud père

    La dernière solution est la plus économe mais c'est la plus bloquante, on ne peut faire qu'un seul parcours à la fois et pendant ce parcours toutes les opérations doivent être suspendues pour cause d'inversion des pointeurs.

  19. #19
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    SpiceGuid a raison. Par fold j'entends le fold classique tel qu'on peut le trouver dans OCaml.

    Pour le parcours d'un arbre binaire, une simple pile suffit, comme si il s'agissait d'un parcours récursif infixé. Ce qui serait intéressant, ce serait d'implanter une pile intelligente permettant de revenir en arrière. Ce n'est absolument pas compliqué à implanter.

    Il existe donc une 4ème solution, je pense.

  20. #20
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    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)

Discussions similaires

  1. Réponses: 2
    Dernier message: 14/06/2008, 18h03
  2. [XSD] Mapper intelligemment un XSD avec des Objets Java
    Par PoteA_Tooz dans le forum Format d'échange (XML, JSON...)
    Réponses: 2
    Dernier message: 09/05/2008, 10h33
  3. [POO] Listing avec des objets
    Par estampille dans le forum Langage
    Réponses: 5
    Dernier message: 27/08/2007, 16h19
  4. Réponses: 1
    Dernier message: 05/06/2007, 17h14
  5. [C#]Travailler en synchrone avec des objets asynchrone
    Par mister3957 dans le forum Windows Forms
    Réponses: 3
    Dernier message: 19/10/2006, 18h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo