Virage

Virage (meaning "turn" in French) is an esoteric programming language created by User:TuxCrafting where the source code is a graph.
= Structure =
A Virage program is an undirected graph where vertices have integer coordinates and edges must be connected to an horizontally, vertically or diagonally adjacent vertex. Edges cannot overlap.
Commands are selected based on the angle between connected edges. Execution starts at the vertex who is connected to the edge of the code. It is an error to have more than one such vertex.
= Representation =
Code is represented in text form as lines of blocks of 3x3 characters. If the center character of a block contains *, it is considered to be a vertex; else, its contents are ignored.
Each border character of a 3x3 block describes a "half-edge" centered at that vertex. The half-edge exists if the character representing it is not a space.
Edges must be complete, with the exception of vertices which connect to the edge of the code.
= Memory =
Virage has two unbounded stacks of bits, the main stack (which is used by most operations), and the secondary stack (which can have data moved to and from the main stack). Popping from an empty stack is an error.
= Commands =
"Top" and "straight" represents the direction the execution is currently going.
Connected edges 	Name 	Description
None 	HALT 	Stop execution.
One straight 	NOP 	Do nothing. Go straight.
One right 	1 	Push a 1 on the main stack. Go right.
One left 	0 	Push a 0 on the main stack. Go left.
One bottom-right 	DROP 	Pop and discard a bit from the main stack. Go bottom-right.
One bottom-left 	DUP 	Duplicate the top of the main stack. Go bottom-left.
One top-right 	M>S	Pop a bit from the main stack and push it on the secondary stack. Go top-right.
One top-left 	S>M	Pop a bit from the secondary stack and push it on the main stack. Go top-left.
One straight and one right 	IN 	Try to input 8 bits from the input (least-significant on top). On EOF, go right; else, go straight.
One straight and one left 	OUT 	Pop 8 bits from the main stack and output them (least-significant on top). Go straight.
One right and one left 	IF 	Pop a bit from the main stack. If 0, go left; else, go right.
One bottom-right and one top-left 	IFM 	If the main stack is empty, go top-left; else, go bottom-right.
One top-right and one bottom-left 	IFS 	If the secondary stack is empty, go bottom-left; else, go top-right.
One straight, one left and one right	CROSS 	Crossing. Go straight.
One left and one top-right 	JOIN1 	Join. Go top-right.
One right and one top-left 	JOIN2 	Join. Go top-left.
Unrecognized commands are errors.
= Computational class =
Virage is Turing-complete by being able to have F2 compiled into it.
== F2 to Virage conversion ==
Simply concatenate the building blocks vertically, with no empty lines between.
Start with:
 |
 *--*
 |
 |
 * *
 |\ |
 | \|
 * *
 |
For +:
 |
 *--*--*
 | |
 | |
 *--* + *--*
 \ /
 \ /
 *
 |
For >:
 |
 * *
 | / \
 |/ \
 * *
 / \
 / \
 * *
 | \
 | \
 *--* * *--*
 \ / |
 \ / |
 * *
 | |
 | > |
 * *
 | |
 | |
 * *--* *--*
 \ / /
 \ / /
 * *
 | /
 | /
 *--* *
 \ /
 \ /
 *
 |
For <:
 |
 * *
 \ /
 \ /
 *
 |
 |
 *--*
 \
 \
 *
 \
 \
 * *
 | \
 | \
 * *--*--*--*
 \ / |
 \ / |
 * < * *
 | / \ |
 | / \|
 *--* * *
 \ /
 \ /
 *
 |
For [:
 |
 * * *
 /| | /
 / | | /
 *--*--*--*--*--*--*--*--*
 | | \
 | | \
 * * * * *--*
 | | / \ /| | |
 | |/ \ / | | |
 * * * * * * * *
 | | \ / | |
 | | \ / | |
 *--* *--*--* * * *
 \ / \ | / \
 \ / \ | / \
 * * * *--*--* *
 | | | / | |
 | | | / | |
 *--*--* * * * *
 / \ / |
 / \ / |
 * * *
 \ | |
 \ [ | |
 * * *
 \ | |
 \ | |
 * *--* *
 \ / |
 \ / |
 * * *
 \ / \ |
 \ / \ |
 * * *
 | \ |
 | \ |
 *--* * *
 \ \ |
 \ \ |
 * * * *
 \ / \ / \
 \ / \ / \
 * * * *
 \ | / \
 \ | / \
 *--*--*--*--* *
 / | | \
 / | | \
 *--* * * * *
 | | | \
 | | | \
 * * * *--*--*
 | | \ /
 | | \ /
 * * *
 / \ ret | skp | body
 / \ | |
 * *--* * *
 | | |
Then everything in the body, NOT including the terminating ],
must have each line starting with:
 | | ...
Or, if the line is on the center of 3x3 blocks:
 * * ...
It is used to transport the "ret" and "skp" lines of the matching '['.
For ]:
 | | |
 * * *--*
 / \ | /
 / \ | /
 * *--*--*--*
 | | \
 | | \
 * *--* *
 /
 ] /
 * *
 \ /
 \ /
 *
 |
