All geek questions in one place

SKI conversion, functional language programming

I came across the following Prolog code. The expression [X] → Y stands for the lambda expression lambda XY The code eliminates the lambda and gives a combinatorial expression over S, K and 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)).

Here is an example of how it works:

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

Suppose I would like to encode the same conversion in Haskell, ML or whatever . How can i do this? Can I use accessible lambda expressions in functional programming language? Or do I need to regress some metaprograms?

Regards

PS: The above code is not a SKI conversion, which leads to a very short SKI Expression. Perhaps the best code that checks for the presence of a bound variable in a lambda expression element.

+3
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

( , SKI, , Haskell, , , )

+1

Source: https://habr.com/ru/post/1786859/

More articles:


All Articles