kantien a écrit 1131 commentaires

Cela ne doit tout de même pas représenter une grande proportion de cette génération. Si l'on suit le principe de Poincaré selon lequel « on ne devient pas mathématicien, on naît mathématicien », ils devaient être de cela. Pour les autres, j'ai toujours entendu dire que ce fût un calvaire. N'ayant pas vécu moi même cette époque, je ne peux que me baser sur des ouïe dires, mais de ce que l'on m'en a dit je ne pense pas que cela m'aurait dérangé non plus comme approche.

Néanmoins, lorsque j'étais étudiant je faisais du soutien scolaire pour des collégiens et des lycéens afin de financer mes études, et pour nombre d'entre eux l'abstraction était une peine. Pour prendre un exemple, j'ai eu plus d'un élève de troisième qui comprenait difficilement que l'on puisse mettre x à la place de prix du kilo de bananes dans un système d'équations, et ils préféraient recopier l'expression complète à chaque ligne de calcul. Après, mon expérience m'a apprise que je ne suis pas un grand pédagogue, même si je m'en sors mieux sur des cours particuliers que des cours de groupes.

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

Merci pour l'exemple d'utilisation. Pour le côté tail-recursive cela vient de son côté CPS, ce qui permet sans doute d'éviter le stackoverflow sur de grands arbres (là où mon fold, qui ne l'est pas, risque d' « exploser ») ?

J'ai néanmoins une question sur la source de l'efficacité de la construction dans le cas où l'on ne parcours l'arbre qu'une seule fois. L'AST semble être représenté par des fermetures sur ses « constructeurs », ce qui en fait une sorte de construction paresseuse, et quand on l'évalue on le construit pour le consommer de concert, c'est cela ? Si je vois à peu près ce que l'on gagne en temps (ça évite de construire l'arbre d'abord, puis de le parcourir ensuite pour l'interpréter), quel est le coût en espace de toutes ces fermetures ?

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

Cette méthode utilise un encoding qui permet de se passer de la récursion.

Je n'avais pas lu le code d'Oleg. ;-)

Apparemment le higher-kinded polymorphisme serait un autre nom de "type constructor polymorphism". Dans notre cas, on peut parler simplement de higher-order polymorphisme, non ?

Oui, le higher-kinded polymophisme c'est du type constructor polymorphisme. Dans ce cas, c'est du higher-rank polymorphisme (ce que précise Oleg dans un de ses commentaires).

Je ne vois pas en quoi le répèter le rend plus vrai… Avec Obj.magic nous sommes même maintenant à une 4e technique ;-)

J'étais parti sur du higher-kinded, et j'admets que ce n'est pas la seule approche. Mais passer par Obj.magic quand on peut l'éviter, il faut aimer jouer avec le feu ;-)

Remarques qu'il semblerait que le language cible soit le language hôte (E-DSL). Aussi que nous construisons un AST directement, ou que nous passions par des constructeurs—sans (val op : expr -> expr -> expr) ou avec (val op : 'a. 'a expr -> 'a expr -> 'a algebre -> 'a) l'encoding illustré dans ce journal --,dans tous les cas nous avons des allocations (en tout cas en ocaml), je ne vois pas comment on pourrait s'en passer ??

Je me suis mal exprimé, j'avais bien vu que le langage cible était le langage hôte : je voulais parler du langage interprété (le DSL). Pour ce qui est de l'absence d'allocation, je faisais réfèrence au contenu du journal :

On constate facilement que la première méthode est au moins plus puissante que la seconde, mais que la seconde peut être beaucoup plus efficace (pas de construction de structure intermédiaire).

et comme tu le soulignes, avec l'encodage du journal les allocations sont juste « déplacées ».

Maintenant que tout ça a été re-dit, la question—que nous semblons tous aussi déjà avoir soulevée—c'est de montrer quels sont les avantages une fois qu'on a passé cette étape. Là je botte en touche…

Maintenant que j'ai lu le code d'Oleg à tête reposée, je comprends mieux pourquoi tu disais que c'était un évaluateur en style CPS. Par contre, je botte aussi en touche sur l'utilité pratique du système. Dans quels cas d'usage s'avère-t-il intéressant ? Qui gagne-ton, vis à vis des problèmes soulevés par Aluminium dans son journal (diversifier les interprétations), par rapport à la solution avec un fold générique sur la structure de l'AST?

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

L'utilité du fold est bien de pouvoir coder un principe général pour pouvoir faire varier les interprétations; ce qui me semblait être le problème d'Aluminium. Sinon pourquoi aurait-il parlé de catamorphisme, et donner l'exemple de réutilisation de son code pour varier l'interprétation afin de faire du pretty printing ? C'est cela la fonction fold.

Pour ce qui est de rajouter des opérateurs au type des expressions, c'est pour cela qu'il y a des variants polymorphes : code reuse through polymorphic variants.

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

