Eighth - a Forth for NES dev (formerly Bytecode Interpreter)

So I've been developing a bytecode interpreter for the NES to solve a few problems. I'm using it to do r&d. Here's why I did it:

1) 6502 is hard - too hard to try out ideas on or get something running quickly.

2) C is not much easier and not space-efficient at all.

3) NES has tight storage, so space-maximizing measures are advantageous

I'd been a fan of Forth for several years and became a minor expert in it. I thought it was the perfect solution to primarily the problem of difficulty of coding. Forth simplifies things a lot, at the cost of speed. The savings in size are almost a side benefit, but they are substantial.

What I settled on is a virtual machine with 8-bit instructions and an 8-bit stack. It's almost fully functional - still tweaking the instruction set. I optimized it as best I could - the estimated speed is about 600 900 instructions on average per frame. This is enough for rapid prototyping of ideas ... but also useful where speed is not critical, like decompression. I estimate that the size savings it provides over plain asm is about 30%. That ratio, as well as the speed can be improved with peephole optimization (when the compiler combines commonly used pairs of "words" into faster hybrids)

A "compiler" coded in SwiftForth (PC) will generate asm6 assembly code. It should run on the trial version.

I thought I might create a thread to let people know what I'm doing, gauge interest, maybe get help with any issues I run into or just hear ideas and answer questions.

8/15/2013
I threw the runtime source up in a Google Code project - https://code.google.com/p/eighth6502/ sorry no docs, compiler, or example yet

8/18/2013
Updated OP to be a little more general and up-to-date

I had a eureka moment and figured out a way to speed it up by 1.5x using a tiny bit of self-modifying code, while also saving a significant amount of ROM space. Like hundreds of bytes.

An additional improvement is it can now call arbitrary asm, so asm and bytecode can be freely mixed. I am looking to add 16-bit math next.

The only thing that needs doing now is testing it. I spent a long time debugging the first version, and I'm not really keen on doing that again, so I'd love it if anyone was interested in maybe helping beta test it.

To give an idea of how optimized this is... here is the heart of it, the "inner loop"



VMNEXT_JMP is actually the ZP address of the lower byte of the literal within the next instruction, only one page of ROM used for opcode implementations. one of the virtual registers IPBASE is actually the 2nd and 3rd bytes of the first instruction in this listing.

Ever read about Steve Wozniak's Sweet16 interpreter?

