<2kbyte 6502 Tiny Basic?

[Chromatix]

Well, here's a possible design concept to realise that. I'm going to assume that there's at least 4KB of "working" RAM at the bottom of the memory map, 2KB somewhere else (either RAM or ROM) to put the interpreter code, and that we're more-or-less running on bare metal. This would be consistent with an Apple I, the Kowalski simulator, or any of the minimal novice-build systems we can now make with a small handful of parts (including something built around a 6507). I'm also going to assume that we're not actually in 1975, so we have access to 6502s with working ROR instructions - this is important for performing a 16/16 division, though there are ways to work around this.

The limited RAM demands a more sophisticated memory management than in bootBasic. I propose a "skip list" based structure for the BASIC program, in which the first byte of each line is an offset to find the next line, and the following two bytes are the line number. This is overall much less wasteful of memory than a fixed line length would be, but can still be scanned quickly to find a given line number. Lines can be inserted and deleted by scanning for the insertion point denoted by the line number, then copying the portion of the program after the insertion point to open or close up the space. This wouldn't be terribly fast - it would be considered poor practice in modern software - but should be interactively tolerable for the program sizes anticipated, even with aggressively size-optimised code and a conservative 1MHz clock. This scheme also relieves the limit on line length, so 200-character lines could be dealt with without difficulty, should they be required.

The interpreter, being very simple, won't need very much RAM for its internal workings. The 6502 has its "empty descending" hardware stack in the top of page 1, and this leaves room for edit-line input from the bottom of page 1. Zero page will be used for variables, pointers, temporary values, and an "empty ascending" software stack that can be accessed using two-byte Zero Page Indexed instructions. There would be no support for arrays or string variables. This leaves all contiguous RAM from $0200 upwards for the BASIC program. With 4KB total RAM, that would be 3.5KB available, plenty for simple demonstration programs.

With 16-bit signed variables and one-letter variable names, 52 variables can be laid out in the upper half of Zero page by simply doubling the ASCII codes of a-z and A-Z to form addresses. This leaves twelve 16-bit spaces for temporary variables, pointers, etc. It also leaves the bottom half of Zero page for the software stack, which would be used for expression parsing, nesting of loops, and BASIC subroutines.

One of the temporary variable slots can be reserved as the program line pointer, with the Y register then indexing along the line. In practical terms this would be the primary function of the Y register during interpretation. If a syntax error is found during expression parsing, the combination of these values allows identifying the precise location of the error, not just the line number. There might not be space for detailed error messages, but printing two numbers instead of one is just another JSR.

The X register would typically serve as the software stack pointer, though it would also serve additional functions, including pointing to variables and counting steps in mul/div algorithms. In these cases the software stack pointer would be saved on the 6502 stack. Note that the ability to have the X register point to either the software stack or the variables in the same context is why I didn't put both stacks in page 1 - because Zero Page Indexed does not carry over into page 1. Stack overflow or underflow can be detected via the N flag after an X register increment.

Compared to bootBasic, I recommend aiming to add comparison and logical operators (so that more useful expressions can be used as IF conditions), FOR-NEXT and/or REPEAT-UNTIL loops, GOSUB-RETURN, and a VDU statement to make dynamic output easier. The implementation of these features should not be difficult, given the slightly more relaxed space constraints. I note that VDU in particular would be useful for the Mandelbrot demo program, and would be particularly easy to implement.

[gfoot]

That sounds quite reasonable. I do wonder though whether we could just not use line numbers, instead requiring the lines to be sequentially-numbered? This wouldn't affect running programs, but would make program editing harder and non-standard - you'd need a separate "insert blank line" command, after which you could overwrite the newly-inserted blank line; and you'd need to renumber references to later lines when inserting. Still it feels like centralising that logic in one place - insert/delete line - would minimise it.

Alternatively, maybe the line numbers could be stored as deltas from the previous one, perhaps restricted to gaps of 255, or better, using a UTF8-style encoding, so that in most cases they only take up one byte but larger gaps are supported. Any such scheme would need to be very compact in the ROM though of course.

