Apsw

Apsw (/ˈɛɪ̯psʊ/) is a reversible esoteric programming language created by User:TuxCrafting based on swapping bits, where the number of set bits in the memory is finite and immutable, and determined at the start of execution.
== Structure ==
An Apsw program is made of instructions on separate lines. The instructions are:
* set A, B, ..., C — Set the bits at the specified addresses. There can only be one such instruction, and it must be at the start of the program.
* loop N — If the bit at N is 0, go to just after the matching endloop.
* endloop — If the bit at N (of the matching loop) is 0, go to just after the matching loop.
* swap A, B — Swap the bit at A with the bit at B.
* base A — Add A to the base address.
* out A, B, ..., C — Write the specified character codes to the standard output.
Comments start with #. Unknown or malformed instructions are an error.
== Memory ==
The memory of Apsw is an unbounded array of bits. Addresses are relative to the base of the memory, which can be set by the base instruction.
== Computational class ==
Apsw is Turing complete by reduction from GARBF (which is Turing complete).
=== GARBF ===
GARBF (Generalized Absolute Reversible Brainfuck) is a language very similar to Reversible Brainfuck, where instead of having an unbounded tape there are N unbounded cells (labelled 0…N-1).
It has a straightforward conversion to Apsw:
The Apsw program starts with set 0, 1, ..., N*2-1, which initializes the cells to 0.
Then, the commands are converted:
'C+' (increment cell C) becomes:
base C
loop 0
base N
endloop
swap 0, N
base N
loop 0
base -N
endloop
base -C
'C-' (decrement cell C; decrementing 0 is undefined) becomes:
base C
loop 0
base N
endloop
swap 0, -N
base -N
loop 0
base -N
endloop
base -C
'C[' (jump to just after matching ']' if cell C is not zero) becomes:
loop N+C
']' (jump to just after matching 'C[' if cell C is not zero) becomes:
endloop
== Examples ==
=== Hello, world! ===
out 72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33, 10
=== Infinite loop ===
This constantly rebases the memory leftwards, and hence eventually consumes unbounded memory. This is necessary since Apsw is reversible, and cannot enter a side-effect-less infinite loop.
set 0
loop 0
base -1
endloop
== Interpreter ==
# Apsw interpreter
# No rights reserved
import re
import sys
INSTR_RE = re.compile(r"(\w+)((?:\s+[-+]?\d+(?:\s*,\s*[-+]?\d+)*)?)")
class Apsw:
	def __init__(self):
		self.mem = [0]
		self.base = 0
		self.code = []
		self.has_set = False
		self.ip = 0
		self.loop_stack = []
	def parse(self, lines):
		for l in lines:
			l = l.strip()
			if not l or l[0] == "#":
				continue
			m = INSTR_RE.match(l)
			if not m:
				raise SyntaxError("could not parse '%s'" % l)
			cmd = m.group(1)
			if m.group(2):
				args = list(map(lambda x: int(x.strip()),
				 m.group(2).split(",")))
			else:
				args = []
			self.parse_instr(cmd, args)
	def parse_instr(self, cmd, args):
		if cmd == "set":
			if self.has_set or self.code:
				raise SyntaxError("set can only be present" + \
				 " once, at the beginning" + \
				 " of the code")
			self.has_set = True
			for x in args:
				self.set(x, 1)
		elif cmd == "loop":
			if len(args) != 1:
				raise SyntaxError("loop expects 1 argument")
			self.code.append(None)
			self.loop_stack.append((args[0], len(self.code)))
		elif cmd == "endloop":
			if len(args) != 0:
				raise SyntaxError("endloop expects 0 arguments")
			if not self.loop_stack:
				raise SyntaxError("endloop without" + \
				 " matching loop")
			n, i = self.loop_stack.pop()
			self.code.append(("jz", n, i))
			self.code[i - 1] = ("jz", n, len(self.code))
		elif cmd == "swap":
			if len(args) != 2:
				raise SyntaxError("swap expects 2 arguments")
			self.code.append(("swap", *args))
		elif cmd == "base":
			if len(args) != 1:
				raise SyntaxError("base expects 1 argument")
			self.code.append(("base", args[0]))
		elif cmd == "out":
			s = ""
			for x in args:
				if x < 0:
					raise SyntaxError("character codes" + \
					 "must be positive")
				s += chr(x)
			self.code.append(("out", s))
	def finalize_parse(self):
		if self.loop_stack:
			raise SyntaxError("loop without matching endloop")
	def grow(self, i):
		i += self.base
		if i < 0:
			for _ in range(-i):
				self.mem.insert(0, 0)
			self.base -= i
		elif i >= len(self.mem):
			for _ in range(i - len(self.mem) + 1):
				self.mem.append(0)
	def get(self, i):
		self.grow(i)
		return self.mem[i + self.base]
	def set(self, i, v):
		self.grow(i)
		self.mem[i + self.base] = v
	def swap(self, i, j):
		x = self.get(i)
		y = self.get(j)
		self.set(i, y)
		self.set(j, x)
	def step(self):
		cmd, *args = self.code[self.ip]
		self.ip += 1
		if cmd == "jz":
			n, i = args
			if self.get(n) == 0:
				self.ip = i
		elif cmd == "swap":
			a, b = args
			self.swap(a, b)
		elif cmd == "base":
			n, = args
			self.grow(n)
			self.base += n
		elif cmd == "out":
			s, = args
			print(s, end="")
	def run(self):
		while self.ip < len(self.code):
			self.step()
	def dump(self):
		i = j = -1
		for k, x in enumerate(self.mem):
			if i == -1 and x:
				i = k
			if x:
				j = k
		if i == j:
			print("|0|")
		else:
			l = []
			for k in range(i, j + 1):
				if k == self.base:
					l.append("|%d|" % self.mem[k])
				else:
					l.append(str(self.mem[k]))
			print(" ".join(l))
if __name__ == "__main__":
	if len(sys.argv) < 2 or \
	 (sys.argv[1] == "-d" and len(sys.argv) != 3) or \
	 (sys.argv[1] != "-d" and len(sys.argv) != 2):
		print("Usage: %s [-d] FILE" % sys.argv[0])
		exit(1)
	debug = False
	if sys.argv[1] == "-d":
		debug = True
		filename = sys.argv[2]
	else:
		filename = sys.argv[1]
	apsw = Apsw()
	with open(filename) as f:
		apsw.parse(f)
	apsw.finalize_parse()
	apsw.run()
	if debug:
		apsw.dump()
Category:2019 Category:Implemented Category:Output only Category:Reversible computing Category:Turing complete Category:Turing tarpits Category:Languages