Knight Shuffling Tower

Knight Shuffling Tower is an esoteric programming language created by User:Koen in 2012. It is based on a special data structure which is almost, but not quite, a queue.

The Tower and the Knights

The only data structure in Knight Shuffling Tower is a tower surrounded by a ring of nine knights. Each knight is a variable that can hold an integer number, a character, or a boolean. The tower is First In, First out. It can be pushed to; however there is no explicit pop function. Whenever a knight is holding 0, it immediately receives the next value in the tower. If at any time a knight is holding 0 and cannot receive a new value because the tower is empty, the program halts. Immediately after a knight has received a new value from the tower, knights change seats: the values held by all of the nine knights are shuffled. Knights can be referred to as "one", "two"... "nine".

Initially, the tower is empty and each knight holds a number between 1 and 9. Those values are dispatched to the knights at random; that is, all numbers from 1 to 9 are assigned to a knight, but the programmer doesn't know which knight holds which value. There are no constants in Knight Shuffling Tower: for instance, "one <- 42" would raise an error.

Functions

A Knight Shuffling Tower program is a succession of functions applied to their arguments. Functions can either return a result, which means they can be used as arguments for other functions, or manipulate the tower or the knights. Parentheses can be used wherever needed. Whitespaces (spaces, tabs and newlines) have no effect other than separating keywords. Comments use the same syntax as in Ocaml: text between (* and *) is ignored, and nested comments are handled correctly. Knight Shuffling Tower is always case insensitive.

In the following lists of functions, "x" and "y" are knights' names and "v" and "w" are values. Please note that these lists may not exhaustive, as the language isn't finished yet.

Functions returning a result

Function	Description
x	The value held by x
v + w	The sum of v and w.
v - w	The difference v minus w.
v * w	The product of v and w.
v / w	Integer division. Note that +, -, *, / can be combined with the usual precedence of operations.
- v	Unary negation. Whitespaces have no meaning; "v -w" is equivalent to "v - w".
max v w	The maximum of v and w. Booleans are considered as 0 or 1 and characters as their ASCII value, but returned with their correct type if the maximum. If v and w are equal, the returned value has the same type as v.
min v w	The minimum of v and w. Similar to max.
bool v	The boolean false if v is either the boolean false or the number 0, the boolean true otherwise.
char v	The character which ASCII value is the number v (modulo 256). Equal to v if v is already a character. Unspecified if v is a boolean.
not v	False if v is the boolean true, true otherwise.
v = w	True if v and w are equal, false otherwise. Always false if v and w have different types.
true	Equivalent to x = x. True and false are the only constants in Knight Shuffling Tower.
false	Equivalent to not true.
next x	The knight two if x is one, three if x is two, etc.; one if x is nine.
prev x	The knight y such that next y is x.

Functions affecting the tower or the knights

Function	Description
push v	Push the value v to the tower.
x <- v	Replace the value hold by x with the value v. Note that if v is the number 0, x will receive a new value from the tower and the knights will change seats.
print x	Print the value held by x, assign a new value from the tower to x, and knights change seats.
inputc	Push a character read from standard input to the tower. Push false in the event of end of file.
inputn	Read a line from standard input, convert it to a number and push it. Raise an error if the line read cannot be converted into a number.

Conditionals and loops

Function	Description
while v do	Start a while loop. Behaviour unspecified if v is not a boolean.
for list as s do	Start a loop to be iterated for each knight specified in place of 'list'. The current knight can be referred as s in the loop, where s is a string of characters (A-B, a-b, 0-9, space and _ only, no keywords, and remember it's case insensitive). The list of knights must be of the form "x y z". "Three..six" is equivalent to "three four five six. "All" is equivalent to "one..nine". "list1 but list2" is equivalent to the list list1 without the knights in list2. The loop is applied in the order specified by the list - that is, for one two do is not necessarily equivalent to for two one do.
done	End the current loop.

Example programs

Cat program

while bool one do
  inputc
  print one
done

This program prints characters out of the standard input. The characters are printed in an approximative order, some of them are lost and a few numbers between 1 and 9 are inserted randomly, but on the plus side, end of file is handled correctly.

Truth-machine

for two three four five six seven eight nine as knight do
  one <- one + knight
  knight <- knight / knight
done

(* one is 45, two..nine are all 1 *)

one <- char (one + two + two + two)

(* one is '0' *)

inputc

three <- three / three
for four..nine as knight do
  knight <- (prev knight) + (knight / knight)
done

two <- two - two

(* something is '0', something is '0' or '1', others are numbers between 1 and 9 *)

for all as k do
  for all but k as j do
    while (k = j) do (* this condition is met only if k = '0' *)
      print k
      (* k is reset but tower is empty, so program halts *)
    done
  done
done

(* something is '0', something is '1', others are numbers under 9 *)

for all but one as knight do
  knight <- max (prev knight) knight
done
for all but nine as knight do
  knight <- nine
done

(* all knights are '1' *)

while true do
  push one
  one <- char one
  print one
done

Other thoughts

The language is not finished yet. If anyone has any idea, please let me know.

• As can be seen in the Truth-machine example, it is possible to make the number 1 using "x / x" and 0 using "x - x". Actually, any number can be made this way, which make the "no constant" thing moot. Maybe should forbid to use the same knight twice in the same expression, or something.
• The number of knights might be reduced, because 9 is a lot. Maybe 3 knights would be good. Or maybe programs should begin by declaring a number of knights.
• Instead of being shuffled every now and then, knights could all have the same name; they would all be called knight and whenever the program refers to knight, one knight is chosen at random. But I guess that would be a different language.

External resources

• Interpreter in C.