Bitcoin BASIC

Every infix language has a stack machine underneath. Script is what BASIC's expression evaluator looks like with the front end deleted — so this puts the front end back, and takes it off again.

BASIC line 110 V = V + F/M - V*D under the hood V F M / + V D * − ← postfix, on a stack Bitcoin Script OP_DIV OP_ADD … OP_MUL OP_SUB ← the same sequence, executed by miners

A locking script hex, or ASM

Or read one of this project's own covenants — hand-written Script, already named.

the stack when it starts

name the OP_PUSH_TX preamble

Those names are the whole product. The script is the source and the names are annotation over it — name the slots and a covenant reads as a program; leave them out and it still reads correctly, just anonymously. If it needs more, it will say exactly how many.

read as BASIC

Paste a script and press Read it.

★ The listing is in the same language the other tab compiles — paste it straight across. Measured: of fifteen test programs, fifteen compile back and nine come out byte-identical. ⚠ With the preamble named, it is a reading for a person rather than a source: PUSHTX and HASHOUTPUTS are names this page gives runs of opcodes, and the compiler has no such words. Untick the box to get the version that compiles back. The six that differ still compute the same thing: a branch reads back as the balancing the compiler performed, and an unrolled FOR reads back as the copies that are really in the script, because the loop is not.

⚠ But a reading is not a source. There is no general decompiler from Script to BASIC: Script does byte surgery, keeps an altstack, and checks a preimage against a derived signature. Those come out as plain functions — SPLIT, CAT, HASH256, NUM2BIN — which is honest, and they are real words in the compiler too. An opcode the reader does not model stops the listing and names itself rather than being skipped, because a listing that quietly dropped an opcode would be worse than none: it would be believed.

Bitcoin BASIC LET · IF/THEN/ELSE · FOR…NEXT · DIM · VERIFY

the stack it starts on

DIM declares a LAYOUT, not a type. DIM v%5 means five bytes, because that is where a covenant splits its own script to read its own state. $ means raw bytes. With any DIM present the compiler also generates the peel and the rebuild around your program. Line numbers are optional and change nothing in the output. ⚠ SAMEBYTES is not =: one compares byte strings and the other compares numbers, so a padded zero and a bare zero are one number and two different strings.

Bitcoin Script

Write some BASIC and press Compile it.

★ The compiler balances the branch arms. Both arms of an OP_IF must leave the stack identical, and getting it wrong is silent — it surfaces two hundred opcodes later as a size complaint. The compiler takes the union of everything either arm assigns and makes both produce all of it, so a whole bug class stops being possible rather than becoming less likely. ★ And FOR…NEXT is unrolled at compile time, because Script has no backward jump — the loop still happens, laid out in space rather than repeated in time, so a program's length is its work. That pays for a fixed-cost body and barely at all for an early-exit one.

★★ Noughts and crosses is the one to read. Five bytes of state, every rule a comparison, and it shows what a racing car cannot: turn-taking enforced by the covenant. You cannot play out of turn, take a taken square, or play on after somebody has won — and none of those rules live in a page. ⚠ Note what it has to do about having no arrays: Script cannot compute a location, so the square is chosen by nine comparisons each selecting a constant, and the board is packed base 3 into one number so that reading a square is arithmetic instead of a lookup. That is a 1982 problem with a 1982 answer. ★ And there is a second version of it packed base 4 — two bits a square, one value wasted — where every access becomes a shift instead of a division. Measured: 657 bytes against 762, for one extra byte of state. Waste a little space to make the arithmetic cheap, which is the oldest trade in the business.

★★★ Rule 110 is the one with the joke in it. A row of cells; each looks at itself and its two neighbours and decides what to be next. Eight patterns, eight answers — 01101110 = 110 — and it draws the famous nested triangles. It is also Turing complete, which Matthew Cook proved, so it is the machine that "Script isn't Turing complete" is usually said about. Both halves are true at once: one generation is 2974 bytes with no backward jump anywhere in it, and the chain of transactions runs unboundedly. ⚠ It does not make Script Turing complete — it shows where the loop went. Into the ledger. ★ And it is the one program here with no runtime index at all: every neighbour sits at a position the compiler knows, so the thirty-one cells unroll with every mask already folded, and no table or shift is needed.

