Nopfunge
| Paradigm(s) | Imperative |
|---|---|
| Designed by | Hubert Lamontagne |
| Appeared in | 2015 |
| Dimensions | Two-dimensional |
| Computational class | Turing complete |
| Major implementations | See below |
| File extension(s) | .nop |
Nopfunge is a fungeoid designed by Hubert Lamontagne in 2015. It is a two-dimensional esoteric programming language based on a severely restricted subset of the well known Befunge language. Its goal is to show that having access to a sufficiently flexible program geometry is indeed the only thing that is needed to achieve Turing completeness. It is an example of extreme Turing tarpit, and very severely sacrifices usability in order to achieve a high degree of theoretical elegance. In other words, it manages to have an amazingly high number of NON-features.
Essentially, its only feature (which is not present in Befunge) is the ability to decide which portions of the program are present only one time and which portions are repeated infinitely, both horizontally and vertically. To compensate for this, it removes literally every other feature.
The ONLY valid commands in Nopfunge are the PC direction change commands < > v ^ and empty space (which are the same as in Befunge). This means that Nopfunge has no stack, no numbers and no conditionals: there are NO stack manipulation commands and NO commands to store or retrieve data from the program grid. There are no variables or data storage or functions or objects of any kind. The ONLY thing that ever happens in Nopfunge is PC movement.
In spite of this, Nopfunge is Turing complete.
Language overview
A Nopfunge is made out of a two-dimensional playfield which can have any size (it is not restricted to a 80x25 grid, unlike Befunge-93). As in Befunge, the instruction pointer starts in the top left corner and initially travels rightwards.
Whereas Befunge programs can be considered to be made out of an infinite grid of repeats of the same program, Nopfunge programs contain a non-repeated section on the left (before the horizontal repeat mark ; ), followed by a repeated section on the right. Likewise, on the vertical axis, there is a non-repeated section on the top (before the vertical repeat mark = ) followed by a repeated section on the bottom.
So for instance, this:
vv ;^v vv ; ====== > ;>v < ;^<
will expand to this:
vv ^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v... vv ... > >v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v... < ^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<... > >v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v... < ^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<... > >v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v... < ^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<... > >v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v... < ^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<... > >v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v... < ^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<^<... etc...
Due to this, the program has 4 sections: a single copy of the top left corner, an infinite line of copies of the top right, an infinite line of copies of the bottom left, and a squarely infinite grid of copies of the bottom right. If the PC escapes to the left or the top side of the program, the program can be considered to have halted, as there is no way for the PC to come back.
The horizontal repeat start point is set by the first instance of ; on the first line, and the vertical repeat start point is set by the first line starting with =.
Instructions
Nopfunge has the following commands:
| Cmd | Description |
|---|---|
>
|
PC direction right |
<
|
PC direction left |
^
|
PC direction up |
v
|
PC direction down |
(space)
|
Nothing happens (PC keeps moving in the same direction). |
Computational class
Using the X and Y position of the PC in a repeated grid, Nopfunge can be shown to be equivalent to a 2 counter Minsky machine. The first counter can be decremented by escaping to the left and incremented by escaping to the right, and likewise moving to the next copy above or below will decrement or increment the second counter. The current path of the PC is equivalent to the current state of the Minsky machine. It is possible to test whether the first counter is zero by having a different path in the left hand fringe of the program (only repeated vertically), and likewise the second counter can be tested for zero equality by having a different path in the top fringe (only repeated horizontally). Since the PC starts in the top left corner, this is equivalent to starting with both counters at zero.
Given a 2d board with infinite repeating sections, the same method can be used to prove Turing completeness for any sort of path walking, as long as wire crossings and joining two paths together are possible. This includes falling dominoes, Chess, directed graphs, cellular automatons, water pipe networks (with possible consequences on the solvability of the Navier-Stokes equations), Super Mario Bros, and even Snakes and Ladders.
Minsky Machine to Nopfunge translator
A tool for translating a Minsky Machine program into Nopfunge can be found here: http://yiap.nfshost.com/esoteric/nopfunge/mmtonop.py It uses a method devised by Keymaker which is unlikely to be the most efficient way.
For example, given the following MM program (which simply computes 4*2 and then halts):
1 inc A 2 2 inc A 3 3 inc A 4 4 inc A 5 5 dec A 6 8 6 inc B 7 7 inc B 5 8 halt
The translator creates:
>; v ; v ; v ; v ; v ; v ; v ; v ========================== ; v < ; v < ; v < ; v < ; v < ; v < ; v < ; v < ;v > ;> ^ ; v > ; > ^ ; v > ; > ^ ; v > ; > ^ v; < ^ >; ^ ; > ^ ; v < ; > ^ ; v < ; < ;
(The last line featuring only ";" is because of the translation for the halting instruction not using more than one line and the translator was constructed so that all instructions use two lines (for the sake of keeping the translator's Python code simple).)
The states of A and B registers are defined by the x and y coordinates of the PC; in which instance of the infinitely tiled bottom-right part of the program the PC resides. If, for example the PC is in the fourth horizontal (x) and third vertical (y) copy, the registers (A & B) are 3 and 2 respectively.
Note: The state of A register cannot be inspected reliably if the program has halted (or is in the process of doing so): for Nopfunge to halt, the PC must get outside the program space, and in this translation the PC is moved out of the space on the left side and thus the value of A register (x) will be zeroed in the process.
Implementations
Python 2.7
import sys
import re
class Halt(Exception):
def __init__(self,pos):
self.pos = pos
class NopFungeProgram:
def __init__(self,prog):
self.pos = 0
self.ptr = 0
self.facing = 1
# convert program to 2D array
self.playfield = re.split('[\r\n]+',prog)
self.hsplit = [i for i,e in enumerate(self.playfield) if e.startswith('=')][0]
self.maxlen = len(self.playfield[self.hsplit])
self.vsplit = self.playfield[0].index(';')
self.playfield = map(lambda s: s.ljust(self.maxlen),self.playfield)
self.commands = {'>':self.right, '<':self.left, '^':self.up, 'v':self.down, ';':self.hwrap, '=':self.vwrap, ' ':self.nop}
def right(self):
self.facing = 1
def left(self):
self.facing = -1
def up(self):
self.facing = -1j
def down(self):
self.facing = 1j
def hwrap(self):
if self.facing==-1 and self.pos!=self.ptr:
self.ptr=self.maxlen + self.ptr.imag*1j
def vwrap(self):
if self.facing==-1j and self.pos!=self.ptr:
self.ptr=self.ptr.real + len(self.playfield)*1j
def nop(self):
pass
def update(self):
self.pos += self.facing
self.ptr += self.facing
if self.pos.imag<0:
raise Halt((int(self.pos.real),0))
if self.pos.real<0:
raise Halt((0,int(self.pos.imag)))
if self.ptr.real>=self.maxlen:
self.ptr = self.vsplit + self.ptr.imag*1j
if self.ptr.imag>=len(self.playfield):
self.ptr = self.ptr.real+self.hsplit*1j
self.commands[self.playfield[int(self.ptr.imag)][int(self.ptr.real)]]()
"""
print "\033c"
for i,line in enumerate(self.playfield):
char = "LURD"[int(self.facing.real*(self.facing.real+1)+self.facing.imag**2*(self.facing.imag+2))]
if i==self.ptr.imag:
print line[:int(self.ptr.real)]+char+line[int(self.ptr.real+1):]
else:
print line
raw_input()
"""
def run(self):
try:
while True:
self.update()
except Halt as e:
return e.pos
if __name__=="__main__":
if len(sys.argv)<2:
print "No filename to execute."
else:
try:
openfile = open(sys.argv[1], "r")
except IOError:
print("File '"+sys.argv[1]+"' not found.")
sys.exit(1)
else:
listing = openfile.read()
openfile.close()
prog = NopFungeProgram(listing)
finalpos = prog.run()
print "Program halted at "+str(finalpos)
See also
- Nopfunge Solid, a simplification of Nopfunge
- Turnfunge, a minimalization of Nopfunge Solid
- Conedy