# Birb

Paradigm(s) functional User:Melvin, User:SCKelemen 2021 untyped stack-based Turing complete [1] Combinatory Logic, Lambda Calculus, Gabriel Lebec, Samuel Kelemen `.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

## 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.