★★★ And Space Invaders is the one that proves something. The arcade original speeds up as you kill aliens, and nobody designed that — the 8080 moved one alien per frame, so a sweep took as many frames as there were aliens left. Here one transaction moves one alien, and the same ramp comes back: measured, a sweep costs 24 spends at 24 aliens and 12 at 12, so the fleet is twice as fast at half strength. ⚠ And it is not automatic — the script is byte-for-byte the same size in every frame, whatever is alive. What falls is the number of transactions. The economics reproduce the accident only because one spend was made to mean one alien.

★★ And it is the full 5 × 11 arcade fleet, which it was not an hour ago. The bit for a slot used to be picked by a table of comparisons — about fifty bytes a slot, and impossible past 2^53, where a double stops being exact. A shift is what stands in for a power of two, and it does not care how wide the fleet is: 1269 B by table at 52 aliens and refused at 55, against 34 B by shift, flat. ⚠ With one trap — read as a number, a mask landing on the top bit of the last byte is negative zero, and one alien in fifty-five would quietly refuse to die. It has to be SAMEBYTES, a byte comparison, never =.

Where Script's constraints come from

A 1980s home microcomputer on a desk in the foreground, with a room-sized 1960s mainframe — tape reels and panel lights — behind it. — The argument in one picture: a home micro from 1982 standing in front of a mainframe from before 1964. **The byte discipline is the little machine's. The control flow is the big one's.** Bitcoin Script inherited both, and an arithmetic neither of them had.

BASIC had arrays. DIM A(9) is in Dartmouth BASIC from 1964. So the nine-comparisons pattern isn't what 1982 did for lack of arrays; it's what ON X GOTO did for lack of a cheap one. The technique is period-authentic. The reason isn't.

What's actually going on is that Script's constraints come from three different eras at once:

Bitcoin Script		where that constraint is from
every byte paid for, twice, forever	✓	1982 — 16KB RAM discipline, exactly
fixed point, no floats	✓	1982 — no FPU on an 8080 or a Z80
no dynamic allocation	✓	1982
no backward jump	✓	pre-1964 — earlier than BASIC itself
no GOSUB, no functions	✓	pre-1964 — a program's length is its work
no computed address	✓	more constrained than a Spectrum, which had `POKE`
arbitrary-precision integers	✓	no home computer, ever — a Spectrum had 16 bits

⚠ Though a shift gets close. LSHIFT builds a mask at runtime, so you can select without being able to address — the difference between reaching a location and constructing a filter for it. It is why the 55-alien fleet costs 34 bytes instead of 1269, and why it can exist at all: a table of powers stops being writable past 2⁵³, where a double stops being exact.

So it isn't a 1982 machine. It's a machine with 1982's economics, control flow older than BASIC, and arithmetic no 8-bit micro ever had.

★ The sharp version: Script has no backward GOTO. BASIC's most famous instruction is the one that cannot be compiled — which is why FOR…NEXT is unrolled rather than emitted. And with no GOSUB either, the thing that made 1982 programs shorter doesn't exist, so length and work are the same quantity. That's why the racer costs what it costs.

⚠ But that is not the same as saying Script cannot loop, and it is worth being exact about. FOR i = 0 TO 30 genuinely iterates thirty-one times in Script — the repetition is simply laid out in space, as opcodes, instead of repeated in time by re-entering the same ones. The loop is still there. It has been rotated from time into space — and that is precisely why length and work become the same quantity: you pay for the iteration in bytes rather than in cycles.

So the limit is narrower and more interesting than "no loops":

a loop whose trip count is…
known when the script is written	yes	unrolled — real iteration, paid for in bytes
decided by data, but bounded	yes, at a price	unroll to the worst case and mask; you always pay the worst case
unbounded	no	nothing in a single script can run an unknown number of times

Where the loop went

That last row has a consequence, and Rule 110 is where it shows. A line of cells; each looks at itself and its two neighbours and picks what to be next. Eight patterns, eight answers — 01101110, which is 110 — and it draws the famous nested triangles.

It is also Turing complete. Matthew Cook proved it: anything computable can be computed by this rule. So it is precisely the machine that "Script isn't Turing complete" is usually said about — and here it is, in Script. Both halves are true at the same time:

the scriptOne generation is 2,974 bytes and contains not one backward jump. It halts. It is paid for in advance. Thirty-one cells, unrolled at compile time.

