タグアーカイブ: 1980年代

マジックリスト構造を使用したテキストエディタの開発

テキストエディタの開発

テキストエディタの開発

テキストエディタのメモ発見

2017年12月、本棚を整理していたらキングファイルの中に「テキストエディタ仕様」というメモを発見しました。このメモは、コンピューターサービス株式会社のDESIGN SHEETに書かれています。

少し考えたら思い出しました。1980年ごろにCSKからＭ電器に派遣になったころに、休日にCSKの社員寮で書いたメモです。

M電器でリアルタイムシステム開発

ちょうどそのころ、CSK技術発表会で「スクリーン・エディタによる開発効率向上」について発表し最優秀賞を受賞しました。

CSK技術発表会で発表

ミニコンU-300でリアルタイムシステム開発

1980年ごろ、パナファコムのミニコンU-300のアセンブラで音声波形リアルタイム表示システムを開発してました。

ソースコードは紙カードにパンチして、カードリーダーから入力します。ビルド結果やソースリストは、ラインプリンターに印刷したものを見て机上デバッグします。私の知る範囲では、その当時のミニコンにはテキストエディタというツールがありませんでした。

現在(2017年)のWindowsで動作する統合システムツールから考えると、とても開発効率が悪いものでした。

紙カードをファイルに読み込んでファイルからビルドする方法がありました。記憶が曖昧ですが、バッチ処理で行(カード)を入れ替えるエディタ風の仕組みはあったような気がします。しかし、とても使えるものではありませんでした。

この開発プロジェクトでは、音声波形をリアルタイムに波形表示するためにミニコンU-300に高解像度のグラフィック・ディスプレイを接続していました。ミニコンによる開発効率を向上できないかと模索していた私は、CSK技術発表会で最優秀賞を受賞したスクリーン・エディタのようなものを作れないか考えていました。

ある日の休日、CSK社員寮でTK-80マイコン・ボードで試作したスクリーン・エディタで趣味のプログラミングをしながら、ミニコンの開発環境のことを検討してました。

試作したスクリーン・エディタは、スクリーン上の任意の位置にカーソルキーを移動して直接ソースコードを編集できました。しかし、開発プロジェクトで導入したグラフィック・ディスプレイは、画面の一番下の行がコマンド入力欄となっており、この位置でだけキー入力できました。

グラフィック表示が目的のディスプレイでしたので、テキストのスクロール機能もありません。テキストの表示は、ディスプレイ上をサイクリックに順々に表示するのが現実的です。

完全なスクリーン・エディタは無理だと思いましたが、行単位のポインタをもったテキストエディタなら作れそうと考えました。

テキストエディタの開発

次の週の日曜日に、テキストエディタのコマンド体系と実装方法を検討して先に示した4枚のメモを書きました。37年前に私が書いた技術メモが捨てずに残っていたことに感動です。当時はワープロなどという便利なツールはありませんでしたのですべて手書きです。当時からあまり綺麗な字を書いていないなと少し反省します。

音声波形リアルタイム表示システムの開発プロジェクトがユーザーインターフェイス設計に入ったころです。Ｍ電器の技術者と試作機を使用するユーザーとの間で仕様の打ち合わせが行われましたが、なかなか仕様や方向性が決まりませんでした。我々だけで暫定的に仕様を決めて見切り発車できず、開発プロジェクトが一時停滞しました。

この先の開発効率向上のために、この期間を利用して検討していたテキストエディタの開発に着手しました。ひとりで集中してコーディング・ビルド・デバッグすること数日間。自分がやりたいことだったので、通常の開発ペースよりもハイペースで開発を推進することができました。数日後には、高解像度のグラフィック・ディスプレイを使用したテキストエディタが動きました。高解像度のモニターなのでソースコードを30行程度表示することができ、ソースコードを眺めながらソースコードを修正できるテキストエディタが完成しました。

CSKの開発メンバーのHさんとYさんに、コマンド体系と操作方法を説明して使用してもらいました。音声波形リアルタイム表示システム開発は、このテキストエディタを使用することにより開発効率を上げることができたと思います。

