コンパイラの楽しみ - ケーブルの幾何設計

コンピュータはほとんど全ての仕事に使える汎用ツールですが、 この汎用性の起源は用途に合ったプログラムが書けることにあります。 しかし、何故か、多くのコンピュータの商用 OS(Operating System)には、 ユーザ自身がプログラムを作成するためのコンパイラ(Compliler) が無かったり、 コンパイラ作成ツール(compiler generator)がなかったりするため、 コンピュータを使うというのは アプリケーション(プログラム)を動かすことと誤解している人も多く、 この理解では創造的な仕事ができないし、当然、競争力も生まれません。 楽しみも感動も得られない、つまらない世界で生きることになります。

一方、Unixの場合はシンプルなコマンドをパイプライン(pipe line)や リダイレクト(redirect)で組み合わせて使う発想を含めて、システムそのものが、 利用者自身がプログラミングすることを前提にしています。 そのため、当初から全利用者が使うマニュアルの１章(Section 1)に yacc(parser generator)と lex(lexical analyzeri generator)が含まれていました。 (注１)

仕事のほとんどには言語で記述できる条件、目標、 作業手順などが含まれますから、 コンピュータのプログラミング言語を実現するためのコンパイラ技術は 日常業務のプログラミングにも使えますし、 しかも極めて有力な手法の一つになります。

V7 Unix が広く使えるようになった 1979 年だと マニュアル、論文、Unix の source code だけが教材でしたが、 それから 40 年後の今では yacc や lex の解説書もたくさん生まれました。 しかし、それらの教材には電卓など 簡単なプログラム言語の処理系の実現例といったものしかなくて、 仕事の現場で使った実例がありません。 始めてコンパイラ技術を学ぶ学生さんの教材としては、それでも良いかもしれませんが、 実務の現場で働く人々にとっては、 自分には無縁の技術と早とちりする可能性が高いと思いますし、 現行の教材で学んだ学生さんたちも同様の結末になるのではないでしょうか。

ここでは、 一般のコンピュータ利用者にコンパイラ技術の有効性を実感していただくために、 ユーザーが自分自身の仕事のために専用言語を設計し、 それを解析して実務を自動化する プログラムを書く手法を、 私自身が電線製造業現役経営者時代に使った事例をもとに解説しようと思います。

1. ケーブルの幾何設計と作図問題

電線としてのケーブルの構造決定問題を考えます。

例えば、左図は 7 本の絶縁導体(insulated conductor)と 8 本の同軸ケーブル(coaxial cable)を２層に撚合わせ、 加工中の形崩れを防ぐためのバインダ(binder)と呼ぶテープを巻き付けた後、 編組シールド(braided shield)と ジャケット(jacket)をかぶせたケーブルの１例です。

中心には１層目の 5 本の絶縁導体の形崩れを防ぐための 介在(filler)が入っています。 介在は繊維を使うのが普通です。 絶縁導体は直径 0.1 mm の軟銅線 50 本を集合機(buncher)で撚合わせ、 1.7 mm のプラスチック被覆で絶縁性を確保し、 同軸ケーブルは 0.1 mm の軟銅線 7 本に外径 1.2 mm の誘電体被覆の上に 0.1 mm 軟銅線の横巻(serve)で外部導体を構成し、 1.9 mm の外部保護被覆(jacket)をかぶせたものです。

この断面図に含まれる円の直径は、 それぞれの絶縁導体に要求される電気的機械的条件で決まりますから、 中心座標(coordinate of center)を求めれば作図可能で、 その中心座標をどうやって求めるかを考えてみてください。 比較的簡単な構造ですが、 中心座標を決定すべき円は 772 個になります。

撚合わせたケーブルの素線断面は円ではなくて、 高精度の計算では微分幾何学(differential geometry)が必要になりますが、 撚ピッチが極めて小さい場合以外は、 円近似で間に合います。

この場合、 素線の外径が等しい場合は座標計算も中学レベルの三角関数で間に合いますが、 外径が異なる素線が混在する場合はコンピュータによる数値計算が必要です。 しかも、幾何学的最小外径配置が電気的機械的最適にならない場合があります。

複数の絶縁導体を含むケーブルのほとんどは円形断面になっていて、 撚合わせ加工(twisting)と被覆加工(covering)を使って製造します。 撚合わせ加工には空間曲線の捻れを考慮した撚機(twisting machine)と、 複数の軟銅線などを集めて強引に捻ってしまう集合機(bunching machine) の二種類があって、 後者は素線の層構成と配列順序を考えなくて済みます。

撚機は直線状の素線を螺旋(helix)に変形して、 ロープ状にする装置ですが、 撚方向には素線の捩率(tortion)の正負により、 Z 撚(right-hand lay)とS 撚(left-hand lay)の２種類があって、 通常は撚機の撚方向を層毎に反転する普通撚を使いますので、 他の層に入り込むもことはなく、各層の外接円は円で近似できます。

被覆加工には樹脂被覆などで使われる押出加工(extrusion)、 組み紐機械を使う編組加工(brading)、 テープ、糸、軟銅線などの被覆で使われる巻き付け加工(serving)などがありますが、 いずれも同心円配置ですから、位置計算は容易です。

ケーブルの仕上外径(overall diameter)は素材の配置の仕方によって変わりますから、 設計時点で仕上外径を最小にする配置を見出さなければなりませんが、 有限数学(discrete mathematics)の円の詰め込み問題と考えると、 かなり難しい問題なります。