the chainEach spend is one enforced generation, and there is no limit to how many follow. The automaton runs for as long as somebody funds it.

⚠ This does not make Bitcoin Script Turing complete, and the page would be worth less if it claimed so. A script still halts, still has no backward jump, and every step is priced before it runs. What Rule 110 shows is where the unboundedness lives.

★★ The iteration is in the script. The UNBOUNDEDNESS is in the ledger. A covenant iterates perfectly well — thirty-one cells, unrolled, every generation. What it cannot do is run an unknown number of times, and that is the only thing Rule 110 needs the chain for. The chain does not supply the looping. It supplies the not knowing when to stop.

★ So Rule 110 can be written two ways — and both are here

the loop in the scriptBOUNDED. Eight generations unrolled into one transaction. You decide how many when you write it, and you pay for all of them up front.

the loop in the chainUNBOUNDED. One generation a spend, and nobody decides how many. It runs for as long as somebody funds it.

Both are real loops, and the test runs eight generations each way and checks they arrive at the same state. What separates them is not capability. It is boundedness.

★★ And which way is cheaper is not a matter of taste — it turns on whether the frame or the body dominates, and the answer is the opposite for these two programs:

program	frame	body	what unrolling buys
the racer (45 ticks)	1,672 B	125 B	~10× — the frame is 13× the body, so there is a great deal to amortise
rule 110 (8 generations)	566 B	2,408 B	1.21× — the body is 4.3× the frame, so there is almost nothing

Same compiler, same machine, opposite advice. Where the loop should live is an economic question, and it has to be measured per program rather than decided once.

★ And you can work out the answer before writing any of it

The frame is a fixed cost per transaction. So the most that batching can ever save is set by one ratio, and you already have both numbers:

ceiling = (frame + body) / body = 1 + frame ÷ body

program	frame ÷ body	ceiling	measured
the racer	13.4	14.4×	10.5× at 45 ticks — 73% of the way there, so there was headroom left
rule 110	0.24	1.24×	1.21× at 8 generations — 98%, so it was already finished at eight

Rule 110 was done at eight generations. Sixteen or thirty-two would have added nothing worth having, and the curve says so rather than a hunch. ★ Which means the question "is it worth batching this?" has a two-number answer available before a line is written: frame ÷ body. Small, don't bother. Thirteen, that is where the money is.

That is the same shape the computation walk had: you don't re-run the program to check it, you read the trace it left.

How to index without an index

Script cannot compute a location. There is no pointer, no computed address, nothing to put an index into — so board[move] cannot be written at all. Every program on this page meets that wall, and each one answers it differently:

the program	how it indexes	cost	why
noughts & crosses	a table of 9 comparisons	762 B	a player picks the square, so it is not known until the script runs
…the same, base 4	a shift	657 B	two bits a square, one value wasted — and every access becomes a shift
space invaders	a shift	34 B	55 slots, and a table would have cost 1,269 B
rule 110	nothing at all	—	every neighbour is at a position the compiler knows

★ The shift wins in proportion to how many things there are to index. At nine squares a table of comparisons is nearly free, so base 4 is only 1.16× better. At fifty-five it is 37×. And past 2⁵³ a table cannot be written at all, because that is where a double stops being exact — so the shift is not merely cheaper there, it is the only way the full arcade fleet exists.

⚠ Base 3 is the tighter packing — the whole board in two bytes. Base 4 is the cheaper access. Which is right depends entirely on the size of the index space, and at nine squares either is defensible. Waste a little space to make the arithmetic cheap is the oldest trade in the business, and it is what an 8-bit programmer did every day: a nibble per cell rather than a tight base-N pack, because the shift is free and the division is not.

⚠ Two traps, both found by experiment rather than by reasoning

1. A shift is big-endian. Script numbers are little-endian. So LSHIFT(NUM2BIN(1,4), k) gives 2^k only while k stays inside the first byte — it agrees up to k=5 and then diverges silently. The answer is not to reconcile them but to never convert: keep the bitmap as raw bytes, test with BITAND, clear with BITXOR, and let it never be a number at all.

2. Read as a number, a mask on the top bit of the last byte is negative zero. Exactly one alien in fifty-five would have quietly refused to die. It has to be SAMEBYTES — a byte comparison — never =, which compares numbers. That distinction is in the language for this reason, and it earned its keep on real code rather than in a comment.