September 15, 1999: As time permits, I'll keep adding to this document. Check back regularly for updates.

Legals

Before viewing, using, modifying or copying the Quetzalcoatl Source Code be sure to read the legal note in legal.txt. If this is missing, contact me. You can send me email by clicking here.

What is Quetzalcoatl?

Queztalcoatl is a Cross Compiler for 6502 Processors. Queztalcoatl runs under Win32 and Linux. It can compile and link programs written in a subset of ANSI C, Assembler, the 1983 UPL language or any combination thereof. It is suitable for producing programs for the Commodore VIC-20 and Commodore 64. (You can run executables directly on emulators such as PCVIC or Free-64). With some minor modifications Queztalcoatl will also produce code for the Apple ][, old 6502 game consoles (such as the Nintendo Entertainment System) and 6502 embedded systems.

History

Quetzalcoatl's roots go back to 1983, when I wrote the UPL Compiler for the VIC-20 just for fun. In 1983 Development tools were in short supply, so I ended up writing UPL in BASIC. This meant some compromises, such as restricting UPL to byte variables and no advanced features, such as local storage, pointers or structures. Despite this, UPL did run and with inline assembler and the mem[] array you write programs that were almost useful. When the VIC-20 finally lost its crown to the Commodore 64 I put my UPL and my other VIC-20 programs into storage, and chalked up writing UPL as a good educational experience. (You can download the original UPL Compiler by clicking here).

In 1998, having purchased an old second-hand VIC-20 at a garage sale, and having discovered VIC-20 emulators on the Internet, my interest in the VIC-20 was renewed. I wondered, as a dare, if I could could write a 6502 Cross Compiler equivalent to UPL in a night? It ended up taking a few nights, but I soon had something that compiled UPL. Of course UPL was kind of useless. Would it be possible to modify the compiler to read Tiny C programs as well as UPL programs? Indeed it was. In a few nights I had that running too. But the Tiny C/UPL hybird wasn't particularly useful either, so I started adding features like subroutine parameters, arrays and pointers. I'd also spent some time adding optimisation so Quetzalcoatl (as the hybrid was now named) started producing some impressively tight code. Unable to find a decent 6502 assembler for the runtime library, I wrote one of those too and integrated it into the compiler.

I had originally developed Quetzalcoatl to satisfy my own curiosity. At Linus Åkerlund's suggestion I placed its binary up on the web site and have been amazed ever since at the number of people that have downloaded it. (I mean, it's a compiler for a museum-piece CPU! Like, why would anyone care!? J)

In September 1998 I was in the middle of adding proper C data types (pointers, structures and composite types) and improving the optimisation when the real-world beckoned. I figured I'd return to Quetzalcoatl and finish it when time permitted, but as of time of writing it's been 12 months and I'm still flat out.

I had been thinking about open sourcing Quetzalcoatl for some time, but the source lacks all but the most basic comments explaining how everything is strung together. The Netscape experience has taught the world it's not good enough just to slap an open source label on a piece of software, and expect the world to rush in to fix it up for you. It has to be maintainable. Plus I take pride in my code; I don't want a half-assed, second-rate product with my name on it floating around out there, periodically coming back to haunt me as an example of why someone shouldn't hire me. (For my commercial quality work I'm expected to use ISO.)

Rather than let Quetzalcoatl sit around and gather bit-rot, I've been documenting it when I get the chance. As of 15 September 1999 it's finally reached the stage where the basic structure is almost understanable. Thus I've decided to do a limited public release to people who have contacted me over the last year and expressed either a curiosity or an interest. Quetzalcoatl 2.0a5 is a limited source release to those people. (Accordingly, I'm asking those people not to redistribute the source.) If they're brave enough they are of course free to modify it, compile and distribute their own version of the compiler executables.

Future

When I've finished commenting Quetzalcoatl (or it is at least in a better state) I intend to open source it under GNU. If the right person comes along I'd be happy to hand it over to someone else with the time and the interest to take over lead development, cos for the forseeable future I'm going to be too busy.

I think Quetzalcoatl needs to reach a certain level of ANSI C functionality for it to be useful. Unless it does, you'll find it kept out of the realms of "real" programs. Given how far it has already come, it'd be a shame not to go than final mile.

