ALGOL

enは、命令型プログラミング言語ファミリーの1つ。名前「en」は「アルゴリズム言語」を意味する英語「en」に由来するP.HAYES。1950年代中ごろに開発され、多くの言語に影響を及ぼし、ACMや教科書や学術論文などでアルゴリズム記述のデファクトスタンダードとして30年以上使われた。現代の多くの言語が「ALGOL系」あるいは「ALGOL風」 とされているという意味で、ほぼ同世代の高水準言語である FORTRAN、LISP、COBOL に比べて最も成功したと言うこともできる。FORTRANで明らかとなった問題を防ぐよう設計され、BCPL、B、Pascal、Simula、Cといった様々なプログラミング言語に影響を与えた。ALGOLは「begin と end で囲む」という構文によるブロック構造を導入し、制御構造を自在に入れ子にできる初の広まった言語となった。また構文の形式的定義を真剣に検討した最初のプログラミング言語でもあり、"Algol 60 Report" で導入されたバッカス・ナウア記法は、その後のコンピュータ言語等の構文の形式的定義を示す手法として定番の記法となっている。

1. 主なバージョン
----------

次の3つの主要な仕様が存在する。後ろについている数は最初に発表された年を表している。

当初 IAL  という名称で提案された。 1960年中ごろに //X1 ALGOL 60// として実装されたのが最初で、1963年に改訂された。 1968年に発表され、1973年に改訂された。可変配列、スライス、並列性、演算子識別、その他の拡張可能な機能などが新たに導入されている。IAL  は後の様々なプログラミング言語に大きな影響を及ぼし、一般にそれらの先祖とみなされている。また、ALGOLの仕様で示された中間コードは ALGOL object code と呼ばれ、単純でコンパクトなスタックベースの命令セットアーキテクチャであり、計算機科学の分野でコンパイラ構築の教育に使われ、他の高水準言語の実装にも使われた。

2. 歴史
-----

1950年代後半、en等の言語が米国で作られていたのに対抗して、ヨーロッパの学術研究者が世界共通のプログラミング言語として開発した。ALGOLは1958年にチューリッヒ工科大学で行われた国際会議で提案されたものが起源とされる。現代のプログラミング言語と比べて著しく異なる点のひとつに、reference syntax、publication syntax、implementation syntax という3種類の構文がある、ということが挙げられる。当時は文字コードの標準化以前であり、また数学の数式のように印刷したいという要望などもあったため、そのようなことになっている。これにより、キーワード名や小数点に使用する記号を選ぶことなどもできた。

ALGOL 58 は主に欧米の計算機科学者がアルゴリズムの研究開発に用いた。商用アプリケーションにはあまり採用されていない。その原因は入出力機能が標準仕様に含まれていなかったためであり、またバロース以外の大手コンピュータメーカーがこの言語に興味を示さなかったためである。

ジョン・バッカスは ALGOL 58 を主たる対象としてプログラミング言語の文法を記述するバッカス正規記法  を開発した。ピーター・ナウアはそれを ALGOL 60 向けに拡張・改訂。ドナルド・クヌースがバッカス・ナウア記法  と改称することを提案した。

ピーター・ナウアは //ALGOL Bulletin// という学術誌の編集者としてこの言語の国際的議論に参加し、1959年11月にヨーロッパの言語設計グループの一員に選ばれた。そして "Algol 60 Report" の編集者となり、1960年1月にパリで開催された ALGOL 60 についての国際会議の結果を発表した。

このパリでの会議には以下の人々が参加している。

ヨーロッパからの参加者 フリードリッヒ・L・バウアー、ピーター・ナウア、ハインツ・ルティシュハウザー、クラウス・サメルソン、Bernard Vauquois、アドリアン・ファン・ワインハールデン、Michael Woodger アメリカからの参加者 ジョン・バッカス、Julien Green、Charles Katz、ジョン・マッカーシー、アラン・パリス、Joseph Henry Wegsteinアラン・パリスはこの会議について、「会合は疲れさせるもので、果てしなく、活発だった。ある人のよいアイデアが悪いアイデアと共に却下されると、その人は機嫌を損ねた。それにもかかわらず、期間中ずっと勤勉さが持続した。13人の作用は素晴らしいものだった」と評している。

