Symbols with lazy, per-frame binding

Summary

• In the stored program: every identifier becomes a symbol token, 2 bytes for the 63 most used names and 3 bytes for the rest. This covers variables, SUB and FUNCTION names, labels, and the sub-keywords of commands. Each program image carries a table of the names as spelled. LIST prints each name exactly as it was typed, so its output does not change.
• Binding at run time: each distinct name gets a small record: its global slot, its SUB/FUNCTION index and its label. These are filled in the first time the name is used and cleared when the thing they point to goes away. Locals use a per-name "shadow" stack. Creating a local pushes it and ending the frame pops it, so a local is found in constant time at any recursion depth.
• Lookup becomes a few loads. There is no hash, no probe, no string compare and no division. The current name-hashing code stays as the fallback. It serves runtime strings (EXECUTE, EVAL, CALL "name", the prompt), programs saved before this change, and the first use of each name.
• Programs get smaller. Sandglass, the largest program, shrinks by about 18 KB and Elite by about 9 KB. The smallest measured program, solar_eclipse, grows by 132 bytes. RAM: on the RP2350 the bindings replace the 18 KB funtbl, a net saving. On the RP2040 they take about 7 KB of heap for a 500-name program.
• Expected gain: most of the 16-34% spent in findvar. Also removed are the +46-48% cost of a LOCAL read at recursion depth 10, the RP2040's +21-47% on calls and array reads with 200 SUBs, and its 67x cost for a far GOSUB. These figures are estimates; phases 2 and 3 measure them.
• Four phases, each tested on both boards and committed on its own. Phase 1 changes only the format and must be exactly as correct as today before any speed work begins.

Where the time goes today

This is the path for reading an existing global scalar, from the variable survey (instruction estimates, not measurements):

1. getvalue walks the name. An array reference also runs FindSubFun first: a second hash on the RP2350, and on the RP2040 a count of the whole SUB table followed by a binary search.
2. findvar reads the name one character at a time, upper-casing it and hashing it. That is about 12-15 cycles a character on the RP2350 and 20-25 on the RP2040.
3. It divides hash % maxglobalvars on every call, even when the name turns out to be local. On the RP2040 this is a library call.
4. Inside a SUB it also runs the local probe. That probe does another division, and then one more for each probe step. Every recursion level's copy of a local sits in the same chain, so a lookup at depth D does D name compares and D divisions.
5. It compares names in the table. Then comes the type and dimension checking, which stays after this change.

Two earlier measurements shape the design:

• A cache keyed on the name's address in the program gained only 1.15% (Phase 0). Array indices, built-in function arguments and SUB arguments are copied into buffers before findvar reads them, so the address is lost. A symbol id is carried along by those copies.
• Recursion makes locals linear (Phase 1, +46-48% at depth 10). Binding has to be per frame, not per name.

Symbols in the stored program

Encoding

• A symbol is an introducer byte followed by one or two payload characters. Payload characters come from a 63-character alphabet: 0-9 A-Z a-z _.
  • Introducers: 0x04 program long, 0x05 program short, 0x06 library long, 0x07 library short. That gives 63 short ids and 3,969 long ids per image.
  • Short ids: the tokeniser gives them to the 63 most used names. That covers 46-80% of name uses in the measured programs.
• Why these bytes:
  • tokenise already turns every control character in source text into a space, so 0x04-0x07 cannot come from what the user typed.
  • Every payload character is a name character. That keeps it clear of what scanners act on: statement ends (0), quotes, brackets, commas, comment marks, and token bytes 0x80 and above.
  • Code that has not been updated sees 0x04 as "not a name" and stops with a syntax error. So anything the audit missed fails loudly in testing and cannot give a wrong result.
• What stays around the symbol: type suffixes, array brackets and struct dots stay as they are. a$(i) becomes <sym a> $ ( <sym i> ). A dotted name p.x is a single symbol, because . is a name character.
• Spelling: each distinct spelling gets its own id, so Foo and FOO list back exactly as typed. Both map to the same binding (see Binding).

The symbol table travels inside the image

• Where it goes: after the program's 0,0 end marker and before the CSUB and font records.
  • It holds a magic word, a count, an offset for each spelling, the names, a canonical index for each id, and a hash index for text lookups.
  • The CSUB records address code by its offset in the program text. That text comes before the table, so those offsets keep working. SaveProgramToFlash computes them after tokenising anyway.
• Copies: flash slots, RAM slots, LIBRARY DISK SAVE files and FLASH DISK LOAD copy images byte for byte, so the table goes with them.
• Images from older firmware: they have no table. Every name in them is raw text, which the kept fallback runs at today's speed. Saving the program again gives it symbols. Nothing is refused.

