「文字列の終端はなぜヌルなのか 」を考察する
Advent Calendarの最終日に寄せて(?)、終端文字の話をします。
文字列の終端文字について
終端がヌルの文字列、いわゆる ヌル終端文字列 ですが、終端文字がヌル文字('\0')なのは何故でしょうか。
他の文字でも良かったんじゃないの?と考えたことはありませんか。
文字列の持ち方
そもそも、文字列の持ち方には、初期のコンピュータでは主に2種類の方式がありました(今はもっといろいろあると思いますが)。
- その2種類とは、
- '\0'で終わる文字列、すなわちヌル終端文字列で、 **ASCIIZ** あるいは『 **C文字列** 』と呼ばれる
- 先頭に文字列長を1バイトで配置する文字列で、『 **Pascal文字列** 』とよばれる
"Hello,"というリテラルを例にとると、
C文字列では
H | e | l | l | o | , | \0 |
Pascal文字列では
6 | H | e | l | l | o | , |
となります。 |
それぞれの方式には、一長一短があります。
文字列長の取得
C文字列は、先頭から1文字ずつ見ていく必要があり計算量は文字列の長さに比例してO(n)だが、文字列長には制限がない。
Pascal文字列では、先頭1バイトだけ見れば良いので計算量はO(1)で済むが、文字列長は1バイトで表現可能な255文字までに制限される。
文字列の連結
"Hello,"+"World."を例に取ると、
(連結した文字列を格納するメモリ領域の確保は同じ手間がかかるとして)
C文字列は文字列を続けて書き込むだけで済む。
H | e | l | l | o | , | \0 |
と |
W | o | r | l | d | . | \0 |
から |
|||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|H|e|l|l|o|,|W|o|r|l|d|.|\n|
Pascal文字列では文字列を続けて書き込んだ上で先頭の文字列長を書き換える必要がある。
6 | H | e | l | l | o | , |
と |
6 | W | o | r | l | d | . |
から |
||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|12|H|e|l|l|o|,|W|o|r|l|d|.|
C文字列とPascal文字列のどちらが優れているかを断言することは難しいと思いますが、UNIXという優れたOSと一心同体であることとハードウェアの性能をフルに引き出しやすいC言語が普及し、結果としてC文字列の方がより広い範囲で使われるようになったのは事実だと思います。
終端文字になぜヌル文字を選んだか
ヌル終端文字列の起源は、 PDP-11 (DECが1970年に販売開始した"ミニ"コンピュータ。ミニというのは汎用の大型コンピュータに対する相対サイズのことで、今となっては十分デカい)のマクロアセンブリ言語であるMACRO-10の仕様に .ASCIZディレクティブ として導入されたこととされているようです( ヌル終端文字列 )。
では、なぜ MACRO-10 の設計者は .ASCIZディレクティブ を定義する際に終端文字に'\0'を選択したのでしょうか。これは、PDP-11の命令セットアーキテクチャから見ると、ごく合理的な選択であったことを明らかにしたいと思います。
PDP-11のアセンブリソースを読む
PDP-11の命令セットアーキテクチャを見るには、PDP-11のアセンブリ言語で書かれたソースを読むのが一番ということで、さっそく見てみましょう。
PDP-11よりソースコードを引用させていただきました。
.TITLE HELLO WORLD
.MCALL .TTYOUT,.EXIT
HELLO:: MOV #MSG,R1 ;STARTING ADDRESS OF STRING
1$: MOVB (R1)+,R0 ;FETCH NEXT CHARACTER
BEQ DONE ;IF ZERO, EXIT LOOP
.TTYOUT ;OTHERWISE PRINT IT
BR 1$ ;REPEAT LOOP
DONE: .EXIT
MSG: .ASCIZ /Hello, world!/
.END HELLO
この当時のコンピュータとしては、驚くほど読みやすい、きれいなアセンブリ言語仕様です。行きがかり上、PDP-11の前身の PDP-8 (1965年製造開始)のアセンブリ言語仕様も見てみたのですが、命令の種類とメモリアクセス方法がまだ整理されておらず、読んでいてつらいです。アポロ誘導コンピュータ(アポロ11号)のアセンブリ言語も同様です。1960年代半ばまでは、こんなものだったのでしょう。
それがPDP-11では大きく改善されており、その直交性の高い命令セットにより、ほとんど現在のCPUのアセンブリ言語と同じ感覚で読むことができます。
- ざっくりコメントすると、
- MOV #MSG,R1 により"MSG"というラベル付けしたアドレスをR1レジスタに代入する
- (ループ開始)
- MOVB (R1)+,R0 によりR1レジスタが指すアドレスから1バイト読み込んでR0レジスタに代入する (同時にR1はインクリメンされる) MOV(B)インストラクションの仕様として、読み込んだ値が0なら演算の結果としてZフラグが立つ
- BEQ DONE により、Zフラグが立っていたら"DONE"ラベルまでジャンプ(条件分岐)して終了する(ループから抜ける)
- .TTYOUTディレクティブ によりR0レジスタの文字が出力される
- BR 1\$ により1$ラベルまでジャンプする(ループの先頭に戻る)
上のループで使われている
- 演算の結果を ステータスレジスタ に出力する(ここでは、ゼロなら汎用レジスタの中のZフラグを立てる)
- ステータスレジスタの状態により条件分岐する(ここでは、Zフラグの状態によりジャンプする)
という動作は、CPU共通の基本設計であり、インテル系( x86 )やモトローラ系、日本製の H-8 (ルネサスエレクトロニクス)、今をときめく ARM 系のCPUでも同様です。
ここで大事なのは、初期のコンピュータの貧弱な処理能力では、少しでも処理を軽くする必要性に迫られていたと言うことです。
PDP-11の MOV(B) では、所定アドレスの値をレジスタに読み込むだけで値がゼロかそれ以外かを判別できています( PDP-11命令一覧表 )。つまり、0という値を特別な値とすることにより 「特定の数値と比較する」というステップ(処理)を省略できているところがポイント です。
CPUの命令とサイクル
初期の貧弱なコンピュータでプログラムを書いていたアセンブラプログラマは、命令を実行するのに必要なサイクル数を数えながらプログラミングをしていました。
例えば、条件分岐を行うには、
- アキュムレータ というCPUの中でも特別なレジスタに値を読み込んでから、
- 数値との比較なり論理演算を行ってステータスレジスタを更新し、
- 条件分岐命令を実行します。
この単純な流れであっても、サイクル数を削るのに心を砕くのです。
私は、アセンブラに関しては、NECの PC-6001 (1981年発売)に採用されている Z-80 (ザイログ社開発の8bit CPU) が母語ですので、この事情をZ-80アセンブラで説明します。
Z-80は、8bitレジスタはA,B,C,D,E,H,Lの7本です(正確には、補助レジスタ(裏レジスタとも言う)があります)。このうち、論理演算や数値演算に使えるアキュムレータは、Aレジスタです。
『高級』言語によるプログラミングしか経験がないプログラマは、レジスタが変数に相当すると思ってください(そのうち式に書けるのは1個だけ)。想像を絶する窮屈さですね。
さて、ある領域の値をシーケンシャルにAレジスタに読ませて処理を実行して行くには、
- 16ビットレジスタにアドレスを設定してAレジスタに読ませ、
- なにがしかの処理を実行し、
- 16ビットレジスタをインクリメント
していくことになります。
Aレジスタに16ビットレジスタの値を読み込ませるには、次の命令があります。
それぞれの命令には、サイクル数も添えます。
参照資料 8ビット CPU Z80命令セット
LD A,(HL) ;サイクル数 7 (BC,DEも同様)
LD A,(IX+d) ;サイクル数 19 (IYも同様)
CPUが命令を実行する時間は、CPUのクロック数とこのサイクル数で決まります(厳密には、割り込みなども発生するのでそう単純ではありませんが)。ざっくり言うと、サイクル数が2倍なら命令を実行する時間も2倍になります。
サイクル数が大きいIXやIYでオフセット値dを利用するのは、各種変数のプール領域とでも言うべきワーク領域を参照する場合に限られます。
次に、Aレジスタの値を判定する方法には、次の命令があります。
LD r,n ;サイクル数 7 rは任意のレジスタ、nは任意の1バイトの値
CP r ;サイクル数 4 rは任意のレジスタ
;合計サイクル数 11
CP n ;サイクル数 7 nは任意の1バイトの値
1つめの方法は、上述したようにZ-80には8bitレジスタは7本しかないのでrの土地代は高く、rにn(ここでは0)を読み込む時間も余分にかかるので採用はしないでしょう。
従って、CP n とするしか方法がないように思えます。
しかし、判定したいバイト値が0である場合に限定して、
OR A ;サイクル数 4
という、アキュムレータ自身で論理演算を行ってステータスレジスタを更新するというテクニックが使えるのです。
余分なレジスタを使う必要はなく、CP n よりも速く判定ができる、合理的な方法と言えます。
Z-80以外のCPUも、同じようなテクニックがあるのではないでしょうか。
私が現役Z80プログラマのときは、ヌル文字に限らず0判定の常套句として書いていました。
「値がゼロであることの判定」は、「値が特定の数値であることの判定」よりも軽い。
CPUの命令セットアーキテクチャにとって ゼロは特別な値 なのです。
さて、上のPDP-11のサンプルソースを、Z-80アセンブラで書くと、次のようになると思います。
;TTYOUTというサブルーチンが事前に定義されている前提
HELLO: LD HL,MSG ;文字列の開始位置をセット
LOOP: LD A,(HL) ;バイト値をAレジスタに読み込む
INC HL ;1バイト次へ
OR A ;0であることを判定
JR Z,DONE ;0ならループを抜ける
CALL TTYOUT ;Aレジスタの内容を出力
JR LOOP ;ループ
DONE: RET ;HELLOの呼び出し元に返る
MSG: DB 'Hello, world!',00H
C言語とPDP-11
ここまで、PDP-11が終端文字にヌルを採用したことの合理性を書いてきました。
「そして、PDP-11の.ASCIZは、C言語のC文字列として継承されたのでした(めでたしめでたし)」と言いたいところですが・・実はそうではないようなのです。
別途、会社の同僚が調べてくれたのですが、Cの前身のB言語の時点で、PDP-11とは関係ないところで終端文字にヌルを採用したようなのです(Bのさらに前身のBCPLでは文字列長を保持していた)。
興味がある人は、
The Development of the C Language
The Most Expensive One-byte Mistake
を読んでみてください。
いろいろ言われているようですが、C文字列の終端文字にヌルを採用したことは、実行速度という観点では悪くない選択だったと思います。
PDP-11だけでなく他のCPU上のアセンブラプログラマが高級言語に移行する際にC言語を支持したのは、システムレイヤーに近いC言語の設計思想に依るところが大きかったと思います(80年代前半までは、C言語は「高級アセンブラ」と呼ばれていた)。
C文字列は、結果的にはC言語のそんな思想にマッチしているのではないでしょうか。
終端
C文字列は、C言語から派生した言語群(C++,C#。JAVAにも)に受け継がれています。
初期に誰かが考えたアイデアが連綿と受け継がれていくところは、自然言語で言うと日本語が漢字を受け継いでいるような歴史のロマンを感じます。
というわけで、メリークリスマス!
おしまい。
参考文献
ヌル終端文字列
https://ja.wikipedia.org/wiki/%E3%83%8C%E3%83%AB%E7%B5%82%E7%AB%AF%E6%96%87%E5%AD%97%E5%88%97
PDP-11
https://ja.wikipedia.org/wiki/PDP-11
PDP-11命令一覧表
http://www.nak.ics.keio.ac.jp/class/asm/t11/opcode.pdf
8ビット CPU Z80命令セット
http://www.yamamo10.jp/yamamoto/comp/Z80/instructions/index.php
The Development of the C Language
http://csapp.cs.cmu.edu/3e/docs/chistory.html
The Most Expensive One-byte Mistake
http://queue.acm.org/detail.cfm?id=2010365