Transortogonal Polymorphism

Transortogonal Polymorphism

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

Transortogonal Polymorphism is an esoteric programming language invented by User:Hakerh400 in 2020.

Overview

Object

There is an object called root and denoted by R. The root object can also be replaced with another object. Each object contains infinitely many keys and all of them are initially unique objects. Keys are also objects. We denote accessing key key from object obj by obj[key]. Note that key[obj] is also valid because keys are objects.

Address

A pair of parentheses is called a list. An address is represented by sequence of keys. The root object is represented by empty list (). Accessing root key of root (which is denoted in this article by R[R]) is represented as (()). Basically, list represent a sequence of reading keys from objects. For example, (A B C) means R[A][B][C]. We can also nest lists: (()(())) means R[R][R[R]].

Instructions

There are only four instructions:

1. Assign x y - Assign the object from the address y to the address x
2. Input x y - If the next input bit is 1 then assign the object from the address y to the address x
3. Output x y - If the object at address x is equal to the object at address y, then output bit 1, otherwise 0
4. Loop x y z - Perform the sequence of instructions z while the object at the address x is equal to the object at the address y

Syntax

Instructions

Instructions are represented in the following way:

• Assign x y - represented as () x y
• Input x y - represented as (()) x y
• Output x y - represented as ((())) x y
• Loop x y z - represented as (()()) x y (z)

Identifiers

Note that the entire source code contains only parentheses. However, we can define some constants and assign them to the identifiers (they are just syntactic sugar). Defining a constant is represented by an identifier followed by either another identifier, or a list. For example, the source code

a()(a)

is converted to ()(()) before program starts (note that identifier definition also includes its value at that location). Multicharacter identifiers can be created by prepending a backslash before the identifier name:

\myIdent (())
((\myIdent)\myIdent)

The above code is equivalent to (())(((()))(())) (note that whitespace has no meaning). The backslash is a part of the identifier name (so x is not equivalent to \x). Identifiers can contain any character except parentheses and whitespace.

Parsing instructions

Instructions are parsed sequentially. We read the first list and check whether it is (), (()), ((())), or (()()). If it is some of them, execute the corresponding instruction (and if there are not enough arguments to the end, assume they are empty lists). If the parsed list is none of these, then replace it with its content repeated two times and continue parsing from the first new element among them that we added. For example, the following code:

(() (())) (() () ())

cannot be parsed as any instruction, because (() (())) does not correspond to any of the four instructions. So, we replace (() (())) with () (()) () (()) (its content repeated two times), so we obtain:

() (()) () (()) (() () ())

The first three lists represent an assignment, because the first list is (), which corresponds to the assignment instruction. In this article we denote assignment by = sign:

R[R] = R        // Parsed
(()) (() () ()) // Not parsed yet

Then we continue parsing. The next list is (()), which means input. We are missing the second parameter, so it is assumed to be an empty list:

R[R] = R
if input
  R[R][R][R] = R

If there is a loop, we also parse the loop body (the third parameter of the loop instruction) in the same way.

I/O format

Both input and output are sequences of bits. Before program starts, each bit from the input stream is prepended with an extra bit 1. Reading after EOF gives 0.

Examples

Cat program

()(((()))(()))((())(()))(())(((()))(()))((())((())))(()())(((()))(()))((())((())))(()(((()))(()))(((
))(()))(())(((()))(()))((())((())))((()))(((()))(()))((())((())))()(((()))(()))((())(()))(())(((()))
(()))((())((()))))

More readable version:

()()(
  R()
  A(R)
  B(A)

  0(AA)
  1(AB)
  x(BA)

  \set ()
  \in (())
  \out ((()))
  \loop (()())
)

\set x 0
\in x 1

\loop x 1 (
  \set x 0
  \in x 1

  \out x 1

  \set x 0
  \in x 1
)

Reverse string

()((()())(()(()())))(()())()((()(()()))(()(()())))(()())(())((()(()()))(()(()())))(()(()()))(()())((
()(()()))(()(()())))(()(()()))(()((()(()()))(()(()())))(()())(())((()(()()))(()(()())))(()(()()))()(
(()(()()))(()()))((()())(()()))()((()())(()()))((()())(()())((()())(()())))()((()(()()))(()())(()())
)((()(()()))(()(()())))()((()(()()))(()())(()(()())))((()())(()(()())))()((()())(()(()())))((()(()()
))(()()))()((()(()()))(()(()())))(()())(())((()(()()))(()(()())))(()(()())))()((()(()()))(()(()())))
(()(()()))(()())((()())(()(()())))(()())(()((()(()()))(()(()())))(()())()((()())(()(()())))(()(()())
))(()())((()(()()))(()(()())))(()(()()))(((()))((()())(()(()()))(()()))(()(()()))()((()())(()(()()))
)((()())(()(()()))(()(()())))()((()(()()))(()(()())))(()(()()))(()())((()())(()(()())))(()())(()((()
(()()))(()(()())))(()())()((()())(()(()())))(()(()()))))

More readable version:

.().(
  \set .
  \in (.)
  \out ((.))
  \loop (..)

  R .
  0 (RR)
  1 (R0)
  + (00)
  ~ (00+)

  \ptr (01)
  \ptr.bit (010)
  \ptr.next (011)

  \elem (10)
  \elem.bit (100)
  \elem.next (101)

  \bit (11)
)

\set \ptr 0

\set \bit 0
\in \bit 1
\loop \bit 1 (
  \set \bit 0
  \in \bit 1
  
  \set \elem +.+~
  \set \elem.bit \bit
  \set \elem.next \ptr
  \set \ptr \elem

  \set \bit 0
  \in \bit 1
)

