It’s been something like 6 months that I started using Haskell for real and I think I’ve got past the point where I can say that I’m comfortable with it ; it’s usually the good time to take a halt and look back and identify the things that weren’t as smooth as one could have hoped.

The good part

At its core Haskell is an amazingly simple language: after you know how to define and call functions and how to define new types and type classes, there aren’t a lot of feature left to understand. I made a small presentation in my company saying that you can learn Haskell syntax in 10 minutes, it actually took 20. That’s still way below the time it takes to learn all the oddities of a language like C++.

The IDE support is quite good. Yes I know there are all kind of memes around this fact on Internet, yet there’s now a Langage Server Protocol for it which is very decent. It still struggles for big projects, for some reason it doesn’t work if there is a compilation failure when I start VS Code and may lack some refactoring tool (like renaming symbols) but other than that I can’t complain: it’s able to show the type of each variable and function in the code, and even with documentation when available, and jumping to definition just works. It also shows unused imports and language imports, something I wish was available for more mature language like C++.

Writing in Haskell helps practice Category Theory concept. Category Theory defines a lot of concepts which I often met with a « so what ? » mood at first read, but their relevance becomes so much more obvious when using them. For fun I ported a 300 lines code that parsed a specific CSV file from Python, and I ended up with something like 15 occurrences of a functor and 11 occurrences of a monad. I have yet to see how some other concepts like Adjunction translate in Haskell and read all the paper about the Categorical Language Query language which uses fibration.

The bad part

Haskell libraries are real beasts. Most of them have very useful features but it always feels like I’m learning a whole new subject each time I just want to use something. The lens libraries are really satisfying to use but there are tons of operators to discover. When reading about parsing in Haskell (one of it’s strengths) I encountered lot of daunting terms like Alternative functor and monadPlus, the former apparently being « just a monoid in a (non canonical) monoidal category »… It’s always challenging.

I can’t mention having 2 build tools is confusing a lot when beginning. As far as I understand Cabal is handling dependencies and Stack is handling the versioning of these dependencies, but apparently Cabal seem to have gained some functionalities lately in this department.

I discovered the hard way that the base library is unsafe which is non-diegetic for a langage that focus so much on safety. The (!!) function for instance doesn’t return a Maybe but an object, and if it fails it crashes. The solution is to use another base library (called relude) in the Stack/Cabal dependencies. It’s something that’s not emphasized enough in my opinion (I discovered it while browsing Zulip funprog channel).

I’m always amazed by how many subtle assumptions we often make when doing day-to-day maths, and how challenging these assumptions yield to some interesting construct.

I’m currently trying to read the Homotopy Type Theory (« Hott ») book. HoTT is an extension of type theory which is the underlying logic foundation of most proof assistant.
It uses the « proposition as type » idea which identifies some usual logical building block like conjunction, disjunctions, implications, quantifiers… with usual (and sometimes less usual) programming type constructs like algebraic types, functions…

One of the most important logical building block covered by type theory is the equality. To be honest I never really thought what « being equals to » really mean before reading the book, besides the usual « it’s just another equivalence relation between things ». But that’s neither a definition nor a satisfying properly, as for instance you can name several other equivalence like isomorphism which wouldn’t act as a good replacement for equality in most context.

Type theory gives two answers to this question : the first one is the definitional equality, or equality by definition. This equality comes from the fact that some composite type can be « reduced » : breaking a tuple into its component, or applying an argument to a function yield simpler syntaxical construct ; for instance in this framework (\x -> x + x)(1) (applying « 1 » to the lambda function which transforms « x » to « x + x ») is definitionally equals to 2, or fst (x, y) is definitionally equals to x. It’s just a matter of « following your nose » and determining if 2 objects are definitionally equal should better be decidable.
Unfortunatly not every equality is decidable in the day to day maths world : equality for reals is not decidable, there is no magic method to determine if 2 sides of an equation are equals. This means we need another kind of equality and here lie the second answer provided by type theory.
Type theory introduce an identity type, sometimes called « judgemental equality ». It’s a proposition and not merely a syntaxical rewriting. However the computation and uniqueness principle are designed to capture the defining property of equality which was hinted by the definitional equality : If two objects x and y are equals, then you can replace x by y in any proposition containing y (it’s a bit more involving but it’s the overall idea). Note that identity type is a generalisation of the definitional equality : an introduction rule for the identity type is equality by reflexivity, ie an object x is equals to itself. Since two definitionnaly equals objects are really just the same object in this framework, 2 definitionnally equals object are also judgmentally equals. But what are the others way to introduce equality then ?

That’s where Homotopy type theory comes into play. There are several answer to this question : one is that reflexivity is always the only way to introduce equality, and thus if 2 objects are equals one can consider that they are really the same. This is the logic under the Extensional Type Theory. There are several consequence to this design choice that I won’t cover.
On the other hand, homotopy type theory allows other kinds of « equalities » with root in homotopy (a subfield of topology as far as I understand which studies continuous path, path between path, and so on). It gives rise to a whole new interpretation of equality that is at the hearth of the book : objects are not merely « element in a set » but become « points in a space » whose path between point are equality relation.

