Birb

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.