3

私は次のPrologコードに直面しています。式[X]>>Yは、ラムダ式lambda XYを表します。コードはラムダを削除し、S、K、およびIの組み合わせ式を提供します。

convert([X]>>Y,'I') :- X==Y, !.
convert([X]>>Y,apply('K',Y)) :- var(Y), !.
convert([X]>>([Y]>>Z),R) :-
     convert([Y]>>Z,H), convert([X]>>H,R).
convert([X]>>apply(Y,Z),apply(apply('S',S),T)) :-
     convert([X]>>Y,S), convert([X]>>Z,T).
convert([_]>>Y,apply('K',Y)).

仕組みの例を次に示します。

 ?- convert([X]>>([Y]>>apply(Y,X)),R).
 R = apply(apply('S', apply(apply('S', apply('K', 'S')), 
  apply('K', 'I'))), apply(apply('S', apply('K', 'K')), 'I'))

HaskellやMLなどで同じ変換をコーディングしたいとします。これどうやってするの？関数型プログラミング言語で利用可能なラムダ式を直接使用できますか？または、いくつかのメタプログラミング機能に回帰する必要がありますか？

よろしくお願いします

PS：上記のコードは、非常に短いSKI式につながるSKI変換ではありません。ラムダ式本体でバインドされた変数の出現をチェックするより良いコードが可能です。

4

2 に答える 2

3

あなたのプロローグコードは、MLまたはHaskellのパターンマッチングにほぼ逐語的に翻訳することができます。もちろん、ラムダ式用に独自のADTを定義する必要があります。そして、そのセットに最適なコンビネータと変換のセットについては、http：//www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497を参照することをお勧めします。

于 2011-01-21T11:50:34.870 に答える
1

lamdba式を直接使用できます。Haskellの場合：

i x = x
k x = \y -> x
s x y z = x z $ y z

r = s (s (k s) (k i)) (s (k k) i)

-- r 3 (+5) -> 8

（私が知るまでSKIについて知らなかったことに注意してください。このスニペットは、ウィキペディアの定義をHaskellに直接変換したものです。機能しますが、概念的に正しいかどうかを確認してください）

于 2011-01-21T08:31:10.813 に答える