kantien a écrit 1131 commentaires

La publicité c'est du temps et des moyens = de l'argent.

Non, pas nécessairement.

Si tu contribue à un logiciel, c'est du temps = de l'argent.

Non, pas nécessairement.

Comme tu ne sembles toujours pas comprendre ce qu'est l'argent, je vais extraire la partie la plus importante sur le sujet du lien que j'ai donné plus haut (le texte est long, mais ça vaut le coup de le lire si tu veux bien comprendre de quoi tu parles lorsque tu parles d'argent).

Vous avez un écu. Que signifie-t-il en vos mains ? Il y est comme le témoin et la preuve que vous avez, à une époque quelconque, exécuté un travail, dont, au lieu de profiter, vous avez fait jouir la société, en la personne de votre client. Cet écu témoigne que vous avez rendu un service à la société, et, de plus, il en constate la valeur. Il témoigne, en outre, que vous n’avez pas encore retiré de la société un service réel équivalent, comme c’était votre droit. Pour vous mettre à même de l’exercer, quand et comme il vous plaira, la société, par les mains de votre client, vous a donné une reconnaissance, un titre, un bon de la République, un jeton, un écu enfin, qui ne diffère des titres fiduciaires qu’en ce qu’il porte sa valeur en lui-même, et si vous savez lire, avec les yeux de l’esprit, les inscriptions dont il est chargé, vous déchiffrerez distinctement ces mots : « Rendez au porteur un service équivalent à celui qu’il a rendu à la société, valeur reçue constatée, prouvée et mesurée par celle qui est en moi-même. »

Maintenant, vous me cédez votre écu. Ou c’est à titre gratuit, ou c’est à titre onéreux. Si vous me le donnez comme prix d’un service, voici ce qui en résulte : votre compte de satisfactions réelles avec la société se trouve réglé, balancé et fermé. Vous lui aviez rendu un service contre un écu, vous lui restituez maintenant l’écu contre un service ; partant quitte quant à vous. Pour moi je suis justement dans la position où vous étiez tout à l’heure. C’est moi qui maintenant suis en avance envers la société du service que je viens de lui rendre en votre personne. C’est moi qui deviens son créancier de la valeur du travail que je vous ai livré, et que je pouvais me consacrer à moi-même. C’est donc entre mes mains que doit passer le titre de cette créance, le témoin et la preuve de la dette sociale. Vous ne pouvez pas dire que je suis plus riche, car si j’ai à recevoir, c’est parce que j’ai donné. Vous ne pouvez pas dire surtout que la société est plus riche d’un écu, parce qu’un de ses membres a un écu de plus, puisqu’un autre l’a de moins.

Que si vous me cédez cet écu gratuitement, en ce cas, il est certain que j’en serai d’autant plus riche, mais vous en serez d’autant plus pauvre, et la fortune sociale, prise en masse, ne sera pas changée ; car cette fortune, je l’ai déjà dit, consiste en services réels, en satisfactions effectives, en choses utiles. Vous étiez créancier de la société, vous m’avez substitué à vos droits, et il importe peu à la société, qui est redevable d’un service, de le rendre à vous ou à moi. Elle s’acquitte en le rendant au porteur du titre.

Maudit argent !

L'argent n'apparaît que lors des échanges à titre onéreux et non à titre gracieux : autrement dit lorsqu'une personne dit à une autre « j'accepte de faire cela pour toi à la seule condition que tu fasses ceci pour moi ». On peut même dire que ce sont ces types de contrats qui créent l'argent : l'argent ce n'est que de la reconnaissance de dette. Il ne fait que représenter un troc suspendu, différé ou non finalisé.

Il y a une grande différence entre ces trois propositions :

• tous les échanges doivent être onéreux ;
• tous les échanges doivent être gracieux ;
• les échanges peuvent être onéreux ou gracieux.

Ce que l'on te dit c'est que l'on ne peut exiger d'autrui qu'il échange avec nous à titre gracieux, c'est-à-dire sans contrepartie.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

L'important ce n'est pas les deux numéros, mais qu'ils correspondaient à deux lignes distinctes. Chez Orange, j'ai toujours eu une ligne branchée directement sur la prise et l'autre était branchée sur la box. Si tu appelais le numéro en 09, les téléphones connectés directement à la prise ne sonnaient pas. Dans ton cas, les numéros en 01 et 09 correspondent-ils à deux lignes distinctes ou sont-ce deux alias pour la même ligne ?

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Merci, mais ça ne parait pas techniquement possible ?

Cela doit bien être possible, étant donné que c'est réel : cela fonctionne comme cela chez moi. ;-) Pour les détails techniques, je n'ai aucune idée de la manière dont cela fonctionne.

Avant j'avais deux lignes : une avec le préfixe en 01-05 (selon la région) et une autre en 09. Maintenant je n'ai plus que la première avec la même offre que celle que j'avais avec la seconde, ce qui est tout de même plus simple pour l'usager : il ne fallait pas se tromper de ligne lorsque l'on appelait.

Edit : je parle de l'offre ADSL.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Dit autrement, le libre est pour toi synonyme de gratuit

Sophisme?
Logiciel libre,oui complètement

Il y a un malentendu sur la notion de logiciel libre. Pour citer la référence FSF et RMS :

To understand the concept, you should think of “free” as in “free speech,” not as in “free beer”. We sometimes call it “libre software,” borrowing the French or Spanish word for “free” as in freedom, to show we do not mean the software is gratis.

Traduction : « Pour comprendre le concept, vous devriez penser à « free » comme dans « liberté d'expression », non comme dans « bière gratuite ». Nous l'appelons parfois « logiciel libre », empruntant le mot français ou espagnol pour « free » comme dans « liberté », pour monter que nous ne signifions pas par là que le logiciel est gratuit. »

Le texte original est essentiellement destiné aux anglophones, car en anglais le mot « free » peut signifier aussi bien « libre » que « gratuit », ambiguïté qui n'existe pourtant pas dans la langue française.

Pour rebondir sur la remarque « l'argent n'est que du travail figé » de Marotte, je rajouterai que le principe de base de l'économie marchande c'est le troc : je te donne ça si tu me donnes ça en échange ou je fais cela pour toi si tu fais cela pour moi, i.e. échange de biens et services. L'argent c'est juste un troc non finalisé, et permet de recevoir en échange du service rendu un service de la part d'une autre personne que celle à qui l'on a rendu service : c'est un bien qui améliore grandement les échanges librement consentis de services, là où sans cela le système de ton village africain ne pourrait nullement passer à l'échelle. ;)

Maudit argent !

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

