[Caml-list] Streams

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3297 bytes --]

    Bonjour,

Dans le cadre de la librairie de structures de données EDiSon
(Efficient Data Structures, Okasaki 2000) que je suis en train de
porter et d'adapter (pour l'instant 500k, prérelease prévue en
septembre), j'ai réalisé plusieurs types de listes à évaluation
retardée.

La première remarque est que j'ai eu beaucoup de mal à trouver de la
documentation à ce sujet :

- une implémentation très simple dans ML for the working programmer
(Paulson 1991, 1996)

- une implémentation par Pierre Weiss pour le problème des 8 dames sur
l'échiquer dans la librairie d'exemples d'Objective Caml

- l'implémentation de Daniel de Rauglaudre, cette dernière ayant
l'inconvénient de s'appuyer sur des fonctions non documentées de Caml,
mais il faut reconnaître que le code est parfaitement lisible et que
l'on devine à peu près ce qui se passe. C'est de surcroît la seule
implémentation à prendre en compte les fonctions génératrices et la
concaténation

- un article de Wadler (1997) sur l'implémentation de l'évaluation
retardée dans les langages stricts, qui a la particularité d'enfoncer
des portes ouvertes (ne considérant que les deux implémentations
traditionnelles) et de parler d'une implémentation particulièrement
efficace en SML/NJ qui serait en cours de développement, or la version
CVS de SML/NJ (110.41) ne comporte rien de tout cela, sinon le
traditionnel module Lazy

Enfin le rapport de recherche de Didier Remy et Daniel de
Rauglaudre (1992) n'est disponible que sous forme papier.


Voici donc mes questions :

- serait-il possible de documenter un peu le module obj ? Peut-être
est-ce une mauvaise idée, dans la mesure où cela pourrait permettre à
des utilisateurs non avertis d'écrire du code dangereux

j'ai écrit une version de listes à évaluation retardée qui simule le
fonctionnement des streams de Caml (fichier joint streamVI.ml)

type 
  'a stream = { mutable data : 'a streamCell } and
  'a streamCell =
    | Nil
    | Cons of 'a * 'a stream
    | Append of 'a stream * 'a stream
    | Delayed of (unit -> 'a stream)
    | Generator of int * (int -> int) * (int -> 'a)

L'inconvénient est que l'on perd le polymorphisme de la liste vide.
N'y a t-il aucun moyen de s'en sortir en utilisant du Caml
conventionnel ?

ensuite je voudrais abstraire le type int du constreur Generator afin
que l'utilisateur puisse indicer sa fonction génératrice par le type
de son choix :

   | Generator of 'k * (k' -> 'k) * ('k -> 'a)

seulement si je déclare un type ('k, 'a) streamCell alors on ne peut
plus utiliser des listes d'indexes de type différent alors qu'elles
sont "logiquement" compatibles puisque le type 'k ne sert qu'a
construire les nouvelles valeurs de type 'a

comment limiter "l'étendue" du type 'k au seul constructeur
[Generator] ?

- la forme spéciale lazy ressemble très fortement à la fonction lazy_
ci-dessous mis à part qu'elle n'évalue pas ses arguments

(* OCaml 3.04 *)
let lazy_ = function x -> ref (Lazy.Delayed (function () -> x))

Quels seraient les inconvénients (théoriques ? pratiques ?) d'une
forme spéciale [uneval_] qui serait équivalente à function () ->,
autrement dit

   uneval : 'a -> (unit -> 'a)
   uneval_ x <=> function () -> x  

        Diego Olivier

[-- Attachment #2: streams --]
[-- Type: APPLICATION/octet-stream, Size: 8911 bytes --]