Logique combinatoire et lambda calcul : des logiques d'opérateurs

Le but de cet ouvrage est de présenter la Logique Combinatoire développée principalement par Curry. Pour les auteurs, la Logique Combinatoire est pensée comme une logique d?opérateurs, de composition et de transformations intrinsèques d?opérateurs où la seule opération de base est l?application d?un opérateur à un opérande. Elle est utilisée pour fournir des fondements logiques aux langages de programmation fonctionnels bien que la plupart des approches prennent appui sur le -calcul de Church. Alors que le -calcul fait appel à des variables liées pour formaliser la notion de fonction comme opérateur, la Logique Combinatoire n?utilise aucune variable liée, elle prend la notion d?opérateur comme première et apparaît de ce fait comme plus simple, conduisant à une véritable algèbre des opérateurs. Ainsi, il est plus facile d?analyser la sémantique des langues naturelles et les représentations cognitives et des connaissances, avec les outils formels (les combinateurs) et les types fonctionnels de La Logique Combinatoire.

Mots clés : Logique Combinatoire, -calcul, types fonctionnels, paradoxe, opérateur, opération, fonction, formalisme applicatif, combinateur, prédicat, Church-rosser.

Liste des figures
Liste des tableaux

Chapitre I : Langages applicatifs : présentation
1. Fonction (au sens mathématique)
2. Systèmes concaténationels
3. Systèmes applicatifs
4. Quelques représentations applicatives

Chapitre II : Logique Combinatoire
1. Règles d’introduction et d’élimination
2. Expressions combinatoires
3. Forme normale
4. bêta-égalité
5. Calcul inférentiel sur les expressions combinatoires
6. Opérations d’abstraction et de substitution sur les expressions combinatoires

Chapitre III : Quelques exemples illustratifs du fonctionnement des combinateurs
1. Combinateur W
2. Combinateur de composition B
3. Combinateur C
4. Combinateurs B et W
5. Combinateurs B, C et S
6. Combinateur K
7. Combinateur C+
8. Quelques prédicats complexes

Chapitre IV : Algèbre des expressions combinatoires et des combinateurs
1. Quelques définitions
2. Produit d’expressions combinatoires
3. Elévation d’une expression combinatoire X à une puissance nième : Xn
4. Combinateurs agissant à distance : X(n)
5. Ordre et degré d’un combinateur
6. Combinateurs étoilés (star *)
7. Inverse d’un combinateur
8. Les combinateurs Sn et (Phi)n
9. Les combinateurs Zn
10. La suite des expressions combinatoires X[n]
11. Suite des expressions combinatoires X[n]
12. Suites définies par itération
13. Constructeur de point fixe .
14. Définition intrinsèque des propriétés d’une opération interne, relative à des objets

Chapitre V :  λ CALCUL
1. Définition des λ-expressions
2. β-réduction et β-expansion
3. Forme normale d’une λ-expression
6. Théories inférentielles de la β-réduction et de la β-égalité
7. Logique combinatoire et λ-calcul : comparaison

Chapitre VI : Logique combinatoire et paradoxes
1. Paradoxe de Curry
2. Les opérateurs constructeurs de points fixes
3. Auto-applicativité

Chapitre VII : Types et expressions combinatoires typées
1. Sortes, types et construction de types
2. Curryfication
3. Types fonctionnels
4. Types logiques
5. Utilisations diverses de la théorie des types fonctionnels dans différents domaines
6. Catégories syntaxiques comme types fonctionnels
7. Schémas de type des combinateurs
8. Représentations graphiques des combinateurs élémentaires

Conclusion
Annexe : corrigé de quelques exercice