スキー変革、機能的な言語でプログラムする方法

Question

私は次のプロログコードに直面しています。式[x] >> yはラムダ式ラムダxyを表します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など。これどうやってするの？機能プログラミング言語で利用可能なLambda式を直接使用できますか？または、いくつかのメタプログラミング施設に回帰する必要がありますか？

よろしくお願いします

PS：上記のコードは、非常に短いスキーの表現につながるスキー変換ではありません。より良いコードは、ラムダ発現本体のバウンド変数の発生をチェックする可能性があります。

Answer 1

Prologコードは、ほぼ逐語的にMLまたはHaskellのパターンマッチングに翻訳できます。もちろん、Lambda式のために独自のADTを定義する必要があります。そして、そのセットのコンビネーターと変換の最も最適なセットのために、私は参照することをお勧めします http://www.amazon.com/functional-programming-international-computer-science/dp/0201192497

Answer 2

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

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