I will write more on it later.

Group in a category

Now we will look at group with a categorical point of view.

A group \(G\) can be regarded as a category with a single arbitrary object and all elements as arrows. Composition, associativity, and existence of an identity morphism are respected by virtue of the group laws. In the following the arbitrary object will be represented by \(\bullet\).

A functor \(F\) between a group and the \(\textbf{Set}\) category is an action on group :

• For every arrow \(f:\bullet\to\bullet\), \(F(f)\) is an arrow from \(F(\bullet)\) in \(\textbf{Set}\) to \(F(\bullet)\), which means it’s a function from a set to itself.
• The identity arrow \(Id_{\bullet}\) is lifted to \(Id_{F(\bullet)}\).
• For all arrow x and y \(\bullet\to\bullet\), \(x . y\) is lifted to \(F(x . y) = F(x) . F(y)\) which is the compatibility property of the action on law.

The converse is also true : given a group action \(\phi: G \times X \to X\), we can build a functor \(F\) by taking \(F(\bullet) = X\), and for \(x\in G, F(x) = \phi(x, .)\). If we got another \(y\) then the compatibility property ensures that \(F(x).F(y) = \phi(x, \phi(y, .)) = \phi(x\otimes y, .) = F(x.y)\).

Proving the connection

We already saw some functors between a group and the \(\textbf{Set}\) category: the hom functors. We even got the Yoneda embedding \(Y\) which is a functor that provides us with such functor.

Let’s apply the Yoneda lemma on our group category’s object: \(Hom(\bullet, \bullet)\to Hom(Y(\bullet), Y(\bullet))\) is an isomorphism.

Now let’s have a closer look at the mapping: the left hand-side is \(Hom(\bullet, \bullet)\), that is all the morphisms of our group as a category. If you remember how we built our group as a category this means this set consists of all the elements of our group.

If we look at the right hand-side of the mapping, \(Hom(Y(\bullet), Y(\bullet))\) are the morphisms of a functor from the group as a category to \(\textbf{Set}\), that is the action of the group on a set.
And this is not any set : the expression of the Yoneda embedding tells us that \(Y(\bullet) = Hom(\bullet, -)\) and again, there is only a single object of the category so we’re talking about \(Hom(\bullet, \bullet)\) here that is the group itself.

If we recap the Yoneda lemma on a group as a category tells us that a group is isomorphic to the group of action of this group on itself. Since the group of action of this group on itself is a subgroup of the group of automorphism of the group, we have proven that a group is isomorphic to a subgroup of the symmetric group of this group.

References

In french : http://www.les-mathematiques.net/phorum/read.php?16,2085554

Voici l’exercice qu’on va abordé dans ce billet :

Soit \((X, T )\) un espace topologique séparé. Montrer que la diagonale \(\Delta\) de \(X ×X\) est fermée dans
\(X × X\).

http://math.univ-lille1.fr/~bodin/exolic1/exolic.pdf

Aparté sur les topologies initiales

Mon livre de topologie définit les produits de topologies comme la topologie initiale des fonctions de projections \(p_i = (x_1, x_2) \in X, X \to x_i\). Ce qui nous amène à regarder ce qu’est une topologie initiale.

Pour être transparent, je vois également le terme de « topologie faible » utilisé ; c’est justement le terme utilisé par coq-topology… Je n’ai pour l’instant pas trouvé s’il y a une différence entre les 2 concepts, dans la suite je pars du principe qu’il s’agit de la même chose.

Une topologie initiale permet de construire une topologie sur un espace qui n’en dispose pas à partir de fonctions de cet espace sur un espace qui, lui, est topologique. Ainsi, si on dispose d’un espace X, et de fonctions \(f_i:X \to Y_i\) avec \(Y_i\) topologique, on définit une topologie sur X comme étant l’ensemble des intersections des \(f_i^{-1}(O_i)\) avec \(O_i\) ouvert de \(Y_i\). Ceci permet d’assurer que, par construction, ces fonctions sont continues.

Dans le cas des fonctions produits, les ouverts sont donc de la forme \(O_1 x O_2\) avec \(O_1\) un ouvert de \(Y_1\) et \(O_2\) un ouvert de \(Y_2\).

Preuve en Coq

Le module coq-topology dispose d’un module ProductTopology qui lui-même se base sur le module WeakTopology qui implémente les définitions du paragraphe précédent.

Comme souvent la principale difficulté n’est pas à trouver dans les mathématiques, il ne s’agit que de dérouler des définitions ; en revanche, ces définitions sont particulièrement peu digestes en Coq.

On va utiliser également les axiomes de séparations déjà définis dans coq-topology.

From Topology Require Import TopologicalSpaces.
From Topology Require Import InteriorsClosures.
From Topology Require Import Neighborhoods.
From Topology Require Import ProductTopology.
From Topology Require Import SeparatednessAxioms.

On dispose de quelques fonctions dans coq-topology pour faciliter l’écriture de produit de 2 topologies, qui se basent sur les fonctions built-in fst et snd de Coq. L’énoncé devient :

