ラムダリフティング

Globalization meta-process

ラムダリフティングは、コンピュータプログラムを再構成し、関数がグローバルスコープ内で互いに独立して定義されるようにするメタプロセスです。個々のリフティングは、ローカル関数（サブルーチン）をグローバル関数に変換します。これは以下の2段階のプロセスです。

• パラメータを追加して関数内の自由変数を削除します。
• 関数を制限されたスコープからより広いスコープまたはグローバル スコープに移動します。

「ラムダリフティング」という用語は、1982年頃にトーマス・ジョンソンによって初めて導入され、歴史的には関数型プログラミングに基づくプログラミング言語を実装するためのメカニズムと考えられてきました。一部の最新のコンパイラでは、他の手法と組み合わせて使用​​されています。

ラムダリフトはクロージャ変換とは異なります。ラムダリフトでは、すべての呼び出し箇所を調整する必要があり（呼び出しに引数（パラメータ）を追加する）、リフトされたラムダ式にクロージャは導入されません。一方、クロージャ変換では、呼び出し箇所を調整する必要はなく、自由変数を値にマッピングするラムダ式にクロージャが導入されます。

この手法は、コード リファクタリングで個々の関数に使用して、関数をそれが書かれたスコープ外でも使えるようにすることができる。 ラムダ リフトはプログラムを変換するために繰り返すこともできる。 リフトを繰り返して使用すると、ラムダ計算で書かれたプログラムを、ラムダを使わない再帰関数のセットに変換することができる。 これは、ラムダ計算で書かれたプログラムと関数として書かれたプログラムの等価性を示している。^[1] しかし、これは演繹におけるラムダ計算の健全性を示すものではない。ラムダ リフティングで使用されるイータ リダクションは、変数の条件を満たす値が 1 つだけであることを最初に確認せずに変数から値を削除するため、ラムダ計算に基数の問題をもたらすステップだからである(カリーのパラドックスを参照)。

ラムダリフティングはコンパイラの処理時間を増大させます。ラムダリフティングの効率的な実装はコンパイラの処理時間を短縮します。^[2] ${\displaystyle O(n^{2})}$

型なしラムダ計算では、基本型は関数であるため、ラムダ式のベータ縮約の結果は、リフティングによって変化する可能性があります。結果として得られる関数は数学的には同じ意味を持ちますが、型なしラムダ計算では同じ関数とはみなされません。内包的等価性と外延的等価性も参照してください。

ラムダリフティングの逆の操作はラムダドロップである。^[3]

ラムダドロップは、コンパイラによるプログラムのコンパイル速度を向上し、パラメータ数とスタックフレームのサイズを削減することで、結果のプログラムの効率を向上させる可能性があります。しかし、関数の再利用は困難になります。ドロップされた関数はコンテキストに結び付けられており、別のコンテキストで使用するには、まず関数を解放する必要があります。

アルゴリズム

次のアルゴリズムは、クロージャをファーストクラスオブジェクトとしてサポートしていない言語で任意のプログラムをラムダリフトする 1 つの方法です。

1. 各関数に一意の名前が付くように関数の名前を変更します。
2. 各自由変数を囲む関数への追加引数に置き換え、その引数を関数を使用するたびに渡します。
3. 自由変数を持たないすべてのローカル関数定義を同一のグローバル関数に置き換えます。
4. すべての自由変数とローカル関数が削除されるまで、手順 2 と 3 を繰り返します。

言語に、引数として渡したり他の関数から返したりできるファーストクラス オブジェクトとしてクロージャがある場合、クロージャは、自由変数のバインディングをキャプチャするデータ構造によって表現する必要があります。

例

次のOCamlプログラムは、1 から 100 までの整数の合計を計算します。

rec  sum  n  =  if n = 1 then 1 else let f x =  n + x in f ( sum ( n - 1 ) ) sum 100                    

（ は自身を呼び出す可能性のある関数としてlet rec宣言されていますsum。）関数 f は、sum の引数に引数より小さい数値の合計を加算する関数であり、局所関数です。f の定義において、n は自由変数です。まず、自由変数を引数に変換します。

rec  sum  n  =  if n = 1 then 1 else let f w x = w + x in f n  ( sum ( n - 1 ) ) sum 100                      

次に、f をグローバル関数に持ち上げます。

rec  f  w  x  = w + xとし、sum n = if n = 1 then 1 else f n ( sum ( n - 1 )) in sum 100 とする。                      

以下は同じ例ですが、今回はJavaScriptで記述されています。

// 初期バージョン関数sum ( n ) {関数f ( x ) { return n + x ; }           n == 1の場合は1 を返します。それ以外の場合はf ( sum ( n - 1 ) )を返します。 }          // 自由変数nを仮パラメータwに変換した後関数sum ( n ) {関数f ( w , x ) { return w + x ; }            if ( n == 1 )は1 を返します。そうでない場合はf ( n 、sum ( n - 1 )を返します。 }           // 関数fをグローバルスコープに持ち上げた後関数f ( w , x ) {戻り値w + x ; }       関数sum ( n ) { if ( n == 1 ) return 1 ; else return f ( n , sum ( n - 1 )); }              

ラムダリフティングとクロージャ

ラムダリフトとクロージャはどちらもブロック構造のプログラムを実装するための手法です。ブロック構造を解消することでブロック構造を実装します。すべての関数はグローバルレベルにリフトされます。クロージャ変換は、現在のフレームを他のフレームにリンクする「クロージャ」を提供します。クロージャ変換はコンパイル時間を短縮します。

再帰関数やブロック構造のプログラムは、リフティングの有無にかかわらず、スタックベースの実装を使用して実装できます。これはシンプルで効率的です。ただし、スタックフレームベースの実装は厳密（eager）である必要があります。スタックフレームベースの実装では、関数の寿命は後入先出（LIFO）である必要があります。つまり、計算を開始した最も新しい関数が、最初に終了する必要があります。

一部の関数型言語（ Haskellなど）は、遅延評価を用いて実装されています。遅延評価とは、値が必要になるまで計算を遅らせるものです。この遅延実装戦略は、プログラマに柔軟性を提供します。遅延評価では、関数によって計算された値が要求されるまで、関数の呼び出しを遅らせます。実装方法の一つとして、値の代わりに、計算内容を記述したデータの「フレーム」への参照を記録する方法があります。後で値が必要になったときに、そのフレームを使って必要なタイミングで値が計算されます。そして、計算された値が参照を置き換えます。

「フレーム」はスタックフレームに似ていますが、スタックに格納されない点が異なります。遅延評価では、計算に必要なすべてのデータがフレームに保存される必要があります。関数が「リフト」されている場合、フレームには関数ポインタと関数へのパラメータのみを記録します。一部の最新言語では、変数の寿命を管理するために、スタックベースの割り当ての代わりにガベージコレクションを使用しています。管理されたガベージコレクション環境では、クロージャは値を取得できるフレームへの参照を記録します。一方、リフトされた関数は、計算に必要な各値に対してパラメータを持ちます。

Let式とラムダ計算

Let式は、リフティング、ドロップ、そして再帰方程式とラムダ式の関係を記述するのに役立ちます。ほとんどの関数型言語にはlet式があります。また、ALGOLやPascalのようなブロック構造のプログラミング言語も、制限されたスコープ内での使用のために関数のローカル定義を許容するという点でlet式に似ています。

ここで使用されるlet式は、多くの関数型言語で実装されているlet recの完全な相互再帰バージョンです。

let式はラムダ計算と関連しています。ラムダ計算は構文と意味論が単純で、ラムダリフティングの記述に適しています。ラムダリフティングはラムダからlet式への変換として、ラムダドロップはその逆として記述すると便利です。これはlet式が相互再帰を許容するためであり、ある意味ではラムダ計算でサポートされているよりもリフティングが進んでいると言えます。ラムダ計算は相互再帰をサポートしておらず、最も外側のグローバルスコープで定義できる関数は1つだけです。

持ち上げずに平行移動を記述する変換規則は、 Let 式の記事に記載されています。

以下の規則は、lambda式とlet式の等価性を説明するものである。

名前	法
イータ還元等価性	${\displaystyle f\ x=y\equiv f=\lambda x.y}$
Let-Lambda同値性	${\displaystyle f\notin FV(E)\to (\operatorname {let} f:f=E\operatorname {in} L\equiv (\lambda f.L)\ E)\ {\text{(where }}f{\text{ is a variable name.)}}}$
組み合わせてみましょう	${\displaystyle x\notin FV(E)\to (\operatorname {let} v,\dots ,w,x:E\land F\operatorname {in} L\equiv \operatorname {let} v,\dots ,w:E\operatorname {in} \operatorname {let} x:F\operatorname {in} L)}$

ラムダ式のリフティングとドロップを記述するメタ関数を示します。メタ関数とは、プログラムをパラメータとして受け取る関数です。プログラムはメタプログラムのデータです。プログラムとメタプログラムは異なるメタレベルにあります。

プログラムとメタプログラムを区別するために、以下の規則が使用されます。

• 角括弧 []は、メタプログラム内の関数の適用を表すために使用されます。
• メタプログラム内の変数には大文字が使用されます。プログラム内の変数は小文字で表されます。
• ${\displaystyle \equiv }$メタプログラム内のequalsに使用されます。
• ${\displaystyle \_}$ダミー変数、つまり未知の値を表します。

簡潔にするために、最初のルールが適用されます。また、これらのルールでは、ラムダ式が前処理され、各ラムダ抽象化に一意の名前が付けられていることを前提としています。

