Archway

From Esolang
Jump to: navigation, search

Archway is an esoteric programming language devised by Scott Feeney in 2005 to disprove a strong claim of the wire-crossing problem; that is, to prove that a universal Turing machine's state diagram need not allow for the possibility of nonplanar graphs. This goal was inspired by Beturing. Nothing was actually disproven by Archway, however, because the method given for translating Brainfuck programs to Archway was invalid.

A later revision, Archway2, made the language useful while fulfilling its intended purpose.

The language itself is a two-dimensional Brainfuck derivative somewhat resemblant of SNUSP. Archway2 takes further inspiration from the turning semantics of 2L.

Operation and commands

There is a memory tape like that of Brainfuck, composed of byte cells initialized to 0, unbounded on the right. At program start, the memory tape is pointing to the leftmost cell. The code pointer starts in the lower left of the program going right.

The original commands are as follows:

< LEFT  Move the memory pointer to the left
> RIGHT Move the memory pointer to the right
+ INCR  Increment current memory cell
- DECR  Decrement current memory cell
, READ  Read a byte into current memory cell
. WRITE Write a byte from current memory cell
\ LURD  If current memory cell is 0, ignore
        Otherwise, if going
            left, go up
            up, go left
            right, go down
            down, go right
/ RULD  If current memory cell is 0, ignore
        Otherwise, if going
            right, go up
            up, go right
            left, go down
            down, go left

As in most Brainfuck implementations, the INCR and DECR instructions wrap around. READ sets the cell to 0 on end of file.

Any other characters carry out the NOOP instruction (see nop), which does nothing. Execution ends when the instruction pointer tries to move outside of code space.

Note that all lines are extended to the length of the maximum line by padding them with characters to carry out NOOP instructions on the end. This makes the code space rectangular.

Changes in Archway2

In Archway2, the LURD and RULD commands are implemented in a slightly different way. Before executing a command in a given cell, the code pointer first looks forward to see if there is a cell in front of it. If so, and if this cell is a LURD and RULD command, and if the current memory cell will be nonzero after the command in the current cell executes, the code pointer changes its direction as it would in the original Archway. Then it executes the command in the current cell and continues as normal. In this way, LURD and RULD are not really commands, but rather stoppers; if a code cell containing a / or \ is actually moved into, it is treated as a NOOP.

This behavior can be implemented simply by making the LURD and RULD commands from the original Archway move the code pointer back one space before changing its direction. However, it is specified as above so that no wire-crossing is necessary for looping.

Example

/.\
\,/

The cat program in Archway, and probably the only useful program that can be written in the original Archway.

   \
// .
  , /
+/\


The cat program in Archway2.

Converting Brainfuck to Archway2

Let a, b, c, d, and e be sequences of the Brainfuck commands excluding [ and ], represented horizontally. Then the Brainfuck program

a[bc]d

becomes

     \
  //
/   bc/+\
 -a/\ + -d
+/     \

As a more complicated example,

a[b[c]d]e

becomes

            \
   /
        \
     //
  /     c/+\
/    b/\ + -d/+\
 -a/\     \  + -e
+/            \

Notice the lack of wire-crossings. It is possible to cross wires in Archway2, but not necessary.

See also

External resources