CARDIAC › Programming basics › Programming with overlays

Beyond the basics: programming with overlays

CARDIAC has 100 cells, and a program shares them with its data. When the two don't fit together, split the program into decks that take turns: each deck loads over the code before it, and the data stays where it is. That is an overlay.

Why split a program

Memory is tight before a program starts. Cell 00 is wired to 001, cells 01 and 02 belong to the loader while a deck goes in, and every JMP writes cell 99. What's left is shared by the instructions and the numbers they work on, so every cell of code is a cell that can't hold data.

The sortem program in cardiac-code shows how much that costs. It reads numbers, sorts them and prints them with their mean, minimum, maximum and median. In one deck its code takes 94 cells, which leaves room for two numbers. Split into two decks, the same machine sorts 35. Cardigan's examples do the same: 10-sort49 sorts up to 49 numbers in one deck, and 11-sort57 splits the work to sort up to 57.

How one deck hands over to the next

Nothing in CARDIAC clears memory. A deck ends with HRS, the operator puts the next deck in the reader and starts the machine at 00, and the loader reads the new deck in over the old one. Each cell the new deck names gets its new contents, and every other cell keeps what it held. That is the whole mechanism.

The convention is to halt with the PC on the next deck's number, so HRS 02 means "load deck 2". On a paper CARDIAC, that number is a note to the operator. Cardigan reads it: when a program halts on n and deck n is open, Cardigan puts that deck in the reader and runs the loader itself. That is one of the few conveniences Cardigan adds to standard CARDIAC.

Across the handover:

Survives: every cell the next deck doesn't load. That's where the data lives, and where one deck leaves a message for the next.
Replaced: the cells the next deck loads, and cells 01 and 02, where the loader builds itself again.
Overwritten: cell 99, by the loader's JMP 00.

Planning the memory

An overlay starts with a map of memory. Put the shared data where no later deck loads anything, and keep each deck's code out of it. In sort57, deck 1 holds its code and variables in cells 03 to 41, and the numbers go in cells 42 to 98. Deck 2 is only cells 03 to 11, so it loads over the start of deck 1's code and leaves everything from cell 12 up alone.

Cell 40 carries the message between them. Deck 1 calls it end and keeps in it where the next number goes, as the instruction STO a+k. Deck 2 doesn't load cell 40, so the value is still there, and deck 2 reads it to know where to stop printing.

sort57 in Cardigan

Open 11-sort57 from the examples. Its 57 input cards are already in Input cards, and the Decks pane, under Run and Debug, says which deck is in the reader.

Cardigan with sort57's first deck loaded: the listing of deck 1, memory with deck 1's cells in blue, and the Decks pane saying deck 1 of 2. — Deck 1 loaded: 39 cells in 123 loader instructions. Its cells are blue, and the PC is on 03, its first instruction.

Run it. Deck 1 reads the numbers one at a time and slides each into place among the ones before it. When the last is in, it halts on 02. Cardigan puts deck 2 in the reader, the loader runs again, and the machine stops on deck 2's first instruction.

Cardigan just after sort57's second deck loaded: deck 2's cells 03 to 11 in red, deck 1's leftover code still in blue, and the sorted numbers in cells 42 to 98. — Deck 2 loaded over deck 1. Its 9 cells are red, with the loader's 01, 02 and 99. Deck 1's leftovers from cell 12 up stay blue and never run again. Cells 42 to 98 still hold the numbers, sorted, and cell 40 still holds `end`.

Continue, and deck 2 prints the numbers, smallest first.

Cardigan after sort57 has finished: the paper strip with the numbers printed in order, smallest first, and the Debug Console's account of both decks loading. — Done. The Debug Console tells the story: deck 1 loaded, deck 2 loaded, halted.

Open sort57 in Cardigan

To watch each handover card by card, tick Step through loading before you run it.

Decks as files

A program in several decks is several files with one name: NAME.cqb for deck 1, then NAME.2.cqb, NAME.3.cqb and so on. Open or drop them on Cardigan together, with a listing for each if you have one, NAME.cq or NAME_n.cq for deck n, to debug them by their source. burn works the same way on the command line: when a program halts on n, it reads NAME.n.cqb from the same folder and starts again at 00.

The tip when it doesn't fit, split it has the smallest overlay there is: two tapes, one number passed between them.