Как рассуждать о безопасности стека в Scala Cats / fs2?

13

Вот фрагмент кода из документации для fs2 . Функция goрекурсивная. Вопрос в том, как узнать, безопасен ли он для стека, и как определить, является ли какая-либо функция безопасной для стека?

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)

Будет ли это также безопасно для стека, если мы вызовем goдругой метод?

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
}
Лев Денисов
источник
Нет не совсем Хотя, если это рекурсия хвоста, расскажите, пожалуйста, но это не так. Насколько я знаю, кошки совершают магию, называемую прыжками на батуте, чтобы обеспечить безопасность стека. К сожалению, я не могу сказать, когда функция батута, а когда нет.
Лев Денисов
Вы можете переписать goдля использования, например, Monad[F]typeclass - есть tailRecMметод, позволяющий явно выполнять батут, чтобы гарантировать, что функция будет безопасна для стека. Возможно, я ошибаюсь, но без этого вы полагаетесь на Fто, что сами по себе безопасны в стеке (например, если он реализует батут внутри), но вы никогда не знаете, кто определит ваше F, поэтому вам не следует этого делать. Если у вас нет гарантии, что Fэто стек безопасно, используйте класс типов, который обеспечивает, tailRecMпотому что это безопасно по стеку по закону.
Матеуш Кубушок
1
Легко позволить компилятору доказать это с @tailrecаннотацией для функций хвостовой записи. Для других случаев нет никаких официальных гарантий в Scala AFAIK. Даже если сама функция безопасна, другие функции, которые она вызывает, могут не быть: /.
ǝsʞǝla

Ответы:

17

Мой предыдущий ответ здесь дает некоторую справочную информацию , которая может оказаться полезной. Основная идея заключается в том, что некоторые типы эффектов имеют flatMapреализации, которые поддерживают рекурсию, безопасную для стека, - вы можете вкладывать flatMapвызовы либо явно, либо через рекурсию настолько глубоко, насколько захотите, и вы не переполните стек.

Для некоторых типов эффектов невозможно flatMapобеспечить безопасность стека из-за семантики эффекта. В других случаях может быть возможно написать безопасный для стека flatMap, но разработчики, возможно, решили не делать этого из-за производительности или других соображений.

К сожалению, не существует стандартного (или даже обычного) способа узнать, является ли flatMapдля данного типа стек-безопасным. Cats включает в себя tailRecMоперацию, которая должна обеспечить безопасную для стека монадическую рекурсию для любого законного монадического типа эффекта, и иногда рассмотрение tailRecMреализации, которая, как известно, является законной, может дать некоторые подсказки о том, является ли объект flatMapбезопасным для стека. В случае Pullэто выглядит как это :

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

Это tailRecMпросто рекурсии через flatMap, и мы знаем , что Pull«s Monadэкземпляр является законным , что является довольно хорошим доказательством того, что Pull» s flatMapесть стек-сейф. Один осложняющий фактор здесь является то , что экземпляр для Pullимеет ApplicativeErrorограничение на Fтом , что Pull«s flatMapне делает, но в данном случае это не меняет ничего.

Таким образом, tkреализация здесь безопасна для стека, потому что flatMapon безопасна для Pullстека, и мы знаем это по ее tailRecMреализации. (Если бы мы копали немного глубже, мы могли бы выяснить, что flatMapэто безопасно для стека, потому что Pullэто, по сути, обертка для FreeC, которая трамплина .)

Вероятно, было бы не очень сложно переписать tkс точки зрения tailRecM, хотя мы должны были бы добавить иное ненужное ApplicativeErrorограничение. Я предполагаю, что авторы документации решили не делать этого для ясности, и потому что они знали, Pullчто flatMapвсе в порядке.


Обновление: вот довольно механический tailRecMперевод:

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

Обратите внимание, что нет явной рекурсии.


Ответ на ваш второй вопрос зависит от того, как выглядит другой метод, но в случае с вашим конкретным примером >>это приведет к большему количеству flatMapслоев, так что все должно быть в порядке.

Чтобы ответить на ваш вопрос в более общем плане, вся эта тема - запутанный беспорядок в Scala. Вам не нужно копаться в реализациях, как мы делали выше, просто чтобы узнать, поддерживает ли тип монадическую рекурсию, ориентированную на стек, или нет. Здесь лучше помогли бы соглашения о документации, но, к сожалению, мы не очень хорошо справляемся с этим. Вы всегда можете использовать, tailRecMчтобы быть «безопасным» (это то, что вы захотите делать, когда F[_], в любом случае, оно является универсальным), но даже тогда вы верите, что Monadреализация законна.

Подводя итог: это плохая ситуация, и в чувствительных ситуациях вы должны обязательно написать свои собственные тесты, чтобы убедиться, что подобные реализации безопасны для стека.

Трэвис Браун
источник
Спасибо за объяснение. Что касается вопроса, когда мы вызываем goдругой метод, что может сделать его небезопасным? Если мы сделаем несколько нерекурсивных вычислений, прежде чем мы вызовем Pull.output(hd) >> go(tl, n - m)это нормально?
Лев Денисов
Да, это должно быть хорошо (конечно, при условии, что сами вычисления не переполняют стек).
Трэвис Браун
Какой тип эффекта, например, не будет безопасным для стека для монадической рекурсии? Тип продолжения?
Боб
@bob право, хотя кошки - х ContT«s flatMap является на самом деле стек безопасно (через Deferограничение на базовый тип). Я больше думал о чем-то вроде List, когда повторение через flatMapне является безопасным для стека ( tailRecMхотя оно имеет законный характер ).
Трэвис Браун