Acquis d'apprentissage

A la fin du cours, les étudiants devraient maîtriser les techniques de base en programmation fonctionnelle et logique et leurs incarnations dans les langages Haskell et Prolog.

Objectifs

L'objectif du cours est d'exposer une introduction aux techniques de programmation fonctionnelle et logique. 

Contenu

Ce cours vise à étudier le paradigme de programmation fonctionnelle et logique. Pour chaque paradigme, on y présente d'abord les concepts de base (fonction, réduction, évaluation, pour la programmation fonctionnelle, logique de Horn, stratégie de sélection, négation) avant d'aborder des sujets plus avancés, comme les fonctions d'ordre supérieur, les types polymorphes, les monades ou encore quelques exemples de programmation non déterministe. Une attention particulière est aussi portée aux techniques de programmation adaptées à ces paradigmes.

 

Table des matières

Partie 1: Programmation déclarative 1. Programmation fonctionnelle (Haskell) - Valeurs, expressions et réductions - Stratégies de réduction et l'évaluation paresseuse - Les expressions lambda - Fonctions à plusieurs arguments (currying) - Opérateurs - Composition de fonctions - Signatures de type polymorphes - Récursion terminale - Types algébriques: énumeration, union, types produits - Le polymorphisme dans les définitions de type - Fonctions élémentaires - Preuve par induction structurelle - Les listes infinies 2. Programmation logique (Prolog) - De la programmation fonctionnelle à la programmation logique - Eléments de base de la programmation logique - Structures de données élémentaires - Programmation non-déterministe - Quelques particularités de Prolog : programmation d'ordre supérieur et l'opérateur cut - Les "difference lists" - Introduction à la méta-programmation 

Méthodes d'enseignement

Le cours est conçu comme une suite d'exposés où se mèlent théorie et applications pratiques. Aux travaux pratiques, les étudiants sont amenés à des travaux de synthèse prenant la forme d'exercices de programmation de taille moyenne.

Méthode d'évaluation

Cet unité d'enseignement est globalement évalué au moyen d'un examen écrit où l'étudiant se voit confronté à des questions de compréhension, de connaissance et d'application. 

Sources, références et supports éventuels

  • S. Russel et P. Norvicq, Artificial Intelligence: a Modern Approach. Prentice Hall, 2003G. Hutton, Programming in Haskell. Cambridge 2007.
  • S. Thompson, The Craft of Functional Programming, Pearson 1999.
  • R. Bird, Introduction to Functional Programming using Haskell, Prentice-Hall, 1998.
  • P. Hudak, J. Peterson, J. Fasel. A Gentle Introduction to Haskell. Available on-line at http://www.haskell.org/tutorial
  • S. Peyton-Jones (ed.). Haskell 98 Language and Libraries - The Revised Report
  • H. Abelson, G.J. Sussman, J. Sussman. Structure and Interpretation of Computer Programs. The MIT Press, 1985
  • A. Aho, J. Ullman. Concepts fondamentaux de l'informatique. Freeman and Company, 1992. Dunod, Paris, 1993.
  • W. F. Clocksin and C. S. Mellish, Programming in Prolog, 2003.
  • M. Bramer, Logic Programming with Prolog, Springer, 2005.
  • U. Nilsson and J. Maluszynski, Logic, Programming and Prolog (2ed), John Wiley & Sons Ltd.
  • L. Sterling, E. Shapiro. The art of Prolog. MIT Press, 1986.
  • Y. Deville. Logic Programming: Systematic Program Development. Addison-Wesley, 1990.

Langue d'instruction

Formation Programme d’études Bloc Crédits Obligatoire
Bachelier en sciences informatiques Standard 0 5
Bachelier en sciences informatiques Standard 3 5