ALGOL 60 報告 ── 言語を文法で定義するということ

デンマーク・イギリス・フランス・ドイツ・オランダ・スイス・アメリカから集まった13名の代表が、 1960年1月11日から16日までパリで会議を開いた。 その成果である Report on the Algorithmic Language ALGOL 60 は、 Peter Naur の編集で同年5月の Communications of the ACM に掲載される（3巻5号 299–314頁）。

この報告が置いていったものは、 プログラミング言語そのものより、 プログラミング言語をどう定義するか の型だった。

ALGOL 58 から ALGOL 60 へ

前身は1958年のチューリッヒ会議でまとめられた暫定報告である。 ACM の Preliminary report — International Algebraic Language（1958年）と、 A. J. Perlis と K. Samelson が編集した Numerische Mathematik 版（1959年）の二つの形で出た。 通称 ALGOL 58、 あるいは IAL。

暫定報告の後、 ヨーロッパでは実装会議が開かれ、 Naur が編集する ALGOL Bulletin が議論の場になった。 1959年6月のパリ ICIP 会議での行き違いを受けて、 1960年1月に最終報告のための国際会議を開くことが決まる。 ヨーロッパ側7名、 米国側7名の代表が選ばれ（うち米国の William Turanski が会議直前に自動車事故で亡くなり、 報告は彼に献じられている）、 13名がパリに集まった。

会議前に、 Naur は暫定報告と準備会合の勧告からまったく新しい草案を書き上げていた。 会議はそれを土台として採り、 項目ごとに合意を作っていく。 報告自身がその過程をこう記している ── 「本報告は、 委員会の概念の和集合であり、 その合意の積集合である」（"The present report represents the union of the Committee's concepts and the intersection of its agreements."）。

三つの層

報告はまず、 言語を三つの層に分けた。

言語の定義と、 人が読むための表記と、 機械が食う表記を最初から分けている。 いま当たり前になっている「仕様と実装は別物」という態度が、 ここに構造として書かれている。

metalinguistic formulae ── のちの BNF

報告の §1 は、 一行でこう始まる ── 「構文は metalinguistic formulae の助けを借りて記述される」（"The syntax will be described with the aid of metalinguistic formulae."）。 続けて記法そのものを定義する。 山括弧で括った文字列は値が記号列であるメタ言語変数を表し、 ::= と |（後者は「または」の意味）がメタ言語結合子である、 と。 変数でも結合子でもない記号は自分自身を表す。 並置は記号列の並置を表す。

そのうえで、 言語の全体がこの記法で書き下される。

<basic symbol> ::= <letter>|<digit>|<logical value>|<delimiter>
<digit> ::= 0|1|2|3|4|5|6|7|8|9

報告の脚注は、 この記法の出所を明示している ── J. W. Backus, The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference, ICIP Paris, June 1959。 John Backus が ALGOL 58 を記述するために作った記法を、 Naur が ALGOL 60 のために整え直したものである。

名前が定まるのは4年後だった。 1964年12月の Communications of the ACM に Donald Knuth が短い投書を載せ、 Backus Normal Form という呼び名をやめて Backus Naur Form と呼ぼうと提案する。 理由は三つ ── Backus と Naur の双方に正当な功績を認められる、 BNF という略記をそのまま使える、 そして Form を Normal Form と呼ばずに済む。 同じ文脈自由言語に対して BNF 文法は無数に書けるのだから、 数学的な意味での正規形ではない、 というのが Knuth の指摘だった。 提案は通り、 以後 BNF は Backus-Naur 形式を指す。

言語の構文を、 散文ではなく形式的な規則の集合として書く。 この一手が、 構文解析の理論とコンパイラ生成器の系譜を開いた。 今日 JSON にも HTTP にも Rust にも文法定義が付いているのは、 この報告の作法の延長にある。

ブロックと有効範囲

もう一つの中心はブロックである。 報告 §4.1.3 は、 一文で本質を書く ── 「すべてのブロックは自動的に新しい命名の層を導入する」（"Every block automatically introduces a new level of nomenclature."）。

そこから先は規則である。 ブロック内の識別子は宣言によってそのブロックに 局所（local） にできる。 局所にすると、 (a) その識別子が表す実体はブロックの外に存在せず、 (b) 外側で同じ識別子が表していた実体はブロックの内側から完全に到達不能になる。 宣言されなかった識別子は 非局所（non-local） となり、 一つ外側の層と同じ実体を指す。 ブロックはブロックを含みうるので、 局所・非局所は再帰的に理解される。

つまり 字句的スコープ である。 変数名の衝突を、 規約や命名習慣ではなく言語の規則が解決する。 own 宣言子を付ければ、 ブロックを出入りしても値が保存される ── 静的変数の原型もここにある。

そして手続きは自分自身を呼べる。 再帰が仕様に入ったのは会議のごく終盤で、 委員の一部の意に反していたと伝えられる。

商業的成功と、 それを超えた影響

ALGOL 60 は市場を取らなかった。 米欧の研究者が主な使い手で、 商業利用が広がらなかった理由もはっきりしている ── 報告が入出力を定義していない こと、 そして大手計算機ベンダーが関心を示さなかったことである。 入出力の記述は、 1975年の Modified Report まで IFIP の作業部会が扱わなかった。

一方で ALGOL 60 は、 アルゴリズムを発表するための標準記法 になった。 最初の実装は1960年8月、 Edsger W. Dijkstra と Jaap A. Zonneveld が Electrologica X1 向けに書いたものである。 CPL、 PL/I、 Simula、 BCPL、 B、 Pascal、 C ── その後の手続き型言語は、 ほとんどがこの報告の子孫にあたる。

誰が言ったのか

ALGOL 60 について最も広く引かれる評言がある ── 「これは自らの時代をあまりに先んじた言語であり、 その先行者たちに対する改良であったばかりでなく、 後継者のほとんどすべてに対する改良でもあった」（"Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors."）。

これは Perlis の言葉ではない。 C. A. R. Hoare が1973年12月のスタンフォード大学の報告 Hints on Programming Language Design（AIM-224 / STAN-CS-73-403）の末尾に置いた注釈付き読書案内の、 ALGOL 60 報告の項に書いたものである。 同じ箇所で Hoare は、 主要なプログラム構造化の概念をすべて導入したこと、 記述の簡潔さと明快さ、 構文名と方程式で略記を避けたこと、 各節に例を入れたことを挙げている。 Perlis は13名の一人だが、 この言葉の出所ではない。