This page has some information on implementing computer languages (beyond ordinary assembly language) on the extremely old and obsolete 6502 chips. I still find it to be an interesting intellectual challenge, even though it has no commercial use that I know of. Many programs for the 6502 were written in assembly language, because it was difficult to efficiently implement high-level languages on the 6502. People certainly use higher-level languages on 6502s, but I often wondered if there were better ways to handle them. I focus slightly on Apple II-based systems, but not much; for development, a 6502 is a 6502.
There's lots of general information on the 6502; here's a summary of the 6502 instruction set. The Virtual 6502 will let you do some quick playing with their assembly language via a browser. Warning: There's lots of variation in assembler syntax; this one that requires zero page accesses be specially marked with "*".
Ideally, a language could be self-hosting and interactive (allowing redefinitions on the fly), but also cross-compiling (emphasizing "best possible performance" and a nicer environment), and would let you do speed vs. space trade-offs. For self-hosting, a small size has value (so that there's room for other stuff!).
Note: I strongly prefer open source software for development tools, especially in this case since there's no possibility of long-term support, so I'll specifically warn away from problem licenses if I know about them.
Here is a discussion on approaches to implementing languages on 6502 chips, which discusses several fundamentally-different approaches to implementing languages on the 6502. The 6502 is not easy to generate good code for, and I think these approaches produce better results than the "obvious" approaches used by most.
Here is some demo code for the first approach, creating overlapping memory locations for use as local variables and for parameter passing (to and fro). (GPL). Using overlapping addresses works around the limited memory, inefficient pointer/stack manipulation routines, and 8-bit registers of the 6502.
Below are various other options. Forth, Action!, and Slang are especially interesting (for different reasons) if someone wants to create/improve new implementation approaches. 65CM is also very interesting, especially for self-hosting; they greatly limit the language, but as a result make it trivial to compile.
Forth is a remarkably useful language if you intend to self-host useful and fast programs on an 8-bit system; it's relatively fast in execution, fast to develop in, powerful, and easily fits in tiny spaces (say, 8K for the Forth system and at least 1K of RAM to create new definitions). You have to get your head around reverse Polish, and be prepared for disaster if you don't put the right number of parameters on the data stack. Forth normally doesn't keep track of how many data values its words consume or produce, so programmers have to keep track (!). (If you don't use locals, it's even trickier; Gforth's locals and ANS Forth locals can make it easier to program in Forth, and there's a a short implementation of {...} local variables that makes Forth programming easier, but it creates inefficiencies if the compiler doesn't do any optimizations.) In my mind, Forth forces humans to switch to a less-common syntax (reverse polish), making the human be the "parser", and almost no error-checking; in return, you get a simple, powerful system (Forth's ability to return multiple values from a single function is more capable than C's). Starting Forth is the classic text for learning Forth; Thinking Forth is good as well. The original "fig-FORTH 6502" was released to the public domain in September 1980, though it did require that you include the notice in further distribution. (its assembly code listing states "RELEASE 1.1 WITH COMPILER SECURITY AND VARIABLE LENGTH NAMES ASSEMBLY SOURCE LISTING"; the assembly listing states that "This public domain publication is provided through the courtesy of Forth Interest Group, P.O. Box 1105, San Carlos, CA 94070. Further distribution must include this notice. FORTH INTEREST GROUP * * * * * PO. Box 1105 * * * * * San Carlos, Ca. 94070". It took me forever to track down its legal status; back then, many people didn't concern themselves about legal statements, which makes things painful to deal with in today's lawsuit-happy times. In general, FIG released code to the public domain, as you can see by their covers, and since they are the ones who made the official releases, I think it's reasonable to rely on the front covers that say that they are "released to the public domain". Here's the FIG-Forth assembly code as PDF, showing that it's released to the public domain which lets you verify that it really is in the public domain. Here's my local copy of the FIG-Forth PDF page to verify this, in case that goes away. There's also an Apple II-specific version Here's a zipped version of FIG-FORTH for the (generic) 6502, and here's the FIG6502.ASM assembly code for FIG-FORTH for the 6502 as text via wrodiger's copy of FIG-FORTH for the 6502. Here's the set of related PDF files, including the Apple II version. Why Forth isn't slow discusses why Forth is remarkably fast; he determined that Forth had about a 29% overhead compared to similar assembly, which is remarkably small (there are BIG caveats with that calculation, but the point is that the overheads are relatively small). (A direct threading implementation would probably be better than fig-Forth's indirect threading, but I digress.)
It would be easy to switch FIG-FORTH over to a split stack that stores low-byte/high-byte on the zero page as separate ranges (my approach #2). This would create lots of efficiency improvements: pushing and popping are shorter operations (1 operation instead of two, every time). Also, although this would make it slightly nonstandard for Forth, logical calculations and checks could use a 1-byte value and ignore the "high" byte, speeding/simplifying things further. You could have many other 8-bit operations too, which would speed things up. ANS Forth specifies a minimum of 32 cells of Parameter Stack {64 bytes, easily fitting in zpage} and 24 cells of Return Stack {usually this is the page 1 return stack} (Brad Rodriguez prefers 64 cells of each). (By having the TOS be 2 bytes in zpage, you can still use the TOS easily as a pointer.)
Forth Interest Group (FIG) and Silicon Valley FIG has more info. Here's a partial list of Forth implementations. Papers about efficiently implementing Forth include "MOVING FORTH: Part 1: Design Decisions in the Forth Kernel" by Brad Rodriguez (a great paper), Threaded Code Variations and Optimizations by M. Anton Ertl, Threaded Code, "Evolution of Forth"'s discussion of future directions, "Threaded interpretive systems and functional programming environments" by Harvey Glass, ACM SIGPLAN Notices, Volume 20, Issue 4 (April 1985), pp. 24-32 (ISSN:0362-1340) and of course Wikipedia's article on threaded code. Forth meta compilation is not only interesting - it helps you understand Forth innards. Forth's advantages don't do much for systems with a Gig of RAM, and its disadvantages (difficult-to-read, little error-checking, etc.) have made it all but disappear from modern systems, but there's much positive to say about it for the 8-bit world. Stack machine briefly introduces the theory behind stack machines. Updating the Forth Virtual Machine (Pelc) has a discussion of interesting additions to the traditional Forth VM as is often implemented today.
Ron's Software Page has interesting things, including QForth; Geocities may disappear soon, so here's a backup copy; here's pre-extracted text of mini-QForth. The backup copy was obtained by doing "wget --recursive --convert-links --page-requisites --no-parent --no-host-directories http://www.geocities.com/oneelkruns/".
SPL is a Forth-like language that is implemented in plain Python and generates 6502 assembly code.
The big problem with Forth is that it's entirely postfix, which many people find hard to read. What can be done about that? Interestingly, several people have developed infix versions of Forth, which might produce the best of all worlds... the readability of more traditional notations, and the speed + small size of Forth. "An infix syntax for Forth (and its compiler)" by Andrew Haley (Red Hat) (2008) describes a nifty reader; "Infix Forth is not a translator from some other language to Forth, but an infix form of the language that doesn’t change its semantics."
I think that a programming language could be devised that combined the efficiency/simplicity of Forth implementations with more traditional syntax.
PyMite implements a Python subset for 8-bit systems; I can easily imagine this working for a 6502.
CC65 (6502 C compiler) exists, it's a descendant from Small-C. It's not open source software (it predates general awareness of licensing issues), unfortunately. It implements a fairly wide range of C, but the code it generates is inefficient. The "Internals doc for CC65" explains how it works (and why it's inefficient). In CC65, "The program stack used by programs compiled with CC65 is located in high memory. The stack starts there and grows down. Arguments to functions, local data etc are allocated on this stack, and deallocated when functions exit... the return address goes on the normal 6502 stack [page 1], *not* on the parameter stack... the AX register pair [is] the primary register. Just about everything interesting that the library code does is done by somehow getting a value into AX, and then calling some routine or other..." It then shows a calling sequence for i = baz(i, c); where i and c are global variables; it doesn't show what you to do work with the parameters, but it's nontrivial.
HyperC (for ProDos) is interesting; they added a "var" prefix for variables like Pascal (though if implemented using pointers, this could be quickly inefficient since pointer manipulation is painful on 6502s.. but if implemented using my approach #1 that'd be nice). They also added a "@address" statement, so you could allocate exactly where a variable would go. HyperC supports K&R C, not ANSI C, and omits stuff like scanf().
I briefly used Manx's Aztec C; it was awful. It generated bad code, and was a pain to use.
It's definitely costly, Micro/C compilers (based on C-Flea (see also here) is a C compiler based on C-Flea, a small virtual machine for C.
65CM implements a "pretty assembler" language for the 6502 (GPL). It's designed so that the compiling is run on a PC, and the resulting code is sent to the 6502. 65CM handles 2 types of variables (BYTE and WORD), and supports inline assembler. It's not high-level at all, so be prepared for that. What it calls "expressions" are actually constant expressions (they can't have any variables), the IF statement must be of the form:
IF VE1 ( '=', '<>', '<', '>', '<=', '>=' ) VE2 THEN
...
ENDIF
where "VE1" and "VE2" must be a variable name or a (constant) expression.
Similarly, you can make calls using:
GOSUB {Variable (pointermode) OR Expression (Address) OR Label (Internal)}
[ PASSING {Variable} AS ACC {Variable} AS XREG {Variable} AS YREG ]
You can assign a variable a value:
LET {Variable} = {Variable OR Expression}
But if you want to add something to the variable, that's another statement:
ADD {VE1} TO {VE2} GIVING {VE3}
"The COMFY 6502 Compiler" by Henry G. Baker (Nov. 1997) describes the COMFY language (and the paper includes the source code!). It is "intended to be a replacement for assembly languages when programming on 'bare' machines", but intentionally has a LISP-based syntax.
"COMFY-65 is a `medium level' language for programming on the MOS Technology 6502 microcomputer [MOSTech76]. COMFY-65 is `higher level' than assembly language because 1) the language is structured- while-do, if-then-else, and other constructs are used instead of goto's; and 2) complete subroutine calling conventions are provided, including formal parameters. On the other hand, COMFY-65 is `lower level' than usual compiler languages because there is no attempt to shield the user from the primitive structure of the 6502 and its shortcomings. Since COMFY-65 ismeant to be a replacement for assembly language, it attempts to provide for the maximumflexibility; in particular, almost every sequence of instructions which can be generated by an assembler can also be generated by COMFY. This flexibility is due to the fact that COMFY provides all the non-branching operations of the 6502 as primitives."COMFY-65 is implemented in Emacs Lisp; it's not clear how hard it would be to create a self-hosting version. Any LISP might be aided by my readable LISP work. Here's a background paper on COMFY. (Henry Baker has many other interesting papers, too.) There's a git-able version of COMFY-65; unfortunately, it's not open source software (not even slightly!), due to ACM licensing nastiness. That's unfortunate.
I should definitely mention Sweet 16, the "pseudo microprocessor" implemented by Steve Wozniak. (Here's the SWEET-16 Wikipedia article). It simulates a simple 16-bit microcomputer (handy when you need to do a lot of 16-bit operations) with 16 registers, running about 10 times slower than native code but taking far less space (each opcode takes 1 byte, and the whole interpreter takes about 300 bytes). Many Apple assemblers include support for Sweet-16. Unfortunately, the rights to use its original implementation aren't entirely clear. Apple, even in its heyday, encouraged it use in programs. Since it was was copyrighted by Apple in 1977, its copyright should have expired in 2005. That's because the U.S. copyright act of 1976 didn't take effect until January 1, 1978, and the previous copyright term in the U.S. was 28 years plus another 28 if renewed. I doubt Apple would have renewed its copyright, since this was not a money-maker by 2005, so it should have gone to the public domain. (This is also true for Applesoft Basic, which was released on cassettes in 1977). Unfortunately, a 1992 revision to the copyright laws automatically renewed all copyrights after 1963. I find this absurd; how are innovators supposed to innovate if essentially everything created is walled-off?
Atalan is a new assembly-like language for 6502s. I have no info on licensing.
Here's a list of several 8-bit LISP implementations.
There's more that can be done; Lisp was originally developed in 1965, on even smaller systems. The book "Lisp in Small Pieces", Program Transformation in Lisp, this Scheme page and these details on implementation are all of interest. R. Kent Dybvig's "Three Implementation Models for Scheme" shows how to implement Scheme while still keeping most stuff on the stack.
I know that there was an "InterLISP 65" available for Atari's 6502-based line.
Various full LOGO implementations were available as well.
Of course, many people used BASIC and Pascal (esp. UCSD Pascal). That's well-documented elsewhere.
UCSD Pascal is now available for non-commercial use, including its source code. (It is not open source software, as misleadingly stated.) UCSD had its own P-code system, which let a lot of code fit in little space. It wasn't fast, and the only "fast" escape was to write assembly. UCSD Pascal also required you to use its operating system, which was a problem for self-hosting systems that needed to interact with the rest of the world. UCSD Pascal was very useful, and many programs (including the first Wizardry!) were written in it. The fundamental problem with UCSD Pascal is that its opcodes weren't designed to be easily-supported by the 6502; instead, its goal was cross-system portability. As a result, any 6502 implementation of them was going to have trouble, in part because all stack-based operations on the 6502 were slow. This discussion about p-code and Sweet-16 notes this difference - Sweet-16 was designed to be easily-implemented by the 6502, and thus was a nicer fit to the 6502.
In theory it wouldn't be hard to at least create a better version of BASIC (e.g., add stuff from True Basic like real subroutines) to run on these things.
Slang is a very very interesting 6502 language, currently for the Commodore 64. It is more like a "clean Basic" than anything else - full expression handling, structured "if" and loop constructs, and so on. It handles subroutines by separating the call from the argument-passing, which is a little unfortunate but understandable. Its approach to handling local variables is very straightforward; since they go in and out of scope, that is used to assign specific locations (a simple and clever approach). It's a big compiler, so probably can't often have the compiler and the running program resident simultaneously. Overall, this is a nice approach, way better than the typical Basics that came with 6502s (both in language cleanliness and in speed of result). I can't find any licensing info.
Action! was a popular self-hosting programming language for Atari 6502-based systems. It was reasonably readable (its syntax similar to ALGOL 68). Wikipedia notes that "Action! is significant for its high performance, which allows games and graphics demos to be written in a high-level language without use of hand-written assembly language code. Action! language constructs were designed to map cleanly to 6502 hardware." "Local variables are assigned fixed addresses in memory, instead of being allocated on the stack. This enables tight code to be generated for the 6502, but precludes the use of recursion." {Note: Action could have added a "recurse" keyword, as I noted my text about implementation, which would have then supported recursion but only where it was needed, so that only functions that could eventually produce a call to themselves would have to pay the price. Effectus is a cross-compiler on Windows that targets Atari 8-bit, and is intentionally similar to Action!, but I don't see any source code available at all (it certainly doesn't appear to be open source software).
In both cases, a few small extensions to support recursive functions (e.g., a "recurse" statement to mark them, so that calls must save the old arguments and local variables) would make them efficient yet easy to use, and permit self-hosting. (Even if a function is recursive, noting simple self tail-recursion would be easy, and would be worthwhile since saving variables is expensive.)
The Amsterdam Compiler Kit is a "cross-platform compiler and toolchain suite that is small, portable, extremely fast, and extremely flexible. It targets a number of low-end machines [and] supports several languages, including ANSI C, Pascal and Modula-2". It has (or at least had) support for the 6502. It dates back to the early 1980s, and was originally developed by Andrew Tanenbaum and Ceriel Jacobs as a commercial product and used as Minix' native toolchain. "After eventually failing as a commercial project, it was made open source under a BSD license in 2003 when it looked like it was going to be abandoned and the code lost... The ACK contains compilers for ANSI C, K&R C, Pascal, Modula-2, Occam 1, and a primitive Basic." Its intermediate language "EM" is a stack-based language; here is the technical description of EM.
If you want to go elsewhere to see related pages, feel free to look at other locations such as www.6502.org (general site on the 6502). You can also find reference material on the web, such as the 6502 opcodes. Bob Sander-Cederlof's newsletter Apple Assembly Line was filled with useful information. Here's a list of 6502 bugs (important if you're doing assembly!).
The Apple II Programmer's Catalog of Languages and Toolkits has a long list of development tools. Apple8 languages has lots of downloads for Apple II development languages. Here's another list of 6502 development tools.
It's not directly 6502 assembly, but High-Level Assembler (HLA) for 80x86 is interesting, and might have some useful lessons. The HLA manual explains the rationale for a "high level" assembly language.
You'll need to transfer files to and fro; this is tricky with Apple IIs because they have an unusual disk format; ADTPro and its cousin ADT can help. Syndicomm has Apple // boot disks available. NuLib can handle various "shrunk" formats.
I've provided this information to world in memory of Bob Pew, an old friend who died in 1994. Bob, you're missed.
Feel free to See my home page.