置換演算子は広く用いられています。式は、L内のGをすべてSに置き換え、その結果を返すことを意味します。ここで用いる定義は、ラムダ計算のページに記載されている定義を拡張し、式の置換もカバーするようにしています。式のマッチングは、式のアルファ同値性（変数名の変更）を比較することで行います。 ${\displaystyle L[G:=S]}$

ラムダ計算におけるラムダリフティング

各ラムダリフトは、ラムダ式の部分式であるラムダ抽象化を取り、それを関数呼び出し（適用）に置き換えます。部分式内の自由変数は、関数呼び出しのパラメータとなります。

コードリファクタリングにおいて、個々の関数に対してラムダリフトを用いることで、関数をそのスコープ外でも使用可能にすることができます。また、ラムダリフトは、式にラムダ抽象がなくなるまで繰り返し適用することで、プログラムを変換することもできます。

ラムダリフト

リフトは、式内の部分式をその式の先頭まで持ち上げる操作です。式はより大きなプログラムの一部である場合もあります。これにより、部分式をどこに持ち上げるかを制御できます。プログラム内でリフトを実行するために使用されるラムダリフト演算は、以下のとおりです。

${\displaystyle \operatorname {lambda-lift-op} [S,L,P]=P[L:=\operatorname {lambda-lift} [S,L]]}$

サブ式は、ラムダ抽象化、またはパラメータに適用されたラムダ抽象化のいずれかになります。

2種類のリフトが可能です。

• 匿名リフト
• 名前付きリフト

匿名リフトは、ラムダ抽象化のみのリフト式を持ちます。これは匿名関数の定義とみなされます。関数には名前を付ける必要があります。

名前付きリフト式は、式にラムダ抽象化を適用したものです。このリフトは関数の名前付き定義とみなされます。

匿名リフト

匿名リフトはラムダ抽象化（Sと呼ばれる）を取ります。Sの場合;

• Sを置き換える関数（V ）の名前を作成します。V で識別される名前が使用されていないことを確認してください。
• S内のすべての自由変数のパラメータをVに追加して、式Gを作成します( make-call を参照)。

ラムダ リフトは、関数定義の追加とともに、関数適用 をラムダ抽象化Sに置き換えるものです。

${\displaystyle \operatorname {lambda-lift} [S,L]\equiv \operatorname {let} V:\operatorname {de-lambda} [G=S]\operatorname {in} L[S:=G]}$

新しいラムダ式では、GがSに置き換えられています。L [ S := G ]は、LのGがSに置き換えられることを意味します。関数定義には、関数定義G = Sが追加されています。

上記の規則において、Gは式Sに代入される関数適用であり、以下のように定義される。

${\displaystyle G=\operatorname {make-call} [V,\operatorname {FV} [S]]}$

ここで、Vは関数名です。これは新しい変数、つまりラムダ式でまだ使用されていない名前である必要があります。

${\displaystyle V\not \in \operatorname {vars} [\operatorname {let} F\operatorname {in} L]}$

ここで、 はEで使用される変数のセットを返すメタ関数です。 ${\displaystyle \operatorname {vars} [E]}$

匿名リフトの例。

例えば、 ${\displaystyle {\begin{aligned}F&=\operatorname {true} \\L&=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\\S&=\lambda x.f\ (x\ x)\\G&=p\ f\end{aligned}}}$ ${\displaystyle \operatorname {de-lambda} [p\ f=\lambda x.f\ (x\ x)]\equiv p\ f\ x=f\ (x\ x)}$ ラムダ式からlet式への変換のde-lambdaを参照してください。結果は次のようになります。 ${\displaystyle \operatorname {lambda-lift} [\lambda x.f\ (x\ x),\operatorname {let} \operatorname {true} \operatorname {in} \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} p\ f\ x=f\ (x\ x)\operatorname {in} \lambda f.(p\ f)\ (p\ f)}$

呼び出しの構築

関数呼び出しGは、自由変数セット（Vで表される）内の各変数のパラメータを関数Hに追加することによって構築されます。

• ${\displaystyle X\in V\to \operatorname {make-call} [H,V]\equiv \operatorname {make-call} [H,V\cap \neg \{X\}]\ X}$
• ${\displaystyle \operatorname {make-call} [H,\{\}]\equiv H}$

呼び出し構築の例。
${\displaystyle S=\lambda x.f\ (x\ x)}$ ${\displaystyle \operatorname {FV} (S)=\{f\}}$ ${\displaystyle G\equiv \operatorname {make-call} [p,\operatorname {FV} [S]]\equiv \operatorname {make-call} [p,\{f\}]\equiv \operatorname {make-call} [p,\{\}]\ f\equiv p\ f}$

名前付きリフト

名前付きリフトは、関数名Vが提供される点を除いて、匿名リフトと似ています。

${\displaystyle \operatorname {lambda-lift} [(\lambda V.E)\ S,L]\equiv \operatorname {let} V:\operatorname {de-lambda} [G=S]\operatorname {in} L[(\lambda V.E)\ S:=E[V:=G]]}$

匿名リフトに関しては、式GはSの自由変数を適用することでVから構築される。これは次のように定義される。

${\displaystyle G=\operatorname {make-call} [V,\operatorname {FV} [S]]}$

名前付きリフトの例。

例えば、 ${\displaystyle {\begin{aligned}V&=x\\E&=f\ (x\ x)\\S&=(\lambda x.f\ (x\ x))\\L&=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\\G&=x\ f\end{aligned}}}$ ${\displaystyle E[V:=G]=f\ (x\ x)[x:=x\ f]=f\ ((x\ f)\ (x\ f))}$ ${\displaystyle L[(\lambda V.E)\ F:=E[V:=G]]=L[(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)):=f\ ((x\ f)\ (x\ f))]=\lambda f.f\ ((x\ f)\ (x\ f))}$ ${\displaystyle \operatorname {de-lambda} [x\ f=\lambda y.f\ (y\ y)]\equiv x\ f\ y=f\ (y\ y)}$ ラムダ式からlet式への変換のde-lambdaを参照してください。結果は次のようになります。 与える、 ${\displaystyle \operatorname {lambda-lift} [(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)),\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} x\ f\ y=f\ (y\ y)\operatorname {in} \lambda f.(x\ f)\ (x\ f)}$

ラムダリフト変換

ラムダリフト変換は、ラムダ式を受け取り、すべてのラムダ抽象を式の先頭まで持ち上げます。その後、これらの抽象は再帰関数に変換され、ラムダ抽象は除去されます。その結果、以下の形式の関数型プログラムが得られます。

• ${\displaystyle \operatorname {let} M\operatorname {in} N}$

ここで、Mは一連の関数定義であり、Nは返される値を表す式です。

例えば、

${\displaystyle \operatorname {lambda-lift-tran} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p}$

その後、 de -letメタ関数を使用して結果をラムダ計算に戻すことができます。

${\displaystyle \operatorname {de-let} [\operatorname {lambda-lift-tran} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]]\equiv (\lambda p.(\lambda q.q\ p)\ \lambda p.\lambda f.(p\ f)\ (p\ f))\ \lambda f.\lambda x.f\ (x\ x)}$

ラムダ式を変換する処理は一連のリフトである。各リフトには、

• 関数lift-choiceによって選択された部分式。部分式は、ラムダを含まない方程式に変換できるように選択する必要があります。
• リフトは、次のセクションで説明するlambda-liftメタ関数の呼び出しによって実行されます。

${\displaystyle {\begin{cases}\operatorname {lambda-lift-tran} [L]=\operatorname {drop-params-tran} [\operatorname {merge-let} [\operatorname {lambda-apply} [L]]]\\\operatorname {lambda-apply} [L]=\operatorname {lambda-process} [\operatorname {lift-choice} [L],L]\\\operatorname {lambda-process} [\operatorname {none} ,L]=L\\\operatorname {lambda-process} [S,L]=\operatorname {lambda-apply} [\operatorname {lambda-lift} [S,L]]\end{cases}}}$

リフトが適用されると、レットは 1 つのレットに結合されます。

${\displaystyle {\begin{cases}\operatorname {merge-let} [\operatorname {let} V:E\operatorname {in} \operatorname {let} W:F\operatorname {in} G]=\operatorname {merge-let} [\operatorname {let} V,W:E\land F\operatorname {in} G]\\\operatorname {merge-let} [E]=E\end{cases}}}$

次に、パラメータドロップを適用し、「let」式で不要なパラメータを削除します。let式では関数定義が互いに直接参照できますが、ラムダ式抽象化は厳密に階層化されており、関数は自身を直接参照することはできません。

リフティングの表現の選択

式をリフト対象として選択する方法は2つあります。1つ目は、すべてのラムダ抽象化を無名関数の定義として扱います。2つ目は、パラメータに適用されるラムダ抽象化を関数の定義として扱います。パラメータに適用されるラムダ抽象化は、関数を定義するlet式と無名関数の定義の2つの解釈が可能です。どちらの解釈も有効です。

これら 2 つの述語は、両方の定義に必要です。

ラムダフリー- ラムダ抽象化を含まない式。

${\displaystyle {\begin{cases}\operatorname {lambda-free} [\lambda F.X]=\operatorname {false} \\\operatorname {lambda-free} [V]=\operatorname {true} \\\operatorname {lambda-free} [M\ N]=\operatorname {lambda-free} [M]\land \operatorname {lambda-free} [N]\end{cases}}}$

lambda-anon - 匿名関数。Xがラムダフリーであるような式。 ${\displaystyle \lambda x_{1}.\ ...\ \lambda x_{n}.X}$

