<p>Yes, there exists a version of BLC working similarly to Zot.</p>
<p>Consider the zot implementation at [1], which mimics the original definition at [2].
It defines 3 lambda expressions:</p>
<p>zot = \c.c I</p>
<p>0 = \c.c(\f.f S K)</p>
<p>1 = \c\L.L(\l\R.R(\r.c(l r)))</p>
<p>such that applying zot to a sequence of 0s and 1s produces any desired lambda term. For instance, I = \x.x = zot 1 0 0.</p>
<p>But while it's true that the concatenation of 2 bit sequences A and B is another bit sequence C, the resulting program has little to do with the program for B, since B no longer follows the initial zot term.</p>
<p>The lambda terms for 0 and 1 in zot are very much unlike plain bits.</p>
<p>Is there any way we can use the plain bits 0 = \x\y.x and 1 = \x\y.y instead? It turns out that we can!
At the cost of moving all complexity into the initial term. This is what I did in the implementation at [3].
The 195 bit term blc serves the same role as zot above.
But by applying it to the sequence of (actual plain) bits that are the BLC code of a lambda term T, we obtain that very term T.
For instance, I = \x.x = blc 0 0 1 0</p>
<p>blc is in fact a binary tree containing all closed lambda terms at its leaves, and applying 0/1 is taking the left/right subtree.</p>
<p>It's also possible to reduce the 195 bits to a much smaller 100 bits by
using the single point combinator basis A = \x\y\z.x z(y(_.z)) [4].</p>
<p>[1] <a href="https://github.com/tromp/AIT/blob/master/ait/zot.lam" rel="nofollow noreferrer">https://github.com/tromp/AIT/blob/master/ait/zot.lam</a></p>
<p>[2] <a href="https://web.archive.org/web/20160312050150/http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html" rel="nofollow noreferrer">https://web.archive.org/web/20160312050150/http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html</a></p>
<p>[3] <a href="https://github.com/tromp/AIT/blob/master/ait/blc.lam" rel="nofollow noreferrer">https://github.com/tromp/AIT/blob/master/ait/blc.lam</a></p>
<p>[4] <a href="https://github.com/tromp/AIT/blob/master/ait/allA.lam" rel="nofollow noreferrer">https://github.com/tromp/AIT/blob/master/ait/allA.lam</a></p>

CC BY-SA 4.0
2023-12-22T22:51:26.613Z
2024-01-08T13:28:41.357Z
2024-01-08T13:28:41.357Z
John Tromp
<p>As per @cody's comment above, if we require only that "the concatenation of any two programs is a valid program" then I believe that Iota, Jot and Zot (semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html) are examples of a).</p>

<p>However, IMO the more interesting question part of the question is b)...</p>

CC BY-SA 3.0
2015-08-18T14:42:38.553Z
2015-08-18T14:42:38.553Z
NietzscheanAI
<p>John Tromp defines a version of the lambda calculus that is encoded in binary:
<a href="https://tromp.github.io/cl/cl.html" rel="nofollow noreferrer">https://tromp.github.io/cl/cl.html</a></p>

<p>a) Does there exist a concatenative version of this language (or its combinatory equivalent)?</p>

<p>b) Does there exist a concatenative version restricted to the primitive recursive functions (e.g. as per <a href="https://cstheory.stackexchange.com/questions/15038/combinators-for-the-primitive-recursive-functions">Combinators for the Primitive Recursive Functions</a>)?</p>

