ニクラウス・ヴィルト 「アルゴリズム＋データ構造＝プログラム」 とSmalltalk
ニクラウス・ヴィルトの古典的名著
「アルゴリズム＋データ構造＝プログラム」
日本コンピュータ協会 刊
を読んだ。名著だというのに何十年も積読本だった。もう古本屋でないと手に入らないかもしれない。
ところで繰り返しますがこの本のタイトルは「アルゴリズム＋データ構造＝プログラム」。この本のカバーだけにタイトル以外のPASCALという文字が入っている。カバー以外にはこの本のどこにもPASCALという表題はない。しかしこのカバーの文字のためにこの本がPASCALの教本だと勘違いする人がいる。つまり私だ。当然ながらこの本でPASCALについてはPASCAL構文グラフ一覧が載っているだけでPASCALについては一言も書かれていない。純粋にプログラム自体に関する本です。
結局PASCALは昔Turb Pascalで勉強して、ひたすらソースコードを読んで覚えた。そのためこの本はついつい積読本になってしまった。いやいや大好きなヴィルト教授、申し訳ない。
この本は配列やツリー構造などのデータ構造に応じたアクセス方法を論じ、それらを一方通行の順ファイル上にまで拡げている。さらにそれらのデータを扱うアルゴリズムの特にソートに関する数学的な効率を可能な限り追及している。最後にこの本で述べてきたことを使ってPL0というコンパイラを作ってみせています。
内容的にはさすがやや古いところもありますが、データ構造を詳細に検討して順ファイル上まできっちりと展開しているのはさすが古典と言われるだけあります。データが大量になった場合、現在でも通じるテーマなんですよね。ソートの種類とサンプルばかり追っかけた言語のありきたりな解説本などとはやはり一線を画する本です。当然ながらお勧めできる本です。
せっかく読んだので何か練習をしてみようと思った。そこで前から覚えようと思っていたSmalltalkの学習をかねて、この本の中でPascalで記述されているPL0コンパイラをSmaltalkで書き換えてみようと思いました。初めてのSmalltalkプログラムになります。
使用したSmalltalkは
VisualWorksの無料版。
参考書には
青木 淳「Smalltalk イディオム」ソフト・リサーチ・センター刊
のみ。後VisualWorksのマニュアルとネットでウィキペディアのSmalltalkの項を読みました。
性格の違う言語のプログラムを変換する作業にはふたつ考えられます。変換先、この場合smaltalkの考え方に従って変換元、Pascalのプログラムの内容を考えて設計しなおしてから最初からsmaltalkのプログラムを書く。もうひとつは、変換元のPascalのプログラムの構造も形式もなるべく変えずに変換先のSmaltalkの構文や書式のみを借りてきて変換する。最初のやり方はすでに変換元の言語Smaltalkに十分わかられている人に向く。まったくの初心者で最初のプログラム書きの人には、つまり私の場合は後者のやり方でいきました。プロの人も変換の仕事が来ると後者の方法をとります。コストを考えたら当然。変換仕事は安いですからね。
結論を先に言いますと、再帰呼び出ししているところで作業を止めました。Pascalは内部手続きや内部関数をサポートしていて、変数も入れ子状に有効範囲が幾重にもはめ込まれています。このPascalのPL0コンパイラのプログラムもたくさん内部手続きや入れ子の内部変数を使っています。それに対してSmalltalkは、再帰呼び出しはできても変数はインスタンス変数にしてもシェア変数にしても一種のグローバル変数です。メッセージを送るだけの単純な考え方で面白いのですが、基本的にオブジェクトのやり取りで、オブジェクトは参照が基本です。コール・バイ・バリューやコール・バイ・リファレンスを厳密に分ける引数という考え方もありません。単なる構文の移し替え作業をしていたので、再帰呼び出しのようなケースで変数の有効範囲を厳密に管理するのには無理がありすぎます。Smalltalkの考え方に合わして再設計が必要だと気付いたのでやめました。変換作業は結構時間を食ったので、もっと最初に気づけよという感じです。
愚痴ついでに変換作業の感想を少し書いてみます。
「Smalltalk イディオム」とVisualWorksのマニュアル
この両書はあまり教育的とはいいがたい。「教育的でない」とは、説明すべきことをその言葉以外で記述してしない、同語反復をしているという意味です。例えばある名前の変数を、クラスの複数のインスタンス(生成物)の個々で有効な変数である場合とクラス全体で1個の変数として有効な変数、つまり複数のクラス・インスタンスで1個として認識される変数の違いがあって、一方は同じ名前に別々の値が代入できて一方は代入するとすべてのインスタンスで同じ値として読めてしまうと説明してから使用すべきインスタンスの項で、そんな違いは当たり前というばかりにいきなりインスタンスの作り方、記述の仕方の説明で始まります。どのメニューを、ダイアログを使うとか、instanceVariableNames:やclassInstanceVariableNames:の後ろに追加して定義しろとかなんとか。その他使用方法のみが記述される等々。説明して欲しい項でいきなりその項の名前ばかり出てこられても困ります。これがいたるところで繰り返されます。ただし意味のない文章というわけではない。マニュアルなんかも昨今のHTML式マニュアルのようにあってもなくても同じという状況の中でよく頑張って作ってあります。もう一押し。「Smalltalk イディオム」も内容は結構広い範囲をカバーしていて話題も豊富、なかなかいいのですが、とても初学者向きじゃありません。
VisualWorksの統合環境も分かっている人には使いやすいでしょうが、タブで切り替えられてソースコードを書くので窓口しか見えずちょいとわかりづらい。うっかりカテゴリを入れ忘れると無所属のところに登録されたりしてゴミが出たりと、慣れるのに少し時間がかかる。私はパッケージにヴィジュアル・ワークスのソースコードを落として、XMLファイルになっているものを直接読みました。こちらの方が全体をつかみやすい。
VWのエディターにはバカで本当に困りました。記述にエラーがあったり、そのとき統合環境がお勧めする次の処理が妥当なものでないときにうっかりキャンセルすると、なんとそのときまで書き続けていてまだ保存していない内容をすべて破棄してくれる。復活もできない。最悪１行書くごとにセーブしなければならない。「継続」ってのを押せばそのまま無視して保存してくれる場合もあるけれど、実にわかりづらい。
定数の初期値を設定するという所でもつまづきました。シェア変数のconstantフィールドをtrueにすればいいのですが、定数をパッケージに封じ込めない。シェア変数の初期化というメニュー・コマンドを実行して手動で初期化文字列を入力すると「変数の定数化」ができるのだけれども、どうも初期化文字列を別のところにバイナリ形式でで保存しているらしい(まだ未確認)。ともかくパーケージと同じファイルに初期化文字列が格納されてくれないとポータビリティが悪すぎる。仕方ないので変更できないという、定数化をあきらめてインスタンスの初期化メソッド内で初期化した。変更できてしまうならシェア変数にする必要はないのでインスタンス変数でも構わないのだけれども、よくわからない初期化の方法がわかった時のためにそのままにしました。initializeメソッドを発信すればいいとか、マニュアルのここの部分の記述は省略が多くて、実にわかりづらい。これもパッケージ・ファイルのXML文を読んで判断しました。
PASCALコード側で困ったのはchar型の定義。数字文字をそのまま配列インデックスに使うように文字そのものを配列インデックスに使っているのですが、char型がASCIIコード配列じゃない。まるで順番の違う使い方をしているうえに、
'=<' '=>' '<>'
のようにASCIIなら２文字のなるところを
'≦' '≧=' '≠'
のような１文字として扱っている。これをそのまま１バイト配列インデックスとして扱っているので当然２バイトと1バイトの混合した文字を数値化するように変更しなければいけない。本にはご丁寧にもASCIIコード表を載せているいるけれども、この本のプログラムの中で実際に扱っているchar型のコード表は載っていない。確かに理論的にはどんなコード表に従っていてもプログラムは動くけれど、このままじゃ実際には動かない。ASCIIコードは1963年ごろの制定らしいし、この本は1976年発行だから主流はASCIIに移っていたはず。いったいどんなコードを使ったのか。どうもPASCAL専用のコード体系らしいのだけれど、私まだヴィルト教授の正式のPASCAL解説書って呼んだことないのでわかりません。ヴィルトのおっちゃん、学者さんやなあ。
goto文も終端に大きくジャンプしてくれるので大変。goto文の使用はわざとやったのではないかと推察。
勉強していて面白かったのは、Smalltalkじゃ制御構文も単なるメッセージ。だから構文も独自に拡張でできる。その点FORCEと似通っていて面白い。言語拡張するのにFORCEの方は構文自体を辞書化するという方法で行うけれども、星の数ほどメタ言語ができてしまうという副作用が起きる。酷いと元の言語仕様がわからなくなるほど見かけが変わる。これは始末が悪く、単純であるというのは意外に悩ましい。ですからメタ化というのはしてほしくない。わたしメタ化したタグ言語のような言語仕様、嫌いなんですよね。なぜって美しくないんですもの。
当然のごとく日本コンピュータ協会の本（誤訳/誤植で有名）は手に入らないでしょうから新訳で読んでください。
「アルゴリズム＋データ構造＝プログラム」
日本コンピュータ協会 刊
を読んだ。名著だというのに何十年も積読本だった。もう古本屋でないと手に入らないかもしれない。
ところで繰り返しますがこの本のタイトルは「アルゴリズム＋データ構造＝プログラム」。この本のカバーだけにタイトル以外のPASCALという文字が入っている。カバー以外にはこの本のどこにもPASCALという表題はない。しかしこのカバーの文字のためにこの本がPASCALの教本だと勘違いする人がいる。つまり私だ。当然ながらこの本でPASCALについてはPASCAL構文グラフ一覧が載っているだけでPASCALについては一言も書かれていない。純粋にプログラム自体に関する本です。
結局PASCALは昔Turb Pascalで勉強して、ひたすらソースコードを読んで覚えた。そのためこの本はついつい積読本になってしまった。いやいや大好きなヴィルト教授、申し訳ない。
この本は配列やツリー構造などのデータ構造に応じたアクセス方法を論じ、それらを一方通行の順ファイル上にまで拡げている。さらにそれらのデータを扱うアルゴリズムの特にソートに関する数学的な効率を可能な限り追及している。最後にこの本で述べてきたことを使ってPL0というコンパイラを作ってみせています。
内容的にはさすがやや古いところもありますが、データ構造を詳細に検討して順ファイル上まできっちりと展開しているのはさすが古典と言われるだけあります。データが大量になった場合、現在でも通じるテーマなんですよね。ソートの種類とサンプルばかり追っかけた言語のありきたりな解説本などとはやはり一線を画する本です。当然ながらお勧めできる本です。
せっかく読んだので何か練習をしてみようと思った。そこで前から覚えようと思っていたSmalltalkの学習をかねて、この本の中でPascalで記述されているPL0コンパイラをSmaltalkで書き換えてみようと思いました。初めてのSmalltalkプログラムになります。
使用したSmalltalkは
VisualWorksの無料版。
参考書には
青木 淳「Smalltalk イディオム」ソフト・リサーチ・センター刊
のみ。後VisualWorksのマニュアルとネットでウィキペディアのSmalltalkの項を読みました。
性格の違う言語のプログラムを変換する作業にはふたつ考えられます。変換先、この場合smaltalkの考え方に従って変換元、Pascalのプログラムの内容を考えて設計しなおしてから最初からsmaltalkのプログラムを書く。もうひとつは、変換元のPascalのプログラムの構造も形式もなるべく変えずに変換先のSmaltalkの構文や書式のみを借りてきて変換する。最初のやり方はすでに変換元の言語Smaltalkに十分わかられている人に向く。まったくの初心者で最初のプログラム書きの人には、つまり私の場合は後者のやり方でいきました。プロの人も変換の仕事が来ると後者の方法をとります。コストを考えたら当然。変換仕事は安いですからね。
結論を先に言いますと、再帰呼び出ししているところで作業を止めました。Pascalは内部手続きや内部関数をサポートしていて、変数も入れ子状に有効範囲が幾重にもはめ込まれています。このPascalのPL0コンパイラのプログラムもたくさん内部手続きや入れ子の内部変数を使っています。それに対してSmalltalkは、再帰呼び出しはできても変数はインスタンス変数にしてもシェア変数にしても一種のグローバル変数です。メッセージを送るだけの単純な考え方で面白いのですが、基本的にオブジェクトのやり取りで、オブジェクトは参照が基本です。コール・バイ・バリューやコール・バイ・リファレンスを厳密に分ける引数という考え方もありません。単なる構文の移し替え作業をしていたので、再帰呼び出しのようなケースで変数の有効範囲を厳密に管理するのには無理がありすぎます。Smalltalkの考え方に合わして再設計が必要だと気付いたのでやめました。変換作業は結構時間を食ったので、もっと最初に気づけよという感じです。
愚痴ついでに変換作業の感想を少し書いてみます。
「Smalltalk イディオム」とVisualWorksのマニュアル
この両書はあまり教育的とはいいがたい。「教育的でない」とは、説明すべきことをその言葉以外で記述してしない、同語反復をしているという意味です。例えばある名前の変数を、クラスの複数のインスタンス(生成物)の個々で有効な変数である場合とクラス全体で1個の変数として有効な変数、つまり複数のクラス・インスタンスで1個として認識される変数の違いがあって、一方は同じ名前に別々の値が代入できて一方は代入するとすべてのインスタンスで同じ値として読めてしまうと説明してから使用すべきインスタンスの項で、そんな違いは当たり前というばかりにいきなりインスタンスの作り方、記述の仕方の説明で始まります。どのメニューを、ダイアログを使うとか、instanceVariableNames:やclassInstanceVariableNames:の後ろに追加して定義しろとかなんとか。その他使用方法のみが記述される等々。説明して欲しい項でいきなりその項の名前ばかり出てこられても困ります。これがいたるところで繰り返されます。ただし意味のない文章というわけではない。マニュアルなんかも昨今のHTML式マニュアルのようにあってもなくても同じという状況の中でよく頑張って作ってあります。もう一押し。「Smalltalk イディオム」も内容は結構広い範囲をカバーしていて話題も豊富、なかなかいいのですが、とても初学者向きじゃありません。
VisualWorksの統合環境も分かっている人には使いやすいでしょうが、タブで切り替えられてソースコードを書くので窓口しか見えずちょいとわかりづらい。うっかりカテゴリを入れ忘れると無所属のところに登録されたりしてゴミが出たりと、慣れるのに少し時間がかかる。私はパッケージにヴィジュアル・ワークスのソースコードを落として、XMLファイルになっているものを直接読みました。こちらの方が全体をつかみやすい。
VWのエディターにはバカで本当に困りました。記述にエラーがあったり、そのとき統合環境がお勧めする次の処理が妥当なものでないときにうっかりキャンセルすると、なんとそのときまで書き続けていてまだ保存していない内容をすべて破棄してくれる。復活もできない。最悪１行書くごとにセーブしなければならない。「継続」ってのを押せばそのまま無視して保存してくれる場合もあるけれど、実にわかりづらい。
定数の初期値を設定するという所でもつまづきました。シェア変数のconstantフィールドをtrueにすればいいのですが、定数をパッケージに封じ込めない。シェア変数の初期化というメニュー・コマンドを実行して手動で初期化文字列を入力すると「変数の定数化」ができるのだけれども、どうも初期化文字列を別のところにバイナリ形式でで保存しているらしい(まだ未確認)。ともかくパーケージと同じファイルに初期化文字列が格納されてくれないとポータビリティが悪すぎる。仕方ないので変更できないという、定数化をあきらめてインスタンスの初期化メソッド内で初期化した。変更できてしまうならシェア変数にする必要はないのでインスタンス変数でも構わないのだけれども、よくわからない初期化の方法がわかった時のためにそのままにしました。initializeメソッドを発信すればいいとか、マニュアルのここの部分の記述は省略が多くて、実にわかりづらい。これもパッケージ・ファイルのXML文を読んで判断しました。
PASCALコード側で困ったのはchar型の定義。数字文字をそのまま配列インデックスに使うように文字そのものを配列インデックスに使っているのですが、char型がASCIIコード配列じゃない。まるで順番の違う使い方をしているうえに、
'=<' '=>' '<>'
のようにASCIIなら２文字のなるところを
'≦' '≧=' '≠'
のような１文字として扱っている。これをそのまま１バイト配列インデックスとして扱っているので当然２バイトと1バイトの混合した文字を数値化するように変更しなければいけない。本にはご丁寧にもASCIIコード表を載せているいるけれども、この本のプログラムの中で実際に扱っているchar型のコード表は載っていない。確かに理論的にはどんなコード表に従っていてもプログラムは動くけれど、このままじゃ実際には動かない。ASCIIコードは1963年ごろの制定らしいし、この本は1976年発行だから主流はASCIIに移っていたはず。いったいどんなコードを使ったのか。どうもPASCAL専用のコード体系らしいのだけれど、私まだヴィルト教授の正式のPASCAL解説書って呼んだことないのでわかりません。ヴィルトのおっちゃん、学者さんやなあ。
goto文も終端に大きくジャンプしてくれるので大変。goto文の使用はわざとやったのではないかと推察。
勉強していて面白かったのは、Smalltalkじゃ制御構文も単なるメッセージ。だから構文も独自に拡張でできる。その点FORCEと似通っていて面白い。言語拡張するのにFORCEの方は構文自体を辞書化するという方法で行うけれども、星の数ほどメタ言語ができてしまうという副作用が起きる。酷いと元の言語仕様がわからなくなるほど見かけが変わる。これは始末が悪く、単純であるというのは意外に悩ましい。ですからメタ化というのはしてほしくない。わたしメタ化したタグ言語のような言語仕様、嫌いなんですよね。なぜって美しくないんですもの。
当然のごとく日本コンピュータ協会の本（誤訳/誤植で有名）は手に入らないでしょうから新訳で読んでください。
"ニクラウス・ヴィルト 「アルゴリズム＋データ構造＝プログラム」 とSmalltalk" へのコメントを書く