Je n'ai toujours pas saisi la finalité de la méthode décrite dans le journal, il va falloir que je médite la vidéo et le code donné en lien à la fin pour mieux saisir.

J'ai l'impression qu'il veut faire de la quantification universelle sur du constructeur (forall a.) ce qui s'appelle du higher-kinded polymorphism et en OCaml on a tendance à utiliser le système des modules pour cela.

D'un autre côte, il semblerait que l'objectif soit aussi d'éviter de construire explicitement l'AST du langage cible pour éviter de l'allocation. Si l'on met de côté cette contrainte, on peut obtenir le résultat qu'il souhaite ainsi sans même passer par les modules :

type expr = Val of int | Op of expr * expr
let rec fold f g e =
  match e with
  | Val i -> f i
  | Op (e1,e2) -> g (fold f g e1) (fold f g e2)
;;
type expr = Val of int | Op of expr * expr
(* oh le joli type de fold ;-) *)
val fold : (int -> 'a) -> ('a -> 'a -> 'a) -> expr -> 'a = <fun>

let e = Op(Val 1, Op(Val 1, Val 2));;
let eval1 = fold (fun i -> i) ( + );;
let eval2 = fold (fun i -> i) ( - );;
let eval3 = fold string_of_int (fun a b -> Printf.sprintf "(%s+%s)" a b);;

(* 1 + (1+2) *)
eval1 e;;
- : int = 4

(* 1 - (1-2) *)
eval2 e;;
- : int = 2

eval3 e;;
- : string = "(1+(1+2))"

Le terme technique pour la fonction fold est bien celui d'un catamorphisme sur la structure d'AST du langage d'experession, que l'on spécialise selon différentes interprétations pour donner eval1, eval2 et eval3.

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

À ce niveau, cela se tient et il me semble que c'est toujours ainsi que cela se pratique (lorsque j'étais étudiant puis chargé de TD c'est ainsi que l'on faisait). Lors de mon premier cours de sup', notre professeur nous avait dit une chose du genre : « pour la première fois de votre vie, vous allez faire des mathématiques » (c'est volontairement provocateur, mais il y a du vrai dedans : cela traduit surtout un changement complet de méthode dans le traitement de cette science).

Cela étant, commencer cette approche dès le primaire et le secondaire ne pouvait qu'être voué à l'échec. Il ne faut pas avoir soi même d'enfant, ou avoir côtoyé des enfants pour imaginer qu'une telle méthode puisse fonctionner.

Les actes logiques de l'entendement qui produisent les concepts selon la forme sont :

• la comparaison c'est-à-dire la confrontation des représentations entre elles en relation avec l'unité de la conscience ;
• la réflexion c'est-à-dire la prise en considération de la manière dont diverses représentations peuvent être saisies dans une conscience ;
• enfin l'abstraction ou la séparation de tout ce en quoi pour le reste les représentations données se distinguent.

Remarques. 1) Pour faire des concepts à partir de représentations, il faut donc comparer, réfléchir et abstraire, car ces trois opérations logiques de l'entendement sont les conditions générales et essentielles de production de tout concept en général. — Par exemple, je vois un pin, un saule et un tilleul. En comparant tout d'abord ces objets entre eux, je remarque qu'ils diffèrent les uns des autres au point de vue du tronc, des branches, des feuilles, etc…; mais si ensuite je réfléchis uniquement à ce qu'ils ont de commun entre eux, le tronc, les branches et les feuilles-mêmes et si je fais abstraction de leur taille, de leur taille, etc… j'obtiens un concept d'arbre.

2) On n'emploie pas toujours correctement en logique le terme : abstraction. Nous ne devons pas dire : abstraire quelque chose (abstrahere aliquid), mais abstraire de quelque chose (abstrahere ab aliquo). Si par exemple dans un drap écarlate je pense uniquement au rouge, je fais abstraction du drap; si je fais en outre abstraction de ce dernier en mettant à penser l'écarlate comme une substance matérielle en général, je fais abstraction d'encore plus de déterminations, et mon concept est devenu par là encore plus abstrait. Car plus on écarte d'un concept de caractères distinctifs des choses, c'est-à-dire plus on en abstrait de déterminations, plus le concept est abstrait. C'est donc abstrayants (conceptus abstrahentes) qu'on devrait nommer les concepts abstraits, c'est-à-dire ceux dans lesquels d'avantage d'abstractions ont eu lieu. Ainsi par exemple, le concept de corps n'est pas à proprement parler un concept abstrait; car du corps lui-même je ne puis faire abstraction puisque dans ce cas je n'en aurais pas le concept. Mais il faut bien que je fasse abstraction de la taille, de la couleur, de la dureté ou de la fluidité, bref de tous les déterminations spéciales des corps particuliers — Le concept le plus abstrait est celui qui n'a rien de commun avec ce qui diffèrent de lui. C'est le concept de quelque chose; car le concept qui s'en distingue est celui de rien et il n'a donc rien de commun avec le quelque chose.

