20

haskellプラットフォームの多くの関数の実装には非常に一般的なパターンがあり、私を悩ませていますが、説明を見つけることができませんでした。最適化のための入れ子関数の使用についてです。

末尾再帰を目的とするwhere句の入れ子関数の理由は（長さのように）私には非常に明確ですが、内部関数が最上位の関数とまったく同じタイプである場合の目的は何ですか？これは、たとえば、次のようなData.Setモジュールの多くの機能で発生します。

-- | /O(log n)/. Is the element in the set?
member :: Ord a => a -> Set a -> Bool
member = go
  where
    STRICT_1_OF_2(go)
    go _ Tip = False
    go x (Bin _ y l r) = case compare x y of
          LT -> go x l
          GT -> go x r
          EQ -> True
#if __GLASGOW_HASKELL__ >= 700
{-# INLINABLE member #-}
#else
{-# INLINE member #-}
#endif

メモ化と関係があるのではないかと思いますが、よくわかりません。

編集：dave4420は厳密さを示唆しているのでSTRICT_1_OF_2、同じモジュールにあるマクロの定義は次のとおりです。

-- Use macros to define strictness of functions.
-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.
-- We do not use BangPatterns, because they are not in any standard and we
-- want the compilers to be compiled by as many compilers as possible.
#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined

goこのマクロがどのように機能するかは理解していますが、なぜ一緒にをSTRICT_1_OF_2(go)の代わりにトップレベルに移動すべきでないのかはまだわかりませんmember。

多分それは最適化のためではなく、単に文体の選択のためですか？

編集2 ：セットモジュールからINLINABLEとパーツを追加しました。INLINE一見、彼らが何か関係があるとは思いませんでした。

4

2 に答える 2

17

INLINABLE(またはINLINE) ローカル ワーカーのラッパーを持つことの直接的な利点の 1 つは、特殊化です。member呼び出しサイトで固定要素型を使用して定義される方法では、Ordディクショナリを破棄して、適切なcompare関数をインライン化するか、少なくとも静的引数として渡すことができます。

直接再帰的な定義でmemberは、ループ ブレーカーになり、インライン化されないため、呼び出しサイトの特殊化は行われません。これは、少なくとも、INLINABLEプラグマの前の話でした。

プラグマを使用するINLINABLEと、呼び出しサイトの特殊化が行われ、辞書が削除されますが、いくつかの試みでmember、現在と同じくらい効率的な直接再帰を書くことができませんでした。しかし、INLINEプラグマを使用すると、法則は依然として有効であり、ループ ブレーカーはインライン化されません。memberこれは、辞書を削除する呼び出しサイトの特殊化が不可能であることを意味します。

そのため、そのスタイルで関数を記述する必要はなくなったかもしれませんが、呼び出しサイトの特殊化を取得する必要がありました。

于 2012-03-18T14:05:10.763 に答える
13

GHC は再帰関数をインライン化できません。方法memberが定義され、再帰が制限されgo、memberそれ自体は再帰的ではなく、インライン化できます。

GHCユーザーガイドから：

GHC は、インライン化が永久に続くことがないように保証します。すべての相互再帰的なグループは、インライン化されない 1 つまたは複数のループ ブレーカーによって切断されます (GHC インライン化の秘密、JFP 12(4) July 2002 を参照)。GHC は INLINE プラグマを含む関数をループ ブレーカーとして選択しないようにしますが、選択の余地がない場合は INLINE 関数を選択することもできます。その場合、INLINE プラグマは無視されます。たとえば、自己再帰関数の場合、ループ ブレーカーは関数自体にしかできないため、INLINE プラグマは常に無視されます。

于 2012-03-18T11:26:09.203 に答える