再帰関数のスタックオーバーフローを倒す話 その1.5

F# IL

連載目次

はじめに

前回は、CPS変換によって再帰関数のスタックオーバーフローを回避する方法を紹介しました。 その中で、「末尾呼び出し」という言葉が出てきましたが、詳細については触れませんでした。 この記事では、本題からはちょっと脇道に逸れて、F#においては何が「末尾」で何が最適化の対象となる「呼び出し」なのかを説明します。

前提知識として、上記記事を理解していることと、一部についてはILがなんとなくわかることです。 大部分はILについて知らなくても読めるはずです。

末尾

再帰関数のスタックオーバーフローを倒す話 その1 では、末尾の説明でこのようなプログラムを扱い、

let example x =
  if f1 x then f2 x
          else 10 + f3 x

f1, f2, f3のうち、f2のみが末尾呼び出しされていると説明しました。

これは間違ってはいませんが、 F#で「末尾」とみなされる位置、みなされない位置というのは自明ではありません。 そこで、F#で「末尾」とみなされる位置、みなされない位置について掘り下げてみていきます。

ちなみに、ここで調べた結果はあくまで現在の実装について述べたものであり、 仕様として末尾が明示されているわけではありませんので、将来変更される可能性はあります。

調べ方

F#の仕様書の Expressionsの章に出てくる式について、関数を呼び出した際にtail.ILプレフィックスが付くかどうかを調べます。 ちなみにこれは、VS2013 / F#3.1.2で調査した結果であり、過去バージョンや将来のバージョンでは結果が変わる可能性がある点に注意してください。

(* これらの関数が定義されている前提 *)
let f x y = x + y
let g x = f x 1
let h = g

F#での末尾一覧

blockで囲まれた式の末尾

let ``block`` () = (h 2)

blockは、(と)で囲まれた式で、囲まれた中の式の末尾は末尾です。

begin-endで囲まれた式の末尾

let ``begin-end`` () = begin h 2 end

begin-endは、beginとendで囲まれた式で、囲まれた中の式の末尾は末尾です。

delayedのlazyに続く式の末尾

let ``delayed`` () = lazy (h 2)

delayedはlazyキーワードで始まる式で、lazyの後ろの式の末尾は末尾です。

functionの本体部分の式の末尾

let ``function`` () = List.map (fun x -> h x)

functionはfunキーワードで始まる式で、本体部分の式の末尾は末尾です。

matching functionの各本体部分の式の末尾

let ``matching function`` () = List.map (function 1 -> h 0 | x -> h x)

matching functionはfunctionキーワードで始まる式で、各本体部分の式の末尾は末尾です。

sequential executionの後ろ側の式の末尾

let ``sequential execution`` () = ignore (h 1); h2

sequential executionは;もしくは改行で区切られた式の並びで、後ろ側の式の末尾は末尾です。

matchの各分岐の式の末尾

let ``match`` x = match x with 1 -> h 0 | x -> h x

matchはmatchキーワードで始まる式で、各分岐の式の末尾は末尾です。

conditionalのthenの式の末尾とelseの式の末尾

let ``conditional`` cond = if cond then h 1 else h 2

conditionalはifキーワードで始まる式で、thenの式の末尾とelseの式の末尾は末尾です。

ただし、elseのないconditionalの場合は、thenの式の末尾だとしても末尾にはならないようです。

[<MethodImpl(MethodImplOptions.NoInlining)>]
let uf x = h x |> ignore

let ``conditional 2`` cond = if cond then uf 1

この関数を最適化あり、末尾呼び出しの生成ありでビルドすると、以下のようなILが吐かれます。

IL_0000: nop
IL_0001: ldarg.0
IL_0002: brfalse.s IL_000c

IL_0004: ldc.i4.1
IL_0005: call void Sample::uf(int32)
IL_000a: nop
IL_000b: ret

IL_000c: ret

tail.が付いていません。

末尾っぽいが末尾ではないもの

assignment

