Jak uzasadnić bezpieczeństwo stosu w Scala Cats / fs2?

13

Oto fragment kodu z dokumentacji dla fs2 . Funkcja gojest rekurencyjna. Pytanie brzmi: skąd wiemy, czy można je bezpiecznie nakładać i jak uzasadnić, czy jakakolwiek funkcja jest bezpieczna w stosie?

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)

Czy byłoby również bezpieczne w stosie, gdybyśmy zadzwonili goz innej metody?

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
}
Lew Denisow
źródło
Nie do końca. Jeśli tak jest w przypadku rekurencji ogona, powiedz to, ale wydaje się, że tak nie jest. O ile wiem, koty wykonują magię zwaną trampolinowaniem, aby zapewnić bezpieczeństwo stosu. Niestety nie wiem, kiedy funkcja jest trampolinowana, a kiedy nie.
Lew Denisov
Możesz przepisać, goaby użyć np. Monad[F]Klasy - istnieje tailRecMmetoda umożliwiająca jawne wykonanie trampoliny, aby zagwarantować, że funkcja będzie bezpieczna w stosie. Mogę się mylić, ale bez tego polegasz na Ftym, że sam jesteś bezpieczny w stosie (np. Jeśli implementuje wewnętrznie trampolinę), ale nigdy nie wiesz, kto cię zdefiniuje F, więc nie powinieneś tego robić. Jeśli nie masz żadnej gwarancji, że Fjest bezpieczny w stosach, użyj klasy typu, która zapewnia, tailRecMże zgodnie z prawem jest bezpieczny w stosach.
Mateusz Kubuszok
1
Łatwo jest pozwolić kompilatorowi udowodnić to za pomocą @tailrecadnotacji dotyczących funkcji nagrywania z tyłu. W innych przypadkach nie ma formalnych gwarancji w Scala AFAIK. Nawet jeśli sama funkcja jest bezpieczna, inne wywoływane funkcje mogą nie być: /.
yǝsʞǝla

Odpowiedzi:

17

Moja poprzednia odpowiedź tutaj zawiera pewne podstawowe informacje, które mogą być przydatne. Podstawową ideą jest to, że niektóre typy efektów mają flatMapimplementacje, które bezpośrednio obsługują rekurencję bezpieczną dla stosu - możesz zagnieżdżać flatMappołączenia jawnie lub poprzez rekurencję tak głęboko, jak chcesz, i nie przepełnisz stosu.

W przypadku niektórych typów efektów nie jest możliwe flatMapzachowanie bezpiecznego stosu, ze względu na semantykę efektu. W innych przypadkach może być możliwe napisanie bezpiecznego dla stosu flatMap, ale implementatorzy mogliby tego nie robić z powodu wydajności lub innych czynników.

Niestety nie ma standardowego (ani nawet konwencjonalnego) sposobu na sprawdzenie, czy flatMapdany typ jest bezpieczny dla stosów. Koty zawierają tailRecMoperację, która powinna zapewnić bezpieczną dla stosu rekurencję monadyczną dla dowolnego zgodnego z prawem typu efektu monadycznego, a czasem spojrzenie na tailRecMimplementację, o której wiadomo, że jest zgodna z prawem, może dostarczyć pewnych wskazówek na temat tego, czy flatMapmożna bezpiecznie stosować stos. W przypadku Pullwygląda na to, to :

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

To tailRecMwłaśnie dzięki recursing flatMap, i wiemy, że Pulljest Monadinstancja jest zgodne z prawem , co jest bardzo dobrym dowodem, że Pull's flatMapznaczy stos bezpieczny. Ten, komplikując czynnikiem jest to, że na przykład Pullma ApplicativeErrorograniczenie na Fto Pull„s flatMapnie, ale w tym przypadku to nie zmienia niczego.

Tak więc tkimplementacja jest bezpieczna dla stosu, ponieważ flatMapon Pulljest bezpieczny dla stosu, i wiemy to po spojrzeniu na jego tailRecMimplementację. (Jeśli wykopali głębiej możemy dowiedzieć się, że flatMapjest bezpieczny, ponieważ stos Pulljest zasadniczo otoki dla FreeC, których jest trampolined ).

Prawdopodobnie nie byłoby strasznie trudne do przerobienia tkw kategoriach tailRecM, choć musielibyśmy dodać inaczej niepotrzebne ApplicativeErrorograniczenie. Zgaduję, że autorzy dokumentacji postanowili nie robić tego dla jasności, a ponieważ wiedzieli Pull, że flatMapjest w porządku.


Aktualizacja: oto dość mechaniczne tailRecMtłumaczenie:

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

Pamiętaj, że nie ma wyraźnej rekurencji.


Odpowiedź na twoje drugie pytanie zależy od tego, jak wygląda druga metoda, ale w przypadku twojego konkretnego przykładu, >>po prostu spowoduje więcej flatMapwarstw, więc powinno być dobrze.

Aby odpowiedzieć bardziej ogólnie na twoje pytanie, cały ten temat jest mylącym bałaganem w Scali. Nie powinieneś zagłębiać się w implementacje, jak to zrobiliśmy powyżej, tylko po to, aby wiedzieć, czy typ obsługuje bezpieczną rekurencję monadyczną, czy nie. Pomocne byłyby lepsze konwencje dotyczące dokumentacji, ale niestety nie robimy tego zbyt dobrze. Zawsze możesz tailRecMbyć „bezpieczny” (co F[_]zresztą chcesz zrobić, gdy jest to ogólne), ale nawet wtedy ufasz, że Monadwdrożenie jest zgodne z prawem.

Podsumowując: ogólnie jest to zła sytuacja, aw delikatnych sytuacjach zdecydowanie powinieneś napisać własne testy, aby sprawdzić, czy takie implementacje są bezpieczne dla stosów.

Travis Brown
źródło
Dziękuję za wyjaśnienie. Jeśli chodzi o pytanie, kiedy dzwonimy goz innej metody, co może sprawić, że będzie się ona niebezpiecznie nakładać? Jeśli wykonamy jakieś nierekurencyjne obliczenia, zanim zadzwonimy, Pull.output(hd) >> go(tl, n - m)czy będzie w porządku?
Lew Denisov
Tak, to powinno być w porządku (zakładając, że samo obliczenie oczywiście nie przepełnia stosu).
Travis Brown,
Jaki typ efektu, na przykład, nie byłby bezpieczny w stosie dla rekurencji monadycznej? Typ kontynuacji?
Bob
@bob rację, chociaż Koty na ContT„s flatMap jest rzeczywiście bezpieczny stos (poprzez Deferograniczenie o typie bazowym). Myślałem bardziej o czymś w rodzaju List, w którym rekurencja flatMapnie jest bezpieczna dla stosów (choć jest zgodna z prawem tailRecM).
Travis Brown,