クロージャと文脈自由文法

Question

理論上のコンピューターサイエンスクラスのシラバスを探しており、「自由な文法」の見出しの中で「クロージャープロパティ」をリストしています。私はこのテーマに関する教科書に目を通しましたが、ほとんど見つかりませんでした。それが持っている少しは、現時点では私の頭の上に少しあります（私はまだコースを受講していません）が、私は少し理解しています。

この文脈自由文法内のクロージャの考え方は、関数型プログラミング内のクロージャの考え方と同じか、関連しているのだろうかと思っていました。私が知る限り、文法の組み合わせと重複の解決について話します。私がまだ理解していない本のセクションには多くの部分があるので、これらのアイデアが同じかどうかはわかりません。

（もう少し文脈：教授に、コースをPerlからRubyまたはPythonに切り替えることができるかどうかを尋ねるメールを書いています。これらの概念が関連している場合は、PerlではなくRubyを使用する必要があります。 ）

Answer 1

用語「閉鎖」さまざまな方法で使用されますが、ほとんどの場合、補完の数学的概念にまでさかのぼって追跡されます。

• 演算子が「閉じられました」その演算子をセットの値に適用すると、常に指定されたセットの値が生成される場合、値のセットたとえば、整数に対する加算は閉じられますが、除算は行われません（4/2は整数ですが、5/2はそうではありません）。整数の追加はどういうわけか「完全」です;分割はそうではないという意味で。

• ＆quot; transitive＆quot;関係の閉鎖「完了」 （可能なすべての）複数のアプリケーションに従うことによる関係。日常的に言えば、「の子孫」という概念は、は、リレーションシップの推移的な閉鎖です。「子」です。

• 機能的な「クロージャ」 「完了」した例えば自由変数の解決方法を指定します。擬似コード式：

  bump = function(x) (x + y)
  

  x は bump の引数ですが、定義では＆quot; open＆quot;のままになっているようです。 y を解決する問題。一方、以下を定義する場合：

  bumper = function(y) (function(x) (x + y))
  

  then bumper を呼び出すと、作成された関数の引数に bumper の元の引数を追加する関数が返されます。

  add3 = bumper(3)
  

  は次の定義と同等です：

  add3 = function(x) (x + 3)
  

  ネストされた定義は＆quot; closed over＆quot;です; （またはそれによって完成）定義の時点で利用可能な変数。

つまり、実際には、「クロージャ」の使用は、何よりも具体的な意味は異なり、一見無関係なように見えますが、微妙な関係があります。

Answer 2

クロージャプロパティは次のようになります。LとMがコンテキストフリー言語である場合、L | Mも同様です。関数クロージャは、ファーストクラスの関数を実装する方法です。いいえ、彼らはお互いにほとんど何の関係もありません。

なぜ同じ名前ですか？関数クロージャは、その自由変数の「クローズド」です：

def adder(n): return lambda m: n + m

ここで、nはラムダの自由変数です。 Lispはもともと自由変数を閉じなかったため、名前がこれを強調しています-内部関数が呼び出されたときにスタック上にあったバインディングから値を取得します。

数学のプロパティの閉鎖はもう少し明白です。操作の下でセットが閉じられている場合、そのセット内でその操作を適用しても、その操作から抜け出すことはできません。整数を追加しても、取得されるのは整数です。

Answer 3

ダライアスは正しい。 「クロージャのプロパティ」 「関数のクロージャ」とは関係ありません。回り込む単語は非常に多いです：-（

クロージャープロパティの概念はコンピューターサイエンス全体に適用されますが、さまざまなクラスの言語に多く適用されます。発話をスキャンまたは認識するために異なるテクノロジーが必要なため、異なるクラスの言語が重要です。たとえば、正規表現では予約語があるかどうかはわかりますが、かっこで囲まれた式があるかどうかはわかりません。そのためには、文脈に依存しない文法が必要です。

人々は一般に、特定の言語を使用して別の言語と交差または結合する場合、または単にその言語を補完する場合、同じクラスで別の言語を取得するかどうかに関心があります。たとえば、予約語 not のトークンと正確に一致する正規表現を書くことは可能ですか？圧倒的な「はい」に答えることができます。正規言語は補数で閉じられているため、つまり、正規言語の補数自体が正規言語です。これはクロージャープロパティの例です。通常、証明は建設的です。つまり、予約語ではないすべてのトークンを記述する正規表現が存在することを存在するだけでなく、クロージャプロパティの証明が >そのような正規表現を見つける。