An incomplete history of the
QED Text Editor

Dennis Ritchie

The text editors ed and vi, still much-used on Unix systems and elsewhere, have a long history, some bits of which are recounted here.
現在でも Unix やその他のシステムで良く使われている、 テキストエディターの edvi は長い歴史を持っていますが、 そのうちのいくつかをここで紹介します。

The QED text editor was first written by Butler Lampson and Peter Deutsch for the Berkeley time-sharing system on the SDS 940; see their paper in C. ACM 10 #12 (December, 1967).
最初の QED テキストエディターは Butler Lampson と Peter Deutsch によって SDS 940 で稼働する Berkeley time-sharing system の上で書かれました; C. ACM 10 #12 (December, 1967) の論文を参照してください。

Ken Thompson used this QED at Berkeley before he came to Bell Labs, and among the first things he did on arriving was to write a new version for the MIT CTSS system. Written in IBM 7090 assembly language, it differed from the Berkeley version most notably in introducing regular expressions for specifying strings to seek within the document being edited, and to specify a substring for which a substitution should be made. Until that time, text editors could search for a literal string, and substitute for one, but not specify more general strings.
Ken Thompson はベル研究所に来る以前にこの QED を使っており、 彼が到着するまでに行なった最初の仕事の中には MIT の CTSS システムのための新しいバージョンを書くことも含まれていました。 IBM 7090 のアセンブリ言語で書かれたこのバージョンは 特に編集しているドキュメントを検索する文字列や 置き換えられるべき文字列の指定に正規表現が導入された点で Berkeley のバージョンとは異なっていました。 その当時のテキストエディターは 文字通りの文字列を探索すること、 また1つの文字列を置き換えることしかできず、 より一般的な文字列を指定することはできませんでした。

Ken not only introduced a new idea, he found an inventive implementation: on-the-fly compiling. Ken's QED compiled machine code for each regular expression that created a NDFA (non-deterministic finite automaton) to do the search. He published this in C. ACM 11 #6, and also received a patent for the technique: US Patent #3568156. (Who said you couldn't get a software patent until recently?)
Ken は新しいアイデアを導入しただけでなく、 on-the-fly compiling という創造性のある実装方法も見つけました。 Ken の QED は 探索を行うための NDFA (non-deterministic finite automaton) (非決定性有限オートマトン) を作成する正規表現を個別に機械コードへコンパイルしました。 彼は C. ACM 11 #6 でこれを発表し、 さらに、この技術の特許を取得しました: US Patent #3568156. (「ごく最近までソフトウェアで特許を取れなかった」なんて誰がいいました?)

While the Berkeley QED was character-oriented, the CTSS version was line-oriented. Ken's CTSS qed adopted from the Berkeley one the notion of multiple buffers to edit several files simultaneously and to move and copy text among them, and also the idea of executing a given buffer as editor commands, thus providing programmability. (TECO, which grew into Emacs, was approximately contemporaneous or just a bit later, and elaborated these ideas independently).
Berkeley の QED がキャラクタ指向だったのに対し、 CTSS バージョンはライン指向でした。 Ken の CTSS qed は Berkeley バージョンから、 いくつかのファイルを同時に編集し、 かつそれらの中のテキストを移動/コピーさせる 多重バッファーの概念や、 与えられたバッファをエディタコマンドとして 実行するアイデアを取り入れてましたので、 プログラミングが可能でした。 (のちに Emacs となる TECO とほぼ同時期か、多少遅れていましたが、 この精巧なアイデアは独自に考え出されたものです)

CTSS was used at Bell Labs as part of our participation in the Multics project, and as Ken began to use Multics, he wrote yet another version of QED for that system. This one was in BCPL, and instead of compiling to machine code, regular expressions were represented as trees that were interpreted by the editor. However, the basic technique of simulating an NDFA was still used.
CTSS は我々の Multics プロジェクトへの参加の一環としてベル研究所で使用されました。 そして Ken が Multics を使い始めた時、 このシステムのためのもう一つのバージョンの QED を書きました。 これは BCPL で書かれたもので、 正規表現は 機械コードにコンパイルする代わりに、 エディターによって解釈されるツリー構造として表現されました。 しかしながら NDFA をシミュレートする基本的な技術はそのまま使用されました。

During the same period (ca. 1967), I arrived at Bell Labs, and fairly soon thereafter the company began withdrawing from Multics. Unix was at first nonexistent and then embryonic, and the main computation resource was GE-TSS, GE's time-sharing system for GECOS. I liked QED, and so set out to write a version of it for this system. This, like Ken's CTSS QED, was written in assembly language and compiled its regular expressions to machine code.
この時期に(1967年頃)、 私はベル研究所に来ましたが、 その直後から会社は Multics からの撤退を開始しました。 Unix も最初は存在せず、その後もごく初期のものでしたので、 主な計算機リソースは GE の GECOS のためのタイムシェアリングシステムである GE-TSS でした。 私は QED が好きでしたので、 このシステムのためのバージョンを書き始めました。 これは Ken の CTSS QED のようにアセンブリ言語で書かれ、 正規表現を機械コードにコンパイルしました。

