INTRODUCTION

L'Institut de la Francophonie pour l'Informatique (IFI) est un institut de l'Agence Universitaire de la Francophonie (AUF) dont les activités de recherche sont spécialisées dans la Formation à distance. Ce cours a été réalisé par Mlle Vo Thi Huyen Chi, étudiante de la promotion 6 de l'IFI avec le soutien actif et financier le l'Agence universitaire de la Francophonie. Ce cours a été réalisé à Institut de la Francophonie pour l'Informatique sous la direction du professeur Patrick Bellot, directeur des études de l'institut.

Le cours de " Théorie des combinateurs " est un cours d'informatique théorique donné à l'Institut de la Francophonie pour l'Informatique en deuxième année. Ce cours a aussi été donné pendant de nombreuses années à l'Ecole nationale supérieure des télécommunications à Paris dans le cadre plus général d'un cours sur les fondements logiques de la programmation. Il a aussi été donné en Magistère d'Informatique d'Ile de France à l'université de René Descartes (Paris 5) pendant plusieurs années également.

Prérequis.

Ce cours en général très apprécié des élèves a pour objet d'apporter une compréhension fine des mécanismes calculatoires à l'oeuvre dans les langages de programmation. Les techniques mathématiques utilisées dans ce cours ne sont pas celles des mathématiques classiques (analyse, algèbre, géométrie, etc.) et ce cours ne demande qu'une aptitude raisonnable aux mathématiques. La connaissance d'un langage de programmation fonctionnelle de type Lisp, Scheme ou ML serait un plus mais elle n'est pas véritablement nécessaire.

Contenu.

La chapitre 2 établit les bases nécessaires, langage et conventions, à la compréhension du cours. Ce chapitre est un prérequis pour la suite du cours. Le chapitre 3 introduit la théorie des combinateurs de manière informelle avec de nombreux exemples et exercices dynamique où l'auditeur pourra pratiquer le calcul dans la théorie des combinateurs. Le chapitre 4 décrit la théorie d'une manière formelle sous la forme d'un système de déduction naturelle. Ceci est indispensable si l'on veut démontrer les résultats fondamentaux de la théorie. Cette partie constitue également une introduction aux systèmes formels. Le chapitre 5 montre comment les mécanismes des langages informatiques peuvent être modélisés en utilisant les combinateurs. On étudie en particulier les structures de données classiques (entiers, booléens, listes). On étudie également les dessous de la notion de définition récursive. Et enfin, on étudie les mécanismes d'évaluation dans les langages de programmation. Le chapitre 6 montre une mise en oeuvre astucieuse des combinateurs appelée Machine SK de Turner.