Code patternsDataWalk an array of records
Walk an array of records
Does the same job on every record of a row, with one copy of the program.
Watch it run
The form “A job on every record” works on 13 cells; the named ones are “zero”, “flag”, “a”, “b” and “end”. Press Play, drag the step slider forwards and back, or edit the a of each record:
The figure needs JavaScript. The program below is the result for the example values.
Brainfuck moves are relative: "two cells to the right of here". So a piece of program written for one record works on any record, if the pointer stands on that record's first cell.
Every record starts with a flag that is 1. The loop does the job, steps one record to the right and tests the next flag. The first empty flag ends the walk.
A zero cell before the first record lets [<<<] walk home again.
The code
This is the program the figure ran. The pointer starts on “flag” (cell 3). It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
[>[->++<]>>]<<<[<<<]>>>
What it needs
- All records the same length; here 3 cells: flag, a, b.
- A zero flag after the last record and a zero cell one record length before the first.
- Any cell size.
Common mistakes
- A job that ends on another cell of the record than it started on. The step to the next record then lands in the wrong column.
- A zero in the flag column inside the row: the walk stops there.
What it costs
A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:
The figure needs JavaScript. The table below has the measured steps.
Cost as a formula, and measured
| Form | Plain steps | Optimised steps |
|---|---|---|
| A job on every record | grows with the values | 3 + 3 per record |
| A running total that travels along | grows with the values | 1 + 3 per record |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| A job on every record | a = 3, 1, 4 | 8 | 23 | 83 | 12 |
| A job on every record | a = 9, 9, 9, 9, 9 | 8 | 23 | 323 | 18 |
| A running total that travels along | a = 3, 1, 4 | 8 | 21 | 194 | 10 |
Other forms
A running total that travels along
Adds up the a of every record. The total moves from record to record in the third cell and ends just past the last record.
[>[->+<]>[->>>+<<<]>]
Run this form step by step
The form “A running total that travels along” works on 15 cells; the named ones are “zero”, “flag”, “a”, “carry”, “end” and “total”. Press Play, drag the step slider forwards and back, or edit the a of each record:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Build toward a chatbot, lesson 7, "No addresses", walks a job over 512 places.
- The chat program does every job this way: one piece of program, walked over hundreds of places. Its version lays the flags itself: one copy of code over many frames.
- Store and fetch by index is a walk that counts.
Sources
- Source: This project: emit.js and patterns.js: eachFrame in patterns.js is the grown-up form.
Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.