ALGOL

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

主なバージョン

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

ALGOL 58

当初 IAL (International Algebraic Language) という名称で提案された。

ALGOL 60

1960年中ごろに X1 ALGOL 60 として実装されたのが最初で、1963年に改訂された。

ALGOL 68

1968年に発表され、1973年に改訂された。可変配列、スライス、並列性、演算子識別、その他の拡張可能な機能などが新たに導入されている。

IAL (ALGOL 58) は後の様々なプログラミング言語（いわゆるALGOL系言語）に大きな影響を及ぼし、一般にそれらの先祖とみなされている。また、ALGOLの仕様で示された中間コードは ALGOL object code と呼ばれ、単純でコンパクトなスタックベースの命令セットアーキテクチャであり、計算機科学の分野でコンパイラ構築の教育に使われ、他の高水準言語の実装にも使われた。

歴史

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

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

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

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

このパリでの会議（1960年1月1日から16日まで開催）には以下の人々が参加している。

ヨーロッパからの参加者

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

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

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

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

実装例

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

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

特徴

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

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

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

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

しかし、ALGOLの設計者は名前渡しをデフォルトとした。また、言語処理系実装者たちは名前渡しの実現にThunk(サンク)という興味深い技法を編み出した。現在、素朴な（ALGOLのような）名前渡しは完全に廃れたが、サンクは遅延（非正格）評価を実装する一般的な手法として知られる。ドナルド・クヌースは処理系が「再帰呼び出しと非局所的参照」を正しく実装しているかを評価するman or boy testを考案した。このテストには名前呼び出しの例が含まれている（クヌースらは他にも、名前渡しの「悪用」とでも言うべきJensen's Deviceと後に呼ばれるようになるような技法の一例を示した "ALGOL 60 Confidential"など、仕様のコーナーケースを暴き、コンピュータ・プログラミング言語設計の難しさをあらわにした）。

ALGOL の影響として、後の言語のうちの最も多くに影響があるものは、BEGIN/END（C 言語などでは{ }）の入れ子によるブロック構造化、つまり次のような典型的な形の記法であろう。

 BEGIN
   X := 1 ;
   IF (X > 0) THEN
     BEGIN
       :
     END
 END

俗に「ALGOL 文法」といった場合は、このブロック構造化記法のことを指していることがある（C言語のように他の記号を使うものも含めて指していることもあれば、そうではなくてBEGIN/ENDのようにキーワードを使う、という意味で言っていることもある）。後の静的スコープの言語についても、ALGOLからの影響と言われることがある。

例と移植性問題

コード例の比較

ALGOL 60

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

 PROCEDURE Absmax(a) Size:(n, m) Result:(y) Subscripts:(i, k) ;
     VALUE n, m ; ARRAY a ; INTEGER n, m, i, k ; REAL y ;
 COMMENT The absolute greatest element of the matrix a, of size n by m
     is transferred to y, and the subscripts of this element to i and k ;
 BEGIN
     INTEGER p, q ;
     y := 0 ; i := k := 1 ;
     FOR p := 1 STEP 1 UNTIL n DO
         FOR q := 1 STEP 1 UNTIL m DO
             IF abs (a[p, q]) > y THEN
                 BEGIN
                     y := abs (a[p, q]) ;
                     i := p; k := q
                 END
 END Absmax

次の例は 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(3),££L??'
   B := SIN(A)'
   C := COS(A)'
   PRINT PUNCH(3),SAMELINE,ALIGNED(1,6),A,B,C'
 END'
 END'

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

ALGOL 68

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

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

 PROC ABS max = ([,]real a, REF real y, REF int i, k)real:
 COMMENT The absolute greatest element of the matrix a, of size ⌈a by 2⌈a
 is transferred to y, and the subscripts of this element to i and k; COMMENT
 BEGIN
    real y := 0; i := ⌊a; k := 2⌊a;
    FOR p FROM ⌊a TO ⌈a DO
      FOR q FROM 2⌊a TO 2⌈a DO
        IF ABS a[p, q] > y THEN
            y := ABS a[p, q];
            i := p; k := q
        FI
      OD
    OD;
    y
 END # abs max #

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

 floating point algol68 test:
 (
   real a,b,c,d;
   
   printf(($pg$,"Enter d:"));
   read(d);
   
   FOR step FROM 0 WHILE a:=step*d; a <= 2*pi DO
     printf($l$);
     b := sin(a);
     c := cos(a);
     printf(($z-d.6d$,a,b,c))
   OD
 )

printf はファイル stand out に出力を送る。printf($p$); は改頁、printf($l$); は改行である。printf(($z-d.6d$,a,b,c)) は小数点以上を1桁、小数点以下を6桁にフォーマットして出力する。

Hello world の変遷

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

ALGOL 58 (IAL)

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

ALGOL 60 ファミリ

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

 BEGIN
   FILE F(KIND=REMOTE);
   EBCDIC ARRAY E[0:11];
   REPLACE E BY "HELLO WORLD!";
   WRITE(F, *, E);
 END.

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

 BEGIN
   FILE F(KIND=REMOTE);
   WRITE(F, <"HELLO WORLD!">);
 END.

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

 BEGIN DISPLAY("HELLO WORLD!") END.

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

 program HiFolks;
 begin
    print ‘Hello world’;
 end;

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

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

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

  'BEGIN'
     'WRITE TEXT'("HELLO WORLD");
  'END'

ALGOL 68

ALGOL 68 のコードは一般に太字または下線つきの小文字で予約語を表す（ただし、以下の例はシンタックスハイライトのために大文字にしている）。

 BEGIN
   printf(($gl$,"Hello, world!"))
 END

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

ALGOLの特殊文字の変遷

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

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

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

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

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

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

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

脚注

注釈

出典

参考文献

• F.L. Bauer, R. Baumann, M. Feliciano, K. Samelson, Introduction to Algol. Prentice Hall, 1964, ISBN 0-13-477828-6
• B. Randell and L.J. Russell, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer. Academic Press, 1964. The design of the Whetstone Compiler. コンパイラの実装についての初期の解説の1つ。関連する論文として次がある。
  • Whetstone Algol Revisited by B. Randell
  • The Whetstone KDF9 Algol Translator 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. [1]

関連図書

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

関連項目

• ISWIM
• Simula
• Scheme

外部リンク

• Algol 68 Genie - GPL配布によるフリーのALGOL 68 インタプリタ
• Algol60 compiler and interpreter - MS-DOS上で動くフリーのALGOL60コンパイラが配布されている。
• Revised Report on the Algorithmic Language Algol 60 by Peter Naur, et al. ALGOLの定義
• Execute ALGOL-68 Script Online ブラウザ上でオンラインで ALGOL 68 を実行 by Mohtashim
• ALGOL 60 のBNFによる syntax summary
• History of ALGOL at the Computer History Museum
• MARST - フリーなALGOLからCへのトランスレータ (User Guide)
• AN IMPLEMENTATION OF ALGOL 60 FOR THE FP6000 実装上の問題についての議論がある。
• "The European Side of the Last Phase of the Development of ALGOL 60" by Peter Naur
• エリック・レイモンドの Retrocomputing Museum には、C言語で書かれた NASE Algol-60 インタプリタへのリンクがある。
• STORIES ABOUT THE B5000 AND PEOPLE WHO WERE THERE By Richard Waychoff
• TrueType font containing U+23E8 Decimal Exponent Symbol（ttfファイル）