kantien a écrit 1189 commentaires

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.

Je pense que la confusion viens du fait que les langages fonctionnels semblent (de ce que j'ai compris) favoriser la copie lors d'écriture et être optimisés pour ça. Ils masquent les mécanismes de bas niveau.

Oula non, malheureux ! :-P

Du moins tout dépend de ce que tu entends par copie. Ils ne favorisent pas du tout la copie, mais au contraire le partage de structures et cela pour deux raisons :

1. garantir l'immutabilité des structures quand on fait du fonctionnel pur;
2. économiser l'espace mémoire pour réaliser le premier point.

Par contre, effectivement, ils cachent les mécanismes bas niveau de gestion de la mémoire puisqu'il y a un GC (même si en OCaml il y a un module qui expose la représentation mémoire, mais dans ce cas il faut savoir ce que l'on fait comme dans des langages tels C ou C++ avec gestion manuelle). Il peut bien, par moment, y avoir « copie » qui en réalité est une « copie + suppression » (ce qui est en fait un « déplacement ») lorsque le GC passe, mais c'est tout.

C'est cet encodage par « partage » de structures que j'avais cru voir dans les shared_ptr. Cela étant, je me demande si ces derniers ne permettent pas de coder le même mécanisme, d'après ce que dit rewind dans ce commentaire :

puisqu'en C++, les struct et les class, c'est la même chose (à la différence que dans une struct, la visibilité par défaut est publique tandis que dans une class, la visibilité par défaut est privée).

Une liste en OCaml, comme dit précédemment, est une liste chaînée de type LIFO ce qui équivaut la structure C suivante :

typedef struct liste
  {
    int head;
    struct liste *tail;
  } liste ;

À la différence de cette structure, les listes OCaml sont polymorphes ce qui n'est pas exprimable en C, mais de ce que j'ai compris devrait être exprimable en C++.

En OCaml une telle définition de structure s'écrirait :

