xref: /plan9/sys/doc/sam/sam.html (revision 5d535f588fe0a7c7f04081512974c9c20b5d87a8) 
1<?xml version="1.0" encoding="utf-8"?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
3"http://www.w3.org/TR/html4/loose.dtd">
4<html>
5<head>
6<meta http-equiv=Content-Type content="text/html; charset=utf8">
7<title>The Text Editor sam</title>
8</meta>
9</head>
10<body>
11<p style="margin-top: 0; margin-bottom: 0.50in"></p>
12<p style="margin-top: 0; margin-bottom: 0.21in"></p>
13
14<p style="line-height: 1.4em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: center;">
15<span style="font-size: 12pt"><b>The Text Editor </b></span><span style="font-size: 12pt"><tt>sam</tt></span><span style="font-size: 12pt"><b></b></span></p>
16<p style="margin-top: 0; margin-bottom: 0.21in"></p>
17
18<p style="margin-top: 0; margin-bottom: 0.17in"></p>
19<p style="line-height: 1.4em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: center;">
20<span style="font-size: 10pt"><i>Rob Pike</i></span></p>
21<p style="line-height: 1.4em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: center;">
22<span style="font-size: 10pt"><i>rob@plan9.bell-labs.com</i></span></p>
23<p style="margin-top: 0; margin-bottom: 0.17in"></p>
24
25<p style="margin-top: 0; margin-bottom: 0.08in"></p>
26<p style="margin-top: 0; margin-bottom: 0.33in"></p>
27<p style="line-height: 1.4em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: center;">
28<span style="font-size: 10pt"><i>ABSTRACT</i></span></p>
29<p style="margin-top: 0; margin-bottom: 0.19in"></p>
30<p style="margin-top: 0; margin-bottom: 0.05in"></p>
31<p style="line-height: 1.2em; margin-left: 1.50in; text-indent: 0.50in; margin-right: 1.50in; margin-top: 0; margin-bottom: 0; text-align: justify;">
32<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
33is an interactive multi-file text editor intended for
34bitmap displays.
35A textual command language
36supplements the mouse-driven, cut-and-paste interface
37to make complex or
38repetitive editing tasks easy to specify.
39The language is characterized by the composition of regular expressions
40to describe the structure of the text being modified.
41The treatment of files as a database, with changes logged
42as atomic transactions, guides the implementation and
43makes a general &lsquo;undo&rsquo; mechanism straightforward.
44</span><span style="font-size: 10pt"></span><span style="font-size: 10pt"></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
45<p style="line-height: 1.2em; margin-left: 1.50in; text-indent: 0.35in; margin-right: 1.50in; margin-top: 0; margin-bottom: 0; text-align: justify;">
46<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
47is implemented as two processes connected by a low-bandwidth stream,
48one process handling the display and the other the editing
49algorithms.  Therefore it can run with the display process
50in a bitmap terminal and the editor on a local host,
51with both processes on a bitmap-equipped host, or with
52the display process in the terminal and the editor in a
53remote host.
54By suppressing the display process,
55it can even run without a bitmap terminal.
56</span><span style="font-size: 10pt"></span><span style="font-size: 10pt"></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
57<p style="line-height: 1.2em; margin-left: 1.50in; text-indent: 0.35in; margin-right: 1.50in; margin-top: 0; margin-bottom: 0; text-align: justify;">
58<span style="font-size: 10pt">This paper is reprinted from Software&mdash;Practice and Experience,
59Vol 17, number 11, pp. 813-845, November 1987.
60The paper has not been updated for the Plan 9 manuals.  Although
61</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
62has not changed much since the paper was written, the system around it certainly has.
63Nonetheless, the description here still stands as the best introduction to the editor.
64</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
65
66<p style="margin-top: 0; margin-bottom: 0.17in"></p>
67<p style="margin-top: 0; margin-bottom: 0.17in"></p>
68<p style="margin-top: 0; margin-bottom: 0.50in"></p>
69<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
70<span style="font-size: 10pt"><b>Introduction
71</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
72<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
73<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
74is an interactive text editor that combines cut-and-paste interactive editing with
75an unusual command language based on the composition of regular expressions.
76It is written as two programs: one, the &lsquo;host part,&rsquo; runs on a UNIX system
77and implements the command language and provides file access; the other, the
78&lsquo;terminal part,&rsquo; runs asynchronously
79on a machine with a mouse and bitmap display
80and supports the display and interactive editing.
81The host part may be even run in isolation on an ordinary terminal
82to edit text using the command
83language, much like a traditional line editor,
84without assistance from a mouse or display.
85Most often,
86the terminal part runs on a Blit<sup></sup></span><sup><span style="font-size: 6pt">1</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt"> terminal
87(actually on a Teletype DMD 5620, the production version of the Blit), whose
88host connection is an ordinary 9600 bps RS232 link;
89on the SUN computer the host and display processes run on a single machine,
90connected by a pipe.
91</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
92<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
93<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
94edits uninterpreted
95ASCII text.
96It has no facilities for multiple fonts, graphics or tables,
97unlike MacWrite,<sup></sup></span><sup><span style="font-size: 6pt">2</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt"> Bravo,<sup></sup></span><sup><span style="font-size: 6pt">3</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt"> Tioga<sup></sup></span><sup><span style="font-size: 6pt">4</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
98or Lara.<sup></sup></span><sup><span style="font-size: 6pt">5</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
99Also unlike them, it has a rich command language.
100(Throughout this paper, the phrase
101</span><span style="font-size: 10pt"><i>command language
102</i></span><span style="font-size: 10pt">refers to
103textual commands; commands activated from the mouse form the
104</span><span style="font-size: 10pt"><i>mouse</i></span><span style="font-size: 10pt">
105</span><span style="font-size: 10pt"><i>language.</i></span><span style="font-size: 10pt">)
106</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
107developed as an editor for use by programmers, and tries to join
108the styles of the UNIX text editor
109</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt"><sup></sup></span><sup><span style="font-size: 6pt">6,7</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
110with that of interactive cut-and-paste editors by
111providing a comfortable mouse-driven interface
112to a program with a solid command language driven by regular expressions.
113The command language developed more than the mouse language, and
114acquired a notation for describing the structure of files
115more richly than as a sequence of lines,
116using a dataflow-like syntax for specifying changes.
117</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
118<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
119<span style="font-size: 10pt">The interactive style was influenced by
120</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">1</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
121an early cut-and-paste editor for the Blit, and by
122</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">8</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
123the Blit window system.
124</span><span style="font-size: 10pt"><tt>Mux</tt></span><span style="font-size: 10pt">
125merges the original Blit window system,
126</span><span style="font-size: 10pt"><tt>mpx</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">1</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
127with cut-and-paste editing, forming something like a
128multiplexed version of
129</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
130that edits the output of (and input to) command sessions rather than files.
131</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
132<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
133<span style="font-size: 10pt">The first part of this paper describes the command language, then the mouse
134language, and explains how they interact.
135That is followed by a description of the implementation,
136first of the host part, then of the terminal part.
137A principle that influenced the design of
138</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
139is that it should have no explicit limits, such as upper limits on
140file size or line length.
141A secondary consideration is that it be efficient.
142To honor these two goals together requires a method for efficiently
143manipulating
144huge strings (files) without breaking them into lines,
145perhaps while making thousands of changes
146under control of the command language.
147</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">&rsquo;s
148method is to
149treat the file as a transaction database, implementing changes as atomic
150updates.  These updates may be unwound easily to &lsquo;undo&rsquo; changes.
151Efficiency is achieved through a collection of caches that minimizes
152disc traffic and data motion, both within the two parts of the program
153and between them.
154</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
155<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
156<span style="font-size: 10pt">The terminal part of
157</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
158is fairly straightforward.
159More interesting is how the two halves of the editor stay
160synchronized when either half may initiate a change.
161This is achieved through a data structure that organizes the
162communications and is maintained in parallel by both halves.
163</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
164<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
165<span style="font-size: 10pt">The last part of the paper chronicles the writing of
166</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
167and discusses the lessons that were learned through its development and use.
168</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
169<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
170<span style="font-size: 10pt">The paper is long, but is composed largely of two papers of reasonable length:
171a description of the user interface of
172</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
173and a discussion of its implementation.
174They are combined because the implementation is strongly influenced by
175the user interface, and vice versa.
176</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
177<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
178<span style="font-size: 10pt"><b>The Interface
179</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
180<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
181<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
182is a text editor for multiple files.
183File names may be provided when it is invoked:
184</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
185<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
186<span style="font-size: 9pt"><tt>sam file1 file2 ...</tt></span></p>
187<p style="margin-top: 0; margin-bottom: 0.17in"></p>
188
189<p style="margin-top: 0; margin-bottom: 0.08in"></p>
190<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
191<span style="font-size: 10pt">and there are commands
192to add new files and discard unneeded ones.
193Files are not read until necessary
194to complete some command.
195Editing operations apply to an internal copy
196made when the file is read; the UNIX file associated with the copy
197is changed only by an explicit command.
198To simplify the discussion, the internal copy is here called a
199</span><span style="font-size: 10pt"><i>file</i></span><span style="font-size: 10pt">,
200while the disc-resident original is called a
201</span><span style="font-size: 10pt"><i>disc file.
202</i></span><span style="font-size: 10pt"></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
203<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
204<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
205is usually connected to a bitmap display that presents a cut-and-paste
206editor driven by the mouse.
207In this mode, the command language is still available:
208text typed in a special window, called the
209</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
210</span><span style="font-size: 10pt"><i>window,</i></span><span style="font-size: 10pt">
211is interpreted
212as commands to be executed in the current file.
213Cut-and-paste editing may be used in any window &mdash; even in the
214</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
215window to construct commands.
216The other mode of operation, invoked by starting
217</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
218with the option
219</span><span style="font-size: 10pt"><tt>-d</tt></span><span style="font-size: 10pt">
220(for &lsquo;no download&rsquo;),
221does not use the mouse or bitmap display, but still permits
222editing using the textual command language, even on an ordinary terminal,
223interactively or from a script.
224</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
225<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
226<span style="font-size: 10pt">The following sections describe first the command language (under
227</span><span style="font-size: 10pt"><tt>sam\fP-d
228and in the
229</tt></span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt"><tt>
230window), and then the mouse interface.
231These two languages are nearly independent, but connect through the
232</tt></span><span style="font-size: 10pt"><i>current</i></span><span style="font-size: 10pt"><tt>
233</tt></span><span style="font-size: 10pt"><i>text,</i></span><span style="font-size: 10pt"><tt>
234described below.
235</tt></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
236<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
237<span style="font-size: 10pt"><b>The Command Language
238</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
239<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
240<span style="font-size: 10pt">A file consists of its contents, which are an array of characters
241(that is, a string); the
242</span><span style="font-size: 10pt"><i>name</i></span><span style="font-size: 10pt">
243of the associated disc file; the
244</span><span style="font-size: 10pt"><i>modified bit
245</i></span><span style="font-size: 10pt">that states whether the contents match those of
246the disc file;
247and a substring of the contents, called the
248</span><span style="font-size: 10pt"><i>current text
249</i></span><span style="font-size: 10pt">or
250</span><span style="font-size: 10pt"><i>dot</i></span><span style="font-size: 10pt">
251(see Figures 1 and 2).
252If the current text is a null string, dot falls between characters.
253The
254</span><span style="font-size: 10pt"><i>value</i></span><span style="font-size: 10pt">
255of dot is the location of the current text; the
256</span><span style="font-size: 10pt"><i>contents</i></span><span style="font-size: 10pt">
257of dot are the characters it contains.
258</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
259imparts to the text no two-dimensional interpretation such as columns
260or fields; text is always one-dimensional.
261Even the idea of a &lsquo;line&rsquo; of text as understood by most UNIX programs
262&mdash; a sequence of characters terminated by a newline character &mdash;
263is only weakly supported.
264</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
265<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
266<span style="font-size: 10pt">The
267</span><span style="font-size: 10pt"><i>current file
268</i></span><span style="font-size: 10pt">is the file to which editing commands refer.
269The current text is therefore dot in the current file.
270If a command doesn&rsquo;t explicitly name a particular file or piece of text,
271the command is assumed to apply to the current text.
272For the moment, ignore the presence of multiple files and consider
273editing a single file.
274</span><span style="font-size: 10pt"></span></p><center><img src="fig1.gif" /></center>
275<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
276<span style="font-size: 8pt"><i>Figure 1. A typical
277</i></span><span style="font-size: 8pt"><tt>sam</tt></span><span style="font-size: 8pt"><i>
278screen, with the editing menu presented.
279The
280</i></span><span style="font-size: 8pt"><tt>sam</tt></span><span style="font-size: 8pt"><i>
281(command language) window is in the middle, with file windows above and below.
282(The user interface makes it easy to create these abutting windows.)
283The partially obscured window is a third file window.
284The uppermost window is that to which typing and mouse operations apply,
285as indicated by its heavy border.
286Each window has its current text highlighted in reverse video.
287The
288</i></span><span style="font-size: 8pt"><tt>sam</tt></span><span style="font-size: 8pt"><i>
289window&rsquo;s current text is the null string on the last visible line,
290indicated by a vertical bar.
291See also Figure 2.
292</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
293<p style="margin-top: 0; margin-bottom: 0.02in"></p>
294
295<p style="margin-top: 0; margin-bottom: 0.05in"></p>
296<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
297<span style="font-size: 10pt">Commands have one-letter names.
298Except for non-editing commands such as writing
299the file to disc, most commands make some change
300to the text in dot and leave dot set to the text resulting from the change.
301For example, the delete command,
302</span><span style="font-size: 10pt"><tt>d</tt></span><span style="font-size: 10pt">,
303deletes the text in dot, replacing it by the null string and setting dot
304to the result.
305The change command,
306</span><span style="font-size: 10pt"><tt>c</tt></span><span style="font-size: 10pt">,
307replaces dot by text delimited by an arbitrary punctuation character,
308conventionally
309a slash.  Thus,
310</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
311<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
312<span style="font-size: 9pt"><tt>c/Peter/</tt></span></p>
313<p style="margin-top: 0; margin-bottom: 0.17in"></p>
314
315<p style="margin-top: 0; margin-bottom: 0.08in"></p>
316<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
317<span style="font-size: 10pt">replaces the text in dot by the string
318</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">.
319Similarly,
320</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
321<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
322<span style="font-size: 9pt"><tt>a/Peter/</tt></span></p>
323<p style="margin-top: 0; margin-bottom: 0.17in"></p>
324
325<p style="margin-top: 0; margin-bottom: 0.08in"></p>
326<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
327<span style="font-size: 10pt">(append) adds the string after dot, and
328</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
329<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
330<span style="font-size: 9pt"><tt>i/Peter/</tt></span></p>
331<p style="margin-top: 0; margin-bottom: 0.17in"></p>
332
333<p style="margin-top: 0; margin-bottom: 0.08in"></p>
334<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
335<span style="font-size: 10pt">(insert) inserts before dot.
336All three leave dot set to the new text,
337</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">.
338</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
339<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
340<span style="font-size: 10pt">Newlines are part of the syntax of commands:
341the newline character lexically terminates a command.
342Within the inserted text, however, newlines are never implicit.
343But since it is often convenient to insert multiple lines of text,
344</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
345has a special
346syntax for that case:
347</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
348<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
349<span style="font-size: 9pt"><tt>a</tt></span></p>
350<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
351<span style="font-size: 9pt"><tt>some lines of text</tt></span></p>
352<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
353<span style="font-size: 9pt"><tt>to be inserted in the file,</tt></span></p>
354<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
355<span style="font-size: 9pt"><tt>terminated by a period</tt></span></p>
356<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
357<span style="font-size: 9pt"><tt>on a line by itself</tt></span></p>
358<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
359<span style="font-size: 9pt"><tt>.</tt></span></p>
360<p style="margin-top: 0; margin-bottom: 0.17in"></p>
361
362<p style="margin-top: 0; margin-bottom: 0.08in"></p>
363<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
364<span style="font-size: 10pt">In the one-line syntax, a newline character may be specified by a C-like
365escape, so
366</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
367<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
368<span style="font-size: 9pt"><tt>c/\n/</tt></span></p>
369<p style="margin-top: 0; margin-bottom: 0.17in"></p>
370
371<p style="margin-top: 0; margin-bottom: 0.08in"></p>
372<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
373<span style="font-size: 10pt">replaces dot by a single newline character.
374</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
375<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
376<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
377also has a substitute command,
378</span><span style="font-size: 10pt"><tt>s</tt></span><span style="font-size: 10pt">:
379</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
380<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
381<span style="font-size: 9pt"><tt>s/</tt></span><span style="font-size: 9pt"><i>expression</i></span><span style="font-size: 9pt"><tt>/</tt></span><span style="font-size: 9pt"><i>replacement</i></span><span style="font-size: 9pt"><tt>/</tt></span></p>
382<p style="margin-top: 0; margin-bottom: 0.17in"></p>
383
384<p style="margin-top: 0; margin-bottom: 0.08in"></p>
385<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
386<span style="font-size: 10pt">substitutes the replacement text for the first match, in dot,
387of the regular expression.
388Thus, if dot is the string
389</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">,
390the command
391</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
392<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
393<span style="font-size: 9pt"><tt>s/t/st/</tt></span></p>
394<p style="margin-top: 0; margin-bottom: 0.17in"></p>
395
396<p style="margin-top: 0; margin-bottom: 0.08in"></p>
397<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
398<span style="font-size: 10pt">changes it to
399</span><span style="font-size: 10pt"><tt>Pester</tt></span><span style="font-size: 10pt">.
400In general,
401</span><span style="font-size: 10pt"><tt>s</tt></span><span style="font-size: 10pt">
402is unnecessary, but it was inherited from
403</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
404and it has some convenient variations.
405For instance, the replacement text may include the matched text,
406specified by
407</span><span style="font-size: 10pt"><tt>&amp;</tt></span><span style="font-size: 10pt">:
408</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
409<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
410<span style="font-size: 9pt"><tt>s/Peter/Oh, &amp;, &amp;, &amp;, &amp;!/</tt></span></p>
411<p style="margin-top: 0; margin-bottom: 0.17in"></p>
412
413<p style="margin-top: 0; margin-bottom: 0.08in"></p>
414<p style="margin-top: 0; margin-bottom: 0.05in"></p>
415<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
416<span style="font-size: 10pt">There are also three commands that apply programs
417to text:
418</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
419<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
420<span style="font-size: 9pt"><tt>&lt; </tt></span><span style="font-size: 9pt"><i>UNIX program</i></span><span style="font-size: 9pt"><tt></tt></span></p>
421<p style="margin-top: 0; margin-bottom: 0.17in"></p>
422
423<p style="margin-top: 0; margin-bottom: 0.08in"></p>
424<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
425<span style="font-size: 10pt">replaces dot by the output of the UNIX program.
426Similarly, the
427</span><span style="font-size: 10pt"><tt>&gt;</tt></span><span style="font-size: 10pt">
428command
429runs the program with dot as its standard input, and
430</span><span style="font-size: 10pt"><tt>|</tt></span><span style="font-size: 10pt">
431does both.  For example,
432</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
433<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
434<span style="font-size: 9pt"><tt>| sort</tt></span></p>
435<p style="margin-top: 0; margin-bottom: 0.17in"></p>
436
437<p style="margin-top: 0; margin-bottom: 0.08in"></p>
438<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
439<span style="font-size: 10pt">replaces dot by the result of applying the standard sorting utility to it.
440Again, newlines have no special significance for these
441</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
442commands.
443The text acted upon and resulting from these commands is not necessarily
444bounded by newlines, although for connection with UNIX programs,
445newlines may be necessary to obey conventions.
446</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
447<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
448<span style="font-size: 10pt">One more command:
449</span><span style="font-size: 10pt"><tt>p</tt></span><span style="font-size: 10pt">
450prints the contents of dot.
451Table I summarizes
452</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
453commands.
454</span><span style="font-size: 10pt"></span></p><center><img src="sam0.png"></center>
455</center>
456<p style="margin-top: 0; margin-bottom: 0.17in"></p>
457<p style="margin-top: 0; margin-bottom: 0.02in"></p>
458
459<p style="margin-top: 0; margin-bottom: 0.05in"></p>
460<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
461<span style="font-size: 10pt">The value of dot may be changed by
462specifying an
463</span><span style="font-size: 10pt"><i>address</i></span><span style="font-size: 10pt">
464for the command.
465The simplest address is a line number:
466</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
467<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
468<span style="font-size: 9pt"><tt>3</tt></span></p>
469<p style="margin-top: 0; margin-bottom: 0.17in"></p>
470
471<p style="margin-top: 0; margin-bottom: 0.08in"></p>
472<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
473<span style="font-size: 10pt">refers to the third line of the file, so
474</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
475<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
476<span style="font-size: 9pt"><tt>3d</tt></span></p>
477<p style="margin-top: 0; margin-bottom: 0.17in"></p>
478
479<p style="margin-top: 0; margin-bottom: 0.08in"></p>
480<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
481<span style="font-size: 10pt">deletes the third line of the file, and implicitly renumbers
482the lines so the old line 4 is now numbered 3.
483(This is one of the few places where
484</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
485deals with lines directly.)
486Line
487</span><span style="font-size: 10pt"><tt>0</tt></span><span style="font-size: 10pt">
488is the null string at the beginning of the file.
489If a command consists of only an address, a
490</span><span style="font-size: 10pt"><tt>p</tt></span><span style="font-size: 10pt">
491command is assumed, so typing an unadorned
492</span><span style="font-size: 10pt"><tt>3</tt></span><span style="font-size: 10pt">
493prints line 3 on the terminal.
494There are a couple of other basic addresses:
495a period addresses dot itself; and
496a dollar sign
497(</span><span style="font-size: 10pt"><tt>$</tt></span><span style="font-size: 10pt">)
498addresses the null string at the end of the file.
499</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
500<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
501<span style="font-size: 10pt">An address is always a single substring of the file.
502Thus, the address
503</span><span style="font-size: 10pt"><tt>3</tt></span><span style="font-size: 10pt">
504addresses the characters
505after the second newline of
506the file through the third newline of the file.
507A
508</span><span style="font-size: 10pt"><i>compound address
509</i></span><span style="font-size: 10pt">is constructed by the comma operator
510</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
511<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
512<span style="font-size: 9pt"><i>address1</i></span><span style="font-size: 9pt"><tt>,</tt></span><span style="font-size: 9pt"><i>address2</i></span><span style="font-size: 9pt"><tt></tt></span></p>
513<p style="margin-top: 0; margin-bottom: 0.17in"></p>
514
515<p style="margin-top: 0; margin-bottom: 0.08in"></p>
516<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
517<span style="font-size: 10pt">and addresses the substring of the file from the beginning of
518</span><span style="font-size: 10pt"><i>address1</i></span><span style="font-size: 10pt">
519to the end of
520</span><span style="font-size: 10pt"><i>address2</i></span><span style="font-size: 10pt">.
521For example, the command
522</span><span style="font-size: 10pt"><tt>3,5p</tt></span><span style="font-size: 10pt">
523prints the third through fifth lines of the file and
524</span><span style="font-size: 10pt"><tt>.,$d</tt></span><span style="font-size: 10pt">
525deletes the text from the beginning of dot to the end of the file.
526</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
527<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
528<span style="font-size: 10pt">These addresses are all absolute positions in the file, but
529</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
530also has relative addresses, indicated by
531</span><span style="font-size: 10pt"><tt>+</tt></span><span style="font-size: 10pt">
532or
533</span><span style="font-size: 10pt"><tt>-</tt></span><span style="font-size: 10pt">.
534For example,
535</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
536<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
537<span style="font-size: 9pt"><tt>$-3</tt></span></p>
538<p style="margin-top: 0; margin-bottom: 0.17in"></p>
539
540<p style="margin-top: 0; margin-bottom: 0.08in"></p>
541<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
542<span style="font-size: 10pt">is the third line before the end of the file and
543</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
544<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
545<span style="font-size: 9pt"><tt>.+1</tt></span></p>
546<p style="margin-top: 0; margin-bottom: 0.17in"></p>
547
548<p style="margin-top: 0; margin-bottom: 0.08in"></p>
549<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
550<span style="font-size: 10pt">is the line after dot.
551If no address appears to the left of the
552</span><span style="font-size: 10pt"><tt>+</tt></span><span style="font-size: 10pt">
553or
554</span><span style="font-size: 10pt"><tt>-</tt></span><span style="font-size: 10pt">,
555dot is assumed;
556if nothing appears to the right,
557</span><span style="font-size: 10pt"><tt>1</tt></span><span style="font-size: 10pt">
558is assumed.
559Therefore,
560</span><span style="font-size: 10pt"><tt>.+1</tt></span><span style="font-size: 10pt">
561may be abbreviated to just a plus sign.
562</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
563<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
564<span style="font-size: 10pt">The
565</span><span style="font-size: 10pt"><tt>+</tt></span><span style="font-size: 10pt">
566operator acts relative to the end of its first argument, while the
567</span><span style="font-size: 10pt"><tt>-</tt></span><span style="font-size: 10pt">
568operator acts relative to the beginning.  Thus
569</span><span style="font-size: 10pt"><tt>.+1</tt></span><span style="font-size: 10pt">
570addresses the first line after dot,
571</span><span style="font-size: 10pt"><tt>.-</tt></span><span style="font-size: 10pt">
572addresses the first line before dot, and
573</span><span style="font-size: 10pt"><tt>+-</tt></span><span style="font-size: 10pt">
574refers to the line containing the end of dot.  (Dot may span multiple lines, and
575</span><span style="font-size: 10pt"><tt>+</tt></span><span style="font-size: 10pt">
576selects the line after the end of dot, then
577</span><span style="font-size: 10pt"><tt>-</tt></span><span style="font-size: 10pt">
578backs up one line.)
579</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
580<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
581<span style="font-size: 10pt">The final type of address is a regular expression, which addresses the
582text matched by the expression.  The expression is enclosed in slashes, as in
583</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
584<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
585<span style="font-size: 9pt"><tt>/</tt></span><span style="font-size: 9pt"><i>expression</i></span><span style="font-size: 9pt"><tt>/</tt></span></p>
586<p style="margin-top: 0; margin-bottom: 0.17in"></p>
587
588<p style="margin-top: 0; margin-bottom: 0.08in"></p>
589<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
590<span style="font-size: 10pt">The expressions are the same as those in the UNIX program
591</span><span style="font-size: 10pt"><tt>egrep</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">6,7</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
592and include closures, alternations, and so on.
593They find the
594</span><span style="font-size: 10pt"><i>leftmost longest
595</i></span><span style="font-size: 10pt">string that matches the expression, that is,
596the first match after the point where the search is started,
597and if more than one match begins at the same spot, the longest such match.
598(I assume familiarity with the syntax for regular expressions in UNIX programs.<sup></sup></span><sup><span style="font-size: 6pt">9</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">)
599For example,
600</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
601<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
602<span style="font-size: 9pt"><tt>/x/</tt></span></p>
603<p style="margin-top: 0; margin-bottom: 0.17in"></p>
604
605<p style="margin-top: 0; margin-bottom: 0.08in"></p>
606<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
607<span style="font-size: 10pt">matches the next
608</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
609character in the file,
610</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
611<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
612<span style="font-size: 9pt"><tt>/xx*/</tt></span></p>
613<p style="margin-top: 0; margin-bottom: 0.17in"></p>
614
615<p style="margin-top: 0; margin-bottom: 0.08in"></p>
616<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
617<span style="font-size: 10pt">matches the next run of one or more
618</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">&rsquo;s,
619and
620</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
621<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
622<span style="font-size: 9pt"><tt>/x|Peter/</tt></span></p>
623<p style="margin-top: 0; margin-bottom: 0.17in"></p>
624
625<p style="margin-top: 0; margin-bottom: 0.08in"></p>
626<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
627<span style="font-size: 10pt">matches the next
628</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
629or
630</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">.
631For compatibility with other UNIX programs, the &lsquo;any character&rsquo; operator,
632a period,
633does not match a newline, so
634</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
635<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
636<span style="font-size: 9pt"><tt>/.*/</tt></span></p>
637<p style="margin-top: 0; margin-bottom: 0.17in"></p>
638
639<p style="margin-top: 0; margin-bottom: 0.08in"></p>
640<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
641<span style="font-size: 10pt">matches the text from dot to the end of the line, but excludes the newline
642and so will not match across
643the line boundary.
644</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
645<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
646<span style="font-size: 10pt">Regular expressions are always relative addresses.
647The direction is forwards by default,
648so
649</span><span style="font-size: 10pt"><tt>/Peter/</tt></span><span style="font-size: 10pt">
650is really an abbreviation for
651</span><span style="font-size: 10pt"><tt>+/Peter/</tt></span><span style="font-size: 10pt">.
652The search can be reversed with a minus sign, so
653</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
654<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
655<span style="font-size: 9pt"><tt></tt></span><span style="font-size: 9pt"><tt>-/Peter/</tt></span><span style="font-size: 9pt"><tt></tt></span></p>
656<p style="margin-top: 0; margin-bottom: 0.17in"></p>
657
658<p style="margin-top: 0; margin-bottom: 0.08in"></p>
659<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
660<span style="font-size: 10pt">finds the first
661</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">
662before dot.
663Regular expressions may be used with other address forms, so
664</span><span style="font-size: 10pt"><tt>0+/Peter/</tt></span><span style="font-size: 10pt">
665finds the first
666</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">
667in the file and
668</span><span style="font-size: 10pt"><tt>$-/Peter/</tt></span><span style="font-size: 10pt">
669finds the last.
670Table II summarizes
671</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
672addresses.
673</span><span style="font-size: 10pt"></span></p><center><img src="sam1.png"></center>
674</center>
675<p style="margin-top: 0; margin-bottom: 0.17in"></p>
676<p style="margin-top: 0; margin-bottom: 0.02in"></p>
677
678<p style="margin-top: 0; margin-bottom: 0.05in"></p>
679<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
680<span style="font-size: 10pt">The language discussed so far will not seem novel
681to people who use UNIX text editors
682such as
683</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
684or
685</span><span style="font-size: 10pt"><tt>vi</tt></span><span style="font-size: 10pt">.<sup></sup></span><sup><span style="font-size: 6pt">9</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
686Moreover, the kinds of editing operations these commands allow, with the exception
687of regular expressions and line numbers,
688are clearly more conveniently handled by a mouse-based interface.
689Indeed,
690</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
691mouse language (discussed at length below) is the means by which
692simple changes are usually made.
693For large or repetitive changes, however, a textual language
694outperforms a manual interface.
695</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
696<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
697<span style="font-size: 10pt">Imagine that, instead of deleting just one occurrence of the string
698</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">,
699we wanted to eliminate every
700</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">.
701What&rsquo;s needed is an iterator that runs a command for each occurrence of some
702text.
703</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">&rsquo;s
704iterator is called
705</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">,
706for extract:
707</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
708<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
709<span style="font-size: 9pt"><tt>x/</tt></span><span style="font-size: 9pt"><i>expression</i></span><span style="font-size: 9pt"><tt>/ </tt></span><span style="font-size: 9pt"><i>command</i></span><span style="font-size: 9pt"><tt></tt></span></p>
710<p style="margin-top: 0; margin-bottom: 0.17in"></p>
711
712<p style="margin-top: 0; margin-bottom: 0.08in"></p>
713<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
714<span style="font-size: 10pt">finds all matches in dot of the specified expression, and for each
715such match, sets dot to the text matched and runs the command.
716So to delete all the
717</span><span style="font-size: 10pt"><tt>Peters:</tt></span><span style="font-size: 10pt">
718</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
719<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
720<span style="font-size: 9pt"><tt>0,$ x/Peter/ d</tt></span></p>
721<p style="margin-top: 0; margin-bottom: 0.17in"></p>
722
723<p style="margin-top: 0; margin-bottom: 0.08in"></p>
724<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
725<span style="font-size: 10pt">(Blanks in these examples are to improve readability;
726</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
727neither requires nor interprets them.)
728This searches the entire file
729(</span><span style="font-size: 10pt"><tt>0,$</tt></span><span style="font-size: 10pt">)
730for occurrences of the string
731</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">,
732and runs the
733</span><span style="font-size: 10pt"><tt>d</tt></span><span style="font-size: 10pt">
734command with dot set to each such occurrence.
735(By contrast, the comparable
736</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
737command would delete all
738</span><span style="font-size: 10pt"><i>lines</i></span><span style="font-size: 10pt">
739containing
740</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">;
741</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
742deletes only the
743</span><span style="font-size: 10pt"><tt>Peters</tt></span><span style="font-size: 10pt">.)
744The address
745</span><span style="font-size: 10pt"><tt>0,$</tt></span><span style="font-size: 10pt">
746is commonly used, and may be abbreviated to just a comma.
747As another example,
748</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
749<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
750<span style="font-size: 9pt"><tt>, x/Peter/ p</tt></span></p>
751<p style="margin-top: 0; margin-bottom: 0.17in"></p>
752
753<p style="margin-top: 0; margin-bottom: 0.08in"></p>
754<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
755<span style="font-size: 10pt">prints a list of
756</span><span style="font-size: 10pt"><tt>Peters,</tt></span><span style="font-size: 10pt">
757one for each appearance in the file, with no intervening text (not even newlines
758to separate the instances).
759</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
760<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
761<span style="font-size: 10pt">Of course, the text extracted by
762</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
763may be selected by a regular expression,
764which complicates deciding what set of matches is chosen &mdash;
765matches may overlap.  This is resolved by generating the matches
766starting from the beginning of dot using the leftmost-longest rule,
767and searching for each match starting from the end of the previous one.
768Regular expressions may also match null strings, but a null match
769adjacent to a non-null match is never selected; at least one character
770must intervene.
771For example,
772</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
773<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
774<span style="font-size: 9pt"><tt>, c/AAA/</tt></span></p>
775<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
776<span style="font-size: 9pt"><tt>x/B*/ c/-/</tt></span></p>
777<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
778<span style="font-size: 9pt"><tt>, p</tt></span></p>
779<p style="margin-top: 0; margin-bottom: 0.17in"></p>
780
781<p style="margin-top: 0; margin-bottom: 0.08in"></p>
782<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
783<span style="font-size: 10pt">produces as output
784</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
785<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
786<span style="font-size: 9pt"><tt>-A-A-A-</tt></span></p>
787<p style="margin-top: 0; margin-bottom: 0.17in"></p>
788
789<p style="margin-top: 0; margin-bottom: 0.08in"></p>
790<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
791<span style="font-size: 10pt">because the pattern
792</span><span style="font-size: 10pt"><tt>B*</tt></span><span style="font-size: 10pt">
793matches the null strings separating the
794</span><span style="font-size: 10pt"><tt>A</tt></span><span style="font-size: 10pt">&rsquo;s.
795</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
796<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
797<span style="font-size: 10pt">The
798</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
799command has a complement,
800</span><span style="font-size: 10pt"><tt>y</tt></span><span style="font-size: 10pt">,
801with similar syntax, that executes the command with dot set to the text
802</span><span style="font-size: 10pt"><i>between</i></span><span style="font-size: 10pt">
803the matches of the expression.
804For example,
805</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
806<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
807<span style="font-size: 9pt"><tt>, c/AAA/</tt></span></p>
808<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
809<span style="font-size: 9pt"><tt>y/A/ c/-/</tt></span></p>
810<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
811<span style="font-size: 9pt"><tt>, p</tt></span></p>
812<p style="margin-top: 0; margin-bottom: 0.17in"></p>
813
814<p style="margin-top: 0; margin-bottom: 0.08in"></p>
815<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
816<span style="font-size: 10pt">produces the same result as the example above.
817</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
818<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
819<span style="font-size: 10pt">The
820</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
821and
822</span><span style="font-size: 10pt"><tt>y</tt></span><span style="font-size: 10pt">
823commands are looping constructs, and
824</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
825has a pair of conditional commands to go with them.
826They have similar syntax:
827</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
828<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
829<span style="font-size: 9pt"><tt>g/</tt></span><span style="font-size: 9pt"><i>expression</i></span><span style="font-size: 9pt"><tt>/ </tt></span><span style="font-size: 9pt"><i>command</i></span><span style="font-size: 9pt"><tt></tt></span></p>
830<p style="margin-top: 0; margin-bottom: 0.17in"></p>
831
832<p style="margin-top: 0; margin-bottom: 0.08in"></p>
833<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
834<span style="font-size: 10pt">(guard)
835runs the command exactly once if dot contains a match of the expression.
836This is different from
837</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">,
838which runs the command for
839</span><span style="font-size: 10pt"><i>each</i></span><span style="font-size: 10pt">
840match:
841</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
842loops;
843</span><span style="font-size: 10pt"><tt>g</tt></span><span style="font-size: 10pt">
844merely tests, without changing the value of dot.
845Thus,
846</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
847<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
848<span style="font-size: 9pt"><tt>, x/Peter/ d</tt></span></p>
849<p style="margin-top: 0; margin-bottom: 0.17in"></p>
850
851<p style="margin-top: 0; margin-bottom: 0.08in"></p>
852<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
853<span style="font-size: 10pt">deletes all occurrences of
854</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">,
855but
856</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
857<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
858<span style="font-size: 9pt"><tt>, g/Peter/ d</tt></span></p>
859<p style="margin-top: 0; margin-bottom: 0.17in"></p>
860
861<p style="margin-top: 0; margin-bottom: 0.08in"></p>
862<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
863<span style="font-size: 10pt">deletes the whole file (reduces it to a null string) if
864</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">
865occurs anywhere in the text.
866The complementary conditional is
867</span><span style="font-size: 10pt"><tt>v</tt></span><span style="font-size: 10pt">,
868which runs the command if there is
869</span><span style="font-size: 10pt"><i>no</i></span><span style="font-size: 10pt">
870match of the expression.
871</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
872<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
873<span style="font-size: 10pt">These control-structure-like commands may be composed to construct more
874involved operations.  For example, to print those lines of text that
875contain the string
876</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">:
877</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
878<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
879<span style="font-size: 9pt"><tt>, x/.*\n/ g/Peter/ p</tt></span></p>
880<p style="margin-top: 0; margin-bottom: 0.17in"></p>
881
882<p style="margin-top: 0; margin-bottom: 0.08in"></p>
883<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
884<span style="font-size: 10pt">The
885</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
886breaks the file into lines, the
887</span><span style="font-size: 10pt"><tt>g</tt></span><span style="font-size: 10pt">
888selects those lines containing
889</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">,
890and the
891</span><span style="font-size: 10pt"><tt>p</tt></span><span style="font-size: 10pt">
892prints them.
893This command gives an address for the
894</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
895command (the whole file), but because
896</span><span style="font-size: 10pt"><tt>g</tt></span><span style="font-size: 10pt">
897does not have an explicit address, it applies to the value of
898dot produced by the
899</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
900command, that is, to each line.
901All commands in
902</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
903except for the command to write a file to disc use dot for the
904default address.
905</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
906<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
907<span style="font-size: 10pt">Composition may be continued indefinitely.
908</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
909<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
910<span style="font-size: 9pt"><tt>, x/.*\n/ g/Peter/ v/SaltPeter/ p</tt></span></p>
911<p style="margin-top: 0; margin-bottom: 0.17in"></p>
912
913<p style="margin-top: 0; margin-bottom: 0.08in"></p>
914<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
915<span style="font-size: 10pt">prints those lines containing
916</span><span style="font-size: 10pt"><tt>Peter</tt></span><span style="font-size: 10pt">
917but
918</span><span style="font-size: 10pt"><i>not</i></span><span style="font-size: 10pt">
919those containing
920</span><span style="font-size: 10pt"><tt>SaltPeter</tt></span><span style="font-size: 10pt">.
921</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
922<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
923<span style="font-size: 10pt"><b>Structural Regular Expressions
924</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
925<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
926<span style="font-size: 10pt">Unlike other UNIX text editors,
927including the non-interactive ones such as
928</span><span style="font-size: 10pt"><tt>sed</tt></span><span style="font-size: 10pt">
929and
930</span><span style="font-size: 10pt"><tt>awk</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">7</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
931</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
932is good for manipulating files with multi-line &lsquo;records.&rsquo;
933An example is an on-line phone book composed of records,
934separated by blank lines, of the form
935</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
936<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
937<span style="font-size: 9pt"><tt>Herbert Tic</tt></span></p>
938<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
939<span style="font-size: 9pt"><tt>44 Turnip Ave., Endive, NJ</tt></span></p>
940<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
941<span style="font-size: 9pt"><tt>201-5555642</tt></span></p>
942<p style="margin-top: 0; margin-bottom: 0.15in"></p>
943
944<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
945<span style="font-size: 9pt"><tt>Norbert Twinge</tt></span></p>
946<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
947<span style="font-size: 9pt"><tt>16 Potato St., Cabbagetown, NJ</tt></span></p>
948<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
949<span style="font-size: 9pt"><tt>201-5553145</tt></span></p>
950<p style="margin-top: 0; margin-bottom: 0.15in"></p>
951
952<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
953<span style="font-size: 9pt"><tt>...</tt></span></p>
954<p style="margin-top: 0; margin-bottom: 0.17in"></p>
955
956<p style="margin-top: 0; margin-bottom: 0.08in"></p>
957<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
958<span style="font-size: 10pt">The format may be encoded as a regular expression:
959</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
960<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
961<span style="font-size: 9pt"><tt>(.+\n)+</tt></span></p>
962<p style="margin-top: 0; margin-bottom: 0.17in"></p>
963
964<p style="margin-top: 0; margin-bottom: 0.08in"></p>
965<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
966<span style="font-size: 10pt">that is, a sequence of one or more non-blank lines.
967The command to print Mr. Tic&rsquo;s entire record is then
968</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
969<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
970<span style="font-size: 9pt"><tt>, x/(.+\n)+/ g/^Herbert Tic$/ p</tt></span></p>
971<p style="margin-top: 0; margin-bottom: 0.17in"></p>
972
973<p style="margin-top: 0; margin-bottom: 0.08in"></p>
974<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
975<span style="font-size: 10pt">and that to extract just the phone number is
976</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
977<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
978<span style="font-size: 9pt"><tt>, x/(.+\n)+/ g/^Herbert Tic$/ x/^[0-9]*-[0-9]*\n/ p</tt></span></p>
979<p style="margin-top: 0; margin-bottom: 0.17in"></p>
980
981<p style="margin-top: 0; margin-bottom: 0.08in"></p>
982<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
983<span style="font-size: 10pt">The latter command breaks the file into records,
984chooses Mr. Tic&rsquo;s record,
985extracts the phone number from the record,
986and finally prints the number.
987</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
988<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
989<span style="font-size: 10pt">A more involved problem is that of
990renaming a particular variable, say
991</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">,
992to
993</span><span style="font-size: 10pt"><tt>num</tt></span><span style="font-size: 10pt">
994in a C program.
995The obvious first attempt,
996</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
997<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
998<span style="font-size: 9pt"><tt>, x/n/ c/num/</tt></span></p>
999<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1000
1001<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1002<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1003<span style="font-size: 10pt">is badly flawed: it changes not only the variable
1004</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">
1005but any letter
1006</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">
1007that appears.
1008We need to extract all the variables, and select those that match
1009</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">
1010and only
1011</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">:
1012</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1013<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1014<span style="font-size: 9pt"><tt>, x/[A-Za-z_][A-Za-z_0-9]*/ g/n/ v/../ c/num/</tt></span></p>
1015<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1016
1017<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1018<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1019<span style="font-size: 10pt">The pattern
1020</span><span style="font-size: 10pt"><tt>[A-Za-z_][A-Za-z_0-9]*</tt></span><span style="font-size: 10pt">
1021matches C identifiers.
1022Next
1023</span><span style="font-size: 10pt"><tt>g/n/</tt></span><span style="font-size: 10pt">
1024selects those containing an
1025</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">.
1026Then
1027</span><span style="font-size: 10pt"><tt>v/../</tt></span><span style="font-size: 10pt">
1028rejects those containing two (or more) characters, and finally
1029</span><span style="font-size: 10pt"><tt>c/num/</tt></span><span style="font-size: 10pt">
1030changes the remainder (identifiers
1031</span><span style="font-size: 10pt"><tt>n</tt></span><span style="font-size: 10pt">)
1032to
1033</span><span style="font-size: 10pt"><tt>num</tt></span><span style="font-size: 10pt">.
1034This version clearly works much better, but there may still be problems.
1035For example, in C character and string constants, the sequence
1036</span><span style="font-size: 10pt"><tt>\n</tt></span><span style="font-size: 10pt">
1037is interpreted as a newline character, and we don&rsquo;t want to change it to
1038</span><span style="font-size: 10pt"><tt>\num.</tt></span><span style="font-size: 10pt">
1039This problem can be forestalled with a
1040</span><span style="font-size: 10pt"><tt>y</tt></span><span style="font-size: 10pt">
1041command:
1042</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1043<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1044<span style="font-size: 9pt"><tt>, y/\\n/ x/[A-Za-z_][A-Za-z_0-9]*/ g/n/ v/../ c/num/</tt></span></p>
1045<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1046
1047<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1048<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1049<span style="font-size: 10pt">(the second
1050</span><span style="font-size: 10pt"><tt>\</tt></span><span style="font-size: 10pt">
1051is necessary because of lexical conventions in regular expressions),
1052or we could even reject character constants and strings outright:
1053</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1054<p style="line-height: 1.1em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1055<span style="font-size: 9pt"><tt>,y/&rsquo;[^&rsquo;]*&rsquo;/ y/"[^"]*"/ x/[A-Za-z_][A-Za-z_0-9]*/ g/n/ v/../ c/num/</tt></span></p>
1056<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1057
1058<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1059<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1060<span style="font-size: 10pt">The
1061</span><span style="font-size: 10pt"><tt>y</tt></span><span style="font-size: 10pt">
1062commands in this version exclude from consideration all character constants
1063and strings.
1064The only remaining problem is to deal with the possible occurrence of
1065</span><span style="font-size: 10pt"><tt>\&rsquo;</tt></span><span style="font-size: 10pt">
1066or
1067</span><span style="font-size: 10pt"><tt>\"</tt></span><span style="font-size: 10pt">
1068within these sequences, but it&rsquo;s easy to see how to resolve this difficulty.
1069</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1070<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1071<span style="font-size: 10pt">The point of these composed commands is successive refinement.
1072A simple version of the command is tried, and if it&rsquo;s not good enough,
1073it can be honed by adding a clause or two.
1074(Mistakes can be undone; see below.
1075Also, the mouse language makes it unnecessary to retype the command each time.)
1076The resulting chains of commands are somewhat reminiscent of
1077shell pipelines.<sup></sup></span><sup><span style="font-size: 6pt">7</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1078Unlike pipelines, though, which pass along modified
1079</span><span style="font-size: 10pt"><i>data</i></span><span style="font-size: 10pt">,
1080</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1081commands pass a
1082</span><span style="font-size: 10pt"><i>view</i></span><span style="font-size: 10pt">
1083of the data.
1084The text at each step of the command is the same, but which pieces
1085are selected is refined step by step until the correct piece is
1086available to the final step of the command line, which ultimately makes the change.
1087</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1088<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1089<span style="font-size: 10pt">In other UNIX programs, regular expressions are used only for selection,
1090as in the
1091</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1092</span><span style="font-size: 10pt"><tt>g</tt></span><span style="font-size: 10pt">
1093command, never for extraction as in the
1094</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
1095or
1096</span><span style="font-size: 10pt"><tt>y</tt></span><span style="font-size: 10pt">
1097command.
1098For example, patterns in
1099</span><span style="font-size: 10pt"><tt>awk</tt></span><span style="font-size: 10pt"><sup></sup></span><sup><span style="font-size: 6pt">7</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1100are used to select lines to be operated on, but cannot be used
1101to describe the format of the input text, or to handle newline-free text.
1102The use of regular expressions to describe the structure of a piece
1103of text rather than its contents, as in the
1104</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
1105command,
1106has been given a name:
1107</span><span style="font-size: 10pt"><i>structural regular expressions.
1108</i></span><span style="font-size: 10pt">When they are composed, as in the above example,
1109they are pleasantly expressive.
1110Their use is discussed at greater length elsewhere.<sup></sup></span><sup><span style="font-size: 6pt">10</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1111</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1112<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1113<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1114<span style="font-size: 10pt"><b>Multiple files
1115</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1116<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1117<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
1118has a few other commands, mostly relating to input and output.
1119</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1120<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1121<span style="font-size: 9pt"><tt>e discfilename</tt></span></p>
1122<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1123
1124<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1125<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1126<span style="font-size: 10pt">replaces the contents and name of the current file with those of the named
1127disc file;
1128</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1129<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1130<span style="font-size: 9pt"><tt>w discfilename</tt></span></p>
1131<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1132
1133<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1134<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1135<span style="font-size: 10pt">writes the contents to the named disc file; and
1136</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1137<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1138<span style="font-size: 9pt"><tt>r discfilename</tt></span></p>
1139<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1140
1141<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1142<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1143<span style="font-size: 10pt">replaces dot with the contents of the named disc file.
1144All these commands use the current file&rsquo;s name if none is specified.
1145Finally,
1146</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1147<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1148<span style="font-size: 9pt"><tt>f discfilename</tt></span></p>
1149<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1150
1151<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1152<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1153<span style="font-size: 10pt">changes the name associated with the file and displays the result:
1154</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1155<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1156<span style="font-size: 9pt"><tt>&rsquo;-. discfilename</tt></span></p>
1157<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1158
1159<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1160<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1161<span style="font-size: 10pt">This output is called the file&rsquo;s
1162</span><span style="font-size: 10pt"><i>menu line,
1163</i></span><span style="font-size: 10pt">because it is the contents of the file&rsquo;s line in the button 3 menu (described
1164in the
1165next section).
1166The first three characters are a concise notation for the state of the file.
1167The apostrophe signifies that the file is modified.
1168The minus sign indicates the number of windows
1169open on the file (see the next section):
1170</span><span style="font-size: 10pt"><tt>-</tt></span><span style="font-size: 10pt">
1171means none,
1172</span><span style="font-size: 10pt"><tt>+</tt></span><span style="font-size: 10pt">
1173means one, and
1174</span><span style="font-size: 10pt"><tt>*</tt></span><span style="font-size: 10pt">
1175means more than one.
1176Finally, the period indicates that this is the current file.
1177These characters are useful for controlling the
1178</span><span style="font-size: 10pt"><tt>X</tt></span><span style="font-size: 10pt">
1179command, described shortly.
1180</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1181<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1182<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
1183may be started with a set of disc files (such as all the source for
1184a program) by invoking it with a list of file names as arguments, and
1185more may be added or deleted on demand.
1186</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1187<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1188<span style="font-size: 9pt"><tt>B discfile1 discfile2 ...</tt></span></p>
1189<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1190
1191<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1192<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1193<span style="font-size: 10pt">adds the named files to
1194</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
1195list, and
1196</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1197<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1198<span style="font-size: 9pt"><tt>D discfile1 discfile2 ...</tt></span></p>
1199<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1200
1201<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1202<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1203<span style="font-size: 10pt">removes them from
1204</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
1205memory (without effect on associated disc files).
1206Both these commands have a syntax for using the shell<sup></sup></span><sup><span style="font-size: 6pt">7</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1207(the UNIX command interpreter) to generate the lists:
1208</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1209<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1210<span style="font-size: 9pt"><tt>B &lt;echo *.c</tt></span></p>
1211<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1212
1213<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1214<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1215<span style="font-size: 10pt">will add all C source files, and
1216</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1217<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1218<span style="font-size: 9pt"><tt>B &lt;grep -l variable *.c</tt></span></p>
1219<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1220
1221<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1222<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1223<span style="font-size: 10pt">will add all C source files referencing a particular variable
1224(the UNIX command
1225</span><span style="font-size: 10pt"><tt>grep\fP-l
1226lists all files in its arguments that contain matches of
1227the specified regular expression).
1228Finally,
1229</tt></span><span style="font-size: 10pt"><tt>D</tt></span><span style="font-size: 10pt"><tt>
1230without arguments deletes the current file.
1231</tt></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1232<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1233<span style="font-size: 10pt">There are two ways to change which file is current:
1234</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1235<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1236<span style="font-size: 9pt"><tt>b filename</tt></span></p>
1237<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1238
1239<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1240<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1241<span style="font-size: 10pt">makes the named file current.
1242The
1243</span><span style="font-size: 10pt"><tt>B</tt></span><span style="font-size: 10pt">
1244command
1245does the same, but also adds any new files to
1246</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
1247list.
1248(In practice, of course, the current file
1249is usually chosen by mouse actions, not by textual commands.)
1250The other way is to use a form of address that refers to files:
1251</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1252<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1253<span style="font-size: 9pt"><tt>"</tt></span><span style="font-size: 9pt"><i>expression</i></span><span style="font-size: 9pt"><tt>" </tt></span><span style="font-size: 9pt"><i>address</i></span><span style="font-size: 9pt"><tt></tt></span></p>
1254<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1255
1256<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1257<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1258<span style="font-size: 10pt">refers to the address evaluated in the file whose menu line
1259matches the expression (there must be exactly one match).
1260For example,
1261</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1262<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1263<span style="font-size: 9pt"><tt>"peter.c" 3</tt></span></p>
1264<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1265
1266<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1267<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1268<span style="font-size: 10pt">refers to the third line of the file whose name matches
1269</span><span style="font-size: 10pt"><tt>peter.c</tt></span><span style="font-size: 10pt">.
1270This is most useful in the move
1271(</span><span style="font-size: 10pt"><tt>m</tt></span><span style="font-size: 10pt">)
1272and copy
1273(</span><span style="font-size: 10pt"><tt>t</tt></span><span style="font-size: 10pt">)
1274commands:
1275</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1276<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1277<span style="font-size: 9pt"><tt>0,$ t "peter.c" 0</tt></span></p>
1278<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1279
1280<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1281<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1282<span style="font-size: 10pt">makes a copy of the current file at the beginning of
1283</span><span style="font-size: 10pt"><tt>peter.c</tt></span><span style="font-size: 10pt">.
1284</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1285<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1286<span style="font-size: 10pt">The
1287</span><span style="font-size: 10pt"><tt>X</tt></span><span style="font-size: 10pt">
1288command
1289is a looping construct, like
1290</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">,
1291that refers to files instead of strings:
1292</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1293<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1294<span style="font-size: 9pt"><tt>X/</tt></span><span style="font-size: 9pt"><i>expression</i></span><span style="font-size: 9pt"><tt>/ </tt></span><span style="font-size: 9pt"><i>command</i></span><span style="font-size: 9pt"><tt></tt></span></p>
1295<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1296
1297<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1298<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1299<span style="font-size: 10pt">runs the command in all
1300files whose menu lines match the expression.  The best example is
1301</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1302<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1303<span style="font-size: 9pt"><tt>X/&rsquo;/ w</tt></span></p>
1304<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1305
1306<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1307<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1308<span style="font-size: 10pt">which writes to disc all modified files.
1309</span><span style="font-size: 10pt"><tt>Y</tt></span><span style="font-size: 10pt">
1310is the complement of
1311</span><span style="font-size: 10pt"><tt>X</tt></span><span style="font-size: 10pt">:
1312it runs the command on all files whose menu lines don&rsquo;t match the expression:
1313</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1314<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1315<span style="font-size: 9pt"><tt>Y/\.c/ D</tt></span></p>
1316<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1317
1318<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1319<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1320<span style="font-size: 10pt">deletes all files that don&rsquo;t have
1321</span><span style="font-size: 10pt"><tt>.c</tt></span><span style="font-size: 10pt">
1322in their names, that is, it keeps all C source files and deletes the rest.
1323</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1324<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1325<span style="font-size: 10pt">Braces allow commands to be grouped, so
1326</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1327<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1328<span style="font-size: 9pt"><tt>{</tt></span></p>
1329<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1330<span style="font-size: 9pt"><tt>    </tt></span><span style="font-size: 9pt"><i>command1</i></span><span style="font-size: 9pt"><tt></tt></span></p>
1331<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1332<span style="font-size: 9pt"><tt>    </tt></span><span style="font-size: 9pt"><i>command2</i></span><span style="font-size: 9pt"><tt></tt></span></p>
1333<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1334<span style="font-size: 9pt"><tt>}</tt></span></p>
1335<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1336
1337<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1338<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1339<span style="font-size: 10pt">is syntactically a single command that runs two commands.
1340Thus,
1341</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1342<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1343<span style="font-size: 9pt"><tt>X/\.c/ ,g/variable/ {</tt></span></p>
1344<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1345<span style="font-size: 9pt"><tt>    f</tt></span></p>
1346<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1347<span style="font-size: 9pt"><tt>    , x/.*\n/ g/variable/ p</tt></span></p>
1348<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1349<span style="font-size: 9pt"><tt>}</tt></span></p>
1350<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1351
1352<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1353<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1354<span style="font-size: 10pt">finds all occurrences of
1355</span><span style="font-size: 10pt"><tt>variable</tt></span><span style="font-size: 10pt">
1356in C source files, and prints
1357out the file names and lines of each match.
1358The precise semantics of compound operations is discussed in the implementation
1359sections below.
1360</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1361<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1362<span style="font-size: 10pt">Finally,
1363the undo command,
1364</span><span style="font-size: 10pt"><tt>u</tt></span><span style="font-size: 10pt">,
1365undoes the last command,
1366no matter how many files were affected.
1367Multiple undo operations move further back in time, so
1368</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1369<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1370<span style="font-size: 9pt"><tt>u</tt></span></p>
1371<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1372<span style="font-size: 9pt"><tt>u</tt></span></p>
1373<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1374
1375<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1376<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1377<span style="font-size: 10pt">(which may be abbreviated
1378</span><span style="font-size: 10pt"><tt>u2</tt></span><span style="font-size: 10pt">)
1379undoes the last two commands.  An undo may not be undone, however, nor
1380may any command that adds or deletes files.
1381Everything else is undoable, though, including for example
1382</span><span style="font-size: 10pt"><tt>e</tt></span><span style="font-size: 10pt">
1383commands:
1384</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1385<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1386<span style="font-size: 9pt"><tt>e filename</tt></span></p>
1387<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1388<span style="font-size: 9pt"><tt>u</tt></span></p>
1389<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1390
1391<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1392<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1393<span style="font-size: 10pt">restores the state of the file completely, including its name, dot,
1394and modified bit.  Because of the undo, potentially dangerous commands
1395are not guarded by confirmations.  Only
1396</span><span style="font-size: 10pt"><tt>D</tt></span><span style="font-size: 10pt">,
1397which destroys the information necessary to restore itself, is protected.
1398It will not delete a modified file, but a second
1399</span><span style="font-size: 10pt"><tt>D</tt></span><span style="font-size: 10pt">
1400of the same file will succeed regardless.
1401The
1402</span><span style="font-size: 10pt"><tt>q</tt></span><span style="font-size: 10pt">
1403command, which exits
1404</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">,
1405is similarly guarded.
1406</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1407<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1408<span style="font-size: 10pt"><b>Mouse Interface
1409</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1410<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1411<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
1412is most commonly run
1413connected to a bitmap display and mouse for interactive editing.
1414The only difference in the command language
1415between regular, mouse-driven
1416</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1417and
1418</span><span style="font-size: 10pt"><tt>sam\fP-d
1419is that if an address
1420is provided without a command,
1421</tt></span><span style="font-size: 10pt"><tt>sam\fP-d
1422will print the text referenced by the address, but
1423regular
1424</tt></span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt"><tt>
1425will highlight it on the screen &mdash; in fact,
1426dot is always highlighted (see Figure 2).
1427</tt></span><span style="font-size: 10pt"></span></p><center><img src="fig3.gif" /></center>
1428<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1429<span style="font-size: 8pt"><i>Figure 2. A
1430</i></span><span style="font-size: 8pt"><tt>sam</tt></span><span style="font-size: 8pt"><i>
1431window.  The scroll bar down the left
1432represents the file, with the bubble showing the fraction
1433visible in the window.
1434The scroll bar may be manipulated by the mouse for convenient browsing.
1435The current text,
1436which is highlighted, need not fit on a line.  Here it consists of one partial
1437line, one complete line, and final partial line.
1438</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1439<p style="margin-top: 0; margin-bottom: 0.02in"></p>
1440
1441<p style="margin-top: 0; margin-bottom: 0.05in"></p>
1442<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1443<span style="font-size: 10pt">Each file may have zero or more windows open on the display.
1444At any time, only one window in all of
1445</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1446is the
1447</span><span style="font-size: 10pt"><i>current window,
1448</i></span><span style="font-size: 10pt">that is, the window to which typing and mouse actions refer;
1449this may be the
1450</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1451window (that in which commands may be typed)
1452or one of the file windows.
1453When a file has multiple windows, the image of the file in each window
1454is always kept up to date.
1455The current file is the last file affected by a command,
1456so if the
1457</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1458window is current,
1459the current window is not a window on the current file.
1460However, each window on a file has its own value of dot,
1461and when switching between windows on a single file,
1462the file&rsquo;s value of dot is changed to that of the window.
1463Thus, flipping between windows behaves in the obvious, convenient way.
1464</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1465<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1466<span style="font-size: 10pt">The mouse on the Blit has three buttons, numbered left to right.
1467Button 3 has a list of commands to manipulate windows,
1468followed by a list of &lsquo;menu lines&rsquo; exactly as printed by the
1469</span><span style="font-size: 10pt"><tt>f</tt></span><span style="font-size: 10pt">
1470command, one per file (not one per window).
1471These menu lines are sorted by file name.
1472If the list is long, the Blit menu software will make it more manageable
1473by generating a scrolling menu instead of an unwieldy long list.
1474Using the menu to select a file from the list makes that file the current
1475file, and the most recently current window in that file the current window.
1476But if that file is already current, selecting it in the menu cycles through
1477the windows on the file; this simple trick avoids a special menu to
1478choose windows on a file.
1479If there is no window open on the file,
1480</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1481changes the mouse cursor to prompt the user to create one.
1482</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1483<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1484<span style="font-size: 10pt">The commands on the button 3 menu are straightforward (see Figure 3), and
1485are like the commands to manipulate windows in
1486</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">8</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1487the Blit&rsquo;s window system.
1488</span><span style="font-size: 10pt"><tt>New</tt></span><span style="font-size: 10pt">
1489makes a new file, and gives it one empty window, whose size is determined
1490by a rectangle swept by the mouse.
1491</span><span style="font-size: 10pt"><tt>Zerox</tt></span><span style="font-size: 10pt">
1492prompts for a window to be selected, and
1493makes a clone of that window; this is how multiple windows are created on one file.
1494</span><span style="font-size: 10pt"><tt>Reshape</tt></span><span style="font-size: 10pt">
1495changes the size of the indicated window, and
1496</span><span style="font-size: 10pt"><tt>close</tt></span><span style="font-size: 10pt">
1497deletes it.  If that is the last window open on the file,
1498</span><span style="font-size: 10pt"><tt>close</tt></span><span style="font-size: 10pt">
1499first does a
1500</span><span style="font-size: 10pt"><tt>D</tt></span><span style="font-size: 10pt">
1501command on the file.
1502</span><span style="font-size: 10pt"><tt>Write</tt></span><span style="font-size: 10pt">
1503is identical to a
1504</span><span style="font-size: 10pt"><tt>w</tt></span><span style="font-size: 10pt">
1505command on the file; it is in the menu purely for convenience.
1506Finally,
1507</span><span style="font-size: 10pt"><tt>~~sam~~</tt></span><span style="font-size: 10pt">
1508is a menu item that appears between the commands and the file names.
1509Selecting it makes the
1510</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1511window the current window,
1512causing subsequent typing to be interpreted as commands.
1513</span><span style="font-size: 10pt"></span></p><center><img src="fig2.gif" /></center>
1514<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1515<span style="font-size: 8pt"><i>Figure 3. The menu on button 3.
1516The black rectangle on the left is a scroll bar; the menu is limited to
1517the length shown to prevent its becoming unwieldy.
1518Above the
1519</i></span><span style="font-size: 8pt"><tt>~~sam~~</tt></span><span style="font-size: 8pt"><i>
1520line is a list of commands;
1521beneath it is a list of files, presented exactly as with the
1522</i></span><span style="font-size: 8pt"><tt>f</tt></span><span style="font-size: 8pt"><i>
1523command.
1524</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1525<p style="margin-top: 0; margin-bottom: 0.02in"></p>
1526
1527<p style="margin-top: 0; margin-bottom: 0.05in"></p>
1528<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1529<span style="font-size: 10pt">When
1530</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1531requests that a window be swept, in response to
1532</span><span style="font-size: 10pt"><tt>new</tt></span><span style="font-size: 10pt">,
1533</span><span style="font-size: 10pt"><tt>zerox</tt></span><span style="font-size: 10pt">
1534or
1535</span><span style="font-size: 10pt"><tt>reshape</tt></span><span style="font-size: 10pt">,
1536it changes the mouse cursor from the usual arrow to a box with
1537a small arrow.
1538In this state, the mouse may be used to indicate an arbitrary rectangle by
1539pressing button 3 at one corner and releasing it at the opposite corner.
1540More conveniently,
1541button 3 may simply be clicked,
1542whereupon
1543</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1544creates the maximal rectangle that contains the cursor
1545and abuts the
1546</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1547window.
1548By placing the
1549</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1550window in the middle of the screen, the user can define two regions (one above,
1551one below) in which stacked fully-overlapping
1552windows can be created with minimal fuss (see Figure 1).
1553This simple user interface trick makes window creation noticeably easier.
1554</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1555<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1556<span style="font-size: 10pt">The cut-and-paste editor is essentially the same as that in Smalltalk-80.<sup></sup></span><sup><span style="font-size: 6pt">11</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1557The text in dot is always highlighted on the screen.
1558When a character is typed it replaces dot, and sets dot to the null
1559string after the character.  Thus, ordinary typing inserts text.
1560Button 1 is used for selection:
1561pressing the button, moving the mouse, and lifting the button
1562selects (sets dot to) the text between the points where the
1563button was pressed and released.
1564Pressing and releasing at the same point selects a null string; this
1565is called clicking.  Clicking twice quickly, or
1566</span><span style="font-size: 10pt"><i>double clicking,
1567</i></span><span style="font-size: 10pt">selects larger objects;
1568for example, double clicking in a word selects the word,
1569double clicking just inside an opening bracket selects the text
1570contained in the brackets (handling nested brackets correctly),
1571and similarly for
1572parentheses, quotes, and so on.
1573The double-clicking rules reflect a bias toward
1574programmers.
1575If
1576</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1577were intended more for word processing, double-clicks would probably
1578select linguistic structures such as sentences.
1579</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1580<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1581<span style="font-size: 10pt">If button 1 is pressed outside the current window, it makes the indicated
1582window current.
1583This is the easiest way to switch between windows and files.
1584</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1585<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1586<span style="font-size: 10pt">Pressing button 2 brings up a menu of editing functions (see Figure 4).
1587These mostly apply to the selected text:
1588</span><span style="font-size: 10pt"><tt>cut</tt></span><span style="font-size: 10pt">
1589deletes the selected text, and remembers it in a hidden buffer called the
1590</span><span style="font-size: 10pt"><i>snarf buffer,
1591</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>paste</tt></span><span style="font-size: 10pt">
1592replaces the selected text by the contents of the snarf buffer,
1593</span><span style="font-size: 10pt"><tt>snarf</tt></span><span style="font-size: 10pt">
1594just copies the selected text to the snarf buffer,
1595</span><span style="font-size: 10pt"><tt>look</tt></span><span style="font-size: 10pt">
1596searches forward for the next literal occurrence of the selected text, and
1597</span><span style="font-size: 10pt"><tt>&lt;mux&gt;</tt></span><span style="font-size: 10pt">
1598exchanges snarf buffers with the window system in which
1599</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1600is running.
1601Finally, the last regular expression used appears as a menu entry
1602to search
1603forward for the next occurrence of a match for the expression.
1604</span><span style="font-size: 10pt"></span></p><center><img src="fig4.gif" /></center>
1605<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1606<span style="font-size: 8pt"><i>Figure 4. The menu on button 2.
1607The bottom entry tracks the most recently used regular expression, which may
1608be literal text.
1609</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1610<p style="margin-top: 0; margin-bottom: 0.02in"></p>
1611
1612<p style="margin-top: 0; margin-bottom: 0.05in"></p>
1613<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1614<span style="font-size: 10pt">The relationship between the command language and the mouse language is
1615entirely due to the equality of dot and the selected text chosen
1616with button 1 on the mouse.
1617For example, to make a set of changes in a C subroutine, dot can be
1618set by double clicking on the left brace that begins the subroutine,
1619which sets dot for the command language.
1620An address-free command then typed in the
1621</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1622window will apply only to the text between the opening and closing
1623braces of the function.
1624The idea is to select what you want, and then say what you want
1625to do with it, whether invoked by a menu selection or by a typed command.
1626And of course, the value of dot is highlighted on
1627the display after the command completes.
1628This relationship between mouse interface and command language
1629is clumsy to explain, but comfortable, even natural, in practice.
1630</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1631<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1632<span style="font-size: 10pt"><b>The Implementation
1633</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1634<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1635<span style="font-size: 10pt">The next few sections describe how
1636</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1637is put together, first the host part,
1638then the inter-component communication,
1639then the terminal part.
1640After explaining how the command language is implemented,
1641the discussion follows (roughly) the path of a character
1642from the temporary file on disc to the screen.
1643The presentation centers on the data structures,
1644because that is how the program was designed and because
1645the algorithms are easy to provide, given the right data
1646structures.
1647</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1648<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1649<span style="font-size: 10pt"><b>Parsing and execution
1650</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1651<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1652<span style="font-size: 10pt">The command language is interpreted by parsing each command with a
1653table-driven recursive
1654descent parser, and when a complete command is assembled, invoking a top-down
1655executor.
1656Most editors instead employ a simple character-at-a-time
1657lexical scanner.
1658Use of a parser makes it
1659easy and unambiguous to detect when a command is complete,
1660which has two advantages.
1661First, escape conventions such as backslashes to quote
1662multiple-line commands are unnecessary;  if the command isn&rsquo;t finished,
1663the parser keeps reading.  For example, a multiple-line append driven by an
1664</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
1665command is straightforward:
1666</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1667<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1668<span style="font-size: 9pt"><tt>x/.*\n/ g/Peter/ a</tt></span></p>
1669<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1670<span style="font-size: 9pt"><tt>one line about Peter</tt></span></p>
1671<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1672<span style="font-size: 9pt"><tt>another line about Peter</tt></span></p>
1673<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1674<span style="font-size: 9pt"><tt>.</tt></span></p>
1675<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1676
1677<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1678<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1679<span style="font-size: 10pt">Other UNIX editors would require a backslash after all but the last line.
1680</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1681<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1682<span style="font-size: 10pt">The other advantage is specific to the two-process structure of
1683</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">.
1684The host process must decide when a command is completed so the
1685command interpreter can be called.  This problem is easily resolved
1686by having the lexical analyzer read the single stream of events from the
1687terminal, directly executing all typing and mouse commands,
1688but passing to the parser characters typed to the
1689</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1690command window.
1691This scheme is slightly complicated by the availability of cut-and-paste
1692editing in the
1693</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1694window, but that difficulty is resolved by applying the rules
1695used in
1696</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">:
1697when a newline is typed to the
1698</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1699window, all text between the newline and the previously typed newline
1700is made available to the parser.
1701This permits arbitrary editing to be done to a command before
1702typing newline and thereby requesting execution.
1703</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1704<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1705<span style="font-size: 10pt">The parser is driven by a table because the syntax of addresses
1706and commands is regular enough
1707to be encoded compactly.  There are few special cases, such as the
1708replacement text in a substitution, so the syntax of almost all commands
1709can be encoded with a few flags.
1710These include whether the command allows an address (for example,
1711</span><span style="font-size: 10pt"><tt>e</tt></span><span style="font-size: 10pt">
1712does not), whether it takes a regular expression (as in
1713</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
1714and
1715</span><span style="font-size: 10pt"><tt>s</tt></span><span style="font-size: 10pt">),
1716whether it takes replacement text (as in
1717</span><span style="font-size: 10pt"><tt>c</tt></span><span style="font-size: 10pt">
1718or
1719</span><span style="font-size: 10pt"><tt>i</tt></span><span style="font-size: 10pt">),
1720which may be multi-line, and so on.
1721The internal syntax of regular expressions is handled by a separate
1722parser; a regular expression is a leaf of the command parse tree.
1723Regular expressions are discussed fully in the next section.
1724</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1725<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1726<span style="font-size: 10pt">The parser table also has information about defaults, so the interpreter
1727is always called with a complete tree.  For example, the parser fills in
1728the implicit
1729</span><span style="font-size: 10pt"><tt>0</tt></span><span style="font-size: 10pt">
1730and
1731</span><span style="font-size: 10pt"><tt>$</tt></span><span style="font-size: 10pt">
1732in the abbreviated address
1733</span><span style="font-size: 10pt"><tt>,</tt></span><span style="font-size: 10pt">
1734(comma),
1735inserts a
1736</span><span style="font-size: 10pt"><tt>+</tt></span><span style="font-size: 10pt">
1737to the left of an unadorned regular expression in an address,
1738and provides the usual default address
1739</span><span style="font-size: 10pt"><tt>.</tt></span><span style="font-size: 10pt">
1740(dot) for commands that expect an address but are not given one.
1741</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1742<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1743<span style="font-size: 10pt">Once a complete command is parsed, the evaluation is easy.
1744The address is evaluated left-to-right starting from the value of dot,
1745with a mostly ordinary expression evaluator.
1746Addresses, like many of the data structures in
1747</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">,
1748are held in a C structure and passed around by value:
1749</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1750<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1751<span style="font-size: 9pt"><tt>typedef long Posn;    /* Position in a file */</tt></span></p>
1752<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1753<span style="font-size: 9pt"><tt>typedef struct Range{</tt></span></p>
1754<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1755<span style="font-size: 9pt"><tt>        Posn    p1, p2;</tt></span></p>
1756<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1757<span style="font-size: 9pt"><tt>}Range;</tt></span></p>
1758<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1759<span style="font-size: 9pt"><tt>typedef struct Address{</tt></span></p>
1760<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1761<span style="font-size: 9pt"><tt>        Range   r;</tt></span></p>
1762<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1763<span style="font-size: 9pt"><tt>        File    *f;</tt></span></p>
1764<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1765<span style="font-size: 9pt"><tt>}Address;</tt></span></p>
1766<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1767
1768<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1769<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1770<span style="font-size: 10pt">An address is encoded as a substring (character positions
1771</span><span style="font-size: 10pt"><tt>p1</tt></span><span style="font-size: 10pt">
1772to
1773</span><span style="font-size: 10pt"><tt>p2</tt></span><span style="font-size: 10pt">)
1774in a file
1775</span><span style="font-size: 10pt"><tt>f</tt></span><span style="font-size: 10pt">.
1776(The data type
1777</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
1778is described in detail below.)
1779</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1780<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1781<span style="font-size: 10pt">The address interpreter is an
1782</span><span style="font-size: 10pt"><tt>Address</tt></span><span style="font-size: 10pt">-valued
1783function that traverses the parse tree describing an address (the
1784parse tree for the address has type
1785</span><span style="font-size: 10pt"><tt>Addrtree</tt></span><span style="font-size: 10pt">):
1786</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1787<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1788<span style="font-size: 9pt"><tt>Address</tt></span></p>
1789<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1790<span style="font-size: 9pt"><tt>address(ap, a, sign)</tt></span></p>
1791<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1792<span style="font-size: 9pt"><tt>    Addrtree *ap;</tt></span></p>
1793<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1794<span style="font-size: 9pt"><tt>    Address a;</tt></span></p>
1795<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1796<span style="font-size: 9pt"><tt>    int sign;</tt></span></p>
1797<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1798<span style="font-size: 9pt"><tt>{</tt></span></p>
1799<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1800<span style="font-size: 9pt"><tt>    Address a2;</tt></span></p>
1801<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1802<span style="font-size: 9pt"><tt>    do</tt></span></p>
1803<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1804<span style="font-size: 9pt"><tt>        switch(ap-&gt;type){</tt></span></p>
1805<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1806<span style="font-size: 9pt"><tt>        case &rsquo;.&rsquo;:</tt></span></p>
1807<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1808<span style="font-size: 9pt"><tt>            a=a.f-&gt;dot;</tt></span></p>
1809<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1810<span style="font-size: 9pt"><tt>            break;</tt></span></p>
1811<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1812<span style="font-size: 9pt"><tt>        case &rsquo;$&rsquo;:</tt></span></p>
1813<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1814<span style="font-size: 9pt"><tt>            a.r.p1=a.r.p2=a.f-&gt;nbytes;</tt></span></p>
1815<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1816<span style="font-size: 9pt"><tt>            break;</tt></span></p>
1817<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1818<span style="font-size: 9pt"><tt>        case &rsquo;"&rsquo;:   </tt></span></p>
1819<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1820<span style="font-size: 9pt"><tt>            a=matchfile(a, ap-&gt;aregexp)-&gt;dot; </tt></span></p>
1821<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1822<span style="font-size: 9pt"><tt>            break;</tt></span></p>
1823<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1824<span style="font-size: 9pt"><tt>        case &rsquo;,&rsquo;:</tt></span></p>
1825<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1826<span style="font-size: 9pt"><tt>            a2=address(ap-&gt;right, a, 0);</tt></span></p>
1827<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1828<span style="font-size: 9pt"><tt>            a=address(ap-&gt;left, a, 0);</tt></span></p>
1829<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1830<span style="font-size: 9pt"><tt>            if(a.f!=a2.f || a2.r.p2&lt;a.r.p1)</tt></span></p>
1831<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1832<span style="font-size: 9pt"><tt>                error(Eorder);</tt></span></p>
1833<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1834<span style="font-size: 9pt"><tt>            a.r.p2=a2.r.p2;</tt></span></p>
1835<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1836<span style="font-size: 9pt"><tt>            return a;</tt></span></p>
1837<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1838<span style="font-size: 9pt"><tt>        /* and so on */</tt></span></p>
1839<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1840<span style="font-size: 9pt"><tt>        }</tt></span></p>
1841<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1842<span style="font-size: 9pt"><tt>    while((ap=ap-&gt;right)!=0);</tt></span></p>
1843<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1844<span style="font-size: 9pt"><tt>    return a;</tt></span></p>
1845<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1846<span style="font-size: 9pt"><tt>}</tt></span></p>
1847<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1848
1849<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1850<p style="margin-top: 0; margin-bottom: 0.05in"></p>
1851<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1852<span style="font-size: 10pt">Throughout, errors are handled by a non-local
1853</span><span style="font-size: 10pt"><tt>goto</tt></span><span style="font-size: 10pt">
1854(a
1855</span><span style="font-size: 10pt"><tt>setjmp/longjmp</tt></span><span style="font-size: 10pt">
1856in C terminology)
1857hidden in a routine called
1858</span><span style="font-size: 10pt"><tt>error</tt></span><span style="font-size: 10pt">
1859that immediately aborts the execution, retracts any
1860partially made changes (see the section below on &lsquo;undoing&rsquo;), and
1861returns to the top level of the parser.
1862The argument to
1863</span><span style="font-size: 10pt"><tt>error</tt></span><span style="font-size: 10pt">
1864is an enumeration type that
1865is translated to a terse but possibly helpful
1866message such as &lsquo;?addresses out of order.&rsquo;
1867Very common messages are kept short; for example the message for
1868a failed regular expression search is &lsquo;?search.&rsquo;
1869</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1870<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1871<span style="font-size: 10pt">Character addresses such as
1872</span><span style="font-size: 10pt"><tt>#3</tt></span><span style="font-size: 10pt">
1873are trivial to implement, as the
1874</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
1875data structure is accessible by character number.
1876However,
1877</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1878keeps no information about the position of newlines &mdash; it is too
1879expensive to track dynamically &mdash; so line addresses are computed by reading
1880the file, counting newlines.  Except in very large files, this has proven
1881acceptable: file access is fast enough to make the technique practical,
1882and lines are not central to the structure of the command language.
1883</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1884<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1885<span style="font-size: 10pt">The command interpreter, called
1886</span><span style="font-size: 10pt"><tt>cmdexec</tt></span><span style="font-size: 10pt">,
1887is also straightforward.  The parse table includes a
1888function to call to interpret a particular command.  That function
1889receives as arguments
1890the calculated address
1891for the command
1892and the command tree (of type
1893</span><span style="font-size: 10pt"><tt>Cmdtree</tt></span><span style="font-size: 10pt">),
1894which may contain information such as the subtree for compound commands.
1895Here, for example, is the function for the
1896</span><span style="font-size: 10pt"><tt>g</tt></span><span style="font-size: 10pt">
1897and
1898</span><span style="font-size: 10pt"><tt>v</tt></span><span style="font-size: 10pt">
1899commands:
1900</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1901<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1902<span style="font-size: 9pt"><tt>int</tt></span></p>
1903<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1904<span style="font-size: 9pt"><tt>g_cmd(a, cp)</tt></span></p>
1905<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1906<span style="font-size: 9pt"><tt>    Address a;</tt></span></p>
1907<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1908<span style="font-size: 9pt"><tt>    Cmdtree *cp;</tt></span></p>
1909<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1910<span style="font-size: 9pt"><tt>{</tt></span></p>
1911<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1912<span style="font-size: 9pt"><tt>    compile(cp-&gt;regexp);</tt></span></p>
1913<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1914<span style="font-size: 9pt"><tt>    if(execute(a.f, a.r.p1, a.r.p2)!=(cp-&gt;cmdchar==&rsquo;v&rsquo;)){</tt></span></p>
1915<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1916<span style="font-size: 9pt"><tt>        a.f-&gt;dot=a;</tt></span></p>
1917<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1918<span style="font-size: 9pt"><tt>        return cmdexec(a, cp-&gt;subcmd);</tt></span></p>
1919<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1920<span style="font-size: 9pt"><tt>    }</tt></span></p>
1921<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1922<span style="font-size: 9pt"><tt>    return TRUE;    /* cause execution to continue */</tt></span></p>
1923<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1924<span style="font-size: 9pt"><tt>}</tt></span></p>
1925<p style="margin-top: 0; margin-bottom: 0.17in"></p>
1926
1927<p style="margin-top: 0; margin-bottom: 0.08in"></p>
1928<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1929<span style="font-size: 10pt">(</span><span style="font-size: 10pt"><tt>Compile</tt></span><span style="font-size: 10pt">
1930and
1931</span><span style="font-size: 10pt"><tt>execute</tt></span><span style="font-size: 10pt">
1932are part of the regular expression code, described in the next section.)
1933Because the parser and the
1934</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
1935data structure do most of the work, most commands
1936are similarly brief.
1937</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
1938<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1939<span style="font-size: 10pt"><b>Regular expressions
1940</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1941<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1942<span style="font-size: 10pt">The regular expression code in
1943</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1944is an interpreted, rather than compiled on-the-fly, implementation of Thompson&rsquo;s
1945non-deterministic finite automaton algorithm.<sup></sup></span><sup><span style="font-size: 6pt">12</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1946The syntax and semantics of the expressions are as in the UNIX program
1947</span><span style="font-size: 10pt"><tt>egrep</tt></span><span style="font-size: 10pt">,
1948including alternation, closures, character classes, and so on.
1949The only changes in the notation are two additions:
1950</span><span style="font-size: 10pt"><tt>\n</tt></span><span style="font-size: 10pt">
1951is translated to, and matches, a newline character, and
1952</span><span style="font-size: 10pt"><tt>@</tt></span><span style="font-size: 10pt">
1953matches any character.  In
1954</span><span style="font-size: 10pt"><tt>egrep</tt></span><span style="font-size: 10pt">,
1955the character
1956</span><span style="font-size: 10pt"><tt>.</tt></span><span style="font-size: 10pt">
1957matches any character except newline, and in
1958</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
1959the same rule seemed safest, to prevent idioms like
1960</span><span style="font-size: 10pt"><tt>.*</tt></span><span style="font-size: 10pt">
1961from spanning newlines.
1962</span><span style="font-size: 10pt"><tt>Egrep</tt></span><span style="font-size: 10pt">
1963expressions are arguably too complicated for an interactive editor &mdash;
1964certainly it would make sense if all the special characters were two-character
1965sequences, so that most of the punctuation characters wouldn&rsquo;t have
1966peculiar meanings &mdash; but for an interesting command language, full
1967regular expressions are necessary, and
1968</span><span style="font-size: 10pt"><tt>egrep</tt></span><span style="font-size: 10pt">
1969defines the full regular expression syntax for UNIX programs.
1970Also, it seemed superfluous to define a new syntax, since various UNIX programs
1971(</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">,
1972</span><span style="font-size: 10pt"><tt>egrep</tt></span><span style="font-size: 10pt">
1973and
1974</span><span style="font-size: 10pt"><tt>vi</tt></span><span style="font-size: 10pt">)
1975define too many already.
1976</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1977<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1978<span style="font-size: 10pt">The expressions are compiled by a routine,
1979</span><span style="font-size: 10pt"><tt>compile</tt></span><span style="font-size: 10pt">,
1980that generates the description of the non-deterministic finite state machine.
1981A second routine,
1982</span><span style="font-size: 10pt"><tt>execute</tt></span><span style="font-size: 10pt">,
1983interprets the machine to generate the leftmost-longest match of the
1984expression in a substring of the file.
1985The algorithm is described elsewhere.<sup></sup></span><sup><span style="font-size: 6pt">12,13</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
1986</span><span style="font-size: 10pt"><tt>Execute</tt></span><span style="font-size: 10pt">
1987reports
1988whether a match was found, and sets a global variable,
1989of type
1990</span><span style="font-size: 10pt"><tt>Range</tt></span><span style="font-size: 10pt">,
1991to the substring matched.
1992</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
1993<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1994<span style="font-size: 10pt">A trick is required to evaluate the expression in reverse, such as when
1995searching backwards for an expression.
1996For example,
1997</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
1998<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
1999<span style="font-size: 9pt"><tt>-/P.*r/</tt></span></p>
2000<p style="margin-top: 0; margin-bottom: 0.17in"></p>
2001
2002<p style="margin-top: 0; margin-bottom: 0.08in"></p>
2003<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2004<span style="font-size: 10pt">looks backwards through the file for a match of the expression.
2005The expression, however, is defined for a forward search.
2006The solution is to construct a machine identical to the machine
2007for a forward search except for a reversal of all the concatenation
2008operators (the other operators are symmetric under direction reversal),
2009to exchange the meaning of the operators
2010</span><span style="font-size: 10pt"><tt>^</tt></span><span style="font-size: 10pt">
2011and
2012</span><span style="font-size: 10pt"><tt>$</tt></span><span style="font-size: 10pt">,
2013and then to read the file backwards, looking for the
2014usual earliest longest match.
2015</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2016<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2017<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Execute</tt></span><span style="font-size: 10pt">
2018generates only one match each time it is called.
2019To interpret looping constructs such as the
2020</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
2021command,
2022</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2023must therefore synchronize between
2024calls of
2025</span><span style="font-size: 10pt"><tt>execute</tt></span><span style="font-size: 10pt">
2026to avoid
2027problems with null matches.
2028For example, even given the leftmost-longest rule,
2029the expression
2030</span><span style="font-size: 10pt"><tt>a*</tt></span><span style="font-size: 10pt">
2031matches three times in the string
2032</span><span style="font-size: 10pt"><tt>ab</tt></span><span style="font-size: 10pt">
2033(the character
2034</span><span style="font-size: 10pt"><tt>a</tt></span><span style="font-size: 10pt">,
2035the null string between the
2036</span><span style="font-size: 10pt"><tt>a</tt></span><span style="font-size: 10pt">
2037and
2038</span><span style="font-size: 10pt"><tt>b</tt></span><span style="font-size: 10pt">,
2039and the final null string).
2040After returning a match for the
2041</span><span style="font-size: 10pt"><tt>a</tt></span><span style="font-size: 10pt">,
2042</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2043must not match the null string before the
2044</span><span style="font-size: 10pt"><tt>b</tt></span><span style="font-size: 10pt">.
2045The algorithm starts
2046</span><span style="font-size: 10pt"><tt>execute</tt></span><span style="font-size: 10pt">
2047at the end of its previous match, and
2048if the match it returns
2049is null and abuts the previous match, rejects the match and advances
2050the initial position one character.
2051</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2052<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2053<span style="font-size: 10pt"><b>Memory allocation
2054</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2055<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2056<span style="font-size: 10pt">The C language has no memory allocation primitives, although a standard
2057library routine,
2058</span><span style="font-size: 10pt"><tt>malloc</tt></span><span style="font-size: 10pt">,
2059provides adequate service for simple programs.
2060For specific uses, however,
2061it can be better to write a custom allocator.
2062The allocator (or rather, pair of allocators) described here
2063work in both the terminal and host parts of
2064</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">.
2065They are designed for efficient manipulation of strings,
2066which are allocated and freed frequently and vary in length from essentially
2067zero to 32 Kbytes (very large strings are written to disc).
2068More important, strings may be large and change size often,
2069so to minimize memory usage it is helpful to reclaim and to coalesce the
2070unused portions of strings when they are truncated.
2071</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2072<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2073<span style="font-size: 10pt">Objects to be allocated in
2074</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2075are of two flavors:
2076the first is C
2077</span><span style="font-size: 10pt"><tt>structs</tt></span><span style="font-size: 10pt">,
2078which are small and often addressed by pointer variables;
2079the second is variable-sized arrays of characters
2080or integers whose
2081base pointer is always used to access them.
2082The memory allocator in
2083</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2084is therefore in two parts:
2085first, a traditional first-fit allocator that provides fixed storage for
2086</span><span style="font-size: 10pt"><tt>structs</tt></span><span style="font-size: 10pt">;
2087and second, a garbage-compacting allocator that reduces storage
2088overhead for variable-sized objects, at the cost of some bookkeeping.
2089The two types of objects are allocated from adjoining arenas, with
2090the garbage-compacting allocator controlling the arena with higher addresses.
2091Separating into two arenas simplifies compaction and prevents fragmentation due
2092to immovable objects.
2093The access rules for garbage-compactable objects
2094(discussed in the next paragraph) allow them to be relocated, so when
2095the first-fit arena needs space, it moves the garbage-compacted arena
2096to higher addresses to make room.  Storage is therefore created only
2097at successively higher addresses, either when more garbage-compacted
2098space is needed or when the first-fit arena pushes up the other arena.
2099</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2100<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2101<span style="font-size: 10pt">Objects that may be compacted declare to the
2102allocator a cell that is guaranteed to be the sole repository of the
2103address of the object whenever a compaction can occur.
2104The compactor can then update the address when the object is moved.
2105For example, the implementation of type
2106</span><span style="font-size: 10pt"><tt>List</tt></span><span style="font-size: 10pt">
2107(really a variable-length array)
2108is:
2109</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
2110<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2111<span style="font-size: 9pt"><tt>typedef struct List{</tt></span></p>
2112<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2113<span style="font-size: 9pt"><tt>        int     nused;</tt></span></p>
2114<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2115<span style="font-size: 9pt"><tt>        long    *ptr;</tt></span></p>
2116<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2117<span style="font-size: 9pt"><tt>}List;</tt></span></p>
2118<p style="margin-top: 0; margin-bottom: 0.17in"></p>
2119
2120<p style="margin-top: 0; margin-bottom: 0.08in"></p>
2121<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2122<span style="font-size: 10pt">The
2123</span><span style="font-size: 10pt"><tt>ptr</tt></span><span style="font-size: 10pt">
2124cell must always be used directly, and never copied.  When a
2125</span><span style="font-size: 10pt"><tt>List</tt></span><span style="font-size: 10pt">
2126is to be created the
2127</span><span style="font-size: 10pt"><tt>List</tt></span><span style="font-size: 10pt">
2128structure is allocated in the ordinary first-fit arena
2129and its
2130</span><span style="font-size: 10pt"><tt>ptr</tt></span><span style="font-size: 10pt">
2131is allocated in the garbage-compacted arena.
2132A similar data type for strings, called
2133</span><span style="font-size: 10pt"><tt>String</tt></span><span style="font-size: 10pt">,
2134stores variable-length character arrays of up to 32767 elements.
2135</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2136<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2137<span style="font-size: 10pt">A related matter of programming style:
2138</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2139frequently passes structures by value, which
2140simplifies the code.
2141Traditionally, C programs have
2142passed structures by reference, but implicit allocation on
2143the stack is easier to use.
2144Structure passing is a relatively new feature of C
2145(it is not in the
2146standard reference manual for C<sup></sup></span><sup><span style="font-size: 6pt">14</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">), and is poorly supported in most
2147commercial C compilers.
2148It&rsquo;s convenient and expressive, though,
2149and simplifies memory management by
2150avoiding the allocator altogether
2151and eliminating pointer aliases.
2152</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2153<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2154<span style="font-size: 10pt"><b>Data structures for manipulating files
2155</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2156<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2157<span style="font-size: 10pt">Experience with
2158</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
2159showed that the requirements
2160of the file data structure were few, but strict.
2161First, files need to be read and written quickly;
2162adding a fresh file must be painless.
2163Second, the implementation must place no arbitrary upper limit on
2164the number or sizes of files.  (It should be practical to edit many files,
2165and files up to megabytes in length should be handled gracefully.)
2166This implies that files be stored on disc, not in main memory.
2167(Aficionados of virtual memory may argue otherwise, but the
2168implementation of virtual
2169memory in our system is not something to depend on
2170for good performance.)
2171Third, changes to files need be made by only two primitives:
2172deletion and insertion.
2173These are inverses of each other,
2174which simplifies the implementation of the undo operation.
2175Finally,
2176it must be easy and efficient to access the file, either
2177forwards or backwards, a byte at a time.
2178</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2179<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2180<span style="font-size: 10pt">The
2181</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
2182data type is constructed from three simpler data structures that hold arrays
2183of characters.
2184Each of these types has an insertion and deletion operator, and the
2185insertion and deletion operators of the
2186</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
2187type itself are constructed from them.
2188</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2189<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2190<span style="font-size: 10pt">The simplest type is the
2191</span><span style="font-size: 10pt"><tt>String</tt></span><span style="font-size: 10pt">,
2192which is used to hold strings in main memory.
2193The code that manages
2194</span><span style="font-size: 10pt"><tt>Strings</tt></span><span style="font-size: 10pt">
2195guarantees that they will never be longer
2196than some moderate size, and in practice they are rarely larger than 8 Kbytes.
2197</span><span style="font-size: 10pt"><tt>Strings</tt></span><span style="font-size: 10pt">
2198have two purposes: they hold short strings like file names with little overhead,
2199and because they are deliberately small, they are efficient to modify.
2200They are therefore used as the data structure for in-memory caches.
2201</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2202<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2203<span style="font-size: 10pt">The disc copy of the file is managed by a data structure called a
2204</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">,
2205which corresponds to a temporary file.  A
2206</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2207has no storage in main memory other than bookkeeping information;
2208the actual data being held is all on the disc.
2209To reduce the number of open files needed,
2210</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2211opens a dozen temporary UNIX files and multiplexes the
2212</span><span style="font-size: 10pt"><tt>Discs</tt></span><span style="font-size: 10pt">
2213upon them.
2214This permits many files to
2215be edited; the entire
2216</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2217source (48 files) may be edited comfortably with a single
2218instance of
2219</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">.
2220Allocating one temporary file per
2221</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2222would strain the operating system&rsquo;s limit on the number of open files.
2223Also, spreading the traffic among temporary files keeps the files shorter,
2224and shorter files are more efficiently implemented by the UNIX
2225I/O subsystem.
2226</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2227<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2228<span style="font-size: 10pt">A
2229</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2230is an array of fixed-length blocks, each of which contains
2231between 1 and 4096 characters of active data.
2232(The block size of our UNIX file system is 4096 bytes.)
2233The block addresses within the temporary file and the length of each
2234block are stored in a
2235</span><span style="font-size: 10pt"><tt>List</tt></span><span style="font-size: 10pt">.
2236When changes are made the live part of blocks may change size.
2237Blocks are created and coalesced when necessary to try to keep the sizes
2238between 2048 and 4096 bytes.
2239An actively changing part of the
2240</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2241therefore typically has about a kilobyte of slop that can be
2242inserted or deleted
2243without changing more than one block or affecting the block order.
2244When an insertion would overflow a block, the block is split, a new one
2245is allocated to receive the overflow, and the memory-resident list of blocks
2246is rearranged to reflect the insertion of the new block.
2247</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2248<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2249<span style="font-size: 10pt">Obviously, going to the disc for every modification to the file is
2250prohibitively expensive.
2251The data type
2252</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">
2253consists of a
2254</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2255to hold the data and a
2256</span><span style="font-size: 10pt"><tt>String</tt></span><span style="font-size: 10pt">
2257that acts as a cache.
2258This is the first of a series of caches throughout the data structures in
2259</span><span style="font-size: 10pt"><tt>sam.</tt></span><span style="font-size: 10pt">
2260The caches not only improve performance, they provide a way to organize
2261the flow of data, particularly in the communication between the host
2262and terminal.
2263This idea is developed below, in the section on communications.
2264</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2265<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2266<span style="font-size: 10pt">To reduce disc traffic, changes to a
2267</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">
2268are mediated by a variable-length string, in memory, that acts as a cache.
2269When an insertion or deletion is made to a
2270</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">,
2271if the change can be accommodated by the cache, it is done there.
2272If the cache becomes bigger than a block because of an insertion,
2273some of it is written to the
2274</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2275and deleted from the cache.
2276If the change does not intersect the cache, the cache is flushed.
2277The cache is only loaded at the new position if the change is smaller than a block;
2278otherwise, it is sent directly to the
2279</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">.
2280This is because
2281large changes are typically sequential,
2282whereupon the next change is unlikely to overlap the current one.
2283</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2284<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2285<span style="font-size: 10pt">A
2286</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
2287comprises a
2288</span><span style="font-size: 10pt"><tt>String</tt></span><span style="font-size: 10pt">
2289to hold the file name and some ancillary data such as dot and the modified bit.
2290The most important components, though, are a pair of
2291</span><span style="font-size: 10pt"><tt>Buffers</tt></span><span style="font-size: 10pt">,
2292one called the transcript and the other the contents.
2293Their use is described in the next section.
2294</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2295<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2296<span style="font-size: 10pt">The overall structure is shown in Figure 5.
2297Although it may seem that the data is touched many times on its
2298way from the
2299</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">,
2300it is read (by one UNIX system call) directly into the cache of the
2301associated
2302</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">;
2303no extra copy is done.
2304Similarly, when flushing the cache, the text is written
2305directly from the cache to disc.
2306Most operations act directly on the text in the cache.
2307A principle applied throughout
2308</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2309is that the fewer times the data is copied, the faster the program will run
2310(see also the paper by Waite<sup></sup></span><sup><span style="font-size: 6pt">15</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">).
2311</span><span style="font-size: 10pt"></span></p><center><img src="sam2.png"></center>
2312</center>
2313<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2314<span style="font-size: 8pt"><i>Figure 5. File data structures.
2315The temporary files are stored in the standard repository for such files
2316on the host system.
2317</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2318<p style="margin-top: 0; margin-bottom: 0.02in"></p>
2319
2320<p style="margin-top: 0; margin-bottom: 0.05in"></p>
2321<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2322<span style="font-size: 10pt">The contents of a
2323</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
2324are accessed by a routine that
2325copies to a buffer a substring of a file starting at a specified offset.
2326To read a byte at a time, a
2327per-</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
2328array is loaded starting from a specified initial position,
2329and bytes may then be read from the array.
2330The implementation is done by a macro similar to the C standard I/O
2331</span><span style="font-size: 10pt"><tt>getc</tt></span><span style="font-size: 10pt">
2332macro.<sup></sup></span><sup><span style="font-size: 6pt">14</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2333Because the reading may be done at any address, a minor change to the
2334macro allows the file to be read backwards.
2335This array is read-only; there is no
2336</span><span style="font-size: 10pt"><tt>putc</tt></span><span style="font-size: 10pt">.
2337</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2338<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2339<span style="font-size: 10pt"><b>Doing and undoing
2340</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2341<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2342<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2343has an unusual method for managing changes to files.
2344The command language makes it easy to specify multiple variable-length changes
2345to a file millions of bytes long, and such changes
2346must be made efficiently if the editor is to be practical.
2347The usual techniques for inserting and deleting strings
2348are inadequate under these conditions.
2349The
2350</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">
2351and
2352</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
2353data structures are designed for efficient random access to long strings,
2354but care must be taken to avoid super-linear behavior when making
2355many changes simultaneously.
2356</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2357<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2358<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2359uses a two-pass algorithm for making changes, and treats each file as a database
2360against which transactions are registered.
2361Changes are not made directly to the contents.
2362Instead, when a command is started, a &lsquo;mark&rsquo; containing
2363a sequence number is placed in the transcript
2364</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">,
2365and each change made to the file, either an insertion or deletion
2366or a change to the file name,
2367is appended to the end of the transcript.
2368When the command is complete, the transcript is rewound to the
2369mark and applied to the contents.
2370</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2371<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2372<span style="font-size: 10pt">One reason for separating evaluation from
2373application in this way is to simplify tracking the addresses of changes
2374made in the middle of a long sequence.
2375The two-pass algorithm also allows all changes to apply to the
2376</span><span style="font-size: 10pt"><i>original</i></span><span style="font-size: 10pt">
2377data: no change can affect another change made in the same command.
2378This is particularly important when evaluating an
2379</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
2380command because it prevents regular expression matches
2381from stumbling over changes made earlier in the execution.
2382Also, the two-pass
2383algorithm is cleaner than the way other UNIX editors allow changes to
2384affect each other;
2385for example,
2386</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s
2387idioms to do things like delete every other line
2388depend critically on the implementation.
2389Instead,
2390</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
2391simple model, in which all changes in a command occur effectively
2392simultaneously, is easy to explain and to understand.
2393</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2394<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2395<span style="font-size: 10pt">The records in the transcript are of the form &lsquo;&lsquo;delete substring from
2396locations
2397123 to 456&rsquo;&rsquo; and &lsquo;&lsquo;insert 11 characters &lsquo;hello there&rsquo; at location 789.&rsquo;&rsquo;
2398(It is an error if the changes are not at monotonically greater
2399positions through the file.)
2400While the update is occurring, these numbers must be
2401offset by earlier changes, but that is straightforward and
2402local to the update routine;
2403moreover, all the numbers have been computed
2404before the first is examined.
2405</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2406<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2407<span style="font-size: 10pt">Treating the file as a transaction system has another advantage:
2408undo is trivial.
2409All it takes is to invert the transcript after it has been
2410implemented, converting insertions
2411into deletions and vice versa, and saving them in a holding
2412</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">.
2413The &lsquo;do&rsquo; transcript can then be deleted from
2414the transcript
2415</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">
2416and replaced by the &lsquo;undo&rsquo; transcript.
2417If an undo is requested, the transcript is rewound and the undo transcript
2418executed.
2419Because the transcript
2420</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">
2421is not truncated after each command, it accumulates
2422successive changes.
2423A sequence of undo commands
2424can therefore back up the file arbitrarily,
2425which is more helpful than the more commonly implemented self-inverse form of undo.
2426(</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2427provides no way to undo an undo, but if it were desired,
2428it would be easy to provide by re-interpreting the &lsquo;do&rsquo; transcript.)
2429Each mark in the transcript contains a sequence number and the offset into
2430the transcript of the previous mark, to aid in unwinding the transcript.
2431Marks also contain the value of dot and the modified bit so these can be
2432restored easily.
2433Undoing multiple files is easy; it merely demands undoing all files whose
2434latest change has the same sequence number as the current file.
2435</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2436<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2437<span style="font-size: 10pt">Another benefit of having a transcript is that errors encountered in the middle
2438of a complicated command need not leave the files in an intermediate state.
2439By rewinding the transcript to the mark beginning the command,
2440the partial command can be trivially undone.
2441</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2442<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2443<span style="font-size: 10pt">When the update algorithm was first implemented, it was unacceptably slow,
2444so a cache was added to coalesce nearby changes,
2445replacing multiple small changes by a single larger one.
2446This reduced the number
2447of insertions into the transaction
2448</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">,
2449and made a dramatic improvement in performance,
2450but made it impossible
2451to handle changes in non-monotonic order in the file; the caching method
2452only works if changes don&rsquo;t overlap.
2453Before the cache was added, the transaction could in principle be sorted
2454if the changes were out of order, although
2455this was never done.
2456The current status is therefore acceptable performance with a minor
2457restriction on global changes, which is sometimes, but rarely, an annoyance.
2458</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2459<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2460<span style="font-size: 10pt">The update algorithm obviously paws the data more than simpler
2461algorithms, but it is not prohibitively expensive;
2462the caches help.
2463(The principle of avoiding copying the data is still honored here,
2464although not as piously:
2465the data is moved from contents&rsquo; cache to
2466the transcript&rsquo;s all at once and through only one internal buffer.)
2467Performance figures confirm the efficiency.
2468To read from a dead start a hundred kilobyte file on a VAX-11/750
2469takes 1.4 seconds of user time, 2.5 seconds of system time,
2470and 5 seconds of real time.
2471Reading the same file in
2472</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
2473takes 6.0 seconds of user time, 1.7 seconds of system time,
2474and 8 seconds of real time.
2475</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2476uses about half the CPU time.
2477A more interesting example is the one stated above:
2478inserting a character between every pair of characters in the file.
2479The
2480</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2481command is
2482</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
2483<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2484<span style="font-size: 9pt"><tt>,y/@/ a/x/</tt></span></p>
2485<p style="margin-top: 0; margin-bottom: 0.17in"></p>
2486
2487<p style="margin-top: 0; margin-bottom: 0.08in"></p>
2488<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2489<span style="font-size: 10pt">and takes 3 CPU seconds per kilobyte of input file, of which
2490about a third is spent in the regular expression code.
2491This translates to about 500 changes per second.
2492</span><span style="font-size: 10pt"><tt>Ed</tt></span><span style="font-size: 10pt">
2493takes 1.5 seconds per kilobyte to make a similar change (ignoring newlines),
2494but cannot undo it.
2495The same example in
2496</span><span style="font-size: 10pt"><tt>ex</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">9</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2497a variant of
2498</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
2499done at the University of California at Berkeley,
2500which allows one level of undoing, again takes 3 seconds.
2501In summary,
2502</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
2503performance is comparable to that of other UNIX editors, although it solves
2504a harder problem.
2505</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2506<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2507<span style="font-size: 10pt"><b>Communications
2508</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2509<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2510<span style="font-size: 10pt">The discussion so far has described the implementation of the host part of
2511</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">;
2512the next few sections explain how a machine with mouse and bitmap display
2513can be engaged to improve interaction.
2514</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2515is not the first editor to be written as two processes,<sup></sup></span><sup><span style="font-size: 6pt">16</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2516but its implementation
2517has some unusual aspects.
2518</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2519<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2520<span style="font-size: 10pt">There are several ways
2521</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
2522host and terminal parts may be connected.
2523The first and simplest is to forgo the terminal part and use the host
2524part&rsquo;s command language to edit text on an ordinary terminal.
2525This mode is invoked by starting
2526</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2527with the
2528</span><span style="font-size: 10pt"><tt>-d</tt></span><span style="font-size: 10pt">
2529option.
2530With no options,
2531</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2532runs separate host and terminal programs,
2533communicating with a message protocol over the physical
2534connection that joins them.
2535Typically, the connection is an RS-232 link between a Blit
2536(the prototypical display for
2537</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">)
2538and a host running
2539the Ninth Edition of the UNIX operating system.<sup></sup></span><sup><span style="font-size: 6pt">8</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2540(This is the version of the system used in the Computing Sciences Research
2541Center at AT&amp;T Bell Laboratories [now Lucent Technologies, Bell Labs], where I work.  Its relevant
2542aspects are discussed in the Blit paper.<sup></sup></span><sup><span style="font-size: 6pt">1</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">)
2543The implementation of
2544</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2545for the SUN computer runs both processes on the same machine and
2546connects them by a pipe.
2547</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2548<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2549<span style="font-size: 10pt">The low bandwidth of an RS-232 link
2550necessitated the split between
2551the two programs.
2552The division is a mixed blessing:
2553a program in two parts is much harder to write and to debug
2554than a self-contained one,
2555but the split makes several unusual configurations possible.
2556The terminal may be physically separated from the host, allowing the conveniences
2557of a mouse and bitmap display to be taken home while leaving the files at work.
2558It is also possible to run the host part on a remote machine:
2559</span></p><p style="margin-top: 0; margin-bottom: 0.08in"></p>
2560<p style="line-height: 1.1em; margin-left: 1.28in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2561<span style="font-size: 9pt"><tt>sam -r host</tt></span></p>
2562<p style="margin-top: 0; margin-bottom: 0.17in"></p>
2563
2564<p style="margin-top: 0; margin-bottom: 0.08in"></p>
2565<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2566<span style="font-size: 10pt">connects to the terminal in the usual way, and then makes a call
2567across the network to establish the host part of
2568</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2569on the named machine.
2570Finally, it cross-connects the I/O to join the two parts.
2571This allows
2572</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2573to be run on machines that do not support bitmap displays;
2574for example,
2575</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2576is the editor of choice on our Cray X-MP/24.
2577</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2578</span><span style="font-size: 10pt"><tt>-r</tt></span><span style="font-size: 10pt">
2579involves
2580</span><span style="font-size: 10pt"><i>three</i></span><span style="font-size: 10pt">
2581machines: the remote host, the terminal, and the local host.
2582The local host&rsquo;s job is simple but vital: it passes the data
2583between the remote host and terminal.
2584</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2585<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2586<span style="font-size: 10pt">The host and terminal exchange messages asynchronously
2587(rather than, say, as remote procedure calls) but there is no
2588error detection or correction
2589because, whatever the configuration, the connection is reliable.
2590Because the terminal handles mundane interaction tasks such as
2591popping up menus and interpreting the responses, the messages are about
2592data, not actions.
2593For example, the host knows nothing about what is displayed on the screen,
2594and when the user types a character, the message sent to the host says
2595&lsquo;&lsquo;insert a one-byte string at location 123 in file 7,&rsquo;&rsquo; not &lsquo;&lsquo;a character
2596was typed at the current position in the current file.&rsquo;&rsquo;
2597In other words, the messages look very much like the transaction records
2598in the transcripts.
2599</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2600<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2601<span style="font-size: 10pt">Either the host or terminal part of
2602</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2603may initiate a change to a file.
2604The command language operates on the host, while typing and some
2605mouse operations are executed directly in the terminal to optimize response.
2606Changes initiated by the host program must be transmitted to the terminal,
2607and
2608vice versa.
2609(A token is exchanged to determine which end is in control,
2610which means that characters typed while a time-consuming command runs
2611must be buffered and do not appear until the command is complete.)
2612To maintain consistent information,
2613the host and terminal track changes through a per-file
2614data structure that records what portions of the file
2615the terminal has received.
2616The data structure, called a
2617</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2618(a weak pun: it&rsquo;s a file with holes)
2619is held and updated by both the host and terminal.
2620A
2621</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2622is a list of
2623</span><span style="font-size: 10pt"><tt>Strings</tt></span><span style="font-size: 10pt">
2624holding those parts of the file known to the terminal,
2625separated by counts of the number of bytes in the interstices.
2626Of course, the host doesn&rsquo;t keep a separate copy of the data (it only needs
2627the lengths of the various pieces),
2628but the structure is the same on both ends.
2629</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2630<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2631<span style="font-size: 10pt">The
2632</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2633in the terminal doubles as a cache.
2634Since the terminal keeps the text for portions of the file it has displayed,
2635it need not request data from the host when revisiting old parts of the file
2636or redrawing obscured windows, which speeds things up considerably
2637over low-speed links.
2638</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2639<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2640<span style="font-size: 10pt">It&rsquo;s trivial for the terminal to maintain its
2641</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">,
2642because all changes made on the terminal apply to parts of the file
2643already loaded there.
2644Changes made by the host are compared against the
2645</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2646during the update sequence after each command.
2647Small changes to pieces of the file loaded in the terminal
2648are sent in their entirety.
2649Larger changes, and changes that fall entirely in the holes,
2650are transmitted as messages without literal data:
2651only the lengths of the deleted and inserted strings are transmitted.
2652When a command is completed, the terminal examines its visible
2653windows to see if any holes in their
2654</span><span style="font-size: 10pt"><tt>Rasps</tt></span><span style="font-size: 10pt">
2655intersect the visible portion of the file.
2656It then requests the missing data from the host,
2657along with up to 512 bytes of surrounding data, to minimize
2658the number of messages when visiting a new portion of the file.
2659This technique provides a kind of two-level lazy evaluation for the terminal.
2660The first level sends a minimum of information about
2661parts of the file not being edited interactively;
2662the second level waits until a change is displayed before
2663transmitting the new data.
2664Of course,
2665performance is also helped by having the terminal respond immediately to typing
2666and simple mouse requests.
2667Except for small changes to active pieces of the file, which are
2668transmitted to the terminal without negotiation,
2669the terminal is wholly responsible for deciding what is displayed;
2670the host uses the
2671</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2672only to tell the terminal what might be relevant.
2673</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2674<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2675<span style="font-size: 10pt">When a change is initiated by the host,
2676the messages to the terminal describing the change
2677are generated by the routine that applies the transcript of the changes
2678to the contents of the
2679</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">.
2680Since changes are undone by the same update routine,
2681undoing requires
2682no extra code in the communications;
2683the usual messages describing changes to the file are sufficient
2684to back up the screen image.
2685</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2686<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2687<span style="font-size: 10pt">The
2688</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2689is a particularly good example of the way caches are used in
2690</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">.
2691First, it facilitates access to the active portion of the text by placing
2692the busy text in main memory.
2693In so doing, it provides efficient access
2694to a large data structure that does not fit in memory.
2695Since the form of data is to be imposed by the user, not by the program,
2696and because characters will frequently be scanned sequentially,
2697files are stored as flat objects.
2698Caches help keep performance good and linear when working with such
2699data.
2700</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2701<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2702<span style="font-size: 10pt">Second, the
2703</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2704and several of the other caches have some
2705</span><span style="font-size: 10pt"><i>read-ahead;</i></span><span style="font-size: 10pt">
2706that is, the cache is loaded with more information than is needed for
2707the job immediately at hand.
2708When manipulating linear structures, the accesses are usually sequential,
2709and read-ahead can significantly reduce the average time to access the
2710next element of the object.
2711Sequential access is a common mode for people as well as programs;
2712consider scrolling through a document while looking for something.
2713</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2714<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2715<span style="font-size: 10pt">Finally, like any good data structure,
2716the cache guides the algorithm, or at least the implementation.
2717The
2718</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2719was actually invented to control the communications between the host and
2720terminal parts, but I realized very early that it was also a form of
2721cache.  Other caches were more explicitly intended to serve a double
2722purpose: for example, the caches in
2723</span><span style="font-size: 10pt"><tt>Files</tt></span><span style="font-size: 10pt">
2724that coalesce updates not only reduce traffic to the
2725transcript and contents
2726</span><span style="font-size: 10pt"><tt>Buffers</tt></span><span style="font-size: 10pt">,
2727they also clump screen updates so that complicated changes to the
2728screen are achieved in
2729just a few messages to the terminal.
2730This saved me considerable work: I did not need to write special
2731code to optimize the message traffic to the
2732terminal.
2733Caches pay off in surprising ways.
2734Also, they tend to be independent, so their performance improvements
2735are multiplicative.
2736</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2737<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2738<span style="font-size: 10pt"><b>Data structures in the terminal
2739</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2740<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2741<span style="font-size: 10pt">The terminal&rsquo;s job is to display and to maintain a consistent image of
2742pieces of the files being edited.
2743Because the text is always in memory, the data structures are
2744considerably simpler than those in the host part.
2745</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2746<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2747<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
2748typically has far more windows than does
2749</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">,
2750the window system within which its Blit implementation runs.
2751</span><span style="font-size: 10pt"><tt>Mux</tt></span><span style="font-size: 10pt">
2752has a fairly small number of asynchronously updated windows;
2753</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2754needs a large number of synchronously updated windows that are
2755usually static and often fully obscured.
2756The different tradeoffs guided
2757</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2758away from the memory-intensive implementation of windows, called
2759</span><span style="font-size: 10pt"><tt>Layers</tt></span><span style="font-size: 10pt">,<sup></sup></span><sup><span style="font-size: 6pt">17</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2760used in
2761</span><span style="font-size: 10pt"><tt>mux.</tt></span><span style="font-size: 10pt">
2762Rather than depending on a complete bitmap image of the display for each window,
2763</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2764regenerates the image from its in-memory text
2765(stored in the
2766</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">)
2767when necessary, although it will use such an image if it is available.
2768Like
2769</span><span style="font-size: 10pt"><tt>Layers</tt></span><span style="font-size: 10pt">,
2770though,
2771</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2772uses the screen bitmap as active storage in which to update the image using
2773</span><span style="font-size: 10pt"><tt>bitblt</tt></span><span style="font-size: 10pt">.<sup></sup></span><sup><span style="font-size: 6pt">18,19</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2774The resulting organization, pictured in Figure 6,
2775has a global array of windows, called
2776</span><span style="font-size: 10pt"><tt>Flayers</tt></span><span style="font-size: 10pt">,
2777each of which holds an image of a piece of text held in a data structure
2778called a
2779</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">,
2780which in turn represents
2781a rectangular window full of text displayed in some
2782</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">.
2783Each
2784</span><span style="font-size: 10pt"><tt>Flayer</tt></span><span style="font-size: 10pt">
2785appears in a global list that orders them all front-to-back
2786on the display, and simultaneously as an element of a per-file array
2787that holds all the open windows for that file.
2788The complement in the terminal of the
2789</span><span style="font-size: 10pt"><tt>File</tt></span><span style="font-size: 10pt">
2790on the host is called a
2791</span><span style="font-size: 10pt"><tt>Text</tt></span><span style="font-size: 10pt">;
2792each connects its
2793</span><span style="font-size: 10pt"><tt>Flayers</tt></span><span style="font-size: 10pt">
2794to the associated
2795</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">.
2796</span><span style="font-size: 10pt"></span></p><center><img src="sam3.png"></center>
2797</center>
2798<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2799<span style="font-size: 8pt"><i>Figure 6. Data structures in the terminal.
2800</i></span><span style="font-size: 8pt"><tt>Flayers</tt></span><span style="font-size: 8pt"><i>
2801are also linked together into a front-to-back list.
2802</i></span><span style="font-size: 8pt"><tt>Boxes</tt></span><span style="font-size: 8pt"><i>
2803are discussed in the next section.
2804</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
2805<p style="margin-top: 0; margin-bottom: 0.02in"></p>
2806
2807<p style="margin-top: 0; margin-bottom: 0.05in"></p>
2808<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2809<span style="font-size: 10pt">The
2810</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2811for a
2812</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2813contains the image of the text.
2814For a fully visible window, the
2815</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2816will be the screen (or at least the
2817</span><span style="font-size: 10pt"><tt>Layer</tt></span><span style="font-size: 10pt">
2818in which
2819</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2820is being run),
2821while for partially obscured windows the
2822</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2823will be off-screen.
2824If the window is fully obscured, the
2825</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2826will be null.
2827</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2828<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2829<span style="font-size: 10pt">The
2830</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2831is a kind of cache.
2832When making changes to the display, most of the original image will
2833look the same in the final image, and the update algorithms exploit this.
2834The
2835</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2836software updates the image in the
2837</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2838incrementally; the
2839</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2840is not just an image, it is a data structure.<sup></sup></span><sup><span style="font-size: 6pt">18,19</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2841The job of the software that updates the display is therefore
2842to use as much as possible of the existing image (converting the
2843text from ASCII characters to pixels is expensive) in a sort of two-dimensional
2844string insertion algorithm.
2845The details of this process are described in the next section.
2846</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2847<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2848<span style="font-size: 10pt">The
2849</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2850software has no code to support overlapping windows;
2851its job is to keep a single
2852</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2853up to date.
2854It falls to the
2855</span><span style="font-size: 10pt"><tt>Flayer</tt></span><span style="font-size: 10pt">
2856software to multiplex the various
2857</span><span style="font-size: 10pt"><tt>Bitmaps</tt></span><span style="font-size: 10pt">
2858onto the screen.
2859The problem of maintaining overlapping
2860</span><span style="font-size: 10pt"><tt>Flayers</tt></span><span style="font-size: 10pt">
2861is easier than for
2862</span><span style="font-size: 10pt"><tt>Layers</tt></span><span style="font-size: 10pt"><sup></sup></span><sup><span style="font-size: 6pt">17</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt">
2863because changes are made synchronously and because the contents of the window
2864can be reconstructed from the data stored in the
2865</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">;
2866the
2867</span><span style="font-size: 10pt"><tt>Layers</tt></span><span style="font-size: 10pt">
2868software
2869makes no such assumptions.
2870In
2871</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">,
2872the window being changed is almost always fully visible, because the current
2873window is always fully visible, by construction.
2874However, when multi-file changes are being made, or when
2875more than one window is open on a file,
2876it may be necessary to update partially obscured windows.
2877</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2878<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2879<span style="font-size: 10pt">There are three cases: the window is
2880fully visible, invisible (fully obscured), or partially visible.
2881If fully visible, the
2882</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2883is part of the screen, so when the
2884</span><span style="font-size: 10pt"><tt>Flayer</tt></span><span style="font-size: 10pt">
2885update routine calls the
2886</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2887update routine, the screen will be updated directly.
2888If the window is invisible,
2889there is no associated
2890</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">,
2891and all that is necessary is to update the
2892</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2893data structure, not the image.
2894If the window is partially visible, the
2895</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2896routine is called to update the image in the off-screen
2897</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">,
2898which may require regenerating it from the text of the window.
2899The
2900</span><span style="font-size: 10pt"><tt>Flayer</tt></span><span style="font-size: 10pt">
2901code then clips this
2902</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
2903against the
2904</span><span style="font-size: 10pt"><tt>Bitmaps</tt></span><span style="font-size: 10pt">
2905of all
2906</span><span style="font-size: 10pt"><tt>Frames</tt></span><span style="font-size: 10pt">
2907in front of the
2908</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2909being modified, and the remainder is copied to the display.
2910</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2911<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2912<span style="font-size: 10pt">This is much faster than recreating the image off-screen
2913for every change, or clipping all the changes made to the image
2914during its update.
2915Unfortunately, these caches can also consume prohibitive amounts of
2916memory, so they are freed fairly liberally &mdash; after every change to the
2917front-to-back order of the
2918</span><span style="font-size: 10pt"><tt>Flayers</tt></span><span style="font-size: 10pt">.
2919The result is that
2920the off-screen
2921</span><span style="font-size: 10pt"><tt>Bitmaps</tt></span><span style="font-size: 10pt">
2922exist only while multi-window changes are occurring,
2923which is the only time the performance improvement they provide is needed.
2924Also, the user interface causes fully-obscured windows to be the
2925easiest to make &mdash;
2926creating a canonically sized and placed window requires only a button click
2927&mdash; which reduces the need for caching still further.
2928</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2929<p style="margin-top: 0; margin-bottom: 0.17in"></p>
2930<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2931<span style="font-size: 10pt"><b>Screen update
2932</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2933<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2934<span style="font-size: 10pt">Only two low-level primitives are needed for incremental update:
2935</span><span style="font-size: 10pt"><tt>bitblt</tt></span><span style="font-size: 10pt">,
2936which copies rectangles of pixels, and
2937</span><span style="font-size: 10pt"><tt>string</tt></span><span style="font-size: 10pt">
2938(which in turn calls
2939</span><span style="font-size: 10pt"><tt>bitblt</tt></span><span style="font-size: 10pt">),
2940which draws a null-terminated character string in a
2941</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">.
2942A
2943</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
2944contains a list of
2945</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">,
2946each of which defines a horizontal strip of text in the window
2947(see Figure 7).
2948A
2949</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
2950has a character string
2951</span><span style="font-size: 10pt"><tt>str</tt></span><span style="font-size: 10pt">,
2952and a
2953</span><span style="font-size: 10pt"><tt>Rectangle</tt></span><span style="font-size: 10pt">
2954</span><span style="font-size: 10pt"><tt>rect</tt></span><span style="font-size: 10pt">
2955that defines the location of the strip in the window.
2956(The text in
2957</span><span style="font-size: 10pt"><tt>str</tt></span><span style="font-size: 10pt">
2958is stored in the
2959</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
2960separately from the
2961</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
2962associated with the window&rsquo;s file, so
2963</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
2964are self-contained.)
2965The invariant is that
2966the image of the
2967</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
2968can be reproduced by calling
2969</span><span style="font-size: 10pt"><tt>string</tt></span><span style="font-size: 10pt">
2970with argument
2971</span><span style="font-size: 10pt"><tt>str</tt></span><span style="font-size: 10pt">
2972to draw the string in
2973</span><span style="font-size: 10pt"><tt>rect</tt></span><span style="font-size: 10pt">,
2974and the resulting picture fits perfectly within
2975</span><span style="font-size: 10pt"><tt>rect</tt></span><span style="font-size: 10pt">.
2976In other words, the
2977</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
2978define the tiling of the window.
2979The tiling may be complicated by long lines of text, which
2980are folded onto the next line.
2981Some editors use horizontal scrolling to avoid this complication,
2982but to be comfortable this technique requires that lines not be
2983</span><span style="font-size: 10pt"><i>too</i></span><span style="font-size: 10pt">
2984long;
2985</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
2986has no such restriction.
2987Also, and perhaps more importantly, UNIX programs and terminals traditionally fold
2988long lines to make their contents fully visible.
2989</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
2990<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
2991<span style="font-size: 10pt">Two special kinds of
2992</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
2993contain a single
2994character: either a newline or a tab.
2995Newlines and tabs are white space.
2996A newline
2997</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
2998always extends to the right edge of the window,
2999forcing the following
3000</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
3001to the next line.
3002The width of a tab depends on where it is located:
3003it forces the next
3004</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
3005to begin at a tab location.
3006Tabs also
3007have a minimum width equivalent to a blank (blanks are
3008drawn by
3009</span><span style="font-size: 10pt"><tt>string</tt></span><span style="font-size: 10pt">
3010and are not treated specially); newlines have a minimum width of zero.
3011</span><span style="font-size: 10pt"></span></p><center><img src="sam4.png"></center>
3012</center>
3013<p style="margin-top: 0; margin-bottom: 0.08in"></p>
3014<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3015<span style="font-size: 8pt"><i>Figure 7. A line of text showing its
3016</i></span><span style="font-size: 8pt"><tt>Boxes</tt></span><span style="font-size: 8pt"><i>.
3017The first two blank
3018</i></span><span style="font-size: 8pt"><tt>Boxes</tt></span><span style="font-size: 8pt"><i>
3019contain tabs; the last contains a newline.
3020Spaces are handled as ordinary characters.
3021</i></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3022<p style="margin-top: 0; margin-bottom: 0.02in"></p>
3023
3024<p style="margin-top: 0; margin-bottom: 0.05in"></p>
3025<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3026<span style="font-size: 10pt">The update algorithms always use the
3027</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">
3028image of the text (either the display or cache
3029</span><span style="font-size: 10pt"><tt>Bitmap</tt></span><span style="font-size: 10pt">);
3030they never examine the characters within a
3031</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
3032except when the
3033</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
3034needs to be split in two.
3035Before a change, the window consists of a tiling of
3036</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">;
3037after the change the window is tiled differently.
3038The update algorithms rearrange the tiles in place, without
3039backup storage.
3040The algorithms are not strictly optimal &mdash; for example, they can
3041clear a pixel that is later going to be written upon &mdash;
3042but they never move a tile that doesn&rsquo;t need to be moved,
3043and they move each tile at most once.
3044</span><span style="font-size: 10pt"><tt>Frinsert</tt></span><span style="font-size: 10pt">
3045on a Blit can absorb over a thousand characters a second if the strings
3046being inserted are a few tens of characters long.
3047</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3048<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3049<span style="font-size: 10pt">Consider
3050</span><span style="font-size: 10pt"><tt>frdelete</tt></span><span style="font-size: 10pt">.
3051Its job is to delete a substring from a
3052</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
3053and restore the image of the
3054</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">.
3055The image of a substring has a peculiar shape (see Figure 2) comprising
3056possibly a partial line,
3057zero or more full lines,
3058and possibly a final partial line.
3059For reference, call this the
3060</span><span style="font-size: 10pt"><i>Z-shape.
3061</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Frdelete</tt></span><span style="font-size: 10pt">
3062begins by splitting, if necessary, the
3063</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
3064containing the ends of
3065the substring so the substring begins and ends on
3066</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
3067boundaries.
3068Because the substring is being deleted, its image is not needed,
3069so the Z-shape is then cleared.
3070Then, tiles (that is, the images of
3071</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">)
3072are copied, using
3073</span><span style="font-size: 10pt"><tt>bitblt</tt></span><span style="font-size: 10pt">,
3074from immediately after the Z-shape to
3075the beginning of the Z-shape,
3076resulting in a new Z-shape.
3077(</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
3078whose contents would span two lines in the new position must first be split.)
3079</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3080<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3081<span style="font-size: 10pt">Copying the remainder of the
3082</span><span style="font-size: 10pt"><tt>Frame</tt></span><span style="font-size: 10pt">
3083tile by tile
3084this way will clearly accomplish the deletion but eventually,
3085typically when the copying algorithm encounters a tab or newline,
3086the old and new
3087</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
3088coordinates of the tile
3089to be copied are the same.
3090This correspondence implies
3091that the Z-shape has its beginning and ending edges aligned
3092vertically, and a sequence of at most two
3093</span><span style="font-size: 10pt"><tt>bitblts</tt></span><span style="font-size: 10pt">
3094can be used to copy the remaining tiles.
3095The last step is to clear out the resulting empty space at the bottom
3096of the window;
3097the number of lines to be cleared is the number of complete lines in the
3098Z-shape closed by the final
3099</span><span style="font-size: 10pt"><tt>bitblts.</tt></span><span style="font-size: 10pt">
3100The final step is to merge horizontally adjacent
3101</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
3102of plain text.
3103The complete source to
3104</span><span style="font-size: 10pt"><tt>frdelete</tt></span><span style="font-size: 10pt">
3105is less than 100 lines of C.
3106</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3107<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3108<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>frinsert</tt></span><span style="font-size: 10pt">
3109is more complicated because it must do four passes:
3110one to construct the
3111</span><span style="font-size: 10pt"><tt>Box</tt></span><span style="font-size: 10pt">
3112list for the inserted string,
3113one to reconnoitre,
3114one to copy (in opposite order to
3115</span><span style="font-size: 10pt"><tt>frdelete</tt></span><span style="font-size: 10pt">)
3116the
3117</span><span style="font-size: 10pt"><tt>Boxes</tt></span><span style="font-size: 10pt">
3118to make the hole for the new text,
3119and finally one to copy the new text into place.
3120Overall, though,
3121</span><span style="font-size: 10pt"><tt>frinsert</tt></span><span style="font-size: 10pt">
3122has a similar flavor to
3123</span><span style="font-size: 10pt"><tt>frdelete</tt></span><span style="font-size: 10pt">,
3124and needn&rsquo;t be described further.
3125</span><span style="font-size: 10pt"><tt>Frinsert</tt></span><span style="font-size: 10pt">
3126and its subsidiary routines comprise 211 lines of C.
3127</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3128<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3129<span style="font-size: 10pt">The terminal source code is 3024 lines of C,
3130and the host source is 5797 lines.
3131</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3132<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3133<span style="font-size: 10pt"><b>Discussion
3134</b></span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3135<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3136<span style="font-size: 10pt"><b>History
3137</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3138<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3139<span style="font-size: 10pt">The immediate ancestor of
3140</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3141was the original text editor for the Blit, called
3142</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">.
3143</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3144inherited
3145</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">&rsquo;s
3146two-process structure and mouse language almost unchanged, but
3147</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3148suffered from several drawbacks that were addressed in the design of
3149</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">.
3150The most important of these was the lack of a command language.
3151Although
3152</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3153was easy to use for simple editing, it provided no direct help with
3154large or repetitive editing tasks.  Instead, it provided a command to pass
3155selected text through a shell pipeline,
3156but this was no more satisfactory than could be expected of a stopgap measure.
3157</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3158<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3159<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Jim</tt></span><span style="font-size: 10pt">
3160was written primarily as a vehicle for experimenting with a mouse-based
3161interface to text, and the experiment was successful.
3162</span><span style="font-size: 10pt"><tt>Jim</tt></span><span style="font-size: 10pt">
3163had some spin-offs:
3164</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">,
3165the second window system for the Blit, is essentially a multiplexed
3166version of the terminal part of
3167</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">;
3168and the debugger
3169</span><span style="font-size: 10pt"><tt>pi</tt></span><span style="font-size: 10pt">&rsquo;s
3170user interface<sup></sup></span><sup><span style="font-size: 6pt">20</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt"> was closely modeled on
3171</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">&rsquo;s.
3172But after a couple of years,
3173</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3174had become difficult to maintain and limiting to use,
3175and its replacement was overdue.
3176</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3177<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3178<span style="font-size: 10pt">I began the design of
3179</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3180by asking
3181</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3182customers what they wanted.
3183This was probably a mistake; the answers were essentially a list of features
3184to be found in other editors, which did not provide any of the
3185guiding principles I was seeking.
3186For instance, one common request was for a &lsquo;&lsquo;global substitute,&rsquo;&rsquo;
3187but no one suggested how to provide it within a cut-and-paste editor.
3188I was looking for a scheme that would
3189support such specialized features comfortably in the context of some
3190general command language.
3191Ideas were not forthcoming, though, particularly given my insistence
3192on removing all limits on file sizes, line lengths and so on.
3193Even worse, I recognized that, since the mouse could easily
3194indicate a region of the screen that was not an integral number of lines,
3195the command language would best forget about newlines altogether,
3196and that meant the command language had to treat the file as a single
3197string, not an array of lines.
3198</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3199<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3200<span style="font-size: 10pt">Eventually, I decided that thinking was not getting me very far and it was
3201time to try building.
3202I knew that the terminal part could be built easily &mdash;
3203that part of
3204</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3205behaved acceptably well &mdash; and that most of the hard work was going
3206to be in the host part: the file interface, command interpreter and so on.
3207Moreover, I had some ideas about how the architecture of
3208</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3209could be improved without destroying its basic structure, which I liked
3210in principle but which hadn&rsquo;t worked out as well as I had hoped.
3211So I began by designing the file data structure,
3212starting with the way
3213</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3214worked &mdash; comparable to a single structure merging
3215</span><span style="font-size: 10pt"><tt>Disc</tt></span><span style="font-size: 10pt">
3216and
3217</span><span style="font-size: 10pt"><tt>Buffer</tt></span><span style="font-size: 10pt">,
3218which I split to make the cache more general
3219&mdash; and thinking about how global substitute could be implemented.
3220The answer was clearly that it had to be done in two passes,
3221and the transcript-oriented implementation fell out naturally.
3222</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3223<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3224<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3225was written bottom-up,
3226starting from the data structures and algorithms for manipulating text,
3227through the command language and up to the code for maintaining
3228the display.
3229In retrospect, it turned out well, but this implementation method is
3230not recommended in general.
3231There were several times when I had a large body of interesting code
3232assembled and no clue how to proceed with it.
3233The command language, in particular, took almost a year to figure out,
3234but can be implemented (given what was there at the beginning of that year)
3235in a day or two.  Similarly, inventing the
3236</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
3237data structure delayed the
3238connection of the host and terminal pieces by another few months.
3239</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3240took about two years to write, although only about four months were
3241spent actually working on it.
3242</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3243<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3244<span style="font-size: 10pt">Part of the design process was unusual:
3245the subset of the protocol that maintains the
3246</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
3247was simulated, debugged
3248and verified by an automatic protocol analyzer,<sup></sup></span><sup><span style="font-size: 6pt">21</span><span style="font-size: 10pt"></span></sup><span style="font-size: 10pt"> and was bug-free
3249from the start.
3250The rest of the protocol, concerned mostly
3251with keeping menus up to date,
3252was unfortunately too unwieldy for such analysis,
3253and was debugged by more traditional methods, primarily
3254by logging in a file all messages in and out of the host.
3255</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3256<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3257<span style="font-size: 10pt"><b>Reflections
3258</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3259<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3260<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3261is essentially the only interactive editor used by the sixty or so members of
3262the computing science research center in which I work.
3263The same could not be said of
3264</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">;
3265the lack of a command language kept some people from adopting it.
3266The union of a user interface as comfortable as
3267</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">&rsquo;s
3268with a command language as powerful as
3269</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s&dagger;
3270</span></p><p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.50in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3271<span style="font-size: 10pt">is essential to
3272</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3273success.
3274When
3275</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3276was first made available to the
3277</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3278community,
3279almost everyone switched to it within two or three days.
3280In the months that followed, even people who had never adopted
3281</span><span style="font-size: 10pt"><tt>jim</tt></span><span style="font-size: 10pt">
3282started using
3283</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3284exclusively.
3285</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3286<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3287<span style="font-size: 10pt">To be honest,
3288</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
3289still gets occasional use, but usually when
3290something quick needs to be done and the overhead of
3291downloading the terminal part of
3292</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3293isn&rsquo;t worth the trouble.
3294Also, as a &lsquo;line&rsquo; editor,
3295</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3296</span><span style="font-size: 10pt"><tt>-d</tt></span><span style="font-size: 10pt">
3297is a bit odd;
3298when using a good old ASCII terminal, it&rsquo;s comforting to have
3299a true line editor.
3300But it is fair to say that
3301</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3302command language has displaced
3303</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s
3304for most of the complicated editing that has kept line editors
3305(that is, command-driven editors) with us.
3306</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3307<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3308<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">&rsquo;s
3309command language is even fancier than
3310</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s,
3311and most
3312</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3313customers don&rsquo;t come near to using all its capabilities.
3314Does it need to be so sophisticated?
3315I think the answer is yes, for two reasons.
3316</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3317<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3318<span style="font-size: 10pt">First, the
3319</span><span style="font-size: 10pt"><i>model</i></span><span style="font-size: 10pt">
3320for
3321</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3322command language is really relatively simple, and certainly simpler than that of
3323</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">.
3324For instance, there is only one kind of textual loop in
3325</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3326&mdash; the
3327</span><span style="font-size: 10pt"><tt>x</tt></span><span style="font-size: 10pt">
3328command &mdash;
3329while
3330</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
3331has three (the
3332</span><span style="font-size: 10pt"><tt>g</tt></span><span style="font-size: 10pt">
3333command, the global flag on substitutions, and the implicit loop over
3334lines in multi-line substitutions).
3335Also,
3336</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s
3337substitute command is necessary to make changes within lines, but in
3338</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3339the
3340</span><span style="font-size: 10pt"><tt>s</tt></span><span style="font-size: 10pt">
3341command is more of a familiar convenience than a necessity;
3342</span><span style="font-size: 10pt"><tt>c</tt></span><span style="font-size: 10pt">
3343and
3344</span><span style="font-size: 10pt"><tt>t</tt></span><span style="font-size: 10pt">
3345can do all the work.
3346</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3347<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3348<span style="font-size: 10pt">Second,
3349given a community that expects an editor to be about as powerful as
3350</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">,
3351it&rsquo;s hard to see how
3352</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3353could really be much simpler and still satisfy that expectation.
3354People want to do &lsquo;&lsquo;global substitutes,&rsquo;&rsquo; and most are content
3355to have the recipe for that and a few other fancy changes.
3356The sophistication of the command language is really just a veneer
3357over a design that makes it possible to do global substitutes
3358in a screen editor.
3359Some people will always want something more, however, and it&rsquo;s gratifying to
3360be able to provide it.
3361The real power of
3362</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3363command language comes from composability of the operators, which is by
3364nature orthogonal to the underlying model.
3365In other words,
3366</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3367is not itself complex, but it makes complex things possible.
3368If you don&rsquo;t want to do anything complex, you can ignore the
3369complexity altogether, and many people do so.
3370</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3371<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3372<span style="font-size: 10pt">Sometimes I am asked the opposite question: why didn&rsquo;t I just make
3373</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3374a real programmable editor, with macros and variables and so on?
3375The main reason is a matter of taste: I like the editor
3376to be the same every time I use it.
3377There is one technical reason, though:
3378programmability in editors is largely a workaround for insufficient
3379interactivity.
3380Programmable editors are used to make particular, usually short-term,
3381things easy to do, such as by providing shorthands for common actions.
3382If things are generally easy to do in the first place,
3383shorthands are not as helpful.
3384</span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3385makes common editing operations very easy, and the solutions to
3386complex editing problems seem commensurate with the problems themselves.
3387Also, the ability to edit the
3388</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3389window makes it easy to repeat commands &mdash; it only takes a mouse button click
3390to execute a command again.
3391</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3392<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3393<span style="font-size: 10pt"><b>Pros and cons
3394</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3395<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3396<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3397has several other good points,
3398and its share of problems.
3399Among the good things is the idea of
3400structural regular expressions,
3401whose usefulness has only begun to be explored.
3402They were arrived at serendipitously when I attempted to distill the essence of
3403</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s
3404way of doing global substitution and recognized that the looping command in
3405</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
3406was implicitly imposing a structure (an array of lines) on the file.
3407</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3408<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3409<span style="font-size: 10pt">Another of
3410</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3411good things is its undo capability.
3412I had never before used an editor with a true undo,
3413but I would never go back now.
3414Undo
3415</span><span style="font-size: 10pt"><i>must</i></span><span style="font-size: 10pt">
3416be done well, but if it is, it can be relied on.
3417For example,
3418it&rsquo;s safe to experiment if you&rsquo;re not sure how to write some intricate command,
3419because if you make a mistake, it can be fixed simply and reliably.
3420I learned two things about undo from writing
3421</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">:
3422first, it&rsquo;s easy to provide if you design it in from the beginning, and
3423second, it&rsquo;s necessary, particularly if the system has some subtle
3424properties that may be unfamiliar or error-prone for users.
3425</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3426<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3427<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">&rsquo;s
3428lack of internal limits and sizes is a virtue.
3429Because it avoids all fixed-size tables and data structures,
3430</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3431is able to make global changes to files that some of our other
3432tools cannot even read.
3433Moreover, the design keeps the performance linear when doing such
3434operations, although I must admit
3435</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3436does get slow when editing a huge file.
3437</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3438<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3439<span style="font-size: 10pt">Now, the problems.
3440Externally, the most obvious is that it is poorly integrated into the
3441surrounding window system.
3442By design, the user interface in
3443</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3444feels almost identical to that of
3445</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">,
3446but a thick wall separates text in
3447</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3448from the programs running in
3449</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">.
3450For instance, the &lsquo;snarf buffer&rsquo; in
3451</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3452must be maintained separately from that in
3453</span><span style="font-size: 10pt"><tt>mux</tt></span><span style="font-size: 10pt">.
3454This is regrettable, but probably necessary given the unusual configuration
3455of the system, with a programmable terminal on the far end of an RS-232 link.
3456</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3457<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3458<span style="font-size: 10pt"></span><span style="font-size: 10pt"><tt>Sam</tt></span><span style="font-size: 10pt">
3459is reliable; otherwise, people wouldn&rsquo;t use it.
3460But it was written over such a long time, and has so many new (to me)
3461ideas in it, that I would like to see it done over again to clean
3462up the code and remove many of the lingering problems in the implementation.
3463The worst part is in the interconnection of the host and terminal parts,
3464which might even be able to go away in a redesign for a more
3465conventional window system.
3466The program must be split in two to use the terminal effectively,
3467but the low bandwidth of the connection forces the separation to
3468occur in an inconvenient part of the design if performance is to be acceptable.
3469A simple remote procedure call
3470protocol driven by the host, emitting only graphics
3471commands, would be easy to write but wouldn&rsquo;t have nearly the
3472necessary responsiveness.  On the other hand, if the terminal were in control
3473and requested much simpler file services from the host, regular expression
3474searches would require that the terminal read the entire file over its RS-232
3475link, which would be unreasonably slow.
3476A compromise in which either end can take control is necessary.
3477In retrospect, the communications protocol should have been
3478designed and verified formally, although I do not know of any tool
3479that can adequately relate the protocol to
3480its implementation.
3481</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3482<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3483<span style="font-size: 10pt">Not all of
3484</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3485users are comfortable with its command language, and few are adept.
3486Some (venerable) people use a sort of
3487&lsquo;&lsquo;</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
3488subset&rsquo;&rsquo; of
3489</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3490command language,
3491and even ask why
3492</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3493command language is not exactly
3494</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s.
3495(The reason, of course, is that
3496</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3497model for text does not include newlines, which are central to
3498</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">.
3499Making the text an array of newlines to the command language would
3500be too much of a break from the seamless model provided by the mouse.
3501Some editors, such as
3502</span><span style="font-size: 10pt"><tt>vi</tt></span><span style="font-size: 10pt">,
3503are willing to make this break, though.)
3504The difficulty is that
3505</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">&rsquo;s
3506syntax is so close to
3507</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">&rsquo;s
3508that people believe it
3509</span><span style="font-size: 10pt"><i>should</i></span><span style="font-size: 10pt">
3510be the same.
3511I thought, with some justification in hindsight,
3512that making
3513</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3514similar to
3515</span><span style="font-size: 10pt"><tt>ed</tt></span><span style="font-size: 10pt">
3516would make it easier to learn and to accept.
3517But I may have overstepped and raised the users&rsquo;
3518expectations too much.
3519It&rsquo;s hard to decide which way to resolve this problem.
3520</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3521<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.35in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3522<span style="font-size: 10pt">Finally, there is a tradeoff in
3523</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3524that was decided by the environment in which it runs:
3525</span><span style="font-size: 10pt"><tt>sam</tt></span><span style="font-size: 10pt">
3526is a multi-file editor, although in a different system there might instead be
3527multiple single-file editors.
3528The decision was made primarily because starting a new program in a Blit is
3529time-consuming.
3530If the choice could be made freely, however, I would
3531still choose the multi-file architecture, because it allows
3532groups of files to be handled as a unit;
3533the usefulness of the multi-file commands is incontrovertible.
3534It is delightful to have the source to an entire program
3535available at your fingertips.
3536</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3537<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3538<span style="font-size: 10pt"><b>Acknowledgements
3539</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3540<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3541<span style="font-size: 10pt">Tom Cargill suggested the idea behind the
3542</span><span style="font-size: 10pt"><tt>Rasp</tt></span><span style="font-size: 10pt">
3543data structure.
3544Norman Wilson and Ken Thompson influenced the command language.
3545This paper was improved by comments from
3546Al Aho,
3547Jon Bentley,
3548Chris Fraser,
3549Gerard Holzmann,
3550Brian Kernighan,
3551Ted Kowalski,
3552Doug McIlroy
3553and
3554Dennis Ritchie.
3555</span></p><p style="margin-top: 0; margin-bottom: 0.17in"></p>
3556<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3557<span style="font-size: 10pt"><b>REFERENCES
3558</b></span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3559<p style="margin-top: 0; margin-bottom: 0.05in"></p>
3560<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3561<span style="font-size: 10pt"> 1.    R. Pike,
3562&lsquo;The Blit: a multiplexed graphics terminal,&rsquo;
3563</span><span style="font-size: 10pt"><i>AT&amp;T Bell Labs. Tech. J.,
3564</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>63</b></span><span style="font-size: 10pt">,
3565(8),
35661607-1631 (1984).
3567</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3568<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3569<span style="font-size: 10pt"> 2.    L. Johnson,
3570</span><span style="font-size: 10pt"><i>MacWrite,</i></span><span style="font-size: 10pt">
3571Apple Computer Inc., Cupertino, Calif. 1983.
3572</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3573<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3574<span style="font-size: 10pt"> 3.    B. Lampson,
3575&lsquo;Bravo Manual,&rsquo;
3576in
3577</span><span style="font-size: 10pt"><i>Alto User&rsquo;s Handbook,
3578</i></span><span style="font-size: 10pt">pp. 31-62,
3579Xerox Palo Alto Research Center,
3580Palo Alto, Calif.
35811979.
3582</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3583<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3584<span style="font-size: 10pt"> 4.    W. Teitelman,
3585&lsquo;A tour through Cedar,&rsquo;
3586</span><span style="font-size: 10pt"><i>IEEE Software,
3587</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>1</b></span><span style="font-size: 10pt">
3588(2), 44-73 (1984).
3589</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3590<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3591<span style="font-size: 10pt"> 5.    J. Gutknecht,
3592&lsquo;Concepts of the text editor Lara,&rsquo;
3593</span><span style="font-size: 10pt"><i>Comm. ACM,
3594</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>28</b></span><span style="font-size: 10pt">,
3595(9),
3596942-960 (1985).
3597</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3598<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3599<span style="font-size: 10pt"> 6.    Bell Telephone Laboratories,
3600</span><span style="font-size: 10pt"><i>UNIX Programmer&rsquo;s Manual,
3601</i></span><span style="font-size: 10pt">Holt, Rinehart and Winston, New York 1983.
3602</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3603<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3604<span style="font-size: 10pt"> 7.    B. W. Kernighan and R. Pike,
3605</span><span style="font-size: 10pt"><i>The Unix Programming Environment,
3606</i></span><span style="font-size: 10pt">Prentice-Hall, Englewood Cliffs, New Jersey 1984.
3607</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3608<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3609<span style="font-size: 10pt"> 8.    </span><span style="font-size: 10pt"><i>Unix Time-Sharing System Programmer&rsquo;s Manual, Research Version, Ninth Edition,
3610Volume 1,
3611</i></span><span style="font-size: 10pt">AT&amp;T Bell Laboratories, Murray Hill, New Jersey 1986.
3612</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3613<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3614<span style="font-size: 10pt"> 9.    </span><span style="font-size: 10pt"><i>Unix Time-Sharing System Programmer&rsquo;s Manual, 4.1 Berkeley Software Distribution,
3615Volumes 1 and 2C,
3616</i></span><span style="font-size: 10pt">University of California, Berkeley, Calif. 1981.
3617</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3618<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3619<span style="font-size: 10pt">10.    R. Pike,
3620&lsquo;Structural Regular Expressions,&rsquo;
3621</span><span style="font-size: 10pt"><i>Proc. EUUG Spring Conf., Helsinki 1987,
3622</i></span><span style="font-size: 10pt">Eur. Unix User&rsquo;s Group, Buntingford, Herts, UK 1987.
3623</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3624<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3625<span style="font-size: 10pt">11.    A. Goldberg,
3626</span><span style="font-size: 10pt"><i>Smalltalk-80 &ndash; The Interactive Programming Environment,
3627</i></span><span style="font-size: 10pt">Addison-Wesley, Reading, Mass. 1984.
3628</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3629<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3630<span style="font-size: 10pt">12.    K. Thompson,
3631&lsquo;Regular expression search algorithm,&rsquo;
3632</span><span style="font-size: 10pt"><i>Comm. ACM,
3633</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>11</b></span><span style="font-size: 10pt">,
3634(6),
3635419-422 (1968).
3636</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3637<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3638<span style="font-size: 10pt">13.    A. V. Aho, J. E. Hopcroft and J. D. Ullman,
3639</span><span style="font-size: 10pt"><i>The Design and Analysis of Computer Algorithms,
3640</i></span><span style="font-size: 10pt">Addison-Wesley, Reading, Mass. 1974.
3641</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3642<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3643<span style="font-size: 10pt">14.    B. W. Kernighan and D. M. Ritchie,
3644</span><span style="font-size: 10pt"><i>The C Programming Language,
3645</i></span><span style="font-size: 10pt">Prentice-Hall, Englewood Cliffs, New Jersey 1978.
3646</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3647<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3648<span style="font-size: 10pt">15.    W. M. Waite,
3649&lsquo;The cost of lexical analysis,&rsquo;
3650</span><span style="font-size: 10pt"><i>Softw. Pract. Exp.,
3651</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>16</b></span><span style="font-size: 10pt">,
3652(5),
3653473-488 (1986).
3654</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3655<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3656<span style="font-size: 10pt">16.    C. W. Fraser,
3657&lsquo;A generalized text editor,&rsquo;
3658</span><span style="font-size: 10pt"><i>Comm. ACM,
3659</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>23</b></span><span style="font-size: 10pt">,
3660(3),
3661154-158 (1980).
3662</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3663<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3664<span style="font-size: 10pt">17.    R. Pike,
3665&lsquo;Graphics in overlapping bitmap layers,&rsquo;
3666</span><span style="font-size: 10pt"><i>ACM Trans. on Graph.,
3667</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>2</b></span><span style="font-size: 10pt">,
3668(2)
3669135-160 (1983).
3670</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3671<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3672<span style="font-size: 10pt">18.    L. J. Guibas and J. Stolfi,
3673&lsquo;A language for bitmap manipulation,&rsquo;
3674</span><span style="font-size: 10pt"><i>ACM Trans. on Graph.,
3675</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>1</b></span><span style="font-size: 10pt">,
3676(3),
3677191-214 (1982).
3678</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3679<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3680<span style="font-size: 10pt">19.    R. Pike, B. Locanthi and J. Reiser,
3681&lsquo;Hardware/software trade-offs for bitmap graphics on the Blit,&rsquo;
3682</span><span style="font-size: 10pt"><i>Softw. Pract. Exp.,
3683</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>15</b></span><span style="font-size: 10pt">,
3684(2),
3685131-151 (1985).
3686</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3687<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3688<span style="font-size: 10pt">20.    T. A. Cargill,
3689&lsquo;The feel of Pi,&rsquo;
3690</span><span style="font-size: 10pt"><i>Winter USENIX Conference Proceedings,
3691Denver 1986,
3692</i></span><span style="font-size: 10pt">62-71,
3693USENIX Assoc., El Cerrito, CA.
3694</span></p><p style="margin-top: 0; margin-bottom: 0.05in"></p>
3695<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: justify;">
3696<span style="font-size: 10pt">21.    G. J. Holzmann,
3697&lsquo;Tracing protocols,&rsquo;
3698</span><span style="font-size: 10pt"><i>AT&amp;T Tech. J.,
3699</i></span><span style="font-size: 10pt"></span><span style="font-size: 10pt"><b>64</b></span><span style="font-size: 10pt">,
3700(10),
37012413-2434 (1985).
3702</span></p><p style="margin-top: 0; margin-bottom: 0.50in"></p>
3703</body>
3704</html>
3705
3706