Que sont les suites Scala et pourquoi les utiliser?

Je viens de terminer la programmation dans Scala , et j'ai étudié les changements entre Scala 2.7 et 2.8. Celui qui semble être le plus important est le plugin de continuations, mais je ne comprends pas à quoi il sert ni comment il fonctionne. J'ai vu que c'était bon pour les E / S asynchrones, mais je n'ai pas été en mesure de savoir pourquoi. Certaines des ressources les plus populaires sur le sujet sont les suivantes:

• Suites délimitées et Scala
• Aller à Scala
• Un avant-goût de 2,8: les suites
• Continuations délimitées expliquées (en Scala)

Et cette question sur Stack Overflow:

• Quelles sont les principales différences entre Scala 2.8 et Scala 2.7?

Malheureusement, aucune de ces références n'essaie de définir à quoi servent les continuations ou ce que les fonctions de décalage / réinitialisation sont censées faire, et je n'ai trouvé aucune référence qui le fasse. Je n'ai pas été en mesure de deviner comment les exemples dans les articles liés fonctionnent (ou ce qu'ils font), donc une façon de m'aider pourrait être de parcourir l'un de ces exemples ligne par ligne. Même ce simple extrait du troisième article:

reset {
    ...
    shift { k: (Int=>Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8

Pourquoi le résultat est-il 8? Cela m'aiderait probablement à démarrer.

Mon blog explique quoi resetet shiftfaire, alors vous voudrez peut-être le relire.

Une autre bonne source, que je mentionne également dans mon blog, est l'entrée de Wikipedia sur le style de passage de continuation . Celui-ci est, de loin, le plus clair sur le sujet, bien qu'il n'utilise pas la syntaxe Scala, et la suite est explicitement passée.

L'article sur les suites délimitées, auquel je renvoie dans mon blog mais qui semble être devenu cassé, donne de nombreux exemples d'utilisation.

Mais je pense que le meilleur exemple du concept de suites délimitées est Scala Swarm. Dans celui-ci, la bibliothèque arrête l'exécution de votre code à un moment donné, et le calcul restant devient la continuation. La bibliothèque fait alors quelque chose - dans ce cas, le transfert du calcul vers un autre hôte, et renvoie le résultat (la valeur de la variable qui a été accédée) au calcul qui a été arrêté.

Maintenant, vous ne comprenez même pas l'exemple simple sur la page Scala, alors ne lisez mon blog. Dans ce document, je me préoccupe uniquement d'expliquer ces bases, de savoir pourquoi le résultat est 8.

J'ai trouvé que les explications existantes étaient moins efficaces pour expliquer le concept que je ne l'espérerais. J'espère que celui-ci est clair (et correct.) Je n'ai pas encore utilisé les suites.

Lorsqu'une fonction de continuation cfest appelée:

1. L'exécution saute le reste du shiftbloc et recommence à la fin
   • le paramètre passé cfest ce à quoi le shiftbloc "évalue" pendant que l'exécution se poursuit. cela peut être différent pour chaque appel àcf
2. L'exécution se poursuit jusqu'à la fin du resetbloc (ou jusqu'à un appel à resets'il n'y a pas de bloc)
   • le résultat du resetbloc (ou le paramètre de reset() s'il n'y a pas de bloc) est ce qui cfretourne
3. L'exécution se poursuit cfjusqu'à la fin du shiftbloc
4. L'exécution saute jusqu'à la fin du resetbloc (ou un appel à réinitialiser?)

Donc, dans cet exemple, suivez les lettres de A à Z

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

Cela imprime:

11
101

Compte tenu de l'exemple canonique du document de recherche pour les suites délimitées de Scala, légèrement modifié de sorte que la fonction saisie shiftreçoit le nom fet n'est donc plus anonyme.

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

Le plugin Scala transforme cet exemple de telle sorte que le calcul (dans l'argument d'entrée de reset) à partir de chacun shiftjusqu'à l'invocation de resetsoit remplacé par la fonction (par exemple f) entrée à shift.

Le calcul remplacé est déplacé (c'est-à-dire déplacé) dans une fonction k. La fonction entre fla fonction k, où k contient le calcul remplacé, les kentrées x: Intet le calcul kremplace shift(f)par x.

f(k) * 2
def k(x: Int): Int = x + 1

Ce qui a le même effet que:

k(k(k(7))) * 2
def k(x: Int): Int = x + 1

Notez que le type Intdu paramètre d'entrée x(c'est-à-dire la signature de type de k) a été donné par la signature de type du paramètre d'entrée de f.

Un autre exemple emprunté avec l'abstraction conceptuellement équivalente, c'est read-à- dire la fonction entrée dans shift:

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

Je crois que cela se traduirait par l'équivalent logique de:

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

J'espère que cela élucide l'abstraction commune cohérente qui a été quelque peu obscurcie par la présentation préalable de ces deux exemples. Par exemple, le premier exemple canonique a été présenté dans le document de recherche comme une fonction anonyme, au lieu de mon nom f, il n'était donc pas immédiatement clair pour certains lecteurs qu'il était abstraitement analogue à celui readdu deuxième exemple emprunté .

Ainsi, des suites délimitées créent l'illusion d'une inversion de contrôle de «tu m'appelles de l'extérieur de reset» à «je t'appelle à l'intérieur reset».

Notez que le type de retour de fest, mais kn'est pas, requis pour être le même que le type de retour de reset, c'est-à-dire qu'il fa la liberté de déclarer n'importe quel type de retour ktant que frenvoie le même type que reset. Idem pour readet capture(voir aussi ENVci-dessous).

Les suites délimitées n'inversent pas implicitement le contrôle de l'état, par exemple readet callbackne sont pas de pures fonctions. Ainsi, l'appelant ne peut pas créer d'expressions référentiellement transparentes et n'a donc pas de contrôle déclaratif (aka transparent) sur la sémantique impérative prévue .

Nous pouvons explicitement réaliser des fonctions pures avec des suites délimitées.

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

Je crois que cela se traduirait par l'équivalent logique de:

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

Cela devient bruyant, à cause de l'environnement explicite.

Notez tangentiellement, Scala n'a pas l'inférence de type global de Haskell et donc, pour autant que je sache, ne peut pas supporter le levage implicite vers une monade d'État unit(comme une stratégie possible pour cacher l'environnement explicite), parce que l'inférence de type global (Hindley-Milner) de Haskell dépend de la non prise en charge de l'héritage virtuel multiple de diamant .

La continuation capture l'état d'un calcul, à invoquer ultérieurement.

Pensez au calcul entre la sortie de l'expression de décalage et la sortie de l'expression de réinitialisation en tant que fonction. Dans l'expression de décalage, cette fonction est appelée k, c'est la continuation. Vous pouvez le faire circuler, l'invoquer plus tard, voire plus d'une fois.

Je pense que la valeur renvoyée par l'expression de réinitialisation est la valeur de l'expression à l'intérieur de l'expression de décalage après le =>, mais je ne suis pas tout à fait sûr de cela.

Ainsi, avec les continuations, vous pouvez intégrer un morceau de code plutôt arbitraire et non local dans une fonction. Cela peut être utilisé pour implémenter un flux de contrôle non standard, tel que le coroutining ou le backtracking.

Les continuations doivent donc être utilisées au niveau du système. Les saupoudrer dans le code de votre application serait une recette sûre pour des cauchemars, bien pire que le pire code de spaghetti utilisant goto ne pourrait jamais être.

Avertissement: Je n'ai pas de compréhension approfondie des continuations dans Scala, je viens de le déduire en regardant les exemples et en connaissant les suites de Scheme.

De mon point de vue, la meilleure explication a été donnée ici: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Un des exemples:

Pour voir le flux de contrôle un peu plus clairement, vous pouvez exécuter cet extrait de code:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

Voici la sortie que le code ci-dessus produit:

A
B
D
E
G
F
C

Un autre article (plus récent - mai 2016) sur les suites de Scala est:
" Voyage dans le temps à Scala: CPS à Scala (suite de scala) " par Shivansh Srivastava ( shiv4nsh) .
Il se réfère également à Jim McBeath l ' article mentionné dans Dmitry Bespalov ' s réponse .

Mais avant cela, il décrit les Continuations comme ceci:

Une continuation est une représentation abstraite de l'état de contrôle d'un programme informatique .
Donc, ce que cela signifie en fait, c'est qu'il s'agit d'une structure de données qui représente le processus de calcul à un moment donné de l'exécution du processus; la structure de données créée est accessible par le langage de programmation, au lieu d'être masquée dans l'environnement d'exécution.

Pour l'expliquer davantage, nous pouvons avoir l'un des exemples les plus classiques,

Disons que vous êtes dans la cuisine devant le réfrigérateur, en train de penser à un sandwich. Vous prenez une suite juste là et vous la mettez dans votre poche.
Ensuite, vous sortez de la dinde et du pain du réfrigérateur et vous vous préparez un sandwich, qui est maintenant posé sur le comptoir.
Vous invoquez la suite dans votre poche, et vous vous retrouvez à nouveau debout devant le réfrigérateur, pensant à un sandwich. Mais heureusement, il y a un sandwich sur le comptoir, et tous les matériaux utilisés pour le fabriquer ont disparu. Alors vous le mangez. :-)

Dans cette description, le sandwichfait partie des données du programme (par exemple, un objet sur le tas), et plutôt que d'appeler une make sandwichroutine « » puis de revenir, la personne appelle une make sandwich with current continuationroutine « », qui crée le sandwich puis continue là où l'exécution laisser derrière soi.

Cela étant dit, comme annoncé en avril 2014 pour Scala 2.11.0-RC1

Nous recherchons des mainteneurs pour prendre en charge les modules suivants: scala-swing , scala-continuations .
2.12 ne les inclura pas si aucun nouveau responsable n'est trouvé .
Nous continuerons probablement à maintenir les autres modules (scala-xml, scala-parser-combinators), mais l'aide est toujours grandement appréciée.

Continuations de Scala via des exemples significatifs

Définissons ce from0to10qui exprime l'idée d'itération de 0 à 10:

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

Maintenant,

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

imprime:

0 1 2 3 4 5 6 7 8 9 10 

En fait, nous n'avons pas besoin x:

reset {
  print(s"${from0to10()} ")
}
println()

imprime le même résultat.

Et

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

imprime toutes les paires:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

Maintenant, comment ça marche?

Il y a le code appelé , from0to10et le code d'appel . Dans ce cas, c'est le bloc qui suit reset. L'un des paramètres passés au code appelé est une adresse de retour qui montre quelle partie du code appelant n'a pas encore été exécutée (**). Cette partie du code d'appel est la suite . Le code appelé peut faire avec ce paramètre tout ce qu'il décide de faire: lui passer le contrôle, ou l'ignorer, ou l'appeler plusieurs fois. Ici from0to10appelle cette continuation pour chaque entier dans la plage 0..10.

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

Mais où finit la suite? Ceci est important parce que la dernière returndes déclarations de continuation le contrôle au code appelé, from0to10. Dans Scala, il se termine là où lereset bloc se termine (*).

Maintenant, nous voyons que la suite est déclarée comme cont: Int => Unit. Pourquoi? Nous invoquons from0to10as val x = from0to10(), et Intest le type de valeur qui va vers x. Unitsignifie que le bloc aprèsreset doit renvoyer aucune valeur (sinon il y aura une erreur de type). En général, il existe 4 signatures de type: entrée de fonction, entrée de continuation, résultat de continuation, résultat de fonction. Tous les quatre doivent correspondre au contexte d'appel.

Ci-dessus, nous avons imprimé des paires de valeurs. Imprimons la table de multiplication. Mais comment sortons-nous\n après chaque ligne?

La fonction backnous permet de spécifier ce qui doit être fait lorsque le contrôle revient, de la suite au code qui l'a appelé.

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

backappelle d'abord sa continuation, puis exécute l' action .

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

Il imprime:

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

Eh bien, maintenant il est temps pour certains cerveaux. Il existe deux invocations de from0to10. Quelle est la suite pour le premier from0to10? Il suit l'appel de from0to10dans le code binaire , mais dans le code source, il comprend également l'instruction d'affectation val i =. Il se termine là où le resetbloc se termine, mais la fin du resetbloc ne renvoie pas le contrôle au premier from0to10. La fin du resetbloc renvoie le contrôle au 2nd from0to10, qui à son tour retourne finalement le contrôle à back, et c'est cela backqui renvoie le contrôle au premier appel de from0to10. Quand la première (oui! La 1ère!) from0to10Sort, l'ensemblereset bloc est quitté.

Une telle méthode de retour de contrôle est appelée retour arrière , c'est une technique très ancienne, connue au moins depuis l'époque des dérivés Lisp orientés Prolog et AI.

Les noms resetet shiftsont des noms erronés. Ces noms auraient mieux dû être laissés pour les opérations au niveau du bit. resetdéfinit les limites de continuation et shiftprend une continuation de la pile d'appels.

Remarques)

(*) Dans Scala, la suite se termine là où le resetbloc se termine.Une autre approche possible serait de le laisser se terminer là où la fonction se termine.

(**) L'un des paramètres du code appelé est une adresse de retour qui montre quelle partie du code appelant n'a pas encore été exécutée. Eh bien, dans Scala, une séquence d'adresses de retour est utilisée pour cela. Combien? Toutes les adresses de retour placées sur la pile d'appels depuis l'entrée dans le resetbloc.

UPD Partie 2 Annulation des continuations: filtrage

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

Cela imprime:

0 2 4 6 8 10 

Retenons deux opérations importantes: abandonner la continuation ( fail()) et lui passer le contrôle ( succ()):

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

Les deux versions de succ()(ci-dessus) fonctionnent. Il s'avère que cela shifta une signature amusante, et bien que succ()ne fasse rien, il doit avoir cette signature pour l'équilibre de type.

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

comme prévu, il imprime

0 2 4 6 8 10

Dans une fonction, succ()n'est pas nécessaire:

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

encore une fois, il imprime

0 2 4 6 8 10

Maintenant, définissons onOdd()via onEven():

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

Au-dessus, si xest pair, une exception est levée et la continuation n'est pas appelée; si xest impair, l'exception n'est pas levée et la suite est appelée. Le code ci-dessus s'imprime:

1 3 5 7 9