Как выполнить оптимизацию хвостового вызова в Scala3?

Question

Я пытаюсь написать программу, которая является 100% итеративной, то есть функции никогда не должны возвращаться, потому что после такого возврата ничего не должно происходить.

Другими словами, программа на 100% находится в хвостовой позиции. Рассмотрим следующую игрушечную программу:

        def foo(): Unit =
    bar()

  def bar(): Unit =
    foo()

  try
    foo()
  catch
    case s: StackOverflowError =>
      println(" Stack overflow!")

вызов foo действительно приводит к переполнению стека, что неудивительно: foo действительно вызывает bar, так как такому bar нужен кадр стека, bar затем вызывает foo, для которого нужен кадр стека и т. д. Понятно, почему возникает ошибка переполнения стека.

Мой вопрос: как я могу определить foo и bar такими, какие они есть, без переполнения стека? Языки типа Scheme позволяют эту программу, да, они будут работать вечно, но стек не будет расти, потому что он знает, что после вызова, например, bar from foo, ничего не должно происходить, поэтому нет необходимости сохранять кадр стека для foo on звонок в бар. Очевидно, что Scala (т. е. JVM?) сохраняет кадр стека живым.

Теперь рассмотрим следующий пример кода:

        def foo(): Unit = 
    foo()

  foo()

Эта программа будет работать вечно, но переполнения стека никогда не произойдет.

Мне известна аннотация @tailrec, но, насколько я понимаю, она применима только к ситуации, подобной второму примеру, но не к первому примеру.

Есть идеи?(Мне нужно, чтобы первый пример работал вечно, как второй пример, без переполнения стека.)

Answer 1

Как вы заметили, JVM запрещает нелокальные переходы, поэтому, если и скомпилированы как отдельные методы (что вообще желательно), исключение хвостового вызова невозможно.

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

      sealed trait TrampolineInstruction[A]

case class JumpOff[A](value: A) extends TrampolineInstruction[A]
case class JumpAgain[A](thunk: => TrampolineInstruction[A])
  extends TrampolineInstruction[A]

@tailrec
def runTrampolined(ti: TrampolineInstruction[A]): A =
  ti match {
    case JumpOff(value) => value
    case JumpAgain(thunk) => runTrampolined(thunk)
  }

def foo(): TrampolineInstruction[Unit] = JumpAgain(bar())
def bar(): TrampolineInstruction[Unit] = JumpAgain(foo())

runTrampolined(foo())  // will not overflow the stack, never completes

Cats предоставляет монаду , которая воплощает в себе идею прыжков на батуте. Приведенные выше определенияfooиbarтогда

      import cats.Eval

def foo(): Eval[Unit] = Eval.defer(bar())
def bar(): Eval[Unit] = Eval.defer(foo())

foo().value  // consumes a bounded (very small, not necessarily 1) number of stack frames, never completes

Монадические качестваEvalможет оказаться полезным для выражения более сложной логики без риска вызоваvalueв середине цепи.

Примечание:JumpOffв первом фрагменте в основномEval.Leaf(обычно создается с использованиемEval.now) иJumpAgainв основном этоEval.Defer.