Who reads names, and what changes

Why not keep sub-keywords as text? The firmware compares 893 distinct words against argument text, and they include most single letters as well as INTEGER, FLOAT and STRING. Those collide with the commonest names: Elite's N alone is used 883 times, and a third of solar_eclipse's name uses match one of these words. Any word kept as text would stay slow, so every identifier becomes a symbol and the comparisons learn to read symbols.

Binding

The canonical table

PrepareProgram builds it at RUN, CHAIN, LIBRARY LOAD, and before each prompt command, as it builds funtbl and subfun today.

• Contents: one canonical entry per distinct upper-case name across the program and the library.
• Id maps: a map from program ids to canonical entries and one from library ids. When there is no library and a name has only one spelling, the map is the identity.
• Old-format images: SUB, FUNCTION and label names found as raw text are added to the table too.
• What it replaces: the RP2350 funtbl, hashlabels, the RP2040 sort, first-letter index and binary search, and the RP2040's scan of subfun[] for name clashes.

Each canonical entry holds:

Lookup (the fast path)

canon = map[id]
s = lbind[canon]
if (s != NONE && g_vartbl[s].level == g_LocalIndex)  -> the local
else if ((s = gbind[canon]) != NONE)                  -> the global
else -> slow path: today's name lookup, which creates the
        variable if needed and then fills gbind / pushes lbind

• After the slot is found: the type, dimension and array-index work is unchanged. So are the checks and errors.
• SUB/FUNCTION calls and array references: the FindSubFun test becomes one load of sbind.
• GOTO, GOSUB, RESTORE and interrupt targets: one load of labind.

Locals: the per-frame shadow stack (S6)

• Creating a local (LOCAL, STATIC, a parameter or a FUNCTION result) at level L saves the old lbind[canon] in a per-slot array lshadow[slot], then sets lbind[canon] = slot.
• Freeing a level: ClearVars(level) already frees locals newest first, using g_hashlist. For each one it restores lbind[canon] = lshadow[slot]. A second array, lcanon[slot], supplies the canonical index without hashing again.
• Visibility is unchanged: only locals at exactly the current level are visible, and the level check does that. A callee without its own x sees the caller's x in lbind, but at the wrong level, so it falls through to the global. GOSUB and interrupts raise the level as today.
• Recursion: finding a local at depth 10 costs the same as at depth 1.
• By-reference parameters, STATIC pointers and FOR variables keep pointing into g_vartbl as today, because slots never move.

One rule for staleness

A binding is cleared at the moment its slot is freed.

• Only three paths free slots: ClearVars(level) (locals), ClearVars(0) (everything: RUN, NEW, CLEAR, CHAIN, errors at the top level), and erase() (ERASE and REDIM).
• ERASE and REDIM find the canonical entry by name, which is fine for rare commands, and clear gbind. ClearVars(0) clears every binding.
• Nothing else deletes or moves a variable, so no other code needs to know about bindings.

What stays text, and the kept fallback