テキストエディタの仕様

テキストエディタは、大学時代に使用した DEC System20 TOPS-20 で経験した程度です。

タイムシェアリング方式のコンピュータ

行単位のポインタをもつラインエディタで、修正する行にポインタを設定して行修正（挿入、削除、置換）を行います。コマンド体系としては、下記表に示す11種類のコマンドを実装することにしました。

  • 行単位のポインタをPTとします
  • mは行数で、省略は m=1
  • nは行位置で、省略は n=0
  • sとeは行数で、省略は s=0 , e=0
  • textは挿入・置換するテキスト
  • keyはキー文字列で、省略は 以前のkey
  • fはファイルの論理番号

 

分類 コマンド 意味 動作
移動 B[m] Backword PT後進 PT←PT－m
移動 F[m] Forword PT前進 PT←PT＋m
移動 L[n] Line PT設定 PT←n
表示 P[s][,e] Print PT－sからPT＋eの行を表示
行削除 D[s][,e] Delete PT－sからPT＋eの行を削除
行挿入 I text Insert PT行の直下にtextを挿入
行置換 R text Replase PT行をtextに置換
行検索 S[key] Search PT行からkeyを含む行を検索しあればPT設定
読み込み G f Get File PT行の直下にファイルfから挿入
終了 E End 編集を保存して終了
破棄 Q Quit 編集を破棄して終了

 

 

【行検索(Sコマンド)の補足】

検索文字列を指定するkeyは、文字列の前後を区切り記号で囲みます。文字列の中に区切り記号が出現すれば、任意の1文字を表すワイルドカードとなります。

コマンド 動作
S/ABC/ 文字列’ABC’を検索
S/A/C/ ‘A’の次に任意の1文字があり次に’C’がある文字列を検索
S@A@@Z@ ‘A’の次に任意の2文字があり次に’Z’がある文字列を検索

この仕様を決めたときはMS-DOSなど存在しませんが、ファイルのワイルドカード「?」みたいな働きをします。また、unixなどの経験があれば正規表現を採用しましたが、残念ながらその当時そんな知識はありませんでした。

 

テキストエディタの実装方法

最初はテキストをすべてメモリに読み込んで編集することを考えていました。ミニコンU-300は最大搭載メモリ容量が64KByteで開発用のマシンはもっと少なかったと思います。
最近(2017年)の64bit Windows10 HOME パソコンは、動作するための最低メモリ容量は2GBで、認識する最大メモリ容量は128GBだそうです。メモリ容量のスケールがまったく異なりますね。

使用メモリ量の制限からファイル上のレコードをリスト構造でつなぐ方針にしました。ファイルの中でカードイメージに対応したレコードを差し替えて編集するわけです。

実装方法を検討した際に、少ないメモリ容量で動作させるためにマジックリスト構造を採用しました。

テキストエディタの実装方法

テキストエディタの実装方法

 

最初に指定したソースファイルをランダムアクセス可能な編集用ファイルにロードします。

次に編集用ファイルを編集します。メモリ上にレコード番号とリンクポインタをペアにした配列を用意します。リンクポインタをリスト構造にすることにより、ポインタの入れ替えにより編集テキストの行を管理して編集します。

編集を終了するときに、リンクポインタをたどりながら編集用ファイルをランダムにアクセスして編集結果をセーブします。

テキストの削除は次のように行います。

リスト構造による削除

A→B→C→D の4行のテキストがあるとします。レコード1からレコード4に順々に格納して、リンクポインタで接続しています。
2行目のテキストBを削除する場合は、レコード1のリンクポインタを2→3に変更します。その結果、テキストAの次の行はテキストCとなり、A→C→D となりテキストBを削除しました。

テキストの挿入は次のように行います。

リスト構造による挿入

リスト構造による挿入

