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
2337 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>