aboutsummaryrefslogtreecommitdiffhomepage
path: root/readme.md
blob: 9023b61275db86bb95002929e6e78791ae7cfd61 (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
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
# 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(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(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`.

## Busy ~~beavers~~ birbs

Contestants:

- *The touring eagle*: `[🐦]ⁿ[πŸ¦…πŸ€]ⁿ` ($n=3$: 9 birbs, ~20M BLC bits)
- better? 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

Birb is Turing complete.

It turns out that even its sub-language $\Sigma=\{🦒πŸ₯\}$ (SK) is Turing
complete, since the semantics allow an initial construction of 🐦 using
`((🦒 πŸ₯) πŸ₯)`. By doing that, birb is equivalent to the
[Jot](https://esolangs.org/wiki/Jot) variant of Iota calculus.

------------------------------------------------------------------------

The idea of the language was originally proposed in 2021 by an
unknown(?) author on [Esolang](https://esolangs.org/wiki/Birb).