En branchant son téléphone directement sur la prise téléphonique. L'offre d'appels illimités vers fixes et mobiles, qui auparavant était réservée au numéro lié à l'abonnement dual play, est dorénavant valable pour l'abonnement de la ligne fixe.

Chez les autres, je n'en sais rien, mais a priori je dirais que c'est spécifique à Orange : avant il y avait deux lignes, maintenant il n'y en a plus qu'une, et je ne crois pas que les autres opérateurs proposent une telle offre.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Il est là :

• processeur ARM double cœur à 1,6 GHz (Marvel Armada 385), avec 1 Gio de mémoire vice ;

Le routeur conserve jusqu'à un Gio de comportements que la morale réprouve pour ensuite faire son rapport à l'État tchèque : c'est du flicage en règle des citoyens ! :-P

Bon sinon j'ai cherché le troll également dans le journal à l'origine de la dépêche et n'ai rien trouvé. Comme dirait Christophe Maé : il est où le troll, il est où ? Il est où ?

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Chez Orange, il n'est plus nécessaire de passer par la box pour la téléphonie, donc je ne pense pas que cela puisse poser un quelconque problème avec l'Omnia.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

L'éthique c'est une norme totalement artificielle que chacun se crée, pour les gens qui poussent ça en avant c'est une forme de croyance qui sert à s'abstenir de réfléchir. On met des étiquettes sur ce qui est valide ou non au près de cette éthique et on piétine le reste. Affirmer que quelque chose est néfaste en expliquant pourquoi c'est bien, expliquer que cette même chose est néfaste parce qu'elle ne suit pas ton éthique ça peut être très grave.

Qu'est-ce que l'éthique si ce n'est la doctrine des devoirs ? Qu'est-ce que le bien si ce n'est un acte accompli en conformité avec le devoir, et le mal si ce n'est un acte contraire au devoir ?

Comment peut-on rejeter l'éthique comme doctrine à valeur universelle en en faisant une « norme totalement artificielle que chacun se crée » (sic), pour dans la foulée qualifier de bien une action et de très grave (comprendre : mal) une autre ? D'autant plus que les deux actions concernées consistent à porter un jugement de nature éthique sur quelque chose, et ne se distinguent que sur le fondement apparent d'un tel jugement ?

On arrive à peu de chose près à la situation suivante : il est admis de porter objectivement¹ un jugement éthique sur une chose en la qualifiant de néfaste, tout en admettant que tout jugement éthique est nécessairement subjectif. Il y a une incohérence flagrante dans les thèses soutenues.

Je peux à la rigueur admettre que l'on doute, voire rejette, le concept d'un système de normes universelles (i.e valant pour tout homme, en tout lieu et en tout temps) du devoir, mais par soucis de cohérence il vaudrait mieux bannir des expressions comme « il faut », « c'est bien », « très grave », ou des mots comme « néfaste » de son vocabulaire.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Je comprends mieux, au départ j'ai cru que ton commentaire n'en était pas un sur le cyclimse.

Et comme l'a dit le grand George : il ne faut pas faire d'amalgame entre la coquetterie et la classe ! :-P

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Comme le commentaire du dessus, je suis en retard par rapport à la date de publication du journal : je l'ai découvert via la dépêche sur les contenus primés de septembre.

Je voudrais juste signaler un article sur les monades en C++ étant donné que c'est ce qui est présenté en fin d'article pour gérer les std::optional via une option monad.

L'article compare les deux approches entre Haskell et C++, ce qui pourrait intéresser l'auteur du journal qui, je le sais, apprécie particulièrement le langage Haskell.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Petite précision pour illustrer qu'une fois le système des modular implicits définitivement mis au point et stabilisé, cela ne demandera pas de grands changements dans la base de code existante.

Pour rappel, on peut déjà écrire :

module type Num = sig
  type t
  val add: t -> t -> t
  val mul: t -> t -> t
end;;
module type Num = sig type t val add : t -> t -> t val mul : t -> t -> t end

