Nearby recent discussions mention Acorn's implementation of BBC Basic, which comes in at 16k, and mentions of Basic interpreters written in C.

To fit a nicely featured Basic into 16k memory footprint, to leave 48k RAM for the user, and to do it on a 6502 but written in C for maintenance and portability, probably something has to give.

So, here's my idle thought: break Basic into subsections to be placed in multiple ROMs mapped to the same 16k space, which either run at different times, or which are complex enough to run slowly enough to make the ROM switching a non-issue.

Break it up only as much as is needed, depending on how big the object code is compared to 16k, which will depend on how complex the Basic is, how it's coded in C, and how good the C compiler is.

For example, tokenisation and line-editing typically happen at time of program entry, not run time, so can be separated. (Similarly, line renumbering.)

Log, trig, and perhaps floating point generally is inherently costly enough that a few cycles of ROM switching on entry and exit isn't going to be too noticeable.

Perhaps string functions are time-consuming enough and separable enough to be moved out.

File handling can be presumed to be operating with I/O devices and so, again, not to be too time-critical, so worth paging out.

Graphics and bitmap character printing is complex enough to be sited elsewhere.

The assembler will typically not be performance critical and is a separate part of the interpreter already.

What's left, as the core, is the interpreter itself, the code to handle variable lookup, integer operations, and control flow (including loops, functions, procedures.)

By relieving pressure on space, perhaps the C code can be more maintainable, and perhaps even include some tactics which trade space for better performance.

Thoughts?

Thoughts ....

I think it's a nice idea and in 2022 it would make a good personal project, but to gain traction elsewhere? I suspect virtually impossible.

Today we have the Raspberry Pi for home users (it's not widely adopted in mainstream schools despite the Pi foundations efforts) and the BBC Micro:Bit computer. (Which is widely adopted). I may of-course just be talking about the UK though. The advantage of the Micro:Bit is that it pugs into an MS Windows running PC and the development IDE is all web based (I know other ways to program it exist, but that's what's being used and promoted for educational use). Virtually all UK schools have labs of MS windows PCs although many primary schools now have cabinets full of iPads to hand out.

That advantage is the disadvantage of the Pi - It needs USB keyboard, Mouse and HDMI screen. (Which is more important as you might think as HDMI monitors were more expensive than VGA monitors in the early days, so finding an HDMI monitor was hard 10 years ago!)

When I was involved with Code Club in it's early days that (cable wrangling) was seen as a bad thing - mostly because "computing" teachers were under equipped - they had a lab of PCs, often locked-down and controlled by an external maintenance company and unplugging keyboards to plug them into a Pi was just not the done thing, but plugging in a simple USB peripheral such as the Micro:Bit was deemed to be OK.

The same would apply to a 65xx based system. We, as hobbyists, can make such a beast but it would never be adopted. It would cost too much, we could not support it in terms of hardware and software maintenance, and documentation - that's the one thing the Pi Foundation (who now own Code Club) have done - they have produced some excellent teaching materials.

Then there's the cost - and at what point does it become easier to just stick it on an FPGA, or even emulate it on another SBC like a Pi or Pi-like device? real PS/2 keyboards are a rarity now and even the old USB keyboard which is really a PS/2 keyboard in disguise, is more and more a real USB keyboard now.

So.. The way to do this - IMO - develop an SBC with an on-board USB serial interface. Plug that into a PC and develop "smart" terminal software for it. That software will need to be written for (a) MS Windows, (b) MacOS and 9c) Linux - in that order. What you have then is a "retro" BBC Micro:Bit. Might as well use one of them, then...

And incidentally this is more or less how my Ruby SBCs work. 6502 or 65816 with on-board storage, requiring a "smart" serial terminal to work. The smarts in the terminal software allow graphics, user defined characters and incorporate a simple file transfer mechanism. It could incorporate sound too but I've never bothered to implement it.

