Steve's Wacky Programming

By steve  on Sun 10 of Oct., 2004 14:25 EDT

(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 80x25 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 80x25 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.

Permalink 0 comments

By steve  on Mon 20 of Sep., 2004 18:03 EDT

I'm sure some of you have seen some strange programming languages out there, like eiffel, intercal, K, brainfuck. If not, do a google on each of those and you'll be in for a treat. Any way, what I'm about to bring up is something truly mind boggling: programming in 3 dimensions.

I've seen one language in particular called BeFunge that gives a user a fixed size 2d programming environment, where every instruction is a single character and the instruction pointer (like the pc register in Intel cpus) can move around freely left, right, up or down. 3d adds another dimension to that and now you have 6 directions: down, left, right, forward and back.

What I'm getting at is, would a beast such as this be worthwhile? Currently I have a VM (virtual machine, like a java interpreter) in the works that does exactly this, with the hopes that it could possibly provide a way to write extremely dense code in 3 dimensions, using less space than a typical compiled binary would yet be just as good if not better. The only drawback is there is no way at the moment to write source in the ways we are used to, using a text editor or other tool to generate "source code" for the vm. All I have at the moment is equivalent to writing x86 machine code by hand in a hex editor. Granted this gaurantees that what you write is what you intended, but hex editing a large 64x64x64 cube of hex code is a bit of a task, even for me. I have a visual tool in the works as well, sort of a 3d hex editor, based on opengl and its almost there, but for this to really be useful, there has to be some way to type in semi-english looking code in a file and produce the same hex output the vm expects. Any ideas, thoughts, flames are welcome. Just be gentle =)

Permalink 0 comments