${\displaystyle {\begin{cases}\operatorname {lambda-anon} [\lambda F.X]=\operatorname {lambda-free} [X]\lor \operatorname {lambda-anon} [X]\\\operatorname {lambda-anon} [V]=\operatorname {false} \\\operatorname {lambda-anon} [M\ N]=\operatorname {false} \end{cases}}}$

持ち上げのためだけに匿名関数を選択する

最も深い匿名抽象化を探索します。これにより、リフトを適用した関数は単純な方程式になります。この定義では、パラメータを持つラムダ抽象化は関数の定義とはみなされません。すべてのラムダ抽象化は匿名関数の定義とみなされます。

lift-choice - 式を走査して見つかった最初の匿名関数、または関数がない場合はnone 。

1. ${\displaystyle \operatorname {lambda-anon} [X]\to \operatorname {lift-choice} [X]=X}$
2. ${\displaystyle \operatorname {lift-choice} [\lambda F.X]=\operatorname {lift-choice} [X]}$
3. ${\displaystyle \operatorname {lift-choice} [M]\neq \operatorname {none} \to \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [M]}$
4. ${\displaystyle \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [N]}$
5. ${\displaystyle \operatorname {lift-choice} [V]=\operatorname {none} }$

例えば、

ラムダの選択は ${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))}$ ${\displaystyle \lambda x.f\ (x\ x)}$

ルール	関数型	選択
2		${\displaystyle \operatorname {lift-choice} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))]}$
3		${\displaystyle \operatorname {lift-choice} [(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))]}$
1	匿名	${\displaystyle \operatorname {lift-choice} [\lambda x.f\ (x\ x)]}$
		${\displaystyle \lambda x.f\ (x\ x)}$

ラムダの選択は ${\displaystyle \lambda f.(p\ f)\ (p\ f)}$ ${\displaystyle \lambda f.(p\ f)\ (p\ f)}$

ルール	関数型	選択
2	匿名	${\displaystyle \operatorname {lift-choice} [\lambda f.(p\ f)\ (p\ f)]}$
2		${\displaystyle \lambda f.(p\ f)\ (p\ f)}$

持ち上げるための名前付き関数と匿名関数の選択

最も深い名前付き関数または無名関数の定義を検索します。これにより、リフトを適用した関数は単純な式になります。この定義は、実引数を持つラムダ抽象化を関数定義として認識します。適用のないラムダ抽象化のみが無名関数として扱われます。

ラムダ名

名前付き関数。Mはラムダフリー、N はラムダフリー、または無名関数のような式。 ${\displaystyle (\lambda F.M)\ N}$

${\displaystyle {\begin{array}{l}\operatorname {lambda-named} [(\lambda F.M)\ N]=\operatorname {lambda-free} [M]\land \operatorname {lambda-anon} [N]\\\operatorname {lambda-named} [\lambda F.X]=\operatorname {false} \\\operatorname {lambda-named} [V]=\operatorname {false} \end{array}}}$

リフト選択

式を走査して見つかった最初の匿名関数または名前付き関数、または関数がない場合はnone 。

1. ${\displaystyle \operatorname {lambda-named} [X]\lor \operatorname {lambda-anon} [X]\to \operatorname {lift-choice} [X]=X}$
2. ${\displaystyle \operatorname {lift-choice} [\lambda F.X]=\operatorname {lift-choice} [X]}$
3. ${\displaystyle \operatorname {lift-choice} [M]\neq \operatorname {none} \to \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [M]}$
4. ${\displaystyle \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [N]}$
5. ${\displaystyle \operatorname {lift-choice} [V]=\operatorname {none} }$

例えば、

ラムダの選択は ${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))}$ ${\displaystyle (\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))}$

ルール	関数型	選択
2		${\displaystyle \operatorname {lift-choice} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))]}$
1	名前	${\displaystyle \operatorname {lift-choice} [(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))]}$
		${\displaystyle (\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))}$

ラムダの選択は ${\displaystyle \lambda f.f\ ((x\ f)\ (x\ f))}$ ${\displaystyle \lambda f.f\ ((x\ f)\ (x\ f))}$

ルール	関数型	選択
1	匿名	${\displaystyle \operatorname {lift-choice} [\lambda f.f\ ((x\ f)\ (x\ f))]}$
		${\displaystyle \lambda f.f\ ((x\ f)\ (x\ f))}$

例

例えば、Yコンビネータ、

${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

次のように解除されます。

${\displaystyle \operatorname {let} x\ f\ y=f\ (y\ y)\land q\ x\ f=f\ ((x\ f)\ (x\ f))\operatorname {in} q\ x}$

パラメータを削除した後、

${\displaystyle \operatorname {let} x\ f\ y=f\ (y\ y)\land q\ f=f\ ((x\ f)\ (x\ f))\operatorname {in} q}$

ラムダ式として（let式からラムダ式への変換を参照）、

${\displaystyle (\lambda x.(\lambda q.q)\ \lambda f.f\ (x\ f)\ (x\ f))\ \lambda f.\lambda y.f\ (y\ y)}$

名前付き関数と匿名関数の持ち上げ

	ラムダ式	関数	から	に	変数
1	${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$	真実	${\displaystyle (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$	${\displaystyle x\ f}$	${\displaystyle \{x,f\}}$
2	${\displaystyle (\lambda f.(\lambda x.f\ (x\ x))(\lambda x.f\ (x\ x)))}$ ${\displaystyle [(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)):=f\ ((x\ f)\ (x\ f))]}$	${\displaystyle x\ f=\lambda y.f\ (y\ y)}$			${\displaystyle \{x,f,p\}}$
3	${\displaystyle \lambda f.f\ ((x\ f)\ (x\ f))}$	${\displaystyle x\ f\ y=f\ (y\ y)}$	${\displaystyle \lambda f.f\ ((x\ f)\ (x\ f))}$	${\displaystyle q\ x}$	${\displaystyle \{x,f,p\}}$
4	${\displaystyle \lambda f.f\ ((x\ f)\ (x\ f))[\lambda f.f\ ((x\ f)\ (x\ f)):=q\ x]}$	${\displaystyle x\ f\ y=f\ (y\ y)\land q\ x=\lambda f.f\ ((x\ f)\ (x\ f))}$			${\displaystyle \{x,f,p,q\}}$
5	${\displaystyle q\ x}$	${\displaystyle x\ f\ y=f\ (y\ y)\land q\ x\ f=f\ ((x\ f)\ (x\ f))}$			${\displaystyle \{x,f,p,q\}}$

匿名関数のみを持ち上げる場合、Yコンビネータは、

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p}$

パラメータを削除した後、

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ f=(p\ f)\ (p\ f)\operatorname {in} q}$

ラムダ式として、

${\displaystyle (\lambda p.(\lambda q.q)\ \lambda f.(p\ f)\ (p\ f))\ \lambda f.\lambda x.f\ (x\ x)}$

匿名関数のみを持ち上げる

	ラムダ式	関数	から	に	変数
1	${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$	真実	${\displaystyle \lambda x.f\ (x\ x)}$	${\displaystyle p\ f}$	${\displaystyle \{x,f\}}$
2	${\displaystyle (\lambda f.(\lambda x.f\ (x\ x))(\lambda x.f\ (x\ x)))[\lambda x.f\ (x\ x):=p\ f]}$	${\displaystyle p\ f=\lambda x.f\ (x\ x)}$			${\displaystyle \{x,f,p\}}$
3	${\displaystyle \lambda f.(p\ f)\ (p\ f)}$	${\displaystyle p\ f\ x=f\ (x\ x)}$	${\displaystyle \lambda f.(p\ f)\ (p\ f)}$	${\displaystyle q\ p}$	${\displaystyle \{x,f,p\}}$
4	${\displaystyle \lambda f.(p\ f)\ (p\ f)[\lambda f.(p\ f)\ (p\ f):=q\ p]}$	${\displaystyle p\ f\ x=f\ (x\ x)\land q\ p=\lambda f.(p\ f)\ (p\ f)}$			${\displaystyle \{x,f,p,q\}}$
5	${\displaystyle q\ p}$	${\displaystyle p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)}$			${\displaystyle \{x,f,p,q\}}$

リフトのために選択される最初の部分式は です。これにより、ラムダ式が に変換され、方程式 が作成されます。 ${\displaystyle \lambda x.f\ (x\ x)}$ ${\displaystyle \lambda f.(p\ f)\ (p\ f)}$ ${\displaystyle p\ f\ x=f(x\ x)}$

2番目に選択される部分式は です。これにより、ラムダ式は に変換され、方程式 が作成されます。 ${\displaystyle \lambda f.(p\ f)\ (p\ f)}$ ${\displaystyle q\ p}$ ${\displaystyle q\ p\ f=(p\ f)\ (p\ f)}$

そしてその結果は、

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p\ }$

驚くべきことに、この結果は、名前付き関数の持ち上げから得られる結果よりも単純です。

実行

Kに関数を適用すると、

${\displaystyle {\begin{cases}\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ K&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ q\ p\ K\\(\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ p\ K\ (p\ K)\\K\ ((\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x)))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=p\ f\ (p\ f)\ \operatorname {in} \ K\ (p\ K\ (p\ K))\\\end{cases}}}$

それで、

${\displaystyle (\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))=K\ ((\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))))\ }$

または

${\displaystyle p\ K\ (p\ K)=K\ (p\ K\ (p\ K))}$