But that said, I don't think it needs to be 100% ANSI C compliant. For one, Quetzalcoatl uses an LL parser, where as C is a LR grammar. For two, it isn't really necessary. Very few C programs need 100% compliance, and if you must compile one of these there are already perfectly good 6502 C Cross Compilers out there. No sense reinventing the wheel. But as an LL compiler Quetzalcoatl offers some interesting opportunities, because you can really get in there and fine-tune the mechanics. For example, you can add custom optimisers to squeeze every byte and cycle out of the machine. This fits well with Quetzalcoatl's orginal goal; to produce 6502 code for a VIC-20; a machine with a scant 3.5Kb of RAM(!) In such a constrained environment, you have to make every little bit count.

To Do

1. Improvements that bring Quetzalcoatl closer to ANSI C, so that it can compile "real" programs.
2. Optimisation.
3. Versatility.

Here are some ideas for Quetzalcoatl development:

• Proper C types. Quetzalcoatl sorely lacks the full range of proper C types, so it can't handle types such as int **foobar[];. It's necessary to support these so Quetzalcoatl can compile reasonably useful "real" programs. I'd already started many of these, but realised the symbol table needs a major reorganisation so it can represent these. The symbol table in its current form simply can't hold these.
  • Pointers. These are partially implemented. You can use 1-level pointers as variables and parameters for call-by-reference. However you can't use them with composite types, such as int **foobar[]; which is where they become particularly useful.
  • Structures. Again, partially implemented.

• More Peephole optimisations. The UPL_COPT.CPP file contains a nifty peephole optimiser. This code peeks at code that has just been written, and if it knows a better or faster way of doing it (much the same way a human programmer would recognise such an opportunity), it does a rollback and replaces it. It's very easy to add new optimisations to this submodule.

• A Flow Optimiser. After an executable has been linked, it'd be good to have a flow optimiser go through and do additional optimisations.

• Tree Optimisations. Quetzalcoatl Rollback optimser can only optimise code at the current end of an object module. A tree-code optimiser would still be able to apply optimisation, even if the optimisable code is not at the current end of the module.

• Relocatable Assembler. The Compiler only produces absolute (ie. non-relocatable) modules, and at that can only have one such (assembler) module per program. It'd be fairly easy to modify the assembler so it can produce relocatable object modules as well.

• &&, ||, ! One feature I never liked about C was its el-obscuro operators. Thus Quetzalcoatl uses meaningful keywords like "and", "or", "not", etc. However for closer ANSI compliance it'd be a good idea to modify Quetzalcoatl so it can read el-obscuro as well.

• Porting the Runtime Library. UPL/Quetzalcoatl can be easily ported to any 6502 platform. It has already been ported to the C64 and VIC-20 in a variety of configurations. Ports to other 6502 platforms are welcome.

• Shrinking the Runtime Library. Anything that can be done to make the runtime library code smaller and faster is a good idea. Take a look at uplrtime.asm to see if you can squeeze any extra bytes and cycles out of it.

• Granular Runtime Linking. As small as the runtime library already is, there will usually be parts of it included in an executable that are never called. The ability to selectively link only those parts of the runtime library that are needed by a particular executable would be a good idea.

• Debugging Quetzalcoatl doesn't support debugging, other than the old "insert a print statement, compile and run it again" kind. Integrated debugging, somehow hooked in with a 6502 emulator, could be a good idea.

• That's it!

Here are some changes I don't see as necessary, and why.

• long. Quetzalcoatl doesn't support longs. The 6502 has a small number of registers. You can hold a 16-bit value in the A and the X registers. If you're working with 32-bit values you're going to have to store at least some its elements in memory, which'll slow things down dramatically, and add bloat out the runtime library.

LL vs LR