Neato - no I hadn't heard of that. It isn't practical to have a full 16-bit VM for realtime code (rather I'm going to just have some extra instructions for doing a couple 16-bit operations) but I will have to look into this later for ideas or code. Thanks.

Btw... I noticed your alias... Dan Weiss right? We've collabed before.

Thanks for the updates sonder. Is your implementation living somewhere out on the web for perusal? I am interested in checking it out.

Update:

During the past couple days I debugged it and optimized it more. Comparison tests, if/then, for loops and while/until control structures are supported and functioning perfectly. A very small set of opcodes and routines for working with 16-bit numbers were added.

On the testing side of things I was able to get significantly more game features going on in roughly same number of cycles with tons to spare (currently using around 1/4 of the frame. About half of that is just the metasprite rendering (about 16 sprites), which is asm, for perspective. One nice thing is calling arbitrary asm routines is pretty fast so they are not limited to being behemoths to justify their existence. Surprisingly, because the interpreter is so fast, a lot of the time trying to squeeze out more speed by turning something into asm doesn't actually buy much. But as the complexity of a bytecode routine grows, the benefit of turning it into asm increases by a lot. So it is still best suited to stuff that can be slow, or simple high-level logic.

Ready for some example code? Here is an excerpt, just really basic moving a guy around. Doing it by hand for now, since the interpreter was basically rehauled and requires a major update to the compiler, but it's actually not too bad.



Once the compiler is done this would be how the same code will look in Forth-style syntax:

No not yet. It just needs to be taken out of the game project folder and cleaned up. I will do that tomorrow since it's in a good working state and throw it in a SVN repository.

Just made the code available, see OP.

Well the desire for speed and more efficient nesting has led to yet another "rehaul" (though not as big as the last one) and I am thinking of moving to 16-bit "opcodes" (really 16-bit direct threaded code, classic Forth)

I discovered a way to do the inner loop for threaded code (basically lists of addresses) that is probably the fastest possible. It's 20 cycles so a bit slower, but, now there is absolutely no penalty for calling arbitrary asm where as before it was ~30 (on top of the 15 cycles for the inner loop that's 45 cycles just to execute something as simple as fetching an object property). As a side bonus nesting interpreted routines is a little faster. But fetching literals is almost twice as slow.

The size savings would be likely less than bytecode but not that bad. This is because of how often custom routines are called. Because all calls are now 2 bytes instead of some being 1 and some being 3, it nearly balances out. I probably don't care about size as much as before because I've moved from NROM to UNROM.

I originally envisioned a bytecode interpreter because I wanted to also use it for data compression but it's looking like I might end up doing what would have seemed counter-intuitive before my pursuit of speed started - two interpreters one for reasonably fast Forth scripting and one specifically tailored for size over speed. The bytecode interpreter may actually become a slower, limited subset of the DTC one, relying on a lot of the same code and variables just a different separate inner loop. The idea was to set it up so the opcodes are extensible, to for instsance specify data using basically simple inline scripts within the map data.

By the way, how is Forth as a programming language? I've never tried it myself. Seems like it uses RPN extensively, but how different would it be from Basic or C if it used infix notation?

It is slower than C (in Eighth's case probably 2x), but faster than Basic. Its big draw is ease of implementation, but it does also have the benefit of teaching you to be a better coder if you stick with it. Mostly because of how the requirement to learn to factor well to effectively use it beefs up your abstraction practices.

It's like C in that it grants you a powerful gun with which to shoot yourself, but like Basic in that it is doesn't have nearly as much punctuation and required boilerplate.

It has no types, which can be seen as a benefit. The one type is the cell - the width of the data stack. In my interpreter Eighth, that's just 8 bits. Any others are derivative and managed by you. This isn't hard if you just notate things using stack diagrams or use certain name conventions (e.g. "<name>?" returns either 0 or -1). Address and 16-bit math are accomplished with "doubles", pairs of values on the stack. You learn not to think in more than a handful of types which are fluid and morph into each other frequently.

It can be implemented in a couple days, like I did. The runtime portion anyway. Doing a complete system takes a couple weeks to months.

It lets routines return multiple values for no extra work. You don't have to name them, just push them on the stack.

It's eminently extensible. Want a custom control structures, inline data (like strings), or custom compiler keywords? Trivial. Many language features can be added, but you get the advantage of being able to tailor it specifically to your app. Many things can't be easily added in full (like C-like structs) but you learn to work around, for instance by using its equivalent of namespaces, or prefixes. Or figuring out some other way to do what you want to do in the end entirely.

Being fully concatenative it lends itself to very natural-reading code (admittedly in your hands.) It frees you to think in broad strokes when reading code, instead of poring through it line-by-line like a computer. You pay more attention to the structure and logic of the program than the nitty gritty. Oftentimes rewriting subroutines or entire modules from scratch rather than trying to shoehorn in kludgy tweaks. Because ideally they should be really short and clean. This gave it its "write-only" rep but I disagree I think it is very readable, just not always easy to make changes to a complex routine, which would be your fault anyway. Keeping your subroutines simple (you're supposed to use lots of subroutines) frees you from having to think like a compiler. (Unfortunately Eighth's subroutines are currently kind of expensive...)

Not requiring named parameters makes code really fluid. Bits and pieces can be easily lifted out and turned into subroutines far easier than any other language I've used (I've heard Lisp is similar though). That contributes to the fun factor. Local named variables/params are supported in fancier Forths.

So TL;DR, actually, Forth is really, really different than both C and Basic. In my opinion it's both easier and more powerful if your goal is writing a program fast. The fundamentals can be learned in a day, but mastering it takes time. You have to unlearn a lot of assumptions and learn all the tricks. In the meantime writing simple scripts should be a cinch for just about anyone - in the old days they'd give customers (like scientists and businesspeople) app-specific vocabularies and let them write scripts (which were really just Forth programs!) all the time.

Right now I'm not sure if it'll be worth the effort to implement 16-bit DTC (direct threaded code). Free arbitary asm, 1.5x faster subroutines, and much faster for/nextare the advantages. The big disadvantage is actually that literals are slow. More than 2x actually. And they are ubiquitous, so that's no bueno. It's totally unclear how it balances out right now, if there's enough overall speed gain to justify. This may be a future upgrade. Kind of tired of rehauling this thing.

Just did a quick analysis of the test script and literals are far less common than callasm's and call's. Moving to 16-bit DTC would eliminate 903 cycles (8 scanlines) of overhead. (originally 1759 - 16 scanlines - so around 2x faster)

That was a naive assumption. I just spent an hour creating a DTC version of the interpreter. I'll post actual test results soon.

The speed increase, as I thought, wasn't as dramatic as I originally hoped. Debugging the DTC version was a BITCH due to the instruction pointer being pre-incrementing now. But the savings in the test program after everything was about 4 scanlines. I tried to get literals down as much as I could, but I could only get them down to 36 cycles, down from ... like 50. I forget. (but compare to the old VM's 25... and i considered that slow...)

It's starting to get to the point of frustration - come up with a great idea, bang it out, then reality hits and after all the work that goes into debugging it, it yields only an incremental improvement. Bleh. Well, what's done is done and now it's slightly faster. Besides, I'm sore from parkour class yesterday so I was fine with coding on the couch half the day

Banged out a brand new compiler supporting DTC and several useful bonus features. Converted the player's script, and got it working fairly quickly:

Seems familiar. There is a whole space of alternate implementations, each trading different things off, and each more appropriate for some use. If you go full-speed down one, you might see another nearby one that was better for your uses. Or you want to take two or more approaches as far as they go, just to have both around (as the comment above indicates). It's one of the things that sometimes derails my efforts, wanting to explore this implementation space, have every one fleshed out, and be able to reach my original goal. I usually have to choose between exploration and focusing on the concrete task and what's necessary to reach it, and possibly then improve on it.

