問題タブ [lambda-calculus]

以下の式の構文木をどのように描画するかを理解しようとしています。まず、これはどの程度正確に動作していますか？パラメータとして1と2を使用しているように見えますが、nが0の場合は、を返しmます。

また、誰かがツリーまたは例を解析するための開始点を示すことができますか？見つかりませんでした。

コードの見た目、感触、ラムダ計算の抽象化のように動作するという点で、ラムダ計算に最も近い FP 言語はどれですか?

関数型プログラミングを学習しているときに、チャーチ ロッサーの定理、特にダイヤモンド プロパティ ダイアグラムへの参照を何度も見てきましたが、優れたコード例に出くわすことはできませんでした。

Haskell のような言語を一種のラムダ計算と見なすことができる場合、その言語自体を使用していくつかの例を作成することが可能であるに違いありません。

ステップまたは削減が簡単に並列化可能な実行につながる方法を例が簡単に示していれば、ボーナスポイントを与えることができます。

学校の課題のために、このスキームのラムダ構造を排除する必要があります。

これを達成する方法はありますか？

Haskellで不純な型なしラムダ計算インタープリターを実装しています。

私は現在、「alpha-congruence」（一部の教科書では「alpha-equivalent」または「alpha-equality」とも呼ばれます）の実装に固執しています。2つのラムダ式が互いに等しいかどうかを確認できるようにしたいと思います。たとえば、インタプリタに次の式を入力すると、True（\ラムダ記号を示すために使用されます）が生成されます。

問題は、次のラムダ式がアルファ等価と見なされるかどうかを理解することです。

私の場合\x.xy == \y.yx、答えはTrueです。これは、\x.xy => \z.zyと\y.yx => \z.zyと両方の右側が等しいためです（記号=>はアルファリダクションを示すために使用されます）。

のcaeで\x.yxy == \z.wzw私は同様に答えがであると推測しますTrue。これは、\x.yxy => \a.yay（\z.wzw => \a.waw私が思うに）どちらが等しいからです。

問題は、私の教科書のすべての定義で、2つのラムダ式が等しいと見なされるには、バインドされた変数の名前のみを変更する必要があると述べられていることです。式の自由変数についても、一律に名前を変更する必要があることについては何も述べていません。したがって、yとwは両方ともラムダ式の正しい位置にありますが、プログラムは、最初が最初を表し、2番目が2番目を表すことをどのように「認識」yしますwか。実装では、これについて一貫している必要があります。yw

つまり、エラーのないバージョンの関数を実装するにはどうすればよいでしょうisAlphaCongruentか。これが機能するために私が従う必要がある正確なルールは何ですか？

deBruijnインデックスを使用せずにこれを実行したいと思います。

興味深い質問がありますが、正確にどのように表現すればよいかわかりません...

ラムダ計算を考えてみましょう。与えられたラムダ式に対して、いくつかの可能な削減順序があります。しかし、これらの中には終了しないものもあれば、終了するものもあります。

ラムダ計算では、1つの特定の還元次数があり、それが実際に存在する場合、常に既約解で終了することが保証されていることがわかります。それは通常の順序と呼ばれます。

簡単なロジックソルバーを作成しました。しかし、問題は、制約を処理する順序が、解決策を見つけるかどうかに大きな影響を与えるように見えることです。基本的に、私の論理プログラミング言語には通常の順序のようなものが存在するかどうか疑問に思っています。（または、単なるマシンでこの問題を決定論的に解決することは不可能かどうか。）

それが私が求めているものです。おそらく、答えは「単純な論理ソルバー」が何であるかによって大きく異なります。それで、簡単に説明しようと思います。

私のプログラムは、 The Fun of Programming（Jeremy Gibbons＆Oege de Moor）の第9章にあるコンビネータのシステムに密接に基づいています。言語の構造は次のとおりです。

• ソルバーへの入力は単一の述語です。述語には変数が含まれる場合があります。ソルバーからの出力は、0個以上の解です。解決策は、述語を真にする一連の変数割り当てです。

• 変数は式を保持します。式は、整数、変数名、または部分式のタプルです。

• 式（述語ではない）を比較して等価である等式述語があります。すべての（バインドされた）変数をその値で置き換えると、2つの式が同一になります。（特に、すべての変数は、バインドされているかどうかに関係なく、それ自体と等しくなります。）この述語は、統合を使用して解決されます。

• ANDとORの演算子もあり、これらは明白な方法で機能します。NOT演算子はありません。

• 基本的にローカル変数を作成する「exists」演算子があります。

• 名前付き述部を定義する機能により、再帰的なループが可能になります。

論理プログラミングの「興味深い点」の1つは、名前付き述語を作成すると、通常は前後方向（場合によっては横方向）に機能することです。標準的な例：2つのリストを連結する述語を使用して、リストをすべての可能なペアに分割することもできます。

ただし、用語の順序を並べ替えない限り、述語を逆方向に実行すると、検索が無限になることがあります。（たとえば、ANDまたはORのLHSとRHSを交換します。）ソリューションセットが正確に設定されているすべての場合に迅速に終了するために、述語を実行するための最良の順序を検出する自動化された方法があるかどうか疑問に思っています。有限の。

助言がありますか？

Wikiでラムダ計算を読んでいるときに、キャプチャ回避置換という用語に出くわしました。どこからともなく定義が見つからなかったので、誰かがそれが何を意味するのか説明してもらえますか？

ありがとう

PS

私が知りたいのは、その操作をキャプチャ回避置換に伝える理由です。誰かがそれをすることができればそれは大きな助けになるでしょう

私はラムダ計算が初めてで、チュートリアルを読んでいるときにこれに出くわしました。これが私の方程式です。

ここで、別の項、たとえば F (YF) を適用すると、これをどのように減らすことができますか? ベータ簡約に従って私が正しければ、 ( ƛx.f(xx))のすべてのfを ( ƛx. f(xx))、これは正しいですか。そうであれば、どうすればそれを行うことができますか。

ありがとう

ラムダ計算について読んでいるときに、ラムダ定義可能性という言葉に出くわしました。良いリソースが見つからなかったので、誰かがそれが何であるかを説明できますか？

ありがとう