Continuations: théorie et pratique

ULG-INFO-XXX -- D. Ribbens -- 30-30-0 -- Cours de 2ème cycle

Objectif

La notion de continuation est un concept fondamental en informatique car elle représente la suite du calcul. Ce cours a pour but l'étude de cette notion et de ses principaux usages.

Prérequis

• Connaissance d'un langage fonctionnel.
  ULG-INFO-054: Eléments de programmation
  ULG-INFO-055: Aspects sémantiques de la programmation

Contenu

Le cours se compose de deux parties.

1. La première partie porte sur la définition de la notion de continuation. Diverses représentations de la continuation sont étudiées:
   1. Le style par passage de continuations est une technique de programmation représentant explicitement la continuation par une fonction.
   2. La notion de contexte, basée sur une représentation lexicale du programme, est équivalente à la notion de continuation, et en fournit une représentation symbolique.
   3. Un type abstrait de données permet de représenter les continuations par des blocs d'activation.
   En complément de la théorie, ce cours présente aussi les utilisations pratiques des continuations. En utilisant le style par passage de continuations, on introduit la programmation par exception et le backtracking. L'on étudie également la façon d'implanter des interpréteurs en utilisant les continuations.

   Les techniques décrites dans cette partie sont applicables à la majorité des langages de programmation.

2. Certains langages, tels que Scheme, possèdent des continuations de première classe, c'est-à-dire que ces dernières ont le même statut que les valeurs numériques (elles peuvent être composantes d'une structure de données, paramètres ou résultats d'une procédure, etc.). La seconde partie du cours a pour but leur étude, des points de vue théorique et pratique. Dans un premier temps, les continuations de première classe sont implantées dans un évaluateur métacirculaire. Dans une deuxième étape, des techniques de programmation les utilisant sont présentées. A nouveau, exceptions, backtracking, mais aussi espaces d'états sont étudiés.

Pédagogie

Exercices sur la matière théorique.

Références