• 木村 泉、米澤 明憲, 1982: 算法表現論 (岩波講座 情報科学 12)。岩波書店, 282 pp.

1982年に出た A5判 横書きのハードカバー。岩波書店は、文科系・理科系にわたるさまざまな専門分野について、「講座」とよばれるシリーズの本をだしている。専門分野内のおおぜいの分担執筆で、分野全体をみわたそうとするものだ。大学院生や学者になったばかりの人の勉強や、学者の知識の更新、また、大学の図書となって学生が参照することなどが想定されていただろう。この「情報科学」の講座の初刷りは、全巻予約購入が原則だったが、最初に発売された2巻はバラ売りもしていて、出版は番号順ではなく、本書は2番めに出たので、バラ売りで買えた、と記憶している。第2刷りは全部バラ売りになった。

わたしは、大学4年生のときから、数値計算をするために Fortran をつかう必要があったが、Fortran の教科書の例文はわかりにくかった。『プログラム書法』という本があって、既存の教科書の例文を添削する形で、Fortran で見とおしのよいプログラムをかく方法をしめしていた。また、Fortran の変種である Ratfor というプログラム言語をつかう機会があった。その言語は Software Tools という本で提示されていた。その本は、Ratforで書かれたプログラムを Fortran に翻訳する前処理系 (pre-processor) があることを前提としながら、その前処理系を自分でつくることができるような技法をおしえるものだった。わたしがその本を英語で読みおわったころ、日本語版『ソフトウェア作法』が出た。訳者は『プログラム書法』と同じ 木村 泉 さんだった。

『算法表現論』の著者名に木村さんの名まえがあがっていたので、わたしはとびついたのだった。買ってみると、木村さんの執筆部分は全10章のうち第1章だけだった (長めの章ではあるが)。しかし、わたしにとってはそれだけでも価値があった。ずっと持っていたのだが、2019年に蔵書をへらしたときに古本屋さんに売ってしまった。2021年からプログラミングをおしえるたちばになったので、その参考にまた読んでおこうと思い、2023年11月に大学の　(東京のキャンパスの) 図書館にあったのを借りて読んだ。

米澤さんの執筆部分は、(数学者はそう思わないだろうが、わたしにとっては) 数学書のような感じだ。わたしは読みとおせていない。プログラム言語を、大きく「命令型」と「作用型」に分類し、両方を統一するモデルをつくって説明しようとしているが、どちらかというと「作用型」のほうが基本に近いと考えているらしい。わたしはこれを読んでしばらくこの用語をプログラム言語の標準的分類名だと思っていたが、他の文献には従来どおり「手続き型」と「関数型」をつかっているものがおおいようだ。わたしは、「手続き」ということばは、たとえば Pascal 言語の procedure をさすこともあるのでまぎらわしいと思い、「手順立て型」ということにしている。わたし自身のプログラム言語への理解は手順立て型にかぎられており、関数型やオブジェクト指向はいまもよくわからないままである。

米澤さんは「命令型」 (わたしのいう「手順立て型」) 言語の例として Pascal をつかっていて、その記述は (同じころに出版された) Pascal の教科書とほとんど同じだったので、その部分にかぎっては理解できた。

木村さんによる序章の趣旨は、米澤さんの執筆部分のような体系的記述がなぜ必要になったのかをしめす、というものだ。内容は、Kernighan & Plauger の訳書とは、まさに同工異曲、いわば「Kernighan & Plauger の主題による即興変奏曲」である。Ratfor 前処理系と似たしごとをするプログラムを、わざと旧式の Fortran でつくって、どのようにこまるかを実演してみせるのだ。これによってわかるのは、プログラム言語は「制御構造」を適切に表現できる形式をもつべきだということだ。旧式のプログラム言語は、計算機に対する命令を順にならべたうえで、そこに「どこどこに行け」という「go to 文」をまぜて構成されていた。その方法で書けるプログラムのほとんどは、順次処理、条件別処理、ループの 3つの基本的な制御構造で書きなおせる。Ratfor や Pascal は条件別処理やループの構文を明示することで、計算手順をわかりやすくした。(関連することを [別ブログ 2020-07-18 「go to」をめぐって] の第3–4節に書いた。)

しかし、これでおわりではない。(木村さんのいう)「データ抽象」の話がつづく。Pascal 言語には変数をいくつか組にしてまとめてあつかう機能があるけれども、それだけでは力不足だ。データとそれにアクセスする手続きをあわせたパッケージ化の機能がほしいのだ。(複数の人がつくった部品をあわせて動くプログラムをつくることをかんがえると、A氏による部品のなかのプログラムがB氏による部品の内部のデータを書きかえることができるのは危険だ。他の部品へのアクセスは、外に見せると約束したデータへのアクセスにかぎるべきだ。) 序章のおわりのほうに、このようなことができる言語として、Ada とか Clu のなまえがでてくるのだが、わたしにはどちらもつかう機会がなかった。のちに発達した C++ 言語の「クラス」機能がいくらかそれにちかいと思うが、「オブジェクト指向」と「データ抽象」とはちがうだろう。そのあたりの概念がわたしにはよくわかっていない。2020年代の「算法表現論」をどなたか書いてくださるとありがたい。

文献

• Brian W. Kernighan, P. J. Plauger, 初版 1974, 第2版 1978: The Elements of Programming Style. McGraw-Hill. [わたしは直接読んでいない。]
• Brian W. Kernighan, P.J. Plauger 著, 木村 泉 訳, 初版 1976, 第2版 1982: プログラム書法。共立出版。[わたしはこの両方の版を読んだ。] [読書メモ (2024-06-23)]
• Brian W. Kernighan, P. J. Plauger, 1976: Software Tools. Addison-Wesley. [わたしはこの版を読んだ。] [読書メモ (2024-08-18)]
• Brian W. Kernighan, P.J. Plauger 著, 木村 泉 訳, 1981: ソフトウェア作法。共立出版。[わたしはこの版も見たがよく読んでいない。]