Theorem exo (X:TopologicalSpace):
  Hausdorff X -> closed (fun x:point_set (ProductTopology2 X X) => fst x = snd x).
Proof.

On va déplier les définitions :

  unfold Hausdorff.
  intros HypSep.
  unfold closed.

Pour plus de lisibilité, on va associer à l’ensemble \(\Delta\) une variable :

  remember (Complement (fun x : point_set (ProductTopology2 X X) => fst x = snd x)) as ExtDiagonale.

On passe ensuite par un résultat intermédiaire sur cette diagonale pour caractériser les éléments qui y appartiennent :

  assert (forall x y, not (x=y) <-> In ExtDiagonale (x,y)).
  split;intros.
  - rewrite HeqExtDiagonale. eauto with sets.
  - rewrite HeqExtDiagonale in H. eauto with sets.

Pour résoudre l’exercice, on va utiliser une base des ouverts sur le produit de topologie.

  - refine (coverable_by_open_basis_impl_open (ProductTopology2_basis X X) _ _ _). apply ProductTopology2_basis_is_basis.
    intros x0 x0inExtDiag. assert (x0 = (fst x0, snd x0)). apply surjective_pairing. rewrite H0 in x0inExtDiag. pose (tmp:=H (fst x0) (snd x0)). rewrite <- tmp in x0inExtDiag. destruct (HypSep (fst x0) (snd x0) x0inExtDiag) as [U [V ]].
    exists (fun x => In U (fst x) /\ In V (snd x)). inversion H1 as [openU [openV [x0InU [x0inV InterUVEmpty]]]].
    split.
    + replace (fun x : point_set X * point_set X => In U (fst x) /\ In V (snd x)) with [p : point_set (ProductTopology2 X X) | let (x, y) := p in In U x /\ In V y]. constructor ; repeat assumption. simpl. apply functional_extensionality. intros. Search ([_:_ | _]). rewrite characteristic_function_to_ensemble_is_identity. autounfold with *. assert (x=(fst x, snd x)). apply surjective_pairing. rewrite H2. simpl. trivial.
    + split.
      * autounfold with *. intros. pose (tmp2:=surjective_pairing x). rewrite tmp2. rewrite <- H. unfold In in H2. inversion H2. unfold not. intro. rewrite H5 in H3. assert(In (Intersection U V) (snd x)). eauto with *. rewrite InterUVEmpty in H6. Search Empty_set. apply Noone_in_empty in H6. assumption.
      * autounfold with *. eauto with *.
Qed.

On continue dans la série des espaces topologiques avec un exercice sur les axiomes de séparation :

Soit \((X, T )\) un espace topologique.
Montrer que les conditions suivantes sont équivalentes :
(i) \(\forall x, y \in X, x \neq y, \exists V \text{voisinage de}x, y \notin V .\)
(ii) \(\forall x \in X, {x} fermé.\)
(iii) \(\forall x \in X, {V ; V \text{voisinage de }x} = {x}.\)
Soit \((X, T )\) ainsi et \(A \subset X\) tel que \(\overline{A} \neq A\). Montrer que si \(x \in \overline{A}\backslash A\), tout voisinage de \(x\) coupe \(\)A en une infinité de points.

Apparté sur la séparation

Cet exercice m’a donné l’occasion de découvrir le concept de séparation en topologie que je ne connaissais que très vaguement. L’idée derrière la séparation est de caractériser le niveau d’ « indépendance » des voisinages de deux points distincts. Plus exactement, on distingue 3 niveaux de séparations notés T0, T1 et T2:

• T0 signifie que si on prend deux points distincts, on a au moins un voisinage de l’un qui ne contient pas l’autre,
• T1 signifie que si on prend deux points distincts, chacun a au moins un voisinage ne contenant pas l’autre,
• Enfin T2 est le niveau au dessus : si on prend deux points distincts, on a au moins un couple de voisinage respectif qui sont disjoints.

La plupart des espaces usuels (les réels, complexes, espaces vectoriels…) sont T2. Parmi les espaces qui ne sont pas séparés il y a les topologies grossières (ie l’ensemble entier et l’ensemble vide). J’avoue que je ne connais pas la motivation derrière les niveaux T0 et T1 et je n’ai pas d’exemples d’espace vérifiant ces niveaux mais pas les suivants.

Le trio d’équivalence est semble-t-il une propriété fondamentale des axiomes de séparation puisqu’il est directement présenté comme propriété dans mon livre de topologie, qui le démontre de bas en haut. J’ai essayé d’effectuer la démonstration en Coq de haut en bas mais je me suis retrouvé bloquer en cherchant à passer de (ii) à (iii) ; ayant ensuite décidé qu’il était peut-être plus sage de suivre une voie connue, j’ai finalement opté pour la démonstration de bas en haut. Il s’avère que le passage de (iii) à (ii) est aussi compliqué et que dans les autres cas les preuves sont plus ou moins des « miroirs » de celles que j’avais faite dans ma première tentative, j’imagine aisément qu’il est malgré tout possible d’effectuer la preuve dans n’importe quel sens.

Préalable

