TL;DR:
As explained on Steven Weyhrich's great and authoritative Apple II History Site, Wozniak simply sat down and wrote his Integer-BASIC (*1) on paper, while assembling it at the same time by hand. In his own words:
I had no assembler, that was another thing. To use an assembler, they figured that somebody was going to buy this processor to use for a company, and their company can pay a few thousand dollars in time-sharing charges to use an assembler that was available in time-share. I didn’t have any money like that, so a friend taught me that you just sort of look at each instruction, you write your instructions on the right side of the page, you write the addresses over on the left side, and you then look up the hex data for each instruction–you could assemble it yourself. So I would just sit there and assemble it myself. The BASIC, which we shipped with the first Apple II’s, was never assembled – ever. There was one handwritten copy, all handwritten, all hand-assembled. So we were in an era that we could not afford tools.
This quote is taken from a transcription of a speech Wozniak held at he Apple World Convention in 1986. See here for the section about his BASIC.
The Question
Was this simply a high-level concept, actual machine code for the 6502, or an actual implementation on a different system?
Actual machine code on paper for the 6502. (*2,*3)
Was the development only on paper, or was a host computer involved (possibly at his work at HP)?
On paper. A computer was used to test the implementation of the stack machine evaluating expressions. It was written in ALGOL. In addition it is mentioned that he used a HP calculator as well to get used to stack-'thinking'
Did he test it elsewhere before putting it on the Apple 1?
Only on the Apple 1 - they didn't had the money to buy computing time for a cross assembler, as he mentions.
How was this possible?
While it's not a job for an extended weekend, writing a BASIC is not as hard as some may think. To start with, a BASIC is at the core a rather simple program consisting of a few fixed parts like
- A line editor
- A cruncher (tokenizer) (*4)
- A fetch and execute loop
- An expression evaluator
- Memory (variable) access
- (Garbage collection *5)
- An error handling/output function
- Startup (cold boot) and recovery (warm boot)
Each of them are rather short tasks and can be written down independent. Some just a few lines, some may require a up to a hundred instructions.
The rest of an interpreter is
- a collection of functions
One for every BASIC command, every Instruction and every function. They are what the fetch and execute loop calls with every found token, which brings the last two parts:
- A list of all commands, instructions and functions to be searched and pointing to its entry point
- A list of error codes/messages
All of these parts are on their own quite manageable on paper and by hand. To give some rough numbers (*6), Integer BASIC occupies 6 KIB of code made up from about 2000 instructions (plus a bunch of tables). With over 50 user visible commands and function this would already average to less than 40 instructions per function. In reality most are way shorter, like PEEK or POKE being 4 instructions each. Even complex one like GOSUB and GOTO are only 14 and 26 instructions.
Programming is about organization of your task, BASIC is not only no exemption to this, but a perfect candidate due the way it operates. Or in his own words:
It was a very efficient approach that broke up a large task in a very orderly way.
*1 - The name Wozniak used, at the time and for the Apple 1, was Apple BASIC, but to a wider audience it was only introduced way later and with some extensions for the Apple II, now named Integer-BASIC. By now the term Apple BASIC is more closely associated with Apple's Microsoft dialect Applesoft. Thus the term Integer-BASIC is used thruout the answer, despite being not all exact.
*2 - Since he did it in 6500 assembly, it can be assumed that this happened after acquiring a first 6502 at Wescon in September 1975. What's interesting is that despite having a 6502 and writing a BASIC in 6500 Assembler he still made the board to accept a 6800 as well.
*3 - 6502 Assembler is rather easy to translate by hand, as every mnemonic plus addressing mode equals a single opcode and parameter encoding can as well be directly made according to addressing mode. No complex encoding to manage, like on a 8086 or 6800.
*4 - Optional, but Woz did add it to save on RAM.
*5 - Usually, but Integer BASIC worked without.
*6 - These numbers are taken from Integer BASIC for the Apple II, which is the only one I had a disassembly at hand). The original Apple 1 BASIC is only 4 KiB and had about a dozend functions less, but the basic considerations match.
