Talk:The Church

I'm not sure if it's optimal (considering it contains the entire C combinator inside it), but *(+^)(**(*^)) is a decently short expression for S. –PkmnQ (talk) 11:19, 9 June 2026 (UTC)

Yup, it is. I still hope my bruteforcer would find something shorter. --Blashyrkh (talk) 11:43, 9 June 2026 (UTC)

Your solution is optimal. There's no size-6 solution for S. --Blashyrkh (talk) 10:48, 14 June 2026 (UTC)

isnt this syntactically invalid? ((+^) and (*^) have an even number of exprs) --MarkFan8901 (talk | contribs) 23:01, 15 October 2026 (UTC)

They used normal CC syntax, not The Church infix syntax to write that expression. --Blashyrkh (talk) 23:46, 15 October 2026 (UTC)

ah --MarkFan8901 (talk | contribs) 01:38, 16 October 2026 (UTC)

1

if this were right-associative then the EOF K 256 may be written (^**10)1414, but whatever... Cleverxia (talk) 12:16, 15 October 2026 (UTC)

Quine is almost ready, too late to change a thing. --Blashyrkh (talk) 12:46, 15 October 2026 (UTC)

syntax

the syntax section could probably be rewritten to be a few short sentences saying something like "Expressions are written in infix syntax. All operators are left-associative, and follow the precedence +*^0123456789. Brackets group expressions accordingly, and take precedence over all operators." --MarkFan8901 (talk | contribs) 23:06, 15 October 2026 (UTC)

You're welcome to improve the article! Since it's published at this wiki, anyone is free to edit it (as long as the information is factually correct and not off-topic). --Blashyrkh (talk) 23:51, 15 October 2026 (UTC)

oki, we were checking to make sure it was okay with you. probably should have said that upfront :P --MarkFan8901 (talk | contribs) 01:38, 16 October 2026 (UTC)

You've almost destroyed the original page. Not that it's something bad, it just means it wasn't good enough to be kept as is. I think I got your idea: do not describe things everyone knows; describe things nobody knows. Particularly, I'm going to add some clarifications on operators priority (because one corner case was covered just a little bit, and now it's not covered at all), and give a bracket abstraction algorithm for this weird basis. --Blashyrkh (talk) 13:05, 16 October 2026 (UTC)

Is that "Completeness of the basis" section correct?

The codeblock under the "Translation from SKI" subsection uses The Church's notation, while all the rest of the codeblocks use usual combinator notation. Though, I'm unsure which would be preferred here. (Mildly related, while the two expressions given for S are optimal in terms of combinator count, does that necessarily mean that the translation of them into The Church notation would be the shortest? I might try seeing if there's shorter.) –PkmnQ (talk) 13:52, 16 October 2026 (UTC)

I'll fix the page on weekend.

Regarding the lengths of expressions: when I said "shortest" I meant "shortest in terms of number of combinators", not "the shortest in The Church infix notation". The latter may be somewhat confusing: K combinator has length-5 The Church expression, but (Kx) would have length 6+len(x) because intermediate "1" appears. And vice versa - some (X) combinator's expression may have length 5 but this 5 includes intermediate "1", and Xx would be length 5 as well. --Blashyrkh (talk) 14:09, 16 October 2026 (UTC)

Since I'm going to write a description of my bracket abstraction algorithm (and it's better to do it in CC prefix syntax), I'm going to use both syntaxes on the page (no changes to the language specification, the page only). The Church syntax would use ()-parentheses, and CC syntax would use []-square brackets. At least, that's what I was doing when been writing the examples. --Blashyrkh (talk) 14:22, 16 October 2026 (UTC)

Hmm, now I'm wondering if including spaces for the CC syntax but excluding them for The Church syntax would work (i.e. * (+ ^) (* * (* ^)) and (+1^*(***1^)). Either way I think the bracket distinction would probably better, but it's an idea. –PkmnQ (talk) 15:06, 16 October 2026 (UTC)

In fact, I used both spaces and different style of brackets. ()-style with spaces is still valid The Church syntax, and I wanted to distinguish them more clearly. Presence of unhandled [] triggers interpreter's syntax error. --Blashyrkh (talk) 15:14, 16 October 2026 (UTC)

Alright, I've done enough checking for my standards to be confident enough that there's no shorter expression for S in The Church than what's already known. I mostly ignored digits greater than 2, though, so for all I know there might be some crazy expression that uses 9 or something (I think it's unlikely). –PkmnQ (talk) 15:33, 16 October 2026 (UTC)

For S I have only these:

• [+[*[+^]][^^]*]
• [++[+1**]^]
• [++[**[**]]^]
• [*[*[+^]*][*^]]
• [*[+^][**[*^]]]

But in general you'll be surprised:

• G: [+*[+1]*[*^]*]
• G: [+*[+3]*[*^]*]
• G: [+*[+5]*[*^]*]
• G: [+*[+7]*[*^]*]
• G: [+*[+9]*[*^]*]
• G: [+^+[**]^[*^]]
• B3: [+*[+3]^[**]]
• B3: [+2*[*^[**]]]
• B3: [+3^[*^[**]]]
• B3: [3[^[*^[**]]]2]
• B3: [4[^[*^[**]]]*]
• B3: [5[^[*^[**]]]^]
• B3: [5[^[*^[**]]]1]
• B3: [6[^[*^[**]]]0]
• R*: [4[^[**]]+[2^]]
• R*: [7[^[**]]3[2^]]

