diff options
Diffstat (limited to 'readme.md')
| -rw-r--r-- | readme.md | 95 |
1 files changed, 60 insertions, 35 deletions
@@ -10,23 +10,23 @@ lambda calculus. 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$ | +| 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: ππ¦π @@ -35,10 +35,13 @@ Lonely/unmatched birbs: ππ¦π - `[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 birb index $\lfloor\frac{\texttt{len}}{2}\rfloor$: +order, starting with left associativity at birb index +$\lfloor\frac{\texttt{len}}{2}\rfloor$: π¦π¦ -> (π¦π¦) π¦π¦π¦ -> ((π¦π¦)π¦) @@ -46,46 +49,65 @@ order, starting with birb index $\lfloor\frac{\texttt{len}}{2}\rfloor$: π¦π¦π¦π¦π¦ -> ((π¦((π¦π¦)π¦))π¦) π¦π¦π¦π¦π¦π¦ -> (π¦((π¦((π¦π¦)π¦))π¦)) π¦π¦π¦π¦π¦π¦π¦ -> ((π¦((π¦((π¦π¦)π¦))π¦))π¦) + ... # Examples -You can find more examples in the `samples/` directory. +You can find more examples (with comments) in the `samples/` directory. ## Relationships -- π¦π¦ $\rightsquigarrow$ π¦ +- πͺ½π¦ $\rightsquigarrow$ π¦’ - π¦’π¦ $\rightsquigarrow$ π¦ +- π¦π¦ $\rightsquigarrow$ π¦ +- ποΈπ¦ $\rightsquigarrow$ π§ - π§π§ $\rightsquigarrow$ ποΈ - π¦©π§ $\rightsquigarrow$ π¦ - π¦©π¦ $\rightsquigarrow$ π§ +- π¦©π¦ $\rightsquigarrow$ π£ -One can only imagine what happens if two parrots repeat each other: π¦π¦ -$\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$ λλ(10) β (Church numeral 1) -- π¦π§π¦π§ποΈπ¦’π§π¦’π§π₯π¦ $\rightsquigarrow$ λλ(1(10)) β (Church numeral - 2) +- π¦π§π¦π¦’π§π₯π¦ $\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: +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 are many alternative ways to do arithmetic. Try writing -the functions above with other birbs! +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 -- The touring eagle: π¦π¦π¦π¦
π€π¦
π€π¦
π€ (~20M BLC bits) -- more? PR! +Contestants: + +- *The touring eagle*: `[π¦]βΏ[π¦
π€]βΏ` ($n=3$: 9 birbs, ~20M BLC bits) +- better? PR! # Usage @@ -102,9 +124,12 @@ 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. +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. ------------------------------------------------------------------------ |