Xenon

Xenon

Paradigm(s)	imperative
Designed by	Jayde M
Appeared in	2024
Memory system	Queue-based
Dimensions	one-dimensional
Computational class	Turing complete
Reference implementation	Unimplemented
File extension(s)	.xen, .xob

Xenon is an esolang created by Jayde M in 2024. It's written at the binary level, and looks quite compact at the byte level, but was not intended for golfing or similar purposes. Specifically, she wrote it for the intention of building a language written in binary and motivated by the concept of registers, but which isn't just a copy of assembly. Unlike assembly, there are infinitely many registers and each is unlimited in size, and unlike the infinitely many cells of a Turing machine it is impossible to build rules acting on arbitrary registers since there can be no dereferencing. Nevertheless, one can simulate Turing machines, as discussed later in this introduction.

In the end it has 23 instructions. Summarizing what has been said so far, it is based off of a low-level, imperative paradigm, deterministic, queue-based design, akin to some traditional programming languages.

It is quite easily seen to be Turing complete because it can simulate counter machines:

• Clearing register X can be achieved by copying in the literal zero: 01000X10111011000.
• Incrementing register X can be achieved via the built in signed adder: 00000X101110111000.
• Decrementing register X can be achieved almost identically: 00000X10111111000.
• Copying a register is already a built-in instruction.
• JZ can be implemented due to the conditional branching functionality, but it is cumbersome as checking whether a register contains 0 is nontrivial.
• Using the same conditional branching functionality, JE(X,Y,Z) ... can be implemented as (assuming X and Y are registers 0 and 1 for simplicity) 00011101101110 001011110 1010110111011000 1011010111111000 1001110111011000 [instruction block Z] 10100 1001110111111000 ... 10100 (where the spaces have been added only for readability).

One can also directly simulate 2-color Turing machines using 4 registers, thanks to JJRubes. This is described later.

Syntax

Programs are written in binary, and may not be renderable as characters. A variant, Legible Xenon, uses the following padding together with ISO 8859-1 encoding to produce "semi-printable" programs (not fully printable in the sense that they may contain control or invisible characters): if P is a program of length n, then we let k be the least integer so that n+3+k is a multiple of 8; then padding adds 3 bits representing k to the beginning, and k zeroes to the end. The addition of the 3 bits is to ensure one can distinguish padding bits from ordinary bits (by knowing how many of the former there are). For example, a cat in Xenon is 1000010 1000110 00100, and this is padded to produce 01010000 10100011 00010000. Further encoding these bytes into text is achieved via the following text encoding scheme, known as SSCfCMP (designed by Jayde for Xenon; note that it is ASCII-incompatible):