Yコンビネータは、そのパラメータ（関数）を自身に対して繰り返し呼び出します。関数が固定小数点を持つ場合、値は定義されます。ただし、関数は決して終了しません。

ラムダ計算におけるラムダドロップ

ラムダドロップ^[4]とは、関数のスコープを狭め、そのスコープのコンテキストを利用して関数のパラメータ数を減らす手法です。パラメータ数を減らすことで、関数の理解が容易になります。

ラムダリフティングのセクションでは、まずラムダ式をリフティングし、その結果得られたラムダ式を再帰方程式に変換するメタ関数について説明しました。ラムダドロップメタ関数は、その逆の処理を行います。まず再帰方程式をラムダ抽象化に変換し、その結果得られたラムダ式をラムダ抽象化へのすべての参照をカバーする最小のスコープにドロップします。

ラムダドロップは2つのステップで実行されます。

• 沈没
• パラメータの削除

ラムダドロップ

ラムダドロップは、プログラムの一部である式に適用されます。ドロップは、ドロップが除外される一連の式によって制御されます。

${\displaystyle \operatorname {lambda-drop-op} [L,P,X]=P[L:=\operatorname {drop-params-tran} [\operatorname {sink-test} [L,X]]]}$

どこ、

Lは削除されるラムダ抽象化です。

Pはプログラムです

Xは、削除から除外される式のセットです。

ラムダドロップ変換

ラムダドロップ変換は、式内のすべての抽象化をシンクします。式セット内の式からはシンクは除外されます。

${\displaystyle \operatorname {lambda-drop-tran} [L,X]=\operatorname {drop-params-tran} [\operatorname {sink-tran} [\operatorname {de-let} [L,X]]]}$

どこ、

Lは変換される式です。

Xは、ドロップから除外されるサブ式のセットです。

sink-tranは各抽象化を最も内側から順にシンクします。

${\displaystyle {\begin{cases}\operatorname {sink-tran} [(\lambda N.B)\ Y,X]=\operatorname {sink-test} [(\lambda N.\operatorname {sink-tran} [B])\ \operatorname {sink-tran} [Y],X]\\\operatorname {sink-tran} [\lambda N.B,X]=\lambda N.\operatorname {sink-tran} [B,X]\\\operatorname {sink-tran} [M\ N,X]=\operatorname {sink-tran} [M,X]\ \operatorname {sink-tran} [M,X]\\\operatorname {sink-tran} [V,X]=V\end{cases}}}$

抽象化の沈没

シンクとは、ラムダ抽象化を可能な限り内側に移動させることですが、それでも変数へのすべての参照の外側に残ります。

応用例-4件。

${\displaystyle {\begin{cases}E\not \in \operatorname {FV} [G]\land E\not \in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=G\ H\\E\not \in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=\operatorname {sink-test} [G\ \operatorname {sink-test} [(\lambda E.H)\ Y,X]]\\E\in \operatorname {FV} [G]\land E\not \in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=(\operatorname {sink-test} [(\lambda E.G)\ Y,X])\ H\\E\in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=(\lambda E.G\ H)\ Y\end{cases}}}$

抽象化。名前の変更を使用して、変数名がすべて異なることを確認します。

${\displaystyle V\neq W\to \operatorname {sink} [(\lambda V.\lambda W.E)\ Y,X]=\lambda W.\operatorname {sink-test} [(\lambda V.E)\ Y,X]}$

変数- 2 件。

${\displaystyle E\neq V\to \operatorname {sink} [(\lambda E.V)\ Y,X]=V}$

${\displaystyle E=V\to \operatorname {sink} [(\lambda E.V)\ Y,X]=Y}$

シンクテストは式をドロップから除外します。

${\displaystyle L\in X\to \operatorname {sink-test} [L,X]=L}$

${\displaystyle L\not \in X\to \operatorname {sink-test} [L,X]=\operatorname {sink} [L,X]}$

例

沈没の例

例えば、 ルール 表現 解除 ${\displaystyle \operatorname {sink-tran} [\operatorname {de-let} [\operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p]]}$ シンクトラン ${\displaystyle \operatorname {sink-tran} [(\lambda p.(\lambda q.q\ p)\ (\lambda p.\lambda f.(p\ f)\ (p\ f)))\ (\lambda f.\lambda x.f\ (x\ x))]}$ 応用 ${\displaystyle \operatorname {sink} [(\lambda p.\operatorname {sink} [(\lambda q.q\ p)\ (\lambda p.\lambda f.(p\ f)\ (p\ f))])\ (\lambda f.\lambda x.f\ (x\ x))]}$ ${\displaystyle \operatorname {sink} [(\lambda q.q\ p)\ (\lambda p.\lambda f.(p\ f)\ (p\ f))]}$ ${\displaystyle E\in \operatorname {FV} [G]\land E\not \in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]}$ ${\displaystyle E=q,G=q,H=p,Y=(\lambda p.\lambda f.(p\ f)\ (p\ f)),X=\{\}}$ ${\displaystyle (\operatorname {sink} [(\lambda E.G)\ Y,X])\ H}$ ${\displaystyle (\operatorname {sink} [(\lambda q.q)\ (\lambda p.\lambda f.(p\ f)\ (p\ f)),X])\ p}$ 変数 ${\displaystyle \operatorname {sink} [(\lambda p.\operatorname {sink} [(\lambda q.q)\ (\lambda p.\lambda f.(p\ f)\ (p\ f))]\ p)\ (\lambda f.\lambda x.f\ (x\ x))]}$ ${\displaystyle \operatorname {sink} [(\lambda q.q)\ (\lambda p.\lambda f.(p\ f)\ (p\ f))]}$ ${\displaystyle E=V\to \operatorname {sink} [(\lambda E.V)\ Y,X]}$ ${\displaystyle E=q,V=q,Y=(\lambda p.\lambda f.(p\ f)\ (p\ f)),X=\{\}}$ ${\displaystyle Y}$ ${\displaystyle (\lambda p.\lambda f.(p\ f)\ (p\ f))}$ 応用 ${\displaystyle \operatorname {sink} [(\lambda p.(\lambda p.\lambda f.(p\ f)\ (p\ f))\ p)\ (\lambda f.\lambda x.f\ (x\ x))]}$ ${\displaystyle E\not \in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]}$ ${\displaystyle E=p,G=(\lambda p.\lambda f.(p\ f)\ (p\ f)),H=p,Y=(\lambda f.\lambda x.f\ (x\ x))}$ ${\displaystyle \operatorname {sink} [G\ \operatorname {sink} [(\lambda E.H)\ Y,X]]}$ 変数 ${\displaystyle \operatorname {sink} [(\lambda p.\lambda f.(p\ f)\ (p\ f))\ \operatorname {sink-test} [(\lambda p.p)\ (\lambda f.\lambda x.f\ (x\ x)),X]]}$ ${\displaystyle \operatorname {sink} [(\lambda p.p)\ (\lambda f.\lambda x.f\ (x\ x)),X]}$ ${\displaystyle E=V\to \operatorname {sink} [(\lambda E.V)\ Y,X]}$ ${\displaystyle E=p,V=p,Y=(\lambda f.\lambda x.f\ (x\ x)),X=\{\}}$ ${\displaystyle Y}$ ${\displaystyle (\lambda f.\lambda x.f\ (x\ x))}$ 抽象化 ${\displaystyle \operatorname {sink} [(\lambda p.\lambda f.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))]}$ ${\displaystyle V\neq W\to \operatorname {sink} [(\lambda V.\lambda W.E)\ Y,X]}$ ${\displaystyle V=p,W=f,E=(p\ f)\ (p\ f),Y=(\lambda f.\lambda x.f\ (x\ x))}$ ${\displaystyle \lambda W.\operatorname {sink} [(\lambda V.E)\ Y,X]}$ 応用 ${\displaystyle \lambda f.\operatorname {sink} [(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x)),X]}$ ${\displaystyle \operatorname {sink} [(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x)),X]}$ ${\displaystyle E\in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]}$ ${\displaystyle E=p,G=(p\ f),H=(p\ f),Y=(\lambda f.\lambda x.f\ (x\ x))}$ ${\displaystyle (\lambda E.G\ H)\ Y}$ ${\displaystyle (\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))}$ ${\displaystyle \lambda f.(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))}$

パラメータの削除

パラメータドロップとは、関数内の位置に合わせて関数を最適化することです。ラムダリフトでは、関数をコンテキスト外に移動するために必要なパラメータが追加されました。ドロップでは、このプロセスが逆になり、自由変数を含む余分なパラメータが削除される可能性があります。

パラメータの削除とは、関数から不要なパラメータを削除することです。この場合、実際に渡されるパラメータは常に同じ式です。式の自由変数は、関数が定義されている箇所でも自由である必要があります。この場合、削除されたパラメータは関数定義本体内の式に置き換えられます。これにより、パラメータは不要になります。

例えば、

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

この例では、仮引数oの実引数は常にpです。p は式全体の中で自由変数であるため、この引数は省略できます。仮引数yの実引数は常にnです。しかし、nはラムダ抽象化によって束縛されているため、この引数は省略できません。

パラメータを削除した結果は、

