DigFill

DigFill is an esoteric programming language by Abraham Karplus, based on the idea that memory is only accessible once it has been dug out.

Memory

The memory consists of an unbounded two-dimensional array of bits, all initialized to 0 except one bit, set to 1, which is where the memory pointer (hereafter called the "miner") begins. The miner can change orthogonally adjacent cells from 0 to 1 or vice-versa, but may only move through cells that are set to 1. The memory may also contain inscriptions (discussed later).

Commands

There are 10 different commands in DigFill. All except Nop and End are followed by one argument, a direction, which may be any of nsew (for north, south, east, and west). The commands are

!

Nop Does nothing.

@

Dig Sets the cell next to the miner in the given direction to 1 and removes any inscription in that cell.

#

Fill Sets the cell next to the miner in the given direction to 0.

$

Step Moves the miner one cell in the given direction, if that cell is a 1.

%

Walk Steps as many times as possible in the given direction.

^

Input See section on I/O.

&

Output See section on I/O.

*

End Terminates program execution.

(code) or +

Inscribe See section on inscriptions.

~

Execute See section on inscriptions.

Comments are enclosed between underbars (non-nesting). Whitespace is ignored.

I/O

DigFill uses UTF-8 character encoding for input and output. Since it has only bitwise memory, I/O is done one bit at a time, starting with the most significant bit in the first byte. End of file is indicated by a 0xFF byte, which can never appear in normal UTF-8 text. The Input command is effectively a Dig command if the next bit is 1 and a Fill command if it is zero. The Output command puts a bit in the output buffer, depending on the value of the adjacent cell in the direction given.

Inscriptions

Inscriptions are the only method of flow control in DigFill. They are effectively blocks of code written onto specific cells in memory. The Inscribe command will put the code between parentheses onto the cell adjacent in the specified direction, if that cell is a 0. Attempting to inscribe on a cell with a 1 does nothing. The plus-sign form of the Inscribe command inscribes the containing block (or the entire program if used outside a parenthesized block). The inscribed code block may include any commands, including other Inscribe commands. The Execute command will execute the code block adjacent to the miner in the given direction, if it exists. Nothing happens if no inscription is there. To remove an inscription, simply dig out the block and fill it in again.

Examples

Hello, World!

@n _Clear a space to output 1 bits_
&s&n&s&s&n&s&s&s _H_
&s&n&n&s&s&n&s&n _e_
&s&n&n&s&n&n&s&s _l_
&s&n&n&s&n&n&s&s _l_
&s&n&n&s&n&n&n&n _o_
&s&s&n&s&n&n&s&s _,_
&s&s&n&s&s&s&s&s _ _
&s&n&s&n&s&n&n&n _W_
&s&n&n&s&n&n&n&n _o_
&s&n&n&n&s&s&n&s _r_
&s&n&n&s&n&n&s&s _l_
&s&n&n&s&s&n&s&s _d_
&s&s&n&s&s&s&s&n _!_

Cat

@n$n@n$n@n$n@n$n@n$n@n$n@n$n _Create an 8-square hallway_
@e$e(*)n$w _Inscribe an end to the program_
(^e$s^e$s^e$s^e$s^e$s^e$s^e$s^e _Input a byte_
  $e%n~n _Exit if EOF_
  $w%n _Go back to start of byte_
  &e$s&e$s&e$s&e$s&e$s&e$s&e$s&e _Output the byte_
  %n~w _Repeat_
)w~w _Inscribe and execute the program body_

Turing-completeness

DigFill is Turing-complete by reduction from the :!^() subset of Underload. The stack needs to be set up with

(*)n(%w@n#n$e#w$e#w%s)e@s$s(*)e@s$s(*)e

and then the commands can be translated as

:            ~e@s$s
!            $n#s%e~e
^            $n#s%n~n
(<code>)     %n@w$w@w$w(%s%e~e<code>)n@s$s

Reduction courtesy of Ørjan Johansen.

Implementations

An implementation (including a shoddy TUI debugger) by User:Challenger5 is available on GitHub.