ALGOL 60 はその後の多数の言語に影響を与えた。アントニー・ホーアは ALGOL 60 を「時代に先行していて、それまでの言語の改良だっただけでなく、その後のほぼ全ての後継者の先駆者となった言語」と評している。SchemeというLisp方言の設計者は、その静的スコープは ALGOL からの影響だと述べている。またSchemeの仕様の名称 "Revised Report on the Algorithmic Language Scheme" もALGOLへのオマージュである。

1968年には、後継として en 68 が開発された。en 68 では、2段階文法のワインハールデン記法で文法が記述された。en 60 の後継言語制定に至るまでの候補としてニクラウス・ヴィルトの en、日本で設計された en 等もあったが最終的に en 68 が後継として制定された。しかし、あまりに複雑かつ巨大な仕様のため en 68 コンパイラの実装は難しく、またワインハールデン記法が難解なこともあり実用的には、ほとんど普及しなかった。そのため単に ALGOL と言った場合にはALGOL 68 ではなくて ALGOL 60 やその方言を指すのが一般的である。

言語の標準化としては、IFIP TC2/WG2.1 において en 60 が制定された。その後、遅々として標準化作業はすすまず、1984年になって、ISOで en 60 相当の言語が標準化されたのみである。日本では、かつて en 60 の言語規格と入出力ライブラリ規格をそれぞれJIS規格で制定していたが 、1983年9月1日付で廃止された。

2.1. ALGOLとプログラミング言語研究
----------------------

ピーター・ランディンが指摘したように、ALGOLは命令型の副作用とラムダ計算を一体に結合した初の言語である。この言語の最も見事な定式化はおそらくジョン・C・レイノルズによるもので、その文法および意味論の純粋さをよく表している。レイノルズの「理想化した」ALGOLも名前渡しの言語のコンテキストにおける「ローカル」な副作用の適切さについて説得力のある方法論的主張を行っており、MLのような値渡しの言語が使用する「グローバル」な副作用と対比される。ALGOLの概念的完全性により、Programming Computable FunctionsやMLと共に意味論研究の主な対象とされるようになった。

2.2. 実装例
--------

これまでに ALGOL 60 の強化版、拡張版、派生版、サブ言語などが少なくとも70ほど存在した。

ALGOL 60 の実装に関する問題は、Nicholas Enticknap と Pat Woodroffe の書いた "[1]" で詳しく議論されている。



3. 特徴
-----

同時期の en、en と比べると、これらの言語が特定のハードウェア上で特定の目的を効率良くこなすための一種のドメイン特化型言語から始まったのに対し、en はいったんハードウェアの特性は置いておき、抽象的なアルゴリズムを手続きとして記述する事を目指している。初期の en 60 仕様では入出力手続きすら標準化されていなかった点から見ても、できる限り言語コアの抽象度を上げようとしていたことは想像に難くない。en、en が直系子孫以外に余り枝分かれをしていないのに対して、en 系が大きな多様性を獲得したのもこの抽象性による所が大と言える。従って en の策定をもって、ソフトウェアのモジュール化、計算機の汎用化が始まった瞬間と捉えても差し支えないであろう。

en 60 は、手続き型言語として再帰呼び出しが可能な初めてのプログラミング言語である。

公式の en 60 では入出力機能が定義されていなかったため、実際の処理系ではそれぞれに互換性のない方法で実装された。それに対して、en 68では transputのための豊富なライブラリが提供された。

en 60 では引数渡しに2種類の評価戦略が定義されている。一般的な値渡しと en に特徴的な名前渡しである。名前渡しは実際のところ、手続き型言語では扱いがかなり難しい。例えば、2つの引数の値を入れ替える手続きを書いたとき、ある整数変数とその整数変数を添え字とする配列要素をその引数として渡すことができない。すなわち swap という場合である。乱数関数を渡す場合にも問題が生じる。