\set \bit 1
\loop \ptr 0 (
  \set \bit 0
  \set \ptr 1
)

\loop \bit 1 (
  \out \ptr.bit 1
  \set \ptr \ptr.next

  \set \bit 1
  \loop \ptr 0 (
    \set \bit 0
    \set \ptr 1
  )
)

Increment as a binary number

()((()())(()())(()(()())))(()())()((()())(()(()()))(()(()())))(()())()((()(()()))(()())(()(()())))((
)(()()))()((()(()()))(()())(()()))(()())(())((()(()()))(()())(()()))(()(()()))(()())((()(()()))(()()
)(()()))(()(()()))(()((()(()()))(()())(()()))(()())(())((()(()()))(()())(()()))(()(()()))()((()())((
)(()()))(()()))((()())(()())(()()))()((()())(()())(()()))((()())(()())(()())((()())(()())(()())))()(
(()())(()(()()))(()())(()()))((()(()()))(()())(()()))()((()())(()(()()))(()())(()(()())))((()())(()(
))(()(()())))()((()())(()())(()(()())))((()())(()(()()))(()()))()((()(()()))(()())(()()))(()())(())(
(()(()()))(()())(()()))(()(()())))()((()(()()))(()())(()()))(()(()()))(()())((()())(()())(()(()())))
(()())(()((()(()()))(()())(()()))(()())()((()())(()())(()(()())))(()(()())))(()())((()(()()))(()())(
()()))(()(()()))(()((()(()()))(()())(()()))((()())(()())(()(()()))(()()))()((()(()()))(()(()()))(()(
)))((()(()()))(()())(()(()())))(()())((()(()()))(()(()()))(()()))(()(()()))((()())((()(()()))(()())(
()()))(()())(()((()())(()())(()(()()))(()()))(()(()()))()((()(()()))(()())(()(()())))(()())()((()(()
()))(()())(()()))())(()())((()(()()))(()())(()()))(()(()()))(()((()())(()())(()(()()))(()()))(()())(
)((()(()()))(()())(()()))())()((()(()()))(()(()()))(()()))())()((()())(()(()()))(()()))((()())(()())
(()()))()((()())(()())(()()))((()())(()())(()())((()())(()())(()())))()((()())(()(()()))(()())(()())
)((()())(()())(()(()()))(()()))()((()())(()(()()))(()())(()(()())))((()())(()(()()))(()(()())))()(((
)())(()(()()))(()(()())))((()())(()(()()))(()()))()((()())(()())(()(()())))((()())(()())(()(()()))((
)(()())))()((()(()()))(()())(()()))(()(()()))(()())((()())(()())(()(()())))(()())(()((()(()()))(()()
)(()()))(()())()((()())(()())(()(()())))(()(()()))))(()())((()(()()))(()())(()(()())))(()(()()))(()(
(()(()()))(()())(()(()())))(()())((())))()((()(()()))(()())(()()))(()(()()))(()())((()())(()(()()))(
()(()())))(()())(()((()(()()))(()())(()()))(()())()((()())(()(()()))(()(()())))(()(()())))(()())((()
(()()))(()())(()()))(()(()()))(((()))((()())(()(()()))(()(()()))(()()))(()(()()))()((()())(()(()()))
(()(()())))((()())(()(()()))(()(()()))(()(()())))()((()(()()))(()())(()()))(()(()()))(()())((()())((
)(()()))(()(()())))(()())(()((()(()()))(()())(()()))(()())()((()())(()(()()))(()(()())))(()(()()))))

More readable version:

.().(
  \set .
  \in (.)
  \out ((.))
  \loop (..)

  R .
  0 (RR)
  1 (R0)
  + (000)
  ~ (000+)

  \ptr1 (001)
  \ptr1.bit (0010)
  \ptr1.next (0011)

  \elem (010)
  \elem.bit (0100)
  \elem.next (0101)

  \ptr2 (011)
  \ptr2.bit (0110)
  \ptr2.next (0111)

  \bit (100)
  \carry (101)
  \aux (110)
)

\set \ptr1 0
\set \ptr2 0
\set \carry 1

\set \bit 0
\in \bit 1
\loop \bit 1 (
  \set \bit 0
  \in \bit 1
  
  \set \elem +.+~
  \set \elem.bit \bit
  \set \elem.next \ptr1
  \set \ptr1 \elem

  \set \bit 0
  \in \bit 1
)

\set \bit 1
\loop \ptr1 0 (
  \set \bit 0
  \set \ptr1 1
)

\loop \bit 1 (
  \set \bit \ptr1.bit
  \set \aux \carry

  \loop \aux 1 (
    \loop \bit 0 (
      \set \ptr1.bit 1
      \set \carry 0
      \set \bit .
    )

    \loop \bit 1 (
      \set \ptr1.bit 0
      \set \bit .
    )

    \set \aux .
  )

  \set \elem +.+~
  \set \elem.bit \ptr1.bit
  \set \elem.next \ptr2
  \set \ptr2 \elem

  \set \ptr1 \ptr1.next

  \set \bit 1
  \loop \ptr1 0 (
    \set \bit 0
    \set \ptr1 1
  )
)

\loop \carry 1 (
  \set \carry 0
  \out
)

\set \bit 1
\loop \ptr2 0 (
  \set \bit 0
  \set \ptr2 1
)

\loop \bit 1 (
  \out \ptr2.bit 1
  \set \ptr2 \ptr2.next

  \set \bit 1
  \loop \ptr2 0 (
    \set \bit 0
    \set \ptr2 1
  )
)

Interpreters

Interpreter