[Chromatix]

The key problem that is solved by line numbers is instructing the interpreter where in the program to insert (or replace) the code line. Screen-based editors were not common in the 1970s, and wouldn't be compatible with a simple "glass TTY" anyway. I believe the code associated with this will be both simple and compact, whereas a screen editor would be a project unto itself and rather more hardware specific.

Incidentally, "replace line" would be implemented as "delete line" immediately followed by "insert line". Simplicity over speed.

[drogon]

Chromatix wrote:

The key problem that is solved by line numbers is instructing the interpreter where in the program to insert (or replace) the code line. Screen-based editors were not common in the 1970s, and wouldn't be compatible with a simple "glass TTY" anyway. I believe the code associated with this will be both simple and compact, whereas a screen editor would be a project unto itself and rather more hardware specific.

Incidentally, "replace line" would be implemented as "delete line" immediately followed by "insert line". Simplicity over speed.

This.

Note that Comal uses line numbers but only for program entry/editing (As does my Apricot system) - there is no GOTO a line number as such - which then presents an issue - BASIC traditionally has a GOTO (and GOSUB) and very few old-time BASICs had the relevant structured programming styles to do without it. Worse (or as a necessity), there are various computed GOTO systems including GOTO/GOSUB a variable - as demonstrated in the above Mandelbrot program...

There were many text editors in the day (and today) that didn't use line numbers though - TECO in the early 60s, ECCE (Edinburgh Compatible Context Editor, also written in the 1960s) and sometime later in about 1973 the ed text editor appeared in Unix. Over the years I've used many text editors including YALOE (Yet Another Line Oriented Editor), em (Editor for Mortals, Unix) another horrible ed on Primos and, some odd one under Northstar DOS, and a good few others, but the issue here would be writing the editor and a sub-system to support it...

TinyBasic started with tapes - paper tapes being punched on a TTY33 ... So you don't even need save and load commands, so "bare metal" operation is much simpler.

So I think sticking with line numbers is relatively easy.

But implementing a renumber command when you have computed GOTO/GOSUBs is nigh on impossible...