This version was described in an internal technical memo, which is obtainable either in a slightly cut-down HTML browsable format, or reproduced as a scanned (and big: 1.1MB) PDF image.
このバージョンは内部の技術メモに解説されており、 ややカットダウンした HTML フォーマットと スキャナーを使って再現した (1.1MBの大きさの) PDF イメージのいずれでも入手可能です。

I wrote some incomplete notes of this QED's internal workings. This was intended to be a published paper, but was never finished.
私はこの QED の 内部動作 に関する完全でないノートを書きました。 これは論文として発表するつもりでしたが、 完成していません。

This QED was probably the most baroque and complicated of all its manifestations, particularly in pushing "regular expressions" well beyond what Kleene thought they should do. Other and later offspring of QED and its predecessors kept the central ideas, but were considerably simpler.
この QED は恐らく 最も過度に装飾されたもので、 特に Kleene が行うべきであると考えたことを越えて 「正規表現」が出しゃばるので、 その全貌を明らかにするのは困難でした。 QED の他のバージョンや後の子孫、 あるいはその前身においても、 この中心的なアイデアは守られましたが、 もっと単純なものでした。

For a brief period in the 1970s, the GECOS QED served us as a scripting language; it was in some ways analogous to the Awk or Perl of today. It was used for such tasks as submitting batch jobs, formatting files for the printer, collecting statistics on a file. A collection of macros to do various useful tasks was put in a commonly available place.
概ね 1970 年代を通して、 GECOS QED はスクリプトを書く言語として役立ち、 今日の awk や Perl と類似した方法でした。 統計をファイルに集めるたり、 バッチジョブを起動したり、 プリンタのためのファイルをフォーマットするといった 仕事に使用されました。 いろいろ有用な仕事をするマクロのコレクションが 一般に利用可能な場所に置かれました。

By 1974, Jay Michlin at Bell Labs wrote a version approximating this rendition for the IBM TSO system, and it was used at the Labs locations using IBM hardware and software. It seems that this version (or perhaps another reimplementation) was released: I have the first few pages of a document, courtesy of Joshua Ryan, that were used as "TSO Short Course Notes" at University of Missouri--Columbia. These discuss BQED, "an editor developed at Bell Labs.... BQED actually has fewer general-purpose commands than EDIT.... many of these concisely-stated commands cannot be performed by the other editors." (Ryan's UMC notes also talk about an apparently unrelated QED, for "Quick Edit").
1974年に、ベル研究所の Jay Michlin が IBM の TSO システムのために これに良く似たバージョンを書き、 IBM のハードウェアとソフトウェアを使用している研究室において使用されました。 このバージョン (あるいはおそらくもう一つの実装例) がリリースされたようです: 私は Joshua Ryan の好意で、 University of Missouri--Columbia の "TSO Short Course Notes" として使用されたドキュメントの最初の数ページを持っています。 これらは BQED について議論しています。 「ベル研究所で開発されていたエディター.... BQED は現実に EDIT より少数の汎用のコマンドしかありません.... このような簡潔なコマンドの多くは 他のエディターがコマンドを実行することができません。」 (Ryan の UMC のノートでは、さらに 見たところでは無関係な QED; "Quick Edit" について解説しています)


Offspring

The "standard Unix editor" ed was first written by Ken Thompson for the PDP-7. It kept the basic text-line orientation, but radically simplified the regular expressions to include only the *operator: no alternation, no parentheses. Where my QED embraced much of the context-free languages, this version could not even express all regular languages. It was not much of a loss.
「Unix の標準エディタ」である ed は 最初に PDP-7 のために Ken Thompson によって書かれました。 これは基本的にテキストのライン指向を維持していますが、 * オペレーターしか含まれない 徹底的に簡略化された正規表現で、 置き換えや括弧もありませんがありませんでした。 多くの文脈自由の言語の含む私の QED では、 このバージョンはすべての一般的な言語を表現できませんでしたが、 ロスは多くありませんでした。

Similarly, Ken's Unix ed ditched the notion of multiple buffers and of execution of buffers. Subsequent versions of ed for Unix (now written in C) began to add back some of the complexity (e.g. back-referencing in "regular" expressions, which now didn't quite include all the regular languages nor context-free languages, but did intrude a bit on the context-sensitive languages.)
同様に、 Ken の Unix ed は多重バッファーやバッファーの実行の概念を捨てました。 Unix の ed の (現在 C の中で書かれている) 後のバージョンは、 複雑な実装のいくつかを付け加え始めました。 (例えば「規則的な」表現 (それらは今全くすべての規則的な言語を含んでいるとは限らなかった) で後ろに参照を付けること、および、文脈自由の言語、しかし文脈依存の言語にビットを侵入した)

