はじめに
日曜日の朝、Crazy Resurrectionシリーズの別のエピソードの時間です。 もう一度脳の破裂の危険がある同じカテゴリーにいますが、それはまさに私たちが好きなことですよね？ 今回は、C＃の型なしラムダ計算を見ていきます。 しかし、C＃は型付けされた言語ではありませんか？ 本当に。 しかし、これは、C＃で行うすべてのことを静的に入力する必要があるということですか？ 必ずしもそうではありません：触れることも適用することもできないツールとして、言語にはタイピングが存在します。 このトピックでは、C＃4.0からの新しい動的キーワードが、いくぶん奇妙な角度からどのように...
型は途中で障壁になる場合があります。最初は型付けされていないもの（スキーマのないXMLドキュメント、WSDL契約のないWebサービスなど）や、動的に型付けされていること（動的言語からのオブジェクトなど） RubyやPythonなど）。 そして最後に、それらの型に準拠していない悪名高いAPI：ある時点で静的型付けがありますが、最終的にはどこにでもSystem.Objectがあるという結論に達します（COM Office MSライブラリの相互作用など）。 これらのすべての場合、動的C＃4.0に依存しています。 この機能を説明する古典的な例として、C＃のIronPythonオブジェクトについて説明します。 Pythonの最初の定義：
class Calc:
def Add(self, a, b):
return a + b
def GetCalc():
return Calc()
* This source code was highlighted with Source Code Highlighter .
このPython計算機の素晴らしいところは、加算演算子がサポートするすべてのものを操作できることです。 言い換えれば、2つの整数オブジェクトまたは2行、またはDateTimeとTimeSpanにフィードすることができます。 これらの呼び出しを行うには、C＃でdynamicキーワードを使用します。
var py = Python.CreateEngine();
dynamic script = py.ImportModule( "Calc" );
dynamic calc = script.GetCalc();
int three = calc.Add(1, 2);
* This source code was highlighted with Source Code Highlighter .
Pythonファイルを読み込むためのいくつかの技術的な行は無視してください。 ここで最も重要なのは、calc変数のタイプが動的と記述されているという事実です。つまり、そこから呼び出されるすべての操作は実行時に許可されます。
これがどのように機能するかについては詳しく説明しませんが、多分（クレイジーな日曜日のトピックのトピック以外）、これがこの可能性の本質です。 代わりに、「自宅で繰り返してはいけない」スタイルで何かを行います： 型のないラムダ計算を導入します。
型のないラムダ計算
1930年頃にアロンゾ教会によって開発された型のないラムダ計算は、関数の計算面に関する理論です。 彼女は関数をルールと見なし、それらと連携する2つの使いやすい操作を定義します。抽象化とアプリケーションです。 本質的にはすべてですが、それにもかかわらず、理論は研究のための巨大な空間を作り出しました。 これを納得させるために、お気に入りのオンライン書店でこの本のページ数を見ることをお勧めします。
（ 翻訳者のメモ：それほど多くない：621 books.google.com.ua/books?id=ZdydJZVue50C&dq=the+lambda+calculus+its+syntax+and+semantics&hl=ja&source=gbs_navlinks_sを参照）
それで、上記の本を引用/言い換えして、主なものを要約します。 まず、 λ項の概念を定義する必要があります。
典型的な練習として、例の4番目のラムダ用語を、完全に括弧で囲まれた形から取り出します。
ラムダ式がある場合はどこでも、ラムダ式を使用するC＃のように、それらは関数で表すことができます。 たとえば、上記の2番目の例は、「x」を返す引数「x」を持つ関数です。 つまり、これは同一の機能です。 ただし、型はありません。あらゆるもの（特に、他のラムダ用語）で動作できます。 C＃では、次のように記述できます。
Func <T、T> I = x => x;
Tはジェネリックパラメーターを表します。 明らかに、この関数は値を使って動作できますが、関数を使ってうまく動作することもできます：関数を受け入れると、まったく同じ関数を返します：
I（5）// 5を生成
I（I）// Iを生成
実際、上記の次の3つの例は、「機能の本体」（ポイントの後の部分）で使用されるすべての文字が抽象化によって「スコープ」にあるという意味で、閉じた用語です。 それらをコンビネーターと呼びます：
前の例の最後の用語は閉じていません。抽象化されていない「x」を返します。 これは、C＃にある閉鎖の概念を反映しています。
R x = ...;
Func <T、R> f = z => x;
ここではこれ以上深く掘り下げることはしませんが、「クロージャ」などの美しい言葉は理論的基礎に深く根ざしていると言えば十分です。 そのような強固な理論的根拠に基づいた言語で偶然働いたことを幸運に思ってください:-)。
次に、 自由変数の概念が必要です 。 つまり、特定の用語の抽象化によって導入されない変数を識別することができます。 この定義は非常に簡単です。
コンビネータの場合、自由変数のセットは空になります。 それどころか、最後の例（1つの結果がクロージャ）では、セットには1つの「x」のみが含まれます。 想像を絶するものはありませんか？
そして最後に、 代入に基づいて、 アプリケーションのカリー化方法を決定できます 。
名前の衝突（上記のFV（自由変数）を適用して変数の命名規則を使用することで正式に防止できる）を回避するために、変数の命名には可能な限り注意します。 私たちは皆、これをC＃から知っています。これは、可視性ゾーンの理論上の基礎にすぎません。
Func <T、T> I1 = x => x;
そして
Func <T、T> I2 = y => y;
実際、それらは「まったく同じ」です。 ランタイム全体（CLR）と言語（C＃）のコンテキストでこのような大きな単語を使用するのは危険です。
I1とI2が同じデリゲートを参照していると言っているわけではありません。「x => x」と「y => y」が同じであると言うデリゲート間での識別はありません。 むしろ、同じオブジェクトに適用された場合、I1とI2の環境は同じになることをここで指摘します。 ラムダ計算では、これはアルファ変換を指します。
名前の競合の重要な問題を無視しながら、上記のベータ変換ルールを詳しく見てみましょう。 アイデアは単純です：「異なる用語で抽象化を適用すると、置換になります。」 これは、C＃でデリゲートを呼び出すのとほとんど同じですが、いくつかの違いがあります。ラムダ計算、置換の世界では、用語の機械的な書き換えにすぎません。 C＃のような言語では、コードはそのままコンパイルされ、デリゲート呼び出しはその場でデリゲート本体を魔法のように書き換えません。 さらに重要なのは、C＃で、値による呼び出しのセマンティクスに直接関心があることです。呼び出しの前に、引数は（デリゲート呼び出しメカニズムを介して）呼び出しに渡すことができる「値」にキャストする必要があります。
型なしまたは普遍的に型付けされた？ （型なしまたはユニタイプ？）
そして今日の問題：すべてのラムダ用語を（CLR / C＃型システムの意味で）入力できますか？ すでにコンビネータIでこれを行っており、汎化（ジェネリック）を使用してFunc <T、T>として表現しているようです。特定の型Tの値を渡すと、結果は同じ値でまったく同じ型になります。 実際、そのような署名を推測するのはどうですか？ C＃はこれを行いませんが、F＃はできます（ML型言語で通常行われるように、Hindley-Milner型推論を使用）：
さて、「I」は、「a」から「a」に至るタイプであると推定されます。「a」は一般化されたパラメーターの表記法です。 K、2つの引数を取り、常に最初の引数（「定数」値の親）を返すコンビネータについてはどうですか。
まだ順調に進んでいるようです。 F＃は型を推測しました。これは「 'a to' b to 'a」でなければなりません。 うわー、ここで何が起こっているの？ C＃では、Func <T1、Func <T2、T1 >>のようになります。T1型の引数を受け取る関数は、T2型の引数を取り、T1型の値を返す関数を返します。 分かりますか？ ここで起こったことは「カリーイング」と呼ばれ、n個の引数を持つ関数が一度に1つの引数を提供する「ネストされた」関数になります。 これは、たとえば、「K 5」を記述して、残りの引数「y」（任意のタイプ）を食べ、常に5を返す新しい関数を作成できることを意味します。
Sのような（比較的）複雑な獣でも、型を推測できます：
印象的？ それほど難しくありません。 ここで、関数の本体からどのように型を導出するかを見てください。 まず、「z」と「（yz）」の2つの用語の前にxがあります。 つまり、「x」は2つの引数を持つ関数であり、何かを返すことになっています。 これらに型名を割り当てます。最初の引数「z」は型「a」を取得し、「（yz）」からの結果は型「b」になります。 結果を「c。 つまり、タイプ「x」は「a-> 'b->' c」と推定されます。 次に、「（yz）」の型の初期識別に基づいて、「b」として型「y」を推定する必要があります。 「y」は1つの引数「z」を持つ関数であることがわかります。 タイプ「z」を「a」としてすでに定義しているため、タイプ「y」は「a->」bの形式を取ります。 最後に、関数「S」も3番目の引数として「z」を取り、「a」と入力します。 ここで、これらすべてが戻り値の型「x」と組み合わされると、上記の署名が得られます。
さて、すべてのラムダ用語を入力できるようです。 残念ながら、ありません。 以下がその証拠です。
ここで、結果の引数xがそれ自体に適用される関数Wを作成しました。 このような単純なラムダ用語と、そのタイプを見つけることができません。 この脳の訓練に参加してください。Wは1つの引数xを取ります。たとえば、「a」と入力します。 現在、xはxに適用されます。 したがって、xは1つの引数を持つ関数のようです。 この引数はxであり、既に「a」と入力しています。 戻り型はどうですか？ それを「b」と呼びましょう。これで、xは型であるという結論に達しました。a->「b、これは以前と同じではありません」a：統合が失敗しました。
これは、型のないラムダ計算と型の変形（型付きラムダ計算と一般化、および「System F」と呼ばれる何か）の違いです。 型付き言語であるC＃では、型を完全に削除することはできないため、「型なし」を取得する方法はありません。 しかし、「ユニバーサルに型付けされた」はどうでしょう（ロバートハーパーのおかげ）：すべての型を1つの型に置き換えます。 できますか？ 答え：「ダイナミック」でそれができます！
dynamic W = new Func <dynamic、dynamic>（x => x（x））;
残念ながら、実際にはデリゲートコンストラクターへのややlyい呼び出しが必要ですが、左側の「動的」に「動的->動的」タイプを割り当てる方法に注意してください。 つまり、すべて（非機能的な値と機能的な「オブジェクト」）を動的であると解釈します。 上記のコードは問題なくコンパイルされますが、ラムダx（x）の本体でどのように機能しますか？ さて、実行時に、システムはタイプxが何であるかを把握し、単項関数として呼び出すことができるかどうかをチェックします。 例：
dynamic W = new Func<dynamic, dynamic>(x => x(x));
W(1);
* This source code was highlighted with Source Code Highlighter .
これは明らかに悪い決定です。 これは、引数「整数1」を使用した「関数整数1の呼び出し」に対応します。 整数値を関数として使用できないことは明らかです（これは良いことです！）。したがって、ランタイムは以下を生成します。
Unhandled Exception: Microsoft.CSharp.RuntimeBinder.RuntimeBinderException: Cannot invoke a non-delegate type
at CallSite.Target(Closure , CallSite , Object , Object )
at System.Dynamic.UpdateDelegates.UpdateAndExecute2[T0,T1,TRet](CallSite site, T0 arg0, T1 arg1)
at UntypedLambda.Program.b__46(Object x)
at CallSite.Target(Closure , CallSite , Object , Int32 )
at System.Dynamic.UpdateDelegates.UpdateAndExecuteVoid2[T0,T1](CallSite site, T0 arg0, T1 arg1)
at UntypedLambda.Program.Main()
, , DLR , .
?
var I = new Func<dynamic, dynamic>(x => x);
dynamic W = new Func<dynamic, dynamic>(x => x(x));
Console .WriteLine(W(I)(42));
* This source code was highlighted with Source Code Highlighter .
. I W, I(I), ( -) I. 42, 42.
… , dynamic
. - Scheme? , :-).
:
, :
SKI combinators
Church Booleans
Church Numerals
Going nuts - recursive functions
Unhandled Exception: Microsoft.CSharp.RuntimeBinder.RuntimeBinderException: Cannot invoke a non-delegate type
at CallSite.Target(Closure , CallSite , Object , Object )
at System.Dynamic.UpdateDelegates.UpdateAndExecute2[T0,T1,TRet](CallSite site, T0 arg0, T1 arg1)
at UntypedLambda.Program.b__46(Object x)
at CallSite.Target(Closure , CallSite , Object , Int32 )
at System.Dynamic.UpdateDelegates.UpdateAndExecuteVoid2[T0,T1](CallSite site, T0 arg0, T1 arg1)
at UntypedLambda.Program.Main()
, , DLR , .
?
var I = new Func<dynamic, dynamic>(x => x);
dynamic W = new Func<dynamic, dynamic>(x => x(x));
Console .WriteLine(W(I)(42));
* This source code was highlighted with Source Code Highlighter .
. I W, I(I), ( -) I. 42, 42.
… , dynamic
. - Scheme? , :-).
:
, :
SKI combinators
Church Booleans
Church Numerals
Going nuts - recursive functions
Unhandled Exception: Microsoft.CSharp.RuntimeBinder.RuntimeBinderException: Cannot invoke a non-delegate type
at CallSite.Target(Closure , CallSite , Object , Object )
at System.Dynamic.UpdateDelegates.UpdateAndExecute2[T0,T1,TRet](CallSite site, T0 arg0, T1 arg1)
at UntypedLambda.Program.b__46(Object x)
at CallSite.Target(Closure , CallSite , Object , Int32 )
at System.Dynamic.UpdateDelegates.UpdateAndExecuteVoid2[T0,T1](CallSite site, T0 arg0, T1 arg1)
at UntypedLambda.Program.Main()
, , DLR , .
?
var I = new Func<dynamic, dynamic>(x => x);
dynamic W = new Func<dynamic, dynamic>(x => x(x));
Console .WriteLine(W(I)(42));
* This source code was highlighted with Source Code Highlighter .
. I W, I(I), ( -) I. 42, 42.
… , dynamic
. - Scheme? , :-).
:
, :
SKI combinators
Church Booleans
Church Numerals
Going nuts - recursive functions