SKI 변환, 함수 언어로 프로그래밍하는 방법

Question

다음 Prolog 코드를 직면하고 있습니다. [X] >> Y 표현식은 람다 식 λ X.Y에 대해 입니다. 이 코드는 람다 을 제거하고 S를 통해 조합 적 표현을 제공, K와 나는 :

?- 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')) 

은 가정하자 나도 같은 변환 코드 싶습니다 : 여기

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)). 

어떻게 작동하는지 예입니다 Haskell, ML 또는 에있는 등. 어떻게해야합니까? 함수 프로그래밍 언어에서 직접 사용할 수있는 λ 식을 으로 사용할 수 있습니까? 아니면 일부 메타 프로그래밍 시설에 회귀해야합니까?

안부

P.S : 위의 코드는 매우 짧은 스키 표현에 이르게 SKI 변환되지 않습니다. 의 발생을 람다 식 본문의 바운드 변수로 검사하는 더 나은 코드가 가능합니다.

Answer 1

귀하의 프롤로그 코드는 거의 그대로 ML 또는 하스켈의 패턴 일치로 변환 될 수 있습니다. 물론 람다 식에 대해 자체 ADT를 정의해야합니다. 그리고 가장 최적의 조합기 및 전환 세트에 대해서는 다음을 참조하십시오. http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497

Answer 2

직접 lamdba 식을 사용할 수 있습니다. 하스켈에서 :;

이

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 

(작동하지만 바로 개념인지 확인합니까 내가 알고까지 스키 몰랐다 있습니다,이 조각은 하스켈에 위키 백과에 정의의 직접 변환입니다)