爲什麼scala不會進行尾部呼叫優化？

只是玩延續。目標是創建將接收另一個函數作爲參數的函數，以及執行量 - 和將應用參數給定次數的返回函數。爲什麼scala不會進行尾部呼叫優化？

實現看起來相當明顯

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的錯誤。爲什麼這裏沒有tail-call優化？

我在Eclipse中使用Scala的插件運行它，它在scala.runtime.BoxesRunTime.boxToInteger（來源不明）在Task_Mult $$ anonfun $ 1返回螺紋異常「主要」 java.lang.StackOverflowError的 .Apply（Task_Mult.scala：25） at Task_Mult $$ anonfun $ n_times_cont $ 1 $ 1.apply（Task_Mult.scala：18）

F＃代碼，這幾乎是直接翻譯，工作沒有任何問題

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

來源

2013-05-14 galkk

的可能重複（http://stackoverflow.com/questions/105834/does -the-jvm-prevent-tail-call-optimizations） – 2013-05-14 09:29:05

斯卡拉標準庫有在scala.util.control.TailCalls中執行蹦牀。所以重新訪問你的實現......當你用continuation(func(t))建立嵌套調用時，這些調用是尾調用，只是沒有被編譯器優化。所以，我們建立一個T => TailRec[T]，其中堆棧將被堆中的對象替換。然後返回，將採取的參數，並將它傳遞給trampolined功能的功能：？是否JVM防止尾調用優化]

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 
}

來源

2013-07-04 03:57:55 huynhjl

我可能是錯在這裏，但我懷疑n_times_cont內部函數被正確地轉換爲使用尾遞歸;罪魁禍首不在那裏。

收集到的continuation關閉（即i=>continuation(func(i))）會使您的方法產生10000000個嵌套調用，一旦您應用主函數的結果，堆棧就會被炸燬。

其實你可以嘗試

scala> val rs = n_times(inc, 1000000) 
rs: Int => Int = <function1> //<- we're happy here 

scala> rs(1) //<- this blows up the stack!

順便說一句，你可以重寫

i=>continuation(func(i))

爲

continuation compose func

爲了更好的可讀性

來源

2013-05-14 10:24:31

據我所知，CPS的整個想法就是這個閉包集合。但它看起來像斯卡拉不能讓這樣的構造工作。 http://stackoverflow.com/questions/8549433/is-it-possible-to-use-continuations-to-make-foldright-tail-recursive?rq=1 p.s.感謝撰寫技巧，我不知道那 – galkk 2013-05-14 14:35:41

是的，你想讓'i => ...'lambda做一個尾部調用'continuation'，這@ @ tailrec'不會爲你做在斯卡拉的土地上也沒有其他的東西。你可以建立自己的蹦牀，我猜:) – 2013-05-14 17:50:53

@MyseriousDan，「斯卡拉土地上的其他東西」可能是一個強有力的聲明。標準庫有'util.control.TailCalls' ... – huynhjl 2013-07-04 03:58:40

爲什麼scala不會進行尾部呼叫優化？

回答

相關問題