${\displaystyle \operatorname {drop-params-tran} [\lambda m,p,q.(\lambda g.\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

${\displaystyle \equiv \lambda m,p,q.(\lambda g.\lambda n.n\ (g\ m\ n)\ (g\ q\ n))\ \lambda x.\lambda y.p\ x\ y}$

主な例として、

${\displaystyle \operatorname {drop-params-tran} [\lambda f.(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))]}$

${\displaystyle \equiv \lambda f.(\lambda p.p\ p)\ (\lambda x.f\ (x\ x))}$

drop-params-tranの定義は、

${\displaystyle \operatorname {drop-params-tran} [L]\equiv (\operatorname {drop-params} [L,D,FV[L],[]])}$

どこ、

${\displaystyle \operatorname {build-param-list} [L,D,V,\_]}$

パラメータリストを作成する

関数を定義する抽象化ごとに、名前を削除するかどうかの判断に必要な情報を構築します。この情報は、各パラメータについて記述します。パラメータ名、実際の値を表す式、そしてすべての式が同じ値を持つことを示す情報です。

例えば、

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

関数gのパラメータは、

形式パラメータ	すべて同じ値	実際のパラメータ式
×	間違い	_
o	真実	p
y	真実	n

各抽象化は一意の名前に変更され、パラメータリストは抽象化の名前に関連付けられます。例えば、gにはパラメータリストがあります。

${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\_,p],[y,\_,n]]}$

build-param-lists は、式を走査することで、式に対応するすべてのリストを構築します。4つのパラメータがあります。

• 分析対象のラムダ式。
• 名前のテーブルパラメータリスト。
• パラメータの値の表。
• 返されるパラメータリストは、

抽象化- 形式のラムダ式を分析して、関数のパラメータの名前を抽出します。 ${\displaystyle (\lambda N.S)\ L}$

${\displaystyle {\begin{cases}\operatorname {build-param-lists} [(\lambda N.S)\ L,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\land \operatorname {build-list} [L,D,V,D[N]]\\\operatorname {build-param-lists} [\lambda N.S,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\end{cases}}}$

名前を検索し、その名前に対応するパラメータリストの構築を開始します。仮パラメータ名を入力します。また、式の本体から実パラメータリストを受け取り、それをこの式の実パラメータリストとして返します。

${\displaystyle {\begin{cases}\operatorname {build-list} [\lambda P.B,D,V,[X,\_,\_]::L]\equiv \operatorname {build-list} [B,D,V,L]\\\operatorname {build-list} [B,D,V,[]]\equiv \operatorname {build-param-lists} [B,D,V,\_]\end{cases}}}$

変数- 関数の呼び出し。

${\displaystyle \operatorname {build-param-lists} [N,D,V,D[N]]}$

関数名またはパラメータの場合は、この名前のパラメータ リストを出力することによって、実際のパラメータ リストの入力を開始します。

アプリケーション- アプリケーション (関数呼び出し) が処理され、実際のパラメータの詳細が抽出されます。

${\displaystyle \operatorname {build-param-lists} [E\ P,D,V,R]\equiv \operatorname {build-param-lists} [E,D,V,T]\land \operatorname {build-param-lists} [P,D,V,K]}$

${\displaystyle \land T=[F,S,A]::R\land (S\implies (\operatorname {equate} [A,P]\land V[F]=A))\land D[F]=K}$

式とパラメータのパラメータリストを取得します。式のパラメータリストからパラメータレコードを取得し、現在のパラメータ値がこのパラメータと一致することを確認します。パラメータ名の値を記録しておき、後で確認に使用します。

${\displaystyle {\begin{cases}\operatorname {equate} [A,N]\equiv A=N\lor (\operatorname {def} [V[N]]\land A=V[N])&{\text{if }}N{\text{ is a variable.}}\\\operatorname {equate} [A,E]\equiv A=E&{\text{otherwise.}}\end{cases}}}$

上記のロジックは、その動作が非常に微妙です。同一値インジケータがtrueに設定されることはありません。すべての値が一致しない場合にのみfalseに設定されます。値は、Sを使用して、 Sに許容されるブール値の集合を構築することで取得されます。trueがメンバーである場合、このパラメータのすべての値は等しいため、パラメータは削除できます。

${\displaystyle \operatorname {ask} [S]\equiv S\in \{X:X=S\}}$

同様に、def は集合論を使用して、変数に値が与えられているかどうかを照会します。

${\displaystyle \operatorname {def} [F]\equiv |\{X:X=F\}|}$

Let - Let 式。

${\displaystyle \operatorname {build-param-list} [\operatorname {let} V:E\operatorname {in} L,D,V,\_]\equiv \operatorname {build-param-list} [E,D,V,\_]\land \operatorname {build-param-list} [L,D,V,\_]}$

And - 「let」で使用します。

${\displaystyle \operatorname {build-param-lists} [E\land F,D,V,\_]\equiv \operatorname {build-param-lists} [E,D,V,\_]\land \operatorname {build-param-lists} [F,D,V,\_]}$

例

例えば、パラメータリストを構築する場合、

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

与える、

${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\operatorname {true} ,p],[y,\operatorname {true} ,n]]}$

パラメータoは省略され、

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ n)\ (g\ q\ n)))\ \lambda x.\lambda y.p\ x\ y}$

