Virage

From Esolang
Jump to: navigation, search

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)