maux
Star on GitHub Buy me a coffee

grep, written with ed

Watch / fedgrep

Filmed on the Apple IIe 80-column display. The same session on the Videx UltraTerm: same keys, same text.

The Videx UltraTerm was an 80-column video card for the Apple IIe, with its own video memory and character generator, real hardware scrolling and more screen modes than the IIe's own 80 columns. This demo runs on either display; the UltraTerm film shows the original Videx UltraTerm, emulated.

grep is named after an ed command, g/re/p: global, regular expression, print. The demo types it again into vi as a six-line shell script that hands a here-document to ed, and runs it on the Federalist Papers: all 85 are on the disk, one file each, as plain public-domain text. It runs the script on Madison's No. 10, the paper on faction, runs the real grep on the same paper, and lets cmp say nothing. Then it runs the script over the 26 papers this edition heads MADISON, with xargs, sped up (the badge under the screen says by how much), and checks the bytes.

What it types

The script it writes, line by line:

#!/bin/sh
ed <<EOF
r $2
g/$1/p
q
EOF

Everything it types, in order. A line starting with $ is a command at the shell, RET included; keys lines are single keystrokes to a program (RET, ESC and the control keys are named).

$ cd /tmp
$ vi grep.sh
  keys: i#!/bin/sh<RET>ed <<EOF<RET>r $2<RET>g/$1/p<RET>q<RET>EOF<ESC>:wq<RET>
$ cat grep.sh
$ ls /mnt/MAUX/FED | wc -l
$ head -8 /mnt/MAUX/FED/NO.10
$ ./grep.sh faction /mnt/MAUX/FED/NO.10
$ grep faction /mnt/MAUX/FED/NO.10
$ ./grep.sh faction /mnt/MAUX/FED/NO.10 > mine
$ grep faction /mnt/MAUX/FED/NO.10 > real
$ cmp mine real
$ ls /mnt/MAUX/FED | xargs -I {} grep -lx MADISON /mnt/MAUX/FED/{} > madison
$ wc -l madison
$ xargs -I {} sh grep.sh faction {} < madison > mine
$ xargs -I {} grep faction {} < madison > real
$ wc -l mine
$ cksum madison mine real
$ cmp mine madison
$ cmp mine real

Between steps it presses ^L to clear the screen.

What the captions say

  1. grep is named after an ed command, g/re/p. Here it is again, written in vi.
  2. The Federalist Papers: 85 essays, one file each.
  3. Madison's No. 10 is about faction. Run the script on it.
  4. ed answers every mistake with a ?. This run gave it none.
  5. The real grep, on the same paper.
  6. Capture both to files, and compare them.
  7. In 1964 Mosteller and Wallace counted words to settle the disputed papers.
  8. Now the 26 papers this edition heads MADISON.
  9. One grep.sh per paper headed MADISON, sped up.

Why the 26 papers this edition heads MADISON, and not all 85

ed keeps the whole file in memory and sizes that memory when it starts. At the revision this was filmed on (63fb62c2), 462 lines of No. 83 (28,613 bytes) load and 463 lines (28,682 bytes) are refused. No. 83, the longest paper, is 34,200 bytes, so ed answers its r command with ? and the script prints that question mark, where the real grep prints nothing. The film does not hide it; it picks the papers this edition heads MADISON, none of which is near the limit. The headings are the edition's, not the authors': who wrote the disputed papers is a question this film does not settle.

The gate that proves it

This film is made by site/demos/fedgrep.py. Run as assertions, the same file is make check-demo-fedgrep, and it runs with the rest of the tests. It requires that the script reads back from vi as typed, that wc counts the papers on the disk, that head shows No. 10 as headed MADISON, dated 22 November 1787, that grep.sh prints exactly the lines of No. 10 that hold the word, in order, as the host finds them in the same bytes, that the real grep prints the same lines, and that cmp on the two captures prints nothing. For the papers headed MADISON it requires that the guest finds 26 of them; that cksum of the list, of the grep.sh output and of the grep output equals the host's checksum of the bytes each must hold; that cmp says the grep.sh output and the list differ (a positive control, so a cmp that always says nothing cannot pass); and that cmp on the two outputs prints nothing. The checks themselves were tested: with ed, grep, cmp, xargs, head or wc replaced by a copy of cat, with cmp, xargs, cksum or vi replaced by true, the demo fails at the row that uses it.

Transcript

The screen at every checkpoint the test checks, as the recorder saved it:

== the script reads back as typed (t=23.4 s)
$ cat grep.sh
#!/bin/sh
ed <<EOF
r $2
g/$1/p
q
EOF
$

== wc counts exactly the papers on the disk (t=33.3 s)
$ ls /mnt/MAUX/FED | wc -l
85
$

== the head of No. 10, as on the disk (t=38.0 s)
$ ls /mnt/MAUX/FED | wc -l
85
$ head -8 /mnt/MAUX/FED/NO.10
FEDERALIST No. 10

The Same Subject Continued (The Union as a Safeguard Against Domestic
Faction and Insurrection)

From the Daily Advertiser. Thursday, November 22, 1787.

MADISON
$

== No. 10 is Madison, 22 November 1787 (t=38.0 s)
$ ls /mnt/MAUX/FED | wc -l
85
$ head -8 /mnt/MAUX/FED/NO.10
FEDERALIST No. 10

The Same Subject Continued (The Union as a Safeguard Against Domestic
Faction and Insurrection)

From the Daily Advertiser. Thursday, November 22, 1787.

MADISON
$