let add (type a) (module M:Num with type t = a) i j = M.add i j;;
val add : (module Num with type t = 'a) -> 'a -> 'a -> 'a = <fun>

Avec les modules de première classe, on a déjà un polymorphisme élargi mais le module doit être donné explicitement. Les modules Int32 et Int64 correspondent à cette interface, même s'ils définissent plus de choses : il n'est pas nécessaire de se restreindre aux seuls éléments d'une interface pour la satisfaire, il suffit qu'ils y soient. D'où :

add (module Int32) 21l 21l;;
- : int32 = 42l

add (module Int64) 21L 21L;;
- : int64 = 42L

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Il n'y a pas de quoi pour mes réponses, on est là pour échanger et partager. Quand j'ai du temps, j'essaye d'être assez précis, d'illustrer le plus que je peux et de fournir des références si le lecteur veut prolonger sa réflexion de son côté.

Pour les différentes représentations, elles ont chacune leur module avec leurs opérateurs propres :

• module Int32 pour les entiers 32-bits signés;
• module Int64 pour les entiers 64-bits signés;
• module Num pour les opérations sur des rationnels en précision arbitraire.

(* exemple sur les Int32 *)
Int32.add 32l 64l;;
- : int32 = 96l

(* mais on peut le renommer localement + si on préfère *)
let (+) = Int32.add in 32l + 54l;;
- : int32 = 86l

(* idem avec les Int64 *)
Int64.add 32L 544L;;
- : int64 = 576L

let (+) = Int64.add in 32L + 544L;;
- : int64 = 576L

(* mais si on travaille dans un module où l'on ne manipule
 * que des Int32, il suffit de l'ouvrir et de renommer *)
open Int32;;

let (+) = add;;
val ( + ) : int32 -> int32 -> int32 = <fun>

127l + 233l;;
- : int32 = 360l

(* là comme j'étais dans la REPL j'ai perdu le + sur les int
 * il me suffit de le renommer et c'est good ! :-) *)
let (+) = Pervasives.(+);;
val ( + ) : int -> int -> int = <fun>

21 + 21;;
- : int = 42

Une fois qu'il y aura le polymorphisme ad hoc, on pourra avoir un opérateur + « unique » pour les différentes représentations. J'ai mis les guillemets car en réalité, cela correspond à un seul alias pour différents codes mais qui préserve tout de même l'essentiel : le typage fort du langage.

En attendant, on peut néanmoins déjà utiliser les principes du code avec les modules de première classe (et oui les modules aussi sont des citoyens de premières classe : c'est du lambda-calcul après tout ;-) mais avec paramètre explicite. Ils sont abordés au chapitre First-Class Modules (en) du livre Real World OCaml, et sont illustrés pour coder un query-handling framework.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Pour les cas que tu décris en Haskell, c'est ce qui manque à l'heure actuelle en OCaml : le polymorphisme ad hoc (en), qu'il faut distinguer du polymorphisme paramétrique (en). Le second est le polymorphisme que l'on trouve en OCaml : une fonction peut prendre en entrée un type quelconque sans que cela change son code dans sa forme (l'algorithme est identique) comme c'est le cas avec des fonctions sur les 'a list ou 'a array, par exemple.

Le polymorphisme ad hoc, lui, est ce qui permet entre autre de faire de la surcharge d'opérateur : une multiplicité de code partage le même alias, et le code adapté sera choisi en fonction du type des entrées. C'est par exemple pour cela qu'en Haskell il y a un seul opérateur d'addition + alors qu'en OCaml il y en un pour chaque type de données : + pour les int et +. pour les float. Ce sont les type classes qui permettent cela en Haskell, dispositif qui ne possède pas encore d'équivalent en OCaml mais il y a des personnes qui y travaillent.

Leo White, Frédéric Bour et Jeremy Yallop ont proposé les modular implicts qui s'insprirent entre autre des type classes de Haskell et des implicits de Scala. Dans leur article, ils comparent leur approche avec celles faites dans d'autres langages, comme les concepts pour le C++, section qui renvoie à un article collaboratif dont un des auteurs est Bjarne Stroustrup : Concepts: linguistic support for generic programming in C++. Comme je ne suis pas abonné à l'ACM, je n'ai pas pu lire l'article, et je me demande si ce sont bien les concept que les développeurs C++ attendent et dont parle la dépêche.

L'idée de base pour ajouter cette possibilité dans le langage OCaml est de passer par le système des modules du langage et des fonctions sur les modules ou foncteurs. Une approches lourde et qui crée beaucoup d'indirection à base de pointeurs, dans l'exemple de l'addition, est de passer par un type somme :

type num = I of int | F of float

let add i j = match i, j with
  |I i, I j -> I (i + j)
  |I i, F j -> F (float_of_int i +. j)
  |F i, I j -> F (i +. float_of_int j)
  |F i, F j -> F (i +. j)

add (I 1) (F 2.3);;
- : num = F 3.3

C'est extrêmement lourd dans l'écriture à l'usage. Leur idée est donc de passer par le système de modules et les modules de première classe. On commence par définir une signature pour les objets numériques :

module type Num = sig
  type t
  val add: t -> t -> t
  val mul: t -> t -> t
end

Puis, on définit deux fonctions¹add et mul qui prennent, en plus de leurs deux paramètres habituels, un module qui choisira l'implémentation adaptée.

let add (type a) (module M:Num with type t = a) (i:a) (j:a) = M.add i j;;
val add : (module Num with type t = 'a) -> 'a -> 'a -> 'a = <fun>

let mul (type a) (module M:Num with type t = a) (i:a) (j:a) = M.mul i j;;
val mul : (module Num with type t = 'a) -> 'a -> 'a -> 'a = <fun>

Il reste à implémenter deux modules de la bonne signature pour nos deux types de base int et float.

module Int_num : (Num with type t = int) = struct
  type t = int
  let add = (+)
  let mul = ( * )
end;;
module Int_num :
  sig type t = int val add : t -> t -> t val mul : t -> t -> t end

module Float_num : (Num with type t = float) = struct
  type t = float
  let add = (+.)
  let mul = ( *. )
end;;
module Float_num :
  sig type t = int val add : t -> t -> t val mul : t -> t -> t end

Pour l'usage cela se passe ainsi :

add (module Int_num) 1 2;;
- : int = 3

add (module Float_num) 1.3 2.5;;
- : float = 3.8

Leur proposition consiste à ajouter quelques modifications légères au langage de base de telle façon que le module en argument soit implicite et inféré automatiquement par le compilateur en fonction du type des autres paramètres. Ce qui permettrait d'avoir la syntaxe (qui n'est pas acceptée à l'heure actuelle) suivante :

(* ajout du mot clé `implicit` en tête de la définition du module *)
implicit module Int_num : Num = struct
  type t = int
  let add = (+)
  let mul = ( * )
end

implicit module Float_num : Num = struct
  type t = float
  let add = (+.)
  let mul = ( *. )
end

(* le paramètre implicite est mis entre accolades {}
 * et non entre parenthèse () *)
let add {M : Num} (i : M.t) (j : M.t) = M.add i j

add 1 2;;
- : int = 3

add 1.3 2.5;;
- : float = 3.8

Le compilateur se chargeant de regarder, dans le dictionnaire des modules implicites ayant la bonne signature, de trouver celui dont le type t correspond à celui des paramètres donnés à la fonction.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Exemple de conversion de type qui doit être explicite sous peine de voir le type checker te foutre une baffe — pour reprendre l'expression de barmic.

(* l'opérateur infixe +. exige deux paramètres de types float *)
(+.);;
- : float -> float -> float = <fun>

(* si on lui donne un int, il proteste ! *)
1 +. 2.3;;
Error: This expression has type int but an expression was expected of type float

(* il faut faire une conversion explicite *)
float_of_int 1 +. 2.3;;
- : float = 3.3

Ce qui ne semble pas être le cas du C++, si j'en crois ce commentaire de Guillaum (développeur C++ expérimenté) :

Aller, j'en ajoute (C++ est mon outil de travail 8h par jour depuis plus de 10 ans) en me focalisant sur les problèmes qui m’embêtent vraiment au quotidien et pour lesquels il n'y a pas de solution simple. J'essaye de rester objectif ;)

• Les casts implicites. Plus particulièrement le fait que les flottants, les ints, les bools, les enums, et j'en passe, c'est la même chose. Le downcast implicite d'une classe vers une autre. Je sais que c'est la philosophie du langage. Combien de fois je me suis fais manger par un int négatif convertit en unsigned…

[…]

C'est moi qui graisse. :-)

Et je le comprends : faire de la conversion de type sans l'accord explicite du développeur, ça ne devrait pas être permis ! C'est quoi ces compilateurs qui prennent des décisions qui affectent la sémantique du code dans le dos du programmeur ?

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Selon le site C++ référence, les lambda seraient apparues avec le C++11 et ne correspondent qu'à de vulgaires fonctions anonymes construisant une clôture : ils ne savent pas ce qu'est le lambda-calcul les concepteurs et développeurs C++ ?

Il n’est pas marqué ça sur le site. Il est marqué que les lambdas sont apparues dans le langage C++ depuis la version C++11. C’est pour ça que je dis que tu es de mauvaise foi, ou que tu ne sais pas lire.

Euh, c'est exactement ce que j'ai écrit ! :-O Enfin, j'ai sous entendu que l'apparition était dans le langage C++; je ne voulais pas entendre par là qu'ils prétendait que C++11 avait inventé les lambda. Je le reconnais, cela pouvait prêter à confusion (enfin, si l'on ne fait pas beaucoup d'effort). ;)

Qu'il y ait de la mauvaise foi dans mes propos précédents, c'est évident, je ne l'ai jamais nié, j'ai même annoncé la couleur. Par contre, je ne sais pas lequel de nous deux à des problèmes de compréhension sur ce qu'il lit.

Mais plus généralement, tu juges de la compétences des concepteurs d’un langage (ne me dis pas que tu poses seulement une question, la tournure est loin d’être innocente et tu le sais très bien) que tu ne connais pas sur une mauvaise lecture que tu fais (probablement volontairement) de documentations sur un site web qui n’est pas en lien avec le comité en charge de l’évolution du langage. Il y a des limites à ce qui acceptable comme troll :).

C'était clairement de la mauvaise foi en ce qui concerne les concepteurs du langage, je sais très bien qu'ils sont loin d'ignorer ce qu'est le lambda-calcul. Pour ce qui est des développeurs C++, cela dépend : DerekSagan ou toi ne semblent pas y connaître grand chose. ;-)

C’est un partage de responsabilité de la durée de vie. Ton idée de liste chaînée ou de tableaux persistants est (de ce que j’en ai compris) un peu à côté de la plaque de ce point de vue.

Alors tu n'as pas compris mon code, mais c'est peut être mon explication qui est défectueuse. En OCaml, en dehors des valeurs de type int et des constructeurs constants comme Nil on ne manipule que des pointeurs qui se comportent comme des smart pointer. Tous mes tableaux se partagent la responsabilité de la durée de vie du 'a array qui sert de mémoire partagée. Quand on a des types somme comme Cons of ... ce sont des smart pointer nommés en lecture seule, avec les ref ce sont des smart pointer en lecture-écriture. Les types somme cela sert à poser des étiquettes sur les branches du graphe des pointeurs, et ça s'implémente en C aussi : le runtime et le GC de OCaml sont codés en C.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Pour la version longue : voir ce commentaire que j'avais fait l'an dernier sur les principes de base du lambda-calcul typé. J'y comparais le typage de OCaml (qui est décidable, sauf sur quelques corner cases, d'où l'inférence de types) et celui de Coq qui lui ne l'est pas et donc le programmeur doit le dériver lui même explicitement, ce qui s'appelle faire une démonstration au sens mathématique du terme.

Pour la version courte : disons que le language des types c'est, grosso modo, celui de la logique propositionnelle du second ordre. C'est à dire que l'on a des variables propositionnelles : A, B, C..., l'implication logique A -> B (si A alors B), la conjonction A et B et la disjonction exclusive A ou B. L'implication : c'est le type des fonctions de A dans B; la conjonction : c'est les types produits, l'équivalent des struct du C; la disjonction : c'est les types sommes, les union du C mais en mieux.

On appelle ces deux genres de types, types sommes et types produits à cause de cette relation : A et (B ou C) <-> (A et B) ou (A et C). Ce qui donne une des définitions du concept d'algèbre de Boole au sens où l'entendent les mathématiciens : c'est un corps dans lequel tout élément est sont propre carré ((A et A) <-> A). L'algèbre a deux éléments {vrai, faux} étant la plus simple et la plus triviale de telles algèbres.

Par exemple, le type des listes : type 'a liste = Nil | Cons of 'a liste exprime une disjonction : c'est soit la constante propositionnelle Nil, soit une variable propositionnelle indexée par le type lui-même (ce qui fait que le type exprime une disjonction infinie, disjonction qui pour un type 'a donné est isomorphe à l'ensemble des entiers naturels 0 ou 1 ou 2 ou 3...). Pour les types produits, on peut prendre par exemple les points du plan : type point = {x:float; y:float}; c'est la donnée d'un int et d'un int, d'où la conjonction.

Ce qui fait qu'à l'arrivée, on tombe bien sur la logique des stoïciens.

Le principe d'application des fonctions, par exemple, c'est la régle de déduction logique dite du modus ponens : Si A alors B, or A, donc B. Règle que l'on écrit en logique propositionnelle : (A -> B) -> A -> B. À comparer avec le type inféré de la fonction suivante :

let apply f x = f x;;
val apply : ('a -> 'b) -> 'a -> 'b = <fun>

L'inférence de type relève de la preuve automatique, Coq c'est de la preuve assistée par ordinateur, et les principes du typage du lambda-calcul proviennent tous de la théorie de la démonstration. Et donc coder en fonctionnel, c'est faire une preuve : le principe même de la correspondance de Curry¹-Howard, ou correspondance preuve-programme. Le compilateur gueule, au niveau du typage, quand il considère qu'il y a un vice de forme dans la preuve.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

J'en déduis donc que selon toi un langage fonctionnel digne de ce nom doit être faiblement typé

Gné ??? Haskell ou OCaml sont fortement et statiquement typé. Voici la page des publications de Jacques Garrigue qui est le responsable principal du système de types du langage OCaml.

Par contre, je n'ai toujours pas vu comment tu illustrais le principe de la curryfication en C++ ni celui des fonctions comme citoyen de première classe. Au passage, Curry qui a donné le nom à ce principe était un mathématicien et logicien qui se prénommait… Haskell. ;-)

Bravo. Tu es donc quelqu'un de bien. Je suppose que c'était le message.

Que nenni ! Je pointais juste du doigt qu'un utilisateur de C++ (ce que je ne suis pas) posait une question sur l'utilité des shared_ptr et qu'aucun spécialiste de ce langage n'avait dénié lui répondre. C'est un peu dans le même ordre que ce commentaire de Benoît Sibaud :

Déjà six commentaires pour dire à quel point c'est un mauvais choix. Et pas un capable d'expliquer et/ou de proposer une solution ou d'être constructif ou donner des références. Pauvre communauté.

Pour ce passage, je ne comprends pas trop :

Et du coup grâce à ta constructivité(1) sur certains sujets tu a acheté le droit de faire preuve de mauvaise foi en écrivant, ceci, comme si cette définition du lambda était propre à C++, y compris OCaml (le seul langage digne de ce nom):

Selon le site C++ référence, les lambda seraient apparues avec le C++11 et ne correspondent qu'à de vulgaires fonctions anonymes construisant une clôture : ils ne savent pas ce qu'est le lambda-calcul les concepteurs et développeurs C++ ?

Pour ensuite répondre:

En fait dans les langages de programmation de ces dernières décennies le mot "lambda" correspond à une fonction anonyme, c'est loin d'être une spécificité de C++.
C'est gentil de me l'apprendre… mais je le savais déjà, hein. ;-)

Premièrement, je n'ai jamais, mais alors jamais, affirmé que OCaml était le seul langage digne de ce nom. Je dis juste qu'un langage qui ne fournit pas nativementt les concepts et principes de la programmation fonctionelle (dont l'archétype est le lambda-calcul) ne mérite pas d'être qualifié de langage fonctionnel. J'allais dire que j'avais passé l'âge de jouer à qui a la plus grosse en comparant les langages, mais à dire vrai je ne l'ai jamais eu : c'est ridicule, je n'en ai jamais vu l'intérêt.

Deuxièmement, oui il y a avait du troll et de la mauvaise foi dans mon message initial : mais c'était clairement affiché. ;-) Cela étant sur le site C++ référence à Lambda, on peut bien lire :

Lambda functions (since C++11)
Constructs a closure: an unnamed function object capable of capturing variables in scope.

Le concept est donc bien apparu avec le C++11 et représente des fonctions anonymes qui capturent des variables d'environnement en construisant une fermeture. Comme cette notion de fermeture est apparue avec le langage scheme en 1975, et que tu raillais Java qui avait mis plus de temps à les implémenter, je me suis permis de railler également le C++. Sur la page wikipédia sur les fermetures, tu pourras en particulier y lire :

En Haskell, grâce à la curryfication, toute fonction peut générer des fermetures lorsqu'on lui passe seulement une partie de ses arguments
[..]
En OCaml […] grâce à la curryfication, toute fonction peut générer une fermeture lorsqu'on lui passe seulement une partie de ses arguments.

c'est ce que j'ai fait avec mon exemple de plus, en faisant une application partielle :

let plus i j = i + j

let plus_2 = plus 2

Ici, on génère une fermeture en capturant 2 dans l'environnement d'évaluation de plus_2. Mais on peut aussi le faire anonymement :

fun i -> plus 2 i

Cela étant, je n'ai toujours pas d'exemples de curryfication et de leur usage pour générer des fermetures en C++.

Au passage, cette notion est empruntée à la logique formelle et au calcul des prédicats : c'est la notion de variable libre et de variable liée (et date donc de la fin du XIXème siècle). Dans un énoncé comme celui-ci : Pour tout entier n, n + i = n, la variable n est liée par le quantificateur universel (on peut changer son alias par j sans changer le sens de l'énoncé) tandis que la variable i est libre (elle représente un entier indeterminé). Pour pouvoir interpréter un tel énoncé, qui est en fait paramétré par un entier indéterminé i, il faut l'évaluer dans un environnement qui attribue une valeur à cette entier i : voilà d'où vient ce concept de fermeture. En l'occurrence pour cet énoncé, il ne sera vrai que pour la valeur i = 0 si on l'interprète dans son environnement naturel qui est celui de l'ensemble des entiers naturels. C'est là la base de la théorie des modèles qui n'est pas sans intérêt pour l'étude de la sémantique des langages de programmation.

accompagné de deux liens où tu réinventes l'eau chaude en découvrant manifestement ce qu'est un smart pointer, je dis ça pour donner de la profondeur à l'adjectif "pertinentes".

Je vois que tu es prompte à répondre, mais que tu n'as rien compris au code que j'ai écrit. Il ne s'agissait pas de réinventer l'eau chaude ou de découvrir ce qu'était un smart pointer mais :

• de montrer quel était l'équivalent de cette notion dans le langage OCaml;
• et d'en faire usage pour implémenter des tableaux persistants.

C'est la partie graissée qui est l'objectif principal du code : donner un exemple d'utilisation possible de ce concept sous la forme des shared_ptr (qui peut aussi existait sous la forme des unique_ptr), car telle était la question de freem. Le premier point était simplement là pour que le lecteur non familier avec les concepts de OCaml, mais familier avec ceux du C++, puisse comprendre le fonctionnement du code et traduise en C++.

Pour reprendre ma question trollesque du premier message :

ils ne savent pas ce qu'est le lambda-calcul les concepteurs et développeurs C++ ?

Dis : tu t'y connais un peu en programmation fonctionnelle et en théorie des langages ou tu veux juste troller ?

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

J'ai l'impression que l'on ne se comprend pas, ou que tu ne sais pas ce qu'est la programmation fonctionnelle.

Premièrement, pour la curryfication et les applications partielles, un langage fonctionnel digne de ce nom (donc basé sur le lambda-calcul) n'a pas besoin d'artifice particulier à la std::bind pour faire cela.

(* le principe de la curryfication se voit dans le type inféré :
 * c'est une fonction qui prend un int et renvoie une fonction
 * qui prend un int pour retourner un int *)
let plus i j = i + j;;
val plus : int -> int -> int = <fun>

(* donc si je lui donne un int, j'obtiens une fonction des
 * int vers les int *)
let plus_2 = plus 2;;
val plus_2 : int -> int = <fun>

plus_2 3;;
- : int = 5

(* la curryfication, ça se voit aussi comme cela : *)
let plus = fun i -> fun j -> i + j;;
val plus : int -> int -> int = <fun>

let plus_2 = plus 2;;
val plus_2 : int -> int = <fun>

plus_2 3;;
- : int = 5

Ensuite ton exemple avec macollection.iterer, je ne vois pas où il illustre le statut de citoyen de première classe pour les fonctions. De ce que je comprends, iterer est une méthode d'un objet itérable qui prend une fonction en paramètre : mais cela fait partie du type même de la méthode d'attendre un tel paramètre. De ce que je comprends, c'est équivalent à ça :

let (+=) x i = x := !x + i;;
val ( += ) : int ref -> int -> unit = <fun>

let sum a = fun x -> Array.iter ((+=) x) a;;
val sum : int array -> int ref -> unit = <fun>

let x = ref 3 in
sum [|1; 2; 3|] x; !x;;
- : int = 9

Moi ce que je disais c'est que le type des tableaux 'a array est polymorphe et contient des éléments de n'importe quel type 'a qui peut être un type de fonction, comme dans l'exemple :

let tab = Array.init 5 (fun i -> fun x -> x += i);;
val tab : (int ref -> unit) array = [|<fun>; <fun>; <fun>; <fun>; <fun>|]

Ici le type 'a est instancié à la valeur particulière int ref -> unit qui est celui des fonctions qui appliquent des effets de bords sur les pointeurs sur int. On peut en user ainsi :

let a = Array.init 5 (fun i -> ref 1);;
val a : int ref array =
  [|{contents = 1}; {contents = 1}; {contents = 1}; {contents = 1};{contents = 1}|]

Array.iteri (fun i f -> f a.(i)) tab;;
- : unit = ()

a;;
- : int ref array = 
  [|{contents = 1}; {contents = 2}; {contents = 3}; {contents = 4};{contents = 5}|]

Mais en fait selon le problème que tu cherches à résoudre ce n'est pas toujours le même modèle de programmation (objet, fonctionnel, procédural) le plus efficace et avoir plusieurs outils ne nuit pas.

Je n'ai jamais dit le contraire, d'ailleurs OCaml permet d'utiliser les paradigmes impératif, orienté objet et fonctionnel (mais vraiment du fonctionnel, pas l'ersatz que tu as illustré jusqu'à maintenant).

En attendant, quand je ne trolles pas pour répondre à du troll, je fournis des réponses plus pertinentes et adaptées aux autres commentaires. Comme quand dans cette dépêche, freem se demandait à quoi pouvait servir les shared_ptr et que je lui ai proposé de s'en servir pour implémenter des tableaux immuables. D'ailleurs, j'attends toujours des adeptes du C++ qu'ils m'éclairent sur la pertinence de mon exemple.

P.S: Bon, le lambda-calcul ça date de 1936, et on a du attendre C++11 pour en avoir un ersatz à lire tes exemples. Pour l'inférence de type et l'argorithme d'unification de Robinson qui en est la base, ça date de 1965. Il va falloir attendre combien de temps, pour celui-là ? L'algorithme en question est présenté sur le blog de la Société Informatique de France par Gilles Dowek.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

En fait dans les langages de programmation de ces dernières décennies le mot "lambda" correspond à une fonction anonyme, c'est loin d'être une spécificité de C++.

C'est gentil de me l'apprendre… mais je le savais déjà, hein. ;-)

Mon message répondait à barmic dans une volonté trollesque clairement affichée, et donc empreinte de mauvaise foi. Cela étant je restais dans le sujet du commentaire initial de ce fil puisque Le Gab y parlait de théorie des langages, et que mon commentaire aborde le sujet à plus d'un titre.

Je suis allé voir tes liens, et la syntaxe me semble bien lourde et difficile à appréhender pour un non initié. Pour comparer :

let tab = Array.init 5 (fun i -> 2 * i);;
val tab : int array = [|0; 2; 4; 6; 8|]

Array.iteri (fun i v -> Printf.printf "%i -> %i\n" i v) tab;;
0 -> 0
1 -> 2
2 -> 4                                                                          
3 -> 6
4 -> 8
- : unit = ()

(* ou mieux avec les applications partielles, merci Curry ! *)
let tab = Array.init 5 (( * ) 2);;
val tab : int array = [|0; 2; 4; 6; 8|]

Array.iteri (Printf.printf "%i -> %i\n") tab;;
0 -> 0
1 -> 2
2 -> 4                                                                          
3 -> 6
4 -> 8
- : unit = ()

Et quand on parle de fonctions comme citoyens de premier classe, on entend aussi par là qu'elles peuvent être utilisées dans un contexte polymorphe comme n'importe quel autre terme sans syntaxe particulière.

let tab = Array.init 5 (fun i -> ( * ) i);;
val tab : (int -> int) array = [|<fun>; <fun>; <fun>; <fun>; <fun>|]

Array.iteri (fun i f ->  Printf.printf "%i * 2 -> %i\n" i (f 2)) tab;;
0 * 2 -> 0
1 * 2 -> 2
2 * 2 -> 4
3 * 2 -> 6
4 * 2 -> 8
- : unit = ()

Mais je peux continuer le troll aussi : si tu veux essayer de me convaincre que la POO (oui ça ne touche pas que le C++ ;-) n'est pas une totale aberration logique et intellectuelle, il va falloir te lever de bonne heure. L'esprit humain est structurellement constitué selon des schèmes fonctionnels, et la POO est fondée sur une étrange analyse logique de la classification et du rapport de subordination des concepts en genres et espèces : à comparer avec les type classes de Haskell, par exemple, et la génération automatique de code dont Guillaum a donné des exemples dans ce commentaire.

Que l'entendement humain soit fonctionnel par essence, ce n'est pas une découverte qui date d'aujourd'hui : je pourrais te renvoyer à la théorie du schématisme dans la Critique de la Raison Pure de Kant qui date de… 1781. ;-)

Et au cas où la référence à un tel ouvrage, dans une question qui traite d'informatique et de théorie des langages, t'étonnerait, je m'auto-cite à partir d'un commentaire sur un autre journal :

Dans son ouvrage Les Métamorphoses du calcul, le mathématicien et informaticien Gilles Dowek revient sur l'évolution du calcul de l'antiquité jusqu'à nos jours et ce qui a donné naissance à l'informatique et l'ordinateur. Un des moments de cette histoire est une polémique lorsque Gottlob Frege voulut s'attaquer à la thèse centrale de l'ouvrage de Kant sus-cité, à savoir que tous les jugements mathématiques sont synthétiques a priori. Il a échoué, et pour cause, Kant avait raison et Gödel le prouva via son théorème d'incomplétude (ce qui équivaut au problème de l'arrêt en informatique). M. Dowek le reconnaît dans son livre, mais en appendice il cite malheureusement le cogito cartésien comme exemple de jugement synthétique a priori : c'est une erreur, ce jugement est analytique et non synthétique.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

BATMAN ?

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Ouais mais là il troll léger : on peut mieux faire, surtout sur sa dernière remarque avec les lambda, j'en ris encore ! :-D

Selon le site C++ référence, les lambda seraient apparues avec le C++11 et ne correspondent qu'à de vulgaires fonctions anonymes construisant une clôture : ils ne savent pas ce qu'est le lambda-calcul les concepteurs et développeurs C++ ? Elles sont où les applications partielles, la curryfication, les fonctions comme citoyens de premières classes ?

Reprenons l'histoire brève, incomplète et globalement erronée des langages de programmations :

1936 - Alan Turing invents every programming language that will ever be but is shanghaied by British Intelligence to be 007 before he can patent them.

1936 - Alonzo Church also invents every language that will ever be but does it better. His lambda calculus is ignored because it is insufficiently C-like. This criticism occurs in spite of the fact that C has not yet been invented.

1970 - Guy Steele and Gerald Sussman create Scheme. Their work leads to a series of "Lambda the Ultimate" papers culminating in "Lambda the Ultimate Kitchen Utensil." This paper becomes the basis for a long running, but ultimately unsuccessful run of late night infomercials. Lambdas are relegated to relative obscurity until Java makes them popular by not having them.

1973 - Robin Milner creates ML, a language based on the M&M type theory. ML begets SML which has a formally specified semantics. When asked for a formal semantics of the formal semantics Milner's head explodes. Other well known languages in the ML family include OCaml, F#, and Visual Basic.

1983 - Bjarne Stroustrup bolts everything he's ever heard of onto C to create C++. The resulting language is so complex that programs must be sent to the future to be compiled by the Skynet artificial intelligence. Build times suffer. Skynet's motives for performing the service remain unclear but spokespeople from the future say "there is nothing to be concerned about, baby," in an Austrian accented monotones. There is some speculation that Skynet is nothing more than a pretentious buffer overrun.

1990 - A committee formed by Simon Peyton-Jones, Paul Hudak, Philip Wadler, Ashton Kutcher, and People for the Ethical Treatment of Animals creates Haskell, a pure, non-strict, functional language. Haskell gets some resistance due to the complexity of using monads to control side effects. Wadler tries to appease critics by explaining that "a monad is a monoid in the category of endofunctors, what's the problem?"

1996 - James Gosling invents Java. Java is a relatively verbose, garbage collected, class based, statically typed, single dispatch, object oriented language with single implementation inheritance and multiple interface inheritance. Sun loudly heralds Java's novelty.

Là on commence à avoir du bon troll sur les querelles de chapelles entre langages. :-P

Et pour être honnête, Turing a développé son concept de machine pour trancher une polémique entre Gödel et Church sur la notion de fonctions calculables, et de son propre aveu il reconnaissait que la notation de Church était préférable à son propre concept pour traiter la notion.

Ensuite quand il s'est agit de typer le lambda-calcul, les théoriciens sont tombés sur la correspondance de Curry-Howard ou correspondance preuve-programme : un programme n'est que la preuve d'un théorème mathématique (voir la dernière page de l'article, par exemple). On pourra, également, regarder le code de ma fonction-lemme reroot qui mime un raisonnement par récurrence : on initialise avec les cas Arr puis pour le cas général on commence par utiliser l'hypothèse de récurrence sur pa'. ;-)

