Exotic

Exotic

Paradigm(s)	Tree-rewriting
Designed by	User:Hakerh400
Appeared in	2020
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.txt

Exotic is an esolang invented by User:Hakerh400 in November 2020.

Overview

Exotic is a tree-rewriting language. It starts with a finite binary tree and modifies it according to some rules.

An expression can be one of the following:

• Term - Represented by .. It is a unique value and contains no other expressions. It represents a leaf in the binary tree.
• Pair - Represented by (left right) where left and right are some other expressions. It represents a node in the binary tree.
• Identifier - Represented by an alphanumeric string. It represents formal variable that can be any expression.
• Call - Represented by *target where target is some other expression. It represents a rule application.

A rule consists of two expressions. The first expression represents the pattern and the second expression represents the replacement for that pattern. For example, the following rule

(. (a .)) (. a)

will replace anything of the form (. (a .)), where a can be any expression, with (. a). The replacement happens only when the expression appears inside a call (prefixed by *).

We do not explain too much details here. For more information, see the implementation of the interpreter.

I/O format

Input and output are binary strings. There is a bijection between binary strings and binary trees, but the mapping is a bit complicated, so we do not explain here in details how it works (see the implementation). Basically, given the input as a binary string (call it input), the initial expression to start with will be

*(. inputTree)

where inputTree is obtained by converting input into a binary tree. This is the main expression and the interpreter searches for *expr patterns and matches them against rules (applies the most specific rule if multiple rules can be applied) until there are no more calls in the main expression. The result is the output of the program. Then we convert it back into a binary string and output it.

Examples

Cat program

(. a) a
a .

Truth machine

(. (. .)) (. .)
(. ((. .) .)) *(. ((. .) .))
a .

Replace leading 1 with two 0s

If the input consists of a single 1 followed by zero or more 0s, then replace 1 with two 0s.

a .
(. .) .
(. (a b)) (. *(. a))

Interpreters

Interpreter