⌂  ☺  ☻  ♥  ♦  ♣  ♠  •  ◘  ○  ◙  ♂  ♀  ♪  ♫  ☼
►  ◄  ↕  ‼  ¶  §  ▬  ↨  ↑  ↓  →  ←  ∟  ↔  ▲  ▼
₧  ƒ  ⌐  ░  ▒  ▓  │  ┤  ╡  ╢  ╖  ╕  ╣  ║  ╗  ╝
╜  ╛  ┐  └  ┴  ┬  ├  ─  ┼  ╞  ╟  ╚  ╔  ╩  ╦  ╠
═  ╬  â  ä  à  á  ã  å  ç  ñ  [  .  <  (  +  !
&  é  ê  ë  è  í  î  ï  ì  ß  ]  $  *  )  ;  ^
-  /  Â  Ä  À  Á  Ã  Å  Ç  Ñ  ¦  ,  %  _  >  ?
ø  É  Ê  Ë  È  Í  Î  Ï  Ì  `  :  #  @  '  =  "
Ø  a  b  c  d  e  f  g  h  i  «  »  ð  ý  þ  ±
°  j  k  l  m  n  o  p  q  r  ª  º  æ  ¸  Æ  ¤
µ  ~  s  t  u  v  w  x  y  z  ¡  ¿  Ð  Ý  Þ  ®
¢  £  ¥  ·  ©  §  ¶  ¼  ½  ¾  ¬  |  ¯  ¨  ´  ×
{  A  B  C  D  E  F  G  H  I  ╨  ô  ö  ò  ó  õ
}  J  K  L  M  N  O  P  Q  R  ¹  û  ü  ù  ú  ÿ
\  ÷  S  T  U  V  W  X  Y  Z  ²  Ô  Ö  Ò  Ó  Õ
0  1  2  3  4  5  6  7  8  9  ³  Û  Ü  Ù  Ú  ╤

Above, the column number is the right nibble and the row number is the left nibble. For example, 00001111, or 0F, encodes to ☼. This encoding is heavily inspired by IBM's CP437 and CP850.

Now, let us return to the specifics of Xenon. In Xenon, variables are stored in infinitely many registers 0, 1, etc. There is also a special register, called register W, but this cannot be explicitly used in copy, add, etc. instructions and is rather used internally by the program when performing if-else checks. Xenon also has a FIFO queue for keeping values safe when one wants to reuse registers or minimise the amount of registers that are used in the first place. Before enqueuing, one must allocate memory corresponding to how many elements one wants to enqueue. Dequeuing doesn't reallocate memory, so e.g. allocating 2 items, enqueuing twice, dequeuing twice and attempting to enqueue again produces an error. This is to make keeping track of how large the stack is easier.

Xenon has no explicit datatypes, for everything is a binary string. There are some implicit conventions in the instructions about how these strings are to be interpreted, though. Anything containing a one is interpreted as falsy, and everything else (e.g. the empty string) is interpreted as truthy. Booleans are hence represented as 0 for True and 1 for False. Each of the 23 instructions is assigned a 5-bit opcode (the other 9 possible opcodes are nops), and takes in at most 3 operands. Register i is written as a string of i+1 ones followed by a zero, and literals (i.e. literal strings) are encoded by prepending 10111 and appending 11000. Because this is unambiguous, operations are simply encoded by the 5-bit opcode followed by the operands, without any delimiter. All of the instructions are either bitwise or arithmetic operations on the registers, operations manipulating the queue, or control flow-related (i.e. unconditional or conditional jump and if-else). They are:

Command	Description
00000XY	Add X to Y, and store the result in X (which must be a register).
00001XY	Bitwise AND X and Y, and store the result in X.
00010XYZ	Checks if X > Y, and stores the result in Z (which must be a register).
00011XYZ	Checks if X == Y, and stores the result in Z.
00100	Halts execution.
00101X	Sets register W to 0 if X is truthy, else to 1.
00110XYZ	Get the Y'th bit of X and stores it in Z.
00111XY	Shifts X to the right by Y bits.
01000XY	Sets the value in X to Y.
01001XY	Bitwise OR X and Y, and store the result in X.
01010X	Enqueues the value X.
01011X	Dequeues to the register X.
01100X	Allocates X more values on the queue.
01101	Dequeues the entire queue, storing the results in registers 0, 1, etc.
01110XY	Bitwise XOR X and Y, and store the result in X.
01111XY	Gets the length of Y, ignoring leading zeros, and stores it in X.
10000X	Gets user input and stores it to X.
10001X	Prints X (which must be a register) to the screen.
10010X	Jumps to the instruction block whose name is X.
10011X	Starts the instruction block X.
10100	Ends the current instruction block.
10101X	Jumps to instruction block X if register W is 0.
10110X	Jumps to instruction block X if register W is 1.

In the 00000, 00010 and 00111 operations, the numbers are treated as signed via two's complement, so e.g. 0 > 1 (since the latter represents negative one; positive one is 01). Shifting right by a negative amount of bits just means shifting left. And adding something to a truthy value acts as prepending, e.g. 0 + 1 = 10; this is for convenience. In the 00110, 01100 and 01111 operations, the number is treated as ordinary, unsigned binary. Indices in strings are 0-indexed and so attempting to jump to the length'th bit would cause an out of bounds error, as is standard. Since we ignore leading zeroes, any truthy value has length zero. As a clarification, n.b. that jumps have an automatic "return" after them, obviously unless one adds a halt instruction. Instruction blocks which are reached during control flow will be automatically jumped into, rather than hanging the program just before, but there will obviously be no "return".

Example Programs

Since there is no datatyping distinction in Xenon, with everything being binary, there is no way to literally print e.g. "Hello World!" Rather, the Hello World program prints out the 96 bits which, in conjunction, spell out "Hello World!" via ASCII. Similarly, FizzBuzz doesn't print out numbers but their unsigned binary representations. So outputs should be "interpreted" as to the intention of the program. This section is a work-in-progress.

Null Program

The empty program is the simplest example of a non-halting program, as it doesn't contain an 00100 command to terminate execution or anything to throw an error. It, however, does nothing at all, so it’s not very interesting.

Infinite Loop

1001110111011000 1010110111011000 1011010111111000 10100 1001110111111000 00100 10100

A more sophisticated example of a non-halting program is one that contains a halt instruction but never reaches it due to infinite looping, such as the one given directly above. Specifically, it will go to instruction block 0 and will only jump out if W is falsy. But noninitialized registers are treated as empty, which is truthy, and W is never modified due to the absence of an if-else statement, i.e. 00101. In Legible Xenon, the above program is

D3 BB 15 BB 16 BF 14 9D F8 25 00

or, with SSCfCMP:

L|§|▬׶¸8▓⌂

Hello World!

0100010101110100100001100101011010000110100001101111001010000010000001010111011011110111001001101000011001000010000111000 010001101011101000110010001101111001001000010000001010111011011110111001001100100011001000010000111000 0100110110 1000110

One unfortunately cannot print out "Hello World!" by moving its ASCII value, saved as a literal, to register 0 and printing out register 0. This is since it contains 11000, signifying the end of a literal, and there are no escape sequences or the like in Xenon. Instead, we use t arithmetic operations to store the ASCII value in a register, without explicitly writing the whole thing. The above program sets register 0 to the ASCII value of "Hello, World!", where 11000 is replaced by 10000, register 1 to the same but with 01000 (and where the first few bits have been removed, as they’re redundant) and then it prints out their (inclusive) OR. In Legible Xenon, it corresponds to:

A8 AE 90 CA D0 D0 DE 50 40 AE DE E4 D0 C8 43 84 6B A3 23 79 21 02 BB 7B 93 23 21 0E 13 68 C0

or:

yÞ°╨}}ú&═ÞúU}Häd,t░`ƒ☻|#l░ƒ♫‼Ç{