しかし、ALGOLの設計者は名前渡しをデフォルトとした。また、言語処理系実装者たちは名前渡しの実現にThunkという興味深い技法を編み出した。現在、素朴な名前渡しは完全に廃れたが、サンクは遅延評価を実装する一般的な手法として知られる。ドナルド・クヌースは処理系が「再帰呼び出しと非局所的参照」を正しく実装しているかを評価するman or boy testを考案した。このテストには名前呼び出しの例が含まれている。

en の影響として、後の言語のうちの最も多くに影響があるものは、BEGIN/ENDの入れ子によるブロック構造化、つまり次のような典型的な形の記法であろう。 俗に「en 文法」といった場合は、このブロック構造化記法のことを指していることがある。後の静的スコープの言語についても、ALGOLからの影響と言われることがある。

4. 例と移植性問題
----------

4.1. コード例の比較
------------

4.1.1. ALGOL 60
---------------

次のコードは en 60 で n × m の2次元配列の中から絶対値が最大の要素を求め、その絶対値をyに、添え字をiとkに格納する手続きを記述したものである。なお、コード中で強調表示されている予約語の記法は処理系に依存する。例えば "INTEGER" は "integer" と書かれることもある。

次の例は Elliott 803 ALGOL で表を生成する方法を示したものである。

FLOATING POINT ALGOL TEST' BEGIN REAL A,B,C,D'

READ D'

FOR A:= 0.0 STEP D UNTIL 6.3 DO BEGIN PRINT PUNCH,££L??' B := SIN' C := COS' PRINT PUNCH,SAMELINE,ALIGNED,A,B,C' END' END'

PUNCH は紙テープのさん孔装置ではなくテレタイプ端末のプリンターへ出力を送るものである。SAMELINE は引数間で通常行われる復帰改行を抑制する。ALIGNED は出力を小数点以上を1文字、小数点以下を6文字とするようフォーマットする。

4.1.2. ALGOL 68
---------------

次のコード例は上掲の ALGOL 60 のコード例の ALGOL 68 版である。

ALGOL 68 でも ALGOL 60 のストロッピングを再利用している。

なお、lower  と upper  は配列の境界を示し、配列を走査する際の添え字の範囲指定に使える。

//printf// はファイル //stand out// に出力を送る。//printf;// は改頁、//printf;// は改行である。//printf)// は小数点以上を1桁、小数点以下を6桁にフォーマットして出力する。

4.2. Hello world の変遷
--------------------

ALGOLの各種実装における移植性の無さは、Hello World プログラムで簡単に示すことができる。

4.2.1. ALGOL 58 
---------------------

ALGOL 58 には入出力機能が存在しないので、例示できない。

4.2.2. ALGOL 60 ファミリ
--------------------

ALGOL 60 にも入出力機能がないので、Hello World プログラムの移植性はない。以下に示すのはユニシスのメインフレームで今も使用可能なALGOLの実装に対応したもので、ミシガン大学の [2] にあるコード例を単純化したものである。

インラインフォーマットを使ったさらに単純なプログラムは次のようになる。

Display文を使うとさらに次のように単純化される。

もう1つの例として Elliott Algol のコード例を示す。Elliott Algol は引用開始符号と引用終了符号とで異なる文字を使用する。

program HiFolks;beginprint ‘Hello world’;end;

次は Elliott 803 Algol  の例である。Elliott 803 は標準では5孔の紙テープを使用するので、大文字しか使えない。引用符として使える文字もないため、ポンド記号  を引用開始、疑問符  を引用終了に使用している。特殊シーケンスは二重引用内に置かれる。

HIFOLKS' BEGIN PRINT £HELLO WORLD£L??' END'

