LearnBuild toward a chatbotObstacle 3: no addresses
Obstacle 3: no addresses
Aim. At the end of this lesson one piece of program does its job at 512 places on the tape, a total travels along with the pointer, and you can fetch a number from far away.
Where the lessons are going
Multiplying, adding, dividing, rounding and clamping all work now, but only in a handful of cells at the start of the tape. A model has to do it for a great many numbers, lying all along the tape.
The same job at many places
Try it: the job is the rounding of step 5 of lesson 5, written out once for every number. Drag the slider to 512 numbers and watch the length of the program:
The program is characters long.
What you just saw
The rounding takes about 11,000 characters. For 512 numbers the program is 5.7 million characters long, and it does nothing new: the same text 512 times.
A normal program would say "do this for number 1 to 512". For that it needs to say where a number is: its house number on the tape, called its address. Brainfuck has no addresses. The pointer moves one cell at a time, and every move is a character in the program.
A model rounds every number it works out. Written out like this, the program would be far too long.
One copy that walks
Try it: three sums lie on the tape: 11,868, 5,290 and −6,330. Press Play, or go to the last step, and watch where the pointer is:
What you just saw
One copy of the rounding did all three sums: 93, 41 and −49.
Remember step 5 of lesson 1: a program never says where it is, only left and right. So the text written for the first sum works on any sum, as long as the pointer stands at the start of it. The loop ends 14 cells to the right of where it began, and the next round does the same work one place further on.
Such a place, a group of cells laid out the same way each time, is called a frame. The first cell of every frame holds a 1, a marker. Each round wipes its own marker, and after the last frame the loop finds a 0 and stops. Table 1 shows what that saves.
| Rounding 512 numbers | Characters |
|---|---|
| Written out 512 times | |
| One copy that walks |
Carry a total along
Try it: press Play and follow the cell called "total". Change the four numbers if you like:
What you just saw
A total cannot stay behind in a fixed cell. From the third frame the program has no idea how far away that cell is. So the total travels: each round adds the number of this frame and moves the total one frame on.
Think of a waiter going down a row of tables with one tray. This is how the chat program looks back at the earlier word pieces: they lie side by side on the tape, and the totals walk past all of them. You build that in step 3 of lesson 10.
Fetch a number from far away
Try it: fetch record 60 with short hops only: go to the last step and read how many steps it took. Then switch to "long and short hops" and fetch it again:
Each square is one record of 6 cells. Filled: where the pointer is. Green border: every eighth record, where a long hop lands. The table has 64 records; the real one has 65,664.
What you just saw
With short hops the pointer walks past every record on the way, and a counter walks with it. With long hops it first jumps eight records at a time, then finishes with short ones.
The record number is split in two with a peel (step 3 of lesson 5): "how many eights" and "what is left". A long hop is nothing special in the program: 48 times > in a row.
The way back needs no counting. The pointer walks left until it meets a marker that says "home".
What you can do now
Do one job at every place of the tape with one copy of the program, carry values along, and fetch a number from far away. The rounding of the sum now works for every sum, wherever it lies. The third obstacle is gone.
How the real program differs
The cost of walking. About three extra steps per frame. The program for 512 frames is still longer than for 3, because planting 512 markers takes some text, but it hardly grows.
The scratch cells travel too. Every frame of step 2 has its own ten scratch cells. In the real program a gap of empty cells moves through the data instead: the program takes the frame next to the gap, works on it with the gap as scratch paper, and puts it down on the other side.
The real table. To turn your typed question into word pieces, the chat program looks up pairs of pieces in a table of 65,664 records on the tape. It hops 128 records at a time, not 8. One lookup costs about 2,600 steps. The table of step 4 is a small version of it. For nearby records the long hops cost more than they save, because splitting the record number takes steps too.