ALGOL

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

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

特徴

同時期の 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の設計者は名前渡しをデフォルトとした。また、言語処理系実装者たちは名前渡しの実現に「サンク」（en:Thunk (functional programming)）という興味深い技法を編み出した。現在、素朴な（ALGOLのような）名前渡しは完全に廃れたが、サンクは遅延（非正格）評価を実装する一般的な手法として知られる。ドナルド・クヌースは処理系が「再帰呼び出しと非局所的参照」を正しく実装しているかを評価するman or boy test（en:Man or boy test）を考案した。このテストには名前呼び出しの例が含まれている（クヌースらは他にも、名前渡しの「悪用」とでも言うべきJensen's Device（en: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" と称している。