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)

I'm not sure whether that closed lambda term is a combinator, so I'm not sure if it's even eligible to be cancellative. Sorry if that sounds like a handwave, but I found that I needed to draw the distinction in order to even talk about non-SK bases. Corbin (talk) 20:03, 17 June 2026 (UTC)

That particular closed lambda term can be rewritten as SI(KK).

And what about the citation at the head of the closed lambda term page? --Blashyrkh (talk) 20:30, 17 June 2026 (UTC)

I chose it ironically. Fokker's 1992 paper is good reading if you'd like to see the details. To me, a combinator always produces an applicative tree and has no lambda-abstractions. This is necessary to justify metrics like rank in the first place.

On SI(KK), that makes sense. I'd imagine that this is rank one, since SI(KK)x = xK captures its effect. The resulting applicative tree contains its argument, so it is not cancellative. I hope that this illustrates how precise the definition already is; we first determine which basis we're working in, then define the combinator to find its rank, and finally examine the applicative tree. At the same time, it's somewhat unsatisfying since either x is cancellative because it doesn't use K, or x does use K, which itself is cancellative; but it can't be used to say anything about IJ because we expressed it in SK. Corbin (talk) 20:53, 17 June 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)

Forgot to say at the time: nice work. I've contemplated having multiple columns so that there's expressions in terms of each system. The expressions would be given in terms of what's easiest, which we could discuss a bit. I don't really see the use of Iota/Alpha/Beta here, but I'm used to thinking in terms of wikipedia:graph reduction which eliminates lambdas entirely; see also closed lambda term. Corbin (talk) 20:35, 17 June 2026 (UTC)

Added two more columns, now we have up to 3 expressions for each combinator - in SKI, in BCKW and in IJ bases. Some IJ cells left empty - I just don't know the shortest expression. I could synthesize them from known ones, but the result would be too long. Same for SKI. Regarding V* - there's some controversy about it (at least what I found here: https://blog.lahteenmaki.net/combinator-birds.html). And it's a mystery to me, how Tromp found his shortest SKI expression for Y. I just have no idea how to search for combinators which (or whose application) have no normal form. --Blashyrkh (talk) 12:04, 18 June 2026 (UTC)

Interestingly, I'm seeing a V*xyzw = xwzy (exactly once when V* is introduced) and a V*xyzw = xwyz (pretty much every other instance of V* within the book). I don't know where the site gets V*xyzw = xzyw from. I'm picking the latter since it's more consistent with the name (like a vireo, but once removed), and I'll assume the former is an error. –PkmnQ (talk) 14:14, 18 June 2026 (UTC)

Affine bases

I have removed I from the affine bases because it can be defined from the other combinators in the bases.

CKKx=KxK=x

B(TK)Kx=TK(Kx)=KxK=x

GKKKx=Kx(KK)=x

Therefore, I=CKK, I=B(TK)K, and I=GKKK. Actually, for any bird A, I=CKA and I=B(TA)K. Also, for any birds A₁, A₂, I=GKA₁A₂.

CKAx=KxA=x

B(TA)Kx=TA(Kx)=KxA=x

GKA₁A₂x=Kx(A₁A₂)=x

Therefore, BCK, BTK, and GK are all affine bases. GK is a 2-combinator affine basis. Bobby Jacobs (talk) 18:48, 17 June 2026 (UTC)

Well spotted. All three reductions look correct to me. Thanks for such a neat answer. Corbin (talk) 19:23, 17 June 2026 (UTC)

Do any of you see a potential for computations in affine systems? --Blashyrkh (talk) 19:25, 17 June 2026 (UTC)

You might want a system where you can delete, but not repeat. Bobby Jacobs (talk) 14:52, 23 June 2026 (UTC)

Without possibility to repeat I can't implement recursion (and - more general - loops). Or can I? --Blashyrkh (talk) 15:49, 23 June 2026 (UTC)