Kayak
Kayak is a reversible esoteric programming language designed and implemented in 2002 by Ben Rudiak-Gould. Any procedure can be run forwards or backwards. Running a procedure backwards is equivalent to reversing its characters.
All many-to-one operations, like sorting, must be implemented by moving the unneeded information into a bit bucket supplied by the system.
Language details
Kayak has two data types: infinite stacks of bits (of which programs can have an arbitrary number) and single-bit temporary registers (only one of which is accessible within a given scope). There are nine symbols recognized in Kayak:
< … > |
Encloses a comment. May be nested. |
[ … ] |
Conditionally executes the enclosed code. |
( … ) |
Encloses the arguments to a procedure. |
{ … } |
Encloses the body of a procedure. |
| |
Complements the value in the temporary register. |
An identifier can be any string that does not include the above symbols and does not include whitespace.
Procedures
Programs are specified as lists of procedures. A procedure definition takes the form
name1(arg1|arg2) { body } (arg3|arg4)name2
Multiple procedures can have the same name1 as long as they have a different name2, or vice versa. Both names are always specified when calling a procedure.
A procedure can take any number of arguments, named both at the start of the definition and at the end. When the procedure starts, the argument names at the entry point (which can be either the beginning or the end) are bound to the arguments supplied, and when the procedure ends, the variables listed at the exit point are updated. The following procedure, for example, swaps its arguments:
swap(a|b) {} (b|a)paws
The commands are:
| Command | Description |
|---|---|
| identifier | If there is no value in the temporary register, pop the top value off the local variable identifier, placing it in the temporary register. If there is a value in the temporary register, remove it and push it onto the local variable identifier. Example: foo bar moves one bit from stack foo to stack bar.
|
|
|
Complement the value in the temporary register. This cannot be used when the temporary register has no value. (Whether the temporary register has a value can be checked at compile time.) |
[ code ]
|
If the temporary register has a 1 in it, run the code; otherwise, skip it. The code is given its own temporary register, initially empty. This cannot be used when the temporary register is empty. In addition, code must result in an empty temporary register when the structure is exited. |
name1(arg1|arg2)name2
|
Runs the procedure with the names name1 and name2, passing it the arguments arg1 and arg2. The arguments are local variables, and they should be modified by the procedure called, since this is the only way for a procedure to have any effect. Recursive calls are legal and are the only looping mechanism. The procedure name can be written in reverse to call the procedure backwards, relative to the current execution direction. Procedures with palindromic names cannot be called in reverse, so it's a good idea to only give palindromic names to self-inverse procedures. |
All local variables in a procedure, except those passed in by arguments, are initialized to contain infinite zeroes. They should also contain only zeroes when the procedure finishes.
The main procedure
The main procedure, which has an empty name, is the procedure run when the program starts. It can be defined to take either one or two arguments. If it takes one argument, the argument is the program's input on entry and the program's output on exit. If it takes two arguments, the argument closest to the procedure body on each side is input or output, and the other argument is the bit bucket. The bit bucket contains unpredictable bits on entry and may contain anything on exit.
Each byte of input or output is encoded as nine bits. The bit closest to the top of the stack is 1, indicating that there is, in fact, another byte of input or output on the stack; the next eight bits are the byte, with the least significant bit at the top.
Computational class
Kayak is Turing-complete, even without the use of a bit bucket, because it is possible to compile Delta Relay with one halt counter into it. (The restriction to one halt counter trivially does not restrict Turing-completeness: it is easy to write a program so that it is known which halt counter the program will terminate at (if it terminates), and the other halt counters (which are known to be unreachable) can be made into non-halt counters by giving them a negative influence on an arbitrary other counter, which does nothing because those counters are never selected as control counters and thus their influence doesn't matter.)
The main loop of the implementation is done using a function step(a|b|c|d|…)pets, where the arguments are the Delta Relay counters, encoded using a number of 1s equal to their value followed by infinite 0s. The function works as follows:
- The function uses a local variable
z, whose value is always all-zeroes, in order to produce 0s (and, by complementing it, 1s) to push onto the counters, and in order to push known values onto (known 1s are complemented into a 0 before pushing them). - Each counter is tested for zeroness in sequence, e.g. a zero test of
aisa|[…]|a. The code inside the zero test implements the counter's influence: positively influenced counters are incremented the appropriate number of times using, e.g.,z|b, and negatively influenced counters are decremented using, e.g.,c|z. (In Delta Relay, negatively influencing a counter below 0 is undefined behaviour, so the compilation may assume that the values pushed ontozwill always be 0.) Testing the counters in sequence ensures that if two counters are both zero, the one that just zeroed will not be tested until after the counter that was newly zeroed is tested. - There is a recursive call conditional on the behaviour of the stop counter. Say the stop counter is
h: then the recursive call ish[z|h step(a|b|c|d|…)pets h|z]h. - Finally, the function contains the inverse of the code that appears before the recursive call, reverting all the changes to the counters.
As such, step(…)pets enters an infinite loop if the Delta Relay program does not halt, and is a no-op (restoring the value of every counter to its original value) if the Delta Relay program halts.
To complete the program, create a main procedure that initialises the counters (which are local variables) to the values specified in the Delta Relay program by pop-invert-push from a local variable, calls step(…)pets, and then deinitialises the counters back to 0 via pop-invert-push onto a local variable (thus setting all the local variables back to 0). As such, just like step(…)pets, the main procedure halts and returns its input if the Delta Relay program halts, or enters an infinite loop if the Delta Relay program does not halt.