Generally the loop termination threshold is set at mag(z) >= 2.0. Which means that you could have an iteration which gets to 1.999, does not terminate there, and proceeds to square again, resulting in a magnitude near 4.0. You could also then have the sum pushing in the same direction, for 6.0.

A division by 4096 implies a 12-bit fractional part, and thus that the intermediate result has 24 bits of fraction. You would need a 32-bit integer to hold that.

While BASICs usually do have internal functions, bootBasic does not, and I assume it would take at least a little bit of extra code to implement the syntax handling necessary for it. Additionally, things like CHR$() presuppose the existence of string-type variables. That's why I've gone for a VDU statement rather than PRINT CHR$(). It would probably be easier for me to just perform all intermediate calculations in a wider size than variables are stored, as that doesn't add any real complications.

Another big design decision is the choice of expression parser algorithm. While bootBasic uses a recursive-descent parser, which is conceptually simple and works for the purpose, it's not a type of parser I'm particularly comfortable with, especially on a 6502 with its limited stack space.

Instead I'm planning to use a variant of the Shunting Yard Algorithm, which likes to push operands and operators onto different stacks, from which they can then be popped during execution (or during output as an RPN expression, which is not what we're after). In this case, the zero-page X-indexed stack will be for operands, and the hardware stack can be used for operators since this is an iterative algorithm not requiring recursion. The algorithm does require comparing the candidate operator with the one presently at top of stack, which I can make considerably more convenient by duplicating the latter somewhere in zero page. Thus encountering a lower-precedence operator causes any higher-precedence operators already stacked to be executed before proceeding further.

Usually this type of parser is implemented by supplying a table of operator tokens, their precedence and associativity. However, I've run out of index registers to iterate over such a table while also iterating over the input (with Y) and maintaining the operand stack (with X). So I'll use a decision tree instead, so the PC effectively becomes the iterator for the operator table. I can use the same approach for executing stacked operators.

There are only two unary operators in my planned set, which I would have to expect in contexts where otherwise only a literal is allowed: arithmetic negation and logical NOT. Presently I have negation as part of numeric literal parsing, but I should probably change it to being an actual operator so that eg. various rearrangements of (a*-b) work as expected. By removing negation from literal parsing, I can unambiguously detect the type of token from its first character, which fits nicely with decision-tree lexing. Unary operators tend to have very high precedence, somewhere around the level of parentheses, so they will tend to get executed almost immediately after parsing, as soon as the next operator (following their operand) is encountered.

Speaking of parentheses, these would be a minor special case. Open paren would be treated as having the highest precedence (ie. the usual process of looking for higher-precedence operators on the stack would be bypassed), but would push a very low-precedence operator on the stack to act as a stop for actual operators. Close paren would have a precedence just above this (causing everything within the parentheses to execute), and when executed itself it would just pop the next operator off the stack and verify that it was an open-paren. Actually executing an open-paren operator would also trigger a mismatched parentheses error. At the end of the expression, a pseudo-operator with zero precedence would cause all stacked operators to be executed and pop a pre-stacked stop marker off the stack, then return control to whichever statement executor called it.

I'm reminded of a quote from Woz in a May 1977 BYTE article about the new Apple ]['s Integer BASIC:

It's a tiny bit over my head, but it sounds like you're in good company. When I ported VTL-2 from the 6800 I simply duplicated its evaluator with default left-to-right behavior and a recurse for parentheses. To be honest, I was surprised that my evaluator worked the first try, because it was the part that stretched my understanding to its limits. I still wonder if I did it as efficiently as realistically possible. At least it isn't encumbered by the need to recognize mal-formed expressions, since every string of characters is a "valid" expression in VTL-2. All of the bugs I had to chase down seemed to involve improper care of and off-by-ones for the y register (text pointer).

P.S. Thanks for that little JSR near the bottom of your decimal number printing routine. You saved me three bytes in mine!

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