When I wrote my own BASIC interpreter (It's in C and will never run on an 8-bit micro) it used traditional line numbers but could also work without line numbers if you used an external editor - but pressure from some users resulted in a built-in screen editor - adding another 1500 lines of code to the project, so sometimes you just need to stop...

-Gordon

[Chromatix]

Yes, it's true that screen editors existed in the 1970s - but on mainframes and minis with a VT attached. It took a while for home micros to catch up, largely due to the limited hardware capability that a hobbyist (rather than business oriented) budget could obtain. BASIC interpreters continued to use line-number based program entry even after screen editors became feasible, due to user familiarity.

WordPerfect, for example, only reached the IBM PC in 1982, and its capabilities were previously only (approximately) available on multiuser systems with smart terminals, or on Wang's crude appendage to a Selectric typewriter. However, the BBC Micro had WordWise from 1981. Though not a WYSIWYG word processor like WordPerfect, it did operate as a screen editor.

Acorn's Archimedes, being GUI based, had a recognisably modern text editor built in from 1987. This was capable of editing BBC BASIC programs without any explicit line numbers being present, provided GOTO and GOSUB were never used in the program. The structured programming facilities of BBC BASIC were by then sufficient to mostly eliminate the need for them. Of course it could also handle line numbers if they were needed, and the traditional BASIC command interface was still available as well.

[barrym95838]

The tiny interpreter you guys are describing on this page sounds very familiar. VTL02C is tantalizingly close to nibbling at the heels of Chromatix's detailed specifications ... error handling, negative numbers, and a FOR/NEXT/GOSUB/RETURN stack are notably absent, but pretty much everything else is packed into 1KB in a form very similar to what is described. In VTLC02, I count 111 of its 957 bytes being used for features that were not included in the original 1977 versions. Sacrificing them to make room for a different set of features like the missing ones mentioned above might be possible inside 1KB. Keeping line lengths below 120 characters would allow the line input buffer to move from $0200 to $0100, as long as interrupts don't pile up too deeply while editing long lines.

But in the end, it's not a "real" BASIC, and that might be a deal breaker for some people who want what they want.

[Chromatix]

I actually made a start on implementing it this evening. I started with the parts least similar to bootBasic, which are the memory management associated with storing the program, and the multiplication and division routines necessary to parse and output decimal numbers. It shouldn't take much more to be able to enter, edit and list a program, though it won't actually run yet since none of the syntax is implemented.

Interestingly, I found a relatively efficient method of division which doesn't use the ROR instruction. Rather, the dividend is shifted past the divisor in a leftward direction, with the quotient following it into the memory locations it is gradually leaving.

Code: Select all

PrintIntInternal:
  ; Successively divide by 10, pushing the remainders on the stack until the quotient is zero
  LDX #16
  LDA #0
  CLC
: ROL tmpWork
  ROL tmpWork+1
  ROL A
  CMP #10
  BCC :+
  SBC #10
: DEX
  BNE :--
  ROL tmpWork
  ROL tmpWork+1
  PHA
  LDA tmpWork
  ORA tmpWork+1
  BEQ :+
  JSR PrintIntInternal
	
  ; Now pop and print each digit in reverse order, ie. most significant first
: PLA
  ORA #'0'
  JMP PutChar

As the saying goes: "I have merely proved the above code correct, not tried it."

[barrym95838]

It appears that great minds think alike, or at least similarly! From VTLC02:

Code: Select all

; - - - - - - - - - - - - - - - - - - - - - - - - - - ;
; Print var[x] as unsigned decimal number (0..65535)  ;
; Clever V-flag trick comes courtesy of John Brooks.  ;
; entry:   var[x] = number to print                   ;
; uses:    outch:                                     ;
; exit:    var[x] = a = 0                             ;
; 36 bytes                                            ;
prnum:
    phy             ; save y
    lda  #0         ; stack sentinel
prnum2:             ; repeat {
    pha             ;   stack ASCII digit
    lda  #0         ;   remainder = 0 
    clv             ;   (sets if quotient > 0)
    ldy  #16        ;   16-bit divide by ten
prnum3:
    cmp  #5         ;     partial rem >= radix/2?
    bcc  prnum4     ;
    sbc  #133       ;     yes: update rem, set V
    sec             ;     and C for non-zero quot
prnum4:
    rol  0,x        ;     new quotient gradually 
    rol  1,x        ;       replaces var[x]
    rol             ;     new remainder gradually
    dey             ;       replaces a
    bne  prnum3     ;   continue 16-bit divide 
    ora  #'0'       ;   convert remainder to ASCII
    bvs  prnum2     ; } until no more digits
prnum5:
    jsr  outch      ; print digits in descending
    pla             ;   order until stack sentinel
    bne  prnum5     ;   is encountered
    ply             ; restore y
    rts             ;

[barrym95838]

drogon wrote:

So what might be needed is a version that would run with 16-bit signed integers so we could all test it with the various Tiny/Integer BASICs out there including Apple Integer BASIC which is, I feel somewhat neglected these days.

(And as it happens I do have a version that will fit the bill and work in 16-bit integers, however it's currently in BCPL, so I'll make an effort soon to translate it into BASIC suitable for Tiny* systems and other systems that support computed GOSUBs...

Picture of your Mandelbrot running on my Ruby 6502 board under BBC Basic. I didn't time it, but it was several minutes:

Screenshot_2023-09-07_17-45-16.png

Cheers,

-Gordon

I tried to port it to VTL02, but while developing a work-around for the negative integer thing I realized that 16-bits aren't wide enough for the fixed-point math, signed or not. I don't think I understand the algorithm quite well enough to modify it, so I'm gonna wait until someone a bit brighter leads the way.

I do have some fixed-point math and I/O in my Super Star Trek port, but it is untested and unfinished:

Code: Select all

20593 ) PRINT SIGNED NUMERIC VALUE
20595 ) RANGE: -32.768 .. 32.767
20597 ) ENTRY: X = VALUE * 1000
20599 ) EXIT: ; = PRINTED CHAR COUNT
20600 .=!
20610 ;=X>32768
20620 %=X
20630 #=;=0*20660
20640 $=45
20650 %=0-%
20660 ;=%>10000+;+1
20670 ?=%/1000
20680 #=%=0*.
20690 $=46
20700 ?=%/100
20710 ;=;+2
20720 #=%=0*.
20730 ?=%/10
20740 ;=;+1
20750 #=%=0*.
20760 ?=%
20770 ;=;+1
20780 #=.

