scala - ¿Es posible usar continuaciones para hacer foldRight tail recursive?

f# tail-call-optimization

Question

El siguiente artículo de blog muestra cómo en F # foldBack se puede hacer la cola recursiva usando el estilo de continuación de paso.

En Scala esto significaría que:

def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
  l match {
    case x :: xs => f(x, foldBack(xs, acc)(f))
    case Nil => acc
  }
} 

se puede hacer la cola recursiva haciendo esto:

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    l match {
      case x :: xs => loop(xs, (racc => k(f(x, racc))))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

Desafortunadamente, todavía recibo un desbordamiento de pila para listas largas. loop es recursivo y optimizado, pero supongo que la acumulación de pila acaba de pasar a las llamadas de continuación.

¿Por qué esto no es un problema con F #? ¿Y hay alguna forma de solucionar esto con Scala?

Editar : aquí un código que muestra la profundidad de la pila:

def showDepth(s: Any) {
  println(s.toString + ": " + (new Exception).getStackTrace.size)
}

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    showDepth("loop")
    l match {
      case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

foldCont(List.fill(10)(1), 0)(_ + _)

Esto imprime:

loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10

Answer 1

El problema es la función de continuación (racc => k(f(x, racc))) . Debería ser optimizado para que todo este negocio funcione, pero no lo es.

Scala no puede realizar optimizaciones de cola para llamadas de cola arbitrarias, solo para aquellas que pueden transformarse en bucles (es decir, cuando la función se llama a sí misma, no a otra función).

Answer 2

¿Por qué esto no es un problema con F #?

F # tiene todas las llamadas de cola optimizadas.

¿Y hay alguna forma de solucionar esto con Scala?

Puedes hacer TCO usando otras técnicas como trampolines, pero pierdes interoperabilidad porque cambia la convención de llamadas y es ~ 10 veces más lenta. Esta es una de las tres razones por las que no uso Scala.

EDITAR

Sus resultados de referencia indican que los trampolines de Scala son mucho más rápidos que la última vez que los probé. Además, es interesante agregar puntos de referencia equivalentes usando F # y para listas más grandes (¡porque no tiene sentido hacer CPS en listas pequeñas!).

Para 1,000x en una lista de 1,000 elementos en mi netbook con un Intel Atom N570 de 1.67GHz, obtengo:

List.fold     0.022s
List.rev+fold 0.116s
List.foldBack 0.047s
foldContTC    0.334s

Para la lista de 1x 1,000,000 de elementos, obtengo:

List.fold     0.024s
List.rev+fold 0.188s
List.foldBack 0.054s
foldContTC    0.570s

Puede que también le interesen las viejas discusiones sobre esto en la lista caml en el contexto de reemplazar las funciones de lista recursiva no cola de OCaml con cola recursiva optimizada.

Answer 3

Jon, nm, gracias por tus respuestas. En base a sus comentarios, pensé en intentarlo y usar trampolín. Un poco de investigación muestra que Scala tiene soporte de biblioteca para trampolines en TailCalls . Esto es lo que se me ocurrió después de un poco de juguetear:

def foldContTC[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  import scala.util.control.TailCalls._
  @annotation.tailrec
  def loop(l: List[T], k: (U) => TailRec[U]): TailRec[U] = {
    l match {
      case x :: xs => loop(xs, (racc => tailcall(k(f(x, racc)))))
      case Nil => k(acc)
    }
  }
  loop(list, u => done(u)).result
} 

Me interesó ver cómo esto se compara con la solución sin el trampolín, así como con las implementaciones foldLeft y foldRight predeterminadas. Aquí está el código de referencia y algunos resultados:

val size = 1000
val list = List.fill(size)(1)
val warm = 10
val n = 1000
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldCont", warm, lots(n, foldCont(list, 0)(_ + _)))
bench("foldRight", warm, lots(n, list.foldRight(0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))

Los tiempos son:

foldContTC: warming...
Elapsed: 0.094
foldCont: warming...
Elapsed: 0.060
foldRight: warming...
Elapsed: 0.160
foldLeft: warming...
Elapsed: 0.076
foldLeft.reverse: warming...
Elapsed: 0.155

De acuerdo con esto, parecería que el trampolín está rindiendo bastante bien. Sospecho que la penalización en la parte superior del boxeo / unboxing es relativamente no tan malo.

Editar: como sugieren los comentarios de Jon, estos son los tiempos en los ítems 1M que confirman que el rendimiento se degrada con listas más grandes. También descubrí que la implementación de la librería List.foldLeft no se ha modificado, así que sincronicé con el siguiente foldLeft2:

def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  list match {
    case x :: xs => foldLeft2(xs, f(x, acc))(f)
    case Nil => acc
  }
} 

val size = 1000000
val list = List.fill(size)(1)
val warm = 10
val n = 2
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft2", warm, lots(n, foldLeft2(list, 0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))
bench("foldLeft2.reverse", warm, lots(n, foldLeft2(list.reverse, 0)(_ + _)))

rendimientos:

foldContTC: warming...
Elapsed: 0.801
foldLeft: warming...
Elapsed: 0.156
foldLeft2: warming...
Elapsed: 0.054
foldLeft.reverse: warming...
Elapsed: 0.808
foldLeft2.reverse: warming...
Elapsed: 0.221

Así que foldLeft2.reverse es el ganador ...

Answer 4

Llegué tarde a esta pregunta, pero quería mostrar cómo puedes escribir un FoldRight recursivo sin usar un trampolín completo; al acumular una lista de continuaciones (en lugar de hacer que se llamen entre sí cuando terminen, lo que lleva a un desbordamiento de la pila) y doblarlas al final, algo así como mantener una pila, pero en el montón:

object FoldRight {

  def apply[A, B](list: Seq[A])(init: B)(f: (A, B) => B): B = {
    @scala.annotation.tailrec
    def step(current: Seq[A], conts: List[B => B]): B = current match {
      case Seq(last) => conts.foldLeft(f(last, init)) { (acc, next) => next(acc) }
      case Seq(x, xs @ _*) => step(xs, { acc: B => f(x, acc) } +: conts)
      case Nil => init
    }
    step(list, Nil)
  }

}

El doblez que ocurre al final es recíproco en la cola. Pruébalo en ScalaFiddle

En términos de rendimiento, funciona un poco peor que la versión de llamada final.

[info] Benchmark            (length)  Mode  Cnt   Score    Error  Units
[info] FoldRight.conts           100  avgt   30   0.003 ±  0.001  ms/op
[info] FoldRight.conts         10000  avgt   30   0.197 ±  0.004  ms/op
[info] FoldRight.conts       1000000  avgt   30  77.292 ±  9.327  ms/op
[info] FoldRight.standard        100  avgt   30   0.002 ±  0.001  ms/op
[info] FoldRight.standard      10000  avgt   30   0.154 ±  0.036  ms/op
[info] FoldRight.standard    1000000  avgt   30  18.796 ±  0.551  ms/op
[info] FoldRight.tailCalls       100  avgt   30   0.002 ±  0.001  ms/op
[info] FoldRight.tailCalls     10000  avgt   30   0.176 ±  0.004  ms/op
[info] FoldRight.tailCalls   1000000  avgt   30  33.525 ±  1.041  ms/op