8

F# の固定小数点コンビネータに問題があります。

let rec fix f a = f (fix f) a

fix (fun body num -> 
    if num = 1000000 
    then System.Console.WriteLine "Done!" 
    else body (num + 1)
) 0

(このコードは問題を示すためのものであり、生成された IL コードが読みやすいように特別に記述されています。)

このコードは、最適化とテールコールを有効にしてコンパイルすると、StackOverflowException. ILコードを調べたところ、次の呼び出し内のラムダに問題を突き止めることができましたfix。

.method assembly static void f@1 (class FSharpFunc`2<int32, class Unit> body,int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0014

ldstr "Done!"
call void Console::WriteLine(string)
ret

IL_0014: ldarg.0 // Load the 'body' function onto the stack.
ldarg.1 // Load num onto the stack.
ldc.i4.1
add

// Invoke the 'body' function with num+1 as argument.
callvirt instance !1 class FSharpFunc`2<int32, class Unit>::Invoke(!0)
// Throw away the unit result.
pop
ret
}

(読みやすいようにコードを少し変更しました。)

の理由は、StackOverflowExceptionへの呼び出しbodyが末尾呼び出し (callvirt下部の命令) ではないためです。その理由は、コンパイラが実際にUnit!を返すラムダへの呼び出しを作成したためです。

したがって、C# の用語で言えば、 Body はFunc<Int32,Unit>実際にあるべきときAction<Int32>です。呼び出しは破棄する必要があるものを返すため、末尾呼び出しにすることはできません。また、メソッドはではなくf@1としてコンパイルされることに注意してください。これが、引数の呼び出しの結果を破棄する必要がある理由です。voidUnit

これは実際に意図されたものですか、それとも何かできることはありますか? コンパイラがこのラムダを処理する方法により、固定小数点コンビネータは、私が意図したすべての目的で役に立たなくなります。

結果として何かを返す限り、それは正常に機能することを付け加えたいだけです。何も返さない関数だけが期待どおりに機能しません。

これは機能します：

let rec fix f a = f (fix f) a

fix (fun body num ->
    if num = 1000000
    then System.Console.WriteLine "Done!"; 0
    else body (num + 1)
) 0
|> ignore

これは、ラムダ用に生成されたコードです。

.method assembly static int32 f@11 (class FSharpFunc`2<int32, int32> body, int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0015

ldstr "Done!"
call void Console::WriteLine(string)
ldc.i4.0
ret

IL_0015: ldarg.0
ldarg.1
ldc.i4.1
add
tail.
callvirt instance !1 class FSharpFunc`2<int32, int32>::Invoke(!0)
ret
}

今、テールコールがあります。そして、すべてがうまくいきます。

ILコードfix（コメントでの議論用）：

.method public static !!b fix<a, b> (class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, class FSharpFunc`2<!!a, !!b>> f, !!a a) 
{    
    ldarg.0
    ldarg.0
    newobj instance void class Program/fix@11<!!a, !!b>::.ctor(class FSharpFunc`2<class FSharpFunc`2<!0, !1>, class FSharpFunc`2<!0, !1>>)
    ldarg.1
    tail.
    call !!0 class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, !!a>::InvokeFast<!!b>(class FSharpFunc`2<!0, class FSharpFunc`2<!1, !!0>>, !0, !1)
    ret
}

したがって(fix f)、 fix の定義の内部は、この時点で発生する再帰呼び出しではなく、fixそれ自体への参照であり、引数とともに、f呼び出されたクロージャーに格納されProgram/fix@11、ラムダに渡されるように見えます。fixこのクロージャーを介して実際に呼び出す引数として。

そうしないと、最初から無限再帰にfixなり、役に立たなくなります。

F# バージョン 3.1.2、F# Interactive バージョン 12.0.30815.0 を使用しています。

お願いします：

代替ソリューションには興味がありません。Unitラムダが結果を生成しない場合に、破棄する必要がある a をコンパイラが返す理由を知りたいだけです。

4

2 に答える 2

7

実際、あなたはすでにあなた自身の質問に答えています。ソースコードのコメントを引用すると、

// Throw away the unit result

呼び出し後の保留中の操作であるため、コンパイラーはここで末尾呼び出しを使用できません。

Keith Battocchi による素晴らしいブログ記事「Tail calls in F#」 (セクション「制限事項 / ユニットを返す関数値の呼び出し」までスクロール) には、多くの詳細が記載されています。

つまり
、通常、F# 関数… -> unitは .NET メソッドを返すようにコンパイルされますvoid。
ただし、値として扱われる関数(たとえば、高階関数に引数として渡される関数) は型のオブジェクトに格納される('a->'b)ため、実際にMicrosoft.FSharp.Core.Unitは ではなくを返しvoidます。
コンパイラは、戻る前にスタックからダミーunit値をポップする必要があります。
したがって、再帰呼び出しの後に保留中の操作があるため、コンパイラは末尾呼び出しに最適化できません。

朗報:

この問題は、第一級関数を値として使用する場合にのみ発生することに注意してください。void を返す通常の .NET メソッドを呼び出しても、スタックからポップする戻り値がないため、この問題は発生しません。

于 2015-04-18T22:31:16.173 に答える