遞歸調用簽名不斷變化

Question

我將實現一個使用遞歸的程序。所以，在我開始出現堆棧溢出異常之前，我認爲能夠實施蹦牀並在需要時使用thunk會很好。

我做的第一個嘗試是階乘。下面的代碼：

callable(f) = !isempty(methods(f)) 

function trampoline(f, arg1, arg2) 
    v = f(arg1, arg2) 
    while callable(v) 
     v = v() 
    end 
return v 
end 

function factorial(n, continuation) 
    if n == 1 
     continuation(1) 
    else 
     (() -> factorial(n-1, (z -> (() -> continuation(n*z))))) 
    end 
end 

function cont(x) 
    x 
end 

另外，我實現了一個天真的階乘，以檢查是否爲事實上，我會阻止堆棧溢出：

function factorial_overflow(n) 
    if n == 1 
     1 
    else 
     n*factorial_overflow(n-1) 
    end 
end 

的結果是：

julia> factorial_overflow(140000) 
ERROR: StackOverflowError: 


#JITing with a small input 
julia> trampoline(factorial, 10, cont) 
3628800 

#Testing 
julia> trampoline(factorial, 140000, cont) 
0 

所以，是的，我正在避免StacksOverflows。是的，我知道結果是無意義的，因爲我得到整數溢出，但在這裏我只是關心堆棧。生產版本當然可以修復。 （另外，我知道因子情況是內置的，我不會使用其中的任何一個，我讓它們用於測試我的蹦牀）。

蹦牀版本在第一次運行時會花費大量時間，然後在計算相同或更低值時會變得很快。 如果我的確輸入trampoline(factorial, 150000, cont)，我將再次編譯一次。

在我看來（受過教育的猜測）我正在爲許多不同的簽名進行JITing：每個生成的thunk都有一個簽名。

我的問題是：我可以避免這種情況嗎？

Answer 1

我認爲問題是每個閉包都是它自己的類型，它專門用於捕獲變量。爲了避免這種專業化，可以使用並非完全專門化的仿函數：

struct L1 
    f 
    n::Int 
    z::Int 
end 

(o::L1)() = o.f(o.n*o.z) 

struct L2 
    f 
    n::Int 
end 

(o::L2)(z) = L1(o.f, o.n, z) 

struct Factorial 
    f 
    c 
    n::Int 
end 

(o::Factorial)() = o.f(o.n-1, L2(o.c, o.n)) 

callable(f) = false 
callable(f::Union{Factorial, L1, L2}) = true 

function myfactorial(n, continuation) 
    if n == 1 
     continuation(1) 
    else 
     Factorial(myfactorial, continuation, n) 
    end 
end 

function cont(x) 
x 
end 

function trampoline(f, arg1, arg2) 
    v = f(arg1, arg2) 
    while callable(v) 
     v = v() 
    end 
return v 
end 

請注意，函數字段是無類型的。現在，功能運行在第一次運行速度更快：

julia> @time trampoline(myfactorial, 10, cont) 
0.020673 seconds (4.24 k allocations: 264.427 KiB) 
3628800 

julia> @time trampoline(myfactorial, 10, cont) 
0.000009 seconds (37 allocations: 1.094 KiB) 
3628800 

julia> @time trampoline(myfactorial, 14000, cont) 
0.001277 seconds (55.55 k allocations: 1.489 MiB) 
0 

julia> @time trampoline(myfactorial, 14000, cont) 
0.001197 seconds (55.55 k allocations: 1.489 MiB) 
0 

我剛翻譯成代碼中的每個閉合成相應的仿函數。這可能不是必需的，可能有更好的解決方案，但它的工作原理和希望證明了方法。

編輯：

，以便爲增長放緩的原因更加清晰，可以使用：

function factorial(n, continuation) 
    if n == 1 
     continuation(1) 
    else 
     tmp = (z -> (() -> continuation(n*z))) 
     @show typeof(tmp) 
     (() -> factorial(n-1, tmp)) 
    end 
end 

此輸出：

julia> trampoline(factorial, 10, cont) 
typeof(tmp) = ##31#34{Int64,#cont} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,#cont}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}}}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}}}}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}}}}}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}}}}}}} 
typeof(tmp) = ##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,##31#34{Int64,#cont}}}}}}}}} 
3628800 

tmp是一個封閉。它自動創建類型##31#34類似於

struct Tmp{T,F} 
    n::T 
    continuation::F 
end 

專業化的continuation領域的F類型是長的編譯時間的原因。

通過使用L2代替，這是不專門在對應的字段f，將continuation參數factorial始終類型L2並且避免的問題。