Stæck

Stæck is an esoteric programming language created by User:TuxCrafting designed to implement a deterministic nonerasing stack automaton.

Memory model

Stæck has two memory spaces: a bounded, read-only input bitstring, and an unbounded stack of bits. The stack can have values pushed into it, but not popped. It is possible to move left and right in the input string, and up and down in the stack, as long as it stays within their bounds.

The input string goes from left to right, and the stack from bottom to up (with top of the stack being the value most at the top).

Input/output

At the start of execution, a string of bits is inputted to the program and serves as the input bitstring.

The program will then either fail or succeed based on the input string.

There is also byte I/O possible, with an input queue and an output queue. When the input queue is dequeued, the next bit (starting from least significant) of the last inputted byte is returned, reading another byte if needed. Similarly, when the output queue contains 8 bits (starting from least significant), the byte represented is outputted.

Computational class

As Stæck is designed to implement a deterministic nonerasing stack automaton, which are Turing-complete, it is also Turing-complete. This is explicitly shown by a Bitwise Cyclic Tag interpreter.

Instructions

Unknown characters are ignored and are no-ops.

• [...] — Execute the block. Always succeeds.
• {...} — Execute the block in an infinite loop until it fails. Always succeeds.
• < — Move the input pointer left. Fail if it is already at the start of if the input is empty.
• > — Move the input pointer right. Fail if it is already at the end or if the input is empty.
• ^ — Move the stack pointer up. Fail if it already at the top or if the stack is empty.
• v — Move the stack pointer down. Fail if it already at the bottom or if the stack is empty.
• ! — Unconditionally fail.

Instructions that move data around have a special format. They are made of between one and three characters: source-[modification]-[destination].

• Source
  • # — Bit pointed to in the input string. Fail if the input string is empty.
  • $ — Bit pointed to in the stack. Fail if the stack is empty.
  • , — Dequeue a bit from the input queue. Fail on EOF.
  • ' — 0 bit.
  • " — 1 bit.
• Modification
  • Nothing — Pass the bit unmodified.
  • @ — Flip the bit.
• Destination
  • Nothing — Discard the bit.
  • & — Push the bit on the stack.
  • . — Enqueue the bit on the output queue.
  • ; — Fail if the bit is 0.
  • : — Fail if the bit is 1.

Examples

Cat program

{,.}

'Hello, World!' program

'.'.'.".'.'.".'.".'.".'.'.".".'.'.'.".".'.".".'.'.'.".".'.".".'.".".".".'.".".'.'.'.".".'.".'.'.'.'.'.'.'.".'.'.".".".'.".'.".'.".".".".'.".".'.'.".'.'.".".".'.'.'.".".'.".".'.'.'.".'.'.".".'.".'.'.'.'.".'.'.

Match input strings of the form '1ⁿ0ⁿ' (n > 0)

