再帰呼び出しのシグニチャが変更され続ける

Question

再帰をかなり使用するプログラムを実装しようとしています。だから、私はスタックオーバーフローの例外を取得する前に、私はトランポリンを実装し、それが必要な場合にはサンクを使用することはいいと思った。

私が最初にやったのは階乗であった。ここでは、コード：

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)をやった場合、もう一度コンパイルするでしょう。

私は階乗のために多くの異なる署名を生成していると思います。

私の質問です：これを避けることはできますか？

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 

私はちょうど対応するファンクタにあなたのコード内のすべての閉鎖を翻訳しました。これは必要ないかもしれないし、おそらくもっと良い解決法があるかもしれませんが、それはうまくいき、うまくいけばアプローチを実証しています。

編集：

低迷の理由をより明確にするために、1を使用することができます。

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はcontinuationフィールドの種類Fに

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

専門に似た長いコンパイル時間の理由です。対応するフィールドfに専門されていない代わりにL2を使用することにより

は、factorialにcontinuationの引数は、常にタイプL2があり、問題が回避されます。