Kant, Logique.

Pour que le processus d'abstraction aboutisse, et lorsque l'on s'adresse à quelqu'un pour qu'il comprenne où l'on veut en venir, il faut déjà pouvoir comparer. Et cette comparaison, suivie de la réflexion, nécessite une grande familiarité avec les objets à partir desquels l'on cherche à produire un concept plus général les englobant tous par abstraction. Parler d'arbre à une personne qui n'en a jamais vu un seul, ni plusieurs différents pour les comparer, cela ne peut aboutir qu'à parler dans le vide et à de l'incompréhension.

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

La meilleure… c'est discutable, non ? Pourquoi pas avec des objets ou avec la méthode ci-dessus utilisée ?

J'ai l'impression que dans mon message du dessus je me suis trompé, et que tu fais référence à la méthode que tu as décrite dans ton message, c'est cela ? Il faut que j'y réfléchisse à tête reposée (pour le choix des objets, je ne les utilise jamais et je me suis toujours demandé ce que cela faisait dans le langage si ce n'est pour le défi théorique d'en comprendre le typage :-P).

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

Je ne vois pas comment faire autrement. Et ça méthode ne marche pas, il le dit lui même dans le journal et en redonne la raison dans ce commentaire. Sa solution fait une quantification existentielle sur le type, alors qu'il cherche une quantification universelle (higher-kinded polymorphism)-> les modules et les foncteurs; et il le dit lui même dans son journal :

En effet, une F-algèbres, pour les gens qui n'ont pas le temps de cliquer sur le lien, c'est un foncteur F (comme celui précédent), et une fonction de « calcul » de type F A -> A.

alors pourquoi ne pas utiliser le système des modules et des foncteurs du langage ?

J'ai regardé rapidement la vidéo, et je n'ai pas encore bien saisi l'intérêt du shallow embedding par rapport au deep embedding. D'après Alluminium cela évite l'allocation de l'AST mais on peut imaginer une implémentation en CPS qui produit et consomme l'AST de concert pour éviter des allocations. Je trouve l'approche en shallow étrange et verbeuse.

Pour l'overhead des frist class modules cela s'inline avec flambda, il me semble.

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

Les GADT ne me semblent pas adaptés, mais, qui sait ?

Je ne pense pas. La meilleure solution, en OCaml, pour faire de l'abstraction sur les types (higher-kinded polymorphism) reste de passer par le système des modules. C'est la solution retenue par Jeremy Yallop, Léo White et Frédéric Bour pour implémenter du polymorphisme ad-hoc (ou surchage d'opérateur, les type class en Haskell) en OCaml (voir la partie 2.4 pour la discussion sur le choix d'utiliser le système de module).

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

Il y a des perles magnifiques dans cette histoire brève, incomplète et globalement erronée ! :-)

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 - Niklaus Wirth creates Pascal, a procedural language. Critics immediately denounce Pascal because it uses "x := x + y" syntax instead of the more familiar C-like "x = x + y". This criticism happens in spite of the fact that C has not yet been invented.

1972 - […] 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.

Pour ceux qui ne sont pas allés lire le lien, ça vaut le coup pour se détendre et rire un bon coup.

Néanmoins, Aluminium95 y est allé un peut fort sur ce journal et je peux comprendre la réaction de wolowizard. Je ne sais pas si ce sont mes messages de samedi dans la dépêche sur la sortie du dernier compilateur GHC Haskell qui l'ont inspiré, mais ils étaient humoristiques et dénoncés le jargon employé par les adeptes de la programmation fonctionnelle. J'y reprenais le fameux « une monade est un monoïde dans la catégorie des endofoncteurs » que je comparais à : il ne faut pas dire « la terres est ronde » mais « une équipotentielle du champ de gravitation terrestre est homéomorphe à la sphère S_2 », tout en montrant sur un exemple élémentaire le fait que ma nièce de 8 ans avait « compris » les notions d'anamorphisme, catamorphisme et hylomorphisme en appliquant l'algorithme élémentaire de la multiplication (bien qu'elle ignore tout de ce jargon qu'elle serait bien incapable de comprendre, Scratch est bien plus amusant pour elle ;-).

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

Pourrais-tu développer l'analogie « anamorphosisme = lens » ?