Subsequent developments along this line include vi, done mostly by Bill Joy at UC Berkeley. The advance here was essentially to adapt the command-set of ed to a screen-editor format; instead of doing things on (possibly virtual) paper on a typewriter, vi keeps a current view of a piece of a document on the screen, while commands are typed on the bottom line. Keeping a constantly updated window on a part of the text being edited is now, of course, completely standard and accepted. The same program, under the name ex, works better on typewriter-like terminals; aside from some fancier commands and better diagnostics, it's essentially ed.
このラインに沿った後の開発はほとんどUCバークレーでの紙幣喜びによって終わって、viを含んでいます。ここの進歩は本質的にスクリーン・エディタフォーマットにedのコマンドセットを適応させることでした;タイプライターの紙上の(恐らく仮想)物事を行う代わりに、コマンドが最終結果上にタイプされている一方、viはスクリーン上で1個のドキュメントの現在の視界を維持します。編集されているテキストの一部上で絶えず最新のウィンドウを維持することは、今もちろん完全にあります、標準、また受理しました。同じプログラムは、名前exの下で、タイプライター状のターミナルに、よりよく作用します;いくつかの空想家コマンドおよびよりよい診断学に加えて、それは本質的にedです。

The current local state of the QED line of descent is exemplified by sam, by Rob Pike (see his "The Text Editor sam," in Software -- Practice and Experience 17 #11, Nov. 1987). It's available for FTP in both Unix and Windows versions; search for "sam editor" on netlib. Sam offers cut-and-paste, mouse-and-menu editing on its text windows together with a command window, the language of which is drawn from the QED line of descent.
家柄のQEDラインの現在のローカルの状態はロブ槍(参照、彼の「テキストエディターsam」、ソフトウェアの中で――実行、また17#11、1987年11月を粂 @ o験する)によってsamによって例証されます。それは、Unixおよびウインドウズ・バージョンの両方の中のFTPに利用可能です;netlibの上の「samエディター」を捜してください。サムはカットおよび貼り付け(コマンド・ウィンドウ(家柄のQEDラインからその言語は取り出される)と一緒にそのテキスト・ウィンドウ上で編集するマウスおよびメニュー)を提示します。

The current implementation of regular expressions in Bell Labs research software uses algorithms close to those in Ken's CTSS and Multics versions, particularly the latter, because they don't try to compile to machine code. They have been elaborated somewhat in that they deal with a very large character set (Unicode), but they keep both the classical set of operators (*, |, concatenation, grouping for parentheses) and the NDFA simulation. We've done some fairly elaborate versions of grep that construct DFAs dynamically on demand, use Boyer-Moore techniques for fast searching of fixed strings, and so on. In the end simple and solid seems best.
ベル研究所の中の正規表現の現在のインプリメンテーション、ソフトウェアを研究する、それらがコンパイルしようとしないので、特に後であるというケンのCTSSおよびMulticsバージョンの中のものに近いアルゴリズムを使用する、機械コードに。それらは多少非常に大きな文字セット(Unicode)に対処する際に入念に作られました、しかし、それらは、オペレーター(*、|、括弧のためにグループ化する連結)の古典的セットおよびNDFAシミュレーションの両方を維持します。私たちはいくらか適正にしました、DFAをダイナミックに構築するgrepのバージョンを入念に作る、オンデマンド、固定ストリングを速く探索するためにボアイエ=ムア技術などを使用します。結局、単純で固体、最良に見えます。

Going back to the 1970s, QED had other offspring. Bob Daley wrote an editor called qedx in PL/1 for the Multics project. See, for example, Tom Van Vleck's encyclopedic discussion of Multics things (this pointer being to things beginning with Q). The tart comments about the rebarbativeness of QED as a scripting language are on the mark, though I don't think that Emacs is all that much better.
1970年代に戻って、QEDは他の結果を持っていました。ボブ・デーリーは、Multicsプロジェクト用のPL/1でqedxと呼ばれるエディターに手紙を書きました。(例えば)トム・ヴァンVleckの百科全書的な議論を参照してください。Multics事態(事態にQから始まることであるこのポインター)の。Emacsはよりよくその多くすべてではないと私は思いますが、スクリプトを書く言語としてのQEDの嫌な性質に関する酸味のコメントは、マーク上にあります。

A traditional (and maybe the nicest) version of QED was done at the University of Toronto by Tom Duff, Rob Pike, Hugh Redelmeier, and David Tilbrook; it supports multiple buffers, execution of buffers, and regular expressions with back-referencing. A more recent Canadian version, also a traditional-style descendant, is Fred, from Thinkage Ltd. It, like various earlier versions, is available for Honeywell GCOS systems and is still used as a scripting language as well as a line-editor for TTY-like communications interfaces.
QEDの従来の(恐らく最もよい)バージョンは、トムまんじゅう、ロブ槍、ヒューRedelmeierおよびデービッドTilbrookによってトロント大学で終わりました;それは多数のバッファー、バッファーの実行および後部に参照を付けることを備えた正規表現を支??オます。より最近のカナダのバージョン(さらに従来のスタイルの子孫)はThinkage株式会社から、フレッドです。それは様々な初期のバージョンのように、ハネウェルGCOSシステムに利用可能で、TTY状のコミュニケーション・インターフェースのためのラインエディターとしてもスクリプトを書く言語としてもまだ使用されます。