(top, height)
(top, height) is a two-dimensional language where the pointer's x-coordinate is based on the value at the top of the stack, while the y-coordinate is based on the height of the stack.
Instructions
The program starts with a stack only containing the value 0. This means the program always starts at (0,0).
| Command | Description |
|---|---|
0-9 |
Push the number onto the stack. |
A-Z,a-z |
Push the ASCII value of the character onto stack. |
+ |
Pop two values A and B, then push the result of A+B. |
- |
Pop two values A and B, then push the result of A-B. |
* |
Pop two values A and B, then push the result of A*B. |
/ |
Pop two values A and B, and check if B equals the number 0. |
% |
Pop two values A and B, and check if B equals the number 0. |
> |
Pop two values A and B, then push whichever one is greater. |
< |
Pop two values A and B, then push whichever one is smaller. |
: |
Duplicate top of stack. |
\ |
Swap top stack values. |
$ |
Pop top of stack and discard. |
. |
Pop top of stack and output as integer. |
, |
Pop top of stack, modulo 256, and output as ASCII character. |
~ |
Get input from user. |
| Anything else | End program. |
! |
Push the ASCII value of the character onto the stack. |
^ |
Pop top two values A and B. |
Every time an action is performed, the pointer's x-coordinate is reset to the absolute value of the value on top of the stack, and the y-coordinate is reset to the height of the stack - 1.
Any operation which uses two values, such as + or -, will end the program if the x-coordinate is less than 0 (meaning the stack height is one).
The program will also end if the stack height is equal to 0.
Code Examples
Truth Machine
~ 2: ..\
Hello, World!
This prints Hello, World! The space is written by multiplying 8 and 4, while the comma is written by taking the ASCII value of X, dividing it by 2, and taking the absolute value of subtracting that from 1. Finally, the exclamation mark is made by subtracting 1 from the ASCII value of A, then subtracting that from the ASCII value of a.
H e lloX8W orldA 1 \++++++4+++++ 1 1 , 21 12 1 1 1 \\ * ,, , a1 ,2 ,, , , , \\ - / -
Parenthesis Checker
The only valid characters are ( and ) and end-of-file. In order to indicate end-of-file, I imagine / will be entered. This should prove that (top, height) Version 0.1.0 has strength equivalent to that of the FSA that recognizes this.
~ TODO
Alternate Writing Convention
This language requires a ridiculous amount of spacing, but I think it's possible to write it in a less tedious way.
In this writing convention, each command in the language consists of a numerical value and a character, separated by a space and surrounded by parentheses. For example, here is the truth machine:
(0 ~) (0 2)(1 :) (0 .)(1 .)(2 \)
The number replaces the x-coordinate in normal (top, height).
This will also make it easier to represent code with very large values in case it's ever needed.
Complexity
I am going to deliberately prove the Computational class of (top, height) by showing that it must be in a specific computational class due to its ability to do things.
This is because at first, I believed Version 0.1.0 to be equivalent to a Push-down automaton due to its stack, even though I don't know how to prove that it is stronger than a Finite-state automaton. I also realized, after thinking about it, that Version 0.1.1 can't do certain things that a Turing machine can do unless given a program which takes an infinite time to write.
Also, thank you to BoundedBeans for giving me some information about this.
Unusable for Computation (impossible)
It is possible that this language is unusable for computation, but the more non-trivial programs I write, the more I can show that this language is computationally powerful.
I just don't think it's computationally useless.
Finite-state automaton
I believe Version 0.1.0 is at least capable of representing some FSAs.
- The pointer is in a finite number of states.
- The machine receives input signals from where the pointer is on the code.
- It transitions to another state because the pointer changes based on the input signal or halts.
- It produces output signals because the pointer is either in a different state or the code halts.
However, Version 0.1.0 is probably less powerful than a PDA because a PDA would require it to have a separate stack which it can manipulate. I believe the stack which Version 0.1.0 uses to store data can't actually do this because it's already holding the instruction value at its top, and any attempt to manipulate the stack also manipulates the next instruction. In order to use the stack correctly, it would have to be able to manipulate stored values in a way which doesn't automatically determine the next instruction.
Possible Proofs:
- It is possible to construct a FSA which can tell you whether or not a string starts with an opening parenthesis and ends with a closing parenthesis, no matter how long that string is.
- You would have to figure out a way to indicate the end of the string; it can't be a space or newline because both of these result in automatic halting.
- Which FSA is it unable to simulate? FSAs are not all computationally equivalent.
- If this language can be simulated by a Turing machine which can't go left, then it's probably equivalent to an FSA.
- Apparently, PricK can simulate FSAs, so if PricK can simulate this language, then it's probably equivalent to an FSA.
Push-down automaton
I used to think Version 0.1.0 was this powerful before realizing I should prove it instead of going off a hunch. All in all, I no longer think Version 0.1.0 is this powerful.
Possible Proofs:
- The problem of recognizing that parentheses are correctly nested in a string can be solved by a PDA, but not by a FSA.
- There are no universal PDAs, so which PDA is it unable to simulate?
- Disproof: There isn't an explicit bound on the command length, so unbounded integers are fine.
Linear bounded automaton
This might also be possible, due to (top, height) obviously having limited data based on the stack.
However, just because it's possible doesn't mean it's likely. I should probably have solid proof of some computational power before I get to this point. Check back later, I guess.
Turing-complete
At one point, I thought Version 0.1.1 was this powerful. This was a ridiculous delusion in hindsight.
Turing-complete languages:
- can freely store and access infinite data
- Version
- Version 0.1.1 explicitly added the ability to store and access data, but not infinite data. If there was some way to access data further up from the top of the stack, that would probably allow this language to be Turing-complete
- have conditional operations
- contrary to what I said before (and in accordance to what I said before I didn't say it), I think Version 0.1.1 has these, where each command operates like an addition to a switch statement
Darn, it's hard to prove computational class.
I don't know if I want to make this language Turing-complete. I would rather add random things which don't make the language Turing-complete.
Implementations
There are going to be multiple versions of the language as I add new features. I did this so that people know what aspects of the language are included by any given interpreter.
Version 0.1.0
This is a Python 3 implementation of Version 0.1.0 of this language.
def run_top_height(code_string: str, text_file = False) -> None:
stack = [0]
code = []
if text_file:
with open(code_string, 'r') as file:
# The newlines don't affect the outcome
code = file.readlines()
else:
code = code_string.split('\n')
while len(stack) > 0:
# The pointer's next position is always x_coord, y_coord.
x_coord = abs(stack[-1])
y_coord = len(stack)-1
if y_coord < len(code) and x_coord < len(code[y_coord]):
instruction = code[y_coord][x_coord]
# appends digits
if instruction.isdigit():
stack.append(int(instruction))
# appends the ASCII values of letters
elif instruction.isalpha():
stack.append(ord(instruction))
# move down one space
elif ':' == instruction:
stack.append(stack[-1])
# arithmetic instructions
elif instruction in {'+', '-', '*', '<', '>', '\\', '/', '%'}:
if y_coord > 0:
a = stack.pop()
b = stack.pop()
if '+' == instruction:
stack.append(a+b)
elif '-' == instruction:
stack.append(a-b)
elif '*' == instruction:
stack.append(a*b)
elif '>' == instruction:
stack.append(max({a,b}))
elif '<' == instruction:
stack.append(min(a,b))
elif '\\' == instruction:
stack.append(a)
stack.append(b)
else:
if b == 0:
break
elif '/' == instruction:
stack.append(a//b)
else:
stack.append(a%b)
else:
break
# popping instructions
elif instruction in {'$', '.', ','}:
new = stack.pop()
if '.' == instruction:
print(new,end='')
elif ',' == instruction:
print(chr(abs(new)),end='')
elif '~' == instruction:
new = input()[0]
if new.isdigit():
stack.append(int(new))
else:
stack.append(ord(new))
else:
break
else:
break
Version 0.1.1
def run_top_height(code_string: str, text_file = True) -> None:
stack = [0]
code = []
if text_file:
with open(code_string, 'r') as file:
# The newlines don't affect the outcome
code = file.readlines()
else:
code = code_string.split('\n')
while len(stack) > 0:
# The pointer's next position is always x_coord, y_coord.
x_coord = abs(stack[-1])
y_coord = len(stack)-1
if y_coord < len(code) and x_coord < len(code[y_coord]):
instruction = code[y_coord][x_coord]
# appends digits
if instruction.isdigit():
stack.append(int(instruction))
# appends the ASCII values of letters
elif instruction.isalpha() or '!' == instruction:
stack.append(ord(instruction))
# move down one space
elif ':' == instruction:
stack.append(stack[-1])
# arithmetic instructions
elif instruction in {'+', '-', '*', '<', '>', '\\', '/', '%', '^'}:
if y_coord > 0:
a = stack.pop()
b = stack.pop()
if '+' == instruction:
stack.append(a+b)
elif '-' == instruction:
stack.append(a-b)
elif '*' == instruction:
stack.append(a*b)
elif '>' == instruction:
stack.append(max({a,b}))
elif '<' == instruction:
stack.append(min(a,b))
elif '\\' == instruction:
stack.append(a)
stack.append(b)
elif '^' == instruction:
anum = (-(a+1) if a+1 < len(stack) else 0)
c = stack[anum]
stack[anum] = b
stack.append(c)
else:
if b == 0:
break
elif '/' == instruction:
stack.append(a//b)
else:
stack.append(a%b)
else:
break
# popping instructions
elif instruction in {'$', '.', ','}:
new = stack.pop()
if '.' == instruction:
print(new,end='')
elif ',' == instruction:
print(chr(abs(new)),end='')
elif '~' == instruction:
new = input()[0]
if new.isdigit():
stack.append(int(new))
else:
stack.append(ord(new))
else:
break
else:
break