Comment raisonner sur la sécurité de la pile dans Scala Cats / FS2?

13

Voici un morceau de code de la documentation de fs2 . La fonction goest récursive. La question est de savoir comment savoir si elle est sans danger pour la pile et comment raisonner si une fonction est sans danger pour la pile?

import fs2._
// import fs2._

def tk[F[_],O](n: Long): Pipe[F,O,O] = {
  def go(s: Stream[F,O], n: Long): Pull[F,O,Unit] = {
    s.pull.uncons.flatMap {
      case Some((hd,tl)) =>
        hd.size match {
          case m if m <= n => Pull.output(hd) >> go(tl, n - m)
          case m => Pull.output(hd.take(n.toInt)) >> Pull.done
        }
      case None => Pull.done
    }
  }
  in => go(in,n).stream
}
// tk: [F[_], O](n: Long)fs2.Pipe[F,O,O]

Stream(1,2,3,4).through(tk(2)).toList
// res33: List[Int] = List(1, 2)

Serait-il également sûr de la pile si nous appelons god'une autre méthode?

def tk[F[_],O](n: Long): Pipe[F,O,O] = {
  def go(s: Stream[F,O], n: Long): Pull[F,O,Unit] = {
    s.pull.uncons.flatMap {
      case Some((hd,tl)) =>
        hd.size match {
          case m if m <= n => otherMethod(...)
          case m => Pull.output(hd.take(n.toInt)) >> Pull.done
        }
      case None => Pull.done
    }
  }

  def otherMethod(...) = {
    Pull.output(hd) >> go(tl, n - m)
  }

  in => go(in,n).stream
}
Lev Denisov
la source
Non, pas exactement. Bien que si c'est le cas de la récursivité de la queue, veuillez le dire, mais il semble que ce ne soit pas le cas. Autant que je sache, les chats font de la magie appelée trampoline pour assurer la sécurité de la pile. Malheureusement, je ne peux pas dire quand une fonction est trampolinée et quand non.
Lev Denisov
Vous pouvez réécrire gopour utiliser, par exemple, une Monad[F]classe de types - il existe une tailRecMméthode vous permettant d'exécuter le trampoline de manière explicite pour garantir que la fonction sera sécurisée. Je peux me tromper, mais sans cela, vous comptez Fêtre sûr de la pile (par exemple, s'il implémente le trampoline en interne), mais vous ne savez jamais qui définira votre F, donc vous ne devriez pas faire cela. Si vous n'avez aucune garantie que la Fpile est sûre, utilisez une classe de type qui fournit tailRecMcar elle est empilable par la loi.
Mateusz Kubuszok
1
Il est facile de laisser le compilateur le prouver avec une @tailrecannotation pour les fonctions d'enregistrement de queue. Pour les autres cas, il n'y a aucune garantie formelle dans Scala AFAIK. Même si la fonction elle-même est sûre, les autres fonctions qu'elle appelle peuvent ne pas être: /.
yǝsʞǝla

Réponses:

17

Ma réponse précédente donne ici des informations générales qui pourraient être utiles. L'idée de base est que certains types d'effets ont des flatMapimplémentations qui prennent en charge directement la récursivité sans pile - vous pouvez imbriquer les flatMapappels explicitement ou par récursion aussi profondément que vous le souhaitez et vous ne déborderez pas la pile.

Pour certains types d'effet, il n'est pas possible flatMapd'être compatible avec la pile, en raison de la sémantique de l'effet. Dans d'autres cas, il peut être possible d'écrire un coffre-fort flatMap, mais les implémenteurs peuvent avoir décidé de ne pas le faire en raison des performances ou d'autres considérations.

Malheureusement, il n'y a pas de moyen standard (ou même conventionnel) de savoir si flatMappour un type donné est empilable. Les chats incluent une tailRecMopération qui devrait fournir une récursion monadique empilable pour tout type d'effet monadique licite, et parfois regarder une tailRecMimplémentation qui est connue pour être licite peut fournir des indices sur si un flatMapest empilable. Dans le cas, Pullcela ressemble à ceci :