What would that give? Well an historical insight into how it was done in the 70s and early 80s. Who would use it? Well other than a few oldies probably no-one. (One reason I've never bothered to try to make a kit for my Ruby systems - you simply can't please everyone)


I know this post may come over as a bit negative, but I've been involved with Pi stuff for over 10 years now, and educational computing in-general for a lot longer. I have been involved with youth groups and other young people groups over the years and seen what they do and what they expect now. Currently we have a lot of children who've effectively missed 2 years of education due to lock-down - those are mostly in the disadvantaged category (low income families). At least in the UK.

I could rant on about the issues I had with older 8-bit BASICs which prompted me to write my own, however there isn't enough time... Is there an ideal teaching language? I'm not sure there is - it's been tried with Logo, Pascal, Modula and so-on... My own BASIC has a unified looping system which not many other languages have (and C's while and do constructs are ugly to me, but back in the 70's memory was expensive, and when character compilation time could be measured in milliseconds, so was time, so code as terse and you didn't need unless (X) when you have if (!(X)) ...

But adding stuff like this in an 8-bit system - it needs more code, takes more time and would it then turn out programmers who expected those constructs in other languages in the real world? I don't know... But enough for now.

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Ah, I think you may have picked up on an educational aspect which isn't quite there in my post!

Still, interesting thoughts.

My thoughts on the big-Basic-in-a-small-ROM come from some recent experiments with a minimal SBC (happens to be 6309 based), which in the Grant Searle tradition has just 16k ROM and 32k RAM.

