C# によるラムダ計算 (1) 基礎

[C# シリーズ経由の LINQ]

[C# シリーズによるラムダ計算]

ラムダ計算 (別名 λ 計算) は、関数の定義、関数の適用、関数の再帰を記述し、関数と関数の適用を使用して計算を表現するための理論的なフレームワークです。これは数学の正式なシステムですが、計算可能な関数を表現および評価できる最小のプログラミング言語と見なすこともできます。計算の普遍的なモデルとして、ラムダ計算はプログラミング言語理論において重要であり、特に関数型プログラミングの基礎です。ラムダ計算の知識は、関数型プログラミング、LINQ、C#、その他の関数型言語を理解するのに大いに役立ちます。

ラムダ計算の核となる概念は式です。ラムダ計算には、変数、関数、アプリケーションの 3 種類の式があります。式は再帰的に定義できます:

  • v が変数の場合、v は式です
  • v が変数で E が式の場合、関数 λv.E は式です。関数構文 λv.E は、C# の無名関数構文 v => E と見なすことができます。ここで、v はパラメーターで、E は関数本体の式です。
  • E1の場合 は式で、E2 が式の場合、E1 E2 アプリケーションと呼ばれる式です。アプリケーション構文 E1 E2 C# 関数呼び出し構文 E1 と見なすことができます (E2 )、ここで E1 は関数定義式で、E2 引数式です。

デフォルトでは、ラムダ計算は関数を匿名で扱います。ラムダ計算には変数名しかありません。関数定義式に含まれる関数名はありません。 C# 言語では、無名関数を表すラムダ式は、C# 3.0 と .NET Framework 3.5 年前に導入された機能です。実際、ラムダ式とラムダ計算の理論は、1930 年代に、数学者でアラン チューリングの博士号顧問であるアロンゾ チャーチによって導入されました。

以下は表現の規則です:

  • 一番外側のかっこは省略できます。 E1 E2 手段 (E1 E2 )、C# では (E1 (E2 )):関数 E1 を呼び出します 引数 E2 付き
  • 関数のシーケンスは短縮されます:、例:関数列 λx.(λy.(λz.E)) は λxyz.E と縮約されます。言い換えると、式 λxyz.E は実際には λx.(λy.(λz.E)) を意味し、これは λx.λy と同一です。 .λz.E は、括弧が必要ないためです。 C# では、(x, y, z) => E は常に x => (y => (z => E)) にカリー化されていることがわかります。これは、x => y => z => E と同じです。 => 演算子は右結合であるため
  • アプリケーションは連想のままです。 E1 E2 E3 手段 ((E1 E2 ) E3 )、C# では ((E1 (E2 ))<サブ> (E3 )):関数 E1 を呼び出します 引数 E2 付き 、次に返された関数を引数 E3 で呼び出します

束縛変数と自由変数

関数では、その本体式で変数を使用できます。関数本体の式で使用される変数には、束縛変数と自由変数の 2 種類があります。

  • 関数の変数 (. 記号の前の変数) が関数本体の式に出現する場合、これらの変数の出現 (. 記号の後) はバインドされた変数です。 C# では、これは関数本体で宣言された関数パラメーターの出現として表示できます。
  • 他のすべての変数は自由変数です。C# では、外部変数またはクロージャと見なすことができます。

たとえば、関数 λx.f x の場合、その本体式 f x には束縛変数 x と自由変数 f があります。これは、C# 構文では x => f(x) と見なすことができます。本体では、x はパラメーターであり、f はクロージャーです。

変数は、その「最も近い」関数によってバインドされます。たとえば、λx.g x (λx.h x) では、ボディ式で最初に出現する x は外部関数によってバインドされ、2 番目に出現する x は内部関数によってバインドされます。 C# では、この理由で x => g(x)(x => h(x)) をコンパイルできません。外側の関数パラメーターが内側の関数パラメーターと同じ名前を持っていますが、これは C# コンパイラでは許可されていません:

internal static class Expression
{
    internal static Func<T, T> Variable<T>(Func<T, Func<Func<T, T>, T>> g, Func<T, T> h) => 
        x => g(x)(x => h(x));
}

自由変数のない式はコンビネーターとも呼ばれますが、これについては後で説明します。

削減

ラムダ計算では、縮約する式の置換規則が 3 つあります。

α変換

ラムダ計算では、ラムダ式のバインドされた変数を別の名前に置き換えることができます。これは、アルファ変換またはアルファリネームと呼ばれます。 C# では、これは関数パラメーターの名前を変更できるように表示できます。たとえば、x => f(x) は y => f(y) と同等です。

上記の λx.g x (λx.h x) の例では、内部関数 λx.h x には変数 x があり、これは別の名前 y で置き換えることができ、本体 h x での出現と共に使用できます。そうすると、内側の関数は λy.h y になるので、外側の関数は λx.g x (λy.h y) になります。これで、x と y が「最も近い」関数によってどのように束縛されるかが直感的にわかります。 C# では、x => g(x)(y => h(y)) をコンパイルできます:

internal static Func<T, T> Variable<T>(Func<T, Func<Func<T, T>, T>> g, Func<T, T> h) => 
    x => g(x)(y => h(y));

β還元

関数適用式 (λv.E) のベータ簡約 R は E[v :=R] と表されます。これは、式 E 内の変数 v のすべての自由な出現箇所を式 R に置き換えることを意味します。C# では、これは、関数が引数で呼び出された場合と見なすことができ、本体では、すべてのパラメーターの出現箇所が引数に置き換えられます。たとえば、関数 x => x + 2 が 1 で呼び出された場合、本体 x + 2 では、パラメーター x が引数 1 に置き換えられるため、関数は 1 + 2 と評価されます。

η-変換

イータ変換とは、同じ引数に対して常に同じ結果が得られる場合にのみ、2 つの関数が同じであることを意味します。たとえば、x が f で自由に表示されない場合、λx.f x を f で置き換えることができます。 C# では、これは、関数 x => f(x) が関数 f と同等であると見なすことができます。例:

internal static void LinqQuery()
{
    Func<int, bool> isEven = value => value % 2 == 0;
    Enumerable.Range(0, 5).Where(value => isEven(value)).ForEach(value => Console.WriteLine(value));
}

ここで、関数値 => isEven(value) と関数 isEven は、同じ引数に対して常に同じ結果になるため、value=> isEven(value) を isEven に置き換えることができます。同様に value => Console.WriteLine(value) は Console.WriteLine に置き換えることができます。上記の LINQ クエリは次と同等です:

internal static void EtaConvertion()
{
    Func<int, bool> isEven = value => value % 2 == 0;
    Enumerable.Range(0, 5).Where(isEven).ForEach(Console.WriteLine);
}

通常の順序

上記の削減規則は、異なる順序の式に適用できます。通常の順序では、左端の最も外側の式が最初に削減されます。関数適用式の場合、これは関数が最初にベータ削減され、次に引数が削減されることを意味します。例:

  (λx.λy.y) ((λa.λb.a) (λv.v))
≡ λy.λy

この式では、関数 (λx.λy.y) に引数式 ((λa.λb.a) (λv.v)) が適用されます。一番左、一番外側の式は関数式 (λx.λy.y) です。したがって、その本体 λy.y では、x のすべての自由な出現は ((λa.λb.a) (λv.v)) で置換する必要があります。また、x の出現がないため、置換結果は依然として λy.y です。通常の順序縮約では、引数式 ((λa.λb.a) (λv.v)) はまったく縮約されません。

ここで、λy.y をこれ以上減らすことはできません。上記の 3 つのルールでこれ以上縮約できない式は、通常の形式で呼び出されます。ここで、λy.λy は (λx.λy.y) ((λa.λb.a) (λv.v)) の正規形です。一部のラムダ式は無限に簡約できるため、後で説明する正規形を持ちません。

適用順序

適用順序では、右端の最も内側の式が最初に削減されます。関数適用式の場合、これは引数が最初に削減され、次に関数がベータ削減されることを意味します。上記の式をもう一度例に取ります:

  (λx.λy.y) ((λa.λb.a) (λv.v))
≡ (λx.λy.y) (λb.λv.v)
≡ λy.λy

引数式 ((λa.λb.a) (λv.v)) は、関数定義式 (λx.λy.y) よりも右側にあるため、((λa.λb.a) (λv.v)) が先に簡約されます。 .これは、通常の形式 (λb.λv.v) にベータ還元できますが、これ以上還元することはできません。次に、(λx.λy.y) に (λb.λv.v) を適用します。これは、通常の形式 λy.λy にベータ縮小できます。適用順序縮約では、関数適用前に引数を縮約する必要があります。これが C# の戦略です。

ラムダ計算では、式をどの順序で還元しても同じ結果が得られます。これがチャーチ・ロッサーの定理です。

機能構成

ラムダ計算では、関数合成とは、単純な関数をより複雑な関数に結合することを意味し、前述の C# 関数合成と同じように見ることができます。 f1 の構成 と f2 f2 と表記されます ∘ f1 .この新しい関数 (f2 ∘ f1 ) のアプリケーションは次のように定義されます:

(f2 ∘ f1) x := f2 (f1 x)

ここで関数名 f1 と f2 適用される順序を示します。 f2 ∘ f1 f2 と読むこともできます f1 の後 . C# では、これは前に説明したフォワード合成と見なすことができます:

public static partial class FuncExtensions
{
    public static Func<T, TResult2> After<T, TResult1, TResult2>(
        this Func<TResult1, TResult2> function2, Func<T, TResult1> function1) =>
            value => function2(function1(value));
}

前述のように、他の関数型言語には、F# の>> のような関数の合成演算子が組み込まれているものがあります。 Haskell など。C# は、関数のカスタム演算子の定義をサポートしていません。回避策として、拡張メソッド o を定義して、この ∘ 演算子を表すことができます:

public static Func<T, TResult2> o<T, TResult1, TResult2>(
    this Func<TResult1, TResult2> function2, Func<T, TResult1> function1) =>
        value => function2(function1(value));

だから f3 ∘ f2 ∘ f1 f3 になる .o(f2 .o(f1 ) より直感的な C# の例:

internal static void Compose()
{
    Func<double, double> sqrt = Math.Sqrt;
    Func<double, double> abs = Math.Abs;

    Func<double, double> absSqrt1 = sqrt.o(abs); // Composition: sqrt after abs.
    absSqrt1(-2D).WriteLine(); // 1.4142135623731
}

結合性

関数合成は連想的です。つまり (f3 ∘ f2 ) ∘ f1 と f3 ∘ (f2 ∘ f1 ) は同等です。

x を (f3 に適用する場合 ∘ f2 ) ∘ f1 、∘の定義によると:

  ((f3 ∘ f2) ∘ f1) x
≡ (f3 ∘ f2) (f1 x)
≡ f3 (f2 (f1 x))

x を f3 ∘ (f2 ∘ f1) に適用すると:

  f3 ∘ (f2 ∘ f1) x
≡ f3 ∘ (f2 (f1 x))
≡ f3 (f2 (f1 x))

C# では、これは f3 を意味します .o(f2 .o(f1 ) と f3 .o(f2 .o(f1 )) は同​​等です:’

internal static void Associativity()
{
    Func<double, double> sqrt = Math.Sqrt;
    Func<double, double> abs = Math.Abs;
    Func<double, double> log = Math.Log;

    Func<double, double> absSqrtLog1 = log.o(sqrt).o(abs); // Composition: (log o sqrt) o abs.
    absSqrtLog1(-2D).WriteLine(); // 0.34642256747438094
    Func<double, double> absSqrtLog2 = log.o(sqrt.o(abs)); // Composition: log o (sqrt o abs).
    absSqrtLog2(-2D).WriteLine(); // 0.34642256747438094
}

ユニット

関数合成用のユニット関数 Id があります:

Id := λx.x

f ∘ Id と Id ∘ f はどちらも f:と同等です。

f ∘ Id = f
Id ∘ f = f

∘ と Id の定義によると:

  (f ∘ Id) x
≡ f (Id x)
≡ f x

  (Id ∘ f) x
≡ Id (f x)
≡ f x

C# では、Id は次のように定義できます:

// Unit<T> is the alias of Func<T, T>.
public delegate T Unit<T>(T value);

public static partial class Functions<T>
{
    public static readonly Unit<T>
        Id = x => x;
}

ここで、関数式 (λx.x) には名前 Id が付けられています。これは、読みやすくするためだけのものです。後でこの関数を参照するときに、その名前 Id が使用されます。これは、ラムダ式よりも直感的です。