ベームの木

B%C3%B6hm_tree
Aベームツリーは、（潜在的に無限の）樹状提供するために使用することができる数学的対象である表示的意味論の用語について（「意味」）ラムダ計算（ラムダ計算への翻訳を使用して、一般的におよびプログラミング言語）。コラドベームにちなんで名付けられました。

コンテンツ
1 動機
2 非公式の定義
3 ノート
4 参考文献

動機
計算の意味を読み取る簡単な方法は、計算が完了すると結果が得られる有限数のステップで構成される機械的な手順と見なすことです。ただし、この解釈は、有限のステップ数の後に終了しないが、それでも直感的な意味を持つプロシージャには不十分です。たとえば、πの小数展開を計算する手順を考えてみましょう。適切に実装されている場合、「実行」時に部分的な出力を提供できます。この継続的な出力は、計算に意味を割り当てる自然な方法です。これは、たとえば、出力を提供せずに無限にループするプログラムとは対照的です。これらの2つの手順は、非常に異なる直感的な意味を持っています。
ラムダ計算を使用して記述された計算は、ラムダ項を正規形に縮小するプロセスであるため、この正規形自体が計算の結果であり、プロセス全体が元の項を「評価」していると見なすことができます。このため、Churchの当初の提案は、ラムダ項の計算（によって記述される）の意味は、それが縮小する正規形でなければならず、正規形を持たない項は無意味であるというものでした。これはまさに上記の不十分さを被ります。ただし、πアナロジーを拡張すると、項を通常の形式に縮小しようとすると、「限界内」に無限に長いラムダ項が得られる場合（そのようなものが存在する場合）、そのオブジェクトはこの結果と見なすことができます。もちろん、ラムダ計算にはそのような用語は存在しないため、ベームの木がこの場所で使用されるオブジェクトです。

非公式の定義
Aベーム状ツリーが（おそらく無限大）である有向非巡回グラフ形式λのラムダ項で標識されたいくつかの頂点を有するX 1 .λ X 2 …λ X nは。y（nは0の場合があります）。ここで、1つの頂点（「ルート」）には親がなく、他のすべての頂点には1つの親があり、すべての頂点には有限数の子があり、ラベルのないすべての頂点には子がありません。
ベームのような木A、Bについて次の概念を考えてみましょう。
λ X。あるA λとX。ルートのラベルの先頭に追加（λ X。A）BであるA [ X = B（下記参照）
B（のルートノードのラベルAは全く持っていないバインダーは）から得られた木であるA加えることによってBをルートノードの新しい右端の子として
ラベル付き頂点λでのx 1 …λ X N。yは、yがλの場合はその頂点で無料発生yはその頂点のラベルまたはその祖先に表示されません。
キャプチャ回避置換A は次のとおりです。（λ X。A）[ X = Bは】λであるX。NS（λ Y。A）[ X = B（xとyは異なる）はλであるZ。 zはしていないAでなく、フリーB（それが残ることがあり、YがあればYがで自由ではないB）
Aのルートノードにラベルxがあり、子C 1 … C nの場合、A は（（B C 1 ）C 2 ）です。 .. C n
Aのルートノードがxでラベル付けされていない場合（ラベル付けされていない可能性があります）、A は（（A C 1 ）C 2 ）..。C n
ラムダ項MのベームツリーBT（M）は、次のように「計算」できます。
BT（x）は、xでラベル付けされた単一ノードです。
BT（λ X。M）λであるX .BT（M）
BT（M N）はBT（M）BT（N）です
この手順は、Mの正規形を見つけることを意味することに注意して場合Mは、通常の形態を有し、ベームツリーは有限であり、通常のフォームに簡単に対応しています。Mに通常の形式がない場合、プロシージャは一部のサブツリーを無限に「成長」させるか、ラベルのないリーフノードのソースであるツリーの一部の結果を生成しようとして「ループに陥る」可能性がこのため、手順はすべてのステップを並行して適用するものとして理解する必要があり、結果のツリーには、手順を無限に適用する「限界」が与えられます。
例えば、手順がBT（のためのすべてで木を成長しないΩ）またはBT（のためのΩ I単一非標識ルートノードに相当します）。
同様に、手順は（BTのために終了しないλ X。X Ω）が、木は、前者の例からもかかわらず異なっています。

ノート
^ ここでのプレゼンテーションでは、可解性または頭の正規形の使用を避けていますが、それ以外は「効果的な」ベームツリーのプレゼンテーションです。

参考文献
^ チャーチ、アロンゾ（1941）。ラムダ変換の結石。プリンストン：プリンストン大学出版局。NS。15. ISBN 0691083940。
^ Barendregt、Henk P. The Lambda Calculus：その構文とセマンティクス。ロンドン：大学の出版物。pp。219–221、486–487。ISBN  9781848900660。
ジェラール・ヒュエット、H。ラウレエール（1997年9月）。「通常のベームツリーとしての有限状態トランスデューサ」。M.アバディとT.伊藤（編）。コンピュータソフトウェアの理論的側面 （PDF）。LNCS。1281。スプリンガー。pp。604–610。
ジェラール・ヒュエット（1998）。「通常のベームの木」 （PDF）。算数。構造体。コンプで。科学。8：671〜680。