Continuation Passing Style (CPS)

6.3 Continuation Passing Style (CPS)

Cette transformation permet d'expliciter le contrôle de l'exécution du programme en donnant à chaque fonction un argument supplémentaire correspondant à la continuation de son calcul. Cette continuation est une fermeture qui s'appliquera au résultat de la fonction. Cette technique a été initialement utilisée pour le compilateur Lisp (Rabbit[]). SML/NJ ([]) l'utilise dans sa dernière version (0.66).

Nous allons l'étudier sur un exemple en utilisant la syntaxe Caml. Soit une fonction count qui prend un prédicat et une liste et retourne le nombre d'éléments de la liste qui vérifient ce prédicat, et une fermeture countZeros qui correspond à l'application partielle de count à un prédicat qui retourne true si son argument vaut 0, et false sinon.

let count pred = 
  let rec f a = if null a 
            then 0 
            else if pred(hd a) 
                 then 1+f(tl a)
                 else f (tl a)
  in f
;;

let countZeros = count (function i -> if i=0 
                                      then true 
                                      else false)
;;

La transformation modifie chaque fonction en lui rajoutant un argument supplémentaire (la continuation) et revient de la fonction en appelant la continuation :

let count (pred,c1) = 
  let rec f (a,c2) = 
    if null a 
    then c2(0) 
    else 
     let c3 b = 
       if b  
       then 
         let  c4(i) =c2(1+i)
         in 
           f(tl(a),c4)
       else
         let c5(i)=c2(i)
         in f(tl(a),c5)
     in 
       pred((hd a),c3)
  in c1(f)
;;

let   countZeros  = ...
;;

Le contrôle de la fonction count est devenu explicite. Ce résultat se prête à plusieurs optimisations. Ici la continuation c5 est inutile car identique à c2 et peut donc être supprimée.
La variable countZeros devient :

let countZeros m = let g i = if i=0 then true else false in count g m
;;

et peut donc se réécrire ainsi :

let countZeros (m,c0) = 
  let g (i,c1) = 
    if i=0 
    then c1(true) 
    else c1(false) 
 in 
    let c3(a) = a
    in 
      let c2(a) = (a (m,c3))
      in
        c0(count(g,c2))
;;

En fait, il aurait été plus astucieux d'expanser dans le corps de countZeros la fonction count car elle est suffisamment petite et non-récursive.

Comme le but de cette transformation est aussi d'aplatir le programme, une phase de conversion des fermetures est utile pour ranger les variables libres dans un enregistrement (premier argument de la fonction), à la manière du l-lifting. Un appel d'une fonction a trois arguments : l'enregistrement des variables libres de la fermeture, les arguments utilisateur, et la continuation.