C'est dans le contenu du premier lien de mon message (la cuisine gloubiboulga ;-) où le titre original de l'article est : Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Les anamoprhismes sont des générateurs de structures (le unfold dont l'opérateur contraire fold est un catamorphisme). Compter sur ces doigts, pour reprendre un de tes exemples, voilà le premier anamorphisme que rencontre un enfant ! ;-) C'est un générateur de nombre entier sous leur forme unaire ou entier de Peano (type peano = Zero | Succ of peano en OCaml) qui ressemble fortement au type des listes (on peut les voir comme une liste dont la valeur des éléments est constante Nil | Cons of unit * peano de type unit list, et le morphisme naturel entre les deux types calcule la longueur de la liste).

Ces trois types d'opérations sont fécondes. Dans ce journal, par exemple, l'auteur utilise les template C++ 14 pour implémenter un interpréteur d'algèbre linéaire sur des vecteurs, et plonger le langage cible dans le langage d'origine. Il utilise le pattern des visiteurs, là où en programmation fonctionnelle on passerait par un catamoprhisme (l'exemple est en F#). Mais pour obtenir le même fonctionnement que lui, ne pas allouer d'objets intermédiaires, on chercherait à produire l'hylomorphisme correspondant à la composition de l'anamorphisme qui réifie l'arbre d'évaluation et au catamorphisme qui le consomme :

A recursive function h : 'a -> 'b whose call-tree is isomorphic to a cons-list, i.e., a linear
recursive function, is called a hylomorphism. […]

A hylomorphism corresponds to the composition of an anamorphism that builds the call-tree as
an explicit data structure and a catamorphism that reduces this data object into the required
value.

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, p. 4-5

On passerait directement par la pile d'appel sans allouer d'intermédiaire. L'idée est assez proche de ce commentaire de gasche sur stackoverflow, reprise ici pour une version en Haskell.

En revanche, je ne suis pas certain qu'il soit pédagogique d'expliquer le concept général de bijection avant de savoir compter, tout comme les hylomorphismes peuvent rester des objets obscurs sans que cela ait un impact trop important sur le développement intellectuel :-p.

Nicolas Bourbaki s'inscrirait en faux contre de tels propos. Il a grandement contribué à la réforme de l'enseignement des mathématiques sous la forme des mathématiques modernes. Cette réforme fut sur le plan pédagogie, et cela de manière surprenante, un véritable échec ! :-P

Tu auras bien compris que mon propos empruntait la démarche inverse, en s'adressant à des adultes qui ont déjà une certaine maîtrise de l'abstraction pour leur montrer que ces concepts abstraits, au premier abord déroutant, ils les manipulaient depuis l'enfance sans les avoir nommé ainsi. ;-)

Pour la monadologie cela se discute. Cela étant, Saunders Mac Lane leur a donné ce nom en référence au concept de Leibniz.

Quand on raisonne à homéomorphisme près c'est pas super cool non ? Tu peux au moins demander que ce soit un Ck-difféormorphisme (avec k grand, par exemple 200000) pour éviter la possibilité d'avoir des trucs trop irréguliers …

Là-dessus, je partage le point de vue de Poincaré (qu'il a exposé dans La valeur de la Science, ou La Science et l'hypothèse, je ne sais plus lequel des deux) selon lequel ce n'est pas spécialement pertinent, en physique théorique, de distinguer continue et différentiable. Mais peu importe, l'essentiel est de faire référence à l'identité topologique avec la sphère S_2. Je vais fonder le comité des adeptes de la capillotétratomie et de la diptérosodomie, et rejoindre le groupe des xyloglottes. :-D

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

(lens mon amour…)
[…]Ces opérateurs font initialement peur, […]

D'un côté les adeptes de la programmation fonctionnelle pratiquent une drôle de cuisine : des bananes aux lentilles enveloppées dans des fils barbelés. Ça fait un peu gloubiboulga à la mode Casimir, ce n'est pas très appétissant ! :-P

Alors qu'au fond, même ma nièce de huit ans a compris le principe des anamorphismes (lens), catamorphismes (banana) et hylomorphismes (la composition des deux premiers). J'en veux pour preuve son cahier d'exercices sur les multiplications dont voici un extrait :

  142
*   4
-----
    8 <-   2 * 4
+ 160 <-  40 * 4
+ 400 <- 100 * 4
-----
= 568

Pour appliquer l'algorithme de multiplication que lui a enseigné son institutrice, elle commence par prendre l'entier 142 qu'elle transforme en une liste d'entiers : [2; 4; 1] (lentilles et anamorphismes, vous voilà !). Ensuite, elle applique la multiplication sur chacun des éléments de la liste (soit un map qui est un cas de catamorphismes ou bananas) à l'aide d'un tableau associatif, autrement connu sous le nom de tables de multiplication, pour obtenir la liste [8; 160; 400] . Puis, pour terminer, elle ajoute le tout (ce qui est toujours un banana) pour obtenir son résultat: 568. \o/

Bilan des courses : un anamorphisme puis deux catamorphismes pour obtenir un hylomorphisme, plus connu sous le nom de multiplication. :-P

Pour la notion de monade et de binding entre monades (>>=) c'est aussi simple : une monade est un monoïde dans la catégorie des endofoncteurs ! Cette formulation paraît absconse ? Pour les lecteurs plus familiers avec le paradigme de la programmation orientée objet, la lecture de l'article Dieu a-t-il programmé le monde en Java ? sur le blog de la Société Informatique de France leur permettra sans doute d'y voir plus clair. D'autant que je trouve que le concept de monade en programmation fonctionnelle, qui a été nommé ainsi en théorie des catégories en référence à la monadologie leibnizienne, capture mieux la signification qu'avait ce terme chez Leibniz que le concept d'encapsulation en POO. Et puis, on peut aussi faire des monades en C++.

C'était mon message a teneur humoristique du samedi midi. Je milite également pour que l'on soit plus rigoureux dans l'expression de certaine proposition, et que l'on ne dise plus : « la terre est ronde », mais plutôt : « d'un certain point vue, une équipotentielle du champ de gravitation terrestre est homéomorphe à la sphère S_2 ». :-D

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

Pour le client lambda, un cozy hebergé sur les serveurs du FAI me semble plus adapté, de même qu'à l'heure actuelle nombre d'abonnés ont un mail chez leur FAI, et certains des pages persos. Quel gain, pour l'utilisateur, à mettre cela sur sa box ? On perd en bande passante et en disponibilité, sans parler de la récupération des données en cas de remplacement de box. Une personne qui a un mail en @orange.fr ou @free.fr a-t-elle son serveur mails sur sa box ?

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

et non, je n'irai pas exhumer des preuves, ça fait longtemps que je n'en ai plus rien à foutre

Il n'y a pas besoin de faire de l'exhumation : les argumentaires se sont zombifiés ! :-P

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

Il y a un outillage autour d'Ocaml pour mesurer ce genre de choses ?

Apparemment c'est encore léger et ce n'en est qu'au début, il y a des efforts à faire de ce côté (c'est apparu avec le nouveau compilateur 4.03 et les efforts de Damien Doligez pour réduire le worst-case latency).

Il y a un message (de gasche ;-) sur la mailing list : Measuring GC latencies for OCaml program dans lequel il renvoie à son article de blog plus complet Measuring GC latencies in Haskell, OCaml, Racket en réaction au billet pointé par GuieA_7 sur les problèmes de latence du GC de Haskell.

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

Dans ce cas, ce n'est peut être pas totalement hors de portée de OCaml non plus. Dans cette direction, outre sa date de sortie ainsi que le premier exemple qui peut engendrer un stack overflow si on ne fait pas attention et n'est pas très optimisé, il y a cet article qui donne des pistes de réflexions.

As you may know, there is a subset of Javascript that compiles efficiently to assembly used as backend of various compilers including a C compiler like emscripten. We’d like to present you in the same spirit how never to allocate in OCaml. […]

Now that we can manage almost any control flow without allocating, we need also to manipulate some values. That’s the point where we simply suggest to use the same approach as ASM.js: allocate a single large bigarray (this is some kind of malloc), consider integers as pointers and you can do anything. We won’t go into too much details here as this would require another post for that topic.

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

Ce qui est marrant c'est ta solution (en tout cas pour moi).

N'étant pas développeur, ce n'est peut être pas très conventionnel ce que j'ai fait : mais ça marche ! :-P
Disons que je me suis adapté au contrainte du test, normalement on évite de faire autant d'allocation dans du code réel. Selon le cas pratique qui amène ce genre de calcul, je dirais même que l'on peut totalement se passer d'allocation. C'est du code qui pourrait ressembler à un interpréteur d'un langage algébrique très très mal optimisé. En pratique, on ferai plutôt comme dans ce journal avec une solution en C++ (comparer le premier commentaire du journal avec le code de ma fonction worker ;-).

En OCaml que ce soit avec du bytecode ou du code natif, on peut aussi gérer le fonctionnement du GC par des variables d'environnement : voir la doc à la variable OCAMLRUNPARAM (c'est ce que j'ai fait au départ avant de le mettre en dur dans le code).

D'ailleurs comment se passe une redéfinition plus petite de la minor heap en Ocaml ? Il fait un stop the world et envoie tout ce qu'il faut dans la major heap ?

Une redéfinition de la taille de la minor heap entraîne une collection mineur : il nettoie, envoie ce qui est encore en vie dans la major heap, et redimensionne. Documentation du module GC.

En fait j'ai opté pour cette solution parce que l'algorithme du test consiste à allouer un arbre binaire parfait de profondeur d (la fonction make) puis à faire un checksum dessus (la fonction check) et répéter cela sur de nombreux arbres (le paramètre iter). Alors j'ai adapté la taille de la minor heap (le memory pool le plus efficace) pour qu'elle puisse contenir deux arbres les plus profonds qu'il y aura à allouer. :-)

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

Alors quelques précisions: […]

C'est globalement ce que j'en avais compris des deux articles du membre de l'équipe chargée du compilateur. L'idée étant de pouvoir rajouter un smart pointer Gc<T> dont l'intention serait similaire à Rc<T>. Si la gestion automatique est basée sur du comptage de références, je comprends pourquoi la politique de gestion est drastique via le borrow checker (comme éviter des cycles dans le graphe des pointeurs qui sont gérés par des éphémérons dans le cas du GC d'OCaml).