(* un type polymorphe qui prend pour paramètre un type 'a quelconque *)
type 'a liste =
  (* soit la liste vide pour le cas du pointeur nul en C *)
  | Nil
  (* soit un élement de type 'a et une liste de même type *)
  | Cons of 'a (* head *) * 'a liste (* tail *)

Pour montrer qu'il y a bien partage en mémoire et non copie, je vais l'illustrer avec l'utilisation de deux prédicats d'égalité = et ==. Le premier est une égalité structurelle et parcourt les deux structures pour vérifier si elles représentent la même chose, bien qu'occupant des zones mémoires différentes; tandis que le second est une égalité physique et vérifie simplement les adresses mémoires. Le second répond en temps constant, tandis que le premier peut même rentrer dans une boucle infinie et ne jamais terminer.

(* deux listes structurellement identiques *)
let l = [1; 2] and l' = [1; 2];;
val l : int list = [1; 2]
val l' : int list = [1; 2]

(* elles n'occupent pas la même zone mémoire mais représente la même liste *)
l = l';;
- : bool = true

l == l';;
- : bool = false

(* maintenant je crée deux liste en ajoutant un élément en tête de l *)
let l1 = 3 :: l and l2 = 4 :: l;;
val l1 : int list = [3; 1; 2]
val l2 : int list = [4; 1; 2]

(* elles sont bien différentes à tout point de vue *)
l1 = l2;;
- : bool = false

l1 == l2;;
- : bool = false

(* mais leurs queues sont identiques à tout point de vue *)
List.tl l1;;
- : int list = [1; 2]

List.tl l1 = List.tl l2;;
- : bool = true

List.tl l1 == List.tl l2;;
- : bool = true

(* en revanche si je pars de la liste l' *)
let l1' = 3 :: l';;
val l1' : int list = [3; 1; 2]

l1 = l1';;
- : bool = true

l1 == l1';;
- : bool = false

List.tl l1 == List.tl l1';;
- : bool = false

C'est pour cela que je me demande si les shared_ptr, au lieu d'être vus comme une zone mémoire partagée dans laquelle plusieurs objets peuvent écrire, ne peuvent être utilisés pour définir des structures vérifiant ces conditions :

1. garantir l'immutabilité des structures ;
2. économiser l'espace mémoire pour réaliser le premier point.

L'immutabilité d'une structure est une propriété très intéressante et qui permet de raisonner bien plus facilement sur le code : c'est pour cela qu'en fonctionnel pur elles sont toutes ainsi faites.

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

L'agression fait du mal, mais la rejeter en un demi-centimètre de tour de molette de la souris pour passer à la suite

Sans oublier la touche j pour passer au commentaire suivant, ce qui plaira aux admirateurs du chiffre de la bête : VI.

Et si cela ne fait pas mal, ce qui est mon cas, et que l'on est d'humeur joviale, on peut toujours revenir dessus avec le k pour se délecter de sa prose et rire un bon coup. :-)

J'ai pu ainsi apprendre des choses fort intéressantes sur moi-même : il semblerait que je sois un malade mental avec un QI d'huître qui croit encore au Père Noël. Fichtre ! je ne pensais pas en être arrivé à ce niveau-là. Cela étant, je me demande ce que je dois penser de Descartes et Leibniz qui étaient persuadés d'en avoir prouver l'existence, et d'avoir ainsi amené la question non sur le terrain de la foi mais sur celui du savoir. Et chose encore plus surprenante, bien que Kant est réduit à néant toute tentative de preuve (que ce soit de l'existence ou de la non-existence) dans sa Critique de la Raison Pure (et ramener ainsi la question sur le terrain qu'elle n'aurait jamais dû quitter : celui de la foi), comment se fait-il que Gödel (qui lui aussi était croyant, donc un malade mental, abruti…) ait tenté de réhabiliter la preuve ontologique leibnizienne ?

Et une petite citation (j'aime bien ça :-P) pour conclure :

Ajoutons encore quelques observations qui se rattachent à ce concept de foi révélée.

Il n’existe qu’une religion (vraie); mais il peut exister beaucoup de formes de croyances. – On peut ajouter que dans les diverses Églises qui se séparaient les unes des autres à cause de la diversité de leur genre de croyances, on peut rencontrer une seule et même vraie religion.

Il convient donc mieux (et c’est aussi plus usité) de dire : Cet homme est de telle ou telle confession (juive, musulmane, chrétienne, catholique, luthérienne) que, il appartient à telle ou telle religion. Ce dernier terme même ne devrait pas équitablement s’employer quand on s’adresse au grand public (dans les catéchismes et les sermons); car pour lui, il est trop savant et inintelligible; aussi bien les langues modernes n’offrent point de terme équivalent à cette expression. Par ce terme l’homme du peuple entend toujours sa foi d’église qui lui tombe sous le sens, tandis que la religion se cache intérieurement et dépend d’intentions morales; à la plupart des gens ont fait trop d’honneur en disant d’eux ; Ils professent telle ou telle religion; car ils n’en connaissent aucune et n’en demandent aucune; la foi statutaire, c’est là tout ce qu’ils entendent par ce terme. C’est pourquoi les prétendues querelles religieuses qui ont souvent ébranlé le monde en l’arrosant de sang, n’ont jamais été autre chose que des disputes sur la croyance d’église et l’homme opprimé ne se plaignait pas en réalité qu’on l’empêchait de rester attaché à sa religion (ce que ne peut aucune puissance extérieure) mais parce qu’on ne lui permettait pas de pratiquer publiquement la foi d’église.

Or, quand une Église, comme d’ordinaire il arrive, se fait passer elle-même pour la seule Église universelle (quoi qu’elle soit établie sur une foi révélée particulière qui, en tant qu’historique, ne peut être exigée en aucune façon de tous) celui qui ne reconnaît pas cette foi d’église (particulière) est appelée par elle mécréant et elle le hait de tout son cœur; quant à celui qui ne s’en écarte que partiellement (en ce qui est inessentiel), elle l’appelle hétérodoxe et l’évite tout au moins comme contagieux. Enfin s’il se rattache vraiment à la même Église, en s’écartant toutefois des croyances de celle-ci pour l’essentiel (c’est-à-dire ce dont on fait l’essentiel), on l’appelle, notamment quand il répand son hétérodoxie, un hérétique et il est considéré, tel un rebelle, comme plus punissable encore qu’un ennemi du dehors; on le rejette de l’église par un anathème (comme les Romains en prononçaient contre celui qui passait le Rubicon sans l’assentiment du Sénat) et on le livre à tous les dieux infernaux. La doctrine prétendue unique et rigoureuse selon les docteurs ou les chefs d’une église en fait de foi d’église se nomme orthodoxie, et on pourrait bien la diviser en orthodoxie despotique (brutale) et en orthodoxie libérale. – Quand une église qui déclare que sa croyance particulière est obligatoire universellement, doit s’appeler catholique, mais celle qui s’inscrit en faux contre ces prétentions d’autres églises (encore qu’il lui plairait bien d’en pratiquer elle-même de pareilles si elle pouvait) protestante, un observateur attentif constatera pas mal d’exemples louables de catholiques protestants et au contraire encore plus d’exemple scandaleux de protestants archicatholiques. Le premier cas concerne des hommes dont la mentalité s’élargit (bien que ce ne soit sans doute pas celle de leur Église); avec eux, les autres font en raison de leur esprit borné un singulier contraste qui n’est pas du tout à leur avantage.

Kant, La religion dans les limites de la simple raison.

La mise en emphase est de moi. Pour notre gentil troll ce terme aussi est bien trop savant pour qu'il puisse y entendre quelque chose, comme a peu près tous les concepts qu'il cherche à utiliser bien qu'il ne cesse de se revendiquer de la science et de la logique : science à laquelle il ne comprend absolument rien !

P.S : pour ceux qui serait étonnés de l'usage fait de l'épithète « catholique » dans le texte cité, je précise que ce mot, en grec, est synonyme de « universel » (qui lui est d'origine latine).

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

Il est effectivement très joli : encore une fois ! L'auteure est la même que celle du thème actuel de Jessie : Juliette Belin. Elle avait donné une courte conférence (35 min) à la debconf 2015 à Lyon pour relater son expérience sur la création du thème pour Jessie.

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

Pour conclure, je veux bien un cas d'usage quotidien de shared_ptr. Si je peux être détrompé, tant mieux.

Disclaimer : je n'y connais rien en C++ donc ce que je vais dire repose essentiellement sur ma compréhension de la documentation de shared_ptr.

On peut y lire :

std::shared_ptr est un pointeur intelligent qui permet le partage d'un objet via un pointeur. Plusieurs instances de shared_ptr peuvent posséder le même objet, et cet objet est détruit dans l'un des cas suivant :

• le dernier shared_ptr possédant l'objet est détruit ;

• le dernier shared_ptr possédant l'objet est assigné à un autre pointeur via operator=() ou reset().

Quand je lis cela, je pense immédiatement, par exemple, à la représentation mémoire des listes en OCaml¹. Les listes dans ce langage sont des listes chaînées qui partagent leur queue. Je m'explique.

let l = [1; 2; 3];;
(* la représentation mémoire de celle-ci est une chaîne :

| 1 | -|-->| 2 | -|-->| 3 | -|-->| |

*)

Chaque élément de la liste contient la valeur et un pointeur vers la queue ou la suite de la liste qui se termine par un « pointeur nul »². Maintenant si je crée deux listes à partir de celle-ci en rajoutant un élément en tête, elles partageront en mémoire la suite l :

let l1 = 4 :: l and l2 = 5 :: l;;
(* ce qui en mémoire donne :

| 4 | \|
       \
        -->| 1 | -|-->| 2 | -|-->| 3 | -|-->| |
       /
| 5 | /|
*)

Ai-je bien compris le concept de shared_ptr et est-ce une utilisation possible ? Pour ce qui est de la libération mémoire par le GC des listes en OCaml, la règle est équivalente à la première de la doc sus-citée : « le dernier shared_ptr possédant l'objet est détruit ».

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

C'est aussi pour l'alléger pour un démarrage plus rapide par exemple.

J'avais lu un article de blog, que je n'ai pas retrouvé, où l'auteur avait poussé l'expérimentation jusqu'à servir un site web statique avec une VM par page. :-P

Quand c'est dans un langage fonctionnel peut être, mais il en existe en C ou en C++ par exemple :)

Oh, c'est dommage ! :-P

Dans le genre sécurité et fonctionnement dans la vie réel, il y a eu un conteste de sécurité avec une prime de 10 bitcoin pour qui casserait la pinãta. Personne n'a réussi, voilà le compte-rendu :

TL;DR: Nobody took our BTC. Random people from the Internet even donated into our BTC wallet. We showed the feasibility of a transparent self-service bounty. In the style of Dijkstra: security bounties can be a very effective way to show the presence of vulnerabilities, but they are hopelessly inadequate for showing their absence.

What are you talking about?

Earlier this year, we released a Bitcoin Piñata. The Piñata was a security bounty containing 10 BTC and it's been online since 10th February 2015. Upon successful mutual authentication, where the Piñata has only a single trust anchor, it sends the private key to the Bitcoin address.

It is open source, and exposes both the client and server side of ocaml-tls, running as an 8.2MB MirageOS unikernel. You can see the code manifest to find out which libraries are involved. We put this online and invited people to attack it.

Any approach was permitted in attacking the Piñata: the host system, the MirageOS TCP/IP stack, our TLS, X.509 and ASN.1 implementations, as well as the Piñata code. A successful attacker could do whatever they want with the BTC, no questions asked (though we would notice the transaction).

Lire la suite…

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

J'aime bien la solution mise en place, j'allais me faire avoir et cela m'a retenu. :-)

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

J'ai régulièrement la capacité de voler (quelque mètre au dessus du sol) de manière volontaire et contrôlé (même si parfois j'ai du mal à gagner de l'altitude, surtout en fin de rêve). C'est assez génial !

Cela fait bien des années que je n'en ai pas fait un similaire, je me souviens d'ailleurs de moins en moins de mes rêves. Lorsque je le faisais, tout comme toi, plus je prenais conscience que je rêvais moins j'arrivais à décoller et cela annonçait la fin du rêve et mon réveil. Mais effectivement : quel pied de se mouvoir tel un oiseau ! :-)

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

Merci pour ces précisions. Comme je l'ai dit c'est ce que j'en avais compris, et ne connaissant pas vraiment le sujet et les problématiques c'était à prendre avec des pincettes. Mais l'idée reste bien de n'embarquer que le strict nécessaire au niveau des fonctionnalités du noyau et de l'application pour réduire la surface d'attaque ? Et cela avec la sécurité des systèmes de typage des langages fonctionnels, ce qui réduit également le risque de failles ?

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

C'est une allusion à un vieux débat entre kantien et cartésien. Descartes, dans ses méditations métaphysiques, doute de sa propre existence et en cherche un preuve; pour cela il se fonde sur la conscience qu'il a de penser et conclue de là à son existence. Pour les kantiens, les deux propositions « je suis » et « je pense » sont identiques, et c'est un paralogisme que de vouloir conclure de l'une à l'autre comme si elle lui servait de fondement; d'autant que derrière Descartes s'en sert pour prouver l'immortalité de l'âme, et là il part en sucette !

Ce qui ne peut être pensé que comme sujet n'existe aussi que comme sujet et est par conséquent susbstance;
Or, un être pensant, considéré simplement comme tel, ne peut être pensé que comme sujet;
Donc il n'existe que comme sujet, c'est-à-dire comme substance.

Dans la majeure, il est question d'un être qui peut être pensé sous tous les rapports en général, et aussi par conséquent tel qu'il peut être donné dans l'intuition. Mais dans la mineure, il n'est plus question du même être qu'autant qu'il se considère lui-même comme sujet uniquement par rapport à la pensée et à l'unité de la conscience, mais non pas en même tant par rapport l'intuition, qui donnerait cet être comme objet de la pensée. La conclusion est donc tirée per sophimsma figuræ dictionnis, c'est-à-dire par un raisonnement captieux.

La pensée est prises dans les deux prémisses en des sens tous différents. Dans la majeure, elle s'applique à un objet en général (tel, par conséquent, qu'il peut être donné dans l'intuition); dans la mineure au contraire, on ne l'envisage que dans son rapport à la conscience de soi, et par conséquent on ne pense plus ici aucun objet; mais c'est seulement le rapport à soi comme sujet qu'on se représente (comme la forme de la pensée). Dans la première, il s'agit des choses, qui ne peuvent être conçues autrement que comme sujet; dans la seconde, au contraire, il ne s'agit plus des choses, mais (puisque l'on fait abstraction de tout objet) de la pensée, dans laquelle le Je sert toujours de sujet à la conscience. On ne saurait donc en déduire cette conclusion : Je ne puis exister autrement que comme sujet, mais celle-ci seulement : Je ne puis, dans la pensée de mon existence, me servir de moi que comme d'un sujet du jugement, proposition qui est identique et qui ne révèle absolument rien sur le mode de mon existence.

Kant, Critique de la Raison Pure.

Ce passage est extrait du chapitre sur la dimension dialectique de la psychologie rationnelle d'inspiration cartésienne, et qui critique le cogito cartésien (le raisonnement en italique est une formalisation du raisonnement de Descartes pour ensuite conclure de la substance à l'immortalité de l'âme). Que l'on dise « je pense » ou bien « je suis » (ou plutôt « je suis pensant ») c'est tout un.

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.

Il me semble concevable de juste produire un binaire et de le faire exécuter sur une machine distante sans avoir à gérer toute une VM pour ça.

De ce que j'ai compris, l'idée de la VM c'est pour l'isolation et la sécurité : si il y a une faille cela ne compromet pas l'hôte, là où une faille dans un binaire peut aller jusqu'à donner un accès root à la machine distante qui, comme elle aura un noyau complet et un user-land, offrirait des possibilités illimités à l'attaquant. Avec un unikernel, même s'il y a une faille l'attaquant ne pourra jamais en tirer partie ou très peu.

D’accord pour dire que la vulgarisation c’est compliqué. J’en ai bien conscience, et apprendre le Haskell ce n’est pas simple en partie à cause d’explications absconses.

Je suis bien d'accord avec toi sur la difficulté de la vulgarisation, je m'améliore avec les années mais j'ai encore de gros progrès à faire sur ce plan. Néanmoins, je maintiens que pour apprendre la programmation fonctionnelle il n'est pas nécessaire de passer par ces explications absconses. Cela peut s'avérer nécessaire si l'on veut faire des choses très poussées et évoluées¹ — comme avec le C++ de ce que j'ai compris de la discussion de ce fil ;-) — mais pour apprendre on n'en a pas besoin.

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

As-tu déjà envisagé d'étudier OCaml ? Il est de la même famille que Haskell : lambda-calcul fortement et statiquement typé, mais contrairement à lui il n'est pas pur : on peut y pratiquer les paradigmes impératif, fonctionnel et orienté objet.

On peut y faire de la programmation système, et même faire des OS.

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.

De ce que j'en ai compris, un des intérêts des unikernels est de faire de l'isolation de service et de réduire la surface d'attaque. À l'arrivée il n'y a pas à proprement parler de user-land, le noyau et l'unique application (serveur web, serveur mail, serveur de minage bitcoin…) sont fondus en un tout unique. D'où la notion de library operating system : selon l'application à la compilation on ne prend que les bibliothèques strictement nécessaire tant du noyau proprement dit que de l'application.

d’accord, les concepts d’Haskell sont très poussés, on est tous d’accord à dessus

Non, on n'est pas tous d'accord là-dessus. Bien souvent ce sont des concepts simples à expliquer mais les haskelleux sont pédants dans leur manière de s'exprimer et ont systématiquement recours au vocabulaire de la théorie des catégories au lieu de vulgariser leur propos.

J'en avais fait un commentaire humoristique en illustrant les notions de catamorphisme, anamorphisme et hylomorphisme… sur l'algorithme de la multiplication tel qu'on l'enseigne à des enfants de 8 ans !

Dans le même genre il y a ce journal (désolé Aluminium 95 ;-) où un docteur en physique, et ce n'est pas le seul, se plaignait de l'usage d'un jargon incompréhensible. Je m'y suis collé pour vulgariser le propos. En gros le problème était : comment encoder des arbres dans un langage fonctionnel dont le système de type ne dispose pas de types récursifs, et cela afin de faire un langage embarqué (EDSL) ?

Pour ce qui est d'ailleurs du vocabulaire et des concepts utilisés en Haskell, l'abus qu'ils en font ne fait pas toujours plaisir aux spécialistes du sujet.

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

Dans mon cas, bien que ce soit une vielle installation avec des fusibles à l'ancienne, lorsque je coupais le fusible du circuit je n'avais plus de fuite sur le neutre. C'est ce que j'ai fini par faire. En fait, j'ai constaté le phénomène en me prenant un léger coup de jus en manipulant le neutre alors que je ne m'y attendais pas trop.

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

Il y a effectivement peut-être de cela. Je me suis également rendu compte, en changeant les prises, qu'elles avaient beau afficher la terre en façade, cette dernière n'était pas connectée sur les prises… :-/

Dans ce cas, si le courant de fuite ne peut partir à la terre, il fuit sur le neutre qui est le point de plus bas potentiel ? Et quand je sépare deux fils du point neutre, celui qui n'est plus lié au fusible se retrouve avec un potentiel plus élevé, au point de pouvoir allumé le tournevis ?

Je n'ai pas fait de test depuis que j'ai remis la terre sur les prises pour voir si le phénomène se produit toujours. Si j'ai le temps, je vérifierai.

Sinon l'installation est ancienne, elle doit dater du début des années 80 et je n'ai pas de voltmètre pour mesurer la tension entre le neutre et la terre.

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

la différence de potentiel ne joue que peu : 100 kV ne feront que se dresser les cheveux sur la tête :-)
en revanche, l'intensité (en ampère) est pertinente : dépassé 24 A, c'est la mort assez rapidement…

Tout à fait. Au palais de la découverte, il y a un atelier d'électrostatique où ils placent un spectateur dans une cage de Faraday sous une tension de 350 kV (mais avec une grosse résistance dans le circuit donc une faible intensité) et celui-ci lance des « éclairs » du bout de ses doigts. Ça a son effet ! :-)

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

Un lien vers les insultes dont tu as été victime pourrait nous aider, parce que sinon, tu donnes l'impression de vouloir aseptiser linuxfr.

Je suppose qu'il fait allusion aux échanges sur la dépêche sur Open Beuaty Fact, avec en particulier ce commentaire dans lequel Riendf affirme que les végétariens sont des malades mentaux.

Sur le même fil il a fait l'éloge de la politique maoïste de contrôle des naissances, du Riendf dans toute sa splendeur… :-/

@ ariasuni : si je peux te donner un conseil, ignore ce type de personnage si tu ne peux les gérer (pour ta pathologie, je compatis, je suis moi-même cyclothymique mais en ce moment je suis dans une phase up).

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

À ce propos, dernièrement je refaisais mon salon et en changeant les différentes prises je suis tombé sur un phénomène electrique que je n'ai pas compris. Si quelqu'un s'y connaissant plus que moi en électricité pouvait me l'expliquer ?

Voilà la situation en exemple sur une prise commandée. Je démonte la prise, et je constate que le code couleur rouge pour la phase et bleu pour le neutre est respecté (avec un tourne-vis testeur sur chacun des pôles). Je coupe l'arrivée de la phase via l'interrupteur, je vérifie avec le tourne vis et c'est bon plus rien n'arrive. Je retire les fils de la prise pour y mettre la nouvelle, et là à mon grand étonnement : un des deux fils bleus neutres, lorsqu'ils ne sont plus en contact, se retrouve avec du potentiel non neutre (le tourne-vis s'éclaire), et quand je les remets en contact j'ai des étincelles. Puis une fois remis en contact, tout revient à la normal : la phase se retrouve bien sur le rouge et le pôle qui contient les deux fils bleus n'allume plus le tourne-vis.

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

tétracapillosection

Tétracapillotomie plutôt ?

Dans les deux cas, il y a un mélange de racine grecque et latine. Avec les racines grecques cela donne « tetratrichotomie » (tricho comme préfixe grec pour les cheveux), et pour les racines latines « quadricapillosection ».

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