为什么 Scala 不进行尾调用优化? [英] why scala doesn't make tail call optimization?

问题描述

只是玩延续.目标是创建一个函数，该函数将接收另一个函数作为参数和执行量 - 并返回将应用参数给定次数的函数.

Just playing with continuations. The goal is to create function which will receive another function as parameter, and execution amount - and return function which will apply parameter given amount times.

实现看起来很明显

def n_times[T](func:T=>T,count:Int):T=>T = {
  @tailrec
  def n_times_cont(cnt:Int, continuation:T=>T):T=>T= cnt match {
        case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
        case 1 => continuation
        case _ => n_times_cont(cnt-1,i=>continuation(func(i)))
      }
  n_times_cont(count, func)
}

def inc (x:Int) = x+1

    val res1 = n_times(inc,1000)(1)  // Works OK, returns 1001

val res = n_times(inc,10000000)(1) // FAILS

但是没有问题 - 此代码因 StackOverflow 错误而失败.为什么这里没有尾调用优化?

But there is no problem - this code fails with StackOverflow error. Why there is no tail-call optimization here?

我在 Eclipse 中使用 Scala 插件运行它，它返回线程main"中的异常 java.lang.StackOverflowError在 scala.runtime.BoxesRunTime.boxToInteger(来源不明)在 Task_Mult$$anonfun$1.apply(Task_Mult.scala:25)在 Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)

I'm running it in Eclipse using Scala plugin, and it returns Exception in thread "main" java.lang.StackOverflowError at scala.runtime.BoxesRunTime.boxToInteger(Unknown Source) at Task_Mult$$anonfun$1.apply(Task_Mult.scala:25) at Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)

附言

几乎是直接翻译的 F# 代码运行没有任何问题

F# code, which is almost direct translation, is working without any issues

let n_times_cnt func count = 
    let rec n_times_impl count' continuation = 
        match count' with
        | _ when count'<1 -> failwith "wrong count"
        | 1 -> continuation
        | _ -> n_times_impl (count'-1) (func >> continuation) 
    n_times_impl count func

let inc x = x+1
let res = (n_times_cnt inc 10000000) 1

printfn "%o" res

推荐答案

Scala 标准库有在 scala.util.control.TailCalls 中实现了蹦床.所以重新审视你的实现......当你用 continuation(func(t)) 构建嵌套调用时，那些是尾调用，只是没有被编译器优化.所以，让我们建立一个 T =>TailRec[T]，其中堆栈帧将被堆中的对象替换.然后返回一个函数，该函数将接受参数并将其传递给该蹦床函数:

The Scala standard library has an implementation of trampolines in scala.util.control.TailCalls. So revisiting your implementation... When you build up the nested calls with continuation(func(t)), those are tail calls, just not optimized by the compiler. So, let's build up a T => TailRec[T], where the stack frames will be replaced with objects in the heap. Then return a function that will take the argument and pass it to that trampolined function:

import util.control.TailCalls._
def n_times_trampolined[T](func: T => T, count: Int): T => T = {
  @annotation.tailrec
  def n_times_cont(cnt: Int, continuation: T => TailRec[T]): T => TailRec[T] = cnt match {
    case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
    case 1 => continuation
    case _ => n_times_cont(cnt - 1, t => tailcall(continuation(func(t))))
  }
  val lifted : T => TailRec[T] = t => done(func(t))
  t => n_times_cont(count, lifted)(t).result
}

这篇关于为什么 Scala 不进行尾调用优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！