== grep.sh prints the lines holding the word (t=62.5 s)
$ ./grep.sh faction /mnt/MAUX/FED/NO.10
control the violence of faction. The friend of popular governments never
By a faction, I understand a number of citizens, whether amounting to a
There are two methods of curing the mischiefs of faction: the one, by
There are again two methods of removing the causes of faction: the
worse than the disease. Liberty is to faction what air is to fire, an
it nourishes faction, than it would be to wish the annihilation of
The latent causes of faction are thus sown in the nature of man; and
the most common and durable source of factions has been the various
and faction in the necessary and ordinary operations of the government.
or, in other words, the most powerful faction must be expected to
The inference to which we are brought is, that the CAUSES of faction
If a faction consists of less than a majority, relief is supplied by the
faction, the form of popular government, on the other hand, enables it
rights against the danger of such a faction, and at the same time to
for the mischiefs of faction. A common passion or interest will, in
over a democracy, in controlling the effects of faction, is enjoyed by
political faction in a part of the Confederacy; but the variety of sects
$

== several lines (t=62.5 s)
$ ./grep.sh faction /mnt/MAUX/FED/NO.10
control the violence of faction. The friend of popular governments never
By a faction, I understand a number of citizens, whether amounting to a
There are two methods of curing the mischiefs of faction: the one, by
There are again two methods of removing the causes of faction: the
worse than the disease. Liberty is to faction what air is to fire, an
it nourishes faction, than it would be to wish the annihilation of
The latent causes of faction are thus sown in the nature of man; and
the most common and durable source of factions has been the various
and faction in the necessary and ordinary operations of the government.
or, in other words, the most powerful faction must be expected to
The inference to which we are brought is, that the CAUSES of faction
If a faction consists of less than a majority, relief is supplied by the
faction, the form of popular government, on the other hand, enables it
rights against the danger of such a faction, and at the same time to
for the mischiefs of faction. A common passion or interest will, in
over a democracy, in controlling the effects of faction, is enjoyed by
political faction in a part of the Confederacy; but the variety of sects
$

== grep prints the same lines, in the same order (t=88.7 s)
$ grep faction /mnt/MAUX/FED/NO.10
control the violence of faction. The friend of popular governments never
By a faction, I understand a number of citizens, whether amounting to a
There are two methods of curing the mischiefs of faction: the one, by
There are again two methods of removing the causes of faction: the
worse than the disease. Liberty is to faction what air is to fire, an
it nourishes faction, than it would be to wish the annihilation of
The latent causes of faction are thus sown in the nature of man; and
the most common and durable source of factions has been the various
and faction in the necessary and ordinary operations of the government.
or, in other words, the most powerful faction must be expected to
The inference to which we are brought is, that the CAUSES of faction
If a faction consists of less than a majority, relief is supplied by the
faction, the form of popular government, on the other hand, enables it
rights against the danger of such a faction, and at the same time to
for the mischiefs of faction. A common passion or interest will, in
over a democracy, in controlling the effects of faction, is enjoyed by
political faction in a part of the Confederacy; but the variety of sects
$

== the capture prints nothing (t=110.8 s)
$ ./grep.sh faction /mnt/MAUX/FED/NO.10 > mine
$

== the capture prints nothing (t=124.8 s)
$ ./grep.sh faction /mnt/MAUX/FED/NO.10 > mine
$ grep faction /mnt/MAUX/FED/NO.10 > real
$

== cmp says nothing (t=128.0 s)
$ ./grep.sh faction /mnt/MAUX/FED/NO.10 > mine
$ grep faction /mnt/MAUX/FED/NO.10 > real
$ cmp mine real
$

== the capture prints nothing (t=154.9 s)
$ ls /mnt/MAUX/FED | xargs -I {} grep -lx MADISON /mnt/MAUX/FED/{} > madison
$

== the host finds the same number of papers (t=157.6 s)
$ ls /mnt/MAUX/FED | xargs -I {} grep -lx MADISON /mnt/MAUX/FED/{} > madison
$ wc -l madison
26 madison
$

== the capture prints nothing (t=175.1 s)
$ xargs -I {} sh grep.sh faction {} < madison > mine
$

== the capture prints nothing (t=186.8 s)
$ xargs -I {} sh grep.sh faction {} < madison > mine
$ xargs -I {} grep faction {} < madison > real
$

== one line per match, as the host counts them (t=189.3 s)
$ xargs -I {} sh grep.sh faction {} < madison > mine
$ xargs -I {} grep faction {} < madison > real
$ wc -l mine
26 mine
$

== cksum (t=196.3 s)
$ cksum madison mine real
1908405861 520 madison
2850541145 1829 mine
2850541145 1829 real
$

== cksum of madison, mine and real equals the host's checksum of the expected bytes (t=196.3 s)
$ cksum madison mine real
1908405861 520 madison
2850541145 1829 mine
2850541145 1829 real
$

== the listing and the lines are different bytes (t=196.3 s)
$ cksum madison mine real
1908405861 520 madison
2850541145 1829 mine
2850541145 1829 real
$

== cmp says they differ (t=199.3 s)
$ cksum madison mine real
1908405861 520 madison
2850541145 1829 mine
2850541145 1829 real
$ cmp mine madison
mine madison differ: char 1, line 1
$

== cmp says that mine and madison differ (t=199.3 s)
$ cksum madison mine real
1908405861 520 madison
2850541145 1829 mine
2850541145 1829 real
$ cmp mine madison
mine madison differ: char 1, line 1
$

== cmp says nothing (t=202.3 s)
$ cksum madison mine real
1908405861 520 madison
2850541145 1829 mine
2850541145 1829 real
$ cmp mine madison
mine madison differ: char 1, line 1
$ cmp mine real
$