Yet another small BASIC interpreter for the 6502

[BillG]

barrym95838 wrote:

drogon wrote:

Most (at least in the 8-bit world) have just a line number and end of line token, or line number + length. The latter is in my TinyBasic - so GOTO/GOSUB involves a linear search, but at least it can skip lines as it knows their length.

I added the length feature to VTL02, and included a condition that would allow "find" to start the linear search at the next line rather than the first line, making forward "GOTO"s less clunky. It worked so well that I decided to re-use it to find the next line during normal execution as well, at the expense of a handful of clocks.

Does that work well enough to also store the length at the end of each line to speed up the search for a lower line number?

You would need to structure it as:

<previous line text><CR><prev length><current length><current line text><CR>...

[drogon]

BillG wrote:

barrym95838 wrote:

drogon wrote:

Most (at least in the 8-bit world) have just a line number and end of line token, or line number + length. The latter is in my TinyBasic - so GOTO/GOSUB involves a linear search, but at least it can skip lines as it knows their length.

I added the length feature to VTL02, and included a condition that would allow "find" to start the linear search at the next line rather than the first line, making forward "GOTO"s less clunky. It worked so well that I decided to re-use it to find the next line during normal execution as well, at the expense of a handful of clocks.

Does that work well enough to also store the length at the end of each line to speed up the search for a lower line number?

You would need to structure it as:

<previous line text><CR><prev length><current length><current line text><CR>...

It's akin to linked-list vs. doubly linked-list data structures - the programming burden (code size, testing) vs. simplicity and smaller code. In traditional memory constrained 8-bit systems, I suspect going for smaller code and simplicity is a bigger win... (or maybe the writers of them back in the 70s and early 80s just didn't have the knowledge then?

My "big" BASIC (written in C) does a pre-run-time fix-up and scans the code for GOTO/GOSUB references and replaces them with a token containing the address of the line, so no searches during run-time. This also means no GOTO {expression}, but I can live with that as you can code mostly line-number free if desired.

I think there was an Atari Basic that did this sort of pre-run-time scan to speed it up too, but I may be wrong...

-Gordon

[barrym95838]

drogon wrote:

Would the overhead of saying "is the target greater than the current line number, or less than or equal?" and picking the appropriate algorithm worth the time to do the test and the extra RAM needed (in a minimal RAM system) ?

I think you might need a good selection of old BASIC programs to find out...

-Gordon

I got the idea from a certain Mr. Gates. I think that the only way for a human to notice the difference would be to run some rather large programs with a bunch of loops, like "Super Star Trek" or similar. I have a version that is stalled in the fixed-point navigation routines ... and has been for some time.

Some of these performance features that weren't in Frank's original 6800 implementation came after my realization that I wasn't going to fit VTL02 into 768 ROMable bytes at my coding skill level. I changed my goal to 1KB or less and used that extra breathing room to add a few features, like proper cold initialization of the user area, five additional binary operators, the VTL-2 equivalents of PEEK & POKE, and performance enhancements. I know a bit more now than I did then, and there's a non-zero chance that I or someone more skillful than I could revisit the 6800 source and try to fit the original features inside 768 bytes of 6502 (or 65c02) assembly, but that ship has probably sailed, at least for me in my current situation.

[teamtempest]

Quote:

My "big" BASIC (written in C) does a pre-run-time fix-up and scans the code for GOTO/GOSUB references and replaces them with a token containing the address of the line, so no searches during run-time. This also means no GOTO {expression}, but I can live with that as you can code mostly line-number free if desired.

The idea of a RUN command triggering some sort of pre-scan that checks for various mistakes before they can happen and/or speeds up later lookups is not a new one, though not one that 6502 Microsoft BASICs adopted.

This book https://www.wang2200.org/2200tech/Imple ... BASICs.pdf touches on the concept.

Overall I think it's a horrible book, far too preachy in its "this is the way it's done" attitude and refusal to acknowledge that there are in fact alternative approaches. But it has one or two ideas I hadn't seen before.

[BigEd]

Thanks for the link! (And the warning)

[barnacle]

Indeed thanks. But it's a bit of a jar to my brain to see the first illustration has Top of Memory as smallest memory address, and Bottom of Memory as largest...

Neil

[BillG]

drogon wrote:

It's akin to linked-list vs. doubly linked-list data structures - the programming burden (code size, testing) vs. simplicity and smaller code. In traditional memory constrained 8-bit systems, I suspect going for smaller code and simplicity is a bigger win... (or maybe the writers of them back in the 70s and early 80s just didn't have the knowledge then?

Except that storing the length of the line instead of the address of the adjacent line is that it does not need to be adjusted when lines are inserted or deleted.

[BillG]

teamtempest wrote:

This book https://www.wang2200.org/2200tech/Imple ... BASICs.pdf touches on the concept.

I bought that book back in the day and totally forgot about it. I do not know where it is now...

[BillG]

barnacle wrote:

But it's a bit of a jar to my brain to see the first illustration has Top of Memory as smallest memory address, and Bottom of Memory as largest...

Funny how that works...

We are accustomed to the lower left as the origin for charts.

Whereas we use the upper left of a display device as the origin with exceptions like OS/2 Presentation Manager.

And some people have real problems with stacks growing downward (toward lower address) on most processors meaning that the top of the stack is at a lower address than the bottom.

Don't get me started on electron vs conventional current flow...

[barrym95838]

BillG wrote:

Except that storing the length of the line instead of the address of the adjacent line is that it does not need to be adjusted when lines are inserted or deleted.

Yeah, I never understood why Applesoft and friends used 16-bit absolute line links instead of 8-bit relative. It seems like a waste of a perfectly good byte for every line and adds an unnecessary burden to the line editor when inserting/deleting.

linelinks.PNG (6.07 KiB) Viewed 6941 times

[BillG]

8-bit relative has its price at run-time: an addition or subtraction involving the line's actual address.

[barrym95838]

BillG wrote:

8-bit relative has its price at run-time: an addition or subtraction involving the line's actual address.

The 6502 does it in such a way that the difference is negligible, and in fact slightly favors the relative technique:

Code: Select all

nextln:
    ldy  #0         ; [2]
    lda  (txt),y    ; [5]
    clc             ; [2]
    adc  txt        ; [3]
    sta  txt        ; [3]
    bcc  next99     ; [2*]
    inc  txt+1      ; [5]
next99:
    ...             ; best case 18, worst 22

nextln:
    ldy  #0         ; [2]
    lda  (txt),y    ; [5]
    tax             ; [2]
    iny             ; [2]
    lda  (txt),y    ; [5*]
    sta  txt+1      ; [3]
    stx  txt        ; [3]
    ...             ; best case 22, worst 23

[BillG]

Touché

How could forget that the 6502 is not like the 680x where I can simply do

ldx 0,X