(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 ,, , , , \\ - / -
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 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.
Combinatorial Logic
I believe that the fact that it has a stack allows it to have states even in Version 0.1.0, so (top, height) is stronger than pure combinatorial logic.
Finite-State Automaton
I believe Version 0.1.0 is at least this powerful.
- 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.
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.
- FSAs are not all computationally equivalent.
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.
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 store data (this is what Version 0.1.1 added)
- have conditional operations (Version 0.1.1 doesn't have these)
Was that so hard to figure out? It was hard for me to accept.
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