let ``assignment`` () =
  let mutable x = 1
  x <- h 2

当然と言えば当然ですが、h 2の結果をxに代入する必要があるため、末尾ではありません。

tuple

let ``tuple`` () = (h 1, h 2)

System.Tupleのコンストラクタ呼び出しが隠れているため、末尾ではありません。 このように書き換えるとわかりやすいでしょう。

let ``tuple`` () = System.Tuple.Create(h 1, h 2)

try/with

let ``try/with`` () = try h 1 with _ -> h 2

例外処理ブロックを抜けるためにはILレベルではleaveが必要なため、 tryやwithの中の式は末尾ではありません。

try/finally

[<MethodImpl(MethodImplOptions.NoInlining)>]
let uf x = h x |> ignore

let ``try/finally`` () = try h 1 finally uf 2

finallyブロックを抜けるためにはILレベルではendfinallyが必要なため、 finallyの中の式は末尾ではありません。

determinstic disposal

let ``determinstic disposal`` () =
  use x = { new IDisposable with member __.Dispose() = () }
  h 2

useはtry/finalyが隠れていますので、これも末尾ではありません。

例えば上のコードは、以下のようなコードに書き換え可能です。

let ``determinstic disposal`` () =
  let x = { new IDisposable with member __.Dispose() = () }
  let mutable result = 0
  try
    result <- h 2
  finally
    if x != null then
      x.Dispose()
  result

最適化される呼び出しとされない呼び出し

ここまでで「末尾」は分かりました。 では、F#において、末尾呼び出し最適化の対象となる「呼び出し」をきちんと理解していると言えるでしょうか？

ここでは、F#における「末尾呼び出し最適化によって最適化される呼び出し」について掘り下げてみていきます。

ここで調べた結果もあくまで現在の実装について述べたものであり、 仕様として最適化される呼び出しが明示されているわけではありませんので、将来変更される可能性はあります。

最適化される呼び出し

関数呼び出し

f x

関数呼び出しが末尾の位置にある場合、その呼び出しは最適化されます。 これが最適化されなかったら困りますよね。

メソッド呼び出し

x.M(y)

メソッド呼び出しが末尾の位置にある場合、その呼び出しは最適化されます。 F#での関数はメソッドとして実装されているので、関数呼び出しが最適化されるのであればこちらが最適化されない理由はないでしょう。

関数値の起動

let g = f
g x

関数を直接呼び出さず、(部分適用などを行って)値として扱う場合、 内部ではFSharpFunc<'T, 'U>型として表現されます*1。

このような場合でも、末尾の位置で関数値を起動している場合、その呼び出しは最適化されます。 安心して部分適用できますね。

演算子

x + y

演算子をユーザ定義している場合、それは関数やメソッドで実装することになるため、 末尾の位置で演算子を適用している場合はその呼び出しは最適化されます。

最適化されない呼び出し

コンストラクタ呼び出し

C(x)

コンストラクタの呼び出しが末尾の位置にあっても、その呼び出しは最適化されません。 コンストラクタの呼び出しはnewobjというILが発行されるのですが、このILに対してtail.プレフィックスは付けれないのです。 そのため、コンストラクタの呼び出しが絡むと必ずスタックが消費されることになります。 F#ではコンストラクタの呼び出しがされることが分かりにくい部分が幾つかあるので、これは罠になる場合があります。

コンストラクタ内でのコンストラクタ呼び出し

type C (res: int) =
  new (acc: int, n: int) =
    if n = 0 then C(acc)
    else C(acc * n, n - 1)

  member __.Result = res

コンストラクタ内で他の(自分もしくは親の)コンストラクタを呼び出す場合、newobjではなくcallvirtなどのcall系のILが発行されます。 しかし、これもtail.プレフィックスは付かないようです。 IL的にはここにtail.プレフィックスを付けても問題ないようなので、もしかすると将来この挙動は変わるかもしれません(し、変わらないかもしれません)。

*1:このような関数値のツールチップを表示させると、括弧で囲まれています