There are two broad families of compilers; LL and LR. Quetzalcoatl is an LL compiler. These are easy to write and easy to understand. The catch is they can only parse certain types of grammars. (A grammar defines the rules of a language.) C is actually an LR grammar, so I had to bend it somewhat to get Quetzalcoatal, an LL compiler, to be able to be able to parse it. (The official response is that Queztalcoatl isn't C, even if it happens to look a lot like it.)

LR compilers are internally quite complicated. Compiler writers need to use a Compiler Compiler such as YACC or Bison to build them. They do the job beautifully, but internally they're extremely boring. Quetzalcoatl was written for fun, education and as a testbed for optimisation, which is why I chose to write it as an LL compiler. If 100% ANSI compliance was my goal, LR would have won, hands down.

Architecture

Here are the major objects within Queztalcoatl:

• Flex. The Lexical Parser. This bites "tokens" from the UPL/Queztalcoatl source file. Here are some example tokens: "(", "20", "+", "and".

• upl_Symbols. The Symbol Table. This stores all active variables, constants and subroutines names and their attributes.

• upl_Object. This object module holds generated object code/data.

• upl_Segments. Each Quetzalcoatl/UPL source file has two segments; code and data. The upl_Segments object contains an object module for each.

• upl_Context. This holds all the contextual information for a program being compiled; the symbol table, the object module segments, options, settings and statistics.

• upl_Context_state. This remembers the compiler state. These are stored as code is generated. If the compiler later realises a better way it could have generated the code, it "rolls back" to the state, and rewrites the new, improved code.

• upl_Compiler. This is where it all happens. Call program() with the Flex object and a upl_Context, and Quetzalcoatl will run away and compile your Quetzalcoatl/UPL source program. This calls other methods to parse different language elements. For example, if_statement() compiles an if-then-else statement, while_statement() a while statement, expr() an expression and so on. An example from while_statement is shown below.

• upl_Assembler. This is the 6502 assembler used to compile the runtime library. It is called in the same manner as upl_Compiler.

• upl_Link. This is the linker. It loads all the object modules and optionally the runtime libray to produce the final executable.

The upl.h file is a good place to look for more detail on many of these objects.

While Statement Example

The actual upl_Compiler parsing routines are contained in the file UPL_COMP.CPP. Here is a fragment from while_statement() illustrating the conceptual simplicity of an LL parser. For clarity, the address patching code is not shown in this example.

void upl_Compiler::while_statement(Flex& L, upl_Context& C)
{
  // ... patching declarations not shown

  upl_Expr_result       clause;
  upl_Expr		expr;

  L.check("while");
  if (L.matches("("))
    {
    expr(L, C, clause, 0);
    L.check(")");
    L.matches("do");
    }
  else
    {
    expr(L, C, clause, 0);
    L.check("do");
    }

  // ... statement parsing and patching code not shown
}

Until a suitable volunteer appears, I'm happy to act as a central point-of-contact for people wanting to modify or otherwise extend the code. I'll keep a list of active developers and what they are doing on the Queztalcoatl web site.

Source Guidelines

If you change the source code, and want to integrate those changes back into the Queztalcoatl primary distribution, please:

• Comment your code properly.

• Keep to the naming, commenting and indentation conventions used in the source.

• Let others know what you are doing. This'll save two or more people all doing the same thing at the same time.

• EVERY SOURCE FILE HAS A MODIFICATION SECTION. PLEASE KEEP THIS UP TO DATE! This is located at the start of each file. When you make a change, make an entry in this section. Assign the modification a sequence number (the previous modification number plus 1, or 1 if there are no prior changes). Enter this number, your initials, the date and a brief description of the change. At the point where you make the change enter a comment describing it, along with the following tag: [initials date MODn]. eg. [bj 15sep1999 MOD6]. If your changes are long include comments denoting where they start and finish. Sticking with this format will make it easier for multiple people to make changes to a module without tripping over each other.

• When appropriate, prefix a comment with the keyword: CAUTION, NOTE, TODO or when you're unsure of something, UNSURE. This'll help other programmers quick identify the relevance of your comment to their current situation.

If you're thinking of changing the code and want to check in, or you're trying to understand what a particular piece of code does or why it was implemented that way, then please click here to send me email.

If you're using Quetzalcoatl for a 6502 programming project, I'm also interested to hear from you. To date there have been over 150 downloads of Quetzalcoatl and I'd love to know what on Earth it is that people are doing with it! J

Links

• The Queztalcoatl web site. Contains the Quetzalcoatl binaries, news and links to the development pages.
• The Geek VIC-20 web site. My collection of software, links and information on the VIC-20.
• The Sachiel.com web site. I'm going to do something interesting with this site, but at the moment I'm not sure what!
• The Kestrel Art Gallery. My online art gallery.
• The Kdef.com web site. Where I work when I'm not writing compilers.
• pussiesgalore.com.au. My friend Katina's Cat Lovers Web Site. (Don't forget the .au!)