Detrovert

Detrovert is a graph-rewriting and object-oriented esoteric programming language.
== Overview ==
=== Classes and objects ===
In this language everything is an object. There is a constant number of classes that are defined at the beginning of the program and each object that is created is an instance of a class. Objects can be constructed explicitly, but they can be destructed only implicitly by a garbage collector.
Each class is either abstract or concrete. Abstract classes can be extended, but cannot instantiated, while concrete classes can be instantiated, but cannot be extended. A class (both abstract and concrete) may have any number of attributes. All attributes are public. Classes do not contain methods. Two attributes with the same name cannot appear in the same class, nor in any class that is in the prototype chain. Each attribute has a type, which is a class.
There is an object called nil. It is a unique object and it can be assigned to any attribute of any class. Also, nil is the default value for any attribute that has no explicitly specified value. nil does not have any attributes. All nil values are equal.
=== Control flow ===
Reading attributes from an object is performed by destructuring and pattern-matching. This also implies that nil cannot be destructured in any way, because it has no attributes. Comparing two objects is also achievable by pattern matching and naming objects with the same identifier in the pattern. Non-extensional equivalence is used in comparing objects.
Source code consists of class definitions and patterns. Each pattern consists of what objects to find and how to transform the found objects.
=== Execution step ===
Execution is performed by a collection of threads. Initially, there is only one thread. A thread can spawn any number of other threads at any execution step. Also, each thread must re-spawn itself if it wants to continue, otherwise, it will be implicitly terminated. Each thread is bound to a single object. A thread itself is not an object.
There is a queue of threads. When the queue becomes empty, the program halts. Otherwise, pop the first (least recently added) thread from the queue. Find the last pattern from the source code that applies to the object to which the thread is bound. If there is no such object, skip this execution step. Otherwise, apply the transformations from the pattern. Transformations may contain information about what new threads need to be spawned. The thread that we popped from the queue is terminated in any case. So, each thread can perform just a single execution step if it does not re-spawn itself (and by re-spawning we mean to spawn another thread that is bound to the same object).
== Native classes ==
There are several native classes. They exist in every program. User classes cannot be extended from native classes, except implicitly from the base class.
Names of native classes start with dot character. Native classes are:
* .Base - The base class. All classes are extended from it. It is not extended from anything. It has no attributes.
* .String - Represents a binary string. Contains attribute bit of type .Bit.
* .Bit - Abstract class representing a bit. It has attribute next of type .Bit which point to the next bit, or nil.
* .Bit0 - Extends .Bit and represents bit 0.
* .Bit1 - Extends .Bit and represents bit 1.
== I/O format ==
Input and output are strings of bits. When program starts, the input string is represented as a linked list using native classes and a single thread is bound to the string object. When program halts, the output is parsed from the main string object (interpreter keeps an extra reference to the main string to prevent it from being garbage-collected).
== Syntax ==
Source code consists of two parts: class definitions and patterns.
Class definitions appear at the beginning of the source code in a pair of parentheses. Inside, all user-defined classes are specified. Extended class is represented by ~. It should be clear from this example:
 (
 MyClass(
 myAttribute TypeOfTheAttribute
 someOtherAttribute SomeOtherType
 )
 
 TypeOfTheAttribute ~ MyClass(
 recursiveAttribute MyClass
 myString .String
 )
 
 SomeOtherType ~ MyClass(
 // No attributes
 )
 )
After we define classes, we specify all patterns. Each pattern contains two parts: 1) what to find and 2) how to transform it. These two parts are separated by -> arrow. Example:
 (
 MyClass x(
 myAttribute y
 )
 ->
 x(
 myAttribute nil
 )
 )
This means: if the current thread is bound to an object of type MyClass (we name it x) and the object x contains attribute myAttribute that is some y, then set myAttribute of x to nil.
To spawn a new thread, put * symbol before identifier name in the second part of the pattern.
Syntax allows a lot of possibilities, which would take a lot of time to explain. See the implementation for more details.
== Examples ==
=== Cat program ===
 ()
=== Invert bits ===
 ()
 
 (
 .String a(bit b)
 .Bit0 b(next c)
 ->
 a(bit d)
 .Bit1 *d(next c)
 )
 
 (
 .String a(bit b)
 .Bit1 b(next c)
 ->
 a(bit d)
 .Bit0 *d(next c)
 )
 
 (
 .Bit a(next b)
 .Bit0 b(next c)
 ->
 a(next d)
 .Bit1 *d(next c)
 )
 
 (
 .Bit a(next b)
 .Bit1 b(next c)
 ->
 a(next d)
 .Bit0 *d(next c)
 )
=== Reverse string ===
 (
 Reverse(
 str .String
 in .Bit
 out .Bit
 )
 )
 
 (
 .String a(bit b)
 ->
 Reverse *c(
 str a
 in b
 out nil
 )
 )
 
 (
 Reverse a(
 in b
 out c
 )
 .Bit0 b(next d)
 ->
 *a(
 in d
 out e
 )
 .Bit0 e(next c)
 )
 
 (
 Reverse a(
 in b
 out c
 )
 .Bit1 b(next d)
 ->
 *a(
 in d
 out e
 )
 .Bit1 e(next c)
 )
 
 (
 Reverse a(
 str b
 in nil
 out c
 )
 .String b()
 ->
 b(bit c)
 )
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020