CC BY-SA 3.0
2015-08-18T14:32:31.687Z
I'm not sure what you mean by concatenative. Do you mean something like here: https://en.wikipedia.org/wiki/Concatenative_programming_language or a language in which the concatenation of any two programs is a valid program?
cody
CC BY-SA 3.0
2015-08-18T14:37:05.357Z
@cody - Actually, it looks like just the condition that the concatenation of any two programs is a valid program suffices. If anyone can say what languages with this weaker condition are called, I'll edit the question/title accordingly.
NietzscheanAI
CC BY-SA 3.0
2015-08-18T14:38:43.483Z
With this weaker condition, I believe that Iota, Jot and Zot are examples of a):
http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html
NietzscheanAI
CC BY-SA 3.0
2015-08-18T14:40:22.167Z
You should turn your comment into an answer.
cody
CC BY-SA 3.0
2015-08-19T00:11:29.387Z
This is a related post. http://cstheory.stackexchange.com/questions/31883/smallest-possible-universal-combinator/31910#31910
Joshua Herman
<lo.logic><combinatory-logic>
Concatenative binary lambda calculus/combinatory logic
NietzscheanAI
# Concatenative binary lambda calculus/combinatory logic

(Asked by: username_0 on 2015-08-17)

username_3 defines a version of the lambda calculus that is encoded in binary:
<https://tromp.github.io/cl/cl.html>

a) Does there exist a concatenative version of this language (or its combinatory equivalent)?

b) Does there exist a concatenative version restricted to the primitive recursive functions (e.g. as per [Combinators for the Primitive Recursive Functions](https://cstheory.stackexchange.com/questions/15038/combinators-for-the-primitive-recursive-functions))?

**Tags:** lo.logic, combinatory-logic

> **Comments:**
> **username_1**: I'm not sure what you mean by concatenative. Do you mean something like here: https://en.wikipedia.org/wiki/Concatenative_programming_language or a language in which the concatenation of any two programs is a valid program?  
> **username_0**: @username_1 - Actually, it looks like just the condition that the concatenation of any two programs is a valid program suffices. If anyone can say what languages with this weaker condition are called, I'll edit the question/title accordingly.  
> **username_0**: With this weaker condition, I believe that Iota, Jot and Zot are examples of a): http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html  
> **username_1**: You should turn your comment into an answer.  
> **username_2**: This is a related post. http://cstheory.stackexchange.com/questions/31883/smallest-possible-universal-combinator/31910#31910  

---

## 2 answers

### Answer by username_3 on 2023-12-22. Score: 1 | Accepted answer

Yes, there exists a version of BLC working similarly to Zot.

Consider the zot implementation at [1], which mimics the original definition at [2].
It defines 3 lambda expressions:

zot = \c.c I

0 = \c.c(\f.f S K)

1 = \c\L.L(\l\R.R(\r.c(l r)))

such that applying zot to a sequence of 0s and 1s produces any desired lambda term. For instance, I = \x.x = zot 1 0 0.

But while it's true that the concatenation of 2 bit sequences A and B is another bit sequence C, the resulting program has little to do with the program for B, since B no longer follows the initial zot term.

The lambda terms for 0 and 1 in zot are very much unlike plain bits.

Is there any way we can use the plain bits 0 = \x\y.x and 1 = \x\y.y instead? It turns out that we can!
At the cost of moving all complexity into the initial term. This is what I did in the implementation at [3].
The 195 bit term blc serves the same role as zot above.
But by applying it to the sequence of (actual plain) bits that are the BLC code of a lambda term T, we obtain that very term T.
For instance, I = \x.x = blc 0 0 1 0

blc is in fact a binary tree containing all closed lambda terms at its leaves, and applying 0/1 is taking the left/right subtree.

It's also possible to reduce the 195 bits to a much smaller 100 bits by
using the single point combinator basis A = \x\y\z.x z(y(\_.z)) [4].

[1] <https://github.com/tromp/AIT/blob/master/ait/zot.lam>

[2] <https://web.archive.org/web/20160312050150/http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html>

[3] <https://github.com/tromp/AIT/blob/master/ait/blc.lam>

[4] <https://github.com/tromp/AIT/blob/master/ait/allA.lam>


---

### Answer by username_0 on 2015-08-18. Score: 0

As per @username_1's comment above, if we require only that "the concatenation of any two programs is a valid program" then I believe that Iota, Jot and Zot (semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html) are examples of a).

However, IMO the more interesting question part of the question is b)...


---