Cat

1000010 1000110 00100

This gets the user's input, saves it to register 0, prints out register 0 and terminates. In Legible Xenon, this binary code corresponds to

50 A3 10

as mentioned in the introduction, or:

&t►

A cat which repeatedly gets user input and echoes it back out until it is manually terminated, rather than doing so once, is:

1001110111011000 1000010 1000110 1001010111011000 10100

which corresponds to

53 BB 10 A3 4A EC 50

or

ë|►t[Ö&

Truth Machine

1000010 0010110 1010110111011000 1011010111111000 1001110111011000 1000110 00100 10100 1001110111111000 0100011010111111000 1001010111111000 10100

This is quite an intuitive implementation of a truth machine - it performs an if-else on the input, if it's truthy it prints it and halts, else it prints 1 and jumps back, repeating forever. Whether there are shorter truth machines utilizing control flow more cleverly is an interesting question. In legible Xenon this truth machine is

D0 8B 56 EC 5A FC 4E EC 46 25 27 7E 11 AF C4 AF C5 00

or

}»îÖ]Ü+Öã▓┤=◄®D®E⌂

Turing Machine Emulator

We describe the aforementioned method for emulating 2-colour Turing machines in Xenon; by emulating a universal Turing machine, one can build a Xenon program individually capable of simulating any Turing machine, with a suitable coding.

Start out with registers 0, 2 and 3 empty, and register 1 containing the initial input to the machine. The tape will be stored in registers 0 and 1, representing the tape to the left of (or at) and to the right of the read head, respectively, with register 2 being a scratch register and register 3 holding the current state. At the end of the Xenon program, add the following instruction block, which appends a 1 bit to register 0: 1001110111011000 0000010101110111000 10100. Checking the current symbol at the read head and the current symbol, and using this to determine the current instruction, is done via conditional jumping. Each rule in the Turing machine program can now be translated into an instruction of Xenon like so:

• Not changing the bit at the head position is a nop, while flipping the bit at the head position is performed by XORing register 0 with 1.
• Moving right is obtained by 000001010111011000 001111010111111000 00110110101110110001110 001011110 1011010111011000 0011111010111111000. This appends the first bit of register 1 to register 0, and appends a zero bit to register 1. The latter is negligible, since the tape will have zeroes on both ends anyways: we’re just storing the fragment where we operate.
• Moving left is more difficult, as we must prepend bits. WIP
• Changing state is obviously done by just copying a literal into register 3.

Brainfuck Interpreter

Jayde is currently working on building a brainfuck interpreter in Xenon.