La différence peut être mince, comme tu le soulignes avec les unikernels, mais je dirais qu'un langage système permet de maîtriser suffisamment parfaitement le comportement du code pour pouvoir écrire du code temps-réel (au sens temps réel dur, pas au sens globalement performant).

Mais dans ce cas ne faut-il pas une gestion totalement manuelle de la mémoire pour faire ce genre de chose ? Un langage tel que Rust peut-il s'attaquer à ce genre de problématique avec son mode de gestion automatique ?

Mais justement le lien que j'ai donné explique bien que Haskell va donner de très bon débit, mais va avoir des problèmes de latences ; ton benchmarck au final est équivalent à tester un débit moyen, mais ne va pas du tout tester les problèmes de latences, parce que 1) c'est pénible à tester 2) ce n'est pas ton problème.

Effectivement mon benchmark ne montre que le débit moyen, j'utilise time, mais parce que n'étant pas programmeur je ne connais pas les outils pour faire de la mesure de latence. En réalité, la modification que j'ai apporté au code OCaml de départ est plus un sketch of proof pour régler des problèmes de latence liés au GC. Ce qui fait que je suis passé de 25 s à 5.5 s est que j'ai fait disparaître une action du GC qui est responsable de la latence observée dans l'article que tu as cité sur le GC de Haskell : un parcours de la major heap.