Having got that SBC working (not me, really, it's a collaboration with hoglet, revaldinho and dominicbeesley) our thoughts are turning to something a bit less minimal and a bit more functional. I am of course very familiar with the Beeb's memory map and the use of sideways address space in the 16k at 8000, but we're likely to end up with something looking a little different from that.

It's easy enough, I think, to put a few ROMs into one slot with a small register to select which is active. It's a bit more involved to think about how to cross-call between them, and to decide what kind of software interface is needed. Acorn had a whole story here, which works well. But for this thread, I was thinking of a monolithic multi-ROM - a piece of software which is assembled at one time, and therefore has known routines at known addresses in known ROM slots, rather than services to be called.

And I suppose I was mostly, initially, thinking about how a featureful Basic interpreter might fall out into component parts, in such a way that a few cycles of inter-ROM call protocol wouldn't be a major performance cost.

(My thinking on SBCs, by the way, is that a lot of the value is in the expansion bus, because it's something which can be probed and something which can be used to expand. If there's no expansion bus, the SBC becomes a bit more like a black box, which might as well be integrated within an FPGA or a software model. It's the separation and accessibility, between CPU, program, data, and I/O devices, which makes an SBC something more than just a retro computer. But this idea too is a bit OT for this thread.)

Not sure how you can assemble to one file to place in a BIG (say 256KB) ROM such that you have 16 images on 16KB, however I'm sure you can assemble 16 files then concatenate them...

But yes, Acorn did it - so if I were doing it, then I'd have a bigger block at the top (say 1KB) for 'vectors' that was identical over all 16 ROM images with a call to another ROM being something like:


and so on.

This assumes some sort of bank switch/latch based on poking any value into a set of addresses - easy to do in a CPLD I suspect and saves corrupting (or saving/restoring) a register to select a bank so you can pass more parameters in A, X & Y if needed. Also more transparent to a high level language like C.

Issues at assembly time are then to make sure all 16 banks have the same top 1KB of code/vectors - and to fix-up the addresses of the labels like doSin, doCos and so on, although you could fix them at the start of each bank image, but it's another layer of indirection.

Issues at run-time might be handling IRQ/NMI - it might mean identical interrupt code in each bank or somehow remembering what bank is live, switching to bank 0, then switching back - or even copying the IRQ code into RAM?

Switching to/from C to asm isn't hard to do with cc65 either and it's not hard to point a C function directly at a fixed address either, so



can just work if you provide the right address/call for the sin() function which could be written in C and the compiler won't know any different. (although cc65 doesn't handle doubles, but that's another issue - other C compilers are there) or make use of a good modern macro assembler.

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

The art of overlaying became a lost art after the infamous DOS 640K barrier finally got broken.

Turbo Pascal for CP/M can create an overlaid program. Phoenix sold an overlay linker for CP/M usable by programmers with other compilers. But they only worked with code on disk. It seems nobody developed overlay linkers for 64K systems with memory banking hardware.

The only thing even close was that OS-9 Level II used dynamic address translation (DAT) on systems with that hardware, but it was only for switching between different tasks. There was no provision for one "overlayed" program to have more code than fits within the address space at the same time.

With some people now building banked 65xx systems, there is a market, though small, for someone to create an overlay linker with banked memory management.

mmm, on reflection I'm not quite sure how to get an assembler or linker to understand the target addressing system (let alone a C compiler). Maybe one could use C to write sections of code and then build a complicated flow with an assembler to put them together.

It should definitely be possible to do in C, but it'd take some finagling. I don't know a whole lot about how 6502 C compilers do parameter passing, but I'd assume it's entirely on the stack? If so, you could keep a table of pointers to "far" functions in one segment, but invoke them through a common "thunk" routine that switches banks before calling the function in its own segment, then switches back before returning to the caller. Something along the lines of:





The challenges here would be:

• Making sure the thunk is at the same address in all banks.
• Getting a table of function addresses in bank B for bank A to use, and vice-versa.
• Having a separate function pointer for the thunk for each function prototype. (Should only require one copy of the thunk code, though, as long as the far-call address is in a consistent place on the stack.)

That's a rough spitball that's probably missing in the fine details, but it's what I can think of off the top of my head. The first two are linker issues, ultimately.

P.S. I know there were a couple C compilers going 'round in the NES and PC-Engine/TurboGrafx-16 homebrew scene some years ago; I'd be surprised if they didn't support code banking, so it might be worth looking at how they handled it.

very interesting project idea! personally i would go for a single large ROM (like a 512kB SST39SF040) and have 8kB fixed (for vectors, startup code, c-runtime library, etc), with the other 8kB switchable, which would give a total 64 banks (one of which is a mirror of the fixed bank, so technically only 63 banks).


after doing a bit of reading online, it seems a lot more doable than i thought!
cc65 seems like the only real option for a modern and actively maintained C Compiler for the 6502/65C02. especially since it's designed for retro systems that also sometimes have to deal with bank switching.
also cc65 is just one part of the whole utility. all the compiler does it generate a regular assembly file that can then be used by ca65 (assembler) to generate an object file, which is then used with ld65 (linker) to finally generate an executable.

Usually cc65 puts all generated code into the CODE segment, which is then mapped to somewhere in memory by the Linker. On a banked system each bank would have it's own segment so obviously that wouldn't work.
luckly, you can tell the compiler to change the segment in which it's puts code/data using #pragma code-name("segment name here"). and #pragma data-name("segment name here")...
that way the programmer still has to manually decide what functions to place into what segments but the linker would automatically place them in the correct order into the output file (or into seperate files if you want).

in order to make everything more organized you could put each Bank's functions into seperate C files with a header file for each bank that defines all the functions of that bank (which you can then include into the main C file)

one big issue is calling functions in other banks. since cc65 is not aware of memory (as that's the linker's job) it will not generate special code when a JSR or JMP crosses bank boundaries. if you go with the idea of having your main execution happening in a fixed bank then you can simply write a small function that just switches the ROM bank to whatever number you give it. you then just have to call that function before calling another function that you know is in a different bank. for example:



you also don't need to care about the exact location of the functions within their banks, as again that's the linker's job. you just need to make sure the functions are actually defined (usually in a header that is then included).

sadly it's pretty late for me, otherwise i would've thrown together a banked system in my Logisim 65c02 and write a little example to test the idea.


kinda, cc65 uses a software stack for parameter passing, since the hardware stack is too small for that. (as a lot of existing systems use a good chunk of it for themselves)


I'm not sure i fully understand what you mean but it sounds similar to what i came up with, but as a wrapper function where you pass the function you want to call as a pointer, plus the bank you want to switch to (since the compiler cannot do that on it's own) instead of a seperate one you call before calling the function you want.

Yeah, there's a couple different ways to do it. Your example is fine if banked functions are only called from functions residing in shared memory (or the same bank,) but depending on A. how much stuff you're trying to fit into shared memory and B. whether functions in banked memory need to be able to make cross-bank calls, it can help to have a small cross-bank dispatcher function (the "thunk") residing in shared memory that can allow a function in any bank to safely call a function in any other, without the risk of pulling the rug out from under itself and sailing off into who-knows-where.

hmm, i think i see what you mean. the switchBank function would be located in the fixed/shared ROM Bank, so running that wouldn't be an issue. but if it was called from a Bank, the system would likely crash once it finishes the RTS instruction, as the contents of the Bank it came from are now completely different.

so i guess you have to do it as a wrapper (or "thunk") function. passing the address of the function you want to jump to, in addition to the bank number (as again i'm like 99.9% sure the compiler cannot handle that on it's own).
that function could then be placed in the fixed bank next to the runtime library and startup code, so you don't need a copy of it in every bank.
also I don't really see how a table of addresses of functions in other banks could be helpful to automate the switching process. since you can't just have the program compare the given function address to all tables to see in which bank it's located because 1. it would be really slow, and 2. the chances of multiple functions sharing the same address but in different banks is non-zero.

another idea would be to try and see if you can just work around the limitation of not being able to call banked functions from another bank (besdies the fixed one obviously). it would certainly simply the calling process, but i don't know how much you would be sacrificing in terms of flexibility...

i should really go to bed now, i have work tomorrow, but this is such an interesting problem that i want to keep thinking about it anyways!

Yes, exactly.


I could've phrased that more clearly. It's not that you need some way to programmatically determine this, but rather that (for the thunked approach) you'll need to know what the addresses of banked functions are in order to pass them to the thunk routine. If the linker can do this automatically, giving the correct value for &someFunction in bank B to the thunk call from bank A, so much the better, I just don't know if it can.


Also an entirely valid strategy, if it doesn't limit what you want to do.


I think we can all relate to this

As it happens, our SBC project is heading towards large RAM and large ROM both mapped into the four 16k regions of the address space in a flexible way.

But one approach would be like this: the large application occupies, say, two 16k banks of ROM, each to be mapped into, say, the region at C000, but the first 3k (or 5k, or any other amount) in the two banks are identical. So we get a 3k + 13k + 13k distribution of our large application, without needing a finely sliced memory mapping. Any calls to the shared area - the area which is identical in both application banks - don't need to worry about which of the two banks is presently mapped in. And of course it could handle 8k + 8k + 8k equally well.

Yeah, that's definitely a valid design choice - it wastes some of the ROM, but ROMs these days are huge, and it saves you having to reserve a whole 'nother bank's worth of address space for the shared segment. But that's more an in-addition-to option you can go with; you'll still need to consider whether you want to allow non-shared functions in the different banks to call each other, determine where function A is stored in bank B, work out the details of the bank-switching process, etc.

I think one of the (implicit) aspects of my original post, in trying to think which bits of the interpreter might be separable into different universes, is the idea that they don't interact much with each other. But I've never written an interpreter so my guess is very much just an uninformed guess.

The call graph could be an interesting thing to study, taken from any Basic interpreter we have the source for. Hopefully it's not very deep. Aside from expression evaluation I wouldn't expect anything recursive or mutually recursive - and (I think) even that needn't be visible in the call graph, depending on how it's done.

Yeah, it's an open question - I'm genuinely not sure myself. Curious to hear what folks find out, though...!