ALGOL

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2014年3月9日 (日) 20:31時点におけるケイ20003 (トーク)による版 (花園明朝の挙動がおかしいので撤去)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

テンプレート:Infobox プログラミング言語 テンプレート:プログラミング言語 ALGOLアルゴル)は、命令型プログラミング言語ファミリの1つ[注 1]。名前「ALGOL」は「アルゴリズム言語」を意味する英語「algorithmic language」に由来する。1950年代中ごろに開発され、多くの言語に影響を及ぼし、ACMや教科書や学術論文などでアルゴリズム記述のデファクトスタンダードとして30年以上使われた[1]。現代の多くの言語が「ALGOL系」あるいは「ALGOL風」(algol-like) とされているという意味で[2]、ほぼ同世代の高水準言語である FORTRANLISPCOBOL に比べて最も成功したと言うこともできる。FORTRANで明らかとなった問題を防ぐよう設計され、BCPLBPascalSimulaCといった様々なプログラミング言語に影響を与えた。ALGOLはコードブロックを導入し、beginend でそれを囲むことで、構文スコープネスティングを可能にした最初の言語となった。また言語の形式的定義を真剣に検討した最初のプログラミング言語でもあり、"Algol 60 Report"[3] で言語設計の主要な記法となったバッカス・ナウア記法を導入している。

主なバージョン

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

テンプレート:仮リンク
当初 IAL (International Algorithmic Language) という名称で提案された。
テンプレート:仮リンク
1960年中ごろに X1 ALGOL 60 として実装されたのが最初で、1963年に改訂された[3][4]
テンプレート:仮リンク
1968年に発表され、1973年に改訂された[5]。可変配列、スライス、並列性、演算子識別、その他の拡張可能な機能などが新たに導入されている。

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) と改称することを提案した[6]

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

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

ヨーロッパからの参加者
テンプレート:仮リンクピーター・ナウアテンプレート:仮リンクテンプレート:仮リンク、Bernard Vauquois、テンプレート:仮リンク、Michael Woodger
アメリカからの参加者
ジョン・バッカス、Julien Green、Charles Katz、ジョン・マッカーシーアラン・パリス、Joseph Henry Wegstein

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

ALGOL 60 はその後の多数の言語に影響を与えた。アントニー・ホーアは「時代に先行していて、それまでの言語の改良だっただけでなく、その後のほぼ全ての後継者の先駆者となった言語」と評している[8]Schemeというプログラミング言語はLISPからの派生だが、ALGOLのブロック構造と構文スコープを取り入れ、文書の題名も "Revised Report on the Algorithmic Language Scheme" としてALGOLへのオマージュを表している[9]

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年になって、ISOALGOL 60 相当の言語が標準化されたのみである。日本では、かつて ALGOL 60 の言語規格と入出力ライブラリ規格をそれぞれJIS規格で制定していたが (JIS C 6210-6219)、1983年(昭和58年)9月1日付で廃止された。

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

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

実装例

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

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

名称 作者 説明 対象CPU
ZMMD-implementation 1958年 Bauer, Rutishauser, Samelson, Bottenbruch ドイツ ALGOL 58 の実装 Z22
(後にツーゼのZ23[12]向けに ALGOL 60 コンパイラを提供している)
X1 ALGOL 60 1960年8月[13] エドガー・ダイクストラ、 Jaap A. Zonneveld オランダ ALGOL 60 の世界初の実装[14] Electrologica X1
Elliott ALGOL 1960年代 アントニー・ホーア イギリス Elliott 803 & Elliott 503
JOVIAL 1960年 Jules Schwarz アメリカ Ada以前の DOD HOL 各種
Burroughs Algol
(いくつか派生がある)
1961年 バロース(ホーアやダイクストラも参加) アメリカ バロースのメインフレーム(およびユニシスの後継シリーズ)の基盤 バロースの大型機
および中型機
Case ALGOL 1961年 ケース・ウェスタン・リザーブ大学[15] アメリカ 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 EVMBESM
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 上にも実装)

特徴

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

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

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

ALGOL 60 では引数渡しに2種類の評価戦略が定義されている。一般的な値渡しALGOL に特徴的な名前渡しである。名前渡しは遅延評価の一種と考えられ、命令型言語では使いこなすのが難しい機能でもある。例えば、2つの引数の値を入れ替える手続きを書いたとき、ある整数変数とその整数変数を添え字とする配列要素をその引数として渡すことができない[16]。すなわち 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 系文法は、記述力と可読性のバランスが良好で、類似の文法をもつ言語は SimulaPascalModulaModula-2Modula-3OberonAdaVHDLVerilog-HDLLolaEiffel など複数存在する。

例と移植性問題

コード例の比較

ALGOL 60

次のコードは ALGOL 60 で n × m の2次元配列の中から絶対値が最大の要素を求め、その絶対値をyに、添え字をikに格納する手続きを記述したものである。なお、コード中で強調表示されている予約語の記法は処理系に依存する。例えば "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[17] で表を生成する方法を示したものである。

 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 にあるコード例を単純化したものである[18]

 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 では、当時のほとんどのコンピュータではサポートされていない数学記号がいくつか使われていた。例えば、×, ÷, ≤, ≥, ≠, ¬, ∨, ∧, ⊂, ≡, ␣, [注 3] などである。

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

1962年、テンプレート:仮リンクは2つの珍しい文字、"᛭" (iron/runic cross) と "⏨" (Decimal Exponent Symbol) を浮動小数点形式で使用するためにALGOLの文字セットに加えた[20][21][22]

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

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

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

脚注

テンプレート:脚注ヘルプテンプレート:Reflist

出典

テンプレート:Reflist

参考文献

  • 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つ。関連する論文として次がある。
  • 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]

関連項目

外部リンク


引用エラー: 「注」という名前のグループの <ref> タグがありますが、対応する <references group="注"/> タグが見つからない、または閉じる </ref> タグがありません
  1. Collected Algorithms of the ACM ACMによるアルゴリズム集
  2. テンプレート:Cite web
  3. 3.0 3.1 テンプレート:Cite book
  4. テンプレート:Cite web
  5. テンプレート:Cite web
  6. テンプレート:Cite journal
  7. ACM Award Citation / Peter Naur, 2005
  8. "Hints on Programming Language Design", C.A.R. Hoare, December 1973. Page 27. (なお、この言葉は間違ってエドガー・ダイクストラのものとされることがある。ダイクストラも ALGOL 60 コンパイラの実装に参加していた)
  9. テンプレート:Cite web
  10. Peter O'Hearn and Robert D. Tennent. 1996. Algol-Like Languages. Birkhauser Boston Inc., Cambridge, MA, USA.
  11. テンプレート:Cite web
  12. Computer Museum History, Historical Zuse-Computer Z23, restored by the Konrad Zuse Schule in Hünfeld, for the Computer Museum History Center in Mountain View (California) USA
  13. テンプレート:Cite journal
  14. テンプレート:Cite book
  15. テンプレート:Cite web
  16. テンプレート:Cite book, Section 7.5, and references therein
  17. "803 ALGOL", the manual for Elliott 803 ALGOL
  18. Hello world! ALGOL Example Program page
  19. How ASCII Got Its Backslash, Bob Bemer
  20. テンプレート:Cite journal
  21. テンプレート:Cite journal
  22. テンプレート:Cite journal
  23. テンプレート:Cite web