# Birb

Paradigm(s) | functional |
---|---|

Designed by | User:Melvin, User:SCKelemen |

Appeared in | 2021 |

Type system | untyped |

Memory system | stack-based |

Computational class | Turing complete |

Reference implementation | [1] |

Influenced by | Combinatory Logic, Lambda Calculus, Gabriel Lebec, Samuel Kelemen |

File extension(s) | `.birb` , `.bird` , |

**Birb** is an untyped, purely functional language based on Lambda Calculus and Combinatory Logic.

## Language overview

The birb language is entirely comprised of bird emojis.

## Symbols

Symbol | Name | Lambda Calculus | Combinator |
---|---|---|---|

π¦ | owl | \ab.b(ab) | owl |

π¦ | eagle | \abcde.ab(cde) | eagle |

πͺ½ | wing | \abcd.a(bd)(cd) | phoenix |

ποΈ | dove | \abcd.ab(cd) | dove |

π¦ | parrot | \a.aa | mockingbird |

π¦ | duck | \abc.c(ba) | quacky |

π€ | touring chick | \ab.b(aab) | turing |

π₯ | kool chick | \ab.a | kestrel |

π£ | hatching chick | \abc.c(ab) | quirky |

π¦ | simple bird | \a.a | identity |

π¦ | peacock | \abc.b(ac) | queer |

π¦€ | dodo | \ab.a(bb)\ab.a(bb) | sage |

π§ | penguin | \abc.a(bc) | blackbird |

π¦’ | swan | \abc.ac(bc) | substitution |

π¦© | flamingo | \abc.acb | cardinal |

## 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 βlen/2β:

π¦π¦ -> (π¦π¦) π¦π¦π¦ -> ((π¦π¦)π¦) π¦π¦π¦π¦ -> (π¦((π¦π¦)π¦)) π¦π¦π¦π¦π¦ -> ((π¦((π¦π¦)π¦))π¦) π¦π¦π¦π¦π¦π¦ -> (π¦((π¦((π¦π¦)π¦))π¦)) π¦π¦π¦π¦π¦π¦π¦ -> ((π¦((π¦((π¦π¦)π¦))π¦))π¦) ...

## Examples

You can find more examples (with comments) in the `samples/`

directory.

### Relationships

- πͺ½π¦ -> π¦’
- π¦’π¦ -> π¦
- π¦π¦ -> π¦
- ποΈπ¦ -> π§
- π§π§ -> ποΈ
- π¦©π§ -> π¦
- π¦©π¦ -> π§
- π¦©π¦ -> π£

One can only imagine what happens if two parrots talk to each other: π¦π¦ -> π₯. 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 π¦’π§:

- π¦π§π¦π¦’π§π₯π¦ ->
`\\(10)`

(Church numeral 1) - π¦π§π¦π§ποΈπ¦’π§π¦’π§π₯π¦ ->
`\\(1(10))`

(Church numeral 2)

Similarly, one can translate the Church addition function to πͺ½π§. Now, to calculate `1+2`

based on their increments from zero:

- π¦π¦ποΈπ§ποΈπ§π¦π§ποΈπ§ποΈπͺ½π§π¦’π§π¦’π§π₯π¦π¦’π§π₯π¦ ->
`\\(1(1(10)))`

(Church numeral 3)

Also: π§ is `a*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 `[X,Y]`

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 `[X_1,X_2,...,X_n]`

: `[π¦©]βΏπ¦©X2X1...XN`

.

## Turing-completeness

Birb is Turing complete, since one can construct any term of the Jot variant of Iota. A Jot term `((X s) k)`

is equivalent to `π¦π¦Xπ¦’π₯`

. Similarly, `(s (k X))`

is equivalent to `π¦π¦Xπ₯π¦’`

.

## Implementations

As of right now there is one interpreter, written by User:melvin in Haskell: [2]. It also features a BLC to birb transpiler.