可以使用SKI组合器表示XOR吗? [英] Can XOR be expressed using SKI combinators?

问题描述

我对SKI组合器有疑问.

能否仅使用S和K组合器来表示XOR(异或)?

我有

True = Cancel
False = (Swap Cancel)

其中

Cancel x y = K x y = x   
Swap: ff x y = S ff x y = ff y x

解决方案

布尔值

您的问题在细节上还不清楚，但是您的意思似乎是您具有以下布尔值表示形式:

T := K
F := S K

这行得通，因为这意味着可以减少以下费用:

T t e => t
F t e => e

换句话说，b t e可以解释为IF b THEN t ELSE e.

根据IF _ THEN _ ELSE _

的

XOR

因此，有了这个框架，我们如何实现XOR?我们可以将XOR表示为IF表达式:

xor x y := IF x THEN (not y) ELSE y = (IF x THEN not ELSE id) y

可以被eta化为

XOR x := IF x THEN not ELSE id = x not id

某些功能组合器

我们以id = SKK为标准，由于flip b t e = b e t = IF b THEN e ELSE t = IF (not b) THEN t ELSE e，not可以表示为flip. flip它本身涉及很多，但可以作为

flip := S (S (K (S (KS) K)) S) (KK)

现在，我们只需要找到一种编写采用x并将其应用于两个术语NOT和ID的函数的方法.要到达那里，我们首先要注意，如果我们设置

app := id

然后

app f x = (id f) x = f x

等等

(flip app) x f = f x

我们快到了，因为到目前为止一切都表明了这一点

((flip app) id) ((flip app) not x) = ((flip app) not x) id = (x not) id = x not id

最后一步是在x上使最后一行无点.我们可以使用函数组合运算符来做到这一点:

((flip app) id) ((flip app) not x) = compose ((flip app) id) ((flip app) not) x

其中compose的要求是

compose f g x = f (g x)

我们可以通过设置来获得

compose f g := S (K f) g

将它们放在一起

总而言之，我们得到了

xor := compose ((flip app) id) ((flip app) not)

或完全展开:

xor = S (K ((flip app) id)) ((flip app) not)
    = S (K ((flip app) (SKK))) ((flip app) flip)
    = S (K ((flip SKK) (SKK))) ((flip SKK) flip)
    = S (K (((S (S (K (S (KS) K)) S) (KK)) SKK) (SKK))) (((S (S (K (S (KS) K)) S) (KK)) SKK) (S (S (K (S (KS) K)) S) (KK)))

I have question about SKI-Combinators.

Can XOR (exclusive or) be expressed using S and K combinators only?

I have

True = Cancel
False = (Swap Cancel)

where

Cancel x y = K x y = x   
Swap: ff x y = S ff x y = ff y x

解决方案

Booleans

Your question is a bit unclear on the details, but it seems that what you mean is that you have the following representation of booleans:

T := K
F := S K

This works because it means the following reductions hold:

T t e => t
F t e => e

in other words, b t e can be interpreted as IF b THEN t ELSE e.

XOR in terms of IF _ THEN _ ELSE _

So given this framework, how do we implement XOR? We can formulate XOR as an IF expression:

xor x y := IF x THEN (not y) ELSE y = (IF x THEN not ELSE id) y

which can be eta-reduced to

XOR x := IF x THEN not ELSE id = x not id

Some function combinators

We have id = SKK as standard, and not can be expressed as flip, since flip b t e = b e t = IF b THEN e ELSE t = IF (not b) THEN t ELSE e. flip it self is quite involved but doable as

flip := S (S (K (S (KS) K)) S) (KK)

Now we just need to figure out a way to write a function that takes x and applies it on the two terms NOT and ID. To get there, we first note that if we set

app := id

then

app f x = (id f) x = f x

and so,

(flip app) x f = f x

We are almost there, since everything so far shows that

((flip app) id) ((flip app) not x) = ((flip app) not x) id = (x not) id = x not id

The last step is to make that last line point-free on x. We can do that with a function composition operator:

((flip app) id) ((flip app) not x) = compose ((flip app) id) ((flip app) not) x

where the requirement on compose is that

compose f g x = f (g x)

which we can get by setting

compose f g := S (K f) g

Putting it all together

To summarize, we got

xor := compose ((flip app) id) ((flip app) not)

or, fully expanded:

xor = S (K ((flip app) id)) ((flip app) not)
    = S (K ((flip app) (SKK))) ((flip app) flip)
    = S (K ((flip SKK) (SKK))) ((flip SKK) flip)
    = S (K (((S (S (K (S (KS) K)) S) (KK)) SKK) (SKK))) (((S (S (K (S (KS) K)) S) (KK)) SKK) (S (S (K (S (KS) K)) S) (KK)))

这篇关于可以使用SKI组合器表示XOR吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！