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()