2

F# を使用してラムダ計算を作成しています。私は現在、固定小数点演算子 (Y コンビネーターとも呼ばれます) を実装する方法を見つけようとして立ち往生しています。

それ以外は順調だと思います。式は、次の判別共用体で表されます。

type Expr =
 | Const of int
 | Plus  of Expr * Expr
 | Times of Expr * Expr
 | Minus of Expr * Expr
 | Div   of Expr * Expr
 | Neg   of Expr
 | Var   of string
 | Fun   of string * Expr
 | App   of Expr * Expr
 | If    of Expr * Expr * Expr

私のeval機能はうまくいっているようです。次の例はすべて、期待どおりの結果をもたらします。
例 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
例 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
例 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

しかし、前述したように、ラムダ計算内で固定小数点演算子を実装するのが困難です。ここでは次のように定義されています。
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

誰か提案はありますか？Yコンビネータに関する他の質問を見てきましたが、うまく採用できたものは見つかりませんでした。

すべての助けに感謝します。

編集：コードのタイプミスを修正しました...以前は、識別された組合のMult代わりに持っていました。Minusふと気がついたのがおかしい！

4

2 に答える 2

4

あなたが参照しているバージョンは遅延言語でのみ機能します。言語が遅延評価戦略を使用していない場合、無限ループに陥ります。これを翻訳してみてください：

Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))
于 2010-11-03T10:49:18.783 に答える
1

私が思い出す限り、型なしラムダ計算には Y Combinators のクラス全体がありますが、言語が厳密に型指定されている場合、ML や F# で特殊なケースを実行しようとする人がいるにもかかわらず、1 つでも実装するのが難しくなります。あなたの言語が再帰をサポートしている場合（ラムダ計算はサポートしていません）、あまり役に立たないようです。Stackoverflow が一般的な「関数型プログラミング」または ML でフラグを立てているのを見たそのトピックに関する議論を見てください。いくつかの洞察があると思います。

Yコンビネータの実際の例

于 2010-11-03T11:53:13.190 に答える