Thanks Chromatix for taking a crack at a 6502 Tiny Basic that will fit within 2kByte.

Might be worth reviewing some of the deliberate design constraints that separates tiny basic from Dartmouth basic (e.g. ehBasic) as per 1976 Dr Dobbs journal Specification reprint - see page4 onwards
http://archive.6502.org/publications/dr ... vol_01.pdf
e.g. 26 variables signed 16 bit arithmetic, no strings, no for/next, barely any functions, and implemented using an Intermediate Language.

Hence my original questions did anyone ever see or create a tiny basic like versions that does not use an IL that was smaller than Tim Pittman's version. But at the end of the day any 6502 basic which is <2kbyte I won't complain!

PS If anyone knows a URL for People's Computer Company newsletter Vol. 4, Nos. 1,2, 3 let me know.

I read far enough to get to the errata noting that the correct name was Tom Pittman! He did claim to have got his 6800-based version of Tiny BASIC within 2KB of ROM, and it's slightly less constrained in features than the original 8080 version. The 6502 is reputed to have slightly better code density than the 6800, as well.

In this case, I think skipping the IL will help to make it smaller in the final analysis. The IL was intended to make Tiny BASIC more portable rather than smaller. Obviously a bunch of space is taken up by the IL interpreter, and then more space is taken up by the implementation of a BASIC interpreter in the IL. The upside was that the IL could be ported to most CPUs of the time without needing to understand much about how a high-level language parser and interpreter works, and the whole thing remained compact enough to run in the constrained memory space typically available then - and, importantly, to not take an excessive amount of time to load from (often paper) tape.

I still have the paper tape of Tom's Tiny Basic for the 6502, no tape reader though!

Please share a photo!

FYI Post 2 of this thread has a copy of Tom Pittman's Tiny Basic, reverse engineered by BillO, which takes about 2.5kbytes

By request This is the leader to the fan fold tape!

Thanks!

Very cool - If anything deserves to be in the Nostalgia sub-forum, I say this is it!

Here's a nostalgia photo from my own collection... some of the gear I rigged up back in my KIM-1 days!

And yes I had Tom Pittmans' Tiny Basic up and running. I ordered the tape by mail, probably in response to an ad in Byte magazine.

-- Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

These days you can make a paper tape reader using LEDs, phototransistors, and Schmitt trigger gates. Once adjusted, it should be a matter of carefully pulling the tape through by hand.

And if you invert the sense, you can make new tapes by printing out strips and joining them together - no chads, hanging or otherwise.

I made a bit of a breakthrough last night, as I had been trying to work out whether I could do 32-bit internal operations, or whether I'd have to limit them to 24-bit. The problem was the availability of fixed-location zero-page space, which I needed to be able to operate on values efficiently while using the X register for counting. To hold three 32-bit values, which I would need for multiplication and division, I would need 12 bytes, which was potentially a problem for finding space in the high half of zero-page.

Then I remembered that the NMOS 6502 doesn't have PHX and PLX anyway. I would have to transfer the X register via A to save and restore it. That's two extra instructions, consuming two extra bytes of overhead for a total of four. But using one byte of fixed zero-page space as the counter instead of X has only three bytes of overhead - a store instruction, and an address byte added to the decrement instruction. This is slower, but smaller.

I would then have X still holding the operand stack pointer, and thus two of the values could remain on the operand stack, requiring only 5 bytes (one 32-bit value and the one-byte counter) to be found in the fixed zero-page area, which is easy. So this method is both one byte smaller in code, and more flexible in addressing so I save memory in a critical area as well, as well as saving more code otherwise required to move those values around. (NB: with the X register I can effectively perform stack-relative addressing with all the major ALU instructions, which I can't do with the 6502's hardware stack; that feature only arrived with the '816.) This is an important architectural decision which will make implementing the rest of the interpreter more straightforward.

Nice - a hidden benefit of zero page (hidden in the sense that it doesn't jump out, but it's a very practical use.)