(update: Please forgive the formatting, this editor doesnt do line breaks/spacing well at all, thats why some parts look pretty funky)
They said it couldnt be done. They said it was impossible.
They were wrong.
What they said was: It is (almost) impossible to successfully compile a working funge source.
Chris Pressey, the author of befunge93, wrote a program called bef2c, which would take a befunge source file and translate it into another C file to be compiled. The c source was a complete mapping of the 2d funge space, complete with goto links to every neighboring instruction, so the program would function just like a befunge93 application. To date this is the only attempt I’ve seen of a ‘true’ b93 compiler. Another user did similar, but the result was an interpreter, not a compiled b93 app. There were 3 very large limits to Chris Pressey’s implementation though:
1) the stringmode operator ( " ) was not supported
2) the modify operator ( p ) was not supported
3) the result was very large. For every b93 instruction, 4 copies were made. Each had its own label and goto link, with code to execute the instruction, each for one direction.
example: the 0 opcode pushes a 0 into the b93 stack. The above compiler would generate:
_op_0_0_left: push(0); goto _op_79_0_left; _op_0_0_right: push(0); goto _op_1_0_right; _op_0_0_up: push(0); goto _op_0_24_up; _op_0_0_down: push(0); goto _op_0_1_down;
repeat for the other 1999 entries in a b93 app (its an 80×25 screen of code)
The reason the same code is repeated 4 times is so when the IP (instruction pointer) changes direction, all that was needed to do was jump to the correct direction label for the next instruction and the app would follow that chain of code, going in the new direction. Now you probably have an idea how hard it would be to support stringmode/modify operations, it would be extremely difficult to modify all 4 instances of that code or inject logic to process stringmode.
I’ve written a compiler that does most of the above. But it supports string mode AND modify operations, and takes no where near as much room as the above compiled source does. And it is extremely fast. Somewhere in the range of over 20 million b93 instructions per second on a p3 1ghz. While not staggeriing, it is a large improvement over the classic loop with opcode switch statement for a b93 interpreter.
The trick to my version is with the following (break out your x86 assembler manuals):
opXY: call [opXhandler]
opXYJumps: dd leftop
dd rightop
dd upOp
dd downOp
dd opValue
There are 2000 of these structures, each initialized so the opXYJumps values are set set to the neighboring 4 cells around it. This includes wraparound on the borders of the 80×25 page, so ip movement tracking is elimiated.
opXhandler is the pointer to the handler for a b93 opcode. When the compiler starts, it initializes that address to a default opcode handler, which does nothing but advance to the next opcode. When the compiler loads a b93 source, it replaces the correct locations with the proper handlers for each b93 opcode loaded. When done, the compiler jumps into the compiled array. Whenever a stringmode (") op is encountered, the app switches to a loop that will trace thru the array, pushing opValue onto the b93 stack until the next (") is found, where it will resume normal execution. When a modify (p) instruction is found, it will replace the call address of opXhandler with the new opcode’s instruction handler, and load the opValue into the correct cell, therefore maintaining the self-modying nature of b93.
The source will be available soon, as right now it is in pure x86 win32 assembler. Im working on a c equivalent that will dump a binary to run directly on the system, the current version compiles the b93 app in memory and executes it.