• Never turned into symbols:
  • string literals;
  • comments (', REM, /* */);
  • DATA items: unquoted strings are case-sensitive data, and READ must return them as typed;
  • CSUB and DefineFont hex lines, which must stay byte-exact until the binary is extracted;
  • OPTION and CONFIGURE board names, which are rewritten before tokenising.
• Runtime strings (the prompt, EXECUTE, EVAL, CALL "name", the MM.STARTUP, MM.PROMPT and MM.END hooks, CSUB RunBasicSub):
  • they are tokenised as today;
  • names already in the canonical table get its ids, so the fast path works there too;
  • other names stay text and use the fallback.
  They run at the caller's level, as today.
• The fallback is today's findvar, FindSubFun and findlabel text path. It gets its answers from the canonical table instead of funtbl. When it creates a variable it also fills the bindings, so the next symbol lookup is fast.
• By name as today: CHAIN, VAR SAVE/RESTORE, g_vartbl and the CSUB interface are unchanged. A chained program starts with empty bindings and fills them as each name is used.

Images, slots, library, editing

• Save paths: SaveProgramToFlash, SaveProgramToRAM and SaveLibraryImage gain a first pass that collects names and counts their uses (for the short ids). The symbol table is written after the text.
• EDIT and AUTOSAVE APPEND go through LIST and then tokenise again, so the table is rebuilt whenever the program changes.
• LIBRARY SAVE already rewrites at token level (it merges the library with the program, drops comments and recomputes the skip bytes). It now also merges the two symbol tables into one library table and renumbers the program's symbols as library symbols. This is the largest single piece of new code.
• The library and the program share one namespace, as today. They have different introducer bytes, so a library SUB called with program arguments decodes each symbol against the right table.
• LIST, the editor, SAVE, XMODEM S and error-line display all go through llist. It prints each symbol's spelling from the right table.
• The trace cache has its own name reader and variable resolver, and it keeps global slot indices that nothing ever invalidates. The design removes it in phase 1 (see Decisions).

Size and RAM

Program size

Estimated from the source files with the command and function tables applied. Strings, comments, DATA and CSUB blocks are excluded. The 63 most used names get 2-byte symbols and the rest 3 bytes. The symbol table costs each spelling plus 3 bytes.

The largest programs shrink the most, so the program-capacity rule is met with room to spare. On HDMIWEB, sandglass should load without the ,C crunch it needs today.

RAM

• Bindings: 8 bytes per canonical name. The id maps and the text-lookup hash add about 6 more. Sandglass (1,019 names) needs about 14 KB.
  • RP2350: this replaces the 18,432-byte funtbl, a net saving of about 4 KB.
  • RP2040: it comes from the heap, sized to the program: about 7 KB for 500 names. Putting the text-lookup hash in the image instead of RAM brings that to about 5 KB.
• Local shadows: lshadow and lcanon cost 4 bytes per local slot: 1 KB on the RP2350 and 960 bytes on the RP2040.
• Flash (firmware): the new code less the retired hash and sort code. Probably a few KB, to be measured in phase 1. HDMIWEB now has 15.7 KB free.

Risks and how each is contained

Phases and tests

1. The format, at today's speed.
   • Tokeniser and image table; llist; the canonical table in PrepareProgram, replacing funtbl, hashlabels and the RP2040 sort.
   • The symbol-aware core readers resolve by name through the table, with no bindings yet.
   • The checkstring change and the audit fixes; LIBRARY SAVE merging; the trace cache removed.
   • Tests: LIST round trip of every Bas/ program and the goldens corpus; goldens on both boards; the three games' checks; the interrupt tests; libtest; EDIT and AUTOSAVE by hand; program sizes; MEMORY before and after.
2. S5, global, SUB and label bindings. gbind, sbind and labind, the fast path in getvalue, findvar, FindSubFun and findlabel, and clearing in the three functions that free slots. Tests: the anchor, the standard set and the goldens; the Phase 1 name micro-tests (200 SUBs, far labels); the debug build's check of fast path against slow path.
3. S6, per-frame locals. The lbind shadow stack. Tests: the recursion micro-tests (depth 1 against depth 10), call loops, the games and the goldens.
4. Optional, later. Store a symbol id in g_vartbl in place of the 32-byte name. That saves 14-28 KB of RAM per variant but changes the CSUB interface and PEEK(VARHEADER). Also cache struct members per symbol, and add call descriptors (S3b), which build on symbols.

Found on the way (not part of this design)

The surveys turned these up by reading the code. None has been tested on a board. They are listed for you to prioritise, and none is fixed here.

1. CurrentSubFunName is not restored after a nested call returns (MMBasic.c:2736). A STATIC executed after a call is mangled with the callee's name, so it may pick up the wrong backing variable. It probably deserves a test.
2. OPTION LOCAL VARIABLES above the compile-time MAXLOCALVARS can overflow g_hashlist (MMBasic.c:332, 5359).
3. Probe loops that can spin forever:
   • The global probe has no wrap guard at level 0.
   • hashlabels' guard originalhash<0 is unsigned, so it is never true.
   • FindSubFun's probe has no bound.
   Each can spin when its table is full.
4. On the RP2350 findlabel does not filter out SUB entries, so GOTO to a label that has a SUB's name would use a small integer as a pointer.
5. FindSubFun ignores its type argument on the RP2350 but not on the RP2040, so a CSUB or SUB name used as a function behaves differently on the two chips.
6. cmd_call and fun_call append the argument text to a 256-byte buffer with no length check. tokenise also has no bound on its output in tknbuf.
7. The rti[2] IRETURN stub has no terminator, so skipelement and checkend read past it.
8. CountLines uses p[0] where it means p[1] (MMBasic.c:4060), on lines longer than 253 bytes.
9. Unbalanced frames on CACHE builds: a SUB-style interrupt and ON…GOSUB never enter a frame but do leave one, so profiling misattributes the time.
10. MM.INFO(VARCNT) is stale after ERASE and after locals are freed.
11. The CSUB header's int dims[] layout is selected only #ifdef PICORP2350, although every RP2350 build uses int dimensions (PicoCFunctions.h:393-413). Worth checking against a CSUB that reads g_vartbl on HDMIUSB.
12. If an argument errors under ON ERROR SKIP while a nested call has cleared DefinedSubFunMem, the outer call's frame and buffers leak.