Programmation Fonctionnelle et Sémantique
Master 1 d'informatique (2008 - 2009)
Solange Coupet-Grimal
__________________________________________________________________________________________
-
Partie I - Caml : un langage fonctionnel
Notes de cours (pdf)
- Programmations impérative et fonctionnelle.
- Syntaxe, sémantiques statique et dynamique.
- Expressions et évaluations. Définitions.
- Types de base et produit cartésien
- Expressions fonctionnelles.
- Polymorphisme, ordre supérieur et curryfication.
- Fonctions récursives et mutuellement récursives.
- Filtrage.
-
Partie II - Sémantique opérationnelle: première approche
Notes de cours (pdf)
- Evaluations par nom et par valeur
- Stratégie d'évaluation dans Caml
- Application à la définition d'un opérateur de point fixe
-
Partie III - Les types
Notes de cours (pdf1, pdf2)
- Le type List
- Définition de types
- Sommes
- Types récursifs
- Types polymorphes
- Retour sur le filtrage
- Récurseurs sur les arbres quelconques
- La sémantique opérationnelle revisitée
- Liaisons, environnements, clôtures
- Evaluation des fonctions récursives
-
Partie IV - Aspects impératifs du langage Caml
Notes de cours (pdf)
- Exceptions
- Entrées-Sorties
- Séquencement
- Fichiers
- Références
- Egalité de valeurs et égalité physique. La construction as.
- Tableaux
- Enregistrements
- Listes circulaires
-
Partie V - Implantation du filtrage en Caml
Notes de cours (pdf)
-
Termes formels, substitutions, filtrage
-
Partie VI - Sémantique dénationnelle
- Le lambda calcul simplement typé
Notes de cours (pdf)
- Syntaxe des termes, variables libres et liées.Règles de typage
- Beta et Eta conversions
- Equations
- Modèles : interprétation des jugements de typage
-
Extension à PCF, la règle µ. Comment interpréter la règle µ?
Notes de cours (pdf)
-
Points fixes dans les ordres partiels complets
: le théorème de Tarski. Exemple des grammaires HC.
- Sémantique par point fixe de PCF
- Cours de clôture: Survol des différentes approches sémantiques:
- Sémantiques opérationnelles
- par transitions (cas des langages impératifs et des langages fonctionnels)
- sémantiques naturelles (cas des langages impératifs et des langages fonctionnels)
- Machine abstraite de Landin
- Sémantiques dénotationnelles
- Cas fonctionnel : c'est ce qui a été présenté en détails
- Exemple d'un petit langage impératif
__________________________________________________________________________________________
Quelques références Bibliographiques
_____________________________________________________________________________________________
TD1
Le premier ordre et l'ordre supérieur
(pdf)
TD2
Les listes
(pdf)
__________________________________________________________________________________________