A→B→C→D の4行のテキストがあるとします。レコード1からレコード4に順々に格納して、リンクポインタで接続しています。
2行目の次にテキストEを挿入する場合は、レコードの空き領域のレコード5にテキストEを書き込み、レコード2のリンクポインタを3→5に変更し、レコード5のリンクポインタを0→3に変更します。その結果、テキストBの次の行はテキストEとなり、次の行はテキストCとなり、A→B→E→C→D となりテキストEを挿入しました。

リスト構造

リンクポインタでリスト構造を作ります。リスト構造には、単方向リスト構造と双方向リスト構造があり、今回は双方向リスト構造と同じ機構を少ないメモリ容量で実現するマジックリスト構造を採用しました。以下、順にリスト構造を説明します。

単方向リスト構造とは

リスト構造としてもっとも簡単な構造は、単方向リストです。

単方向リスト構造

単方向リスト構造

このリスト構造は、下記のセルで構成します。

  • DATAセル : データを格納
  • LINKセル : 後方のセルを指すポインタを格納

先頭はHEADセルで指し、LINKセルをたどることにより前方から後方に向かう一方通行のリスト構造となります。

双方向リスト構造とは

エディタで編集するときは、行ポインタを前方や後方に移動しますので、単方向リスト構造では適しません。前のデータも後ろのデータもたどれるようにした、双方向リスト構造が必要です。

双方向リスト構造

双方向リスト構造

このリスト構造は、下記のセルで構成します。

  • DATAセル : データを格納
  • LINK Fセル : 後方のセルを指すポインタを格納
  • LINK Bセル : 前方のセルを指すポインタを格納

先頭はHEADセルで指し、LINK Fセルをたどることにより前方から後方に向かうリスト構造となります。
末尾はTAILセルで示し、LINK Bセルをたどることにより後方から前方に向かうリスト構造となります。

DATAセル, LINK Fセル, LINK Bセルにそれぞれ16bitを割り付けると、1要素が6バイトの容量となります。最大5000要素のリスト構造とすると、6×5000＝30000バイトとなり約30キロバイトが必要です。
もっとメモリ容量を節約する方法はないでしょうか？

マジックリスト構造とは

双方向リスト構造と同じように、前のデータも後ろのデータもたどれてメモリ容量がもっと少なくなるリスト構造はないでしょうか？

共立出版社から出版されたコンピュータ・サイエンス bit誌のマジックリスト構造について書かれたある記事を思い出しました。1980年当時は、bit誌を本棚に入れて保存していました。その記事をもう一度読むために、過去6年分のバックナンバーを読み返してマジックリスト構造を探しました。

マジックリスト構造

マジックリスト構造

マジックリスト構造は、下記のセルで構成します。

  • DATAセル : データを格納
  • LINKセル : 後方／前方のセルを指すポインタ生成する情報を格納

具体例を Address A03の要素について考えてみます。LINKセルは、次の要素を指すA04 と前の要素を指すA02の排他的論理和(EXclusive OR)の演算結果を格納します。

ひとつ前の要素A02 が既知であれば、ひとつ後ろの要素を求めることができます。また、ひとつ後ろの要素A04 が既知であれば、ひとつ前の要素を求めることができます。

既知 説明 算出式 結果
前A02 A03次の要素算出 A02 EXOR (A02 EXOR A04) → A04
後A04 A03前の要素算出 A04 EXOR (A02 EXOR A04) → A02

 

 

排他的論理和の真理値表を下記に示します。

入力A 入力B 出力
0 0 0
0 1 1
1 0 1
1 1 0

 

マジックリスト構造は、単方向リストと同じメモリ使用量で双方向リストを実現できます。

DATAセル、LINKセルにそれぞれ16bitを割り付けると、1要素が4バイトの容量となります。最大5000要素のリスト構造とすると、4×5000＝20000バイトとなり約20キロバイトで実現できます。

マジックリスト構造は、排他的論理和の性質を利用したすご技ですね。メモリ節約が必要だった時代のテクニックですが、知っていれば何かの役に立つかと思います。