1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
# Birb
Birb is an *advanced* programming language that only consists of bird
emojis π£. Each emoji gets substituted by a [*combinator
bird*](https://www.angelfire.com/tx4/cus/combinator/birds.html) of pure
lambda calculus.
## Birbs
Unfortunately, the Unicode standard does not yet have many
(single-character) birds. These are the ones currently mapped/supported:
| emoji | animal | combinator | term |
|:-----:|----------------|--------------|------------------------------------|
| π¦ | owl | owl | $\lambda ab.b(ab)$ |
| π¦
| eagle | eagle | $\lambda abcde.ab(cde)$ |
| πͺ½ | wing | phoenix | $\lambda abcd.a(bd)(cd)$ |
| ποΈ | dove | dove | $\lambda abcd.ab(cd)$ |
| π¦ | parrot | mockingbird | $\lambda a.aa$ |
| π¦ | duck | quacky | $\lambda abc.c(ba)$ |
| π€ | touring chick | turing | $\lambda ab.b(aab)$ |
| π₯ | kool chick | kestrel | $\lambda ab.a$ |
| π£ | hatching chick | quirky | $\lambda abc.c(ab)$ |
| π¦ | simple bird | identity | $\lambda a.a$ |
| π¦ | peacock | queer | $\lambda abc.b(ac)$ |
| 𦀠| dodo | sage | $\lambda ab.a(bb)\lambda ab.a(bb)$ |
| π§ | penguin | blackbird | $\lambda abc.a(bc)$ |
| π¦’ | swan | substitution | $\lambda abc.ac(bc)$ |
| 𦩠| flamingo | cardinal | $\lambda abc.acb$ |
Lonely/unmatched birbs: ππ¦ππͺΏ
# Syntax
- `[birb]+`: Birb
- everything else: Comment
Syntax errors are impossible as long as you use at least one birb.
# Semantics
Birbs stagger as they walk: they are reduced in alternating associative
order, starting with left associativity at birb index
$\lfloor\frac{\texttt{len}}{2}\rfloor$:
π¦π¦ -> (π¦π¦)
π¦π¦π¦ -> ((π¦π¦)π¦)
π¦π¦π¦π¦ -> (π¦((π¦π¦)π¦))
π¦π¦π¦π¦π¦ -> ((π¦((π¦π¦)π¦))π¦)
π¦π¦π¦π¦π¦π¦ -> (π¦((π¦((π¦π¦)π¦))π¦))
π¦π¦π¦π¦π¦π¦π¦ -> ((π¦((π¦((π¦π¦)π¦))π¦))π¦)
...
# Examples
You can find more examples (with comments) in the `samples/` directory.
## Relationships
- πͺ½π¦ $\rightsquigarrow$ π¦’
- π¦’π¦ $\rightsquigarrow$ π¦
- π¦π¦ $\rightsquigarrow$ π¦
- ποΈπ¦ $\rightsquigarrow$ π§
- π§π§ $\rightsquigarrow$ ποΈ
- π¦©π§ $\rightsquigarrow$ π¦
- π¦©π¦ $\rightsquigarrow$ π§
- π¦©π¦ $\rightsquigarrow$ π£
One can only imagine what happens if two parrots talk to each other:
π¦π¦ $\rightsquigarrow$ π₯. The same happens with π€π€; they just canβt
stop waddling!
## Arithmetic
For this example I use the Church numerals. Zero would then be encoded
as π₯π¦. The successor function can be written as π¦’π§:
- π¦π§π¦π¦’π§π₯π¦ $\rightsquigarrow\lambda\lambda(10)$ β (Church numeral
1)
- π¦π§π¦π§ποΈπ¦’π§π¦’π§π₯π¦ $\rightsquigarrow\lambda\lambda(1(10))$ β
(Church numeral 2)
Similarly, one can very obviously translate the Church addition function
to πͺ½π§. Now, to calculate $1+2$ based on their increments from zero:
- π¦π¦ποΈπ§ποΈπ§π¦π§ποΈπ§ποΈπͺ½π§π¦’π§π¦’π§π₯π¦π¦’π§π₯π¦
$\rightsquigarrow\lambda\lambda(1(1(10)))$ β (Church numeral 3)
Also: π§ is $a\cdot b$, π¦ is $n^n$ and π¦π¦ $a^b$.
Note that there exist many alternative ways to do arithmetic. Try
writing the functions above with other birbs!
## Containers
You can create a pair $\langle X,Y\rangle$ using `π¦©π¦©π¦©YX`.
Typically, one would now construct a list using repeated application of
pairs (Boehm-Berarducci/Church encoding). However, due to the reversed
application and alternating associativity, the Mogensen-Scott encoding
is more suitable:
List $\langle X_1,X_2,\dots,X_n\rangle$: `[π¦©]βΏπ¦©X2X1...XN`.
## Boolean logic
See this excellent [codegolf
stackexchange](https://codegolf.stackexchange.com/a/266078/119961)
answer.
## Busy ~~beavers~~ birbs
Contestants:
- *The touring eagle*: `[π¦]βΏ[π¦
π€]βΏ` ($n=3$: 9 birbs, ~20M BLC bits)
- better? PR!
# Transpiler
I created a lambda calculus to Birb transpiler. It works by converting
binary lambda calculus to SKI combinators, which then get converted to
Jot and back to SKI combinators. The resulting SKI combinators then get
converted to Birbs.
The reason I convert to Jot first is that Birbs semantics donβt allow
trivial transpilation from arbitrary SKI expressions. With Jot however,
applications with non-associative expressions like `((s k) (k s))` are
impossible, as only a single non-associative application exists (the
innermost/deepest expression).
With all these conversions, the resulting transpiled Birb code is big,
ugly and slow. There should be a way to optimize the transpilation
process, but itβs probably a bit more complicated.
# Usage
Install [Haskellβs
stack](https://docs.haskellstack.org/en/stable/install_and_upgrade/).
Then,
- `stack run -- reduce file.birb` or `stack run -- reduce <(echo π§π§)`
- `stack run -- transpile <(echo 01000110100000011100111001110011100111010)`
to generate a birb program that calculates $5^5$
- `stack install` so you can enjoy `birb` from anywhere
If the output cannot be translated to birbs, the raw lambda calculus
term (with De Bruijn indices) is printed. For the examples above I
sometimes manually converted the term back to birbs.
# Turing-completeness
Birb is Turing complete, since one can construct any term of the
[Jot](https://esolangs.org/wiki/Jot) variant of Iota. A Jot term
`((X s) k)` is equivalent to `π¦π¦Xπ¦’π₯`. Similarly, `(s (k X))` is
equivalent to `π¦π¦Xπ₯π¦’`.
------------------------------------------------------------------------
The idea of the language was originally proposed in 2021 by @SCKelement
on [Esolang](https://esolangs.org/wiki/Birb).
|
