ALGOL 68
ALGOL 68(源自英語:ALGOrithmic Language 1968的縮寫),一種指令式程式語言,作為ALGOL家族的成員,是官方上的ALGOL 60後繼者。它的設計目標,是提供更廣泛的應用,以及更嚴格的語法定義。
編程範型 | 多范型:指令式,過程式,結構化,並發 |
---|---|
設計者 | 阿德里安·范·韋恩加登, B.J. Mailloux, J.E.L. Peck, C.H.A. Koster等人 |
釋出時間 | 最終報告: 1968年 修訂報告: 1973年 |
型態系統 | 靜態、強類型、安全、結構式 |
網站 | Revised Report on the Algorithmic Language ALGOL 68 |
主要實作產品 | |
Algol68toC[1], ALGOL 68 Genie[2], ALGOL 68-R, ALGOL 68C, ALGOL 68RS, ALGOL 68S, FLACC | |
衍生副語言 | |
ALGOL 68r0 (最終報告:1968年), ALGOL 68r1 (修訂報告:1973年) | |
啟發語言 | |
ALGOL 60, ALGOL X, ALGOL Y | |
影響語言 | |
C[3]、C++[4]、Bourne shell、KornShell、Bash、Steelman、Ada、Python[5]、Seed7、Mary、S3 |
ALGOL 68的特徵包括基於表達式的語法,用戶聲明的類型和結構與標籤聯合類型,變量與引用參數的引用模型,可變長數組和字符串、數組與矩陣的分片,用戶定義的運算符和運算符重載,高階函數與匿名函數,以及並發。
概論
ALGOL 68由IFIP工作組2.1負責設計。1968年12月20日,IFIP工作組2.1通過了這個語法規範,並提交IFIP大會通過且出版。
ALGOL 68的定義使用了阿德里安·范·韋恩加登發明的一種數學形式主義的兩級形式文法。Van Wijngaarden文法使用分別稱為「超規則」和「元產生式規則」的兩組上下文無關文法規則,生成形成一個可能無限的產生式集合,而這些常規的產生式將識別特定的ALGOL 68程序;值得注意的是,它們能夠表達在很多其他程式語言的技術標準中被標記為「語義」的那種要求,其他語言的語義必須用易致歧義的自然語言敘述來表達,並接着在編譯器中實現為附加到形式語言解析器的「特設」代碼。
ALGOL 68設計的主要目標和原則為:
在1970年,ALGOL 68-R成為了第一個投入工作的ALGOL 68編譯器。在1973年9月確定的修訂版本中,省略了特定特徵比如過程化、gomma和形式邊界[6]。Stephen R. Bourne是ALGOL 68修訂委員會成員,他選取了它的一些想法到他的Bourne shell之中。
ALGOL 68曾受到嚴厲批評[8],最突出的是來自其設計委員會的一些成員比如C. A. R. Hoare[9],還有ALGOL 60編譯器作者比如Edsger Dijkstra[10],它獲評為拋棄了ALGOL 60的簡單性,成為了複雜或過於籠統的想法的載體,與刻意保持簡單的同時代(競爭)者如C、S-algol和Pascal形成了鮮明對比。
ALGOL 68的語言定義出版後的文本長達兩百多頁並充斥着非標準術語,這種複雜性使得編譯器實現任務變得困難,故而它曾被稱為「沒有實現也沒有用戶」。這麼說只是部份真實的,ALGOL 68曾應用於一些小眾市場,特別是流行於英國的國際計算機有限公司(ICL)的機器之上,還有在教學角色之上。在這些領域之外,其使用相對有限。
儘管如此,ALGOL 68對計算機科學領域的貢獻是深刻、廣泛而持久的,雖然這些貢獻大多只是在它們於後來開發的程式語言中重現之時才被公開認可。很多語言是為了應對設計這門語言時所採用的形式化方法導致的複雜性而專門開發的,其中最著名的是Niklaus Wirth的ALGOL W及其後繼者Pascal[11],或者是針對特定角色而重新實現的,比如有些人認為Ada可以看作ALGOL 68的後繼者[12]。
1970年代的很多語言可以追溯其設計至ALGOL 68,選取一些特徵,並放棄被認為太複雜或超出給定角色範圍的其他特徵。其中就有C語言,它受到ALGOL 68的直接影響,特別是它的強類型和結構。多數現代語言都至少可以追溯其部份語法至要麼C語言要麼Pascal,因而很多語言可直接或間接的經由C語言而追溯至ALGOL 68。
規定和實現時間線
名稱 | 年 | 國家 | 描述 | 目標CPU/平台 | 屬主/許可證 | 實現語言 |
---|---|---|---|---|---|---|
廣義ALGOL | 1962 | 荷蘭 | 廣義文法的ALGOL[13] | |||
ALGOL 68DR | 1968 | IFIP WG 2.1草案報告[14] | ||||
ALGOL 68r0 | 1968 | IFIP WG 2.1最終報告[15] | ||||
ALGOL 68-R | 1970 | 英國 | GEORGE 3之下的ALGOL 68 | ICL 1900 | 皇家雷達研究所 | ALGOL 60 |
DTSS ALGOL 68 | 1970 | 美國 | Dartmouth分時系統的ALGOL 68[16] | GE-635 | 達特茅斯學院 | |
Mini ALGOL 68 | 1973 | 荷蘭 | 針對簡單ALGOL 68程序的解釋器[17] | 可移植解釋器 | 荷蘭數學中心 | ALGOL 60 |
OREGANO | 1973 | 美國 | 實踐「實現模型的重要性。」[18] | 加州大學洛杉磯分校 | ||
M-220 ALGOL 68 | 1974 | 蘇聯 | 使用EPSILON在M-220上實現ALGOL 68[19] | M-220 | EPSILON | |
ALGOL 68C | 1975 | 英國 | 劍橋大學ALGOL 68實現[20] | ICL,IBM System/360,PDP-10和Unix,Telefunken TR440/TR445,Tesla 200和Z80(1980年)[21] | 劍橋大學 | ALGOL 68C |
ALGOL 68r1 | 1975 | IFIP WG 2.1修訂報告[22] | ||||
ALGOL 68 H | 1975 | 荷蘭, 加拿大 | ALGOL 68編譯器[23] | 阿爾伯塔大學,荷蘭數學中心 | ALGOL W | |
CDC ALGOL 68 | 1975 | 美國 | 完全實現的ALGOL 68[24] | CDC 6000系列,CDC Cyber | 控制數據公司 | |
Odra ALGOL 68 | 1976 | 蘇聯, 波蘭 | Odra 1204/IL | ALGOL 60 | ||
Oklahoma ALGOL 68 | 1976 | 美國 | 俄克拉何馬州立大學ALGOL 68實現[25] | IBM 1130和System/370 Model 158 | 俄克拉何馬州立大學 | ANSI Fortran 66 |
Berlin ALGOL 68 | 1977 | 德國 | 柏林工業大學ALGOL 68實現[26] | 基於抽象ALGOL 68機器的機器無關編譯器 | 柏林工業大學 | CDL 2 |
FLACC | 1977 | 加拿大 | 具有調試特徵的修訂報告完整實現 | System/370 | 租用,Chion公司 | 匯編 |
ALGOL 68RS | 1977 | 英國 | 可移植編譯器 | ICL 2900系列,Multics,VMS和C生成器(1993年) | 皇家信號與雷達研究所 | ALGOL 68RS |
ALGOL 68-RT | 1979 | 英國 | 並行ALGOL 68-R | |||
ALGOL 68+ | 1980 | 荷蘭 | 提議的ALGOL 68的超語言[27] | |||
Leningrad ALGOL 68 | 1980 | 蘇聯 | 列寧格勒國立大學開發的完全語言加上模塊系統 | IBM,DEC,CAMCOH,PS 1001和PC | ||
交互式ALGOL 68 | 1983 | 英國 | 增量編譯,1992年再版MK2[28] | PC | 非商業共享軟件 | |
ALGOL 68S | 1985 | 英國, 美國 | ALGOL 68的子集語言[29][30] | Sun-3,Sun SPARC(在SunOS 4.1和Solaris 2下),Atari ST(在GEMDOS下),Acorn Archimedes(在RISC OS下),VAX-11(在Ultrix-32下) | 利物浦大學,卡內基·梅隆大學,曼徹斯特大學 | BLISS,Pascal |
Rutgers ALGOL 68 | 1990 | 美國, 匈牙利 | Mini ALGOL 68解釋器後續版本[31] | 可移植解釋器 | 寫於羅格斯大學的非商業開源軟件 | C |
Algol68toC | 1993 | 英國 | 基於源自1985年ELLA ALGOL 68RS的ctrans[32][1] | 可移植C生成器 | 國防研究局的皇冠版權開源軟件 | ALGOL 68RS |
ALGOL 68 Genie | 2001 | 荷蘭 | 完全語言包括標準的並立子句[2] | 可移植解釋器;2010年版本2之後,具有可選的選定單元的編譯 | GNU GPL | C |
樣例代碼
下面是Hello World樣例代碼,採用了ALGOL 68RS的程序結構,嚴格的說只有在BEGIN與END之間的諸行是ALGOL 68程序,第一行、第二行和最後一行都特定於a68toc
編譯器。
PROGRAM helloworld CONTEXT VOID
USE standard
BEGIN
print(("hello, world!", newline))
END
FINISH
第一行給出這個程序的標識為helloworld
而且這個名字的文件包含了這個程序;CONTEXT VOID
短語指定這個程序獨立而非嵌入到其他部份之中。第二行的USE
加載了標準預置(prelude),print
就在其中。將上述代碼保存入文本文件helloworld.a68
中,然後使用ALGOL 68RS編譯器a68toc
執行它:
$ ca -u ASDFGHJ helloworld.a68
$ ./helloworld
hello, world!
下面的樣例代碼實現了埃拉托斯特尼篩法來找到小於等於100的所有素數。ALGOL 68中NIL
類似於其他語言中的空指針,x OF y
表示訪問STRUCT y
的成員x
。
BEGIN # ALGOL68的素数筛法,基于链表实现 #
MODE
NODE = STRUCT (INT h, REF NODE t),
LIST = REF NODE;
OP CONS = (INT n, LIST l) LIST: HEAP NODE := NODE (n, l);
PRIO CONS = 9;
PROC one to = (INT n) LIST:
(PROC f = (INT m) LIST: (m > n | NIL | m CONS f(m + 1));
f(1));
PROC error = (STRING s) VOID:
(print((newline, " error: ", s, newline)); stop);
PROC hd = (LIST l) INT:
(l IS NIL | error("hd NIL"); SKIP | h OF l);
PROC tl = (LIST l) LIST:
(l IS NIL | error("tl NIL"); SKIP | t OF l);
PROC show = (LIST l) VOID:
(l ISNT NIL | print((" ", whole(hd(l), 0))); show(tl(l))
| print(newline));
PROC filter = (PROC (INT) BOOL p, LIST l) LIST:
IF l IS NIL THEN NIL
ELIF p(hd(l)) THEN hd(l) CONS filter(p, tl(l))
ELSE filter(p, tl(l))
FI;
PROC sieve = (LIST l) LIST:
IF l IS NIL THEN NIL
ELSE hd(l) CONS sieve(filter(
(INT n) BOOL: n MOD hd(l) NE 0, tl(l)))
FI;
PROC primes = (INT n) LIST: sieve(tl(one to(n)));
show(primes(100))
END
將上述代碼保存入文本文件primes.a68
中,然後使用ALGOL 68 Genie解釋器執行它:
$ a68g primes.a68
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
顯著的語言元素
符號和保留字
標準語言包含六十一個保留字,典型的用粗體字打印,並且其中一些還具有「簡短」符號等價者:
MODE,OP,PRIO,PROC, FLEX,HEAP,LOC,LONG,REF,SHORT, BITS,BOOL,BYTES,CHAR,COMPL,INT,REAL,SEMA,STRING,VOID, CHANNEL,FILE,FORMAT,STRUCT,UNION, AT @,IS :=:, ISNT :/=:,OF →r0,TRUE,FALSE,EMPTY,NIL ○,SKIP ~, COMMENT CO # ¢,PRAGMAT PR, CASE ~ IN ~ OUSE ~ IN ~ OUT ~ ESAC ( ~ | ~ |: ~ | ~ | ~ ), FOR ~ FROM ~ TO ~ BY ~ WHILE ~ DO ~ OD, IF ~ THEN ~ ELIF ~ THEN ~ ELSE ~ FI ( ~ | ~ |: ~ | ~ | ~ ), PAR,BEGIN ~ END ( ~ ),GO TO GOTO,EXIT □r0。
GO TO被當作兩個保留字,未修訂報告的語言還有保留字EITHER和IS NOT結合。
符號表示
「臻選字符」(worthy character)是1977年出版的ALGOL 68標準硬件表示報告出於可移植性而推薦的字符集中的字符[33]:
- A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9
這反映了當年一些硬件不支持在ANSI的ASCII或IBM的EBCDIC之外其他字符的事實。
傳輸表示採用「臻選字符」時,「加上 乘以」符號⊥
替代為I,「乘以 的冪」符號⏨
和\
替代為E。
ALGOL的「特殊」字符:
- × ÷ ≤ ≥ ≠ ≡ ¬ ∧ ∨ ⊃ ↑ ⏨ ␣ ↓ → ⊥ ○ □ ⌊ ⌈ ⎩ ⎧ ¢
多數都可以在1965年出現的配備APL打字球與鍵帽後的IBM 2741終端的鍵盤上找到。這些字符也是Unicode標準的一部份,並且在一些流行的字體中可獲得到。
單元
基本語言構造是「單元」(unit)。單元可以是「公式」、「封閉子句」、「例程正文」這樣的構造,也可以是某個技術上需要的構造諸如賦值、跳轉、越過和空無。
技術術語「封閉子句」(enclosed clause)統一了某些固有的加括號的構造,在其他當代語言中被稱為「塊」、「do語句」、「switch語句」。在使用關鍵字的時候,通常使用介入關鍵字的反轉字符序列來終結這個包圍,比如:IF ~ THEN ~ ELSE ~ FI
、CASE ~ IN ~ OUT ~ ESAC
和FOR ~ WHILE ~ DO ~ OD
。這種守衛命令語法被Stephen Bourne重新使用在常用的Unix Bourne shell之中。
一個表達式還可以產生多元值(multiple value)即有多個元素的一個值,它是通過「並立子句」(collateral clause)從其他一些值構造出來的。這種構造看起來就像過程調用的參數包(pack)。
模態
基本數據類型在ALGOL 68用語中叫做「模態」(mode),其原始聲明符為:INT、REAL、COMPL(複數)、BOOL、CHAR、BITS和BYTES。ALGOL 68不再定義long
、short
和double
這樣的類型,而是提供了修飾符(modifier)LONG和SHORT。
- BITS – BOOL值的包裝向量(packed vector)。
- BYTES – CHAR值的包裝向量。
- LONG – 聲明INT、REAL或COMPL的大小為LONG。
- SHORT – 聲明INT、REAL或COMPL的大小為SHORT。
ALGOL 68提供了預置常量(prelude constant)如max real
和long max real
等來將程序適配到不同實現之中。
所有變量都必須被聲明,但是聲明不必須先於第一次使用。例如:
INT n = 2; # n被固定为常量2 # INT m := 3; # m是新建的局部变量,它的值被初始化为3 # # 这是REF INT m = LOC INT := 3;的简写 # REAL avogadro = 6.02214076E23; # 阿伏伽德罗常数 # LONG LONG REAL long long pi = 3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510; COMPL square root of minus one = 0 I 1; # 复数0 + 1i #
原始聲明符還包括:COMPLEXG、STRING、FORMAT、FILE、PIPEG、CHANNEL和SEMA。
- STRING – CHAR值的FLEX(靈活)元組。
- SEMA – 可以通過運算符LEVEL初始化的信號量。
複雜類型可以使用類型構造子REF、STRUCT、UNION和PROC來創建自更簡單的類型:
- REF
mode
– 到類型mode
的值的引用,類似於C/C++中和Pascal中的指針。 - STRUCT – 用來建造結構,類似於C/C++中的
struct
和Pascal中的recode
。 - UNION – 用來建造聯合,類似於C/C++和Pascal中的
union
。 - PROC – 用來指定過程,類似於C/C++中的函數和Pascal中的過程/函數。
其他聲明符號包括:FLEX、HEAP、LOC、EVENTS。
- FLEX – 所聲明的名字是靈活的,就是說它可以引用任何數量元素的元組。
- HEAP – 為變量從全局堆中分配一些空閒空間。
- LOC – 為變量分配這個局部棧的一些空閒空間。
聲明REAL x;
只是REF REAL x = LOC REAL;
的語法糖。就是說,x
實際上是「常量標識符」,它「引用到」一個新創建的局部REAL變量。
聲明模態(類型)的名字可以使用MODE聲明,它類似於C/C+中的typedef
和Pascal中的type
:
INT max = 99; MODE NEWMODE = [0:9][0:max]STRUCT ( LONG REAL a, b, c, SHORT INT i, j, k, REF REAL r);
這類似於如下C99代碼:
const int max = 99;
typedef struct {
double a, b, c; short i, j, k; float *r;
} newmode[9+1][max+1];
對於ALGOL 68,只有模態標示(indicant)NEWMODE
出現在等號的左側,最值得注意的是,構造的製造和讀取,是從左至右而不顧及優先級的。還有ALGOL 68數組的下界(lower bound)缺省的是1
,但也可以是從-max int
到max int
的任何整數。
模態聲明允許類型是遞歸的:直接或間接的依據自身來進行定義。這要服從一些限制,例如下列聲明是非法的:
MODE A = REF A; MODE A = STRUCT (A a, B b); MODE A = PROC (A a) A;
而下列聲明是有效的:
MODE A = STRUCT (REF A a, B b); MODE A = PROC (REF A a) REF A;
註釋和編譯指導
註釋可以按各種方式插入:
¢ 最初方式是在程序中增加两个美分符号 ¢ COMMENT "粗体"注释 COMMENT CO 风格i注释 CO # 风格ii注释 # £ 针对英国键盘的横杠/英镑注释 £
一般而言,註釋在ALGOL 68中不能嵌套。這個限制可以使用不同的註釋分界符來繞過,比如只對臨時代碼刪除使用井號。
語用指定(pragmat)是在程序中的編譯指導,典型的提示給編譯器;在新近的語言中叫做「pragma」。例如:
PRAGMAT heap=32 PRAGMAT PR heap=32 PR
表達式和複合語句
ALGOL 68成為了面向表達式程式語言,賦值語句所返回的值是到目的地的引用。因此下列代碼在ALGOL 68中是有效的:
REAL half pi, one pi; one pi := 2*(half pi := 2*arc tan(1))
這種表示法也出現在C語言和Perl以及其他一些語言之中。注意在早期語言比如ALGOL 60和FORTRAN中,在標識符中的空格是允許的,所以half pi
是一個單一的標識符,因而無需採用蛇形命名法或駝峰式大小寫。
另一個例子,要表達數學中f(i)
從i=1
到n
的總和,下列ALGOL 68整數表達式就可充任:
(INT sum := 0; FOR i TO n DO sum +:= f(i) OD; sum)
注意,作為整數表達式,上述的代碼塊可以用在「整數值可以使用的任何上下」之中。代碼塊在ALGOL 68稱為「系列子句」(serial clause),它返回其中被求值的最後一個表達式的值;這個概念也出現在LISP以及其他一些語言之上。系列子句加上封閉它的一對圓括號或BEGIN與END叫做閉合子句(closed-clause)。
複合語句都終止於獨特的閉括號:
IF選擇子句
IF 条件 THEN 诸语句 [ ELSE 诸语句 ] FI 简短形式:( 条件 | 诸语句 | 诸语句 )
IF 条件1 THEN 诸语句 ELIF 条件2 THEN 诸语句 [ ELSE 诸语句 ] FI 简短形式:( 条件1 | 诸语句 |: 条件2 | 诸语句 | 诸语句 )
這種方案不僅避免了懸擺else問題,還避免了必須對嵌入的語句序列使用BEGIN
和END
。
CASE選擇子句
CASE 开关 IN 诸语句, 诸语句, ... [ OUT 诸语句 ] ESAC 简短形式:( 开关 | 诸语句, 诸语句, ... | 诸语句 )
CASE 开关1 IN 诸语句, 诸语句, ... OUSE 开关2 IN 诸语句, 诸语句, ... [ OUT 诸语句 ] ESAC 简短形式:( 开关1 | 诸语句, 诸语句, ... |: 开关2 | 诸语句, 诸语句, ... | 诸语句 )
採用簡短符號的選擇子句的例子:
PROC days in month = (INT year, month) INT: (month| 31, (year%*4 = 0 AND year%*100 /= 0 OR year%*400 = 0 | 29 | 28), 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
採用粗體符號的選擇子句的例子:
PROC days in month = (INT year, month) INT: CASE month IN 31, IF year MOD 4 EQ 0 AND year MOD 100 NE 0 OR year MOD 400 EQ 0 THEN 29 ELSE 28 FI, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ESAC;
混合了粗體和簡短符號的選擇子句的例子:
PROC days in month = (INT year, month) INT: CASE month IN #一月# 31, #二月# (year MOD 4 = 0 AND year MOD 100 /= 0 OR year MOD 400 = 0 | 29 | 28), #三月# 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 # 直到十二月 # ESAC;
ALGOL 68允許開關(switch)具有的類型,要麼是INT要麼是(獨有的)UNION。後者允許在UNION變量上施加強類型,參見後面的聯合例子。
DO循環子句
[ FOR 索引 ] [ FROM 第一个 ] [ BY 增量 ] [ TO 最后一个 ] [ WHILE 条件 ] DO 诸语句 OD
循環語句的極小化形式是:DO 诸语句 OD
。
下面是這種「通用」循循的完整例子:
FOR i FROM 1 BY -22 TO -333 WHILE i*i /= 4444 DO ~ OD
這個構造有一些不尋常的方面:
- 只有DO ~ OD部份是強制性的,在這種情況下循環將無限迭代。
- 因此子句 TO 100 DO ~ OD,將只迭代100次。
- WHILE「語法元素」允許編程者更早的從FOR循環中破出,例如:
INT sum sq := 0; FOR i WHILE print(("So far:", i, newline)); sum sq /= 70**2 DO sum sq +:= i**2 OD
後續的對標準ALGOL 68的擴展,允許TO語法元素被替代為UPTO和DOWNTO來達成小優化。這些編譯器還結合了:
- UNTILC – 用於更晚的循環終止。
- FOREACHS – 用於並行的運算於數組之上。
結構與聯合
ALGOL 68支持多字段結構STRUCT和標籤聯合UNION。引用變量可以指向任何MODE,包括數組切片和結構字段。
作為遞歸模態的例子,下面是傳統的鍊表的聲明:
MODE VALUE = UNION (VOID, REAL, INT, COMPL, STRING), NODE = STRUCT (VALUE val, REF NODE next), LIST = REF NODE;
對上述VALUE
的UNION使用共形子句(conformity clause)的CASE的例子:
VALUE v := "1234"; # 或者 v := EMPTY; # CASE v IN (VOID): print(("void:", "EMPTY")), (REAL r): print(("real:", r)), (INT i): print(("int:", i)), (COMPL c): print(("compl:", c)), (STRING s): print(("string:", s)) OUT print("undefined value") ESAC
在未修訂報告的語言中共形子句的功能通過在CASE子句中採用共形關係CTAB來實現。
多元組
在ALGOL 68中,不再採用術語數組或陣列(array),轉而基於數學中的 元組( -tuple)定義了多元值(multiple value)亦簡稱多元組(multiple)。多元組由一定數量的元素組成,每個元素都有相同的模態,有時稱之為基礎模態。多元組的模態由前導着一對方括號的針對每個元素的模態標示組成,它被讀作「成行的模態」(row of mode),它不同於函數式程式語言如ML中的對應於代數數據類型里積類型的「元組」(tuple)。
ALGOL 68多元組的屬性之一是它的維度數目。可以聲明任何數目維度的多元組,整數的二維多元組擁有模態[,]INT
,它被讀作「行套行的整數」(row-row-of-int),而實數的三維多元組擁有模態[,,]REAL
。
MODE VECTOR = [1:3]REAL; # 向量MODE声明 # MODE MATRIX = [1:3,1:3]REAL; # 矩阵MODE声明 # VECTOR v1 := (1,2,3); # 向量变量初始化为 (1,2,3) # []REAL v2 = (4,5,6); # 常量元组,类型等价于VECTOR,边界是隐含的 # OP + = (VECTOR a, b) VECTOR: # 二元OP即运算符定义 # (VECTOR out; FOR i FROM LWB a TO UPB a DO out[i] := a[i]+b[i] OD; out); MATRIX m := (v1, v2, v1+v2);
這裏的冒號分隔構造:第一个元素的下标 : 最后一个元素的下标
,被稱為裁剪器(trimmer)。
ALGOL 68的分片,在概念上涵蓋了向多元組的各個維度加下標(subscript)從而訪問其中特定元素的常規情況,但這個術語更常用的保留給至少一個維度不加下標的情況,比如從矩陣中切分出部份橫行(row)或縱列(column)。例如:
REF VECTOR row = m[2,]; # 定义一个REF至矩阵的第二个横行 # REF VECTOR col = m[,2]; # 定义一个REF至矩阵的第二个纵列 # print ((m[,2:])); # 打印矩阵的从第二个至最后一个的纵列 #
省略了裁剪器中第一個下標則假定其為此維度的下界,而省略了第二個下標則將假定其為對應的上界,兩個下標都省略則產生下界為1
的全部分片。
過程
過程(procedure)的PROC聲明對參數和結果二者要求類型指定,如果沒有則為VOID:
PROC max of real = (REAL a, b) REAL: IF a > b THEN a ELSE b FI;
或者使用條件語句的簡短形式:
PROC max of real = (REAL a, b) REAL: (a > b | a | b);
過程的返回值是在過程中求值的最後一個的表達式的值 。到過程的引用REF PROC也是允許的。提供了傳引用調用參數來在形式參數列表中指定引用,比如REF REAL
。下列例子定義一個過程,它將(作為參數而指定的)一個函數應用於一個數組的每個元素:
PROC apply = (REF [] REAL a, PROC (REAL) REAL f): FOR i FROM LWB a TO UPB a DO a[i] := f(a[i]) OD;
這種代碼的簡單性是在ALGOL 68的前身ALGOL 60中不能達成的。
運算符與關聯名字的單元
過程和運算符(operator)合稱例程(routine),編程者可以定義新的運算符,並且這些自定義的和預定義的運算符二者都可以重載,並且它們的優先級可以由編碼者變更。下列例子定義的運算符MAX
具有二元和一元形式二者,一元形式在一個數組的元素之上進行掃描。
PRIO MAX = 9; OP MAX = (INT a, b) INT: (a > b | a | b); OP MAX = (REAL a, b) REAL: (a > b | a | b); OP MAX = (COMPL a, b) COMPL: (ABS a > ABS b | a | b); OP MAX = ([]REAL a) REAL: (REAL out := a[LWB a]; FOR i FROM LWB a + 1 TO UPB a DO (a[i] > out | out := a[i]) OD; out);
初等和二等單元
初等單元(primary)涵蓋封閉子句,此類屬自身包括:所應用的標識符、調用、鑄型、除了例程指示之外的指示和分片。
所應用的標識符(applied-identifier)意味着標識符在一個上下文之中被使用,並非處在其定義之中。
指示(denotation)比如3.14
或"abc"
,是其所產生與任何行動都無關的構造,在其他語言中,它們有時叫做「文字」(literal)或「常值」(constant)。
鑄型(cast)構成自一個模態標示(indicant)和隨後的通常為閉合子句的封閉子句。鑄型可被用來提供強位置,在強上下文中能獲得所有的強制。例如在REF REAL (xx) := 1
中的REF REAL (xx)
。
調用(call)引起(invoke)一個過程,調用在ALGOL 68 Genie中可以被部份參數化(partial parameterisation):就是說增加實際參數到一個過程的語境(locale)中,當這個語境完全之時調用這個過程,否則發生柯里化。
PRIO | ALGOL68r1「臻選字符」 | ALGOL68G |
---|---|---|
相當於12 | 加下標[~] ,分片[~,~] ,裁剪[~:~] ,AT @
|
DIAG,TRNSP,ROW,COL |
二等單元(secondary)包括生成器(generator)和選取(selection)。
PRIO | ALGOL68r1「臻選字符」 | ALGOL68r0−r1 | ALGOL68G |
---|---|---|---|
相當於11 | OF,LOC,HEAP | → | NEW |
有關的符號在技術上不是運算符,它們轉而被當作「關聯名字的單元」[34]。
三等單元
三等單元(tertiary)包括公式和NIL(可替代為○
)。公式構成自運算符和運算元。
一元運算符
PRIO | ALGOL68r1「臻選字符」 | ALGOL68r1替代符號 | ALGOL68C,G | ALGOL68r0-r1 |
---|---|---|---|---|
相當於10 | NOT,-,UP,DOWN,LWB,UPB,ABS,ARG,BIN,ENTIER,LENG,LEVEL,ODD,REPR,ROUND,SHORTEN | ¬ ~,↑,↓,⌊,⌈ | NORM,TRACE,T,DET,INV | LWS ⎩,UPS ⎧,BTB,CTB |
二元運算符及其關聯的優先級
PRIO | ALGOL68r1「臻選字符」 | ALGOL68r1替代符號 | ALGOL68r0−r1 |
---|---|---|---|
9 | I +* | ⊥ +× | ! |
8 | UP **,DOWN,LWB,UPB,SHL,SHR | ↑,↓,⌊,⌈ | ^ ××,LWS ⎩,UPS ⎧ |
7 | *,/,OVER %,MOD %*,ELEM | ×,÷,÷× ÷* %×,□ | ÷: |
6 | -,+ | ||
5 | LT <,LE <=,GE >=,GT > | ≤,≥ | |
4 | EQ =,NE /= | ≠ ¬= ~= | |
3 | AND | ∧ & | /\ |
2 | OR | ∨ | \/ |
1 | MINUSAB -:=,PLUSAB +:=,TIMESAB *:=,DIVAB /:=,OVERAB %:=,MODAB %*:=,PLUSTO +=: | ×:=,÷:=,÷×:=,÷*:=,%×:= | MINUS,PLUS,TIMES,DIV,OVERB,MODB ÷::=,PRUS |
特殊細節:
- LWS:在ALGOL 68r0中,運算符LWS(可替代為
⎩
),在一個多元組(數組)的這個維度的「下界狀態」為固定的(fixed)的情況下返回TRUE。 - UPS(可替代為
⎧
)運算符針對「上界狀態」。 - LWB和UPB運算符自動的可獲得在一個多元組(數組)的不同階次(和MODE)的UNION之上,例如:
UNION([]INT, [,]REAL, FLEX[,,,]CHAR)
的UPB。
四等單元
四等單元(quaternary)包括:賦值、恆等(identity)關係、例程指示(也稱作例程正文)和SKIP(可替代為~
)。四等單元並非語言報告中的術語,它是給從單元這個類屬中除去封閉子句、初等單元、二等單元和三等單元所餘下的只稱為「單元」的類屬的別名。
PRIO | ALGOL68r1「臻選字符」 | ALGOL68r1替代符號 | ALGOL68C,R | ALGOL68r0−r1 |
---|---|---|---|---|
相當於0 | :=,IS :=:,ISNT :/=: | :≠: :¬=: :~=: | :=:=C,=:=R | ..= .=,IS NOT,CT ::,CTAB ::= |
在ALGOL 68中除了恆等聲明之外的所有構造都有一個值,它允許鏈式賦值,例如a := b := c
,這些賦值是從右至左執行的。
恆等關係包括:IS(可替代為:=:
)測試兩個引用是否相等;ISNT(可替代為:/=:
)測試兩個引用是否不相等。恆等關係的一側是可以解引用來匹配另一側的強側,而另一側則為軟側,不允許兩側都解引用。
強制
強制(coercion)依據三個要件,從被強制者(coercend)產生已強制者(coercee):在應用任何強制之前作為要被強制者的一個先驗模態,在這些強制之後作為已經強制者的一個後驗模態,已強制者的的語法位置(position)或類屬(sort)。強制是可以級聯的(cascaded)。
有7種可能的強制,其術語為解過程化(deproceduring),解引用(dereferencing)和弱解引用(weakly-dereferencing),聯合化(uniting),擴大(widening)、入行(rowing)和棄置(voiding)。除了聯合化之外,每種強制都在所關聯的值之上,規制(prescribe)一個相應的動態效果。因此,可以使用強制來編程很多原始行動。
允許特定強制的境況(circumstance)叫做上下文(context)。下面列出每種上下文所固有的強度及其允許的強制:
- 軟(soft)– 解過程化。
- 弱(weak) – 軟強制,隨後弱解引用而產生一個名字。
- 柔(meek)– 軟強制,隨後解引用。
- 硬(firm)– 柔強制,隨後聯合化。
- 強(strong)– 硬強制,隨後擴大、入行或棄置。
在任何上下文中,都有擁有或產生某種模態的值的一個單元,並且在這個上下文中亦有所需的一個模態。如果兩個模態不同而現有模態的值能夠強制成所需模態的值,則這種強制是合法的。
平衡是將條件、case
和共形子句中的交替者(alternative)即可供選擇者,和恆等關係的兩側,都強制成共同(common)的模態的手段,這使得所涉及構造的上下文會被提升(promote)從而獲得這種強制。
強制層級及例子
ALGOL 68有着上下文層級,它確定在程序中特定點之上可獲得的強制的種類。這種上下文分為五個層次:
上下文 | 上下文位置 | 可獲得的強制 | 在此上下文中強制例子 | ||||
---|---|---|---|---|---|---|---|
軟 | 弱 | 柔 | 硬 | 強 | |||
強 |
|
解過程化 | 只在弱上下文時軟強制再弱解引用 | 軟強制再解引用 | 柔強制再聯合化 | 硬強制再擴大或入行或棄置 |
擴大出現在沒有精度損失的情況下。例如:
變量可以入行為長度為1的元組。例如:
|
硬 |
|
例子:
| |||||
柔 |
|
例子:
| |||||
弱 |
|
例子:
| |||||
軟 |
|
例子:
|
正交性
ALGOL 68文法的表達依據了一些原始概念:值、模態、上下文、強制和短語(phrase)。短語是聲明和單元二者之一。共有5種上下文、7種強制、22種不同的單元,和潛在無窮數量的值和模態。在每種上下文中都有可獲得的強制。
正交性所稱謂的是基本概念可以被沒有副作用的組合。原始概念:值、模態、上下文、強制和短語,是相互獨立的,它們的組合給予了ALGOL 68少有程式語言擁有的靈活性。舉個例子,如果需要模態INT的一個值,比如在多元組的聲明的裁剪器或邊界中,那麼在這個上下文中任何會產生一個整數的單元都可充任。其結果是ALGOL 68程序可以用寬廣多樣的風格來書寫。例如打印從鍵盤讀取的兩個數的總和,用常規風格可以寫為:
INT a, b; read((a, b)); print((a + b, newline))
也可以等價的寫為:
print(((INT a, b; read((a, b)); a + b), newline))
只要所書寫的是合法的ALGOL 68代碼,可以採用編程者喜好的任何方式。這種獨立性的另一個結果是語言的規則極少有例外。
傳輸
傳輸(transput)是ALGOL 68用來稱謂輸入和輸出設施的術語。它包括針對非格式化、格式化和二進制傳輸的預定義的過程。文件和其他傳輸設備以機器無關的方式來處理。下面的例子打印出一些非格式化的輸出到「標準輸出」設備:
print ((newpage, "Title", newline, "Value of i is ", i, "and x[i] is ", x[i], newline))
注意預定義的過程newpage
和newline
作為實際參數而傳送。
print
和read
接受可能具有各種所需模態的實際參數,這些例程的形式參數具有成行的聯合模態:
PROC print = ([]SIMPLOUT items) VOID: …… ; MODE SIMPLOUT = UNION ( INT, REAL, BOOL, CHAR, []INT, []REAL, []BOOL, []CHAR, [,]INT, [,]REAL, [,]BOOL, [,]CHAR, …… ); PROC read = ([]SIMPLIN items) VOID: …… ; MODE SIMPLIN = UNION ( REF INT, REF REAL, REF BOOL, REF CHAR, REF []INT, REF []REAL, REF []BOOL, REF []CHAR, REF [,]INT, REF [,]REAL, REF [,]BOOL, REF [,]CHAR, …… );
read
使用的模態SIMPLIN
是來自各種名字的模態的聯合。print
使用共形子句來從參數行中每個元素提取出實際的值。
在ALGOL 68中「格式化傳輸」擁有自己的語法和模式(函數),具有嵌入在兩個$
字符之間的FORMAT。例如:
printf (($2l"The sum is:"x, g(0)$, m + n)); # 其打印相同于下列: # print ((new line, new line, "The sum is:", space, whole(m + n, 0))
並行處理
ALGOL 68支持並行處理編程。使用關鍵字PAR,可以將「並立子句」轉換成「並行子句」,這裏的行動的同步使用信號量來控制。並行行動在ALOGL 68 Genie中被映射到線程上,如果它們在宿主作業系統上能獲得到的話。例如:
PROC eat = VOID: (muffins -:= 1; print(("Yum!", newline))), speak = VOID: (words -:= 1; print(("Yak...", newline))); INT muffins := 4, words := 8; SEMA mouth = LEVEL 1; PAR BEGIN WHILE muffins > 0 DO DOWN mouth; eat; UP mouth OD, WHILE words > 0 DO DOWN mouth; speak; UP mouth OD END
未修訂報告的語言
原本依據1968年最終報告的語言在模態鑄型的語法上有所不同,並且它擁有過程化(proceduring)這個特徵,就是說,將一個項目的值強制成求值這個項目的一個過程。過程化意圖進行惰性求值。最有用的應用是實現布爾運算符的短路求值:
OP ANDF = (BOOL a, PROC BOOL b) BOOL: (a | b | FALSE); OP ORF = (BOOL a, PROC BOOL b) BOOL: (a | TRUE | b);
在ANDF
中,b
只在a
為TRUE的情況下才求值。預期下面例子中的print
不會被執行:
IF FALSE ANDF (print("Should not be executed"); TRUE) THEN …… FI
語言修訂之後,已經不再允許這種從模態BOOL到模態PROC BOOL的強制和鑄型。ALGOL 68 Genie將ANDF
和ORF
作為擴展而實現為偽運算符。
在語言修訂之前,編程者可以通過使用叫做「gomma」的分號替代逗號(comma),從而決定一個過程的參數串行而非並立的求值。例如:
PROC test = (REAL a; REAL b): …… ; test (x +:= 1, x);
這裏保證第一個實際參數求值在第二個實際參數之前,但是在平常情況:
PROC test = (REAL a, b): …… ; test (x +:= 1, x);
這時編譯器可以按它喜好的次序來求值實際參數。
參見
- ALGOL 60
- ALGOL X
- ALGOL Y
- ALGOL N
- C
- C++
- ALGOL 68與C++的比較
- Bourne shell
- Bash (Unix shell)
註釋
- ^ 1.0 1.1 Neil Matthew. The RSRE Algol-68RS Compiler. May 2021.
An update of the original port by Sian Mountbatten of a68toc (ctrans) from Algol-68RS/ELLA2000 updated to run on Intel and ARM processors (32- and 64-bit) Linux and macOS systems.
- ^ 2.0 2.1 ALGOL 68 Genie. [2020-04-22]. (原始內容存檔於2020-08-14).
- ^ Dennis Ritchie. The Development of the C Language (PDF). April 1993.
The scheme of type composition adopted by C owes considerable debt to Algol 68, although it did not, perhaps, emerge in a form that Algol’s adherents would approve of. The central notion I captured from Algol was a type structure based on atomic types (including structures), composed into arrays, pointers (references), and functions (procedures). Algol 68’s concept of unions and casts also had an influence that appeared later. …… a notation for type conversions (called 『casts』 from the example of Algol 68) was invented to specify type conversions more explicitly.
- ^ A History of C++: 1979−1991 (PDF). Page 12, 2nd paragraph: Algol68 [gave] operator overloading(§3.3.3), references (§3.3.4), and the ability to declare variables anywhere in a block (§3.3.1). March 1993.
- ^ Interview with Guido van Rossum. July 1998 [2007-04-29]. (原始內容存檔於2007-05-01).
String slicing came from Algol-68 and Icon.
- ^ 6.0 6.1 6.2 6.3 Revised Report on the Algorithmic Language Algol 68.
- ^ Adriaan van Wijngaarden. Orthogonal design and description of a formal language (PDF). 1965.
- ^ ALGOL Bulletin 30.1.1.1 "Minority Report". March 1970 [2007-03-01]. (原始內容存檔於2007-09-30).
More than ever it will be required from an adequate programming tool that it assists, by structure, the programmer in the most difficult aspects of his job, viz. in the reliable creation of sophisticated programs. In this respect we fail to see how the language proposed here is a significant step forward: on the contrary, we feel that its implicit view of the programmer's task is very much the same as, say, ten years ago. This forces upon us the conclusion that, regarded as a programming tool, the language must be regarded as obsolete.
- ^ Hoare, C. a. R. Critique of ALGOL 68. ALGOL Bulletin. November 1968, 29: 27–29.
I believe that the essential problem in the design of self-extending languages is in the design of the nucleus of built-in features, which the implementor will be expected to represent within the machine code of his computer. It is essential that this nucleus should have the properties: 1. Extreme simplicity and small size …… 2. Extreme efficiency of implementation …… I would therefore reckon that a language at about the level of FORTRAN would be a suitable choice for a nucleus. The language nucleus described in MR93 is far too elaborate; and some of its defects are listed in Appendix II.
- ^ Dijkstra, E. W. To the Editor ALGOL 68 Mathematische Centrum. [2007-04-28]. (原始內容存檔於2007-04-21).
On account of the draft report my faith in WG.2.1 (at least in its present constitution) is very low. The draft report is thick and difficult, in fact too thick and too difficult to inspire much confidence. …… Size and complexity of the defining apparatus you needed terrify me. Being well-acquainted with your ingenuity I think it a safe assumption that ALGOL 68 as conceived can hardly be defined by significantly more concise and transparent means. …… I feel inclined to put the blame on the language you tried to define. If this is correct, WG.2.1 should return to its proper subject matter, viz. programming languages.
- ^ Niklaus Wirth. ALGOL Colloqium – Closing Word. 1968.
The implied and rather vague goal was the specification of a universal language, a sensible goal in 1960, even 1964, but an utopia in 1968; a goal which if pursued faithfully, invariably lead towards a monster language, a species of which there already exists a sample hardly worth nor possible to compete with.
- ^ Learning Algol 68 Genie (PDF).
Some claim that Ada is Algol 68’s successor but many dispute that.
- ^ Adriaan van Wijngaarden. Generalized ALGOL (PDF). Symbolic Languages in Data Processing, Proc. Symp. Intl, Computation Center Rome, Gordon & Beach, New York. 1962.
- ^ Van Wijngaarden, A.; Mailloux, B. J.; Peck, J.; Koster, C. H. A. Draft Report on the Algorithmic Language ALGOL 68. ALGOL Bulletin. 1 March 1968, (Sup 26): 1–84 [7 April 2023] –透過Mar. 1968.
- ^ Report on the algorithmic language ALGOL 68. 1969.
- ^ Sidney Marshall. J. E. L. Peck , 編. ALGOL 68 Implementation (PDF). Proceedings of the IFIP Working Conference on ALGOL 68 Implementation, Munich,: 239–243. July 20–24, 1970.
Sidney Marshall. On the implementation of ALGOL 68 (PDF). PhD Thesis, Dartmouth College. 1972. - ^ L. Ammeraal. An interpreter for simple Algol 68 Programs (PDF). 1973.
- ^ Daniel M. Berry. The importance of implementation models in ALGOL 68: or how to discover the concept of necessary environment.
- ^ "Application of the Machine-Oriented Language Epsilon to Software Development", I.V. Pottosin et al., in Machine Oriented Higher Level Languages, W. van der Poel, N-H 1974, pp. 417–434
- ^ Algol68C Release 1.3039 for IBM 360/370/etc mainframes (or their emulations) running MVT or MVS. March 2013.
- ^ Liverpool Software Gazette March 1980 (PDF). [2010-03-20]. (原始內容 (PDF)存檔於2010-04-15).
- ^ Revised report on the algorithmic language ALGOL 68 (PDF). 1976.
- ^ Hendrik Boom. 1978 branch of Algol 68 H development tree. 2008.
- ^ ALGOL 68 Version I Reference Manual (PDF). Control Data Services B.V., Rijswijk, Netherlands. 1976.
- ^ ALGOL68 instruction at Oklahoma State University.
- ^ "The Berlin ALGOL 68 implementation"
An abstract ALGOL 68 machine and its application in a machine independent compiler – Springer. Springerlink.com. Retrieved on 2013-07-21. - ^ Algol 68+, a superlanguage of Algol 68 for processing the standard-prelude (PDF). 1981.
- ^ a68mk2.zip. (原始內容存檔於2006-08-29).
- ^ Hibbard, P.G. A Sublanguage of ALGOL 68. SIGPLAN Notices. May 1977, 12 (5): 71–79. S2CID 37914993. doi:10.1145/954652.1781177 .
- ^ Dr C. H. Lindsey. The ALGOL 68S System. 1988.
- ^ Laci Csirmaz. An ALGOL 68 interpreter, lots of sample programs. You can learn the usage of UNION types. 2000.
- ^ Dr Sian Mountbatten. A68ToC port to Debian Linux. Version 1.15. Sep 13 2012.
- ^ Report on the Standard Hardware Representation of Algol 68. 16 May 1977.
- ^ Units associated with names.
參考文獻
- Brailsford, D. F. and Walker, A. N. Introductory ALGOL 68 Programming. Ellis Horwood/Wiley. 1979.
- Lindsey, C. H. and van der Meulen, S. G. Informal Introduction to ALGOL 68 : Revised Edition. (PDF). North-Holland. 1981.
- Lindsey, C. H. A History of ALGOL 68. ACM SIGPLAN Notices. 1993-03-02, 28 (3): 97–132. doi:10.1145/155360.155365 .
- McGettrick, A. D. ALGOL 68, A First and Second Course. Cambridge Univ. Press. 1978.
- Peck, J. E. L. An ALGOL 68 Companion. Univ. of British Columbia. October 1971.
- Tanenbaum, A. S. A Tutorial on ALGOL 68. Computing Surveys 8, 155-190, June 1976 and 9, 255-256. September 1977.
- Woodward, P. M. and Bond, S. G. ALGOL 68-R Users Guide. London, Her Majesty's Stationery Office. 1972.
外部連結
- Revised Report on the Algorithmic Language ALGOL 68(頁面存檔備份,存於互聯網檔案館) The official reference for users and implementors of the language (large pdf file, scanned from Algol Bulletin)
- Revised Report on the Algorithmic Language ALGOL 68(頁面存檔備份,存於互聯網檔案館) Hyperlinked HTML version of the Revised Report
- A Tutorial on Algol 68, by Andrew S. Tanenbaum, in Computing Surveys, Vol. 8, No. 2, June 1976, with Corrigenda (Vol. 9, No. 3, September 1977)
- Algol 68 Genie – a GNU GPL Algol 68 compiler-interpreter(頁面存檔備份,存於互聯網檔案館)
- Open source Algol 68 implementations, on SourceForge(頁面存檔備份,存於互聯網檔案館)
- Algol68 Standard Hardware representation (.pdf)(頁面存檔備份,存於互聯網檔案館)
- Из истории создания компилятора с Алгол 68(頁面存檔備份,存於互聯網檔案館)
- Algol 68 – 25 Years in the USSR(頁面存檔備份,存於互聯網檔案館)
- Система программ динамической поддержки для транслятора с Алгол 68
- C history with Algol68 heritage
- McJones, Paul, "Algol 68 implementations and dialects"(頁面存檔備份,存於互聯網檔案館), Software Preservation Group, Computer History Museum, 2011-07-05
- Web enabled ALGOL 68 compiler for small experiments