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