Here's the cherry on top. The fastest intepreter is no interpreter at all - I realized that recently. What I really wanted was just to code my game in Forth, not to perform a technical magic trick by stuffing it into NROM. I have 128KB now to splash around in, so I could have used macros and jsr's. Because it should be 99% source-compatible it can be done anytime. But there has been enough work done on this for a first game, and it would be a big risk on time to upgrade now. I didn't know 6502 very well before I started, now I know half the instruction set's sizes and cycle times. I'm just glad that I decided on basically avoiding writing asm as much as possible. Doing the Eighth code "by hand" was hellish, but I was putting off writing the compiler because I thought that was going to be worse but it wasn't at all, in fact it was exhilarating. I just needed a good nap. Of course, I think "bytecode interpreter" in the pure sense will now be implemented in Eighth and multiple ones tailored to specific applications, similar to the manner of SWEET16 with its embedded register # operands.

Got a large amount of code compiling - and achieved buggy-ass collision detection. Speed is... OK. I was converting some old Forth code, caught a lot of bugs in the compiler actually. You really have to be conscious of how efficient your code is. And of course there are no divides, multiplies, or modulus.

Through this process, I realized that in its current state, without interactive testing it's really only an incremental improvement over C/asm. There needs to be interactive testing - a pillar of Forth. Therefore I'm going to write a simulator - basically a program in SwiftForth that lets you compile Eighth programs in "simulator mode" and basically it tries to create the 8-bit environment of the 6502 so you can test out the logic of your various subroutines by typing them into SwiftForth's commandline window and observing the effect on variables and the data stack. It won't be able to help you with debugging asm words but those are relatively few and short (and you can step through them in a debugger like Nintendulator's or FCEUX).

edit: alternatively I was thinking to look into Nintendulator's Lua scripting and implement a dialog to interact with a ROM's compiled Eighth code and asm words using the symbol file. then you could debug asm words without having to rewrite them in Eighth or Forth so they can work in the simulator. but then it would require Nintendulator - I don't think that's unfair though.

You'd probably be among the first to use the Lua UI features in NintendulatorDX. They haven't been tested that much so if you decide to do this let me know how it goes!

I read the docs and it seems promising. I'm thrilled that you're interested. The first hurdle is figuring out IUP. I need a dialog box with a multiline text out, and a text input. And one more textfield for the data stack.

I am leaning in this direction because if it works it is guaranteed to be a reliable way to verify code, whereas a simulator would have some annoying limitations. I have a good idea of how it will work.

However because I'm using asm6 I am going to have to either port to cc65 (dreading that) or add the debugging file export support to asm6. It's a shame; I should've stuck with cc65. (though -/+ labels and not dealing with segments have been nice). I emailed you about it already.

It'd be fair enough if Wine were improved to run Nintendulator. Last time I checked, Nintendulator required Genuine Windows. FCEUX, on the other hand, works on GNU/Linux in either Wine or SDL.

If FCEUX added Lua scripting the interactive commandline could in theory support that emulator too. You're only losing interactivity without, the compiler is a separate program. It may need modification for the Linux version of SwiftForth though.

I kind of have to do it this way anyway; I painted myself into a bit of a corner and this is the escape plan. The simulator idea is not good compared to this.

Fortunately, if true.

Do either of these emulators have the ability to call a lua script when the program writes a given value to memory?

In FCEUX, your Lua script can register a function that gets called when a certain address is written, then check if the address contains the desired value inside the function. (In FCEUX Help - Lua Functions List, see memory.register aka memory.registerwrite.) For example, to do something when $82 is written with 0, run this Lua script:

Crap!! So I added FCEUX-labels-exporting to asm6 only to discover FCEUX doesn't have Lua access to the labels!!! :O wonder if I should attempt adding it myself or do a feature request :/

You could generate a Lua file that has corresponding variables for each symbol. Either from asm6 or with a separate tool from the label-file generated by asm6.

I think that will be easier. Thanks.

Success! I lazily implemented it in fits and starts throughout the day, but it's now functional. You can test any Eighth word interactively and push numbers on the stack. One caveat is you have to use the assembler labels ... so for instance 1+ has to be typed as oneplus... Coming soon, more than one word per input And maybe somehow get the punctuated word names in there (the compiler could take care of this).

Very cool!

Have you considered a subroutine threaded compiler? Instead of an inner interpreter that goes through lists of indirect addresses, you just have a list of jumps.

JSR dup
JSR drop
.... etc.

It's typically a bit faster as there's no interpreter and it's easier to perform optimizations on, but the code size is usually bigger.

I'm currently writing such a forth compiler for the Genesis, but I wouldn't mind trying the same thing on the nes at some point.

Yeah. I've actually already implemented one since the last update, and updated the interactive console to work with it. I am going to use it to code my game. Since it's in parallel development and somewhat coupled I decided to announce/release it after the game was done. But I'm not exactly actively working on the game because I'm busy with other priorities.

I hope you continue this project. There is definitely room for a more accessible language than C or assembly.