À l'arrivée, on se retrouve avec un langage qui date de 1936, un système de type (pour Haskell ou OCaml) qui est peu ou proue la logique propositionnelle du second ordre (i.e. la logique des stoïciens qui a plus de 2000 ans), et une analogie forte avec la plus ancienne de toutes les sciences : la mathématique. Pour ce qui est du recul et des possibilités d'un tel système, on peut difficilement tenter la comparaison.

Mais comme disait Platon : « nul ne peut entrer ici s'il n'est géomètre » (à moins que ce ne soit « s'il neigeait au mètre »); et son maître Socrate, dans La République, comparait l'humanité à un peuple d'esclaves passant leur temps à observer des ombres changeantes sur le mur d'une caverne, incapables qu'ils étaient de se libérer de leurs chaînes pour se retourner et contempler le monde immuable des Idées dont les ombres n'étaient qu'une pâle projection. :-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Tout simplement parce que le Dieu Mercure était représenté accompagné d'un coq, d'un bélier et d'une tortue; cette dernière faisant référence à l'invention de la lyre avec une carapace de tortue : d'où son choix pour les notes. Il reste à espérer qu'elles seront moins fausses que la voix d'Assurancetourix, sinon ça va barder !

Nous ne voyons pas d'autres explications. :-P

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Je viens de réaliser qu'il y a un bug dans le code de mon module sur les tableaux persistants : les codes des fonctions to_array et of_array permettent de manipuler la mémoire partagée en dehors des fonctions fournies par le module, et donc de casser l'invariant. :-/

Au passage ça me permet d'illustrer ce qui se passe sur cette mémoire partagée.

let shared = [|0; 1; 2; 3|];;

let tab = PA.of_array shared;;
val tab : int PA.t = <abstr>

let tab' = PA.set tab 0 4;;
val tab' : int PA.t = <abstr>

(* maintenant la zone partagée contient le tableau tab' *)
shared;;
- : int array = [|4; 1; 2; 3|]

(* dès qu'on opère sur tab, c'est lui qui se retrouve dans shared *)
PA.get tab 0;;
- : int = 0 
shared;;
- : int array = [|0; 1; 2; 3|]

(* par contre si on modifie shared, cela modifie les tableaux sensés être immuables *)
Array.set shared 1 6;;
- : unit = ()

PA.to_array tab;;
- : int array = [|0; 6; 2; 3|]

PA.to_array tab';;
- : int array = [|4; 6; 2; 3|]

La solution consiste à effectuer une copie des tableaux mutables pour conserver « l'encapsulation » et maintenir l'invariant.

let to_array pa = Array.copy (reroot pa)

let of_array a = ref (Arr (Array.copy a))

let shared = [|0; 1; 2; 3|];;
val shared : int array = [|0; 1; 2; 3|]

let tab = PA.of_array shared;;
val tab : int PA.t = <abstr>

(* si on modifie shared, le tableau tab reste bien inchangé *)
Array.set shared 0 5;;
- : unit = ()

PA.to_array tab;;
- : int array = [|0; 1; 2; 3|]

Au passage, cet exemple m'aura permis de montrer que l'on peut également faire de la gestion de mémoire bas niveau en OCaml : pointeur en lecture, pointeur en lecture-écriture, pointeur sur pointeur… bien que la libération de la mémoire soit automatisée et déléguée au runtime et au GC.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

J'ai réfléchi depuis l'autre jour sur cette notion de shared_ptr (qui n'est qu'un « fichu stupide pointeur », mais géré d'une manière particulière) et je te propose une autre utilisation possible : s'en servir, effectivement, comme une zone mémoire partagée où tous les possesseurs peuvent écrire dedans pour implémenter une structures de tableaux persistants. :-)

Le principe de l'encodage sera écrit en OCaml (ce sera plus simple pour moi, et je laisse la traduction en C++ à toi ou un autre). Avant cela, je vais revenir sur la notion de constructeurs de type dans ce langage pour que tu puisses faire le lien.

Quand j'ai présenté la définition du type des listes chaînées, je l'ai écrit ainsi :

type 'a liste =
  | Nil
  | Cons of 'a * 'a liste

Une expression de la forme Cons of ... est en réalité un « pointeur » en lecture seule sur la structure décrite ensuite. On pourrait l'illustrer ainsi :

type 'a ptr = Ptr of 'a;;
let read (Ptr x) = x;;

let i = Ptr 1;;
val i : int ptr = Ptr 1

read i;;
- : int = 1

Ceci dit, ce langage propose également la notion de zone mémoire accessible en lecture et écriture avec la notion de référence (mot clé ref).

let i = ref 1;;
val i : int ref = {contents = 1}

(* lecture avec l'opérateur préfixe !*)
!i;;
- : int = 1

(* écriture avec l'opérateur infixe := *)
i := 2;;
- : unit = () (* le type unit est équivalent à void *)

(* nouvelle lecture *)
!i;;
- : int = 2

Avant d'en venir au cœur de ce commentaire, il me faut présenter rapidement une autre structure représentant une zone mémoire accessible en lecture et écriture, commune à tous les langages impératifs : les tableaux (ou array).

let tab = [|0; 1; 2; 3|];;
val tab : int array = [|0; 1; 2; 3|]

Array.get tab 0;;
- : int = 0

Array.set tab 0 4;;
- : unit = ()

Array.get tab 0;;
- : int = 4

(* on peut faire la même chose avec cette notation *)
tab.(0) <- 5;;
- : unit = ()

tab.(0);;
- : int = 5

tab;;
- : int array = [|5; 1; 2; 3|]

Ces présentations préliminaires étant faites, venons en à l'objectif principal : coder une structure de tableaux persistants en recourant à une zone mémoire accessible en lecture-écriture commune à chacun d'eux. On pourrait faire cela en recopiant le tableau à chaque écriture puis en renvoyant la copie modifiée, mais ce serait vite coûteux en mémoire. L'idée pour obtenir la persistance à moindre coût va être celle qui est derrière les gestionnaires de versions (git, svn, mercurial…) : une écriture sera vu comme un patch et on conservera en mémoire la structure des diff.

On commence par définir le type polymorphe 'a t de nos tableaux :

type 'a t = 'a data ref
and 'a data = |Arr of 'a array 
              |Diff of int * 'a * 'a t

On a deux types mutuellement récursifs : le type 'a data qui pointe en lecture soit sur un tableau, soit sur un triplet correspondant à une écriture atomique sur un tableau, qui lui est un pointeur en lecture-écriture sur une structure 'a data.

Tout le code sur cette structure va reposer sur la fonction reroot qui modifie le graphe des pointeurs afin de toujours rentrer dans la structure par un pointeur en lecture sur un tableau 'a array. Autrement dit : on applique tous les patchs sur le tableau d'origine pour présenter le tableau résultant.

let rec reroot pa = match !pa with
  |Arr a -> a
  |Diff (i, v, pa') ->
     (* pa est vu comme un diff de pa', on commence par rerooter sur lui *)
     let a = reroot pa' in

     (* on applique le patch atomique *)
     let old = a.(i) in
     a.(i) <- v;
     pa := Arr a;

     (* maintenant c'est pa' qui est vu comme un diff de pa *)
     pa' := Diff (i, old, pa);

     (* on retourne le « véritable » tableau correspondant à pa *)
     a

À partir de cette fonction utilitaire, on peut définir les fonctions usuelles sur les tableaux à partir de celles sur les array.

let length pa = Array.length (reroot pa)

let get pa i = (reroot pa).(i)

let iter f pa = Array.iter f (reroot pa)

(* ici la fonction f que l'on itère prend deux paramètres : l'indice et la valeur *)
let iteri f pa = Array.iteri f (reroot pa)

Pour la fonction set, il faut prendre soin de rerooter sur le tableau que l'on veut patcher puis rajouter le diff dans la structure :

let set pa i v =
  let a = reroot pa in
  let old = a.(i) in
  a.(i) <- v;
  let res = ref (Arr a) in
  pa := Diff (i, old, res);
  res

On peut également, par exemple, rajouter des fonctions de conversions vers et à partir des tableaux non persistants ainsi qu'une fonction de copie qui oublie tout l'historique des patchs.

let to_array = reroot

let of_array a = ref (Arr a)

let copy pa = ref (Arr (Array.copy (reroot pa))

Maintenant, à la manière de la POO, on peut masquer une partie de la mécanique interne ainsi que le type implémentant une telle structure à l'utilisateur. On passe pour cela par le système de modules en n'exposant pas certains détails dans l'interface.

(* l'interface du module :
 *   - la définition du type n'est pas exposée
 *   - le type 'a data non plus
 *   - la fonction reroot reste privée *)

module type PA = sig
  type 'a t
  val init : int -> (int -> 'a) -> 'a t
  val length : 'a t -> int
  val get : 'a t -> int -> 'a
  val set : 'a t -> int -> 'a -> 'a t
  val iteri : (int -> 'a -> unit) -> 'a t -> unit
  val iter : ('a -> unit) -> 'a t -> unit
  val to_array : 'a t -> 'a array
  val of_array : 'a array -> 'a t
  val copy : 'a t -> 'at
end

(* le code complet du module *)

module Persistent_Array : PA = struct
  type 'a t = 'a data ref
  and 'a data = |Arr of 'a array 
                |Diff of int * 'a * 'a t

  let init n f = ref (Arr (Array.init n f))

  let rec reroot pa = match !pa with
    |Arr a -> a
    |Diff (i, v, pa') -> 
       let a = reroot pa' in
       let old = a.(i) in
       a.(i) <- v;
       pa := Arr a;
       pa' := Diff (i, old, pa);
       a

  let length pa = Array.length (reroot pa)

  let to_array = reroot

  let of_array a = ref (Arr a)

  let copy pa = ref (Arr (Array.copy (reroot pa))

  let get pa i = (reroot pa).(i)

  let iteri f pa = Array.iteri f (reroot pa)

  let iter f pa = Array.iter f (reroot pa)

  let set pa i v = 
    let a = reroot pa in
    let old = a.(i) in
    a.(i) <- v;
    let res = ref (Arr a) in
    pa := Diff (i, old, res);
    res
end

Illustration du module :

module PA = Persistent_Array;;

let tab = PA.of_array [|0; 1; 2; 3|];;
val tab : int PA.t = <abstr> (* la représentation est abstraite pour l'utilisateur *)

let tab' = PA.set tab 0 4;;
val tab' : int PA.t = <abstr>

(* le tableau est bien persistant *)
PA.to_array tab;;
- : int array = [|0; 1; 2; 3|]

PA.to_array tab';;
- : int array = [|4; 1; 2; 3|]

Il reste à noter, tout de même, que la fonction reroot qui réorganise la structure des pointeurs n'est pas thread safe (les merge peuvent créer des conflits ;-), donc la structure ne l'est pas non plus. On pourrait, par exemple, la rendre thread safe en rajoutant un verrou que l'on pose au début de reroot et qu'on libère une fois la réorganisation effectuée.

Voilà, à mon avis, une structure qu'il peut être intéressant d'implémenter avec des shared_ptr plutôt qu'avec de « simples » pointeurs — si j'en ai bien compris le principe. Et encore une fois : la persistance des données, c'est le bien ! :-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Il y a déjà beaucoup (trop) de services sur ton site.
Quel sont les deux services/produits qui rapportent le plus?

C'est l'éternel problème : à vouloir chasser trop de lièvres à la fois, on se fatigue et l'on n'en attrape aucun.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.