!!! A-LANG: WAYS TO IMPLEMENT COMPUTER LANGUAGES ON 6502s

__David A. Wheeler__

(original at [http://www.dwheeler.com/6502/a-lang.txt] )

[{TableOfContents }] \\

Here are some of my ideas on how
to create efficient and easy-to-use programming languages
for 6502-based computers (such as the Apple II, Commodore 64/128,
Atari 400/800, and the original Atari game machine).

I haven't tried to implement these ideas at length, since I haven't directly
used Apple II's (or any other 6502-based system) for some time
(though there was a time I could rebuild an Apple II from memory!).
For me, this is simply an intellectual exercise.
I did create a partial prototype of some of these ideas, particularly
some of the linking techniques.

Still, this was an old problem that a friend of mine
(Bob Pew) & I often hashed out.  Bob passed away just when I completed
writing the first draft of these ideas, and I was about to call
him about my new ideas for this old puzzle we'd often chatted about.
I miss him; perhaps this little file will serve as a small memorial to him.

Perhaps some reader of this file actually DOES decide to do this. If you do:
(a) are you SURE you don't have better things to do?
(b) please let me know, I'd love to hear about it.

Who knows; maybe the ideas of an "optimizing assembler" and
"compiling linker" can be taken to other systems. It makes some sense,
especially for systems where compilers are quickly written & can
generate assembly, so that poor compiler code can be made a little better.
It's possible these ideas have been created before, especially on far
older systems.

These are essentially notes, and are a little rough in places.
Sorry about that, but I think you'll still find them useful.

--- David A. Wheeler

File originally created 11-April-1994.
This version (slightly revised) 12-Sep-2002.


!! BACKGROUND/THE PROBLEM

The 6502 is a weird beast with a very irregular instruction set.
Bob Pew & I wanted a language that would be (a) faster to program in (than
assembly) but be (b) fast when running.  It needed to be pretty efficient.
This turns out to be an intellectually challenging problem; below
are (what I think are) some solutions.

There are many odd things about the 6502 that make it hard to do this:
+ It's REALLY an 8-bit processor. It doesn't even have 16-bit
data registers or instructions (many other 8-bit chips, like the Z80,
at least had these). That means that, where possible, use
8-bit manipulations instead of 16 or 32 bit data types.
+ Its instruction set is rather irregular and has a few
odd addressing schemes (esp. "zero page").
+ Its built-in stack (for subroutines) is only 256 bytes long -
possibly enough for storing the return address, but probably not
big enough for storing data as well.

A key to using the 6502 is to keep as much as possible in the "zero
page." The zero page is the first 256 bytes of memory; the 6502 has
a large set of special operations that use this area of memory, in
many ways like an extended register set.
Loads and stores are faster to the zero page, and some operations
(such as indirect addressing) REQUIRE use of the zero page.

!! THE SOLUTIONS

I have developed 2 new (to my knowledge) solutions to this problem:
1. Statically assign parameter and local variables in a special way.
To do this, divide the work of compilation & linking
in an unusual way (the linker does a ton of "compilation" work)
to efficiently use 6502 resources, and
in particular assign all local variables and parameters to static
addresses. Global analysis is then used to assign addresses so that,
in most cases, all copying between locations (e.g., between
the addresses for parameters and addresses for local variables)
are essentially optimized away.  This could probably be best utilized
by creating a different language, so it then discusses a potential
ASM+ & Simple, a pair of languages that squeeze as much
efficiency out of the 6502 as reasonably possible.
However, the approach could be used by C, etc., especially if the
programmer is willing to accept certain conventions and extensions
(e.g., extending C to support pass-by-reference like C++ and then writing
6502 code that uses that extension in most cases).
This approach can support recursion - even automatically - but there
is a cost where the recursion occurs.
2. Fixed location data stack.
This would be easier to implement & would support recursion more easily.
This approach wouldn't be as fast or small as the previous approach,
but it would support a more traditional approach
(linking could just link, compiling could just compile).
This approach would be particularly good for FORTH-based languages.

It's hard to argue that these are "always better", but I suspect
they're better in at least some circumstances than other approaches.
Stack-based approaches that use a zero page two-byte pointer to an
arbitrary stack are flexible, but SLOW on a 6502 and create large code sizes.
Anyway, if you're implementing these kinds of systems, you might want
to think about these ideas.


! SOLUTION 1: Overloaded static parameter/local addresses - ASM+ and Simple.

This approach creates overloaded static addresses for
parameters and local variables, in a special way that
maximizes use of the zero page.
It's probably easiest if specialized languages are designed to
exploit this property, so I also discuss 2 specialized languages to do so.

The approach below uses the zero page as much as possible,
overloading each zero page location with many different variable values
(as long as they aren't used simultaneously). In fact, it's difficult to
believe that normal humans could overload its usage so well, so this
approach has the potential to be in some ways more efficient than humans.

This approach doesn't _require_ specialized language, but it might
be easier and more flexible that way, and originally I had in mind
the idea of creating a high-level language specifically to be easier to
efficiently implement on a 6502 (of which this idea would be part).
Two specialized computer langauges are discussed here:

ASM+: A macro assembler with 2 peephole optimization stages and a special
macro language with common operations (increment integer, etc).
It can be used as a "smart" assembly language directly, or as an
intermediate compilation language generated by a "Simple" compiler.

Simple: A higher-level language that would be C (and Ada) like,
but would pass by reference (like Fortran) instead of by value (like C).
Why reference-passing, when the 6502 poorly supports arbitrary pointers
and copies?  The answer is that, with this new overloading approach,
reference passing could often be implemented by a copy that never
actually happens (via address overloading).
Since the 6502 doesn't have a usable data stack, this approach is
more efficient on this platform (in the implementation, the
"reference" is implemented not necessarily by copying values, but
by having exactly the same address assigned to the parameter and
the variable calling it, creating "zero-copy" calls where possible).
Recursion could still be done, though recursive calls could be
expensive when executed.
By using Ada-like parameter passing (noting IN, OUT, and IN OUT)
passing data is MUCH more efficient than for C, because most "copies"
could be eliminated.

Creating code when everything was implemented would go through
the following steps (with product types in square brackets):

~[Simple Code as ASCII text, created by a programmer] ->
Simple compiler. ->
~[ASM+ Code as ASCII text] ->
Special preprocessor and/or done as part of the "linker" step ->
~[List of procedures & what they call; also input/output params, globals,
and a list of variable sizes which need allocation] ->

(At this step "compilation" is done. Now to link:)

Run "linker" across all ASM+ code - first determine what procedures call
what & then do a topological sort. Then determine address locations
of all variables (including variables used to pass data between
procedures), trying to use zero page as much as possible.
Generate a file of all address locations.
I've written a quickie "demo" program that handles the topological
sort and shows that you really can stick in a lot of variables into
zero page if you do this (it also generates a huge batch of EQU's that
a simple assembler could use to support this idea).
Note that you also want to "prefer"
a memory allocation that eliminates copying memory for parameter passing;
this is possible by judiciously "overlapping" memory locations
from different calls.
Pass one of ASM+ assembler. Transforms "early" macro expansions, then
does a peephole optimization pass on the assembly-with-some-macros.
Pass two of ASM+ assembler. Transform all normal macro expansions into
6502 code, then do another peephole optimization.

~[Executable Code]

"Compiling" a Simple or ASM+ file is relatively cheap.
Linking on larger systems would get expensive, since there would be
some global analysis followed by assembly of everything.
This is necessary to maximize zero page usage.

The ASM+ assembler could fit in the restricted 6502 memory.
The assembler would need to keep the macros, global definitions,
jump addresses of procedures, and addresses for parameters in memory
at all times; for each procedure definitions could be kept & then dropped.
Code could come in & out via the disk.  Thus, this could be self-hosting.

The procedure call system should be by-reference, since this is cheaper
on a system without a stack and where "copies" aren't really copied.
By-value can be supported too, but the goal is to minimize actual copies.
Values are simply written to fixed locations
(preferably in the zero page)
and the procedures are then JSRed. Return values are handled the same way.
Recursive calls can be handled, though expensively: copy the values that
might be changed onto a stack and/or malloced area, call the recursive call,
then pop the values off the stack.   This can be noticed at link time;
by simply following the call tree you can see which calls
"loop back", and wrap those calls with the commands to save & restore
the variables covered by everything memory location possibly used "between".

Implementation order: naturally not everything need be built at once.
The ASM+ assembler could start out as a stock macro assembler, and just
create macros for it in the stock macro language.
The macro language would need the ability to do .IF's during expansion,
since it would need to pick from a number of expansions depending on
whether or not certain values were contant, in the zero page, etc.
Thus only the "linker" would need to be built, which would simply
examine for special macros that define procedures,
etc, and generate addresses for everything.
The peephole optimizers could be built later.

Bob originally wanted an ASM+-like language, and he always liked Fortran--
I think he would have liked a Fortran-like parameter system!

Here's a sample ASM+ syntax:

{{{
"I" is used for (2-byte) integers, "C" for (1-byte) characters,
"L" is used for (4-byte) longs, "P" for (2-byte) pointers,
"R" for records of other sizes.
}}}

Results are always the left-hand-side argument (so that later Simple
operations will look similar).


{{{
I++  A    increment integer A.      INC A ; BNE .1 ; INC A+1 ; .1
C++  A    increment character A.    INC A
I--
C--

I:=I A,B  copy B into A.
C:=C A,B  copy B into A.
I:=C A,B  copy B into A.

I+=I A,B
C+=C A,B
I+=C A,B
}}}

also -=, *=, /*

{{{
I:=I+I A,B,C
}}}

also -, *, /, and for C as well.

{{{
MEMCOPY

IFI==0 A, BR
IFI==I A, B, BR

also !=, >, >=, <, <=
also for C.
}}}

And also some "combined" macros, which expand into optimized 6502
instructions (some for loops, for example):

{{{
I--==0 A, BR       Decrement A; if not 0, branch.
I++!=I A, B, BR    Increment A; if not B, branch
I++<=I A, B, BR    Increment A; if less than or equal to B, branch.

IZERO A            Same as I:=I #0.


FOR  ... various forms, inc. some which use the Y register for fast loops.

CALL location
}}}

To call another procedure, use I:=I etc to copy values into the procedure's
IN and INOUT parameters, then use CALL to call into it.
A processor will examine ASM+ files to look for CALL, IN, OUT, INOUT,
FUNC, and PROC commands.


The first peephole optimization step would try to fold constants,
combine copies together (so that they're all done at once), and combine
separate macros into specialized combined macros (like the ones listed
above). Example:  I--; IFI==0  becomes  I--==0
I:=I B, #0   becomes  CLEARI B

The second peephole optimization step would try to optimize combinations
of assembly instructions to eliminate extra work.
For example: LDA #!XXX; STA ?A; LDA #?B; STA ?C ; LDA #!XXX becomes
LDA #?B; STA ?C; LDA #!XXX; STA ?A;
so loading sets of variables with constants is faster.
For example, if the constants are <256 this would combine the high byte 0s.
If the constants were identical (say 5), similar approaches could
combine all the loads into pretty reasonable items.

{{{
JSR X ; RTS => JMP X
}}}

Two peephole steps could be used - one to see "wider" areas of code
(collections of copies, etc.), and the second one to cover
special-case asm instructions, etc.
As a quick-and-dirty implementation, lex/flex or a regular expression
engine could be used to implement the peephole optimizations.


Now for the "Simple" language.
It is to generate the ASM+ language.
It's designed to be simple to parse (probably by recursive descent or LL(1),
since they're easy to build & small).
It would be easier to create if, at first, the language were VERY restricted.

The syntax I've put down is very C-like, but with some Ada & Pascal
influences. Ideally, with the "right" definition files or simple text
preprocessing, it should compile on a stock compiler on other machines.

The syntax should also fit within the target machine limits.
For example, old Apple II's can't generate curly brackets ({}) or
underscores (_). I would substitute the dollar sign ($) for _, and
use [] instead of {} - again, to support self-hosting.

As far as parsing it goes, recursive descent is often easy to understand,
but I suspect an LL(1) parser would be better (see Fisher, page 120).
Eventually it'd be good if Simple were written in itself, and using an
LL(1) parser driver would mean that recursion wouldn't be necessary
(which would be an expensive operation in Simple).
Also, a table-driven parser would be much smaller (inserting comparisons
everywhere would make the compiler large) & according to Fisher they
tend to be faster too (that's surprising).
The table could be used to at least list what are legal tokens where
an error occurs, and for LL(1) it's easy to add an automatic error repairer.

Down the road, it'd be better if there was a way to specify that
some parameters get passed in a register, and/or fix certain addresses.
This could be used to reduce link-time, -- precompile large modules, and
could be used to create really nice interfaces to underlying OSs.
While it might be difficult to generate code that used the params in
registers, it'd be useful to low-level routines -- allow direct calls to
assembly-level procedures.

{{{
File = External_Statements*

External_Statements =
Global_Declaration |
Subprogram_Definition

Global_Declaration =
["private"] variable_definition


Subprogram_Definition =
( "function" | "procedure" ) identifier [ "(" argument_list ")" ]
}}}

Here's a sample Simple program:

{{{
private char current_x, current_y;

procedure move$cursor(in char x, in char y)
[
int b = 0;
// Move the cursor to the new position x, y.
x++;
y += current_y;
b += 0x1fff;
];
}}}

Which would generate the following ASM+:

{{{
MODULE LOCAL$FILE
PRIVATE-BYTE LOCAL$FILE.CURRENT_X
PRIVATE-BYTE LOCAL$FILE.CURRENT_Y

PROC MOVE$CURSOR
IN X,1 ; second parameter is size
IN Y,1
ALLOC B,2
; so far we've just been allocating space. Here's executable code!
IZERO B
C++ X
C+=C Y, CURRENT_Y
I++ B
; The following should probably deallocate storage in the assembler so
; that entire large programs can be assembled in one pass.
ENDPROC MOVE$CURSOR
ENDMODULE LOCAL$FILE
}}}

Which in the end would probably generate something like the following:

{{{
; Example of Link-generated allocation of storage.
MOVE$CURSOR.X EQU $10
MOVE$CURSOR.Y EQU $11
MOVE$CURSOR.B EQU $12 ; for low byte; also covers $13.
LOCAL$FILE.CURRENT_X EQU $900
LOCAL$FILE.CURRENT_Y EQU $901

; Example of code.

MOVE$CURSOR
LDA #0        ; zero
STA $12
STA $13
INC $10       ; ++ for character.
CLC           ; += for character.
LDA $11
ADC $901
STA $901

LDA $12       ; B += 0x1fff
ADC #$ff
STA $12
LDA $13
ADC #$1f
STA $13
}}}

There's a lot of allocation operations in the intermediary code,
but that makes sense.. the
key to using the 6502 is to allocate scarce zero page resources, and
the key to making a faster assembler is to allocate & deallocate
procedure space so all procedures can be assembled at one time.
There needs to be a keyword that hints "put this in the zero page."
The C "register" keyword isn't quite right, since it's perfectly
reasonable to take the address of such a variable.
Perhaps the right keyword is "zpage".

Probably recursive calls should be marked as "recurse" to note that they're
expensive and that's okay, though maybe not - the compiler in particular
might need to recurse.  Ideally, the compiler/linker combo could
figure this all out automatically (this is quite practical, since the
linker has to determine the call tree any for allocation purposes).

Procedures-in-procedure support could be added later. That's easy as long
as they don't recurse - simply reference the address of the object.

Various other words as compiler hints (like "register" in C) would be
helpful, esp. for the loops (so that the X or Y register can be used as a loop
register where appropriate).
Such keywords probably include ZPAGE, REG{A,X,Y}.
Perhaps FOR REGX I := 10 DOWNTO 0 {by 2} DO ... ENDFOR;
could become
{{{
LDX #$0a
; if constant start, don't need to check here!
.1
...
DEX
BPL .1
}}}

Probably it should support modules (like C, based on files), header
files (maybe add a C-like macro expander?), etc.

Note one odd thing: in a big program, it might be efficient if the
tightest loops are in separate subroutines called by others; that way,
since they're lower in the tree, they're more likely to get zero
pages assigned to them.


CC65, a freeware C compiler for 6502s, has a "-static-locals" option.
This option lets locals be in static locations, and they correctly
note that this produces faster code but doesn't permit it to be
re-entrant.  However, it doesn't appear that CC65 takes advantage
of allowing function parameters to also be passed statically, nor does
it exploit the approach discussed here to allocate so that copying
(e.g., to parameters) is only notional and doesn't actually occur in the
code itself.  CC65 appears to be open source software,
and is available at: http://www.cc65.org
CC65 normally takes a different approach (based on the older SmallC);
it uses the A and X registers as a register, and pushes parameters on
a small stack through multiple JSR's (that are simple to implement as
a compiler, but not really very efficient).


Then a small text editor could be built, both to use these things
(eventually the Simple compiler, linker, and ASM+ assembler
should be self-hosted) and to show how to use these things.

It would probably have a buffer module (for storing the text) and a
display module (to take what's in the buffer & display it).
If text has been modified, move it to a line buffer internally so that
inserts & deletes don't move everything.
Allow cursor motions keys like wordstar (control ESDX), delete previous
letter, move around like emacs, find (control-F?), and ESC back to a menu
for saving, loading, cataloging, help.  Two option sets: one for normal
text vs. one for programs, and a general host-based one (shift key mod, etc).

The key here is to have a basic, easy-to-use text editor; one didn't
come with the Apples, oddly enough.


! SOLUTION 2: FIXED LOCATION DATA STACK

This approach depends on fixing the location of the data stack,
but spreads the lower and upper bytes to different locations
(possibly different pages) instead of having the bytes be
adjacent in the memory space.  It would work nicely for
Forth, C, etc.  The trick is that the upper & lower bytes of multibyte
values aren't stored contiguously in memory, but are instead "spread"
into parallel pages; this trick increases the available space significantly,
makes stack movement code faster, and increases safety.
IE, you have "all data stack low bytes" continguous,
and "all data stack high bytes" continguous if you
allow 2-bytes of data on your stack.

Though it's the normal 6502 convention, there's no REQUIREMENT to
store 16-bit values in the order of "lower 8 bits", followed
immediately by "upper 8 bits".
The upper & lower bytes could be separated by a standard
distance (e.g., 256 bytes) instead.

If you create fixed positions for the array of "lower bytes" and
the "upper bytes", as long as there aren't more than 256 elements, access
is easy. Simply set the X or Y register to the index, then use
the "address,X" or "address,Y" access mode to get or store the
lower & upper byte of whatever you want.
Of course, the address+X shouldn't cross pages, since this would
slow down access on an already slow machine.

Thus, the X or Y register becomes the stack pointer, into a stack
that might use 2 pages.

For data stacks (necessary for Forth, C, etc),
this works out particularly well. This means that if you're
willing to live with a 256-element data stack (not completely unreasonable),
you can have a pretty clean & quick interface.
Moving up & down the stack involves a single increment or decrement to
the X or Y register, the cheapest possible operation.
You can also cheaply access operations "inside" the stack by selecting
precomputed offsets, again making access MUCH easier.

I'd earlier toyed with a 128-element data stack, but this
"spreading" approach is easier,
and allows twice as many data elements!
Pushing and popping are cheaper (one inc/dec instead of two, without
lots of carry checks).
This also means that char-vs-int errors aren't deadly (as they are
if chars push 1 byte and ints push 2).
Just use the X or Y register as the data stack pointer, and have two
pages set aside for data (one for low, one for high).
Even better, you could have 4 pages, and long ints can be passed around
without worrying about incorrectly taking them off the stack as the
wrong size! Type conversions between char, int, and long become no-ops,
eliminating a set of dangerous mistakes.

If you want the approach but can't live with only 256 data elements,
you could check on each stack push & pop, and move (most of the) data
elements when the stack got full or empty.
This is slower, obviously.

Conversely, if you're willing to accept a far smaller data stack,
the results would be ESPECIALLY efficient if you slap the
stack into the zero page.  If you normally have to deal with 16-bit
integers, this won't waste any more space, but it saves all the
incrementing/decrementing you have to do to fix up stacks, AND
if there's an error in stack manipulations (a serious problem in Forth)
you'll have far less damage.

You could even combine techniques: use the zero page for the data stack,
with a standard offset. if the stack overflows or underflows
you copy to/from elsewhere.  Having a zero-page stack,
accessed this way, with overflows might give really good performance
for a data stack-based system.

One problem is that the stack can't handle many large
data elements (no local variables with 200 bytes each); I've
programmed on such systems before, and as long as there's a heap
allocation system that's not a serious problem.
The implementation could even put variables beyond a certain size
on the heap automatically.

One design decision: do you keep an X or Y register set nearly all
the time as the stack pointer?  Almost certainly yes, since this
would be heavily used.  If so, do you use the X or Y register, and
which direction do you grow (up or down)?
I'm not _certain_ if the X or Y register is best, nor if
growing up or down is best.  At first I used X, then someone
suggested I use Y, but after examination I think X would be better.
There are some accesses using indirect pointers that are useful
and require the Y register.
Even more importantly, many instructions such as the
incrementing and decrementing instructions can only be used directly if X
is used as the stack pointer; with Y it's more complicated.

Here's a sample. For the stack, the X-reg points to the top of stack,
growing downwards in memory.  Thus X starts large & get smaller as more
items get put onto it.  If it becomes 0, the stack is full.
On decrementing X, you can check to see if it's become negative,
or to be more paranoid you could declare an error if it's zero (X=0).
Set X=$FE (say) as an "empty" value.
To look "inside" the stack, simply use addresses with assembly-time
increments (i.e. no runtime cost!).

{{{
; perhaps alias "LOWSTACK+1" as "SECOND$PARAMETER$LOWBYTE",
;               "LOWSTACK+2" as "THIRD$PARAMETER$LOWBYTE", etc.
; LOWSTACK and HIGHSTACK could be in the zero page, giving less data space
; but more speed and smaller code -- or they could be at the beginning
; of two different pages, giving 256 possible data values.
; Note that the assembly language given here can assemble either way,
; so that could be an easy configuraion option.

ADD-INTEGERS
; pop & add top two integers on the stack.
; pushing result onto stack.
CLC
LDA LOWSTACK,X       ; add low bytes.
ADC LOWSTACK+1,X     ; this is how to look at the "one inside".
STA LOWSTACK+1,X     ; replace 2nd parameter (which will be the return value)
LDA HIGHSTACK,X      ; add high bytes.
ADC HIGHSTACK+1,X
STA HIGHSTACK+1,X
INX                  ; pop the stack (once), leaving result on stack.
RTS

DUP-INTEGER
DEX                  ; push the stack, making room for the new value.
; Always make room for a value first by pushing first;
; that way, the system could support
; interrupts which use this stack too.
LDA LOWSTACK+1,X
STA LOWSTACK,X
LDA HIGHSTACK+1,X
STA HIGHSTACK,X
RTS
}}}

If the stack were always pushed before data was stored on it,
interrupt handling could be well-supported.
This would make it easily possible to create time-sharing on
a 6502 (a frightening thought!).

Obviously, stack-checking code could be inserted too, at some cost
in code size and performance.

In comparison, the FIG Forth implementation available at:
http://www.6502.org/crossdev/lang/index.htm
does use the zero page, but it has to do a little more work to manipulate
the stack (more fiddling with the X pointer to move data around).
Even more importantly, if the programmer makes a mistake, it's curtains
for the data.  Doing this can encourage using single-byte data
(something the 6502 is FAR more efficient at), since it no longer is
as dangerous to use in a Forth system.
The FIG Forth implementation is a word-based intepretive system, which
is slower than a JSR-based implementation (where the Forth words are
compiled into JSR WORD everywhere)... I'm partial to the JSR design due to
its speed, but the approach described in this paper will work with either.

Implementing a C compiler this way would produce less efficient code
that a "Simple" compiler would, in general, since reading or writing
any value requires an indirection using a register (,X or ,Y) instead
of a direct write to memory, and would mainly use non-zero-page
(instead of zero page).  Thus, it'd take more bytes of code, and it'd
be slower to execute.  However, recursive code
would be much easier to handle  - Simple would have to work hard to do it.
Also, implementing this scheme is _extremely_ easy, while doing "ASM+"
right would take a LOT more work.

If I were building a "language shop", this would be a good way to add
a Forth & a C compiler to the "language collection."
Programming languages which are often implemented using a
stack-based language would fit this model easily too
(Java, C#, Python, Perl, PHP, Pascal).
The next trick would be to figure out how to make sure each can call
the others.  Probably not too bad via some special "external language
call" interface, at least no worse than other approaches.
Forth in particular would work nicely in this scheme.

The two different solutions need not be completely independent.
For Simple, using the basic idea implies that integer arrays
(up to 256 elements) could be stored as an array of low bytes, then an
array of high bytes, making access easy.

In fact, it seems like 2 macro languages could be developed -
the ASM+ one above, based on fixed addresses, and a
stack-based macro language, and lots of reuse could occur.
The underlying assembler & peephole optmization system could be the
same, and the same 2nd-stage peephole optimizations might be used for both
(though some optimizations would only be useful in one or the other).

Then you could allow something of the form:

{{{
PROC HELLO            ; proc hello(in int c, out char d)
TEMPS 2               ; use this so can set up space for temporaries.
S-IN-I  C             ; make sure these are in order.
S-OUTI  D             ; the macros remember order to make declaration easy
TEMP-I  E             ; int e;
TEMP-I  F             ; int f;
SZEROI F              ; f := 0;
SI+ E, C, F           ; E := C + F;
SI:= D, E             ; D := E;
SI++ E;               ; I++;
ENDPROC               ; pop off temporaries, deallocate in assembler.

Would generate:
HELLO
DEX                   ; space for E
; stack overflow check if desired.
DEX                   ; space for F
; stack overflow check if desired.
; Now stack looks like: (top/low mem) F E D C (bottom/higher mem)
LDA #0                ; F := 0
STA LSTACK,X
STA HSTACK,X
CLC                   ; E := C + F
LDA LSTACK+3,X
ADC LSTACK,X
STA LSTACK+1,X
LDA HSTACK+3,X
ADC HSTACK,X
STA HSTACK+1,X
LDA LSTACK+1,X        ; D := E
STA LSTACK+2,X
LDA HSTACK+1,X
STA HSTACK+2,X
; Now need to implement E++.  Since
; INC LSTACK+1, Y  is not a legal addressing mode,
; this is a good argument for using X and not Y.
LDA LSTACK+1,X        ; E++
CLC
ADC #1
STA LSTACK+1,X
LDA HSTACK+1,X
ADC #0
STA HSTACK+1,X

.1
INX
INX                   ; pop temporaries. Should params be popped by caller?
RTS
}}}

A few notes regarding incrementing - Geoff Weiss noted that
if you find that you rarely have to increment the high byte, and want to get
better performace from incrementing 8-bit values and add a penalty to the
16-bit operation, use this code:

{{{
LDA LSTACK+1,X
CLC
ADC #1
STA LSTACK+1,X
BCC .1
LDA HSTACK+1,X
ADC #0
STA HSTACK+1,X
.1
}}}

Again, note that implementing "E++" can't be done with the following
code, since it doesn't use a legal addressing mode:
{{{
INC LSTACK+1,Y        ; E++.  This addressing mode is not legal.
; Should use X instead of Y.
BNE .1
INC HSTACK+1,Y
}}}


!! COMPARING THE TWO APPROACHES

Approach #1 takes more work to implement, has the linker do more work,
and doesn't handle recursion as easily, but it has lots of
performance advantages.
Approach #2 is probably much easier to implement, but it has its weaknesses.

Let's examine adding two numbers (ignoring any return) to compare them.
Here's approach #1, adding A and B and placing them in C
(to keep things consistent, I'll only use normal adding and not the
adding that speeds low-only-byte adding while making higher-byte adding
more expensive and adding code):

{{{
ADD-INTEGERS
CLC
LDA A$LOW
ADC B$LOW
STA C$LOW
LDA A$HIGH
ADC B$HIGH
STA C$HIGH
}}}

Here's approach #2:

{{{
ADD-INTEGERS
; pop & add top two integers on the stack.
; pushing result onto stack.
CLC
LDA LOWSTACK,X       ; add low bytes.
ADC LOWSTACK+1,X     ; this is how to look at the "one inside".
STA LOWSTACK+1,X     ; replace 2nd parameter (which will be the return value)
LDA HIGHSTACK,X      ; add high bytes.
ADC HIGHSTACK+1,X
STA HIGHSTACK+1,X
INX                  ; pop the stack (once), leaving result on stack.
}}}

Pulling up the 6502 opcodes (e.g., at
http://www.6502.org/tutorials/6502opcodes.htm), we can compare the approaches.


Approach #1 - all zero page:      13 bytes of code,  19 cycles to run
no zero page:      19 bytes of code,  25 cycles to run
Approach #2 - all zero page:      14 bytes of code,  26 cycles to run
no zero page:      20 bytes of code,  28 cycles to run

Approach #2 is only one byte longer in code because it has to
manipulate the stack at the end.  Approach #1 might have to do
copying, which would take more effort and make it much slower than #2,
but if the linkage overlap idea works well that copying is rare.
Approach #2 is always slower than #1; even when approach #1 can't use
a zero page, it's faster than approach #2 when it's using the zero page.
Is that a problem? Well, it depends.

Although approach #2 has its drawbacks by this measure,
it's much easier to implement, and there's something to be said
for easy.. no fancy zero-page allocation is required for this stack-based
approach, so a macro assembler would be able to implement it
(without peepholes, though peepholes would improve the results).
In particular, approach #2 would be simpler for self-hosting.

This solution #2 is also more traditional, so link times
would be much smaller.


!! Notes on creating other languages:

A finalization system would be useful, since a number of
allocation requests could be to compensate for the inability of
the system to have large local variables.
Heck, an automatic garbage collector might be fine - mark & sweep collectors
wouldn't have much to do, since there's not much memory to sweep.

Initialization and adjustment (like Ada 95) would be useful in
eliminating common errors.

Inheritance can be implemented as with C++ or Ada 95.
Dispatching would be little expensive, though; each indirection
would require copying an address into the zero page and using it.

A completely controlled, unbounded-length string type would be very
handy; it would make text manipulation a lot easier.

Obviously, for real efficiency this would need to be combined with
many other techniques.  For example, using registers is even faster,
so using A,X, and/or Y to pass some data is even faster in most cases
(no saving out and writing back).  However, there are only 3 8-bit
registers, and they are needed for other things too, so while using them
in part for parameter passing is a good idea, it's limited in its utility.
PHA and PLA and the zero page can be used to briefly store and retrieve
registers, and there are lots of clever techniques for performance
aids too.

It's critical to use 8-bit (char) values when you can, e.g., for booleans,
because the 6502 is FAR more efficient at them.
Even on the rare cases where Approach #1 has to do a copy, it's far less.
Approach #2 even encourages this, because an error in typing is
less catestrophic.


!! REFERENCES:

``Crafting a Compiler'' by Charles N. Fisher & Richard J. LeBlanc, Jr.
1988. Benjamin/Cummings Publishing Company. Menlo Park, CA.