--Blashyrkh (talk) 15:50, 16 October 2026 (UTC)

Undefined operator precedence?

When evaluating: 1^2(expr)5

It seems like (expr) will end up with a precedence which could be higher or lower than ^, but it's not clear that it is necessarily well defined? Presumably it could evaluate to any combinator expression, not just one of the 13 defined operators?

I was trying to come up with a more direct translation to Lazy-k by using an x= (S(KK)(S(K(S(KK)))(S(K(S(SKK)))K))) prefix which handles the infix to prefix re-ordering of every triple. (λa.λb.λc.λd.λe.cae, which maps AxBxC -> BAC), but this won't handle operator precedence. It'd require correctly grouping by precedence in advance... but that seems quite hard to do correctly, and maybe undefined in some cases? Is this a gap in the spec? The interpreter must be doing something concrete.

To group the brackets correctly to perform a correct conversion to Lazy K for anything other than simple examples you'd need to actually evaluate the sub-expressions all the way, and that doesn't seem practical for TC sub-expressions. I don't think the Translation to Lazy K 1. works in practice. As currently written it ignores precedence, and the halting problem prevents determining precedence in all cases. There's something interesting going on here. I'm pretty sure the language is TC, but there seems to be some inconsistency between the specified and implemented precedence handling? Salpynx (talk) 08:05, 26 October 2026 (UTC)

When ()-expression is at operator position (not operand position), it has lowest priority: 1^2(expr)5 is (1^2)(expr)5. I can demonstrate how terms are grouped if you give your example. --Blashyrkh (talk) 08:14, 26 October 2026 (UTC)

Ok, that makes sense for parsing, and I see now that is stated on the page. I'm still overthinking it and worried that having S copying expressions around will make them evaluate differently, and things like 1+5(*)3 seem pathological for changing the precedence, but this unblocked me to get a translation working! I'm still wrapping my head around precedence and combinators. The rule of 3 grouping is quite important to get right when converting. Thanks for the clarification! Salpynx (talk) 09:51, 26 October 2026 (UTC)

And of course the language is TC because the basis is complete, which is demonstrated in the article. One can always use ()-subexpressions of length 3 only if not sure in operator precedence. --Blashyrkh (talk) 08:22, 26 October 2026 (UTC)

Alternative translation to Lazy-K

This is what I was working on, unfortunately it's not as exciting as I had hoped. The hardest part was correctly grouping the Hello World example to begin the translation, which is step 1. on the current page. This table lets you skip step 2...

This _requires_ operator triples to be correctly bracketed first. There's a prefix (S(KK)(S(K(S(KK)))(S(K(S(SKK)))K))) which handles the infix to prefix re-ordering of every triple. It's: λa.λb.λc.λd.λe.cae which maps AxBxC -> BAC. The first ( of each triple sub-group needs to be replaced too.

1. Group each sub-expression such that none have more than one operator, e.g.: (1+2+3*5) -> (1+2+(3*5)) -> ((1+2)+(3*5))
2. Replace each The Church combinator according to the following table:

The Church to Lazy K

Source	Replacement
(	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(
0	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(SK)
1	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))I
2	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(S(KS)K)I)
3	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(SS(SS(SK))(S(KS)K))
4	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(SII(S(S(KS)K)I))
5	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(SIS)I(S(S(KS)K))I)
6	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(SSI(SSS)(S(KS)K)I)
7	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(SI)S(SSK(S(S(KS)K)))I)
8	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(S(S(KS)K))I(S(S(KS)K)I))
9	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(SI)(SSKI)(S(S(KS)K)))
+	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(K(S(S(KS)(S(K(S(KS)K))))))K)
*	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(K(S(S(KS)K)))K)
^	(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K)))(S(K(SI))K)

I tested it on this re-grouping of the Hello World example (I did this by hand, it was painful working with non-operator looking operators, but seems correct in the lazy-k interpreter as a .holy and with the above substitutions to convert to .lazy):

((4*(3^3))(((4*(3^3))+3)((2^5)(((4*(3^3))+3)((4*(3^3))(((3^3)+6)(((**(*10))1(224))((^*(*1(((21^)*(*1(^**)))**)))(2*7)(**(*10)))(9+1))(4*(5^2)))((4*(3^3))+6))(((4^2)*7)+7))((6^2)+8))(4*(3^3)))((4*(5^2))+1))1(9*8)

Note: The outermost triple needs to remain un-bracketed. Salpynx (talk) 10:08, 26 October 2026 (UTC)

Few more steps (IO, proper handling of operator precedence), and you'd end up with The Church interpreter in Lazy K or The Church self-interpreter.

If you don't mind, I'll add a subsection to the article with your alternative translation (or you may do it yourself if you like).