ICT 1900シリーズのALGOLでは、紙テープまたはパンチカードを入力として利用可能である。紙テープは小文字も使用可能である。出力はラインプリンターに対して行う。 'BEGIN' 'WRITE TEXT'; 'END'

4.2.3. ALGOL 68
---------------

ALGOL 68 のコードは一般に太字または下線つきの小文字で予約語を表す。

"Algol 68 Report" では、入出力を "transput" と称している。

4.3. ALGOLの特殊文字の変遷
------------------

ALGOLは文字セットが急速に発展し多様化していた時代に登場した。また、ALGOLは大文字だけで記述できるよう定義されていた。

1960年の情報処理国際連合  で発表された ALGOL 60 では、当時のほとんどのコンピュータではサポートされていない数学記号がいくつか使われていた。例えば、×, ÷, ≤, ≥, ≠, ¬, ∨, ∧, ⊂, ≡, ␣, ⏨ などである。

1961年9月、初期のASCII文字セットが登場し、ALGOLのブーリアン演算子 "/" と "/" をサポートするためにバックスラッシュ  が初期段階で追加された。

1962年、ALCORは2つの珍しい文字、"᛭"  と "⏨"  を浮動小数点形式で使用するためにALGOLの文字セットに加えた。

1964年、ソビエト連邦が策定したGOST規格 GOST 10859 で、ALGOL用の4ビット、5ビット、6ビット、7ビットの文字セットを定義した。

1968年の "Algol 68 Report" では既存のALGOL用文字セットに加えて、IBM 2741 端末で使用可能な →, ↓, ↑, □, ⌊, ⌈, ⎩, ⎧, ○, ⊥, ¢}} という文字を加えた。このレポートはロシア語、ドイツ語、フランス語、ブルガリア語に翻訳され、それぞれの言語向けに文字セットが拡張された。例えばソビエト連邦のBESM-4はキリル文字が使用可能だった。ALGOLの使用する全ての文字はUnicode規格の一部になっており、その大部分は主要なフォントが対応している。

2009年10月、浮動小数点形式記述のための "⏨"  が Unicode 5.2 に追加された。これはブランで使われたALGOLソフトウェアとの後方互換を保つためである。

5. 脚注
-----

5.1. 注釈
-------

5.2. 出典
-------

6. 参考文献
-------

F.L. Bauer, R. Baumann, M. Feliciano, K. Samelson, //Introduction to Algol//. Prentice Hall, 1964, ISBN 0-13-477828-6
[5]. The design of the Whetstone Compiler. コンパイラの実装についての初期の解説の1つ。関連する論文として次がある。
[6] by B. Randell
[7] by B. Randell
E. W, Dijkstra, //Algol 60 translation: an algol 60 translator for the x1 and making a translator for algol 60//, report MR 35/61. Mathematisch Centrum, Amsterdam, 1961. [8]

7. 関連図書
-------

森口繁一：「ＡＬＧＯＬ入門」、日本科学技術連盟、。
Eric Foxley and Henry R. Neave:"A FIRST COURCE IN ALGOL60", Addison-Wesley Pub., .
エリック フォクスレイ、ヘンリイ Ｒ．ニーヴ、岸田孝一：「プログラミングＡＬＧＯＬ入門」、日本生産性本部。

8. 関連項目
-------

ISWIM
Simula
Scheme

9. 外部リンク
--------

[9] - GPL配布によるフリーのen 68 インタプリタ
[10] - MS-DOS上で動くフリーのALGOL60コンパイラが配布されている。
[11] by Peter Naur, et al. ALGOLの定義
[12] ブラウザ上でオンラインで ALGOL 68 を実行 by Mohtashim
ALGOL 60 のBNFによる [13]
[14] at the Computer History Museum
[15] - フリーなALGOLからCへのトランスレータ 
[17] 実装上の問題についての議論がある。
[18]
エリック・レイモンドの [19] には、C言語で書かれた NASE Algol-60 インタプリタへのリンクがある。
[20] By Richard Waychoff
[21]