{#;"&>}'&{^}{#:v"&>}{^}{v<$;}#;{>v}[v'&]{^}$;

Truth-machine

{#.'.'.'.".".'.'.#;}

Bitwise Cyclic Tag interpreter

The input string contains the program and initial data in the format '1p 1p 1p 1p 00 d d d d', where 'p' is program bits, and 'd' is data bits. Wrapping arguments to 1x commands (eg 01 -> 0 10 10 10) aren't supported.

The stack contains each iteration of the data string, each in the format '00 1a 1b 1c ... 1n', with the pointer being at the initial 0 at each command.

Mutating the data is done by copying it back to the top of the stack, doing modifications if needed.

This interpreter proves that Stæck is Turing complete.

{#;>>}>>'&'&{"&#&>}{<}{^^vv[#:{<}][#;>[#:^^^^'&'&{$;^"&$&^}][#;>>^^^[$;"&#&]vvv]>]}

Or, annotated:

{#;>>}>>'&'&{"&#&>}{<} [! Copy initial data to stack ]

{ [! Main loop ]
	^^vv [! Stop if the data string is empty ]
	[#:{<}] [! Rewind if at the end of the program ]
	[#; [! If it's a command ]
		> [! Get command ]
		[#: [! It's 0, copy data without leftmost bit ]
			^^^^'&'&{$;^"&$&^}
		]
		[#; [! Else, it's 1 ]
			>> [! Advance pointer to bit to append ]
			^^^[$;"&#&]vvv [! If leftmost bit of the data is 1, append bit ]
		]
		> [! Go to next command ]
	]
}

Infinite loop

{}

Looping counter

{'&{'.".'.".'.".'.'.^}'.".'.".'.'.'.'.{v}}

Collatz sequence

Input string contains the starting number in unary. Outputs every step in unary.

'&'&{"&>}{^^^vvv^{^".'.'.'.".".'.'.}{$;v}v'.".'.".'.'.'.'.{^}{$;vv}^[$;'&'&{$;"&^^}^^][$:'&'&{^$;"&"&"&}"&^^]vv}".'.'.'.".".'.'.'.".'.".'.'.'.'.

Implementation

# Stæck interpreter
# No rights reserved

import sys

def parse(s):
	st = [[]]
	op = []
	for c in s:
		if c == "[":
			st.append([])
			op.append("[")
		elif c == "]":
			x = st.pop()
			if not st or op.pop() != "[":
				raise SyntaxError("unbalanced brackets")
			st[-1].append(("[", x))
		elif c == "{":
			st.append([])
			op.append("{")
		elif c == "}":
			x = st.pop()
			if not st or op.pop() != "{":
				raise SyntaxError("unbalanced brackets")
			st[-1].append(("{", x))
		elif c in "<>^v!":
			st[-1].append(c)
		elif c in "#$,'\"":
			st[-1].append([c, None, None])
		elif c == "@":
			if st[-1] and \
			   isinstance(st[-1][-1], list) and \
			   st[-1][-1][1] is None and \
			   st[-1][-1][2] is None:
				st[-1][-1][1] = c
			else:
				raise SyntaxError("unexpected %c" % c)
		elif c in "&.;:":
			if st[-1] and \
			   isinstance(st[-1][-1], list) and \
			   st[-1][-1][2] is None:
				st[-1][-1][2] = c
			else:
				raise SyntaxError("unexpected %c" % c)
	x = st.pop()
	if st:
		raise SyntaxError("unbalanced brackets")
	return x

class Staeck:
	def __init__(self, input):
		self.stack = []
		self.input = input
		self.sp = 0
		self.ip = 0
		self.outqueue = []
		self.inqueue = []
	def read(self):
		if not self.inqueue:
			c = sys.stdin.read(1)
			if not c:
				return None
			c = ord(c)
			for i in range(8):
				self.inqueue.append((c >> i) & 1)
		return self.inqueue.pop(0)
	def write(self, n):
		self.outqueue.append(n)
		if len(self.outqueue) == 8:
			c = 0
			for i, x in enumerate(self.outqueue):
				c |= x << i
			sys.stdout.write(chr(c))
			self.outqueue = []
	def run(self, ast):
		for x in ast:
			if isinstance(x, list):
				if x[0] == "#":
					if not self.input:
						return False
					n = self.input[self.ip]
				elif x[0] == "$":
					if not self.stack:
						return False
					n = self.stack[self.sp]
				elif x[0] == ",":
					n = self.read()
					if n is None:
						return False
				elif x[0] == "'":
					n = 0
				elif x[0] == "\"":
					n = 1
				if x[1] == "@":
					n ^= 1
				if x[2] == "&":
					self.stack.append(n)
				elif x[2] == ".":
					self.write(n)
				elif x[2] == ";":
					if n == 0:
						return False
				elif x[2] == ":":
					if n == 1:
						return False
			elif isinstance(x, tuple):
				if x[0] == "[":
					self.run(x[1])
				elif x[0] == "{":
					while self.run(x[1]):
						pass
			elif x == "<":
				if not self.input or \
				   self.ip == 0:
					return False
				self.ip -= 1
			elif x == ">":
				if not self.input or \
				   self.ip == len(self.input) - 1:
					return False
				self.ip += 1
			elif x == "^":
				if not self.stack or \
				   self.sp == len(self.stack) - 1:
					return False
				self.sp += 1
			elif x == "v":
				if not self.stack or \
				   self.sp == 0:
					return False
				self.sp -= 1
			elif x == "!":
				return False
		return True

if __name__ == "__main__":
	if len(sys.argv) < 3 or \
	   len(sys.argv) > 4 or \
	   (len(sys.argv) == 4 and sys.argv[1] != "-f"):
		print("Usage: %s [-f] CODE INPUT" % sys.argv[0], file=sys.stderr)
		exit(1)
	if sys.argv[1] == "-f":
		with open(sys.argv[2]) as f:
			code = f.read()
		inp = sys.argv[3]
	else:
		code = sys.argv[1]
		inp = sys.argv[2]
	inp = list(map(lambda x: int(x) % 2, inp))
	st = Staeck(inp)
	r = st.run(parse(code))
	if r:
		exit(0)
	exit(1)