Le tas est composé de deux memory pool : une minor heap et une major heap. La première sert pour les objets à courte durée de vie et est très efficace pour ce qui concerne les temps d'allocation et de désallocation mémoire. Lorsqu'elle est pleine le GC nettoie et transfert les structures encore en vie vers la major heap, puis à chaque fois qu'il fait cela, il nettoie par tranche cette major heap (de manière incrémentale) : c'est ce processus en mode stop the world qui prend plus du temps et génère de la latence. Dans mon code, j'ai adapté la gestion de la mémoire pour ne pas y avoir recours. Cela se passe en trois temps :

(* le memory pool de la minor heap est définie avec une taille
 * suffisante pour les besoins du calcul : un gros malloc une
 * bonne fois pour toute *)
let () = set_minor_heap (8 lsl max_depth)

(* c'est la partie proprement calculatoire du code *)
let worker (niter, d) =
  let c = ref 0 in
  for i = 1 to niter do
    (* je nettoie la minor heap pour éviter des transferts
     * vers la major heap *)
    Gc.minor();
    c := !c + check(make  i d) + check(make (-i) d)
  done;
  !c

(* le bout de code qui enchaîne les calculs
 * ne subit plus de latence *)
compute ~worker ~master tasks;

Sans cela j'avais un grand nombre de major collection, qui sont responsables des latences observées dans le fonctionnement du GC, là où maintenant je n'en ai plus aucune. ;-)

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

Je vois un peu mieux le principe du borrow checker, je regarderai peu être plus en détail la façon dont Rust gère les références. Cela étant, au début de Rust il y avait un GC qu'ils ont abandonné, mais l'idée de remettre de la gestion automatique est toujours présente, cela semble être néanmoins compliqué. Il y a deux articles sur le sujet sur le blog d'un des membres de l'équipe du compilateur :

• GC and Rust Part 1: Specifying the Problem
• GC and Rust Part 2: The Roots of the Problem

Sinon quelle différence fais-tu entre un langage qui peut faire de la programmation système et un langage système ? Il y a des personnes qui écrivent des noyaux, sous la forme d'unikernel, en OCaml :

MirageOS is a library operating system that constructs unikernels for secure, high-performance network applications across a variety of cloud computing and mobile platforms. Code can be developed on a normal OS such as Linux or MacOS X, and then compiled into a fully-standalone, specialised unikernel that runs under the Xen hypervisor.

MirageOs

Il y a bien des problèmes de latence liés au GC qui peuvent apparaître (contrairement à la gestion totalement manuelle du C par exemple) mais cela se gère aussi en adaptant son fonctionnement à l'application. Je ne connais pas le fonctionnement du GC de Haskell (mais d'après l'article c'est similaire à celui de OCaml), mais pour celui de OCaml ce chapitre de Real World OCaml en détail bien le fonctionnement.

Le premier commentaire de l'article que tu cites renvoie sur un benchmark (dont je n'ai pas estimé la pertinence) qui mesure la latence d'un serveur web qui stocke une hashtable (pour le serveur web en OCaml, il utilise d'ailleurs une bibliothèque développée par l'équipe de MirageOS) :

