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
- grep is named after an ed command, g/re/p. Here it is again, written in vi.
- The Federalist Papers: 85 essays, one file each.
- Madison's No. 10 is about faction. Run the script on it.
- ed answers every mistake with a ?. This run gave it none.
- The real grep, on the same paper.
- Capture both to files, and compare them.
- In 1964 Mosteller and Wallace counted words to settle the disputed papers.
- Now the 26 papers this edition heads MADISON.
- 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
$