Talk:Combinatory logic

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)

Keywords

The keyword pointfree programming (or point-free) should probably appear somewhere on the wiki, because they apply to these combinatory logic systems like the ones on this page and Unlambda, and also for some stack-based languages with no variable bindings such as Underload. I don't know where to mention this, perhaps there should be a separate article for the pointfree programming concept. --(this comment by B jonas at 08:03, 13 September 2018‎ UTC; please sign your comments with ~~~~)

Is there anything between IJ and complete bases?

IJ basis contains all non-cancellative combinators (so called Aristocratic system). Is it enough to add any cancellative combinator to IJ basis to make the basis complete? In other words, is there a non-complete system (other than Aristocratic system itself) that includes Aristocratic system as a subset? --Blashyrkh (talk) 23:14, 23 January 2026 (UTC)

This is a great question. I think that the answer is yes, but I don't have a proof. Certainly IJK is complete. Corbin (talk) 00:11, 24 January 2026 (UTC)

An example proves nothing, but...

I've checked first 23 37 cancellative combinators (User:Blashyrkh/Between IJ and SK), and in all cases an expression of K combinator in IJX basis exists (i.e. IJX basis is proven to be complete where X is the cancellative combinator in question). --Blashyrkh (talk) 08:11, 24 January 2026 (UTC)

What's the exact definition of cancellative combinator?

The page says:

A combinator is cancellative if it does not use all of its arguments.

Should we consider λx.xK a cancellative combinator? Pro: it can't be expressed in IJ basis. Con: it uses all its arguments (x). --Blashyrkh (talk) 12:00, 24 January 2026 (UTC)

An interactive SKI calculator I wrote

It can be inserted to a HTML file easily, while not affecting the environment.

<div style="display:flex;flex-wrap:nowrap;overflow-x:auto;gap:6px;font-family:monospace;white-space:nowrap"><input type="text" placeholder="SII(SI(SKx))"><button onclick="{const i=this.previousElementSibling.value;const o=this.nextElementSibling;let s=[];let h=i.includes('()');let m=true;for(let n=0;n<i.length;n++){const c=i[n];if(c==='('){s.push(n)}else if(c===')'){if(s.length===0){m=false;break}s.pop()}}if(s.length>0)m=false;if(!m||h){o.innerHTML='<span style="color:red">Unmatched Parentheses</span>';return}let r='<span><span></span>';for(let n=0;n<i.length;n++){const c=i[n];if(c==='('){r+='<span><button onclick="{const p=this.parentElement;const o=p.parentElement;if([...o.children].indexOf(p)===1||p.children.length===3){const m=[...p.children].slice(1,-1);const f=document.createDocumentFragment();m.forEach(e=>f.appendChild(e));o.insertBefore(f,p);o.removeChild(p)}}">(</button>'}else if(c===')'){r+='<button>)</button></span>'}else if(c==='S'){r+='<button onclick="{const p=this.parentElement;if([...p.children].indexOf(this)===1&&p.children.length>=6){const c=p.children;const t3=c[2],t4=c[3],t5=c[4];const d=document.createElement(\'span\');const b1=document.createElement(\'button\');b1.setAttribute(\'onclick\',\'{const p=this.parentElement;const o=p.parentElement;if([...o.children].indexOf(p)===1||p.children.length===3){const m=[...p.children].slice(1,-1);const f=document.createDocumentFragment();m.forEach(e=>f.appendChild(e));o.insertBefore(f,p);o.removeChild(p)}}\');b1.textContent=\'(\';const b2=document.createElement(\'button\');b2.textContent=\')\';d.appendChild(b1);d.appendChild(t4);d.appendChild(t5);d.appendChild(b2);const f=document.createDocumentFragment();f.appendChild(t3);f.appendChild(t5.cloneNode(true));f.appendChild(d);p.insertBefore(f,this);p.removeChild(this)}}">S</button>'}else if(c==='K'){r+='<button onclick="{const p=this.parentElement;if([...p.children].indexOf(this)===1&&p.children.length>=5){p.removeChild(p.children[3]);p.removeChild(this)}}">K</button>'}else if(c==='I'){r+='<button onclick="{const p=this.parentElement;if([...p.children].indexOf(this)===1&&p.children.length>=4)p.removeChild(this)}">I</button>'}else{r+='<button>'+c+'</button>'}}r+='<span></span></span>';o.innerHTML=r}">Load -></button><span></span></div>

-- i  s  l  p  t  n  g  01:21, 27 February 2026 (UTC)

Table of common well-studied combinators - other bases?

Would it be useful to give expressions for combinators in the table not only in SKI basis, but also in BCKW, IJ (non-cancellative only), Iota, Alpha and Beta? I've got good collection for IJ basis. --Blashyrkh (talk) 19:34, 3 June 2026 (UTC)

I have added a new column to split the table into definition and formula. The definition expresses the combinator in terms of other combinators. The formula is an equation using variables. For example, for the identity bird I, the definition is SKK and the formula is Ix=x. I guess you can add expressions with J and I. Which combinators have you found IJ expressions? Bobby Jacobs (talk) 16:52, 4 June 2026 (UTC)

Here's my list: Crazy J#BCS+ (unlambda syntax is not very friendly, rewriting in CC style is in my TODO list). And at the moment I'm working on optimized bruteforce program to find any combinators' expressions in any bases. My previous bruteforce program was able to find Beta (Closed lambda term#Completeness) but still searching for expression of S in Beta basis, so I decided to improve it. --Blashyrkh (talk) 17:57, 4 June 2026 (UTC)