Une propriété particulièrement utile pour cette exercice est la caractérisation de l’adhérence d’un ensemble, appelé closure_impl_meets_every_open_neighborhood dans coq-topology : un point est dans l’adhérence d’un ensemble si tous ses voisinages rencontrent cet ensemble, ou dit autrement si l’intersection de ses voisinages avec cet ensemble n’est jamais vide.

Du point de vue plus pratique, on continue à utiliser quelques astuces qui simplifient la vie sur le long terme : on définit une tactic ensemble_proof_intro pour automatiquement nous fournir les 2 inclusions de l’égalité de l’ensemble à prouver, on se sert d’inversion plutôt que de destruct, et on nomme autant que possible les hypothèses/variables pour faciliter la lecture.

A noter qu’à un moment j’ai eu besoin de définir un axiome sur la décidabilité sur l’égalité de 2 éléments d’un ensemble. Par défaut si deux éléments d’un ensemble ne sont pas égaux, Coq ne déduit pas automatiquement qu’ils sont différents ; en effet la logique constructive sur laquelle est basée Coq se passe de l’axiome du tiers exclu qui stipule qu’une propriété (comme ici l’égalité) est vraie ou sa négation est vraie. Il faut donc manuellement indiqué que dans notre cas, c’est vrai.

Trio d’équivalence

On commence par les imports de circonstances et l’écriture des propriétés :

From Topology Require Import TopologicalSpaces.
From Topology Require Import InteriorsClosures.
From Topology Require Import Neighborhoods.
Require Import Decidable.

Definition P1 (X:TopologicalSpace) :=
  forall x y:point_set X, not (x = y) -> exists N, neighborhood N x /\ not (In N y).

Definition P2 (X:TopologicalSpace) :=
  forall x:point_set X, closed (Singleton x).

Definition P3 (X:TopologicalSpace) :=
  forall x:point_set X, FamilyIntersection [V:Ensemble (point_set X) | neighborhood V x] = Singleton x.

Ltac ensemble_proof_intro:=apply Extensionality_Ensembles; unfold Same_set; split.

On aura également besoin de montrer que si un singleton est contenu dans un autre, alors leur élément est égal :

Theorem Singleton_Inclusion (T:Type): forall x y:T, Included (Singleton x) (Singleton y) -> x = y.
Proof.
  intros.
  unfold Included in H. symmetry. apply Singleton_inv. apply H. eauto with sets.
Qed.

On commence ensuite par l’implication la plus compliqué, P3 vers P2 :

Theorem P3_implies_P2 {X:TopologicalSpace}:
  P3 X -> P2 X.
Proof.
  unfold P3. unfold P2.
  
  intros P3 x0.

La stratégie pour montrer que le singleton x est fermé, est de montrer qu’il est égal à son adhérence. Cette stratégie part de l’intuition que l’écriture de l’ensemble des voisinages est proche d’une intersection en ensemble de fermé contenant un ensemble.

  assert (Included (closure (Singleton x0)) (Singleton x0)).

  unfold Included.
  intros x xInClosure.

On va se servir de la propriété sur la caractérisation des adhérences. Quand on regarde les hypothèses de cette propriété, on voit qu’il va falloir trouver un ouvert, qui contient x, et on en déduira que x0 est dans V (car l’intersection du singleton x0 et V est non vide).

pose (tmp2:=closure_impl_meets_every_open_neighborhood  _ (Singleton x0) x xInClosure).

  assert (forall V, open_neighborhood V x -> Inhabited (Intersection (Singleton x0) V)).
  intros V VNeighbor. inversion VNeighbor. unfold open_neighborhood in VNeighbor.
  apply tmp2. 
  assumption. assumption.
  assert(forall V, open_neighborhood V x -> In V x0).
  intros. pose (tmp3:=H V H0). inversion tmp3. inversion H1. inversion H2. subst. assumption.

