Detrovert

Detrovert

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

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