Continuation-passing style dans Scala

Question

J'ai lu superficiellement quelques articles de blog/Wikipedia sur le style continuation-passing. Mon objectif de haut niveau est de trouver une technique systématique pour rendre toute fonction récursive (ou, s'il y a des restrictions, en être conscient) récursive. Cependant, j'ai du mal à articuler mes pensées et je ne sais pas si mes tentatives en la matière ont un sens.

Pour les besoins de l'exemple, je proposerai un problème simple. Le but est, donné une liste triée de caractères uniques, de sortir tous les mots possibles faits de ces caractères dans l'ordre alphabétique. Par exemple, sol("op".toList, 3) doit renvoyer ooo,oop,opo,opp,poo,pop,ppo,ppp.

Ma solution récursive est la suivante:

def sol(chars: List[Char], n: Int) = { 
    def recSol(n: Int): List[List[Char]] = (chars, n) match { 
     case (_ , 0) => List(Nil) 
     case (Nil, _) => Nil 
     case (_ , _) => 
      val tail = recSol(n - 1) 
      chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _) 
    } 
    recSol(n).map(_.mkString).mkString(",") 
} 

J'ai essayé de réécrire en ajoutant une fonction en tant que paramètre, mais je ne l'ai pas réussi à faire quelque chose que j'étais convaincu d'être récursive. Je préfère ne pas inclure mes tentatives dans la question car j'ai honte de leur naïveté, alors s'il vous plaît excusez-moi pour cela. Par conséquent, la question est la suivante: comment la fonction ci-dessus serait-elle écrite en CPS?

Answer 1

Essayez que:

import scala.annotation.tailrec 
def sol(chars: List[Char], n: Int) = { 
    @tailrec 
    def recSol(n: Int)(cont: (List[List[Char]]) => List[List[Char]]): List[List[Char]] = (chars, n) match { 
    case (_ , 0) => cont(List(Nil)) 
    case (Nil, _) => cont(Nil) 
    case (_ , _) => 
     recSol(n-1){ tail => 
     cont(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _)) 
     } 
    } 
    recSol(n)(identity).map(_.mkString).mkString(",") 
} 

Answer 2

Le premier ordre du jour dans l'exécution de la CPS transform est de décider sur une représentation pour les continuations. Nous pouvons considérer les continuations comme un calcul suspendu avec un "trou". Lorsque le trou est rempli avec une valeur, le reste du calcul peut être calculé. Ainsi, les fonctions sont un choix naturel pour représenter continuations, au moins pour des exemples de jouets:

type Cont[Hole,Result] = Hole => Result 

Ici Hole représente le type de trou qui doit être rempli et Result représente le type de valeur le calcul calcule en fin de compte. Maintenant que nous avons un moyen de représenter les continuations, nous pouvons nous inquiéter de la transformation CPS elle-même. Fondamentalement, cela implique les étapes suivantes:

• La transformation est appliquée de manière récursive à une expression, en s'arrêtant aux expressions/appels de fonction "triviaux". Dans ce contexte, "trivial" inclut les fonctions définies par Scala (car elles ne sont pas transformées par CPS et n'ont donc pas de paramètre de continuation).
• Nous devons ajouter un paramètre de type Cont[Return,Result] à chaque fonction, où Return est le type de retour de la fonction non transformée et Result est le type du résultat final du calcul dans son ensemble. Ce nouveau paramètre représente la continuation actuelle. Le type de retour pour la fonction transformée est également modifié en Result.
• Chaque appel de fonction doit être transformé pour s'adapter au nouveau paramètre de continuation. Tout après l'appel doit être mis dans une fonction de continuation, qui est ensuite ajoutée à la liste des paramètres.

Par exemple, une fonction:

def f(x : Int) : Int = x + 1 

devient:

def fCps[Result](x : Int)(k : Cont[Int,Result]) : Result = k(x + 1) 

et

def g(x : Int) : Int = 2 * f(x) 

devient:

def gCps[Result](x : Int)(k : Cont[Int,Result]) : Result = { 
    fCps(x)(y => k(2 * y)) 
} 

Maintenant, gCps (5) renvoie (via l'exécution) une fonction qui représente un calcul partiel. Nous pouvons extraire la valeur de ce calcul partiel et l'utiliser en fournissant une fonction de continuation. Par exemple, nous pouvons utiliser la fonction d'identité pour extraire la valeur inchangée:

gCps(5)(x => x) 
// 12 

Ou, nous pouvons imprimer en utilisant println à la place:

gCps(5)(println) 
// prints 12 

Appliqué à votre code, nous obtenons:

def solCps[Result](chars : List[Char], n : Int)(k : Cont[String, Result]) : Result = { 
    @scala.annotation.tailrec 
    def recSol[Result](n : Int)(k : Cont[List[List[Char]], Result]) : Result = (chars, n) match { 
    case (_ , 0) => k(List(Nil)) 
    case (Nil, _) => k(Nil) 
    case (_ , _) => 
     recSol(n - 1)(tail => 
         k(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _))) 
    } 

    recSol(n)(result => 
       k(result.map(_.mkString).mkString(","))) 
} 

Comme vous pouvez le voir, même si recSol est maintenant récursive, il est livré avec le coût de la construction d'une poursuite plus complexe à chaque itération. Donc tout ce que nous avons vraiment fait est d'échanger de l'espace sur la pile de contrôle de la JVM pour de l'espace sur le tas - la transformation CPS ne réduit pas magiquement la complexité de l'espace d'un algorithme.

En outre, recSol est seulement récursif en queue car l'appel récursif à recSol se trouve être la première (non-trivial) expression recSol effectue. En général, cependant, les appels récursifs se dérouleraient dans une continuation. Dans le cas où il y a un appel récursif, nous pouvons contourner cela en transformant seulement appels à la fonction récursive en CPS. Même ainsi, en général, nous ne ferions toujours que de l'espace de pile pour l'espace de tas.