def tailRecM[A, B](a: A)(f: A => Pull[F, O, Either[A, B]]) =
  f(a).flatMap {
    case Left(a)  => tailRecM(a)(f)
    case Right(b) => Pull.pure(b)
  }

tailRecMC'est juste récursion par flatMap, et nous savons que Pull« de Monadl'instance est légitime , ce qui est assez bonne preuve que Pulll » flatMapest - pile de sécurité. Le facteur de complication est ici que l'instance pour Pulla une ApplicativeErrorcontrainte Fqui Pullest le flatMapfait pas, mais dans ce cas ne rien de changement.

Donc l' tkimplémentation ici est stack-safe car flatMapon Pullest stack-safe, et nous le savons en regardant son tailRecMimplémentation. (Si nous creusions un peu plus profondément, nous pourrions comprendre que flatMapc'est empilable car Pullc'est essentiellement un wrapper pour FreeC, qui est trampoliné .)

Il ne serait probablement pas très difficile de réécrire tken termes de tailRecM, bien que nous devions ajouter la ApplicativeErrorcontrainte autrement inutile . Je suppose que les auteurs de la documentation ont choisi de ne pas le faire par souci de clarté, et parce qu'ils savaient Pullque tout allait flatMapbien.


Mise à jour: voici une tailRecMtraduction assez mécanique :

import cats.ApplicativeError
import fs2._

def tk[F[_], O](n: Long)(implicit F: ApplicativeError[F, Throwable]): Pipe[F, O, O] =
  in => Pull.syncInstance[F, O].tailRecM((in, n)) {
    case (s, n) => s.pull.uncons.flatMap {
      case Some((hd, tl)) =>
        hd.size match {
          case m if m <= n => Pull.output(hd).as(Left((tl, n - m)))
          case m => Pull.output(hd.take(n.toInt)).as(Right(()))
        }
      case None => Pull.pure(Right(()))
    }
  }.stream

Notez qu'il n'y a pas de récursivité explicite.


La réponse à votre deuxième question dépend de ce à quoi ressemble l'autre méthode, mais dans le cas de votre exemple spécifique, >>il en résultera simplement plus de flatMapcouches, donc ça devrait aller.

Pour répondre à votre question de manière plus générale, tout ce sujet est un désordre déroutant à Scala. Vous ne devriez pas avoir à fouiller dans les implémentations comme nous l'avons fait ci-dessus juste pour savoir si un type prend en charge ou non la récursion monadique empilable. De meilleures conventions autour de la documentation seraient une aide ici, mais malheureusement nous ne faisons pas un très bon travail. Vous pouvez toujours utiliser tailRecMpour être «sûr» (c'est ce que vous voudrez faire quand le F[_]est générique, de toute façon), mais même alors, vous êtes confiant que l' Monadimplémentation est légale.

Pour résumer: c'est une mauvaise situation tout autour, et dans des situations sensibles, vous devez absolument écrire vos propres tests pour vérifier que les implémentations comme celle-ci sont compatibles avec la pile.

Travis Brown
la source
Merci pour l'explication. En ce qui concerne la question lorsque nous appelons god'une autre méthode, qu'est-ce qui peut rendre la pile dangereuse? Si nous faisons des calculs non récursifs avant d'appeler, Pull.output(hd) >> go(tl, n - m)ça va?
Lev Denisov
Oui, cela devrait être bien (en supposant que le calcul lui-même ne déborde pas la pile, bien sûr).
Travis Brown
Quel type d'effet, par exemple, ne serait pas compatible avec la pile pour la récursivité monadique? Le type de continuation?
bob
@bob droit, bien que les chats de ContTl » flatMap est en fait pile de sécurité (via une Defercontrainte sur le type sous - jacent). Je pensais plutôt à quelque chose comme List, où la récurrence flatMapn'est pas empilable (elle a cependant un caractère légal tailRecM).
Travis Brown