[BigEd]

16 bits is very limited for Mandelbrot - unless you can do a multiply-and-shift in one go, which BCPL offers (probably for this very kind of reason).

Quote:

The library function muldiv take three signed numbers and returns the mathematically correct result of dividing the third argument into the product of the first two. Thus muldiv(x,y,z)=(x*y)/z, but x*y is computed as a double length quantity.

Hmm, it seems Microsoft put something similar at the heart of Windows32...

Quote:

Multiplies two 32-bit values and then divides the 64-bit result by a third 32-bit value. The final result is rounded to the nearest integer

[Chromatix]

It would be possible to make the multiplication result and dividend input used internally within a single expression into 32-bit quantities, without requiring syntax changes. Essentially this would involve recognising that the operand comes from the existing accumulator, and thus doesn't need to be moved and sign-extended. This isn't a common BASIC feature though.

[drogon]

Chromatix wrote:

It would be possible to make the multiplication result and dividend input used internally within a single expression into 32-bit quantities, without requiring syntax changes. Essentially this would involve recognising that the operand comes from the existing accumulator, and thus doesn't need to be moved and sign-extended. This isn't a common BASIC feature though.

BASICs have built-in functions - like RND(x) and so on, so creating a MULDIV (x,y,z) is just a matter of writing the code...

I don't think it's needed for a proof of concept 16bit Mandelbrot though, but I'll need to go through, my BCPL version to work out the maximum magnitude. It does a lot of x*x / 4096 in the inner loop, but I don't know just how big x gets...

But 32-bit "tiny" basic vs. a 16-bit one? what's a couple of bytes between friends ... And BBC Basic has shown that you can get blindingly fast 32-bit integer arithmetic if you try hard enough.

-Gordon

[BigEd]

(A couple of previous threads on limited-precision Mandelbrot
Mandelbrot implementation for the Apple II?
Adventures in optimising a Mandelbrot explorer
)

[VinCBR900]

Wow didn't realize there would eb such a response about running a Mandelbrot on a tiny basic system - I should have led with that.

Its been a while, but I think I ported that to run on a system without CHR$ hence the gosubs - they are not needed if you have CHR$ function.

Re 16 bit Math - I think I attempted to keep everything running within 16 bits but it might need some more parenthesis or breaking apart to multiple line numbers.

Look forward to hearing more about chromatix's Work!

[GARTHWILSON]

BigEd wrote:

16 bits is very limited for Mandelbrot - unless you can do a multiply-and-shift in one go, which BCPL offers (probably for this very kind of reason).

Quote:

The library function muldiv take three signed numbers and returns the mathematically correct result of dividing the third argument into the product of the first two. Thus muldiv(x,y,z)=(x*y)/z, but x*y is computed as a double length quantity.

Hmm, it seems Microsoft put something similar at the heart of Windows32...

Quote:

Multiplies two 32-bit values and then divides the 64-bit result by a third 32-bit value. The final result is rounded to the nearest integer

This is done regularly in Forth, with words like */ and */MOD.  (The MOD part gives the remainder of the division operation.)  In 6502 Forth, 16-bit is the normal single-precision size, and it works out surprisingly well, particularly where integers are scaled (hence the term "scaled-integer") to take advantage of the full 16-bit range, which they won't always do if the decimal point is only moved around like in fixed-point.