ALGOL

テンプレート:Infobox プログラミング言語 テンプレート:プログラミング言語 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つの主要な仕様が存在する。後ろについている数は最初に発表された年を表している。

テンプレート:仮リンク

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

テンプレート:仮リンク

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

テンプレート:仮リンク

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

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

歴史

1950年代後半、FORTRAN等の言語が米国で作られていたのに対抗して、ヨーロッパの研究者が、世界共通のプログラミング言語として開発した。1958年にチューリッヒ工科大学で行われた国際会議で提案されたのが起源とされる。その仕様は3つの異なる構文規則、reference syntax、publication syntax、implementation syntax を含んだもので、キーワード名や小数点に使用する記号（カンマかピリオドか）を選べるようになっていた。

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日まで開催）には以下の人々が参加している。

ヨーロッパからの参加者

テンプレート:仮リンク、ピーター・ナウア、テンプレート:仮リンク、テンプレート:仮リンク、Bernard Vauquois、テンプレート:仮リンク、Michael Woodger

アメリカからの参加者

ジョン・バッカス、Julien Green、Charles Katz、ジョン・マッカーシー、アラン・パリス、Joseph Henry Wegstein

アラン・パリスはこの会議について、「会合は疲れさせるもので、果てしなく、活発だった。ある人のよいアイデアが悪いアイデアと共に却下されると、その人は機嫌を損ねた。それにもかかわらず、期間中ずっと勤勉さが持続した。13人の作用は素晴らしいものだった」と評している。

ALGOL 60 はその後の多数の言語に影響を与えた。アントニー・ホーアは「時代に先行していて、それまでの言語の改良だっただけでなく、その後のほぼ全ての後継者の先駆者となった言語」と評している。Schemeというプログラミング言語はLISPからの派生だが、ALGOLのブロック構造と構文スコープを取り入れ、文書の題名も "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 60 やその方言を指すのが一般的である。

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

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

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

実装例

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

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

名称	年	作者	国	説明	対象CPU
ZMMD-implementation	1958年	Bauer, Rutishauser, Samelson, Bottenbruch	ドイツ	ALGOL 58 の実装	Z22 （後にツーゼのZ23向けに ALGOL 60 コンパイラを提供している）
X1 ALGOL 60	1960年8月	エドガー・ダイクストラ、 Jaap A. Zonneveld	オランダ	ALGOL 60 の世界初の実装	Electrologica X1
Elliott ALGOL	1960年代	アントニー・ホーア	イギリス		Elliott 803 & Elliott 503
JOVIAL	1960年	Jules Schwarz	アメリカ	Ada以前の DOD HOL	各種
Burroughs Algol （いくつか派生がある）	1961年	バロース（ホーアやダイクストラも参加）	アメリカ	バロースのメインフレーム（およびユニシスの後継シリーズ）の基盤	バロースの大型機 および中型機
Case ALGOL	1961年	ケース・ウェスタン・リザーブ大学	アメリカ	Simulaは Case ALGOL のシミュレーション向け拡張として開発された。	UNIVAC 1107
GOGOL	1961年	Bill McKeeman	アメリカ	ODINタイムシェアリングシステム向け	PDP-1
RegneCentralen ALGOL	1961年	ピーター・ナウア、Jørn Jensen	デンマーク	ALGOL 60 の完全実装	DASK (Regnecentralen)
Dartmouth ALGOL 30	1962年	テンプレート:仮リンク 他	アメリカ		LGP-30
USS 90 Algol	1962年	L. Petrone	イタリア
Algol Translator	1962年	G. van der Mey, W.L. van der Poel	オランダ	オランダ国営電話会社	ZEBRA
Kidsgrove Algol	1963年	F. G. Duncan	イギリス		イングリッシュ・エレクトリック KDF9
VALGOL	1963年	Val Schorre	アメリカ	META II コンパイラジェネレータのテストとして開発
Whetstone	1964年	Brian Randell, L J Russell	イギリス		イングリッシュ・エレクトリック KDF9
NU ALGOL	1965年		ノルウェー		UNIVAC
ALGEK	1965年		ソビエト連邦	ALGOL 60 とCOBOLに基づいた経済タスク用	Minsk-22
MALGOL	1966年	publ. A. Viil, M Kotli & M. Rakhendi	エストニア・ソビエト社会主義共和国		Minsk-22
ALGAMS	1967年	GAMS（中型機のための自動プログラミング）グループとコメコン科学アカデミーの共同開発	コメコン		Minsk-22、後に ES EVM、BESM
ALGOL/ZAM	1967年		ポーランド		ZAM（ポーランド製）
Simula 67	1967年	オーレ＝ヨハン・ダール、クリステン・ニゴール	ノルウェー	ALGOL 60 にオブジェクト指向を導入	UNIVAC 1107
Chinese Algol	1972年		中国	漢字を表示可能
DG/L	1972年	データゼネラル	アメリカ		Eclipseファミリ
S-algol	1979年	Ron Morrison	イギリス	直交データ型を追加。教育向け	PDP-11（後に Java VM 上にも実装）

特徴

同時期の 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の制作者は名前渡しを好み、その実装に「テンプレート:仮リンク」という興味深い技法を使った。ドナルド・クヌースは ALGOL 60 コンパイラが「再帰呼び出しと非局所的参照」を正しく実装しているかを評価する "man or boy test" を考案した。このテストには名前呼び出しの例が含まれている。

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

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

俗に「ALGOL 文法」といった場合は、このブロック構造化記法のことを指している。

式と文を持ち、字下げ(必須ではないが)されたブロック構造で手続きを記述していくという ALGOL 系文法は、記述力と可読性のバランスが良好で、類似の文法をもつ言語は Simula、Pascal、Modula、Modula-2、Modula-3、Oberon、Ada、VHDL、Verilog-HDL、Lola、Eiffel など複数存在する。

例と移植性問題

コード例の比較

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 UNIT 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のブーリアン演算子 "テンプレート:Backslash/" と "/テンプレート:Backslash" をサポートするためにバックスラッシュ (テンプレート:Backslash) が初期段階で追加された。

1962年、テンプレート:仮リンクは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]

関連項目

• 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ファイル）