3

最後のステートメントから関数の戻り型を推測できるカスタム言語を実装しようとしています。ただし、直接または間接の再帰関数呼び出しが見つかった場合、型推論システムは明らかに失敗します。

func factorial(a:int) -> 
    if a == 0
        1
    else
        a * factorial(a - 1)

たとえば、F＃は、引数の型が指定されていない場合でもこれを行います。

let rec fact i =
    if i = 0 then 1 else i * fact (i-1)

このシステムはどのように機能しますか？

4

1 に答える 1

15

F＃型チェッカーは、Damas-Hindley-Milner型推論アルゴリズムを使用します。階乗の例は、大まかに次のように説明できます。

  • の宣言からfact、そのタイプはフォームtx -> tyにありtx = t(i)、t(i)は値のタイプですi。

  • 等式チェックから、val (=): 'T -> 'T -> bool私たちも持っているのでt(i) = t(0) = int。

  • thenブランチから、別の制約を取得しますty = t(1) = int。
  • elseブランチから、正規作用素(*)は'T -> 'T -> 'Tなので、を取得しt(i) = tyます。

一連の制約に基づく：

tx = t(i)
t(i) = t(0) = int
ty = t(1) = int
t(i) = ty

統合を使用して、asに到達し、tx = ty = intタイプを推測します。また、 （条件を逆にすることによって）の句の順序を変更しても、型推論は正常に機能することも意味します。factint -> intif/then/else

とはいえ、これは型推論アルゴリズムの非常に単純な例です。上記のウィキペディアのリンクをたどって、詳細を読むことができます。

アルゴリズムをカスタム言語に適用するために、さまざまな関数型プログラミングの本で実装を見つけることができます。詳細については、このスレッドDamas-Hindley-Milner型推論アルゴリズムの実装を参照してください。

于 2013-03-15T09:55:08.430 に答える