Introduction à PLFA et Agda

PLFA.github.io (Programming Language Foundations in Agda) est un projet open source qui utilise le langage Agda pour enseigner les fondements de la théorie des langages de programmation. Il fournit un environnement interactif pour construire des preuves formelles, mettant l'accent sur l'induction et les nombres naturels. Ce guide explore des exemples pratiques pour acquérir une compréhension solide de ces concepts.

L'importance de l'induction en informatique

L'induction est une méthode essentielle pour prouver la correction des programmes et l'analyse des algorithmes. PLFA offre un parcours structuré avec des preuves vérifiables dans Agda, permettant aux apprenants de pratiquer la vérification formelle.

Définition des nombres naturels

Dans Agda, les nombres naturels sont définis de manière récursive avec deux constructeurs :

• zero : le cas de base représentant zéro.
• suc n : le cas indutcif représentant le successeur de n.

Cette structure adaptée à l'induction se compose de deux étapes : la base (pour zero) et l'étape inductive (pour suc n en supposant la propriété vraie pour n).

Exemple pratique : preuve de l'associativité de l'addition

Considérons la propriété d'associativité : (a + b) + c ≡ a + (b + c) pour tous nombres naturels a, b, c. Dans Agda, nous pouvons la prouver par induction sur a.

associAdd : ∀ (x y z : ℕ) → (x + y) + z ≡ x + (y + z)
associAdd zero y z = 
  begin
    (zero + y) + z  ≡⟨⟩  y + z  ≡⟨⟩  zero + (y + z)
  ∎
associAdd (suc x) y z = 
  begin
    (suc x + y) + z
  ≡⟨⟩  suc (x + y) + z
  ≡⟨⟩  suc ((x + y) + z)
  ≡⟨ cong suc (associAdd x y z) ⟩  suc (x + (y + z))
  ≡⟨⟩  suc x + (y + z)
  ∎

Cette preuve utilise une chaîne d'équations et applique l'hypothèse inductive via cong (congruence).

Techniques avancées : de l'associativité à la commutativité

Pour prouver la commutativité a + b ≡ b + a, nous avons besoin de deux lemmes auxiliaires :

1. L'identité à droite : a + zero ≡ a
2. Le successeur : a + suc b ≡ suc (a + b)

Avec ces lemmes, la preuve de commutativité devient :

commAdd : ∀ (u v : ℕ) → u + v ≡ v + u
commAdd u zero = identDroite u  -- où identDroite prouve u + zero ≡ u
commAdd u (suc v) = begin
  u + suc v    ≡⟨ sucLemma u v ⟩  -- sucLemma prouve u + suc v ≡ suc (u + v)
  suc (u + v)  ≡⟨ cong suc (commAdd u v) ⟩
  suc (v + u)  ≡⟨⟩
  suc v + u
∎

Ressources d'apprentissage

Pour progresser dans PLFA, il est recommandé de :

• Commencer par les définitions de base des nombres naturels.
• Pratiquer des preuves comme l'associativité et la commutativité de la multiplication.
• Utiliser l'environnement interactif d'Agda (par exemple, le mode Emacs) pour inspecter les objectifs de preuve.
• Explorer des concepts plus avencés tels que l'égalité et les systèmes de types.

Ces compétences fondent une base solide pour la vérification formelle et la théorie des types, applicables dans des domaines comme la sécurité des protocoles et la conception de logiciels fiables.