合成に基づいた縮小処理

以下の文章はこちらの記事を翻訳したものです：https://github.com/HypothesisWorks/hypothesis/blob/master/HypothesisWorks.github.io/_posts/2016-12-08-compositional-shrinking.md

以前に書いた記事で、縮小処理を実行する際に値の型に依存することの問題点について触れました。しかし、その記事を書いている間、私はいくつかの実装で見られる、完全ではなくともまずまずの効果を持つ中間的な手法を見落としていたことに気づきました。

この手法では、縮小が型に基づかないものの、値を受け取り、その値の縮小を行う遅延リストを返す従来の縮小APIに従います。このようなライブラリの例には、「theft」や「QuickTheories」があります。

このアプローチは比較的うまく機能し、型指向の縮小に伴う主要な問題点を解決します。しかし、それでもいくらか脆弱性があり、Hypothesisやtest.checkが採用している方法ほど柔軟に組み合わせることはできません。

生成される値の型に依存しないだけでなく、実際に生成された値にも全く基づかないものであることが理想です。これは直感に反するかもしれませんが、実際にはかなりうまく機能する方法です。

実装の詳細に入る前に、なぜこれが重要なのかを考えてみましょう。前回の投稿からの例を挙げてみます：

from hypothesis import given
from hypothesis.strategies import integers

even_numbers = integers().map(lambda x: x * 2)

@given(even_numbers)
def test_even_numbers_are_even(n):
    assert n % 2 == 0

ここでは、あるストラテジーを取り、そのストラテジーが生成した値に対する関数をマッピングして、新しいストラテジーを作成しています。

Hypothesisのストラテジー実装が以下のようなものだとします：

class SearchStrategy:
    def generate(self, random):
        raise NotImplementedError()

    def shrink(self, value):
        return ()

このコードでは、SearchStrategy クラスには generate メソッドと shrink メソッドが含まれています。generate メソッドはランダムな値を生成するのに使用され、shrink メソッドは与えられた値を縮小するために使用されますが、この例では空のタプルを返しており、縮小が行われないことを意味しています。

このアプローチの鍵は、縮小プロセスが生成された値に依存しないことです。つまり、生成された値を直接変更するのではなく、値を生成するストラテジー自体を変更することに焦点を当てています。これにより、より堅牢で柔軟なテストケースの生成が可能になり、様々な状況に適応しやすくなります。

要するに、サブクラスで実装する必要があるため、デフォルトでは値の生成方法を知らず、何も縮小できません。しかし、サブクラスではこれを修正することも、そのままにしておくこともできます（問題がなければ）。

実際には、これは非常に初期の実装の様子です。このアプローチの問題は、上述の 'map' 関数が縮小を保持する方法で定義することができない点です。生成された値を縮小するためには、合成している関数を逆にする何らかの方法が必要ですが、これは一般的に不可能で、言語がそれを実現するための機能を提供していたとしても、実現はほぼ間違いなく不可能です。したがって、生成された値を取り、それを生成した値にマップし直し、それを縮小し、マッピング関数と合成する必要があります。

Hypothesisとtest.checkは、より複雑なストラテジーの合成をサポートしていますが、任意の値を縮小する必要がある場合、最も単純な合成でさえ失敗します。この問題を解決するための鍵ですが、出力を縮小するためには、ほぼ常に入力を縮小することで十分だということです。理論的には、より単純な入力からより複雑な出力が生じる関数を得ることができますが、実際にはこれが十分にまれであるため、それらのケースではより複雑なテスト出力を受け入れることが適切です。

この考え方に基づき、マッピングされたストラテジーの出力を縮小する方法は、最初のストラテジーから生成された値を縮小し、その後マッピング関数に適用することです。これには、そのような縮小をサポートするためのAPIが必要です。

例えば、test.checkでは、このプロセスは単一の値を生成するのではなく、縮小可能な値を含む遅延ツリー全体を生成することで実現されます。Reid Draperの記事では、このトピックについてさらに詳しい説明があります。

この方法はマッピングの実装を容易にします。初めに生成された値と、それらの全ての縮小された子の値に対して、マッピング関数を単純に適用するだけです。

Hypothesisの実装はより複雑で、これについては別の記事で詳しく説明する必要がありますが、根本的な考え方として、Hypothesisは「出力を縮小するためには入力を縮小すれば良い」という概念を論理的な終着点まで追求しており、すべての生成がそれに基づく統一された中間表現を持っています。ストラテジーは、この表現上で実行可能な有効な縮小に関するヒントを提供することはできますが、それ以外ではほとんど縮小プロセスを制御することができません。これはさらにマッピングをサポートしやすくします。なぜなら、ほとんどは単に中間表現(IR)オブジェクトを取り、値を返す関数であり、マップされたさらには同じことを行い、追加でマッピング関数を適用するだけだからです。

私はHypothesisの実装が優れていると考えていますが、test.checkの実装も非常に価値があり、プロパティベースドテストシステムをゼロから実装する場合には、おそらくより簡単に適用できるでしょう。

しかし、どちらのアプローチを選ぶにしても、重要なのは以下の考えを持ち去ることです：出力を縮小するには入力を縮小し、ストラテジーは縮小を保持する方法で合成するべきだということです。その結果として、ユーザーは自身の縮小関数をほとんどまたは全く書く必要がなくなり、使用するのが非常に便利になります。また、縮小と生成が非同期になる可能性が減少します。