「素人の初心者がオブジェクト指向プログラミングをちょっとだけ調べてみた」 2023年1月14日版 著者：dhrname 1, はじめに 　オブジェクト指向プログラミングとは「構造化プログラミング（Structured Programming）」である。 　1960年代後半に、科学者たちが「オブジェクト（object）」、「クラス（class）」、「サブクラス（subclass）」、「不変 (不変量、不変条件、invariant)」などのアイデアをヨーロッパで提唱した。また、オランダのダイクストラは、数学者Th.J.Dekkerの理論から、65年に「Communication of the ACM volume 8」で並列処理の「メッセージ（message)」を提唱した。そして、68年にはマルチプログラミング の「階層構造 (hierarchical structure) 」を提唱した。 　ダイクストラと、イギリスのホーア、クラスを提唱したノルウェーのダールの三人がそれらのアイデアを定義して、1972年に、一冊の本にまとめた。その本『構造化プログラミング』第一部で、ダイクストラは、制御構造を不変（不変量、不変条件、 invariant）と結びつけ、「抽象 (抽象化、abstraction)と型 (type)」の関係に言及した。構造化プログラミング第二部で、ホーアは、制御構造と、「直積（カルテシアン積、カルテジアン積、cartesian product）型」や「再帰データ型」などの「データ構造化 (データ構造、date structure) 」との対応付けをした。そのうえで、彼らは、構造化プログラミング第三部で、ダイクストラが提唱した構造化プログラミングの「階層構造」と、SIMULA67言語のクラスプログラミングを結びつけた。さらに、ホーアは、クラスプログラミングを利用して、離散事象シミュレーション (Discrete Event Simulation, DES)と「セマフォ (semaphore)」を関連付けた。 　また、71年、ダイクストラの階層構造を研究していたパルナスは「情報隠蔽 (information hiding)」を発表した。これがリスコフのデータ隠蔽、ストラウストラップのカプセル化の研究に発展していった。 　この科学理論を念頭に置いて、上半分が複数の仮想の機械で、下半分が複数の物理の機械で、数珠つなぎでプログラミングすることを、「構造化プログラミング」、あるいは「オブジェクト指向プログラミング」と呼ぶ。 　1975年、日本で、ダイクストラらの「構造化プログラミング」を翻訳した書籍が、サイエンス社から出版された。その中で、オブジェクトは「対象」、サブクラスは「部分クラス」、インスタンスは「実例」と訳されている。例えば、「構造化プログラミング」の本文(1)を引用してみよう。 特殊な実例(instance)が集まったクラス(class)なのである。いい換えると、動的システムに現れる現象を、現象のクラスとしてひとまとめにし、それぞれのクラスをプログラム部分として記述しようというのである。 （「構造化プログラミング」199ページより引用） 存在し続けるブロックの実例のもとになる手続きをクラス(class)という。そして、その実例をそのクラスの対象(object)という。 （「構造化プログラミング」202ページより引用） G5 :- new Gauss(5); G7 :- new Gauss(7); …… G5.integral(F, A, B) …… G7.integral(F, A, B) ……（中略）手続き integralが対象の外部から何度も使われることを想定している。 （「構造化プログラミング」207ページより引用） find: if x = val then this tree （中略） findの本体の中に現れる表現 　this tree は、そのときに扱っている節、すなわち所属物 find の、この特定の実例を所有している参照を値としようとするものである。たとえば、Xの手続き find が関数呼び出し 　X.find(x) で呼び出され、X.val = xであると、関数の値はX自身を指す参照値である。 （「構造化プログラミング」218ページより引用） "truck", "bus", "car"は、クラスvehicleの部分クラス(subclass)と考えてよいであろう。 （「構造化プログラミング」228ページより引用） 　以降は各々この訳語に従う。 　また、この記事では、C言語の「structure」を「構造化カルテシアン積」もしくは、「構造化体」と訳すことにする。 　本記事では、題名のとおり、オブジェクト指向プログラミングの興味深い成り立ちと理論について調べたことを整理してみる。読者のプログラミング技術の助けになれば幸いである。 　まず、第2章では、1957年から1994年までの歴史を振り返る。これにより、オブジェクト指向プログラミングがさまざまな基礎研究を土台にしていることを示す。 　第3章では、「構造化」の概念を使って、対象とクラスの定義をする。構造化プログラミングであるクラスとコルティン（コルーチン）を使って、ダイクストラが指摘した手続きとサブルーチンの問題点を考える。1975年に日本語に翻訳された「構造化プログラミング」(1)と1979年に翻訳された「アルゴリズム+データ構造=プログラム」（4）の二冊を主な参考資料として使う。 　第4章では、SIMULA ⅠとSmallTalk72の二つのプログラミング言語が、SIMULA67とは別の系統であることを示す。 　第5章では、第2章から第4章まで述べたことをまとめていく。反省し、課題を見つける。 　注意点として、 -氏名の敬称は略す。 -長くなりそうなので、本記事を数回に分ける。 -訳書や絶版をもっぱら使う（本来ならば、原文や最新研究をあたるべきと言う意味で、「ちょっとだけ調べてみた」） -独自解釈となる -私はプログラミングと数学と論理学と数学基礎論とORとCSと電子工学と物理学の初心者であるので、以下のことを知らないし、質問や反論されても回答できない。 -べき集合やカルテシアン積（直積）など集合全般 -ルベーグ積分や重積分など数学解析全般 -ボレル集合体やσ-集合体、ポアソン過程 (Poisson process)、マルコフ連鎖、離散時間と連続時間を含む確率過程(stochastic process)全般 -待ち行列ネットワーク、BCMP網 -待ち行列ネットワークを用いて、バッチ処理などのマルチプログラミング多重度の性能評価をすること -並行処理と並列処理の違い -離散事象ネットワーク -クライアント・サーバ方式などの通信 -チャーチ・チューリングの提唱やラムダ計算やライスの定理や一般帰納的部分関数など計算論全般 -グラフ理論と（一般）帰納的関数の関係 -表示的意味論（スコットの領域理論）と公理的意味論、Plotkinの操作的意味論などプログラム意味論全般 -圏論（カルテシアン閉圏CCCや、mogiの計算効果とモナド、タングル圏など） -順序機械（逐次機械、シーケンシャル機械、sequencial machine)における、ブロックと分割、等価性、並列分解 (parallel decomposition) -プロセス代数とパイ計算 -ミュー計算 -原始帰納的関数とタプル（組）を使ったべき集合モデルや、プリンキピア・マセマティカ（数学原理）体系。ZFC公理系（プリンキピア・マセマティカ体系から導き出されるゲーデルの第一不完全定理を含めた数学基礎論として） -クラス論理や普遍代数学などの論理学全般 - ベーム-ヤコピーニの定理と、二部テープのチューリング機械と、二部グラフと、（非）決定性有限オートマトンと、順序機械の状態遷移関数 -ラッセルのプリンキピア・マセマティカ（数学原理） -プリンキピア・マセマティカ（数学原理）から発展した単純な型付きラムダ計算 -オランダの数学者、J・デッカーによる、並列処理のクリティカルセクション問題に関する証明 -タルスキ意味論 -部分型多相（subtyping polyphorism)など型システム -計算が停止しない計算、もしくは、計算が停止しない場合を含む計算を示すようなオブジェクト指向言語。すなわち、C++、Java、Ruby、JavaScript言語などで、while文や再帰呼び出し機構を使わずに、計算が停止しない計算を作ることができること -C言語の自己参照構造体で使われる不定型とポインタの違い -ML言語の型定義不能性 -if文などの条件分岐を、while文などの繰り返し文に置き換えることができること -while文などの繰り返し文を、goto文に置き換えることができること -ハミルトン閉路問題や、セールスマン巡回問題や、エイトクイーン問題における、効率が良い解決方法と、逐次処理が制限時間内に終了するかどうかを処理の実行前に判別する方法（ただし、この方法を使うと、例えば、ハミルトン閉路ではない有向グラフ、巡回不能、チェスのマスが少ない場合などは、有限時間内に計算が終わることはない。それ以外の場合は、有限時間内に効率よく終了する） -バイナリによるデータの内部表現 -ハイパーバイザ法 -シーケンス制御（順序制御、逐次制御、シーケンシャル制御、sequencial control）など制御工学 -数学の不変量 (invariant)や位相（トポロジー）、結び目理論 -シュレディンガーの箱の観察の解釈（ただし、放射性物質の崩壊->ガイガーカウンターの警報->箱を空けるの順序、逐次、因果関係となる）、ヤングの実験などの物理学 -超限帰納法（数学的帰納法の一般化）と整列集合 (well-ordered set)の切片 -数え上げの推論（科学的帰納法。数学でいうところの経験的事実、予想） -ダイクストラが提唱したソフトウェア検査技法 -ダイクストラ法（ダイクストラのアルゴリズム）と動的計画法 -分割統治法 -ダイクストラが提唱したガード節（guard command)と述語論理意味論 -自然演繹（カリー＝ハワード同型対応も含む） -有向非循環グラフ(閉路を持たないような有向グラフのこと。DAG)とフローグラフなどデータフロー解析全般 -代数的仕様 -ゲーデル不完全と、チューリング完全と、完備性、部分関数と、不完全定義関数（ブール代数） 以上の初歩的なことを読者は知っているものとして、話を進める。 -便宜上、二グループに分ける。 グループA　（プログラムで実装したとき、計算停止しないことを予期させるもの。ただし、必ずしも計算停止しないとは限らない） -計算停止しない場合を含む計算 -構造化プログラミング（オブジェクト指向プログラミング） -型なしラムダ計算 -単純な型付けラムダ計算の型付け -while文のみを使ったプログラミング -ジャンププログラム -並列処理（あるいは、マルチプログラミング） -有向グラフ -帰納的（再帰的、recursive） -確率過程 -待ち行列ネットワーク（ネットワークフローは重み付き有向グラフ） -数学的構造 -選出公理を含めたZFC公理系 -述語論理 -計算誤差のない数値解析 -IO入出力、通信、ゲーム、アニメーションや動画などの大規模かつ、複雑なプログラム -離散事象シミュレーション グループB　（計算停止することを予期させるもの） -オブジェクト指向（ケイによれば、1+2+3 = 6の場合、オブジェクトが1であり、メッセージが+2+3であり、6というresponseを返す） -β正規形を持つ単純な型付きラムダ計算（型の強正規化定理により、ラムダ式がβ正規形を持つならば、β正規形へとたどりつく） -β正規形を持ち、最左評価戦略をとる型なしラムダ計算（標準定理により、ラムダ式がβ正規形を持つならば、β正規形へとたどりつく） -自然演繹 -待ち行列ネットワーク（ただし、BCMP網） -型付け可能と証明器で証明されたlet多相（型推論） 準備 　ラムダ計算の文法に着目すれば、ラムダ計算は一つのゲーデル数で表すことができることを示す。 　例えば、λx.xというラムダ式があって、次のように文字ごとに自然数を割り振っていこう。ただし、空白は無視できるものとする。 λ - 1 x - 2 . - 3 ( - 4 ) - 5 　このとき、タプルa, bをという形で書けるのだとすると、λx.xは次のように書ける。 <<<λ, x>, .>, x> = <<<1, 2>, 3>, 2> 　このタプルを、次のゲーデル関数の一種である関数Gを使って、一つのゲーデル数に変換させる。 G(x, y) = ( (x+y) * (x+y+1) / 2) + x + 1) 　すなわち、G(G(G(1, 2), 3), 2)を計算すると、一つのゲーデル数が得られる。こうして得られたゲーデル数集合をゲーデル数型Geとみなす さて、つぎのような形無しラムダ計算とベータ簡約(->β)を与える。 (λx.x) λy.y ->β λy.y 　このベータ簡約を次のような単純な型付きラムダ計算へと変換する（ただし、Ge はゲーデル数型とする）。 λω.λy.y ( (λx.x) λy.y): Ge -> Ge 　しかるに、ゲーデル数の定義から、次のようなことが言える。 　任意の二つの形無しラムダ計算A, Bによるベータ簡約（A ->β B)から、ゲーデル数型の関数型（Ge -> Ge)が型付けできる単純な型付きラムダ（ (λω.B) A: Ge->Ge)へと変換できる (1.0) 　次に、β正規形を持たないラムダ計算について考えてみる。不動点コンビネータであるYコンビネータにYコンビネータを関数適用させると、すなわち、Y Y ->β Y (Y Y) は、(1.0)より、 ( λω.Y (Y Y) ) (Y Y): Ge -> Ge 　さらに、最左評価戦略を用いて、Y Yを繰り返し次のようにベータ簡約できる。 Y Y ->β Y (Y Y) ->β (Y Y) (Y (Y Y)) ->β (Y (Y Y)) (Y (Y Y)) 　Yコンビネータ自体にも自然数を割り振ると、(Y Y) (Y (Y Y))の式にも、(Y (Y Y)) (Y (Y Y))の式にも、両方とも関数Gを使って、一つのゲーデル数を求めることができる。そのため、結局、(1.0)より、 (λω.(Y Y) (Y (Y Y))) ( λω.Y (Y Y) ) (Y Y): (Ge -> Ge) -> Ge (λω. (Y (Y Y)) (Y (Y Y))) (λω.(Y Y) (Y (Y Y))) ( λω.Y (Y Y) ) (Y Y):( (Ge -> Ge) -> Ge) -> Ge) 　こうして見ていくと、Y Yのベータ簡約を繰り返したとき、その型付けは、ゲーデル数型を要素としたnタプル(n項組)である。例を挙げる。 (Ge -> Ge) -> Ge ( (Ge -> Ge) -> Ge) -> Ge) <, Ge> <<, Ge>, Ge> 　このnタプルは、直積（カルテシアン積）である。また、nタプル二つとブール代数とを組み合わせて、べき集合モデルを作ることができる。 　次に、構造化プログラミングを子供でも分かりやすく解説するため、まず、簡単なゲームをやってみよう。日本のくじである「あみだくじ」を私が改造した遊びである。 　平行に、縦の線を二本描く。このたての線をぬうようにして、平行な横の線を数本えがくことにする。例えば、一本描くと、Hという文字ができるだろう。これらの線がななめに交わることはない。こうして、あみだくじの模様ができる。 　二本の縦の棒の上に、それぞれ、自分の左手と右手を置く。さらに、以下のルールに従いながら、縦の棒の一番下まで進んでいくことにしよう。 ルール （その1）手は縦の線に沿って、下へ進む。縦の線の一番下まで手が来たら、ゴールである （その2）手が横と縦の線の交点にぶつかったら、必ず曲がって、横の線を通り、その後、別の縦の線を下りなければならない （その３）右手と左手がぶつかったら、ゲームオーバーである （その４）両手は同時にスタートして、同時にゴールしなければならない （その5）手の動く速さは、両手とも同じである（ただし、手の位置と速度を同時に測定することはできない） 　実際にHという文字を書いてやってみると、このルールでは、絶対に手がぶつかってしまい、ゲームオーバーとなってしまう。では、どのような解決方法があるだろうか。 　片手をゆっくりと動かすのは、「ルールその5」にひっかかる。片手だけを止めると、今度は同時にゴールすることができなくなって、「その4」に違反してしまう。 　では、横の線を右手専用にして、左手を排他するのはどうだろうか。だが、これも失敗するのである。なぜなら、右手が横の線を渡ったとき、その先には、通れなかった左手が待ち受けており、手がぶつかるからである。時間ごとに、右手専用、左手専用、右手専用...と排他する相手を切り替えても同じである。横の線をロックする排他制御の方法はいずれも失敗する。 　そこで、1965年にダイクストラが提唱した「メッセージ」を解決に活用することにしよう。ここでは、簡単のため、メッセージが瞬時に届くものとする。 解決方法 あらたなルールとして次を追加する。 ルール （その6）「待ち」 (wait) の状態（手を止めているが、指先はぐるぐるとその場で反復しながら回転している状態）でダイクストラ・メッセージを受け取ると、止まった手の動きを再開させる １、スタートしたら、右手が縦横の交点にぶつかる前に、ダイクストラ・メッセージを左手へ発信して、「待ち」の状態に入る ２、左手がメッセージを受信したら、左手も「待ち」の状態に入って、右手へメッセージを発信 ３、メッセージを受け取った右手は「ルールその6」により、「待ち」をやめて、再び手を動かす ４、右手がHの横の線を渡って、ゴールする直前で、メッセージを左手へ発信して、「待ち」の状態に入る ５、メッセージを受け取った左手は、再び手を動かして、ゴールの直前で右手へメッセージを発信 ６、両手ともゴールする 　このダイクストラ・メッセージを使った解決方法では、右手も左手も、両手がともに同時にスタートして、同時にゴールする。さらに、ゴールした時、腕が交差しており、右手と左手がそれぞれ別の動きをしたのは明らかである。したがって、この手の動きは並列処理(parallel process) なのである。なおかつ、一本道である横の線を、両手がぶつかることなく通ったわけだから、これは逐次処理（順序処理、シーケンシャル処理、シーケンス処理, sequencial process) である。また、（ルールその5）より、次の等式が成り立つ。 　（解決法2での左手の待ち時間） = （解決法3，4での右手の処理時間） 　したがって、逐次処理が制限時間内に終わることを左手は事前に知っているわけだから、この手の動きは並行処理(concurrent process)やマルチスレッドではなく、並列処理である。例えば、左手の待ち時間が1秒であった場合、1秒以内に自身が横の線を渡ることができることを、左手は前もって知っているのである。これは自身が停止することを事前に知っていたと言うことである。 　このように、ダイクストラ・メッセージを使えば、通常のアルゴリズムでは解けないような問題でも、効率よく解決ができる。 　さらに、右手と左手が同じ横の線をなぞったということは、情報の共有である。すなわち、横の線を、2台の機械の間で共有したい情報に置き換えることもできる。例えば、横の線を食器に置き換えて、両手を二人の哲学者に置き換えれば、ダイクストラがホーアに提案した、いわゆる「哲学者の円卓」問題も解決できる。すなわち、円卓を囲んだ哲学者たちがダイクストラ・メッセージを使って、「お先にどうぞ」と互いに譲り合えばよい。譲られた方は食べ始めると、円卓の哲学者たちは、複数の待ち行列に並んだことになる。 　さて、この手の動きとメッセージを、プログラムとして実装したい。これらのアイデアを実現するには、計算機が2台以上の、大規模な開発を想定したプログラミングが必要となる。「待ち」に関しては、67年にシミュレーション分野を研究していたダールと二ゴールが「クラス」と「コルーチン（疑似並列、coroutine）」をSimula67で実装した。60年代後半になると、ダイクストラは（疑似ではない）並列処理の研究を進めて、「3つの型」や「階層構造」、「不変（不変量、不変条件）」というアイデアを生み出した。さらに、彼は、このアイデアを発展させると、科学者や数学者が無意識に使う「抽象」が、プログラミングの型に似ていることに気づいた。72年に、ダイクストラ、ダール、ホーアはこれらの研究を一冊の本にまとめて、「構造化プログラミング」として体系化した。この本により、ダイクストラの研究とクラスプログラミングが結びつけられたのである。 　構造化プログラミングは、情報技術 (Inforamation Technology) において、計算、証明に関する革命的な考えをもたらした科学理論である。 　これで、構造化プログラミングについて、かんたんに理解できるような、やさしい説明を終わりにする。 2, 歴史 2.1 導入 　歴史に触れる前に注意点を述べる。すばらしいアイデアは誰かが先に見つけているものだ。したがって、アイデアの混用を避けるために、よく引用が用いられる。だが、日本と違って、海外の論文は表現を変えることで引用する習慣が根づいている。この点を踏まえたうえで、技術の観点から、オブジェクト指向プログラミングの歴史を振り返ろう。 2.2 new構文 　1957年、アメリカのジャクソンは、ネットワーク理論とアーランの待ち行列理論の両方を使った「待ち行列ネットワーク(queueing network)」のモデルを発表した。それはネットワークの「窓口（server)」間を複数の「客（customer)」が独立して移動するモデルである。ネットワークのノードは待ち行列で形成されている。その各待ち行列には窓口が付いている。 　さらに、待ち行列理論の考えをもとにしたプログラミング言語が出現した。1962年には、SIMSCRIPT言語がリリースされた。この言語が後にSIMULA言語に影響を与えた。 　この動きとは別に、1960年にリリースされたAlgol60言語は「ブロックプログラミング」と「手続き(procedure)」という、アクセスコントロールの技法をプログラミングにもたらした。この手続きはFortran ⅠⅠの関数を拡張した形をとる。ブロックプログラミングでは、関数と違って、ブロックの中に手続きを入れ子にすることが可能である。 　さて、当時、ノルウェーの科学者ダールはモンテカルロ法シミュレーションを研究していたが、王立ノルウェー計算機センターで、ノルウェーのニゴールとともに、新しい言語の開発に取り組んだ。 　62年、ニゴールはヨーロッパの学会で「離散事象ネットワーク（discrete event network)」のアイデアを発表 (5)した。ここでは、同時期のペトリネット（注1）と区別するために、そのアイデアを「ニゴールネット」と名付けよう。 　ニゴールネットは待ち行列ネットワークから着想を得ている。ニゴールとダールによれば (34)、このモデルは「中継点（station)」間を客が移動するネットワーク構造である。中継点には「待ち行列部 (queuing part)」と「サービス部 (service part)」が備わっている。63年に、二ゴールネットをSIMULA Ⅰ言語の基本構想に取り入れた。その構想の中で、サービス部はAlgol60の記法を使って書くことをニゴールたちは決めていた。64年には、「疑似並列 (quasi-parallel)」を言語開発に採用した。さらに、一年後に「we found important examples of systems which we felt could not naturally be regarded as "networks"」 (5)という理由から、「ネットワーク」の文言は新言語の構想から消えて、二ゴールネットは「離散事象」という名称になったのである。 　65年に、この疑似並列を実装したSIMULA Ⅰ言語をニゴールとダールは発表した。この言語は、客の生成のために、次のようなnew構文を備えていた。 Element :- new Activity() 　上記のElementとActivityは、Algol60のブロックプログラミングと手続きの拡張である。このElementとActivityについては、第4章で詳しく言及する。 　また、用済みになった客を自動で消去できるのが、この言語の特徴である。 2.3 メッセージとセマフォ 　1965年、オランダのダイクストラは研究報告の中で、いわゆるクリティカルセクション問題の解決方法を示した。その解決方法とは、二つのプロセス間でメッセージを「通信 (communication)」するというものである。一つのプロセスAに「待ち (wait)」状態が発生すると、このプロセスAはもう一方のプロセスBに対して、「お先にどうぞ (after you)」というメッセージを送る。待ちの間、プロセスBが先に処理を行うのである。 　1966年、Vilard-de-Lansという町において、NATO（北大西洋条約機構）が主催するSummer Schoolで、ダイクストラは「順序機械 (sequential machine)」を使った「逐次プロセス (sequential process)」について講義を行った。 　この講義の中で、ダイクストラは互いに影響しない独立したプロセスを複数想定し、 When two or more of such processes have to cooperate with each other, they must be connected, i.e. they must be able to communicate with each other in order to exchange information すなわち、情報交換のために、プロセス同士が通信する状況を考えた(13)。一連の動作を「協調逐次プロセス (Cooperationg Sequential Process)」とダイクストラは呼んで、「セマフォ（腕木信号、Semaphore)」の信号に例えた。さらに、彼は協調逐次プロセスが並列処理に応用できるとした。 　また、同じくVilard-de-Lans大会のSummer Schoolで、ダールは、SIMULA Ⅰ言語の講義を行った(6)。彼は、その際、イギリスのホーアの影響を受けて、「クラス (class)」を提唱した。 　その後、ダイクストラとホーア、ダールの3人は1972年、『構造化プログラミング』の著書の中で、クラスと「コルーチン（コルティン、coroutine)」を使ったセマフォの実装を紹介した。 　さらに、78年には、ホーアはダイクストラの研究とダールのクラスを紹介した「通信逐次プロセス（Communication Sequential Process 、通称、CSP)」という題名の論文を発表した。このCSPはプロセス代数に影響を与えた。 　このようにして、ダイクストラの研究はプログラミングに「メッセージ」と「シーケンシャル（順序、逐次、シーケンス、sequential）」という考え方をもたらした。この「メッセージ」はクラスとコルーチンで実装が可能であることを、ダイクストラとホーアとダールは72年の「構造化プログラミング」で示した。 　セマフォの意味は、歴史上、オランダ語と英語で異なる。そこで、セマフォを次の2種類に分ける。 「ダイクストラ式セマフォ」 　バケツリレー方式の腕木通信。伝言ゲームのように、片側通行のメッセージを1種類送る。語源は、フランス占領下の19世紀、オランダのアムステルダムに設置されたバケツリレー方式の腕木通信の施設。これは3本の木を動かすことで、手旗信号のように、20種類以上の信号をどれか選んで、文字を送る。 「ホーア式セマフォ」 　2種類の信号を使って、処理の進行を制御する。語源は、英国鉄道の腕木式信号機。これは青信号（進め）と赤信号（止まれ）を腕木で切り替えて、列車の運転手に伝える。オランダ語のセマフォとは異なる。 　この二つのセマフォは互いに機能を補完し合っている。すなわち、プロセスが、ダイクストラ式セマフォのメッセージを送信したときに、ホーア式セマフォが「止まれ」の赤信号をそのプロセス自身に出す。そして、ダイクストラのメッセージを受信したときに、「進め」の青信号をそのプロセス自身に出せばよい。こうすれば、「お先にどうぞ」と、プロセスは別のプロセスに譲り、待ち行列に並ぶことができるのである。 2.4 クラスと部分クラス 　1965年、ホーアは論文「RECORD HANDLING」(7)の中で「レコードクラス(record class)」を発表した。この論文は、レコード (record)と、それを破壊するdestroy手続きと、それを参照(reference)する概念とnullを生み出した。 　さらに、彼はスイスのウィルトとともに、レコードクラスを実装したAlgol W言語をリリースした。また、ダイクストラはレコードクラスをwhile文で実装した。 　上記の論文の中で、ホーアはレコードクラスの応用例として、待ち行列モデルの実装を挙げている。 　1966年、NATOのSummer School (2.3節参照) でホーアのレコードクラスを知ったダールとニゴールは、このレコードクラスをSIMULA言語に実装すべく、研究開発を進めた。 　67年に、ダールとニゴールはSIMULA67言語をリリースした。ダールによれば、この言語は、レコードクラスと違って、動的リンク(dynamic link)と、ブロックと手続きの「連接（concatenation)」により「部分クラス(subclass)」を実現している。彼らはレコードクラスと区別するために、自分たちが開発したクラス技術を「対象クラス(object class)」と名付けた。対象クラスと連接のしくみについては、第3章で詳しく述べる。 　68年には、ニゴールたちが論文「Class And SubClass Declaration」で発表している。この中で、対象や「所属物（attribute)」などのアイデアを解説している。また、手続きか「this」の使用で、隠蔽された(hidden)属性へアクセスできることも示している（2）。 　また、SIMULA67はドット(.)を使ったいわゆるメソッド呼び出しやプロパティ呼び出し、書きかえにも対応した。構造化プログラミングでも触れられているが、今日メソッド呼び出しと呼ばれる手法を「遠隔識別 (remote identification)」と呼ぶ。 2.5 virtual quantity 　67年にSIMULA67が発表されたヨーロッパの学会において、科学者たちは「virtual quantity」という重要なアイデアを提唱した。ダールとニゴールによれば、これは、virtualという接頭語を付けた手続きを名前呼び（call by name)で評価できる機構である。メソッドのオーバライド(override)によって、この機構を実現できる。 　1981年の時点では、SIMULAがvirtual接頭語を標準化していた。 2.6 階層構造 　1968年、ダイクストラは、「マルチプログラミング (multi-programming)」の設計と実装に関する論文(11)の中で「階層構造 (hierarchical structure)」を示した。この考え方は、おなじくマルチプログラミングの研究をしていたアメリカのパルナスに大きな影響を与えた。 　1971年には、パルナスはモジュールと「情報隠蔽（infomation hiding)」のアイデアを導入して、ダイクストラの「階層構造」と、「分解 (decomposition)」を別々に切り離して考えることを提言した (12)。 2.7 構造化プログラミング 　ダイクストラは、構造化プログラミングのアイデアを3回に分けて発表している。 　1回目は、68年のNATOソフトウェア国際会議の場で、研究報告として発表した。これを題名から「ノート版」と称することにする。 　2回目は、69年のNATOソフトウェア国際会議ローマ大会の場である。これを「ローマ版」とする。 　3回目は、72年に「構造化プログラミング」という名前の書籍をダイクストラたちが出版した。これを「書籍版」と呼ぶ。 　いずれの案も、内容が大幅に異なっている。たとえば、ローマ版には、ノート版に書かれた内容がほぼ触れられていない。ノート版では、ダイクストラは「不変 (不変量、invariant)」と「抽象 (abstraction)」という考えをプログラミングにもたらした。それに対して、ローマ版では、ノート版の内容に触れず、彼は分解を発展させた「洗練（refinement)」（注2）という考えを導いた。 　書籍版の第一部「構造化プログラミング」では、ダイクストラがノート版とローマ版を修正して、ウィルトの講義資料を加えて加筆した。また、順序機械を使って、デンマークのナウアが69年に提唱した「作用 (action)」と分解と制御構造の関係、あるいは、複数の機械の「階層 (hierarchy)」について考察した。 １、抽象 ２、数え上げの推論（科学的帰納法） ３、数学的帰納法 この3つが「連接」、「選択」、「反復」という3パターンの「型 (type)」に応用できることを、彼は書籍版の中で主張した。 　また、書籍版の第二部「データ構造化序論」は、70年のホーアが発表した論文をもとにしている。ホーアはダイクストラの「構造化」の原理が適用できるものとして、この論文を書籍版に載せた。論文の中で、彼は数学的構造を用いて、「データ型 (data type) 」の定義と「データ構造 (data structure) 」の分類をした。その上で、制御構造とデータ構造の対応付けを提唱した。彼の主張によれば、case文は複数の型に応じて、振る舞いを分岐させることができる。これがダイクストラの「選択」にあたり、また、再帰的データ型は彼の「反復」に相当するともホーアは主張した。 　そして、以下のような点（ドット）記法を使った選択的更新を取りあげた。 n.imagpart:= 0; r.x:= a * r.x + b * r.y （「構造化プログラミング」123ページより引用） 　これとは別に、ウィルトは自分の書籍「アルゴリズム+データ構造=プログラム」（4）で、制御構造とデータ構造の対応付けした表（第三章を参照）を発表した。 　書籍版の第三部「階層的プログラム構造」は1970年に、Marktoberdorfという場所で、NATO主催のSummer Schoolでダールが行ったSIMULA 67の講義をもとにしている。それをホーアが加筆修正したものである。書籍版では、2.4節で触れたクラスと「対象 (object)」と「実例 (instance)」の定義をする。さらに、「部分クラス(subclass)」や連接、メソッド呼び出しを使ったソースコードの紹介がなされている。また、以下のようなnew構文を紹介した。 G5 :- new Gauss(5); （「構造化プログラミング」207ページより引用） このソースコードでは、クラスと疑似並列を使い、「離散的事象シミュレーション (discrete event simulation)」を作った。この離散的事象シミュレーションについて、書籍版の中では次のように述べている(1)。 離散的事象のシミュレーション シミュレーションのモデルの対象は、生産ライン、交通システム、計算機（のハードウェア、ソフトウェアの）システム、作用し合う個体からなる社会的システムなどである。つぎのことがらは、これらのシステムの多くに共通している。 (1) いくつかのプロセスが、不規則な時間間隔を置いて離散的な事象を生み出しながら、並行して (in parallel) 進行する。 (2) 対象が、その時にふさがっている窓口でサービスを待たなければならないときに、待ち行列 (queueing) の現象が生じる。 （「構造化プログラミング」235、236ページから引用） 　また、この離散的事象シミュレーションを使って、ネットワーク上の二つのノードの最短距離を求める「ダイクストラのアルゴリズム（あるいは、ダイクストラ法とも呼ぶ）」とジョブショップモデルを実装した。また、実装のコードをホーア式セマフォと関連付けた。 　書籍版のまえがきの中で、ホーアはこの第三部の講義資料を指して、「ここの例で、構造化プログラミングの原則がプログラムの"下降型"の設計と同様に"上昇型"の設計にも適用できることを示している」(1のまえがきより引用)と指摘した。また、その第三部の本文に目を向けると、「概念の水準の層は、クラス宣言の前置きの系列 (prefix sequence)によってあらわすことができる」（234ページ）としている。さらに、クラスの「連接」(2.4節参照）と概念の階層との関係について論じている。 　つまり、書籍版「構造化プログラミング」の第三部「階層的プログラム構造」でSIMULA 67のクラスを使って示しているのは、ダイクストラの階層構造（2.6節参照）なのである。 2.8 構造化プログラミングの普及 　72年に出版された「構造化プログラミング」は大きな反響を得た。 　構造化プログラミングの影響を受けて、アメリカのリスコフ（リズコフとも呼ばれる）が「抽象データ型 (abstract data type)」を提唱した。後に、抽象データ型はC++言語などに取り込まれた。また、90年代以降は、抽象データ型の影響を受けたabadi と Cardelliらのオブジェクト計算や「部分型多相 (subtyping polymorphism)」が登場した。やがて、これはOCaml言語の開発へとつながっていく。 　また、構造化プログラミングの影響を受けた(10)フランスのメイヤーはプログラミング言語Eiffel言語を開発した。 　70年代以降、構造化プログラミングの考え方は、書籍版やリスコフ、メイヤーらを通じて普及していった。 2.9 先祖返り型言語 　1970年に、ウィルトはAlgol WをベースとしたPascal言語をリリースした。 　しかし、一方で、73年ごろから登場したC言語は、PascalのようなAlgol系統のブロックと手続きをサポートしなかった。アメリカのカーニハンとリッチーによれば (3)、 CはPascalやそれと類似の言語で使われる意味では、ブロック構造の言語ではない。 　彼らの言うとおり、実際に、C言語（注3）では、手続きを入れ子にする機能や、ブロックの中に手続きを入れ子にする機能がない。すなわち、この言語はAlgol60の主要な機能を失ったのである。 　以降、この言語のように、Algol系統から離れたプログラミング言語を「先祖返り型言語」と呼ぶことにする。また、Algol系統のブロックと区別するため、C言語のブロックを「非ラムダブロック」と呼ぶことにする。 2.10 ポインタと参照 　Pascalのデータ型では、型のポインタ(pointer)と参照という考えが導入された。開発者のウィルトによれば(4)、この二つの考えについて、記憶領域の大きさが初めから明らかではない再帰的 (recursive)構造に対して有効とした。その上で、この記憶領域の不明問題を解決するため、動的割り付けについて、ウィルトは次のように述べた（ただし、型Tはtype Tとしてすでに宣言されているものとする）。 データとデータに対する参照を記法的に明確に区別することが必要であり、その結果、その値がほかのデータへのポインタ（参照）であるようなデータ型が導入されなければならない。この目的のために我々が用いる記法は、次のようなものである： type Tp = ↑T (4.4) 型宣言(4.4)は、型Tpの値は型Tのデータへのポインタであることを表している。したがって、(4.4)の矢印は "...へのポインタ" を表している。指されている要素の型がTpの宣言から明白であることは基本的に重要である。われわれはTpはTに束縛されているという。この束縛は高級言語におけるポインタを、アセンブラ語における番地から区別するものであり、記法上の冗長性を利用して、プログラム言語における安全性を増加させるための最も重要な機構の一つである。 　さらに、ウィルトは続けて、 var p: Tp; new(p); というコードを書く。そうすれば、動的に「型Tの変数を実際に割り付け、この新しい変数を参照する型Tpのポインタを生成し、そしてこのポインタを変数pに代入」(4)することができるとした。p↑と書くと、動的に割り付けられた型Tの変数を指す。 　束縛に似たアイデアは、Simula67でもref(T) p;という「参照の制限」（ただし、変数pは参照型）として登場する。また、PascalとSimula67の参照はホーアのレコードクラス（2.4節）に基づく。 　改めて、それぞれ二つの言語のコードをまとめてみよう。 「Simula67 言語」（1967年リリース） ref(T) p; p :- new T(); 「Pascal 言語」（1970年リリース） type Tp = ↑T; var p: Tp; new(p); 2.10 protected 機構 　1973年、スウェーデンのパルメは手続きをアクセスコントロールするための「protected 機構 (protected mechanism)」を考え出した。 　この考えは71年のパルナスの情報隠蔽とともに、抽象データ型の「データ隠蔽 (data hiding)」に大きな影響を与えた。 　パルミはSimulaの標準化団体にこの機構を提案して、1981年の時点にはもう、SIMULAにprotected接頭語が導入された。 　SIMULAで導入された後に、C++言語は86年の仕様でこのprotected機構を取りこんだ（5）。 2.11 外部仕様 　1975年、圏論の研究から、アメリカのADJグループは「代数仕様記述言語」として、Clear言語を発表した。代数仕様は、外部仕様と内部仕様に分かれている。後に、OBJ言語が代数仕様をサポートした。 　その後の研究で、抽象データ型で代数仕様が定義でき、逆に、代数仕様で抽象データ型を定義できることが示された。 　C++言語の技術者たちは、外部仕様（注4）のために、関数プロトタイプ宣言をサポートした。86年には、ANSIがその機能をC言語に移植した。また、関数プロトタイプとは別のやり方で、JAVA言語がinterfaceをサポートした。 2.12 オブジェクト指向プログラミング 　1990年、C++を開発したアメリカのストラウストラップとエリスは自身の書籍 (33)において、「オブジェクト指向プログラミング」の定義を次のように示した。 基底クラスと派生クラスと言う用語は、代替案であったスーパークラス(superclass)とサブクラス(subclass)を押しのけて選択された。（中略） 派生クラスと仮想関数の使用は、多くの場合、オブジェクト指向プログラミング(object-oriented programming)と呼ばれる。さらに、――仮想関数で与えられるような――厳密に同じインターフェースを使って、様々な関数を呼び出す機能は、多相性（polymorphism)と呼ばれることもある。 　ストラウストラップは、データ隠蔽の考えを発展させた「カプセル化 (encupsulation)」を発表した。このアイデアはプログラミングに（外部仕様に対する）「内部実装」の考えをもたらした。 2.13 メッセージング・メッセージパッシング仮説 　1994年に、アメリカのジョブズが、「オブジェクト指向プログラミング」の定義として「メッセージング・メッセージパッシング仮説」をメディアへ発表した。しかし、この主張は誤りだ。なぜならば、時系列に矛盾があるからである。 　もとのアイデアは、アメリカのケイが生み出した「オブジェクト指向」という考えである。ところが、「構造化プログラミング」の書籍版が出版された1972年より前、すなわち、1971年以前に、オブジェクト指向に関する学術論文は存在しない。つまり、71年までに、ケイは自分のアイデアを公表していないのである。 　ゆえに、1960年から1972年までにかけて、ケイの主張がダイクストラたちに影響をおよぼすのは困難である。よって、オブジェクト指向プログラミングのメッセージング・メッセージパッシング仮説は誤りである。 2.14 まとめ 　このように歴史を見ていくと、70年代に、ヨーロッパの科学がアメリカに伝わっていった様子が明らかになった。つまり、60年代にパラダイムシフトの起きたヨーロッパから、アメリカへオブジェクト指向プログラミングが伝来した。 　SIMULA言語を種子島銃と見立てるならば、構造化プログラミングの書籍版は銃の設計書のようなものである。この二つがアメリカで大きなうねりを作り上げたのだ。すなわち、オブジェクト指向プログラミングの「new構文」と「メソッド呼び出し」と、「プロパティ呼び出し」は、構造化プログラミングの書籍版 (72年版）で紹介されたものが広まったのである。 　よって、構造化プログラミングの書籍版は、地道な基礎研究を積み上げて、ソフトウェアやプログラミングにおける科学の基礎体系を築き上げたと評価できよう。 　さらに、68年にダイクストラが提唱した「階層構造」はパルナスのモジュール、リスコフの抽象データ型を通じて広がっていった。これはプログラミング技術の土台となっている。 　また、この章で触れなかったが、以下の点に注意しよう。 -ダイクストラは複数の論文の中で、プログラムの繰り返しをしたいとき、while文やrepeat文などの制御構造の代わりに、goto文を使った。SIMULA 67言語が登場する1967年までは。 -ウィルトは「ポインタの導入はgoto文の使用に対応する」(4)と主張した -SmallTalk72はnew構文をサポートしていない -SmallTalk72はメソッド呼び出しをサポートしていない -SmallTalk72はプロパティ呼び出しをサポートしていない -SmallTalk72はクラスの継承 (inheritance) をサポートしていない 注記 （注1）ドイツのペトリがペトリネットを文書として発表したのは1962年。なお、ペトリネットの図式化をしたのはペトリではなく、別人である （注2）refinementに洗練や純化という意味はあるが、詳細化という意味はない。本来の意味とは逆の意味なので、詳細化という言葉は日本人の造語であると推察される。ここでは野下浩平の「洗練」という訳（1）に従った （注3）1988年当時のANSI規格による(3) （注4）Cの系統は、OBJ言語の系統に見られるようなソート隠蔽は未実装 3, 構造化プログラミング 3.1 導入 　第三章では「構造化プログラミング」（書籍版）を使って、それがどういったプログラミングなのかを説明する。彼、あるいは彼と同時代の技術者たちが抱えていた問題を理解したとき、我々は多くの知識を得ることができるだろう。 　「構造化プログラミング」（書籍版）は3部構成となっている。 　第一部はダイクストラが執筆した「構造化プログラミング論」である。第二部はホーアが執筆した「データ構造化序論」である。第三部はダールとホーアの「階層的プログラム構造」である。 　はじめに、第二部のデータ構造化を考察する。続けて、ブロックプログラミングについて考えていき、第三部の階層的プログラム構造における対象とクラスの定義を見ていく。以上から得られた知識をもとに、第一部で示されたダイクストラの構造化プログラミングがオブジェクト指向プログラミングであることを明らかにする。 　特に断わりがないかぎり、書籍版の数字のページにおいては、日本語版(1)を使う。 3.2 データ構造化 3.2.1 抽象 　3.2節では、まず、ホーアの「データ構造化序論」を見ていく。ホーアによれば、ダイクストラとウィルトの助言に従って、この論を書いた。 　その論に従い、データ構造化とは何かを定義していこう。データ構造化について我々が考えなければならないのは、「抽象（abstraction)」である。 　一般に、抽象は、人間の思考の上で重要な役割をになう。それ以上に、プログラミングとは深い関係がある。「データ構造化序論」の中で、ホーアは抽象について次のように述べた。 複雑な現象を理解してゆく過程において、人間の理解力の助けとなる最も強力な道具は抽象（abstraction)である。（中略）抽象の過程は4つの段階に要約される。 　（1）抽象：　現実界の多くの対象物や状態が共通に持っている性質にもっぱら着目し、相互間の差異は無視することの決定 　（2）表現：　抽象された概念を表現する記号集合の選択。これらは情報交換の手段として用いられる 　（3）操作：　記号によって表現されたものの変換に関する規則で、現実界における類似操作の効果を予測する手段となる 　（4）公理化：　現実界から抽象された各種性質の厳密な記述。この性質は、現実界における操作と、それを表現する記号上での操作とが、共通に持っているものである。 （「構造化プログラミング」97，98ページより引用） 　まず、第一段階として、現実に起きている事がらについて、その共通点に着目する。共通点以外の違いを無視して考えることは、複雑な現象を理解する手助けとなる。これはけっして難しい作業ではなく、我々の日常作業でも見られるだろう。例としては、お金を数えるときに、その金額に着目すれば、お札や硬貨の重さや材質を気にする必要はないのである。ただし、先の引用では、「抽象」となっているが、「抽象の第一段階が抽象」と言うよりも、むしろ「抽象 (abstraction)の第一段階が抽出 (abstract)」と言ったほうがよい。先ほどの例で、我々は貨幣から金額という共通点を抽出したのである。今後、抽出と呼ぶことにする。 　続けて、第二段階では、現実世界に起きている事がら、あるいは自分の考えを表現したいとき、その表現 (representation)によって指し示す情報を明らかにするのである。第一段階における共通する性質を表現するとき、その指し示したいものを「抽象概念（abstract concept)」と呼ぶ。 　人類が後世に記録を残すときに発明した手段は文字である。文字は発話、あるいは、書かかれた記号を通じて、情報を交換する。しかし、日常で使う文字は誤解を与えることがあるので、抽象概念の表現は、厳密な定義が求められるもの、例えば、数学や論理学で使われる記号がもっぱら選ばれるだろう。例えば、100円という金額の表現はアラビア数字の「1」、「０」、「0」の十進法が使われる。我々は、「いっぱい」や「少ない」というあいまいな表現を除くのである。 　第三段階となると、表現を操作していく。ここで、操作そのものについて注意しなければならない。例えば、天気予報の図で、雨雲を動かしているのは現実の世界の雲ではなく、データ上のことである。雨ごいをしているわけではなく、データを変えさせて、雨雲の動きを再現していることから現実の動きを予測している。すなわち、データを変換した結果が現実に影響を与えるわけではないのである。 　こうしたデータから別のデータへの転換は、ある法則に従う。天気予報の例でいえば、物理法則によって、我々は現実の天候の移り変わりを予測することができる。その転換に使われる規則が操作なのである。 　最後に、第四段階においては、表現とその操作を実際に記述することになる。この公理化 (axiomatization)の目的について、ホーアは「（これらの公理が現実界を正確に記述しているという条件の下で）表現物の操作によって得られる結果が、現実界にもきちんと適用できると言うことを、厳密に証明する」（98ページ）ことであると述べている。あるいは、公理 (axiom)が「今日のプログラミング作業につきものの混同や誤りを減少させ、プログラムおよびプログラム手法の文書化と解説を容易ならしめることも可能」（100ページ）だと期待を寄せた。すなわち、ホーアによれば、表現と操作を記述した、第四段階目の公理化で、特定のプログラムが正しいのかどうかを調査できるというのである。 3.2.2 抽象の例 　理解を深めるために、抽象の例を挙げてみよう。まず、お金を数える例でいくと、1円玉を1枚数えるとき、 1(円玉）を1（枚） とカッコの中に書かれた違いは無視して、1という共通の性質を取り出すことができる。 　さて、ホーアは抽象概念の例として「数 (number)」を挙げた。先ほどはお金であったが、現実において、昔の人が最初に数えたのは自然界にあるような石ころや、木の枝であったと考えられる。どのような木の種類であるかは無視して、枝が何本あるかを数えていくとき、それを記録する必要がある。 　第一段階で抽出された数を表現するために、人が使用したのは数字という記号の集まりであった。当初は木の棒を表現する簡単なものであったと言われる。ローマ数字では縦の棒を引いて、Ⅰ、Ⅱ、Ⅲと書いていく。漢数字では横の棒を引いて、一、二、三と書いていく。しかしながら、4、５、6...と数を多くしていくと、この二種類のやり方では不便である。時代が下り、ゼロが発明されると、1、2、3と、簡単な書き方ができるアラビア数字と、十進法の方式で数を表現するようになった。 　第三段階の操作において、数は和という演算をする。例えば、1 + 1のように計算をして、1を加えて別の数をはじき出そうと言うのである。この段階において、数の性質について厳密な定義が求められる。 　そこから、次の段階に移ると、peanoの公理が現れた。この公理は人工のお金であろうと、自然界の石や木の枝であろうと、現実における数を厳密に定義することができるのである。確かに、節の冒頭の「数える」という行為は、第三段階の和という操作と一致する。 　このように、抽象を4段階の「抽出 -> 表現 -> 操作 -> 公理化」に分けて考えていくと、現実の世界への理解が容易となる。 3.2.3 型 　近代に入ってから、数学と論理学、この二つの学問で、とある共通点が見出された。その共通点とは型 (type) の概念である。 　型の概念を知るために、まず、数学の手法について考えてみよう。数学者は新しい変数を使うために、その変数がある種類に属することを宣言する。このとき、変数を示す記号の字体を変える。たとえば、 "小文字は要素, 大文字は要素の集合, そして筆写体文字は集合の族を表すのに用いる" (「構造化プログラミング」106ページより引用） というような使用法である。この使用法は、記号の種類をそれぞれ区別するのに用いられる。しかし、ホーアの考えによれば、非素数と素数を区別するのに使用されることはなく、よって、数学者の慣習ではない。数学者が無意識に使う手法であるが、記号の字体を変えるのは、変数を型という概念に属させる目的があるのである。 　一方で、論理学の一分野でも、型という概念が生まれた。 3.3 ブロックプログラミングと手続き 3.3.1 ブロックと手続きの誤ったイメージ 　第二章では、C言語などの先祖返り型言語において、手続きを入れ子にし、ブロックの中に手続きを入れる機能が未実装であることを述べた。このことは、ブロックと手続きに対する誤ったイメージを作り上げた可能性が高い。 　まず、先祖返り型言語の開発者に向けて、ブロックと手続きの正しいイメージとは何かを説明しておこう。かんたんな比較のために、Algol60のbeginとendをそれぞれカッコの{と}に、あるいは、手続きのreturn機構(return mechanism) などをreturn文といった先祖返りの構文に置き換えて、正しいブロック構造を再現してみよう。 ブロックプログラミング（ブロックと手続きの正しいイメージ） { int x = 0; { int y= 1; int f (int n) { int g (int m) { return n+m+x+y; } return g(12); } printf("%d\n", f(10) ); // 23を出力 } } 続いて、あえて間違った非ラムダブロック構造（第2章2.6節を参照）のソースコードを書いてみる。 非ラムダブロックプログラミング（手続きの誤ったイメージ） int x = 11; void f (int m) { int y = 0; ... x = m + x + y; } main(){ f(12); printf("%d\n", x); // 23を出力 } 　手続きの正しいイメージでは、ラムダ計算モデル（注1）で裏付けられている。手続きの誤ったイメージの場合、その裏付けが難しい。 　さらに、変数xを見てほしい。正しいほうでは、変数はブロックの中にある。したがって、外部のブロックからはアクセスできない仕組みになっている（4）。だが、間違ったほうでは、変数xはブロックの内部にはなく、外部から自由に参照されたり、書きかえられる。こうした誤ったイメージでは、一つのファイルで複数の部品を作ることすら不可能（注2）である。 　さて、ブロックプログラミングを理解する準備ができたところで、ブロックを見ていく。 注記 （注1）型無しラムダ計算（ただし、+の中間演算子と数字はそのままにしておく）で書くと、λx.λy.(λn.((λm.n+m+x+y) 12) 10) 0 1 　となる。評価すると23 （注2）C言語においては、複数のファイル間でリンケージを活用してモジュールを作る 3.3.2 ブロック 　Algol60では、先祖返り型言語の構文と異なり、beginとendで囲まれたブロックを使ってプログラミングをする。 begin （ここにコードを書いていく） end 　このbeginとendで囲まれたブロックは入れ子にしてもよい。例えば、 begin begin end end といった具合である。 3.4 対象クラスによる階層プログラム構造 3.5 洗練による構造化 4, オブジェクト指向とは 5, まとめ 参考資料 注：印刷物ではない電子情報の資料に対しては、閲覧日を記しておいた。閲覧日のないものは、紙の書籍である。 (1) 「構造化プログラミング」（ダイクストラ/ホーア/ダール　共著、　野下/川合/武市　共訳、サイエンス社、1975年8月） (2) 「Common base language」 (Ole-Johan Dahl / Bjørn Myhrhaug / Kristen Nygaard 著、NORWEGIAN COMPUTING CENTER Forskningsveien、1968年)　https://bibsys-k.userservices.exlibrisgroup.com/view/delivery/47BIBSYS_UBO/12216823070002204　閲覧日2019年12月2日 (3) 「プログラミング言語C 第２版（訳書訂正版） ANSI規格準拠」（B.W.カーニハン/D.M.リッチー　著、石田晴久　訳、共立出版株式会社、1996年2月、p102） (4)「アルゴリズム+データ構造=プログラム」（Niklaus Wirth　著、片山卓也　訳、日本コンピュータ協会、科学技術出版社、1979年9月、pp.188-190) (5) 「SIMULA Session PAPER: THE DEVELOPMENT OF THE SIMULA LANGUAGES」（Kristen Nygaard/Ole-Johan Dahl　著、 the Association for Computing Machinery, Inc.1981年）pp442-443, p.447 https://www.cs.tufts.edu/comp/150FP/archive/kristen-nygaard/hopl-simula.pdf　閲覧日2020年5月8日 (6) 「The Birth of Object Orientation: the Simula Languages∗」(Ole-Johan Dahl　著、 2001年6月pp.3-4）https://www.mn.uio.no/ifi/english/about/ole-johan-dahl/bibliography/the-birth-of-object-orientation-the-simula-languages.pdf　閲覧日2020年11月5日 (7) 「RECORD HANDLING」（C. A. R. Hoare　著、Elliott Bros. (London) Ltd.　1965年7月）https://archive.computerhistory.org/resources/text/algol/ACM_Algol_bulletin/1061032/p39-hoare.pdf　閲覧日2020年1月25日 (8) 「Bibliography Kommunikation mit Automaten Carl Adam Petri.」（Universität Hamburg　編） http://www.informatik.uni-hamburg.de/TGI/publikationen/public/1962/Petri62/Petri62_eng.html　閲覧日2020年2月25日 (9) 「Petri net」（Carl Adam Petri and Wolfgang Reisig　著 Scholarpedia, 3(4):6477. doi:10.4249/scholarpedia.6477、2008年）http://www.scholarpedia.org/article/Petri_net　閲覧日2020年2月25日 (10) 「Bertrand Meyer: publication list, by date」http://se.ethz.ch/~meyer/publications/index_date.html　閲覧日2020年2月26日 (11) 「The Structure of the "THE"-Multiprogramming」(Edsger W. Dijkstra　著、Technological University, Eindhoven, The Netherlands、1968年5月) https://klevas.mif.vu.lt/~liutauras/books/Dijkstra%20-%20The%20structure%20of%20the%20THE%20multiprogramming%20system.pdf　閲覧日2020年3月19日 (12) 「On the Criteria To Be Used in Decomposing Systems into Modules」 (D.L. Parnas　著、Reprinted from Communications of the ACM, Vol. 15, No. 12, 1972年12月) http://sunnyday.mit.edu/16.355/parnas-criteria.html　閲覧日2020年3月19日 (13) 「E.W.Dijkstra Archive: Cooperating sequential processes (EWD 123)」(E. W. Dijkstra　著、transcribed by Nick James and Ham Richards、revised Tue, 4 Dec 2007） https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html　閲覧日2020年6月16日 (14) https://hannemyr.com/cache/knojd_acm78.pdf　閲覧日2020年11月5日 (28) 「コンピュータサイエンス大学講座24 計算論-計算可能性とラムダ計算-」(高橋正子 著、近代科学社、2016年2月） (29) 「Computer Science Library 4 C言語による計算の理論」（鹿島亮　著、サイエンス社、2013年9月） (30) 「SIMULA ―an ALGOL-based simulation language」（Ole-Johan Dahl / Kristen Nygaard 著、Communications of the ACM、1966年9月）www.cs.tufts.edu/comp/150FP/archive/kristen-nygaard/simula-cacm-1966.pdf　閲覧日2020年1月30日 (32) 「経営科学のニューフロンティア　13　待ち行列ネットワーク」（紀一誠　著、朝倉書店、2002年11月） (33) 「注解　C++レファレンス・マニュアル」 (M・A・エリス、B・ストラウストラップ　著、足立高徳　小山裕司　訳、p.3） (34) 「Revised Report on the Alogorithmic Language ALGOL 60」（PETER NAUR　他著、IFIP TC2、1962年8月、4.1.3節）http://standardpascaline.org/Algol60-RevisedReport.pdf　閲覧日2019年12月24日 (100) 「■6 群（コンピュータ‐基礎理論とハードウェア）-- 2 編（計算論とオートマトン）2 章有限オートマトンと正則表現」http://www.ieice-hbkb.org/files/06/06gun_02hen_02.pdf　閲覧日2020年5月11日