Any relation to ActionScript?
replies(1):
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.
This comes straight from Algol if I'm not mistaken. It seems weird to us now (tho bourne shell / bash kinda has this in spots) but it was in the air in the 60s/70s.
When I've looked at it in the past I definitely got the sense that Action was very much inspired by Algol-68, but with some accomodations for the niche of 6502.
6502 is a terrible target for C (and even Pascal) compilation, I have often wondered if it made sense for someone to try and revive Action for the 21st century as a general purpose 6502 high level PL.
https://ataripodcast.libsyn.com/antic-interview-111-clinton-...
The Action! language may not have been as advanced as C or Pascal, but because it was designed with the 6502 CPU in mind, compiling the language was astonishingly fast.
The original Atari Pascal system from APX needed multiple disk drives and could take several minutes to compile a small program. The only C package available in 1983 (Deep Blue C) was at least as limited as Action!, but also not an integrated package and compiled slowly. Draper Pascal only compiled to pseudo-code.
Action! compiled your program to machine code in memory and in seconds. Typing C (to compile) and then R (to run) was hardly slower than just typing RUN in BASIC.
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'.
Whether it was the best language for 8-bit programming, it certainly was a great fit for the 6502, as the language targeted the peculiarities of that chip. Accessing hardware-specific features of the 8-bit Atari's was a snap, which was necessary in order to do anything more interesting than sieves or print loops.
Action! probably could've been ported to the Apple line, but 8-bits were winding down by the time it was released. Porting to 16-bit machines like the IBM PC or Mac (or even the Atari ST) would have been a tougher sell, since Pascal and C were better established by that point, and worked well on those machines.
Two bad things about Action!: Charging a license fee to distribute the runtime, and that dumb bang in the name.
Definitely leads to a feeling of velocity. I don't like the language that much but I do get the fun from that feeling!
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).
https://github.com/greggman/rockfall/blob/main/ROCK4.ACT
I've since ported that code multiple times. Once to Gameboy (unshipped, it was just for learning when I was hired to make a gameboy game). Once to C. Once to Java for a feature phone software interview. A couple of years ago to JavaScript
https://www.atariarchives.org/APX/showdocs.php?cat=20166
There were some other weird 8-bit programming languages: PLM and MPL. These are PL/I clones for 8080 and 6800. I used MPL long ago and wrote an article about it:
https://github.com/jhallen/exorsim/tree/master/mpl
PLM was much more popular and better:
However I love the ease of cross compiling and distributing cross compiled binaries that much that Go is still the best tool for some jobs
As in after X recursion, you'd get in trouble as the memory kept allocating new stack frames for every recurse...
It's a nice to have that makes your life easier
Again on System/360, I benchmarked BCPL procedure call costs against subroutine call costs in Fortran G (the non-optimizing compiler). BCPL was about 3 times faster.
That said, as soon as you added multi-tasking (what we'd now call threads), it all went to hell. It's not an accident that one IBM PL/I manual of the 1960s said “Do not use procedures, they are expensive.”
As mentioned by others, it was the tiny stack in the 6502 that killed this approach. I appreciate all those who pine for the 6502, but it made implementing modern (even for the 1970s) languages almost impossible.
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.
What you do is, you do a three-point approximation and a five-point approximation. The difference between the two gives you a fairly good estimate of the error. If the difference is too high, you cut the region in half, and recursively call the same function on each half.
That calling twice is what makes it hard for a while loop. I mean, yes, you could do it with a work queue of intervals or something, but it would be much less straightforward than a recursive call.
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.
> 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.