固有のλ項を与えられたλ引用表現を返す「引用」関数を作成することは可能ですか?

λ-計算をλ-エンコーディングとBruijnインデックスで実装すると仮定します。

Lam = λ body .        λ Lam . λ App . λ Var . Lam body
App = λ fun . λ arg . λ Lam . λ App . λ Var . App fun arg
Var = λ idx .         λ Lam . λ App . λ Var . Var idx

ネイティブの言葉で与えられたλコード化表現を返す
quote()関数を実装することは可能ですか?例えば:

quote(λ f . λ x . f (f x)) 

戻ります:

Lam (Lam (App (Var 1) (App (Var 1) (Var 0))))

もしそうでなければ、タイプが与えられれば可能ですか?

quote(Arr(Arr(T,T),Arr(T,T)), λ f . λ x . f (f x)))

Where Arr(Arr(T,T),Arr(T,T)) represents that the
term we want to quote has the following STLC type: (o ->
o) -> o -> o
.

ベストアンサー

いいえ、これは可能ではありません。あなたが任意のラムダ項からいくつかの一次ASTに行きたいと仮定します。

ラムダ計算は拡張です。つまり、ラムダ計算では、動作上同等な2つのラムダ項を区別できません。たとえば、クイックソートとマージソートを実行する用語がある場合、それらは両方とも内在的に同じ関数なので、他のラムダ用語は区別できません。結果として、完全な見積もりは不可能です。なぜなら、それらの2つの用語に対して異なるソースコードを得ることができるからです。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です