Finally, end with:
 |
 *
= Examples =
== Cat ==
 |
 * * *
 \ | |
 \ | |
 *--*--*--* *
 / | \ /
 / | \ /
 *--* * *
 | |
 | |
 * meow~ *--*
 / \ /
 / \ /
 * *--*--*--*
 | \
 | \
 * *
==Truth-machine==
 *--*--*
 | | )
 | | \ U T H
-*--*--*
 | | |
 | | |
 * * *--* 
 /
 /
 *--*
 | \
 | \
 *--* *
 | \ 
 | \ 
 *--* * * 
 | | \ 
 | | \ 
 * *--*--*--*
 | | \
 | | CHINE \
 *--* *
= Interpreter =
# Virage interpreter
# No rights reserved
import sys
# set this to True for (verbose) debug info
DEBUG = False
def dprint(*args, **kwargs):
	if DEBUG:
		print(*args, **kwargs)
N = 0
NE = 1
E = 2
SE = 3
S = 4
SW = 5
W = 6
NW = 7
DIR = [
	(-1, 0),
	(-1, 1),
	(0, 1),
	(1, 1),
	(1, 0),
	(1, -1),
	(0, -1),
	(-1, -1),
]
def go(b, n):
	return (b + n) & 7
def inv(n):
	return n ^ 4
def rot8(x, n):
	return ((x >> n) | (x << (8 - n))) & 255
def cmd(*args):
	n = 0
	for x in args:
		n |= 1 << x
	return n