折りかえしのあとに目次をつける。

===== 目次 =====
まえがき /木村、米澤
目次
第1章 序論 — アルゴリズムにおける具体と抽象 /木村
– 1. 例題
– 2. 素朴な解
– 3. 穴ふさぎ
– 4. 穴ふさぎの穴ふさぎ
– 5. スパゲッティの “構造化” ?
– 6. 擬似コードと前処理プログラム
– 7. データ抽象
– 8. 展望
第2章 算法表現の基礎 /米澤
– 1. プログラム言語論
– 2. 関数、算法、プログラム言語
– – (a) 数学的関数と算法
– – (b) プログラム言語と算法の基本性質
第3章 作用的算法表現の基礎
– 1. 再帰的関数
– – (a) 原始再帰法
– – (b) 同時再帰法
– – (c) 経過値再帰法と多重再帰法
– – (d) μ-作用素と探索
– – (e) Kleene の標準化定理と算法の標準形
– – (f) Ackermann 関数 — 一般再帰的関数
– 2. λ-算法
– – (a) λ-記法 と λ-抽象
– – (b) λ-式とその変換規則
– – (c) λ-式の評価と Church-Rosser 定理
– – (d) 数の表現
– – (e) 条件式、継続、繰返し、再帰
– – (f) 組合せ子
第4章 作用型算法言語
– 1. 作用的算法表現
– – (a) 作用的構造
– – (b) 関数定義と条件式
– – (c) 局所定義式と再帰的関数定義式
– – (d) 記号式とその関数
– – (e) 高階の関数と関数形式
– – (f) 自由変数と名前の束縛方式
– – (g) 万能評価関数とプログラム・データ
– – (h) 遅延評価法
– 2. 作用的データ表現
– – (a) データ型とその定義法
– – (b) 型の宣言
– – (c) 構造型データの演算と不変対象
– – (d) 枚挙型と関数データ型
– – (e) 直積型、直和型、列型
– – (f) 写像型と再帰的データ型
– – (g) 型の同値性と型多形態
第5章 命令型算法言語
– 1. 命令的表現の基礎
– – (a) 効果による計算
– – (b) 変数の意味
– – (c) 代入文
– – (d) 制御の流れ
– 2. 命令的データ構造
– – (a) 命令的データ
– – (b) レコード型と配列型
– – (c) ポインタ型
– 3. 命令的表現の構造化
– – (a) 手続きと関数
– – (b) 手続き、関数の情報受渡し機構
– – (c) 宣言とプログラムの構造
– – (e) ブロック構造とプログラムの論理構造
第6章 命令的表現の抽象化
– 1. データ、データ型の抽象化
– – (a) 抽象化に基づく方法論
– – (b) 抽象データ型
– – (c) 抽象データ型のための言語機構
– 2. 制御構造の抽象化
– – (a) 繰返しの抽象化とコルーチン
– – (b) 例外処理のモデル
– – (c) 例外処理のための言語機構
– 3. 抽象化に基づくプログラム言語
– – (a) 対象物
– – (b) 変数と対象物
– – (c) 代入文と引数受渡し機構
– – (d) 抽象化とプログラムの部品構造
第7章 非決定性と並列性の算法表現
– 1. 非決定性算法表現
– – (a) 非決定性の源
– – (b) 2種類の非決定性
– – (c) バックトラック
– 2. 並列性算法表現の基礎
– – (a) プロセス
– – (b) 相互独立プロセス
– – (c) 同期・更新するプロセス
– – (d) データ駆動型のプログラム実行
– 3. 同期表現
– – (a) 同期基本操作
– – (b) 同期表現の構造化
– – (c) 同期表現の抽象化に向けて
– – (d) 同期に関する諸問題
第8章 算法表現の統一モデル
– 1. 諸概念の統一
– – (a) 手続きとデータの統一
– – (b) データの流れと制御の流れの統一
– 2. 統一計算モデル
– – (a) actor と メッセージ
– – (b) 純 actor と 不純 actor
– – (c) actor 計算モデル
– – (d) actor の階層性とモジュール性
第9章 算法表現 (プログラム) の意味論
– 1. 算法言語の形式的意味記述
– – (a) 目的と方法
– – (b) 抽象構文
– – (c) 被定義言語
– – (d) 意味記述用インタプリタ
– 2. 操作的意味記述法
– – (a) 高階関数と抽象機械
– – (b) 高階関数の除去 (1) — apply の導入
– – (c) 高階関数の除去 (2) — 環境のデータ化
– – (d) 抽象機械の動作記述
– 3. 表示的意味記述法
– – (a) プログラムの意味と意味関数
– – (b) 表示的意味記述の例
– – (c) 数学的基礎付け
– – (d) 命令的表現の意味記述
第10章 算法表現 (プログラム) の証明論
– 1. プログラミングの公理論的基礎
– – (a) 目的と方法
– – (b) プログラマーの意図の表現
– – (c) 公理と推論規則
– – (d) プログラム (算法表現) の証明
– – (e) プログラムの停止性
– 2. 公理的意味記述法と完全性
– – (a) 公理的意味記述
– – (b) 手続きと goto 文の意味記述
– – (c) 不完全性と相対的完全性
– 3. 公理的方法の周辺
– – (a) プログラミングと公理的方法
– – (b) 言語設計と公理的方法
– – (c) 言語定義の 3方法
– – (d) その他の公理的方法
付録 BNF 記法
参考書
索引
==========