And would you like to join the Golf Club (User:Blashyrkh/Golf, User:PkmnQ/Golf, User:Cleverxia/golfing results)?

--Blashyrkh (talk)

Why replacing ( with (T = (S(K(SI))K is not enough to swap first and second terms of each triplet? --Blashyrkh (talk) 13:37, 26 October 2026 (UTC)

It worked for me. I took my HW example, added parentheses to ensure there are only 3-term expressions (including the topmost one), then replaced all ( with (S(K(SI))K and all others according to my table. Got this one:

(S(K(SI))K(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K))))(S(K(SI))K(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K))))(S(K(S(S(KS)(S(K(S(KS)K))))))K)(SS(SS(SK))(S(KS)K)))(S(K(SI))K(S(K(SI))K(S(S(KS)K)I)(S(K(SI))K)(S(SIS)I(S(S(KS)K))I))(S(K(SI))K(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K))))(S(K(S(S(KS)(S(K(S(KS)K))))))K)(SS(SS(SK))(S(KS)K)))(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K))))(S(K(SI))K(S(K(SI))K(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K)))(S(K(S(S(KS)(S(K(S(KS)K))))))K)(SSI(SSS)(S(KS)K)I))(S(K(SI))K(S(K(SI))K(S(K(SI))K(S(K(S(S(KS)K)))K)(S(K(S(S(KS)K)))K)(S(K(SI))K(S(K(S(S(KS)K)))K)I(SK)))I(S(K(SI))K(S(S(KS)K)I)(S(S(KS)K)I)(SII(S(S(KS)K)I))))(S(K(SI))K(S(K(SI))K(S(K(SI))K)(S(K(S(S(KS)K)))K)(S(K(SI))K(S(K(S(S(KS)K)))K)I(S(K(SI))K(S(K(SI))K(S(K(SI))K(S(S(KS)K)I)I(S(K(SI))K))(S(K(S(S(KS)K)))K)(S(K(SI))K(S(K(S(S(KS)K)))K)I(S(K(SI))K(S(K(SI))K)(S(K(S(S(KS)K)))K)(S(K(S(S(KS)K)))K))))(S(K(S(S(KS)K)))K)(S(K(S(S(KS)K)))K))))(S(K(SI))K(S(S(KS)K)I)(S(K(S(S(KS)K)))K)(S(SI)S(SSK(S(S(KS)K)))I))(S(K(SI))K(S(K(S(S(KS)K)))K)(S(K(S(S(KS)K)))K)(S(K(SI))K(S(K(S(S(KS)K)))K)I(SK))))(S(K(SI))K(S(SI)(SSKI)(S(S(KS)K)))(S(K(S(S(KS)(S(K(S(KS)K))))))K)I))(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(S(SIS)I(S(S(KS)K))I)(S(K(SI))K)(S(S(KS)K)I))))(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K))))(S(K(S(S(KS)(S(K(S(KS)K))))))K)(SSI(SSS)(S(KS)K)I)))(S(K(SI))K(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(SI))K)(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(SI)S(SSK(S(S(KS)K)))I))(S(K(S(S(KS)(S(K(S(KS)K))))))K)(S(SI)S(SSK(S(S(KS)K)))I)))(S(K(SI))K(S(K(SI))K(SSI(SSS)(S(KS)K)I)(S(K(SI))K)(S(S(KS)K)I))(S(K(S(S(KS)(S(K(S(KS)K))))))K)(S(S(S(KS)K))I(S(S(KS)K)I))))(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(SS(SS(SK))(S(KS)K))(S(K(SI))K)(SS(SS(SK))(S(KS)K)))))(S(K(SI))K(S(K(SI))K(SII(S(S(KS)K)I))(S(K(S(S(KS)K)))K)(S(K(SI))K(S(SIS)I(S(S(KS)K))I)(S(K(SI))K)(S(S(KS)K)I)))(S(K(S(S(KS)(S(K(S(KS)K))))))K)I))I(S(K(SI))K(S(SI)(SSKI)(S(S(KS)K)))(S(K(S(S(KS)K)))K)(S(S(S(KS)K))I(S(S(KS)K)I))))

And it works as Lazy K HW. Your alternative translation is somewhat over-complicated. --Blashyrkh (talk) 20:10, 26 October 2026 (UTC)

Yeah, I haven't tested T yet, but what you say sounds correct if every triple is bracketed, which seems to be a requirement for all of the translations so far anyway. I started by trying to find a way to translate every symbol individually so that they would rearrange un-bracketed operand1 operator operand2 correctly when it was the first of a triple, and de-activate that code in operator operand2 leaving just the original functions. I only realised I had to add the same feature to sub-grouped ( at the last minute for it to work. As you noticed, if we can guarantee there's a ( before every operand1, the rearrangement code can go there, and it's much simpler. Use that as the step-2 skipping translation: ( -> (T. I took me working through the complex translation exercise to fully grasp implications of The Church's triple requirement. Your simplification is good. I went on a bit of a detour, but it was a fun exercise, and your lazy-k interpreter seems good and robust for testing these kinds of conversions :D Salpynx (talk) 21:25, 26 October 2026 (UTC)