Suich

From Esolang
Jump to: navigation, search

Suich is an esoteric programming language created by User:TuxCrafting.

Introduction

A Suich program is made of one or more lines. The lines are all padded with nops to the length of the longest line.

There is a line pointer, which points to the line to be run, and a command pointer, which points to a command in the line selected by the line pointer. The pointers are respectively modulo the number of lines and modulo the length of lines. They are both incremented at the end of each execution step.

Each line has a separate counter, able to store unbounded positive integers. This is the only form of storage available.

Commands

Undefined commands are errors.

Command Description
i Increment the line's counter.
d If the line's counter is 0, increment the command pointer; else, decrement the line's counter.
h Halt the program.
I Input an Unicode character and set the line's counter to its codepoint.
O Output an Unicode character with the codepoint in the line's counter, or increment the command counter on EOF. Undefined codepoints are undefined behavior.
Space Do nothing.

Computational class

Suich is Turing-complete because programs in The Waterfall Model can be compiled into it.

The first step in the compilation is to note that The Waterfall Model can be compiled into a counter machine that uses a linear sequence of commands of the following forms (placed into an implicit infinite loop):

  • if counter is 0, skip all commands to the next "end if" command, otherwise decrement it;
  • increment counter
  • end if

In this construction, if…end-if sequences are not allowed to nest.

To do this compilation, we simply write an if-zero-or-decrement on the first counter, followed by increments that increment each counter by the amount specified in the first waterclock's zeroing trigger, followed by an end-if, followed by an if-zero-or-decrement on the second counter, followed by increments for the second waterclock's zeroing trigger, followed by an end-if, and so on. The net result of one iteration of the entire program will be to decrement every counter once, and if a counter became -1 in this process, to increment all counters according to the zeroing trigger of that counter. The resulting counter machine thus implements The Waterfall Model, with the counter values off-by-1 (i.e. a counter of x in The Waterfall Model is represented as x-1 in the counter machine).

This counter machine can then be compiled into Suich via taking a program with one row per counter, and one additional row for a counter that's always 0, and a sufficiently large number of columns. The program is written along a wrapping diagonal of the rectangle (the direction in which Suich control flow naturally runs), with the exception that the diagonal moves one space to the right (i.e. half a space to the up-right) with every end-if command; the width of the rectangle is chosen so that this single line of program execution lines up with itself, forming a closed loop, after crossing the rightmost edge of the program. The if-zero-or-decrement command is then implemented via adding no-ops until the program flow reaches the row representing the appropriate counter and doing d; increment pads with no-ops in the same way, but does i; end-if does d on the line representing the additional row. It can therefore be seen that upon running an if-zero-or-decrement with the counter at 0, the Suich control flow will get knocked one space to the right, and only line up with the line on which the program is written when an end-if command is run. Thus, increment, decrement, and end-if all have the desired semantics.

One remaining issue is that The Waterfall Model can initialise waterclocks to arbitrary values, but in Suich, all counters start at 0 (the equivalent of 1 in The Waterfall Model). Decrementing two waterclocks to 0 simultaneously is undefined behaviour in The Waterfall Model; however, with this construction, the behaviour is to run the zeroing trigger of the first waterclock first, and then to run the zeroing triggers of the other waterclocks only if their values have not been increased from 0 in the process. Therefore, it's possible to implement the intialization via adding an extra waterclock at the start of the program and using its zeroing trigger to specify the initial values of the counters, and ensuring that its value never reaches 0 during program execution (which can be done via making its self-reset value higher than the initial value of any other counter, and having the zeroing triggers for every other waterclock increase it by a sufficiently large amount).

Similar techniques can be used to implement I/O and halting, so Suich is thus fully I/O complete, rather than just Turing-complete, placing it in the same computational class as languages like brainfuck.

Examples

Hello, world program

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiOiiiiiiiiiiiiiiiiiiiiiiiiiiiiiOiiiiiiiOOiiiOdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddOiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiOddddddddOiiiOddddddOddddddddOdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddOh

Cat program

  h
I O

Truth machine

IOO d i
  d   h

0 is the NUL character and anything else is 1.

Add two characters

I        d
 I        iO
   d   d    h d

Take two characters, add their codepoints, and print the character associated with the sum.

Looping counter

Print characters with codepoints 0,1,0,1,2,0,1,2,3,0,1,2,3,4,...

Since there is a finite number of Unicode codepoint, this may not run eternally.

d   ii
 id O
 d

Interpreter

# Suich interpreter
# No rights reserved

import sys

class Suich:
	def __init__(self):
		self.lines = []
		self.counters = []
		self.lp = self.cp = 0
		self.running = False
	def parse(self, lines):
		m = 0
		for l in lines:
			if l[-1] == "\n":
				l = l[:-1]
			self.lines.append(l)
			self.counters.append(0)
			m = max(m, len(l))
		for i in range(len(self.lines)):
			self.lines[i] += " " * (m - len(self.lines[i]))
		self.lines_m = m
	def step(self):
		c = self.lines[self.lp][self.cp]
		if c == "i":
			self.counters[self.lp] += 1
		elif c == "d":
			if not self.counters[self.lp]:
				self.cp += 1
			else:
				self.counters[self.lp] -= 1
		elif c == "h":
			self.running = False
		elif c == "I":
			s = sys.stdin.read(1)
			if s:
				self.counters[self.lp] = ord(s)
			else:
				self.cp += 1
		elif c == "O":
			sys.stdout.write(chr(self.counters[self.lp]))
		elif c == " ":
			pass
		else:
			raise SyntaxError("undefined command '%c'" % c)
		self.lp = (self.lp + 1) % len(self.lines)
		self.cp = (self.cp + 1) % self.lines_m
	def run(self):
		self.running = True
		while self.running:
			self.step()

if __name__ == "__main__":
	if len(sys.argv) < 2 or len(sys.argv) > 3 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], file=sys.stderr)
		exit(1)
	debug = sys.argv[1] == "-d"
	if debug:
		filename = sys.argv[2]
	else:
		filename = sys.argv[1]
	suich = Suich()
	with open(filename) as f:
		suich.parse(f)
	suich.run()
	if debug:
		print("counters: %s" % " ".join(map(str, suich.counters)),
		      file=sys.stderr)