¿Cómo razonar sobre la seguridad de la pila en Scala Cats / fs2?

13

Aquí hay un fragmento de código de la documentación para fs2 . La función goes recursiva. La pregunta es ¿cómo sabemos si es seguro para la pila y cómo razonar si alguna función es segura para la pila?

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)

¿También sería seguro para la pila si llamamos godesde otro método?

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
fuente
No, no exactamente Aunque si este es el caso de la recursividad de la cola, dígalo, pero parece que no lo es. Hasta donde yo sé, los gatos hacen algo de magia llamada trampolín para garantizar la seguridad de la pila. Lamentablemente, no puedo decir cuándo se trampolina una función y cuándo no.
Lev Denisov
Puede reescribir gopara usar, por ejemplo, Monad[F]typeclass: hay un tailRecMmétodo que le permite realizar el trampolín explícitamente para garantizar que la función sea segura para la pila. Puede que me equivoque, pero sin eso Fdependes de la seguridad de la pila por sí solo (por ejemplo, si implementa el trampolín internamente), pero nunca sabes quién definirá tu F, así que no deberías hacer esto. Si no tiene garantía de que Fsea ​​apilable, use una clase de tipo que proporcione tailRecMporque es apta para la ley.
Mateusz Kubuszok
1
Es fácil dejar que el compilador lo pruebe con @tailrecanotaciones para las funciones de grabación de cola. Para otros casos no hay garantías formales en Scala AFAIK. Incluso si la función en sí es segura, las otras funciones que está llamando podrían no ser: /.
yǝsʞǝla

Respuestas:

17

Mi respuesta anterior aquí proporciona información de fondo que podría ser útil. La idea básica es que algunos tipos de efectos tienen flatMapimplementaciones que admiten directamente la recursividad segura para la pila; puede anidarflatMap llamadas explícitamente o mediante recursión tan profundamente como desee y no desbordará la pila.

Para algunos tipos de efectos no es posible flatMapapilar con seguridad debido a la semántica del efecto. En otros casos, es posible escribir una pila segura flatMap, pero los implementadores pueden haber decidido no hacerlo debido al rendimiento u otras consideraciones.

Desafortunadamente, no hay una forma estándar (o incluso convencional) de saber si flatMapun tipo determinado es apilable. Los gatos incluyen una tailRecMoperación que debería proporcionar una recidiva monádica segura para cualquier tipo de efecto monádico legal, y a veces mirar una tailRecMimplementación que se sabe que es legal puede proporcionar algunas pistas sobre si una flatMappila es segura para la pila. En el caso de Pullque se parece a esto :

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)
  }

Esto tailRecMes sólo a través recursiva flatMap, y sabemos que Pull's Monadejemplo, es legal , lo cual es bastante buena evidencia de que Pull' s flatMapes pila de fallos. El único factor de complicación aquí es que la instancia de Pulltiene una ApplicativeErrorrestricción en Fque Pull's flatMapno lo hace, pero en este caso eso no cambia nada.

Entonces, la tkimplementación aquí es segura flatMappara la Pullpila porque on es segura para la pila, y lo sabemos al observar su tailRecMimplementación. (Si profundizáramos un poco más, podríamos descubrir que flatMapes apta para apilar porque Pulles esencialmente un envoltorio para FreeC, que está trampolinado ).

Probablemente no sería terriblemente difícil reescribir tken términos de tailRecM, aunque tendríamos que agregar la ApplicativeErrorrestricción innecesaria . Supongo que los autores de la documentación decidió no hacerlo por razones de claridad, y porque sabían Pull's flatMapestá muy bien.


Actualización: aquí hay una tailRecMtraducción bastante mecánica :

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

Tenga en cuenta que no hay una recursión explícita.


La respuesta a su segunda pregunta depende de cómo se ve el otro método, pero en el caso de su ejemplo específico, >>solo dará como resultado más flatMapcapas, por lo que debería estar bien.

Para abordar su pregunta de manera más general, todo este tema es un desastre confuso en Scala. No debería tener que profundizar en las implementaciones como lo hicimos anteriormente solo para saber si un tipo admite la recursión monádica segura para la pila o no. Las mejores convenciones sobre documentación serían una ayuda aquí, pero desafortunadamente no estamos haciendo un buen trabajo al respecto. Siempre se puede usar tailRecMpara ser "seguro" (que es lo que querrá hacer cuando F[_]sea ​​genérico, de todos modos), pero aun así confía en que la Monadimplementación es legal.

En resumen: es una mala situación en general, y en situaciones delicadas definitivamente debes escribir tus propias pruebas para verificar que implementaciones como esta sean aptas para la pila.

Travis Brown
fuente
Gracias por la explicación. Con respecto a la pregunta cuando llamamos godesde otro método, ¿qué puede hacer que se apile inseguro? Si hacemos algunos cálculos no recursivos antes de llamar, ¿ Pull.output(hd) >> go(tl, n - m)está bien?
Lev Denisov
Sí, eso debería estar bien (suponiendo que el cálculo en sí no desborde la pila, por supuesto).
Travis Brown
¿Qué tipo de efecto, por ejemplo, no sería apilable para la recursión monádica? El tipo de continuación?
bob
@bob derecho, aunque los gatos de ContT's flatMap es realmente pila de fallos (a través de una Deferrestricción sobre el tipo subyacente). Estaba pensando más en algo así List, donde recurrir flatMapno es seguro para la pila (aunque sí es legal tailRecM).
Travis Brown