J'ai eu une polémique récemment sur le coup de la latence du GC de OCaml en rapport à ce benchmark du benchmarkgame de chez Debian. J'avais mal estimé le rôle du GC dans les mauvais résultats : comme pour le cas de ton article, il y a des objets trop gros qui restent vivants trop longtemps. En adaptant la taille de la minor heap on obtient de meilleurs résultats (j'utilise aussi la bibliothèque functory, qui fait une sorte de MapReduce, pour le parallélisme ) :

open Functory.Cores
let () = set_number_of_cores 4

let set_minor_heap size = Gc.set {(Gc.get()) with Gc.minor_heap_size=size}

type tree = Empty | Node of tree * int * tree

let rec make i d =
  if d = 0 then Node(Empty, i, Empty)
  else let i2 = 2 * i and d = d - 1 in Node(make (i2 - 1) d, i, make i2 d)

let rec check = function Empty -> 0 | Node(l, i, r) -> i + check l - check r

let min_depth = 4
let max_depth = 
  let n = try int_of_string(Array.get Sys.argv 1) with _ -> 10 in
  max (min_depth + 2) n

(*
* c'est ici que j'adapte la taille de la minor heap 
* ce qui évite de nombreuse copie entre la minor et la major heap
* et réduit grandement la latence due au GC 
*)
let () = set_minor_heap (8 lsl max_depth)

let stretch_depth = max_depth + 1

let () =
  let c = check (make 0 stretch_depth) in
  Printf.printf "stretch tree of depth %i\t check: %i\n" stretch_depth c

let long_lived_tree = make 0 max_depth

let worker (niter, d) =
  let c = ref 0 in
  for i = 1 to niter do 
    Gc.minor();
    c := !c + check(make  i d) + check(make (-i) d)
  done;
  !c

let () =
  flush stdout;
  let tasks =
    let l = ref [] in
    for i = ((max_depth - min_depth) / 2 + 1) - 1 downto 0 do
      let d = min_depth + i * 2 in
      let niter = 1 lsl (max_depth - d + min_depth) in
      l := ((niter, d), None) :: !l
    done;
    !l
  in
  let res = ref [] in
  let master ((niter, d), _) c =
    res := (2*niter, d, c) :: !res;
    []
  in
  (* il n'y a plus de major collection pendant ce calcul *)
  compute ~worker ~master tasks;
  let log (niter, d, c) =
    let s = Printf.sprintf "%i\t trees of depth %i\t check: %i" niter d c in
    print_endline s;
  in
  List.iter log (List.sort (fun (_, d, _) (_, d', _) -> compare d d') !res);
  Printf.printf "long lived tree of depth %i\t check: %i\n"
    max_depth (check long_lived_tree)

avec ce code, sur ma machine à 4 cœurs, j'obtiens comme résultat standard avec un time btree 20 :

real    0m5.411s
user    0m16.320s
sys     0m0.492s

là où avec le code C le plus performant je suis dans cet ordre de grandeur :

real    0m3.721s
user    0m13.144s
sys     0m0.204s

c'est pas si mal et bien mieux que le 25.82 s du meilleur code OCaml du test. D'autant que, n'étant pas moi même programmeur (je suis mathématicien et logicien, pas informaticien), il est fort probable qu'un spécialiste du langage puisse encore améliorer cela.

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

Oui c'est ce que je disais dans mon commentaire avec "si les objets contenus sont mutable ils pourraient être modifiés de l'extérieur malgré ça"

J'avais bien compris, mais je préférais illustrer par un exemple pour que ceux qui se demandent comment éviter ces effets de bords puissent avoir une illustration du problème. Résultat cela m'a amené à regarder s'il n'y avait pas une fonction de copie profonde d'une structure en Python, et voilà : copy.deepcopy() :-)

>>> class Test:
...     def __init__(self, items=()):
...       from copy import deepcopy
...       self.items = list(deepcopy(items))
... 
>>> l = [1, [2, 3], 4]
>>> a = Test(l)
>>> l.append(5)
>>> l[1].append(6)
>>> l
[1, [2, 3, 6], 4, 5]
>>> a.items
[1, [2, 3], 4]

La décorrélation est totale ! \o/

Et le système d'emprunt de références va tout de même garantir qu'un seul endroit du code a la responsabilité de modification à un instant T.

C'est un système de lock pour les problèmes d'accès concurrents ? Ou si plusieurs structures se partagent une référence, seule une peut la modifier jusqu'à ce qu'elle soit désallouée et une autre en prend le contrôle, et ainsi de suite ? (j'essaye de traduire les notions de propriétaire/temps de vie).

le système de typage est moins puissant qu'en Haskell/OCaml

Il y a des travaux pour améliorer encore celui d'OCaml pour pouvoir faire du polymorphisme ad-hoc et de la surcharge d'opérateur en utilisant son système de module et les foncteurs. Et on peut aussi manipuler des références (mais là c'est sans garde-fou) et faire de la programmation système en OCaml (la seule limite actuelle, c'est le GC qui ne gère pas les accès concurrents sur la major heap ce qui pose problème pour le parallélisme, cf multicore OCaml).

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

C'est même plus propre par rapport à ma solution et au problème initial : si on passe une liste dans l'appel au constructeur, on peut se retrouver au même désagrément sur les effets de bords.

>>> class Test:
...    def __init__(self, items=None):
...      self.items = [] if items is None else items
...    
...    def add(self, item):
...      self.items.append(item)
... 
>>> l = [1, 2, 3]
>>> a = Test(l)
>>> l.append(4)
>>> a.items
[1, 2, 3, 4]

Là où avec ta solution, en plus d'accepter plus de type comme paramètre du constructeur, l'attribut est un peu mieux décorrélé (mais pas totalement) de l'argument.

>>> class Test:
...     def __init__(self, items=()):
...         self.items = list(items)
... 
>>> l = [1, [2, 3], 4]
>>> a = Test(l)
>>> l.append(5)
>>> a.items
[1, [2, 3], 4]
>>> l[1].append(6)
>>> a.items
[1, [2, 3, 6], 4]
>>>

Je ne sais pas ce que sont les notions de propriétaires/temps de vie en Rust, mais je dirais pour ma part : comme quoi le fonctionnel pur (ou l'observationnellement immuable) ça a son intérêt ! :-)

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

Heu, le gestionnaire d'openSUSE, construit autour de libsolv?

Je ne connaissais pas. Quel est l'ordre de grandeur du temps de résolution ?

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

Je suis entrain de me former à Python. Comment expliquer ce comportement, et comment faudrait-il modifier le code pour avoir un bon fonctionnement ?

Le comportement observé est du au fait que les arguments optionnels ne sont évalués qu'une seule fois lors de la définition de la fonction. S'ils sont mutables, et qu'on les affecte comme attribut aux objets de la classe, ils ne sont alors pas propre aux objets mais deviennent des variables de classe. Pour éviter cela, si ce n'est pas ce que l'on souhaite, il faut utiliser la solution de flan et utiliser la valeur None comme paramètre par défaut, puis tester dessus pour avoir des listes vides différentes pour chaque objet de la classe.

>>> class Test:
...   def __init__(self, items=None):
...     self.items = [] if items is None else items
...   
...   def add(self, item):
...     self.items.append(item)
... 
>>> a = Test()
>>> a.add('foo')
>>> b = Test()
>>> b.add('bar')
>>> a.items
['foo']
>>> b.items
['bar']

En OCaml, par exemple, les arguments optionnels sont implicitement représentés par le type polymorphe 'a option :

let foo ?x () =
  match x with
  | None -> print_endline "pas d'argument optionnel"
  | Some i -> Printf.printf "l'entier %i\n" i
;;
val foo : ?x:int -> unit -> unit = <fun>

foo ~x:2 ();;
l'entier 2
- : unit = ()

foo ();;
pas d'argument optionnel
- : unit = ()

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

C'est ce qui m'a séduit dans Haskell.

Je peux comprendre, les effets de bords et les valeurs mutables ça peut avoir des comportements surprenants :

>>> class Test:
...   def __init__(self, items=[]):
...     self.items = items
...   
...   def add(self, item):
...     self.items.append(item)
... 
>>> a = Test()
>>> a.add("foo")
>>> b = Test()
>>> b.add("bar")
>>> a.items
['foo', 'bar']
>>> b.items
['foo', 'bar']

La valeur optionnelle, qui est mutable, est initialisée une fois et partagée par toutes les instances ! \o/

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

Tous les travaux universitaires existants montrent que le réel scandale de l'impôt français, c'est qu'il n'est pas assez progressif, et que les pauvres payent parfois plus que les riches.

J'aurais plutôt dit que le réel scandale de l'impôt français (il n'est pas le seul), c'est qu'il soit progressif. Le problème c'est l'assiette pas le taux : à taux fixe, celui qui a plus, paye plus.

Art. 13. Pour l'entretien de la force publique, et pour les dépenses d'administration, une contribution commune est indispensable : elle doit être également répartie entre tous les citoyens, en raison de leurs facultés.

Art. 14. Tous les Citoyens ont le droit de constater, par eux-mêmes ou par leurs représentants, la nécessité de la contribution publique, de la consentir librement, d'en suivre l'emploi, et d'en déterminer la quotité, l'assiette, le recouvrement et la durée.

Déclaration des Droits de l'Homme et du Citoyen de 1789

J'ai tendance à penser que dans la langue du XVIII^e l'expression « en raison de » est synonyme de « au prorata ».

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