ビルドパラメータリスト ${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$
ビルドパラメータリストの例
${\displaystyle \operatorname {build-param-list} [\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y,D,V,\_]}$ ルール 表現 抽象化 ${\displaystyle \operatorname {build-param-list} [\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y,D,V,\_]}$ 抽象化 ${\displaystyle \operatorname {build-param-list} [(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y,D,V,\_]}$ ${\displaystyle \operatorname {build-param-lists} [n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,V,R]\land \operatorname {build-list} [\lambda x.\lambda o.\lambda y.o\ x\ y,D,V,D[g]]}$ ${\displaystyle \operatorname {build-list} [\lambda x.\lambda o.\lambda y.o\ x\ y,D,V,D[g]]}$ ルール 表現 パラメータを追加 ${\displaystyle \operatorname {build-list} [\lambda x.\lambda o.\lambda y.o\ x\ y,D,V,D[g]]\land D[g]=L_{1}}$ パラメータを追加 ${\displaystyle \operatorname {build-list} [\lambda o.\lambda y.o\ x\ y,D,V,L_{1}]\land D[g]=[x,\_,\_]::L_{1}}$ パラメータを追加 ${\displaystyle \operatorname {build-list} [\lambda y.o\ x\ y,D,V,L_{2}]\land D[g]=[x,\_,\_]::[o,\_,\_]::L_{2}}$ リスト終了 ${\displaystyle \operatorname {build-list} [o\ x\ y,D,V,L_{3}]\land D[g]=[x,\_,\_]::[o,\_,\_]::[y,\_,\_]::L_{3}}$ ${\displaystyle \operatorname {build-param-lists} [o\ x\ y,D,V,[]]\land D[g]=[x,\_,\_]::[o,\_,\_]::[y,\_,\_]::[]}$ ${\displaystyle \operatorname {build-param-lists} [n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,V,R]}$ ルール 表現 応用 ${\displaystyle \operatorname {build-param-lists} [n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,V,R]}$ 応用 ${\displaystyle \operatorname {build-param-lists} [n\ (g\ m\ p\ n),D,V,T_{1}]\land \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]}$ ${\displaystyle \land ((T_{1}=[F_{1},S_{1},A_{1}]::R}$ ${\displaystyle \land (S_{1}\implies (\operatorname {equate} [A_{1},g\ q\ p\ n]\land V[F_{1}]=g\ q\ p\ n))\land D[F_{1}]=K_{1})}$ 変数 ${\displaystyle \operatorname {build-param-lists} [n,D,V,T_{2}]\land \operatorname {build-param-lists} [g\ m\ p\ n,D,V,K_{2}]\land \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]}$ ${\displaystyle \land ((T_{2}=[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::R}$ ${\displaystyle \land (S_{1}\implies (\operatorname {equate} [A_{1},g\ q\ p\ n]\land V[F_{1}]=g\ q\ p\ n))\land D[F_{1}]=K_{1})}$ ${\displaystyle \land (S_{2}\implies (\operatorname {equate} [A_{2},g\ m\ p\ n]\land V[F_{2}]=g\ m\ p\ n))\land D[F_{2}]=K_{2})}$ 変数 ${\displaystyle \operatorname {build-param-lists} [g\ m\ p\ n,D,V,K_{2}]\land \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]}$ ${\displaystyle \land ((D[n]=[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::R}$ ${\displaystyle \land (S_{1}\implies (\operatorname {equate} [A_{1},g\ q\ p\ n]\land V[F_{1}]=g\ q\ p\ n))\land D[F_{1}]=K_{1})}$ ${\displaystyle \land (S_{2}\implies (\operatorname {equate} [A_{2},g\ m\ p\ n]\land V[F_{2}]=g\ m\ p\ n))\land D[F_{2}]=K_{2})}$ 与える、 ${\displaystyle D[n]=[\_,\_,g\ m\ p\ n]::[\_,\_,g\ q\ p\ n]::R}$ ${\displaystyle \operatorname {build-param-lists} [g\ m\ p\ n,D,V,K_{2}]}$ ルール 表現 応用 ${\displaystyle \operatorname {build-param-lists} [g\ m\ p\ n,D,V,K_{2}]}$ ${\displaystyle \operatorname {build-param-lists} [g\ m\ p,D,V,T_{3}]\land \operatorname {build-param-lists} [n,D,V,K_{3}]}$ ${\displaystyle \land ((T_{3}=[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},n]\land V[F_{3}]=n))\land D[F_{3}]=D[n])}$ アプリケーション、変数 ${\displaystyle \operatorname {build-param-lists} [g\ m,D,V,T_{4}]\land \operatorname {build-param-lists} [p,D,V,K_{4}]}$ ${\displaystyle \land T_{4}=[\_,S_{4},A_{4}]::[\_,S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},n]\land V[F_{3}]=n))\land D[F_{3}]=D[n])}$ ${\displaystyle \land (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[F_{4}]=p))\land D[F_{4}]=D[p]}$ アプリケーション、変数 ${\displaystyle \operatorname {build-param-lists} [g,D,V,T_{5}]\land \operatorname {build-param-lists} [m,D,V,K_{5}]}$ ${\displaystyle \land T_{5}=[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},n]\land V[F_{3}]=n))\land D[F_{3}]=D[n])}$ ${\displaystyle \land (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[F_{4}]=p))\land D[F_{4}]=D[p]}$ ${\displaystyle \land (S_{5}\implies (\operatorname {equate} [A_{5},m]\land V[F_{5}]=m))\land D[F_{5}]=D[m]}$ 変数 ${\displaystyle D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},n]\land V[y]=n))\land D[y]=D[n])}$ ${\displaystyle \land (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[o]=p))\land D[o]=D[p]}$ ${\displaystyle \land (S_{5}\implies (\operatorname {equate} [A_{5},m]\land V[x]=m))\land D[x]=D[m]}$ ${\displaystyle \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]}$ ルール 表現 応用 ${\displaystyle \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]}$ ${\displaystyle \operatorname {build-param-lists} [g\ q\ p,D,V,T_{6}]\land \operatorname {build-param-lists} [n,D,V,K_{6}]}$ ${\displaystyle \land ((T_{6}=[F_{6},S_{6},A_{6}]::K_{1}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},n]\land V[F_{6}]=n))\land D[F_{6}]=D[n])}$ アプリケーション、変数 ${\displaystyle \operatorname {build-param-lists} [g\ q,D,V,T_{7}]\land \operatorname {build-param-lists} [p,D,V,K_{7}]}$ ${\displaystyle \land T_{7}=[\_,S_{7},A_{7}]::[\_,S_{6},A_{6}]::K_{1}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},n]\land V[F_{6}]=n))\land D[F_{6}]=D[n])}$ ${\displaystyle \land (S_{7}\implies (\operatorname {equate} [A_{7},p]\land V[F_{7}]=p))\land D[F_{7}]=D[p]}$ アプリケーション、変数 ${\displaystyle \operatorname {build-param-lists} [g,D,V,T_{8}]\land \operatorname {build-param-lists} [m,D,V,K_{8}]}$ ${\displaystyle \land T_{8}=[F_{8},S_{8},A_{8}]::[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{1}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},n]\land V[F_{6}]=n))\land D[F_{6}]=D[n])}$ ${\displaystyle \land (S_{7}\implies (\operatorname {equate} [A_{7},p]\land V[F_{7}]=p))\land D[F_{7}]=D[p]}$ ${\displaystyle \land (S_{8}\implies (\operatorname {equate} [A_{8},q]\land V[F_{8}]=q))\land D[F_{8}]=D[q]}$ 変数 ${\displaystyle D[g]=[x,S_{8},A_{8}]::[o,S_{6},A_{7}]::[y,S_{6},A_{6}]::K_{1}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},n]\land V[y]=n))\land D[y]=D[n])}$ ${\displaystyle \land (S_{7}\implies (\operatorname {equate} [A_{7},p]\land V[o]=p))\land D[o]=D[p]}$ ${\displaystyle \land (S_{8}\implies (\operatorname {equate} [A_{8},q]\land V[x]=q))\land D[x]=D[q]}$ の定義がないので、equateは次のように簡略化できる。 ${\displaystyle V[n],V[p],V[q],V[m]}$ ${\displaystyle \operatorname {equate} [A,N]\equiv A=N\lor (\operatorname {def} [V[N]]\land A=V[N])\equiv A=N}$ 不要な表現を削除することで、 ${\displaystyle D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land S_{3}\implies A_{3}=n}$ ${\displaystyle \land S_{4}\implies A_{4}=p}$ ${\displaystyle \land S_{5}\implies A_{5}=m}$ ${\displaystyle D[g]=[x,S_{8},A_{8}]::[o,S_{6},A_{7}]::[y,S_{6},A_{6}]::K_{1}}$ ${\displaystyle \land S_{6}\implies A_{6}=n}$ ${\displaystyle \land S_{7}\implies A_{7}=p}$ ${\displaystyle \land S_{8}\implies A_{8}=q}$ の2つの式を比較すると、 ${\displaystyle D[g]}$ ${\displaystyle S_{5}=S_{8},A_{5}=A_{8},S_{4}=S_{7},A_{4}=A_{7},S_{3}=S_{6},A_{3}=A_{6}}$ が真の場合; ${\displaystyle S_{3}}$ ${\displaystyle n=A_{3}=A_{6}=n}$ が偽の場合、何の含意もありません。つまり、真か偽かのどちらかです。 ${\displaystyle S_{3}}$ ${\displaystyle S_{3}=\_}$ が真の場合; ${\displaystyle S_{4}}$ ${\displaystyle p=A_{4}=A_{7}=p}$ が真の場合; ${\displaystyle S_{5}}$ ${\displaystyle m=A_{5}=A_{8}=q}$ それは誤りです。 ${\displaystyle S_{5}}$ その結果、 ${\displaystyle D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_}$ ${\displaystyle \operatorname {build-param-lists} [o\ x\ y,D,V,L]}$ ルール 表現 応用 ${\displaystyle \operatorname {build-param-lists} [o\ x\ y,D,V,L]}$ 応用 ${\displaystyle \operatorname {build-param-lists} [o\ x,D,V,T_{9}]\land \operatorname {build-param-lists} [y,D,V,K_{9}]}$ ${\displaystyle \land T_{9}=[F_{9},S_{9},A_{9}]::L}$ ${\displaystyle \land (S_{9}\implies (\operatorname {equate} [A_{9},y]\land V[F_{9}]=A_{9})\land K_{9}=D[F_{9}]}$ 変数 ${\displaystyle \operatorname {build-param-lists} [o,D,V,T_{10}]\land \operatorname {build-param-lists} [x,D,V,K_{10}]\land \operatorname {build-param-lists} [y,D,V,K_{10}]}$ ${\displaystyle \land T_{10}=[F_{10},S_{10},A_{10}]::[F_{9},S_{9},A_{9}]::L}$ ${\displaystyle \land (S_{9}\implies (\operatorname {equate} [A_{9},y]\land V[F_{9}]=A_{9})\land K_{9}=D[F_{9}]}$ ${\displaystyle \land (S_{10}\implies (\operatorname {equate} [A_{10},y]\land V[F_{10}]=A_{10})\land K_{10}=D[F_{10}]}$ ${\displaystyle \land D[o]=[F_{10},S_{10},A_{10}]::[F_{9},S_{9},A_{9}]::L}$ ${\displaystyle \land (S_{9}\implies (\operatorname {equate} [A_{9},y]\land V[F_{9}]=A_{9})\land K_{9}=D[F_{9}]}$ ${\displaystyle \land (S_{10}\implies (\operatorname {equate} [A_{10},y]\land V[F_{10}]=A_{10})\land K_{10}=D[F_{10}]}$ 上記と同様の議論により、 ${\displaystyle D[o]=[\_,\_,x]::[\_,\_,y]::\_}$ そして以前から、 ${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\operatorname {true} ,p],[y,\operatorname {true} ,n]]}$ ${\displaystyle D[n]=[[\_,\_,(g\ m\ p\ n)],[\_,\_,(g\ q\ p\ n)]]}$ ${\displaystyle D[m]=\_}$ ${\displaystyle D[p]=\_}$ ${\displaystyle D[q]=\_}$

もう一つの例は、

${\displaystyle \lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))}$

ここでxはfに等しい。パラメータリストのマッピングは、

${\displaystyle D[p]=[[q,\_,p],[x,\_,f]]}$

そしてパラメータxは省略され、

${\displaystyle \lambda f.((\lambda q.f\ (q\ q))\ (\lambda q.f\ (q\ q))}$

ビルドパラメータリスト ${\displaystyle \lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))}$