Pour rappel, on cherche à montrer ici que x est dans le singleton x0, ie que x = x0. Pour l’instant on n’a pas encore utilisé l’hypothèse P3. Pour se simplifier la vie on peut remarquer qu’on peut se servir des voisinages ouverts plutôt que des voisinages quelconques :

  assert( forall x : point_set X,  FamilyIntersection [V : Ensemble (point_set X) | neighborhood V x] =
                              FamilyIntersection [V : Ensemble (point_set X) | open_neighborhood V x]).
  {
    intros x1. ensemble_proof_intro.
   - intros  S SinInters. inversion SinInters.
    constructor. intros. apply H1. inversion H3. constructor. apply open_neighborhood_is_neighborhood. apply H4.
  - intros y yinIntersOpen. inversion yinIntersOpen.
    constructor. intros S SInInters. inversion SInInters as [[S' [OpenS' S'InS]]].
    refine (S'InS _ _). apply H1. split. assumption.
  }

Muni de ce résultat on peut prouver l’égalité:

  assert(Included (Singleton x0) (Singleton x)).
  unfold Included. intros y yisx0. inversion yisx0.
  rewrite <- (P3 x).
  rewrite (H1 x).
  constructor.
  intros. inversion H3. subst. eauto.

et donc l’inclusion inverse :

  apply Singleton_intro.
  refine (Singleton_Inclusion _ _ _ _). assumption.

La suite est relativement directe:

  assert (closure (Singleton x0) = Singleton x0).
  ensemble_proof_intro.
  apply H. apply closure_inflationary.
  rewrite <- H0. apply closure_closed.
Qed.

L’inclusion P2 vers P1 est plus simple:

Theorem P2_implies_P1 {X:TopologicalSpace}:
  P2 X -> P1 X.
Proof.
  unfold P1, P2.
  intros P2 x y xNeqy.
  unfold closed in P2.

  exists (Complement (Singleton y)). split.
  unfold neighborhood. exists (Complement (Singleton y)). split. unfold open_neighborhood. split. apply (P2 y).
  unfold Complement. unfold not. unfold In. intros. destruct xNeqy. inversion H. trivial.
  eauto with sets.
  eauto with sets.
Qed.

Celle de P1 vers P3 n’est pas beaucoup plus compliqué, mais nécessite quand même la décidabilité dont on a préalablement parlé, pour faire une disjonction de cas :

Theorem P1_implies_P3 {X:TopologicalSpace}:
  P1 X -> P3 X.
Proof.
  unfold P1. unfold P3.
  intros P1 x0.
  ensemble_proof_intro.
  - unfold Included. intros x xInIntersNeigh.
    destruct (decT X x0 x).
    + eauto with sets.
    + inversion xInIntersNeigh. destruct (P1 x0 x H). inversion H2. pose (tmp:= H0 x2). autounfold with sets in tmp.
      assert([V : Ensemble (point_set X) | neighborhood V x0] x2).
      constructor. assumption.
      apply tmp in H5. destruct (H4 H5).
  - unfold Included. intros x xIsx0.
    inversion xIsx0.
    constructor. intros. inversion H0. inversion H1. inversion H2. unfold Included in H4. apply H4. inversion H3. assumption.
Qed.

Seconde propriété

Alors là c’est vraiment costaud à démontrer, la faute à la démonstration de l’infinité. Coq dispose de quelques résultats sur les ensembles infinis, mais malheureusement peu nombreux et que nous n’utiliserons donc pas.
En revanche il est beaucoup plus simple de travailler sur les ensembles finis, on va donc procéder par l’absurde.

En particulier une propriété des ouverts qui est vraie dans le cas des ensembles finies mais qui ne l’est plus dans les ensembles infinis est la stabilité par intersection. On va donc prouver cette propriété, par récursion sur la taille de l’ensemble :

Theorem intersection_finite (X:TopologicalSpace):
  forall F:Family (point_set X), Finite _ F /\ (forall S, In F S -> open S) -> open (FamilyIntersection  F).
Proof.
  intros F [F_Finite F_Set_Of_Opens].
  apply finite_cardinal in F_Finite.
  destruct F_Finite as [n cardFn].
  generalize dependent F.
  induction n ; intros F cardFn F_Set_Of_Opens.
  - inversion cardFn. Search FamilyIntersection. rewrite empty_family_intersection.
    Print TopologicalSpace. apply open_full.
  - inversion cardFn. pose (tmp:= IHn A H0).
    assert(FamilyIntersection (Add A x) = Intersection (FamilyIntersection A) x).
    ensemble_proof_intro; unfold Included; intros x0.
    + intros x0InIntersAx.
      inversion x0InIntersAx.
      constructor.
      * constructor. eauto with sets.
      * eauto with sets.
    + intros x0InInters. inversion x0InInters. inversion H3. constructor. unfold Add.
      intros. inversion H8.
      * eauto with sets.
      *  inversion H9. subst. eauto with sets.

    + rewrite H3. apply open_intersection2.

      * apply tmp. intros. apply F_Set_Of_Opens. Search Add.
        unfold Add in H1. rewrite <- H1. eauto with sets.
      * apply F_Set_Of_Opens. rewrite <- H1. unfold Add. eauto with sets.
Qed.   

Un autre résultat qui m’a été utile est que l’égalité est conservée par passage au complément :

Theorem Complement_inv (X:Type) : forall (S1 S2: Ensemble X), Complement S1 = Complement S2 -> S1 = S2.
Proof.
  intros. ensemble_proof_intro; rewrite <- Complement_Complement with (A:=S1); rewrite <- Complement_Complement with (A:=S2); apply complement_inclusion; rewrite H; eauto with sets.
Qed.

On peut ensuite passer à la démonstration en elle-même :

Theorem part2 (X:TopologicalSpace): P2 X -> forall A: Ensemble (point_set X), forall x, In (Setminus (closure A) A) x -> forall N, neighborhood N x -> not (Finite _ (Intersection N A)).
Proof.
  intros P2 A x0 x0inclAminA.
  unfold Top.P2 in P2.
  destruct x0inclAminA as [x0InClA x0NotInA].
  intros N [O [[OpenO x0inO] OInN]].
  
  pose (tmp:=closure_impl_meets_every_open_neighborhood _ A x0 x0InClA).

  unfold not. intros NInterAFinite.
  
  remember (fun E => exists x, In (Intersection N A) x /\ E = Complement (Singleton x)) as SetOfElems.
  (**pose (tmp3:=intersection_finite _ SetOfElems).**)
  assert(Finite _ SetOfElems).
  generalize dependent SetOfElems.
  induction NInterAFinite; intros.
  - assert (SetOfElems = Empty_set). rewrite HeqSetOfElems. ensemble_proof_intro.
    + unfold Included. intros. unfold In in H. destruct H. destruct H. destruct H.
    + eauto with sets.
    + rewrite H. eauto with sets.


  - assert (SetOfElems = Add (fun E : Ensemble (point_set X) => exists x0 : point_set X, In A0 x0 /\ E = Complement (Singleton x0)) (Complement (Singleton x))).
    ensemble_proof_intro ; unfold Included; rewrite HeqSetOfElems.
    + intros. inversion H0. inversion H1.  unfold In. inversion H2 as [x2InA0|]. 
      * left. exists x2. split. assumption. assumption.
      * right. inversion H4. subst. eauto with sets.
    + intros. unfold In. inversion H0.
      * inversion H1. inversion H3. exists x3. split. left. assumption. assumption.
      * exists x. inversion H1. split. right. eauto with sets. trivial.


    + rewrite H0. constructor.
      * remember (fun E : Ensemble (point_set X) => exists x1 : point_set X, In A0 x1 /\ E = Complement (Singleton x1)) as P0.
        apply IHNInterAFinite. trivial.
      * unfold In. unfold not. intros. inversion H1. inversion H2.
        apply Complement_inv in H4. 
        apply Singleton_equal in H4. subst. destruct (H H3).
    
   
  - remember (FamilyIntersection SetOfElems) as ContraGen.
    assert (open ContraGen).
    rewrite HeqContraGen.
    apply intersection_finite. split.
    + assumption.
    + intros S SInSetOfElems. rewrite HeqSetOfElems in SInSetOfElems. unfold In in SInSetOfElems. inversion SInSetOfElems.
      inversion H0. rewrite H2. refine (P2 _).
    + pose (contra:= tmp (Intersection ContraGen O) (open_intersection2 ContraGen O H0 OpenO)).
      assert (In (Intersection ContraGen O) x0).
      rewrite HeqContraGen.
      constructor. constructor. rewrite HeqSetOfElems. intros. unfold In in H1. inversion H1. inversion H2. rewrite H4. Search Intersection. apply Intersection_decreases_r in H3. unfold In. unfold Complement. unfold not. intros. inversion H5. subst. contradiction.
      assumption.

      apply contra in H1. inversion H1. inversion H2. inversion H4. rewrite HeqContraGen in H6. rewrite HeqSetOfElems in H6. unfold In in H6. inversion H6. pose (contra2:= H9 (Complement (Singleton x))). unfold In in contra2.
      assert(exists x0 : point_set X, Intersection N A x0 /\ Complement (Singleton x) = Complement (Singleton x0)). exists x. split. constructor.
      eauto with sets. eauto with sets. trivial. apply contra2 in H11. destruct H11. constructor.
Qed.

Au bureau, on nous a cédé le code source d’un logiciel relativement ancien et dont le précédent propriétaire ne souhaitait pas continuer la maintenance.Si d’ m point de vue business il s’ agissait d’une opportunité des plus lucratives, puisqu’on a hérité d’une base de clients colossales, travailler sur du code qui a dormi parfois pendant près de 10 ans est particulièrement difficile.

Pour dresser une image plus précise, le projet utilise une version antédiluvienne de WxWidgets et de boost, en réimplémentant toutefois les smart pointers (qui étaient probablement encore à l’état de standardisation à l’époque ). On ressent assez rapidement le fait que plusieurs personnes sont passés dessus, avec un étrange mélange de pratique douteuses de développement logiciel (des fichiers entiers copié et collés) qui côtoient les design pattern classiques d’une base de code de taille respectable.

Et bien entendu, il n’y a pas ou peu de tests unitaires rendant chaque tentative de refactoring hasardeuse.

La récente série de posts autour de la customisation de clang-tidy sur le blog de visual c++ tombe à bien nommé :

• https://blogs.msdn.microsoft.com/vcblog/2018/10/19/exploring-clang-tooling-part-1-extending-clang-tidy/
• https://blogs.msdn.microsoft.com/vcblog/2018/10/23/exploring-clang-tooling-part-2-examining-the-clang-ast-with-clang-query/
• https://blogs.msdn.microsoft.com/vcblog/2018/11/06/exploring-clang-tooling-part-3-rewriting-code-with-clang-tidy/

Pour référence pour plus tard je partage le bout de code qui permet de détecter les types std::string, qu’ils apparaissent explicitement ou via un using ou typedef:

auto typeParamMatcher =
		varDecl(hasType(hasUnqualifiedDesugaredType(
     recordType(hasDeclaration(cxxRecordDecl(hasName("basic_string")))))));

Si on supprime le hasUnqualifiedDesugaredType, on peut ne matcher que l’apparition explicite de ce type:

varDecl(hasType(cxxRecordDecl(matchesName("string"))))

Lors de mon précédent billet j’avais présenté comment utiliser les Windows Forms pour afficher une image. J’ai depuis découvert l’existence d’EMGU, un wrapper pour OpenCV qui fournit pas mal de fonctions utilitaires dont certaines pour charger et afficher des images. La plupart des fonctions usuelles de la bibliothèque sont disponibles de façon directe sous le namespace CvInvoke. Ainsi pour charger une image on utilisera imread comme suit :

open Emgu.CV

let img = CvInvoke.Imread(@ »C:\Users\vljno\Desktop\Canardcomission.png »)

Et pour l’afficher on utilisera imshow comme suit :

CvInvoke.Imshow(« nom de fenêtre », img)

CvInvoke.WaitKey(0)

Ce qui ne surprendra pas les personnes ayant déjà utilisé OpenCV dans d’autres langage.

Pour récupérer les données d’une image on utilisera le membre GetData de l’objet Mat retourné par Imread qui donnera un tableau 1d de bytes de l’image. A l’inverse, le membre SetTo permettra de changer le contenu de l’image.

img.GetData ([||])

img.SetTo someArray

En ce moment je découvre les possibilités de F# en matière de scientific computing. F# (prononcé « Fsharp ») est un langage calqué sur OCaml dont il partage la syntaxe de base et une grosse partie de la bibliothèque standard. Quelques fonctionnalités disparaissent (les foncteurs et plus généralement tout ce qui concerne les modules, les types algébriques généralisés), des fonctionnalités sont légèrement retouchées (le quotation mark devient <@… @>, indentation non libre…), en contrepartie le langage a accès à la totalité de l’écosystème DotNet ou leur équivalent Mono et NetCore. Ces environnements étant particulièrement populaires il n’est pas étonnant de voir qu’il existe déjà des bibliothèques pour le calcul statistique, la recherche opérationnelle, les divers algorithmes d’intelligence artificielle, et pour ce qui nous concerne ici l’interfaçage avec des APIs de GPGPU comme OpenCL. Ce qui me donne l’occasion de tester les capacités de F# en tant que langage pour le traitement d’image face à un Python ou à un Matlab.

Commençons déjà par le code permettant de charger une image. De base DotNet fournit la classe Bitmap permettant de charger à peu près n’importe quel format courant et nous proposant d’accéder à ses pixels. Cette dernière est présente dans l’espace System.Drawing (dont il faudra référencer l’assembly) :

open System.Drawing
[<EntryPoint>]
let main argv =
    let img = new Bitmap(@"C:\Users\moi\Documents\fichier.jpg")
    // ….
    0

Afin de vérifier que tout se passe comme attendu il est souhaitable d’afficher cette image. Pour cela nous allons créer un System.Windows.Forms et dessiner l’image dedans via ce code :

open System.Windows.Forms
// ….
let form = new Form(Visible=true)
form.Paint.Add(function e-> e.Graphics.DrawImage(img, e.ClipRectangle, e.ClipRectangle, GraphicsUnit.Pixel))
System.Windows.Forms.Application.Run(form)

Si tout se passe bien vous devriez voir apparaitre votre image à l’écran dans une fenêtre relativement simple.

Maintenant que nous avons chargé notre image nous pouvons nous pencher sur l’utilisation d’OpenCL. Pour cela nous allons passer par la bibliothèque Brahma.OpenCL qui fournit à Fsharp une interface de relativement haut niveau autour d’OpenCL.Net. Cette dernière est disponible via Nuget.
L’initialisation de Brahma est relativement simple, il faut deux objets, un provider (qui représente votre installation OpenCL sur votre machine) et une CommandQueue à laquelle nous soumettrons les tâches que nous voulons effectuer :

open Brahma.OpenCL
open Brahma.FSharp.OpenCL.Core
open Brahma.FSharp.OpenCL.Extensions
open OpenCL.Net
open FSharp.Core
// ….
let provider = ComputeProvider.Create("*", DeviceType.Gpu)
let mutable commandQueue = new Brahma.OpenCL.CommandQueue(provider, provider.Devices |> Seq.head)

Ici nous utiliserons le premier GPU disponible, d’où le Seq.head.

L’avantage de Brahma.OpenCL est qu’elle repose sur les quotations marks pour la création de kernel OpenCL. Une quotation mark est un code F# sous forme d’arbre de syntaxe abstrait, ie une expression qui peut ensuite être passée comme argument à une fonction F#, par exemple pour la modifier, l’interpréter, ou dans le cas de Brahma, la traduire en code OpenCL. Ici nous allons écrire un filtre de Sobel (norme du gradient) prenant en argument un tableau 1d source et un tableau 1d destination (le gradient a besoin des informations des pixels l’entourant, il n’est pas possible de modifier « inplace » les données d’un tableau de façon concurrente. A noter que les quotations mark peuvent capturer des variables comme ici stride.

open Microsoft.FSharp.Quotations
// ….
let stride = img.Height;
let command = <@ fun (range:_2D) (buf:array<byte>) (dst:array<byte>) ->
    let i = range.GlobalID0
    let j = range.GlobalID1
    let mutable h = float32 0.
    if (i > 0 && i < stride) then
        let left = float32 buf.[i - 1 + stride * j]
        let right = float32 buf.[i + 1 + stride * j]
        h <- abs (left - right)
    let mutable v = float32 0.
    if (j > 0) then
        let top = float32 buf.[i + stride * (j - 1)]
        let bottom = float32 buf.[i + stride * (j + 1)]
        v <- abs (top - bottom)
    dst.[i + stride * j] <- byte (sqrt (h * h + v * v)) @>

Bien entendu il n’est pas possible d’écrire n’importe quel code, les kernels OpenCL ne pouvant pas être récursifs par exemple ou appeler des lambdas. La compilation d’une quotation mark sur du code qui ne peut être traduit génèrera une exception.

let kernel, kernelprepare, kernelrun = provider.Compile command

Les valeurs kernelprepare et kernelrun de la compilation permettent respectivement de mettre à disposition les dimensions et arguments (ici les tableaux buf et dst) du kernel au GPU, et d’exécuter ce code kernel via la syntaxe suivante :

kernelprepare d src dst
commandQueue.Add(kernelrun()) |> ignore
commandQueue.Add(dst.ToHost provider).Finish() |> ignore

d est un objet contenant les dimensions du workgroup (global et local) à utilizer pour le kernel, src et dst sont des Arrays F# classiques. On aura au préalable transféré le contenu 2d de img dans src 1d :

let d = _2D(img.Width, img.Height, 8, 8)
let src = Array.init (img.Width * img.Height) (function i -> img.GetPixel(i / stride, i % stride).R)
let dst = Array.zeroCreate (img.Width * img.Height)

Enfin une fois le kernel execute nous copions le contenu de dst dans img :

Array.iteri (fun i (v:byte) -> img.SetPixel(i / stride, i % stride, Color.FromArgb(255, int(v), int(v), int(v)))) dst

Voilà !

Visual Studio 2008 had an Emacs mode that added most commonly used Emacs keybindings in the IDE. VS 2010 later made the feature available as an optional extension which unfortunaly wasn’t carried over on VS 2013. However the source of the extensions were published so that the communit could carry over : https://github.com/zbrad/EmacsKeys

Porting the extension to the latest version of Visual Studio is actually quite easy. It requires enabling Desktop DotNet and Visual Studio SDK feature in the installer though.

Out of the box the solution won’t compile because of missing assemblies : EnvDTE, Microsoft.VisualStudio.Shell.10*. EnvDTE references should be manually replaced by a reference to the envdte.dll assembly on the disk (in Program Files(x86)\Common Files\Microsoft Shared\MSEnv\PublicAssemblies\) ; I’m not sure why VS2017 doesn’t find it automatically to be honest seems it’s registered in a rather standard location.
Microsoft.VisualStudio.Shell.15 (there’s 2 versions available in the reference browser, both are needed) and Microsoft.VisualStudio.Shell.15.Framework will replace the reference to the older Shell.10 ones ; doing so will make the project target the 4.6.2 Framework.

The last piece of the port is to add a Prerequisites in the vsixmanifest file. I suggest adding the base IDE as the sole one.

Next the extension should build properly.

My Android phone was stolen 2 weeks ago and unfortunatly the thieves were able to see my unlock pattern and thus to unlock it and access my gmail account. I could retrieve my account back thanks to google allowing password reset in case of dubious password change. I also hadn’t double authentication enabled which in such circumstance would have been annoying since I obviously couldn’t look at my phone messages anymore.

This leads me to write this small blog post gathering some advices in how to secure your accounts against physical phone access:

• Use the fingerprints readers. I know it’s completely unreliable and fails nearly half of the time to detect your fingerprint but at least it’s unlikely to unlock without your own fingers.
• Get a secondary mail account whose sole purpose is to serve as a password recovery option for your critical web accounts and NEVER access it from your phone or from a device you don’t own.
• Critical web account obviously includes Samsung and/or Google one: since modern phone can be tracked remotely and includes a kill switch it’s the first thing that will be targeted. At least it happened in my case since I could see password reset notification from my Samsung account when I was back home and could restore my access to GMail.
• Two-way authentication is becoming increasingly more popular. It’s probably very efficient to prevent security breach when accessing your account from a third party’s device but it’s also very dangerous if one has access to your phone. Having a spare phone line whose sole purpose is to serve as a second way authentication is likely costly; on the other hand, there are some physical alternative (like Yubi keys) which may be used instead. If you don’t accidently loose it.
• Do regular backup since online service doesn’t always store every data or may need some obscure configuration to work as you may expect. For instance, I lost some of my text messages.
• Don’t use the paypal mobile app. Never.
• Don’t store any password PIN or credit card number as a clear text on your phone. If you have issue remembering a password, try to create one as a visual pattern on a keyboard. Muscle memory often works great in such case.
• Even if unlock pattern are more secure than PIN number since there are at least 9! potential combination instead of 1000 numbers they are also easier to observe and harder to hide ; prefer good old password if possible (for instance as fingerprint fallback option).