But Apple Pascal was released for the Apple II in 1979. Based on UCSD Pascal, the Apple Pascal system was basically an OS that simply was an IDE; and it worked perfectly well on 8-bit hardware. I had quite a lot of fun with it back in the day.
Because, yeah, the 6502 is a difficult target for high level languages.
The article is broadly correct. The 6502 had what amounts to a mixed-performance address space. All indirect addressing had to be done via pairs of registers in the zero page at addresses 0-255. Essentially all the "pointers" in your application wanted naturally to live as one of these 128 "pointer registers". But that's not the way natural code generation wants to work, where the pointers get stored in the data memory along with everything else.
So compiled languages need to have some kind of trampoline for every pointer to copy it into the memory where it needed to live, which was a really tall order for the optimizers of 1983.
Or they could just cheat and compile to a virtualized instruction set and feed that to an interpreter. Apple chose this, twice: once with Woz's sweet16 in which Integer BASIC was written, and again with the port of the P-Code interpreter for Pascal.
The 6502 might not have been able to handle Pascal well, but Borland Turbo Pascal for CP/M (z80, 8080, etc) worked very, very well. It was also released in 1983 or so, but dunno whether it or Factor was 'first'.
Even worse, the bytecode was standard UCSD Pascal, designed for mainframes, and not really how you'd design bytecode if you knew you were going to implement it on a 6502.
We can actually compile Pascal / C style languages to the 6502 pretty well these days. The way to do it is treat it the same as a RISC machine with a lot of registers (let's say 32 2-byte pairs in zero page, leaving 75% of ZP for globals and a handful of important runtime functions that benefit from self-modifying code). Split the 32 pseudo-registers up into A, S, T registers the same as you do for any RISC (or x86_64 for that matter).
It's problem to handle recursion. Just the same as any function call, put anything you still want after the function call into S registers, and in the called function if it needs to use S registers then it needs to save them on a stack (NOT the 256 byte hardware stack) first and restore them after. For more than one or two saved registers it's better to use a runtime function for this -- 12 cycles overhead, but lots of bytes of code saved. RISC-V's -msave-restore provides a good model for this.
You can make a nice set of 2-address arithmetic routines between 16 or 32 bit Zero-Page registers by using the X and Y registers to pass which locations to work on.
add16:
clc
lda 0,x
adc 0,y
sta 0,x
lda 1,x
adc 1,y
sta 1,x
ret
...
ldx #dst
ldy #src
jsr add16
For 32 bit arithmetic the time overhead is much reduced. For floating point it would be negligable!
There is no convenient way to make 3-address routines, but `mov16` is only 5 instructions and 28 cycles. Or just 4 instructions (8 bytes) and 12 cycles if inlined, which might be a better tradeoff i.e.
lda src1
sta dst
lda src1+1
sta dst+1
ldx #dst
ldx #src2
jsr add16
ldx #dst
ldy #src1
jsr mov16
ldy #src2
jsr add16
Stack-based bytecode has a whole lot more overhead again to fetch the next instruction and dispatch to the correct code for it. Register-based bytecode would be a much better idea, as it uses several times fewer bytecode instructions, and is more compact to boot (see Dalvik vs JVM ... sad that webasm didn't pay attention).
I agree about the general approach to taking advantage of the zero page, but I don't have the 6502 competency to comment on your proposed instruction sequences.
That's not my experience, and I don't see how it can be true, even theoretically, for typical programs.
I don't at all mind more instructions, if that works out smaller or at least not bigger. E.g. RISC-V using `c.slli; c.srli` or `c.slli; c.srai` (all 2-byte opcodes) to extract unsigned or signed bitfields instead of having a 4-byte "extract field" instruction.
It is true that a stack-based ISA can have a size advantage in evaluating very complex expressions, such as those typical in scientific / engineering computing, when you get a lot of arithmetic operators in a row with no arguments needed.
But in general purpose programs the vast majority of lines of C code have only very simple expressions. `x=x+y`. `x=x+10`. `if x<y`.
Register ISAs provide short addressing for the most frequently-used 8 or 16 or 32 variables in a function (the registers). Experience shows 8 isn't really enough, 32 is usually a little more than you need -- I think some study showed 24 was enough but you don't get a code size advantage from that, so ...
Stack based ISAs do similarly. JVM can load or store any of four local variables within a 1-byte instruction. For more than than you can refer to 256 variables with a 2-byte instruction. Four really isn't enough, but 256 is a waste of code size. WASM doesn't have any option to include a variable number in the main opcode byte -- `local.get 1` is two bytes.
A very typical statement in programs is `x += y`.
JVM 4 bytes:
iload 0 // 1A
iload 1 // 1B
iadd // 60
istore 0 // 3B
WASM 7 bytes:
(local.get 0) // 20 00
(local.get 1) // 20 01
(i32.add) // 6A
(local.set 0) // 21 00
add r0, r0, r1 // 08 44
add a0, a0, a1 // 2E 95
8086, M68k, PDP-11, Super-H, MSP430 can all also do this very common operation with a 2-byte instruction, with anything from 8 to 16 local variables.
Exactly the same analysis applies to `x += 10`.
Most programs consist almost entirely of statements like these, not things like `det = a(ei − fh) − b(di − fg) + c(dh − e*g)`
There are two main problems with stack code:
- you need four opcodes: `load`, `load`, `add`, `store`. Each opcode needs at minimum 3 or 4 bits, so no matter what you do you're going to have 12-16 bits to specify four actions. In contrast, the register machine can just use a single `add` opcode, again using 3 or 4 bits.
- all the common stack ISAs use a minimum of 8 bits for an instruction (even the extremely common `iadd` or `i32.add` and use a multiple of 8 bits for every instruction. Four instructions is going to be minimum 4 bytes.
- the register machine needs only one 3 or 4 bit opcode for `add` AND can pack the other operands arbitrarily into a 16-bit instruction, using whatever field size and position makes sense.
- the register machine needs to mention the dst/rs1 variable only once.
Stack machine code could be improved in size a little if you bit-packed the instructions, but you'll still have the problems of needing more opcode fields and needing to repeat variable names.
Perhaps ironically, some accumulator machines do better. For example the much-hated PIC microcontroller actually does this well:
MOVF 0x21, W ; Load y (from address 0x21) into W register
ADDWF 0x20, F ; Add W (containing y) to x (at address 0x20), store result in x
On the smaller chips each of those instructions is 12 bits (with 32 registers, many with special purposes), though those are very limited and most applications use mid-range chips with 14 bit instructions (allowing 128 directly accessible registers).
So this is 24 or 28 bits of code, still not as compact as the 16 bits for that extensive list of register machines: RISC-V, Arm Thumb, 8086, M68k, PDP-11, Super-H, MSP430.
It certainly does depend on which stack machine. I'm surprised that Wasm doesn't have a one-byte encoding for (local.get 0) or (local.set 0)! As you point out, even the JVM has one. My survey of bytecode instruction sets in https://dercuano.github.io/notes/tiny-interpreters-for-micro... found such an 8-bit or 5-bit instruction in nearly every example except CPython, with a 3-to-5-bit operand field in the local.get and local.set instruction byte, but of course Wasm didn't exist in 02007. The JVM only offering 2 bits is atypically stingy.
RVC and Thumb2 are pretty extreme cases of optimized register-machine encoding, and probably not something you'd want to decode in software on a 6502. The comparable stack-machine code would be something like Chuck Moore's x18/F18A with its four instructions per 18-bit word or James Bowman's J1A.
It also depends, as you say, on the code. Most code is somewhere in between the extremes of x += y and your example of
det = a*(e*i − f*h) − b*(d*i − f*g) + c*(d*h − e*g)
dstRect.bottom := Max(dstRect.bottom,dstRect.top + txMinHeight);
thePort^.grafProcs := Nil; { restore to normal }
if (n != 0 && --n != 0) ...
target_command = entry_i + CAM_CONTENT_COUNT * j;
tfd = open(ptr, O_RDWR|O_TRUNC|O_EXCL|O_CREAT, 0600);
for (size_t i = 1; i < n; i++) ...
if (event == EV_enter_state) ... else if (event == EV_tick) ... else if (event == EV_reenter_state) ...
Subroutine calls in particular are typically a single bytecode once all the operands are on the stack, referring to a subroutine name or address stashed elsewhere with a short literal index, which similarly is usually allocated a 3–5-bit field in the opcode byte. Very popular subroutines like car or #at:put: can get their own bytecode.
There's a bit of a difference between the 8 registers in the PDP-11 or the 8086 and the 3-bit local variable field in an Emacs Lisp bytecode byte. The stack pointer soaks up one of those slots; on the PDP, the program counter soaks up another. (On ARM the link register sometimes is a third. Thumb and RVC do better here by excluding these registers from their 3-bit namespaces.) Analogously, one of the 8 local-variable indices in Elisp is "see next byte". Also, though, stack machines don't need to spend local variable indices on temporaries, and they often have instance-variable-access opcodes as well. So in effect register machines have less local variables than it at first appears.
Incidentally, as that note mentions, Aztec C for the 6502 did support a bytecode interpreter to more than halve code size:
> As an alternative, the pseudo-code C compiler, CCI, produces machine language for a theoretical machine with 8, 16 and 32 bit capabilities. This machine language is interpreted by an assembly language program that is about 3000 bytes in size.
> The effects of using CCI are twofold. First, since one instruction can manipulate a 16 or 32 bit quantity, the size of the compiled program is generally more than fifty percent smaller than the same program compiled with C65 [the Aztec C native code compiler for the 6502]. However, interpreting the pseudo-code incurs an overhead which causes the execution speed to be anywhere from five to twenty times slower.
But I don't know whether it was a stack bytecode, an accumulator bytecode, a register bytecode, or something weirder.
My experience programming in FORTH is that often I can profitably keep about one variable on the operand stack, so accessing that variable takes no instructions and no bytes. In theory this is something that a compiler could do, but the only case I know of is when you store to a variable in Smalltalk inside a larger expression. Similarly it's common in FORTH to spend no instructions on accessing arguments or returning a value; you just don't drop it before returning.
Oh, cool, I'll take a look. Having started with Apple ][ in 1980 I'm already well aware of SWEET16 and admire both it's effectiveness, integration with native code, and small size of the interpreter.
> it's common in FORTH to spend no instructions on accessing arguments or returning a value
Yes, good point. Stack machines might not be good for code inside a function, but they often are good on function call/return, if you can arrange things to not need extra stack shuffling. Again, this matches very well to evaluating complex arithmetic expressions where some of the operations are function calls not inline code.
RISC-V has recent extensions -- so far the RP2350 is the most common chip that implements them -- that optimise function prologue and epilog and marshalling function arguments to S registers and S registers to function argument registers for a call. See the Zcmp extension.
https://docs.openhwgroup.org/projects/cva6-user-manual/01_cv...
Also, Zcmt provides optimised 2-byte jumps and calls to up to 256 well-known arbitrary entry points: 32 jumps and 224 calls.
> RVC and Thumb2 are pretty extreme cases of optimized register-machine encoding, and probably not something you'd want to decode in software on a 6502.
I wan't thinking of 6502. I don't think either JVM or WASM runs there :-) If you're JITing then decoding complexity really doesn't matter much, providing it doesn't increase the VMs code size too much.
I've a couple of times worked on some notes and the beginnings of an interpreter for MSP430 on 6502. I think it can be relatively small and relatively fast. There are very few instructions, and the encoding is very regular. And there is a good optimising GCC for it.
If you're not familiar with it, think "PDP-11 extended to 16 registers and 4 bit opcode (plus byte/word) instead of 3 by trimming src addressing modes to 4 (Rs, @Rs, @Rs+, 0xNNNN(Rs) plus immediate and absolute (ok PC-rel) by punning on PC) and trimming dst addressing modes to just 2 (Rd, 0xNNNN(Rd) plus the punning on PC).
Decoding is fairly 6502-friendly, with the src and dst registers in the low 4 bits of each byte of the instruction, the opcode in the high 4 bits of one byte, and the two addressing modes and B/W flag in the high bits of the other byte.
If you keep the hi and lo bytes of each register in separate arrays in Zero Page then you don't even need to shift the register numbers -- just mask them off and shove them into X & Y registers. Similarly, opcode can just be masked and then shove it into a location that is the bottom half of a modified JMP or JSR, or a JMP (zp), giving 16 bytes of code to get started. Or shift it once if 8 bytes is enough. Similarly, the two addressing modes and B/W flag don't need to be parsed with shifting and masking (at least if you care about speed more than interpreter size), you can just mask that byte and also use a jump table to "decode" it
--
Also, there is an intermediate stage between full interpretation and full JITing. I don't know if you've looked at the "Spike" RISC-V reference emulator. It doesn't normally decode instructions, it hashes them to look up a pre-decoded form with src and dst registers and any immediate/offset decoded into a struct, along with a pointer to the code to interpret the instruction. The hash table size is 8000 and that gets a good hit rate on most code. Of course if there is a hash table miss then the instruction is actually decoded the hard way and inserted into the hash table.
This wouldn't be a good fit for an 8 bit micro (unless you knocked the hash table size down a lot) but would be fine with even 1 MB of RAM.
--
>> The effects of using CCI are twofold. First, since one instruction can manipulate a 16 or 32 bit quantity, the size of the compiled program is generally more than fifty percent smaller than the same program compiled with C65 [the Aztec C native code compiler for the 6502]. However, interpreting the pseudo-code incurs an overhead which causes the execution speed to be anywhere from five to twenty times slower.
I'll just point out again that the native code technique I showed in my original message up-thread cuts a 16 bit register-to-register add down from 13 bytes of code to 7 bytes (or fewer for sequential operations on the same register) at a cost of increasing execution time from 20 cycles to 42 i.e. not a 5x-20x slowdown but only a 2.1x slowdown.
For a 32 bit add it reduces the code size from 25 bytes to 7, and increases the execution time from 38 cycles to 66, a 1.7x slowdown.
Well, I don't know how "native" the native code compilation for C65 is. I'm assuming all operations are inline for speed.
00010448 <fib>:
10448: b570 push {r4, r5, r6, lr}
1044a: 0004 movs r4, r0
1044c: 2500 movs r5, #0
1044e: 2c01 cmp r4, #1
10450: dd05 ble.n 1045e <fib+0x16>
10452: 1e60 subs r0, r4, #1
10454: f7ff fff8 bl 10448 <fib>
10458: 3c02 subs r4, #2
1045a: 182d adds r5, r5, r0
1045c: e7f7 b.n 1044e <fib+0x6>
1045e: 1960 adds r0, r4, r5
10460: bd70 pop {r4, r5, r6, pc}
00010186 <fib>:
10186: b872 cm.push {ra,s0-s2},-16
10188: 842a mv s0,a0
1018a: 4481 li s1,0
1018c: 4905 li s2,1
1018e: 00895863 bge s2,s0,1019e <fib+0x18>
10192: fff40513 addi a0,s0,-1
10196: 3fc5 jal 10186 <fib>
10198: 1479 addi s0,s0,-2
1019a: 94aa add s1,s1,a0
1019c: bfcd j 1018e <fib+0x8>
1019e: 00940533 add a0,s0,s1
101a2: be72 cm.popret {ra,s0-s2},16
Falling back to original 2015 RV32IC (no newfangled extensions) adds 2 bytes to 32:
0001018a <fib>:
1018a: 050002ef jal t0,101da <__riscv_save_0>
1018e: 842a mv s0,a0
10190: 4481 li s1,0
10192: 4905 li s2,1
10194: 00895863 bge s2,s0,101a4 <fib+0x1a>
10198: fff40513 addi a0,s0,-1
1019c: 37fd jal 1018a <fib>
1019e: 1479 addi s0,s0,-2
101a0: 94aa add s1,s1,a0
101a2: bfcd j 10194 <fib+0xa>
101a4: 00940533 add a0,s0,s1
101a8: a899 j 101fe <__riscv_restore_0>
00000000 <fib>:
0: 1a 15 pushm #2, r10 ;16-bit words
2: 0a 4c mov r12, r10 ;
4: 49 43 clr.b r9 ;
00000006 <.L3>:
6: 5c 43 mov.b #1, r12 ;r3 As==01
8: 0c 9a cmp r10, r12 ;
a: 00 34 jge $+2 ;abs 0xc
c: 0c 4a mov r10, r12 ;
e: 3c 53 add #-1, r12 ;r3 As==11
10: b0 12 00 00 call #0 ;
14: 3a 50 fe ff add #-2, r10 ;#0xfffe
18: 09 5c add r12, r9 ;
1a: 30 40 00 00 br #0x0000 ;
0000001e <.L2>:
1e: 0c 4a mov r10, r12 ;
20: 0c 59 add r9, r12 ;
22: 19 17 popm #2, r10 ;16-bit words
24: 30 41 ret
0a 4c mov r12, r10
0: register addressing mode, Word size
a: dst = r10
4: mov
c: src = r12