このより難しい例では、 equateのロジックが使用されています。 ${\displaystyle \operatorname {build-param-list} [\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x)),D,V,\_]}$ ルール 表現 抽象化 ${\displaystyle \operatorname {build-param-list} [\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x)),D,V,\_]}$ 抽象化 ${\displaystyle \operatorname {build-param-list} [(\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x)),D,V,\_]}$ ${\displaystyle \operatorname {build-param-lists} [f\ (p\ p\ f),D,\_]\land \operatorname {build-list} [\lambda q.\lambda x.x\ (q\ q\ x),D,D[p]]}$ ${\displaystyle \operatorname {build-param-lists} [f\ (p\ p\ f),D,\_]\land \operatorname {build-list} [\lambda q.\lambda x.x\ (q\ q\ x),D,D[p]]}$ ${\displaystyle \operatorname {build-list} [\lambda q.\lambda x.x\ (q\ q\ x),D,D[p]]}$ ルール 表現 パラメータを追加 ${\displaystyle \operatorname {build-list} [\lambda q.\lambda x.x\ (q\ q\ x),D,D[p]]\land D[p]=L_{1}}$ パラメータを追加 ${\displaystyle \operatorname {build-list} [\lambda x.x\ (q\ q\ x),D,L_{2}]\land D[p]=[q,\_,\_]::L_{2}}$ リスト終了 ${\displaystyle \operatorname {build-list} [x\ (q\ q\ x),D,L_{3}]\land D[p]=[q,\_,\_]::[x,\_,\_]::L_{3}}$ ${\displaystyle \operatorname {build-param-lists} [x\ (q\ q\ x),D,[]]\land D[p]=[q,\_,\_]::[x,\_,\_]::[]}$ ${\displaystyle \operatorname {build-param-lists} [\lambda p.f\ (p\ p\ f),D,V,T_{1}]}$ ルール 表現 抽象化 ${\displaystyle \operatorname {build-param-lists} [\lambda p.f\ (p\ p\ f),D,V,T_{1}]}$ 応用 ${\displaystyle \operatorname {build-param-lists} [f\ (p\ p\ f),D,V,T_{1}]}$ 名前 ${\displaystyle \operatorname {build-param-lists} [f,D,V,T_{2}]\land \operatorname {build-param-lists} [p\ p\ f,D,V,K_{2}]}$ ${\displaystyle \land T_{2}=[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_}$ ${\displaystyle \land (S_{2}\implies (\operatorname {equate} [A_{2},p\ p\ f]\land V[F_{2}]=A_{2}))\land D[F_{2}]=K_{2}}$ 名前 ${\displaystyle \operatorname {build-param-lists} [p\ p\ f,D,V,K_{2}]}$ ${\displaystyle \land D[f]=[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_}$ ${\displaystyle \land (S_{2}\implies (\operatorname {equate} [A_{2},p\ p\ f]\land V[F_{2}]=A_{2}))\land D[F_{2}]=K_{2}}$ 名前 ${\displaystyle \operatorname {build-param-lists} [p\ p,D,V,T_{3}]\land \operatorname {build-param-lists} [f,D,V,K_{3}]}$ ${\displaystyle \land T_{3}=[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[F_{3}]=A_{3}))\land D[F_{3}]=K_{3}}$ 応用 ${\displaystyle \operatorname {build-param-lists} [p\ p,D,V,T_{3}]}$ ${\displaystyle \land T_{3}=[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{2}\implies (\operatorname {equate} [A_{2},p\ p\ f]\land V[F_{2}]=A_{2}))\land D[F_{2}]=K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[F_{3}]=A_{3}))\land D[F_{3}]=D[f]}$ 名前 ${\displaystyle \operatorname {build-param-lists} [p,D,V,T_{4}]\land \operatorname {build-param-lists} [p,D,V,K_{4}]}$ ${\displaystyle \land T_{4}=[F_{4},S_{4},A_{4}]::[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[F_{3}]=A_{3}))\land D[F_{3}]=D[f]}$ ${\displaystyle \land (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[F_{4}]=A_{4}))\land D[F_{4}]=K_{4}}$ ${\displaystyle D[p]=[F_{4},S_{4},A_{4}]::[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[F_{3}]=A_{3}))\land D[F_{3}]=D[f]}$ ${\displaystyle \land (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[F_{4}]=A_{4}))\land D[F_{4}]=D[p]}$ ${\displaystyle \operatorname {build-param-lists} [x\ (q\ q\ x)),D,V,\_]}$ ルール 表現 抽象化 ${\displaystyle \operatorname {build-param-lists} [\lambda q.\lambda x.x\ (q\ q\ x)),D,V,\_]}$ 応用 ${\displaystyle \operatorname {build-param-lists} [x\ (q\ q\ x)),D,V,K_{1}]}$ 名前 ${\displaystyle \operatorname {build-param-lists} [x,D,V,T_{5}]\land \operatorname {build-param-lists} [q\ q\ x,D,V,K_{5}]}$ ${\displaystyle \land T_{5}=[F_{5},S_{5},A_{5}]::\_}$ ${\displaystyle \land (S_{5}\implies (\operatorname {equate} [A_{5},q\ q\ x]\land V[F_{5}]=A_{5}))\land D[F_{5}]=K_{5}}$ 名前 ${\displaystyle \operatorname {build-param-lists} [q\ q\ x,D,V,K_{5}]}$ ${\displaystyle \land D[x]=[F_{5},S_{5},A_{5}]::\_}$ ${\displaystyle \land (S_{5}\implies (\operatorname {equate} [A_{5},q\ q\ x]\land V[F_{5}]=A_{5}))\land D[F_{5}]=K_{5}}$ 名前 ${\displaystyle \operatorname {build-param-lists} [q\ q,D,V,T_{6}]\land \operatorname {build-param-lists} [x,D,V,K_{6}]}$ ${\displaystyle \land T_{6}=[F_{6},S_{6},A_{6}]::K_{5}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=K_{6}}$ 応用 ${\displaystyle \operatorname {build-param-lists} [q\ q,D,V,T_{6}]}$ ${\displaystyle \land T_{6}=[F_{6},S_{6},A_{6}]::K_{5}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ 名前 ${\displaystyle \operatorname {build-param-lists} [q,D,V,T_{7}]\land \operatorname {build-param-lists} [q,D,V,K_{7}]}$ ${\displaystyle \land T_{7}=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ ${\displaystyle \land (S_{7}\implies (\operatorname {equate} [A_{7},q]\land V[F_{7}]=A_{7}))\land D[F_{7}]=K_{7}}$ 名前 ${\displaystyle \operatorname {build-param-lists} [q,D,V,K_{7}]}$ ${\displaystyle \land D[q]=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\displaystyle \land (S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ ${\displaystyle \land (S_{7}\implies (\operatorname {equate} [A_{7},q]\land V[F_{7}]=A_{7}))\land D[F_{7}]=D[q]}$ 結果をまとめて、 ${\displaystyle D[p]=[q,\_,\_]::[x,\_,\_]::L_{3}}$ ${\displaystyle D[p]=[F_{4},S_{4},A_{4}]::[F_{3},S_{3},A_{3}]::K_{2}}$ ${\displaystyle \land (S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[F_{3}]=A_{3}))\land D[F_{3}]=D[f]}$ ${\displaystyle \land (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[F_{4}]=A_{4}))\land D[F_{4}]=D[p]}$ ${\displaystyle D[q]=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\displaystyle (S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ ${\displaystyle (S_{7}\implies (\operatorname {equate} [A_{7},q]\land V[F_{7}]=A_{7}))\land D[F_{7}]=D[q]}$ の 2 つの定義から; ${\displaystyle D[p]}$ ${\displaystyle F_{4}=q}$ ${\displaystyle F_{3}=x}$ それで ${\displaystyle D[p]=[q,S_{4},A_{4}]::[x,S_{3},A_{3}]::K_{2}}$ ${\displaystyle (S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[x]=A_{3}))\land D[x]=D[f]}$ ${\displaystyle (S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[q]=A_{4}))\land D[q]=D[p]}$ 使用して ${\displaystyle D[q]=D[p]}$ ${\displaystyle D[p]=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\displaystyle (S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ ${\displaystyle (S_{7}\implies (\operatorname {equate} [A_{7},q]\land V[F_{7}]=A_{7}))\land D[F_{7}]=D[q]}$ 上記と比較すると、 ${\displaystyle F_{7}=q,F_{6}=x,A_{3}=A_{6},A_{4}=A_{7},S_{3}=S_{6},S_{4}=S_{7}}$ それで、 ${\displaystyle V[x]=A_{3}}$ ${\displaystyle V[q]=A_{4}}$ で、 ${\displaystyle S_{3}\implies A_{3}=f}$ ${\displaystyle S_{3}\implies (A_{3}=x\lor A_{3}=v[x])}$ 次のように減少する。 ${\displaystyle S_{3}\implies A_{3}=f}$ また、 ${\displaystyle S_{4}\implies A_{4}=p}$ ${\displaystyle S_{4}\implies (A_{4}=q\lor A_{4}=v[q])}$ 次のように減少する。 ${\displaystyle S_{4}\implies A_{4}=p}$ したがって、p のパラメータ リストは実質的に次のようになります。 ${\displaystyle D[p]=[q,\_,p]::[x,\_,f]::\_}$

ドロップパラメータ

ビルドパラメータリストによって得られた情報を使用して、不要になった実際のパラメータを削除します。drop -paramsには、

• パラメータを削除するラムダ式。
• 変数名とパラメータ リスト (ビルド パラメータ リストに組み込まれている) のマッピング。
• ラムダ式内の変数のセットを解放します。
• 返されるパラメータリスト。アルゴリズム内部で使用されるパラメータ。

抽象化

${\displaystyle \operatorname {drop-params} [(\lambda N.S)\ L,D,V,R]\equiv (\lambda N.\operatorname {drop-params} [S,D,F,R])\ \operatorname {drop-formal} [D[N],L,F]}$

どこ、

${\displaystyle F=FV[(\lambda N.S)\ L]}$

${\displaystyle \operatorname {drop-params} [\lambda N.S,D,V,R]\equiv (\lambda N.\operatorname {drop-params} [S,D,F,R])}$

どこ、

${\displaystyle F=FV[\lambda N.S]}$

変数

${\displaystyle \operatorname {drop-params} [N,D,V,D[N]]\equiv N}$

関数名またはパラメータの場合は、この名前のパラメータ リストを出力することによって、実際のパラメータ リストの入力を開始します。

アプリケーション- アプリケーション（関数呼び出し）が処理され、

${\displaystyle (\operatorname {def} [F]\land \operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R]}$

${\displaystyle \neg (\operatorname {def} [F]\land \operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R]\ \operatorname {drop-params} [P,D,V,\_]}$

Let - Let 式。

${\displaystyle \operatorname {drop-params} [\operatorname {let} V:E\operatorname {in} L]\equiv \operatorname {let} V:\operatorname {drop-params} [E,D,FV[E],[]]\operatorname {in} \operatorname {drop-params} [L,D,FV[L],[]]}$

And - 「let」で使用します。

${\displaystyle \operatorname {drop-params} [E\land F,D,V,\_]\equiv \operatorname {drop-params} [E,D,V,\_]\land \operatorname {drop-params} [F,D,V,\_]}$

アプリケーションからパラメータを削除する

${\displaystyle \lambda g.\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n)}$ 状態 表現 ${\displaystyle \operatorname {drop-param} [\lambda g.\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\displaystyle \lambda g.\operatorname {drop-param} [\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\displaystyle \neg (\operatorname {def} [F_{1}]\land ...)}$ ${\displaystyle \lambda g.\lambda n.\operatorname {drop-param} [n\ (g\ m\ p\ n),D,\{p,q,m\},[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\displaystyle \neg (\operatorname {def} [F_{2}]\land ...)}$ ${\displaystyle \lambda g.\lambda n.\operatorname {drop-param} [n\ ,D,\{p,q,m\},[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-param} [(g\ m\ p\ n),D,\{p,q,m\},\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\displaystyle D[n]=[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]}$ ${\displaystyle \lambda g.\lambda n.n\ \operatorname {drop-param} [(g\ m\ p\ n),D,\{p,q,m\},\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]}$ パラメータリストの構築結果から; ${\displaystyle D[n]=[[\_,\_,(g\ m\ p\ n)],[\_,\_,(g\ q\ p\ n)]]}$ それで、 ${\displaystyle F_{1}=\_}$ ${\displaystyle F_{2}=\_}$ それで、 ${\displaystyle \operatorname {def} [F_{1}]=\operatorname {false} }$ ${\displaystyle \operatorname {def} [F_{2}]=\operatorname {false} }$ ${\displaystyle \operatorname {drop-param} [(g\ m\ p\ n),D,\{p,q,m\},\_]}$ 状態 拡大 表現 ${\displaystyle V=\{p,q,m\}}$ ${\displaystyle \operatorname {drop-param} [(g\ m\ p\ n),D,V,\_]}$ ${\displaystyle FV(A_{1})\not \subset \{p,q,m\}}$ ${\displaystyle n\not \subset \{p,q,m\}}$ ${\displaystyle \operatorname {drop-params} [g\ m\ p,D,V,[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\displaystyle \operatorname {def} [F_{2}]\land \operatorname {ask} [S_{2}]\land FV[A_{2}]\subset V}$ ${\displaystyle \operatorname {def} [y]\land \operatorname {ask} [\_]\land FV[p]\subset \{p,q,m\}}$ ${\displaystyle \operatorname {drop-params} [g\ m,D,V,[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\displaystyle \neg \operatorname {ask} [S_{3}]}$ ${\displaystyle \neg \operatorname {ask} [\operatorname {false} ]}$ ${\displaystyle \operatorname {drop-params} [g,D,V,[F_{3},S_{3},A_{3}]::[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [m,D,V,\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\_,p],[y,\_,n]]}$ ${\displaystyle =[F_{3},S_{3},A_{3}]::[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]}$ ${\displaystyle F_{3}=x,S_{3}=\operatorname {false} ,A_{3}=\_}$ ${\displaystyle F_{2}=o,S_{2}=\_,A_{2}=p}$ ${\displaystyle F_{1}=y,S_{1}=\_,A_{1}=n}$ ${\displaystyle g\ m\ n}$ ${\displaystyle \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]}$ 状態 拡大 表現 V = \{p, q, m\} ${\displaystyle \operatorname {drop-param} [(g\ q\ p\ n),D,V,\_]}$ ${\displaystyle FV(A_{4})\not \subset V}$ ${\displaystyle n\not \subset \{p,q,m\}}$ ${\displaystyle \operatorname {drop-params} [g\ q\ p,D,V,[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\displaystyle \operatorname {def} [F_{5}]\land \operatorname {ask} [S_{5}]\land FV[A_{5}]\subset V}$ ${\displaystyle \operatorname {def} [o]\land \operatorname {ask} [\_]\land p\subset \{p,q,m\})}$ ${\displaystyle \operatorname {drop-params} [g\ q,D,V,[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\displaystyle \neg \operatorname {ask} [S-6]}$ ${\displaystyle \neg \operatorname {ask} [\operatorname {false} ]}$ ${\displaystyle \operatorname {drop-params} [g,D,V,[F_{6},S_{6},A_{6}]::[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [m,D,V,\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\_,p],[y,\_,n]]}$ ${\displaystyle =[F_{6},S_{6},A_{6}]::[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]}$ ${\displaystyle F_{6}=x,S_{6}=\operatorname {false} ,A_{6}=\_}$ ${\displaystyle F_{5}=o,S_{5}=\_,A_{5}=p}$ ${\displaystyle F_{4}=y,S_{4}=\_,A_{4}=n}$ ${\displaystyle g\ q\ n}$

形式パラメータを削除する

drop-formalは、ドロップリストの内容に基づいて仮パラメータを削除します。そのパラメータは以下のとおりです。

• ドロップリスト、
• 関数の定義 (ラムダ抽象化)。
• 関数定義からの自由変数。

ドロップフォーマルとは、

1. ${\displaystyle (\operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-formal} [[F,S,A]::Z,\lambda F.Y,V]\equiv \operatorname {drop-formal} [[F,S,A]::Z,Y[F:=A],L]}$
2. ${\displaystyle \neg (\operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-formal} [[F,S,A]::Z,\lambda F.Y,V]\equiv \lambda F.\operatorname {drop-formal} [[F,S,A]::Z,Y,V]}$
3. ${\displaystyle \operatorname {drop-formal} [Z,Y,V]\equiv Y}$

これは次のように説明できる。

1. すべての実際のパラメータが同じ値を持ち、その値のすべての自由変数が関数の定義に使用できる場合は、パラメータを削除し、古いパラメータをその値に置き換えます。
2. それ以外の場合はパラメータを削除しないでください。
3. それ以外の場合は関数の本体を返します。

状態	表現
${\displaystyle \operatorname {false} }$	${\displaystyle \operatorname {drop-formal} [D,\lambda x.\lambda o.\lambda y.o\ x\ y,F]}$
${\displaystyle \operatorname {true} \land \{p\}\subset F}$	${\displaystyle \lambda x.\operatorname {drop-formal} [D,\lambda o.\lambda y.o\ x\ y,F]}$
${\displaystyle \neg (\operatorname {true} \land \{n\}\subset F}$）	${\displaystyle \lambda x.\operatorname {drop-formal} [D,(\lambda y.o\ x\ y)[o:=p],F]}$
	${\displaystyle \lambda x.\lambda y.\operatorname {drop-formal} [D,p\ x\ y,F]}$
	${\displaystyle \lambda x.\lambda y.p\ x\ y}$

例

Yコンビネータの関数定義から始めると、

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p\ }$

変換	表現
	${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p}$
要約* 4	${\displaystyle \operatorname {let} p=\lambda f.\lambda x.f\ (x\ x)\land q=\lambda p.\lambda f.(p\ f)\ (p\ f)\operatorname {in} q\ p}$
ラムダ抽象トランザクション	${\displaystyle (\lambda q.(\lambda p.q\ p)\ (\lambda f.\lambda x.f\ (x\ x)))\ (\lambda p.\lambda f.(p\ f)\ (p\ f))}$
シンクトラン	${\displaystyle (\lambda p.\lambda f.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))}$
シンクトラン	${\displaystyle \lambda f.(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))}$
ドロップパラメータ	${\displaystyle \lambda f.(\lambda p.p\ p)\ (\lambda x.f\ (x\ x))}$
ベータ-レデックス	${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ }$

Yコンビネータを返す。

${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

参照

• Let式
• 固定小数点コンビネータ
• ラムダ計算
• 演繹的ラムダ計算
• スーパーコンビネーター
• カリーのパラドックス

参考文献

1. ジョンソン、トーマス (1985). 「ラムダリフティング：プログラムから再帰方程式への変換」. ジュアンノー、JP (編).関数型プログラミング言語とコンピュータアーキテクチャ. FPCA 1985 . コンピュータサイエンス講義ノート. 第201巻. シュプリンガー. CiteSeerX  10.1.1.48.4346 . doi :10.1007/3-540-15975-4_37. ISBN 3-540-15975-4。
2. Morazán, Marco T.; Schultz, Ulrik P. (2008). 「Optimal Lambda Lifting in Quadratic Time」.関数型言語の実装と応用 ― 改訂選集. pp.  37– 56. doi :10.1007/978-3-540-85373-2_3. ISBN 978-3-540-85372-5。
3. Danvy, O.; Schultz, UP (1997). 「ラムダドロップ」. ACM SIGPLAN Notices . 32 (12): 90– 106. doi : 10.1145/258994.259007 .
4. Danvy, Olivier; Schultz, Ulrik P. (2000年10月). 「ラムダドロップ：再帰方程式をブロック構造のプログラムに変換する」(PDF) .理論計算機科学. 248 ( 1–2 ): 243– 287. CiteSeerX 10.1.1.16.3943 . doi :10.1016/S0304-3975(00)00054-2. BRICS-RS-99-27. 

外部リンク

• Stack Overflow での説明（JavaScript の例付き）
• スロネガー、ケン、カーツ、バリー。「5. let式についての考察」(PDF)プログラミング言語の基礎. アイオワ大学。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lambda_lifting&oldid=1323097752"