class Virage:
	def __init__(self):
		self.code = []
		self.main = []
		self.secondary = []
		self.current = None
		self.direction = None
		self.mi = self.mj = 0
		self.running = False
	def parse(self, s):
		s = s.split("\n")
		if len(s) % 3 != 0:
			s += [""] * (3 - len(s) % 3)
		n = max(map(len, s))
		if n % 3 != 0:
			n += 3 - n % 3
		for i, x in enumerate(s):
			s[i] = list(s[i] + " " * (n - len(x)))
		for i in range(0, len(s), 3):
			self.code.append([])
			for j in range(0, n, 3):
				if s[i + 1][j + 1] != "*":
					self.code[-1].append(0)
					continue
				x = 0
				x |= (s[i][j + 1] != " ") << N
				x |= (s[i][j + 2] != " ") << NE
				x |= (s[i + 1][j + 2] != " ") << E
				x |= (s[i + 2][j + 2] != " ") << SE
				x |= (s[i + 2][j + 1] != " ") << S
				x |= (s[i + 2][j] != " ") << SW
				x |= (s[i + 1][j] != " ") << W
				x |= (s[i][j] != " ") << NW
				self.code[-1].append(x)
		self.mi = len(self.code)
		self.mj = len(self.code[0])
		visited = []
		for i in range(0, self.mi):
			for j in range(0, self.mj):
				if self.code[i][j]:
					self.visit(i, j, visited)
		if not self.current:
			raise SyntaxError("no starting point")
	def visit(self, i, j, visited):
		x = self.code[i][j]
		if (i, j) in visited:
			return
		visited.append((i, j))
		for n in range(8):
			if x & (1 << n):
				self.visit_half(i, j, x, n, visited)
	def visit_half(self, i, j, x, n, visited):
		di, dj = DIR[n]
		ti, tj = i + di, j + dj
		if ti < 0 or tj < 0 or \
		 ti >= self.mi or tj >= self.mj:
			if self.current is not None:
				raise SyntaxError(
					"only one starting point possible" + \
					" (%d,%d)" % (i, j))
			self.current = (i, j)
			self.direction = inv(n)
		elif (self.code[ti][tj] & (1 << inv(n))) == 0:
			raise SyntaxError("no matching half-edge (%d,%d)" % \
			 (i, j))
	def step(self):
		i, j = self.current
		dprint("(%d,%d)" % (i, j), end=" ")
		x = rot8(self.code[i][j], self.direction) & ~(1 << S)
		if x == cmd():
			dprint("HALT")
			self.running = False
		elif x == cmd(N):
			dprint("NOP")
		elif x == cmd(E):
			dprint("1")
			self.main.append(1)
			self.direction = go(self.direction, E)
		elif x == cmd(W):
			dprint("0")
			self.main.append(0)
			self.direction = go(self.direction, W)
		elif x == cmd(SE):
			dprint("DROP")
			if not self.main:
				raise IndexError("main stack empty (%d,%d)" %\
				 (i, j))
			self.main.pop()
			self.direction = go(self.direction, SE)
		elif x == cmd(SW):
			dprint("DUP")
			if not self.main:
				raise IndexError("main stack empty (%d,%d)" %\
				 (i, j))
			self.main.append(self.main[-1])
			self.direction = go(self.direction, SW)
		elif x == cmd(NE):
			dprint("M>S")
			if not self.main:
				raise IndexError("main stack empty (%d,%d)" %\
				 (i, j))
			self.secondary.append(self.main.pop())
			self.direction = go(self.direction, NE)
		elif x == cmd(NW):
			dprint("S>M")
			if not self.secondary:
				raise IndexError("secondary stack empty" + \
				 " (%d,%d)" % (i, j))
			self.main.append(self.secondary.pop())
			self.direction = go(self.direction, NW)
		elif x == cmd(N, E):
			dprint("IN")
			c = sys.stdin.buffer.read(1)
			if c:
				c = c[0]
				for n in range(8):
					d = c & (1 << (7 - n))
					self.main.append(d != 0)
			else:
				self.direction = go(self.direction, E)
		elif x == cmd(N, W):
			dprint("OUT")
			if len(self.main) < 8:
				raise IndexError("not enough elements" + \
				 " on main stack (%d,%d)" %\
				 (i, j))
			c = 0
			for n in range(8):
				c |= self.main.pop() << n
			sys.stdout.buffer.write(bytes([c]))
		elif x == cmd(E, W):
			dprint("IF")
			if not self.main:
				raise IndexError("main stack empty (%d,%d)" %\
				 (i, j))
			if self.main.pop():
				self.direction = go(self.direction, E)
			else:
				self.direction = go(self.direction, W)
		elif x == cmd(SE, NW):
			dprint("IFM")
			if self.main:
				self.direction = go(self.direction, SE)
			else:
				self.direction = go(self.direction, NW)
		elif x == cmd(NE, SW):
			dprint("IFS")
			if self.secondary:
				self.direction = go(self.direction, NE)
			else:
				self.direction = go(self.direction, SW)
		elif x == cmd(N, W, E):
			dprint("CROSS")
		elif x == cmd(W, NE):
			dprint("JOIN1")
			self.direction = go(self.direction, NE)
		elif x == cmd(E, NW):
			dprint("JOIN2")
			self.direction = go(self.direction, NW)
		else:
			c = []
			if x & (1 << N): c.append("straight")
			if x & (1 << E): c.append("right")
			if x & (1 << W): c.append("left")
			if x & (1 << SE): c.append("bottom-right")
			if x & (1 << SW): c.append("bottom-left")
			if x & (1 << NE): c.append("top-right")
			if x & (1 << NW): c.append("top-left")
			raise SyntaxError("unknown command: %s (%d,%d)" % \
			 (", ".join(c), i, j))
		di, dj = DIR[self.direction]
		self.current = (i + di, j + dj)
	def run(self):
		self.running = True
		while self.running:
			self.step()
if __name__ == "__main__":
	if len(sys.argv) != 2:
		print("usage: %s FILE" % sys.argv[0])
		exit(1)
	with open(sys.argv[1]) as f:
		s = f.read()
	v = Virage()
	v.parse(s)
	v.run()
	dprint(v.main, v.secondary)
Category:2019 Category:Low-level Category:Implemented Category:Stack-based Category:Turing complete Category:Turing tarpits Category:Two-dimensional languages Category:Languages