Talk:Combinatory logic

From Esolang
Jump to: navigation, search

Simple Bases for Combinatory Logic

It might be worth mentioning that CL (combinatory logic) can be defined in the KS-basis as follows ...

Syntax
------
<combinator> ::= K | S | ( <combinator> <combinator> )

Semantics
---------
((K x) y)  -->  x
(((S x) y) z)  -->  ((x z)(y z))

That's all! And even the right-parenthesis is not needed for disambiguation -- e.g. leave it out altogether, and replace '(' with '*':

Syntax
------
<combinator> ::= K | S | * <combinator> <combinator> 

Semantics
---------
* * K x y  -->  x
* * * S x y z  -->  ** x z * y z

One further step, replacing the KS-basis with any single-combinator basis (call it B -- there are many single-combinator bases), brings us to an even more minimalistic language (we get the language Iota by taking B = i = \x.xSK):

Syntax
------
<combinator> ::= B | * <combinator> <combinator>

Semantics
---------
* B x  -->>  <def'n of the basis combinator B>   (e.g. * i x -->> * * x S K)

It can't get much simpler!

Added note:
It's a theorem in CL that every single-combinator basis is improper; that is, a single combinator cannot properly serve as a basis, because it is itself necessarily defined in terms of two or more other combinators. E.g., the i in Iota is defined in terms of K and S (which are proper combinators -- contrast \x.xSK with \xy.x etc.). So although programs in the resulting language are binary strings on the alphabet {*,B}, they actually amount to encodings of trinary strings on the alphabet {*,K,S}.

--r.e.s.


Role of free and bound variables

In the content page on Combinatory Logic, of course you mean to say

"Each combinator is like a function or lambda abstraction, but without any FREE variables."

--r.e.s.

Yes, thank you. --Chris Pressey 00:39, 2 Jul 2005 (GMT)

Don't understand something

I don't understand something about this article. For example "S K K x". I have understood that "x" also is a combinator, so it's also a series of S and K symbols. Say x is a K. Then what is the meaning of this last K? There's nothing behind it anymore, so it isn't applied to anything. There's no possible thing that x can be that doesn't require another combinator behind it. But there has to be a last combinator somewhere! --Aardwolf 02:21, 27 Oct 2005 (GMT)

You don't need to supply combinators with 'arguments' - when no more reductions are possible, they remaining combinators just sit there. So KKS reduces to K, and that's it. --Safalra 10:29, 27 Oct 2005 (GMT)