しかし、製造に必要な撚機という製造条件に着目すれば、絶縁導体の

 1) 層順(layer) - どの層に入れるか
 2) 撚順(order) - 層内配置をどうするか

それでもなお、この２つを完全自動で決定するのは難しい仕事ですから、 1), 2) は人が決めてみることにして、 その結果いかなる幾何学的配置になるか を計算し作図するシステムの実現を考えます。 つまり、とりあえず配置を決めてみて作図し、 その結果を見て配置を修正する作業の繰り返しで 最適解に近付こうというアプローチです。

2. ケーブルの構造記述言語とコンパイラ

導体、絶縁体、介在、バインダーなどのケーブル材料をELEMENT、 ケーブルの撚工程で使われる素線をcore(芯)と呼ぶことにすると、 撚合わされたケーブルもまた core になり得ますから、 数式に見られるような再帰的(recursive)構造になります。

絶縁体や編組などの被覆構造(covering)を

  '*' ELEMENT

  '(' core [ '+' core ] ')'

  '*' '(' core [ '+' core ] ')'

%token ELEMENT '(' ')'
%left  '+' '*'
%%
cable	:
	| core
	;
core	: ELEMENT
	| core '*' ELEMENT
	| core '*' '(' core ')'
	| core '+' ELEMENT
	| core '+' '(' core ')'
	| '(' core ')'
	;
%%

実際のプログラムとしては、 多様な ELEMENT に対応するための字句解析(lexical analyzer)、 エラー処理の構文や core の中心座標などを求める構文認識時のアクションが必要ですし、 細部の構造を記述する構文や、より簡単なフラットケーブル(flat cable) の組み込みも必要ですが、 たったこれだけで円形ケーブル(round cable)のいかなる構造にも対応できるのが 再帰構造の面白いところです。

例えば、前記のケーブル図面は、 この方針で作成したプログラムに入力した下記のデータから描かれたものです。

#1 50/0.10*1.7
#2 7/0.10*1.20*?/0.10*1.9
(#1^5-%)*(#2^3+#1+#2^2+#1+#2^3+#1)*.05t*?/?/.12*1t

こういった全ての ELEMENT の中心座標は 撚の内層から外側に向けて順次計算してゆくプログラムを書くことで決定できて、 その結果を元に作図も自動化できます。 通常のCAD(Computer Aided Design/Drafting)と呼ばれるプログラムでは、 人間が図形の寸法と位置をコンピュータに入力してゆきますが、 この仕事だけでも人材派遣業界が生まれるほど、 大変な労力を必要とします。

一方、ケーブル構造を記述する言語を設計し、 そのコンパイラを作成するという手法だと、 人間の仕事は配置順を決めるだけで済みますから、 大幅な省力化ができて、しかも、 図面の画像データの保存が不要ですから、 コンピュータに必要な記憶容量も激減します。

なお、実用的なプログラムの場合は、 個々の ELEMENT の寸法に加えて材料記述を追加して材料計算を行い、 さらに、加工条件を追加して、 原価計算や日程計算情報を作成したりします。

以下、この方法で作ったプログラムを体験するための、 簡単なデモを付けておきます。

ケーブル構造の記述法については c0プログラム教科書を見てください。 テキストボックスに構造記述式を入力し、 Drawをクリックすると構文を解析し、仕上外径(O.D)を描画します。 BOM(Bills of materials)をチェックすると部品表を追加し、 MASY(main assembly)をチェックすると撚組立図を描画します。

ここで動かしているプログラム自体は Unix の X11 で動くもので、 材料の面積、重量などを計算したり、 画像データの作成などもできるのですが、 ここではごく簡単な作図機能のみ動かしています。

3. 注

3.1. 注１ - Unix の Commands

例えば、V7 Unixの MANUAL では Section 1 Commands の最後が yacc になっていて、 「Commands are programs intended to be invoked directly by the user」が Commands の定義です。 Section 2 以下は Section 6 Games を除いて基本的にプログラマやシステム管理者が必要とする情報になります。

yacc(yet another compiler compiler)はBNF(Backus-Naur Form) 形式で記述された文法に基づく構文解析プログラムを 自動生成するプログラムです。 lex(lexical analyzer)は正規表現(regular expression) で規定できる文字パターンを識別する 字句解析プログラム(lexical analyzer)を自動生成するプログラムです。

V7 Unix の MANUAL VOLUME 2 には詳しい解説論文

  Stephen C. Johnson,- Yacc: Yet Another Compiler-Compiler
	(July 31, 1978)

  M.E.Lesk and E.Schmidt,- Lex - A Lexical Analyzer Generator

当初 Unix の記述に使われた Ritchie による最初の C コンパイラでは 式の構文解析に演算子順位法(operator precedance grammar)、 その他の部分に再帰下降構文解析(recursive descent parsing)が使われていましたが、 Version 7 Unix 以降は Johnson による移植性のよい PCC (Portable C Compiler) が使われました。 この PCC で使われたのが yacc です。

また、手軽に使える汎用プログラミング言語awkや、 文書整形システムroffの数式処理を引き受けるプログラム eqnでもyaccが使われています。 当時のawkはyaccとlexで書かれていましたが、 今のone-true-awkでは字句解析部分を lex から c に置き換えています。