XYZ?
XYZ? is an esolang by User:BoundedBeans designed to be interpretable by Deadfish PDA, a language that is not even powerful enough to simulate every Push-down automaton since it has only 256 states, 4 stack symbols, and 4 input symbols. It seems remarkably powerful for this condition, featuring conditionals and procedural control flow instead of the case-checking control flow of Deadfish PDA. One thing of note is it is not directly interpreted by Deadfish PDA, but instead an automated "feeder" program should be used to infinitely feed input to Deadfish PDA until halting happens.
This language tries to have nice syntax, but must be compiled to a language Deadfish PDA can understand. It has only a stack, and no states, since the states are needed to actually interpret the language. However, the implementation only uses 19 states, so it is very likely that a much larger language could be built, with around 13 times more features. It only has forward control flow, and no explicit loops, but the "feeder" is required to continually input the program over and over to the Deadfish PDA interpreter, effectively placing the whole program in a loop.
There are two variants of this language, which are completely different in syntax: XYZ? Assembly and XYZ? Native. Mostly this article covers XYZ? Assembly, but also details how it translates to XYZ? Native.
There are five commands in this language, their names describing what they do (the numbers are not included):
1. Push (A|B|C|!) to the stack. 2. Pop from the stack. 3. Skip unless the stack has (A|B|C|!). 4. Output the top stack symbol as a number from 0-3. 5. Halt.
An extra command not handled by Deadfish PDA is this:
6. Push input to the stack.
Outputting requires mapping stack symbols to numbers, which uses the following mapping: A: 0, B: 1, C: 2, !: 3.
They should be on their own line. Indentation is optional and ignored, but encouraged.
Letters have a correspondance of X: A, Y: B, Z: C, ?: !.
Command 1 is translated to X(letter)?. X puts the interpreter in a special state which tells it to look for another character, and depending on that character, to push something onto the stack.
Command 2 is translated to Y?. This puts the interpreter into a state where it pops from the stack no matter what it is
Command 3 is translated Z(letter). If the character is not that, it skips all characters until the next Z with the same letter. If it doesn't skip the characters, the "ending brace" will be checked as if it was a "starting brace". To make this a non-issue, always make sure the condition is met by the end of the if statement if it is not skipped (which can be very easily met by simply pushing the symbol onto the stack, skip-checking, and popping).
Command 4 is translated ?X?.
Command 5 is translated ?Y?.
Command 6 is not handled by Deadfish PDA, but by the Feeder of the XRE. It is replaced by the internal representation of X@?.
This language should ideally be fed automatically to a Deadfish PDA interpreter. If it does, it should continue feeding it in repeatedly until Halt. is executed (in a skipped conditional block, it won't count).
States and transitions
0:
If input is X, go to state 1.
If input is Y, go to state 2.
If input is Z, go to state 3.
If input is ?, go to state 4.
1:
If input is X, go to state 10.
If input is Y, go to state 11.
If input is Z, go to state 12.
If input is ?, go to state 13.
2:
Pop from the stack, go to state 0.
3:
If input is X and stack is not A, go to state 30.
If input is Y and stack is not B, go to state 31.
If input is Z and stack is not C, go to state 32.
If input is ? and stack is not !, go to state 33.
Otherwise, go to state 0.
4:
If input is X, go to state 40.
If input is Y, go to state 41.
10:
Push A, go to state 0.
11:
Push B, go to state 0.
12:
Push C, go to state 0.
13:
Push !, go to state 0.
30:
If input is Z, go to state 34.
31:
If input is Z, go to state 35.
32:
If input is Z, go to state 36.
33:
If input is Z, go to state 37.
34:
If input is X, go to state 0.
Otherwise, go to state 30.
35:
If input is Y, go to state 0.
Otherwise, go to state 31.
36:
If input is Z, go to state 0.
Otherwise, go to state 32.
37:
If input is ?, go to state 0.
Otherwise, go to state 33.
40:
If stack is A, print 0 and go to state 0.
If stack is B, print 1 and go to state 0.
If stack is C, print 2 and go to state 0.
If stack is !, print 3 and go to state 0.
41:
Halt.
XYZ? Native Interpreter in Deadfish PDA
# 0 # 0 0 X A i 0 # 0 0 X B i 0 # 0 0 X C i 0 # 0 0 X ! i 0 # 0 1 X A isiiiiii 0 # 0 1 X B isiiiiii 0 # 0 1 X C isiiiiii 0 # 0 1 X ! isiiiiii 0 # 0 1 Y A isiiiiiii 0 # 0 1 Y B isiiiiiii 0 # 0 1 Y C isiiiiiii 0 # 0 1 Y ! isiiiiiii 0 # 0 1 Z A isiiiiiiii 0 # 0 1 Z B isiiiiiiii 0 # 0 1 Z C isiiiiiiii 0 # 0 1 Z ! isiiiiiiii 0 # 0 1 ? A isiiiiiiiii 0 # 0 1 ? B isiiiiiiiii 0 # 0 1 ? C isiiiiiiiii 0 # 0 1 ? ! isiiiiiiiii 0 # 0 10 ? A dddddddddd 0 A 0 10 ? B dddddddddd 0 A 0 10 ? C dddddddddd 0 A 0 10 ? ! dddddddddd 0 A 0 11 ? A ddddddddddd 0 B 0 11 ? B ddddddddddd 0 B 0 11 ? C ddddddddddd 0 B 0 11 ? ! ddddddddddd 0 B 0 12 ? A dddddddddddd 0 C 0 12 ? B dddddddddddd 0 C 0 12 ? C dddddddddddd 0 C 0 12 ? ! dddddddddddd 0 C 0 13 ? A ddddddddddddd 0 ! 0 13 ? B ddddddddddddd 0 ! 0 13 ? C ddddddddddddd 0 ! 0 13 ? ! ddddddddddddd 0 ! 0 2 ? A # 1 # 0 2 ? B # 1 # 0 2 ? C # 1 # 0 2 ? ! # 1 # 0 4 X A ssdddddddddddddddddddddddd 0 # 0 4 X B ssdddddddddddddddddddddddd 0 # 0 4 X C ssdddddddddddddddddddddddd 0 # 0 4 X ! ssdddddddddddddddddddddddd 0 # 0 4 Y A ssddddddddddddddddddddddd 0 # 0 4 Y B ssddddddddddddddddddddddd 0 # 0 4 Y C ssddddddddddddddddddddddd 0 # 0 4 Y ! ssddddddddddddddddddddddd 0 # 0 40 ? A ddddddddddddddddddddddddddddddddddddddddo 0 # 0 40 ? B dddddddddddddddddddddddddddddddddddddddod 0 # 0 40 ? C ddddddddddddddddddddddddddddddddddddddodd 0 # 0 40 ? ! dddddddddddddddddddddddddddddddddddddoddd 0 # 0 41 ? A # 0 # 1 41 ? B # 0 # 1 41 ? C # 0 # 1 41 ? ! # 0 # 1 3 X A ddd 0 # 0 3 X B ssiii 0 # 0 3 X C ssiii 0 # 0 3 X ! ssiii 0 # 0 3 Y A ssiiii 0 # 0 3 Y B ddd 0 # 0 3 Y C ssiiii 0 # 0 3 Y ! ssiiii 0 # 0 3 Z A ssiiiii 0 # 0 3 Z B ssiiiii 0 # 0 3 Z C ddd 0 # 0 3 Z ! ssiiiii 0 # 0 3 ? A ssiiiiii 0 # 0 3 ? B ssiiiiii 0 # 0 3 ? C ssiiiiii 0 # 0 3 ? ! ddd 0 # 0 30 Z A iiii 0 # 0 30 Z B iiii 0 # 0 30 Z C iiii 0 # 0 30 Z ! iiii 0 # 0 31 Z A iiii 0 # 0 31 Z B iiii 0 # 0 31 Z C iiii 0 # 0 31 Z ! iiii 0 # 0 32 Z A iiii 0 # 0 32 Z B iiii 0 # 0 32 Z C iiii 0 # 0 32 Z ! iiii 0 # 0 33 Z A iiii 0 # 0 33 Z B iiii 0 # 0 33 Z C iiii 0 # 0 33 Z ! iiii 0 # 0 34 X A dddddddddddddddddddddddddddddddddd 0 # 0 34 X B dddddddddddddddddddddddddddddddddd 0 # 0 34 X C dddddddddddddddddddddddddddddddddd 0 # 0 34 X ! dddddddddddddddddddddddddddddddddd 0 # 0 35 Y A ddddddddddddddddddddddddddddddddddd 0 # 0 35 Y B ddddddddddddddddddddddddddddddddddd 0 # 0 35 Y C ddddddddddddddddddddddddddddddddddd 0 # 0 35 Y ! ddddddddddddddddddddddddddddddddddd 0 # 0 36 Z A dddddddddddddddddddddddddddddddddddd 0 # 0 36 Z B dddddddddddddddddddddddddddddddddddd 0 # 0 36 Z C dddddddddddddddddddddddddddddddddddd 0 # 0 36 Z ! dddddddddddddddddddddddddddddddddddd 0 # 0 37 ? A ddddddddddddddddddddddddddddddddddddd 0 # 0 37 ? B ddddddddddddddddddddddddddddddddddddd 0 # 0 37 ? C ddddddddddddddddddddddddddddddddddddd 0 # 0 37 ? ! ddddddddddddddddddddddddddddddddddddd 0 # 0 34 Y A dddd 0 # 0 34 Y B dddd 0 # 0 34 Y C dddd 0 # 0 34 Y ! dddd 0 # 0 34 Z A dddd 0 # 0 34 Z B dddd 0 # 0 34 Z C dddd 0 # 0 34 Z ! dddd 0 # 0 34 ? A dddd 0 # 0 34 ? B dddd 0 # 0 34 ? C dddd 0 # 0 34 ? ! dddd 0 # 0 35 X A dddd 0 # 0 35 X B dddd 0 # 0 35 X C dddd 0 # 0 35 X ! dddd 0 # 0 35 Z A dddd 0 # 0 35 Z B dddd 0 # 0 35 Z C dddd 0 # 0 35 Z ! dddd 0 # 0 35 ? A dddd 0 # 0 35 ? B dddd 0 # 0 35 ? C dddd 0 # 0 35 ? ! dddd 0 # 0 36 X A dddd 0 # 0 36 X B dddd 0 # 0 36 X C dddd 0 # 0 36 X ! dddd 0 # 0 36 Y A dddd 0 # 0 36 Y B dddd 0 # 0 36 Y C dddd 0 # 0 36 Y ! dddd 0 # 0 36 ? A dddd 0 # 0 36 ? B dddd 0 # 0 36 ? C dddd 0 # 0 36 ? ! dddd 0 # 0 37 X A dddd 0 # 0 37 X B dddd 0 # 0 37 X C dddd 0 # 0 37 X ! dddd 0 # 0 37 Y A dddd 0 # 0 37 Y B dddd 0 # 0 37 Y C dddd 0 # 0 37 Y ! dddd 0 # 0 37 Z A dddd 0 # 0 37 Z B dddd 0 # 0 37 Z C dddd 0 # 0 37 Z ! dddd 0 # 0
Assembly to Native Compiler in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
String code = "";
while (true){
String line = in.nextLine();
if (line.equals("@END")){
System.out.print(code);
break;
}
switch (line.trim()){
case "Push A to the stack.":
code += "XX?";
break;
case "Push B to the stack.":
code += "XY?";
break;
case "Push C to the stack.":
code += "XZ?";
break;
case "Push ! to the stack.":
code += "X??";
break;
case "Pop from the stack.":
code += "Y?";
break;
case "Skip unless the stack has A.":
code += "ZX";
break;
case "Skip unless the stack has B.":
code += "ZY";
break;
case "Skip unless the stack has C.":
code += "ZZ";
break;
case "Skip unless the stack has !.":
code += "Z?";
break;
case "Output the top stack symbol as a number from 0-3.":
code += "?X?";
break;
case "Halt.":
code += "?Y?";
break;
case "Push input to the stack.":
code += "X@?";
default:
throw new Exception("Invalid instruction" + line.trim());
}
}
}
}
Conditional flow
An if-statement can be translated:
if stack.peek() == 'B':
stack.pop()
stack.push('C')
print(stack.peek)
Skip unless the stack has B. Pop from the stack. Push C to the stack. Output the top stack symbol as a number from 0-3. Push B to the stack. Skip unless the stack has B. Pop from the stack.
Nested if-statements can be simulated as long as they have different conditions.
if stack.peek() == '!':
stack.pop()
if stack.peek() == 'A':
stack.push('C')
print(stack.peek())
Skip unless the stack has !.
Pop from the stack.
Skip unless the stack has A.
Push C to the stack.
Output the top stack symbol as a number from 0-3.
Push A to the stack.
Skip unless the stack has A.
Pop from the stack.
Push ! to the stack.
Skip unless the stack has !.
Pop from the stack.
Else statements can be simulated by checking every other option, and a different set of nestings can be in each one.
if stack.peek() == 'C':
print(stack.peek())
else:
stack.push('!')
Skip unless the stack has C. Output the top stack symbol as a number from 0-3. Push C to the stack. Skip unless the stack has C. Skip unless the stack has A. Push ! to the stack. Push A to the stack. Skip unless the stack has A. Skip unless the stack has B. Push ! to the stack. Push B to the stack. Skip unless the stack has B. Skip unless the stack has !. Push ! to the stack. Push ! to the stack. Skip unless the stack has !. Pop from the stack.
Nested if-else is not possible. Since checking every possible condition is necessary for if-else, you cannot put an if-else inside of an if-else. You can, however, put ifs inside of an else section, if they check the same condition the main if block does.
if stack.peek() == 'A':
print(stack.peek())
else:
if stack.peek() == 'A':
stack.push('!')
Skip unless the stack has A.
Output the top stack symbol as a number from 0-3.
Skip unless the stack has A.
Skip unless the stack has B.
Skip unless the stack has A.
Push ! to the stack.
Push A to the stack.
Skip unless the stack has A.
Pop from the stack.
Push B to the stack.
Skip unless the stack has B.
Skip unless the stack has C.
Skip unless the stack has A.
Push ! to the stack.
Push A to the stack.
Skip unless the stack has A.
Pop from the stack.
Push C to the stack.
Skip unless the stack has C.
Skip unless the stack has !.
Skip unless the stack has A.
Push ! to the stack.
Push A to the stack.
Skip unless the stack has A.
Pop from the stack.
Push ! to the stack.
Skip unless the stack has !.
Pop from the stack.
You can of course do elif by having a different condition in each block. In this case, any condition not already enclosing the code can be used inside. For example:
if stack.peek() == 'C':
print(stack.peek())
push('A')
elif stack.peek() == 'A':
stack.pop()
if stack.peek() == '!':
stack.pop()
stack.pop()
elif stack.peek() == 'C':
stack.pop()
stack.push('!')
Skip unless the stack has C.
Output the top stack symbol as a number from 0-3.
Push A to the stack.
Push C to the stack.
Skip unless the stack has C.
Skip unless the stack has A.
Pop from the stack.
Skip unless the stack has !.
Pop from the stack.
Pop from the stack.
Push ! to the stack.
Skip unless the stack has !.
Pop from the stack.
Push A to the stack.
Skip unless the stack has A.
Pop from the stack.
Why I bothered to make this
Deadfish PDA is an extremely simple language that cannot even emulate every single push-down automata. Due to its 256 states and restricted stack access, it is not even likely to be able to emulate some huge finite-state automata.
I wanted to show that computationally impowerful languages can be still used to make interesting things (like other languages). XYZ? is interpretable by Deadfish PDA, and appears to be able to actually be used for computing a few things. It also demonstrates how to take a "conditional paradigm" construct like a push-down automata and transform it into a procedural language.
A few notes:
- There is a limited amount of "code" Deadfish PDA can handle directly. Since there are only 256*4*4 = 4096 conditions to check for, there are only a specific amount of possible push-down automata this can represent, barring output. However, input can be indefinite, so there is an infinite amount of distinct XYZ? programs. Deadfish PDA has now been proven to be able to handle procedural code by this language, allowing an infinite set of possible tasks Deadfish PDA can do with a given input.
- The reference Runner source uses only 19 states. They are numbered up to 41, but this is simply for organisation and only 19 states will ever be entered. This means many much, much bigger languages can be created in Deadfish PDA, and there is a limit, but it is huge.
XYZ? Runtime Environment
The XRE needs four parts:
- The Compiler, which compiles XYZ? Assembly to XYZ? Native.
- The Feeder, which takes the result of the Compiler and feeds it to the Runner. The Feeder also takes @ symbols and replace them with user input before feeding them into the Runner.
- The Runner, written in Deadfish PDA, which takes input from the Feeder and runs it.
- The Interpreter, which allows the running of Deadfish PDA.
Often, the Feeder and the Interpreter may actually be different parts of the same program. This may be extremely helpful since then you won't need to transfer the XYZ? Native code to the Interpreter and the Runner.