blob: c64fd84ea2b65dc824d0e8e2946a22837ce07f23 (
plain) (
blame)
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
|
# 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 | bruijn | term |
|:-----:|----------------|--------------|---------------------|------------------------------------|
| ๐ฆ | owl | owl | `[[0(10)]]` | $\lambda ab.b(ab)$ |
| ๐ฆ
| eagle | eagle | `[[[[[43(210)]]]]]` | $\lambda abcde.ab(cde)$ |
| ๐ชฝ | wing | phoenix | `[[[[3(20)(10)]]]]` | $\lambda abcd.a(bd)(cd)$ |
| ๐๏ธ | dove | dove | `[[[[32(10)]]]]` | $\lambda abcd.ab(cd)$ |
| ๐ฆ | parrot | mockingbird | `[00]` | $\lambda a.aa$ |
| ๐ฆ | duck | quacky | `[[[0(12)]]]` | $\lambda abc.c(ba)$ |
| ๐ค | touring chick | turing | `[[0(110)]]` | $\lambda ab.b(aab)$ |
| ๐ฅ | kool chick | kestrel | `[[1]]` | $\lambda ab.a$ |
| ๐ฃ | hatching chick | quirky | `[[[0(21)]]]` | $\lambda abc.c(ab)$ |
| ๐ฆ | simple bird | identity | `[0]` | $\lambda a.a$ |
| ๐ฆ | peacock | queer | `[[[1(20)]]]` | $\lambda abc.b(ac)$ |
| ๐ฆค | dodo | sage | `[[0(11)][0(11)]]` | $\lambda ab.b(aa)\lambda ab.b(aa)$ |
| ๐ง | penguin | blackbird | `[[[2(10)]]]` | $\lambda abc.a(bc)$ |
| ๐ฆข | swan | substitution | `[[[20(10)]]]` | $\lambda abc.ac(bc)$ |
| ๐ฆฉ | flamingo | cardinal | `[[[201]]]` | $\lambda abc.acb$ |
Lonely/unmatched birbs: ๐๐ฆ๐
# Syntax
- `[birb]+`: Birb
- everything else: Comment
# Semantics
Birbs stagger as they walk: they are reduced in alternating associative
order, starting with birb index $\lfloor\frac{\texttt{len}}{2}\rfloor$:
๐ฆ๐ฆ -> (๐ฆ๐ฆ)
๐ฆ๐ฆ๐ฆ -> ((๐ฆ๐ฆ)๐ฆ)
๐ฆ๐ฆ๐ฆ๐ฆ -> (๐ฆ((๐ฆ๐ฆ)๐ฆ))
๐ฆ๐ฆ๐ฆ๐ฆ๐ฆ -> ((๐ฆ((๐ฆ๐ฆ)๐ฆ))๐ฆ)
๐ฆ๐ฆ๐ฆ๐ฆ๐ฆ๐ฆ -> (๐ฆ((๐ฆ((๐ฆ๐ฆ)๐ฆ))๐ฆ))
๐ฆ๐ฆ๐ฆ๐ฆ๐ฆ๐ฆ๐ฆ -> ((๐ฆ((๐ฆ((๐ฆ๐ฆ)๐ฆ))๐ฆ))๐ฆ)
# Examples
You can find more examples in the `samples/` directory.
## Relationships
- ๐ฆ๐ฆ $\rightsquigarrow$ ๐ฆ
- ๐ฆข๐ฆ $\rightsquigarrow$ ๐ฆ
- ๐ง๐ง $\rightsquigarrow$ ๐๏ธ
- ๐ฆฉ๐ง $\rightsquigarrow$ ๐ฆ
- ๐ฆฉ๐ฆ $\rightsquigarrow$ ๐ง
One can only imagine what happens if two parrots repeat each other: ๐ฆ๐ฆ
$\rightsquigarrow$ ๐ฅ
## Arithmetic
For this example I use the Church numerals. Zero would then be encoded
as ๐ฅ๐ฆ. The successor function can be written as ๐ฆข๐ง:
- ๐ฆ๐ง๐ฆ๐ฆข๐ง๐ฅ๐ฆ $\rightsquigarrow$ ฮปฮป(10) โ (Church numeral 1)
- ๐ฆ๐ง๐ฆ๐ง๐๏ธ๐ฆข๐ง๐ฆข๐ง๐ฅ๐ฆ $\rightsquigarrow$ ฮปฮป(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:
- ๐ฆข๐ง๐ฆข๐ง๐ฅ๐ฆ
Also: ๐ง is $a\cdot b$, ๐ฆ is $n^n$ and ๐ฆ๐ฆ $a^b$.
Note that there are many alternative ways to do arithmetic. Try writing
the functions above with other birbs!
## Busy ~~beavers~~ birbs
- The touring eagle: ๐ฆ๐ฆ๐ฆ๐ฆ
๐ค๐ฆ
๐ค๐ฆ
๐ค (~20M BLC bits)
- more? PR!
# Usage
Install [Haskellโs
stack](https://docs.haskellstack.org/en/stable/install_and_upgrade/).
Then,
- `stack run -- file.birb` or `stack run <(echo ๐ง๐ง)`
- `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
The language is probably Turing complete. If the language supported
left- *and* right-associativity, ๐ง would be enough to prove its
completeness.
------------------------------------------------------------------------
The idea of the language was originally proposed in 2021 by an
unknown(?) author on [Esolang](https://esolangs.org/wiki/Birb).
|
