AI tools

ALGOL 60

来自维基百科，自由的百科全书

ALGOL 60（源自ALGOrithmic Language 1960的縮寫），是在1960年創建的稱為「算法語言」的一種程式語言。它是以後來稱為ALGOL 58的「國際代數語言」為基礎，其官方後繼者是ALGOL 68，它們一起並稱為ALGOL語言家族。Algol 60引進了許多新的概念如：塊、詞法作用域、遞歸[2]、巴科斯-諾爾範式（BNF），它在程式語言設計和發展演化中有着巨大的影響力。

快速預覽 編程範型, 語言家族 ...
ALGOL 60
編程範型指令式，過程式，結構化
語言家族ALGOL
設計者Bauer（英語：Friedrich L. Bauer）, Rutishauser（英語：Heinz Rutishauser）, Samelson（英語：Klaus Samelson）, 巴科斯, Katz（英語：Charles Katz）, 佩利, Wegstein（英語：Joseph Henry Wegstein）, 諾爾, Vauquois（英語：Bernard Vauquois）, 范·韋恩加登, Woodger（英語：Michael Woodger）, J. Green, 麥卡錫
釋出時間1960年，​65年前​（1960）
當前版本
  • ISO 1538:1984（1984年10月15日）[1]
編輯維基數據鏈接
型態系統靜態, 強類型
作用域詞法
啟發語言
ALGOL 58
影響語言
ALGOL 68, 所有「類似ALGOL語言」比如: Simula, Pascal, C等, ISWIM, Scheme
關閉

歷史

1960年，在巴黎舉行的討論會上，來自歐洲的諾爾、Bauer（英語：Friedrich L. Bauer）、Rutishauser（英語：Heinz Rutishauser）、Samelson（英語：Klaus Samelson）、范·韋恩加登、Vauquois（英語：Bernard Vauquois）、Woodger（英語：Michael Woodger），與來自美國的佩利、巴科斯、麥卡錫、Katz（英語：Charles Katz）、Wegstein（英語：Joseph Henry Wegstein）和J. Green，共同發表了《算法語言ALGOL 60報告》[3]。戴克斯特拉實現了ALGOL 60語言的第一個編譯器。在1962年羅馬會議上，ALGOL 60報告得到了修訂，並於1963年出版[4]。

ALGOL 60是程式語言發展史上的一個里程碑，影響到其後的Simula、CPL、ALGOL W、ISWIM、BCPL、B、Pascal、C、Scheme等。它標誌着程式語言成為一門獨立的科學學科，並為後來軟件自動化及軟件可靠性的發展奠定了基礎。

標準

ALGOL 60以及COBOL，是最初的企圖標準化的程式語言。ALGOL60曾經提出兩項ISO標準：

  • ISO 1538: 1984年，程式語言ALGOL 60[5]，它已穩固化。
  • ISO 1672: 1977年，ALGOL基本符號的ISO 7位編碼字符集硬件表示[6]，它已撤消。

實現時間線

ALGOL 60在語言報告中沒有I/O設施；諸多實現以少有相互兼容的方式定義了自己的設施。迄今ALGOL 60已經有了至少70個擴充、擴展、派生和子語言[7]。

更多資訊 名字, 年份 ...
名字 年份 作者 國家 描述 目標CPU
X1 ALGOL 60 1960年8月[8] Edsger W. Dijkstra和Jaap A. Zonneveld  荷蘭 第一個ALGOL 60實現[9] Electrologica X1（英語：Electrologica X1）
ALGOL 1960[10] Edgar T. Irons  美國 ALGOL 60 CDC 1604（英語：CDC 1604）
Burroughs ALGOL（英語：Burroughs large systems#ALGOL）（及一些變體） 1961 Burroughs公司（英語：Burroughs Corporation）（有Hoare、Dijkstra和其他人參與）  美國 以Burroughs（後來基於Unisys MCP（英語：Burroughs MCP））計算機為基礎。Burroughs方言包括了特殊系統編程方言比如ESPOL（英語：Executive Systems Problem Oriented Language）和NEWP（英語：NEWP）。 Burroughs大型系統（英語：Burroughs large systems）和中型系統（英語：Burroughs Medium Systems）。
Case ALGOL 1961  美國 Simula最初簽約為Case ALGOL的模擬器擴展 UNIVAC 1107（英語：UNIVAC 1100/2200 series）
GOGOL 1961 William M. McKeeman  美國 用於ODIN分時系統 PDP-1
DASK ALGOL 1961 Peter Naur，Jørn Jensen（英語：Jørn Jensen）  丹麥 ALGOL 60 Regnecentralen（英語：Regnecentralen）的DASK（英語：DASK）
SMIL ALGOL 1962 Torgil Ekman，Carl-Erik Fröberg  瑞典 ALGOL 60 隆德大學的SMIL（英語：SMIL (computer)）
GIER ALGOL 1962 Peter Naur，Jørn Jensen（英語：Jørn Jensen）  丹麥 ALGOL 60 Regnecentralen（英語：Regnecentralen）的GIER
Dartmouth ALGOL 30（英語：Dartmouth ALGOL 30）[11] 1962 Thomas Eugene Kurtz（英語：Thomas Eugene Kurtz），Stephen J. Garland，Robert F. Hargraves，Anthony W. Knapp（英語：Anthony W. Knapp），Jorge LLacer  美國 ALGOL 60 LGP-30（英語：LGP-30）
Alcor Mainz 2002 1962 Ursula Hill-Samelson，Hans Langmaack  德國 Siemens 2002
ALCOR-ILLINOIS 7090 1962[12][13] Manfred Paul，Hans Rüdiger Wiehle，David Gries（英語：David Gries），Rudolf Bayer  美國， 西德 ALGOL 60，伊利諾伊大學和慕尼黑工業大學的實現，1962年-1964年 IBM 7090
USS 90 ALGOL 1962 L. Petrone  意大利
Elliott ALGOL（英語：Elliott ALGOL） 1962 C. A. R. Hoare  英國 在他的1980年圖靈獎演講中討論 Elliott 803（英語：Elliott 803） & Elliott 503（英語：Elliott 503）
ALGOL 60 1962 Roland Strobel[14]  東德 由柏林德國科學院（英語：German Academy of Sciences at Berlin）應用數學研究所實現 Zeiss-Rechenautomat ZRA 1
ALGOL 60 1962 Bernard Vauquois（英語：Bernard Vauquois），Louis Bolliet[15]  法國 格勒諾布爾計算機科學與應用數學研究所(IMAG)和Bull機器公司 Bull Gamma 60（英語：Bull Gamma 60）
ALGOL Translator 1962 G. van der Mey，W.L. van der Poel（英語：Willem van der Poel）  荷蘭 荷蘭國家郵政局，電報電話 ZEBRA（英語：ZEBRA (computer)）
Kidsgrove ALGOL 1963 F. G. Duncan  英國 英國電氣公司（英語：English Electric）KDF9（英語：English Electric KDF9）
SCALP[16] 1963 Stephen J. Garland，Anthony W. Knapp（英語：Anthony W. Knapp），Thomas Eugene Kurtz（英語：Thomas Eugene Kurtz）  美國 作為ALGOL 60子集的自齊備Algol處理器 LGP-30（英語：LGP-30）
VALGOL 1963 Val Schorre  美國 META II（英語：META II）編譯器的編譯器的測試品
FP6000 ALGOL 1963 Roger Moore（英語：Roger Moore (computer scientist)）  加拿大 為Saskatchewan電力公司（英語：SaskPower）寫作 FP6000（英語：Ferranti-Packard 6000）
Whetstone（英語：Whetstone (benchmark)） 1964[17] Brian Randell（英語：Brian Randell），Lawford John Russell  英國 英國電氣公司原子能部。以Ferranti Pegasus（英語：Ferranti Pegasus）為前提，國家物理實驗室ACE和English Electric DEUCE（英語：English Electric DEUCE）實現。 英國電氣公司KDF9（英語：English Electric KDF9）
ALGOL 60 1964 Jean-Claude Boussard[18]  法國 格勒諾布爾信息與數學應用研究所 IBM 7090
ALGOL-GENIUS 1964 Börje Langefors  瑞典 增加受COBOL啟發的數據記錄和I/O Datasaab（英語：Datasaab） D-21
ALGOL 60 1965 Claude Pair[19]  法國 南錫科學學院計算中心 IBM 1620（英語：IBM 1620）
Dartmouth ALGOL 1965 Stephen J. Garland，Sarr Blumson，Ron Martin  美國 ALGOL 60 用於GE 235（英語：GE-200 series）的Dartmouth分時系統（英語：Dartmouth Time Sharing System）
NU ALGOL 1965  挪威 UNIVAC
ALGOL 60 1965[20] F.E.J. Kruseman Aretz  荷蘭 用於EL-X8的MC編譯器 Electrologica X8（英語：Electrologica X8）
ALGEK 1965  蘇聯 АЛГЭК，基於ALGOL-60並支持COBOL，用於經濟任務 Minsk-22（英語：Minsk family of computers）
MALGOL 1966 publ. A. Viil，M Kotli，M. Rakhendi 愛沙尼亞蘇維埃社會主義共和國 愛沙尼亞SSR Minsk-22（英語：Minsk family of computers）
DJS-6 ALGOL 1966  中國 華北計算所 DJS-6
ALGAMS 1967 GAMS組織（ГАМС，中型機器自動化編程小組），協作於Comecon科學院 經濟互助委員會 Minsk-22（英語：Minsk family of computers），後來的ES EVM（英語：ES EVM），BESM（英語：BESM）
ALGOL/ZAM 1967  波蘭 波蘭ZAM計算機
DG/L（英語：DG/L） 1972  美國 DG Eclipse（英語：Data General Eclipse）計算機家族
NASE[21] 1990 Erik Schoenfelder  德國 解釋器 Linux和MS Windows
MARST[22] 2000 Andrew Makhorin  俄羅斯 ALGOL 60到C轉換器 GNU編譯器套件支持的全部CPU；MARST是GNU計劃成員
關閉

詞法

簡單符號

除了字母和數字之外，ALGOL定義了運算符：

更多資訊 優先級, 運算符 ...
優先級 運算符
第一
算術		 第一 ↑（冪）
第二 ×，/（實數），÷（整數）
第三 +，-
第二 <，≤，=，≥，>，≠
第三 ¬（非）
第四 ∧（與）
第五 ∨（或）
第六 ⊃（蘊涵）
第七 ≡（等價）
關閉

和分界符（英語：Delimiter）:

, . ⏨ : ; ≔ ␣
( ) [ ] ‘ ’

在ISO 1672標準中，用:=表示≔（U+2254），用*表示×；用%表示÷，用**或^表示↑，用@表示科學記數法中指數運算的底數10所用符號⏨（U+23E8），用{表示‘，並且用}表示’，用空格 表示在字符串中的空白字符␣（U+2423）。

關鍵字

ALGOL 60有24個關鍵字：

  • array
  • begin
  • Boolean
  • comment
  • do
  • else
  • end
  • false
  • for
  • go to
  • if
  • integer
  • label
  • own
  • procedure
  • real
  • step
  • string
  • switch
  • then
  • true
  • until
  • value
  • while

還包括標準函數名字作為限制標識符：

  • abs
  • sign
  • sqrt
  • sin
  • cos
  • arctan
  • ln
  • exp
  • entier

關鍵字寫法依賴於實現，常見的是一種叫做索繞（英語：Stropping (syntax)）（stropping）的方法，即將關鍵字大寫並包圍在兩個'之間，例如將go to寫為'GOTO'。在ISO 1672標準中關鍵字還包括對特定符號的某種文字轉寫：

更多資訊 符號, 轉寫 ...
符號 轉寫 符號 轉寫 符號 轉寫 符號 轉寫
[ '(/' ] '/)' ‘ '(' ’ ')'
< 'LT' > 'GT' ≤ 'LE' ≥ 'GE'
= 'EQ' ≡ 'EQV' ≠ 'NE' ¬ 'NOT'
∧ 'AND' ∨ 'OR' ⊃ 'IMPL' ÷ '/'
關閉

語義

塊與作用域

在ALGOL 60中，「複合語句」被定義為：包圍在語句括號begin和end之間的成序列的語句，形成一個複合語句。塊被定義為：成序列的聲明，跟隨着成序列的語句，並被包圍在begin和end之間，形成一個塊；所有聲明以這種方式出現在一個塊中，並只在這個塊中有效。[23]

一個程序是特定的一個塊或複合語句，它不包含在另一個語句之中，並且不使用不包含在它之中的其他語句。在1976年的修改版語言報告中，程序只能包含在叫做「環境塊」的假定總是存在的一個虛構塊之中，除了可以使用在環境塊中聲明的過程標識符和函數指定符之外，不使用不包含在它之中的其他語句。

量（quantity）被區分出如下種類：簡單變量、數組、標籤、switch（switch列表由標籤組成[24]）和過程。聲明負擔定義在程序中用到的量的特定屬性，並給它們關聯上標識符。聲明包括：類型聲明、數組聲明、switch聲明和過程聲明。量的作用域是語句和表達式的集合，在其中關聯於這個量的標識符的聲明是有效的。所有的塊，自動地介入名稱目錄（英語：Nomenclature）（nomenclature）的一個新的層級：

  • 在這個塊內出現的標識符，可以通過合適的聲明，而被指定為局部於所論及的這個塊。這個標識符在這個塊裏面的所表示的實體，不存在於它的外面。這個標識符在這個塊外面的所表示的任何實體，在這個塊裏面是不可見的。
  • 除了表示標籤的標識符之外，一個標識符，如果出現在一個塊中，而且並非聲明於這個塊中，則它非局部（英語：Non-local variable）於這個塊[25]，就是說它在這個塊裏面和在緊鄰其外的層級中所表示的是同一個實體。
  • 因為塊中的語句自身可以是一個塊，局部和非局部於一個塊的概念，必須遞歸地去理解，就是說非局部於一個塊A的一個標識符，可是亦可否地，非局部於A是其中語句的塊B。

這動態的蘊涵了：在通過begin進入一個塊的時候，所有為這個塊聲明的標識符，假定了這個給定聲明的本性（英語：Nature (philosophy)）所蘊涵的意義（英語：Meaning (philosophy)）（significance）；如果這些標識符已經被外面的其他聲明所定義，這時它們被給予新的意義；在另一方面，並非為這個塊聲明的標識符，保持它們舊有的含義。在通過end或go to語句退出一個塊的時候，為這個塊聲明的標識符失去它們的局部意義。聲明可以標記上額外的聲明符own，其效果為：在重新進入一個塊的時候，自有的這些量的值將不變更而仍是上次退出時的值，然而聲明的沒有標記上own的變量的值是未定義的。

表達式和語句

在描述算法處理的程序中，主要構成者是算術表達式、布爾表達式，和得到語句標籤的指定（designational）表達式。除了特定的分界符之外，表達式的構成者包括：邏輯值、數值、變量、函數指定式，和基本的算術、關係、邏輯運算符（operator）及順序運算符。用以形成語句的關鍵字，在ALGOL 60中被歸入順序運算符和分隔符之中。

變量是對一個單一值的指名（designation（英語：Designation (law)））。下標（subscripted）變量指定（designate）多維數組的元素的值，這裏將數組元素稱為「組成元件」（component）[26]。函數指定式（designator）定義單一的數量值或邏輯值，它們是將給定的由過程聲明定義的規則集合，應用於固定的實際參數集合的結果。

現在通常將變量定義為抽象的存儲位置，它含有了被稱為一個值的某種已知或未知的信息量，並且配對了關聯的符號（英語：Symbol (programming)）名字。在ALGOL 60中，某些語法單位，比如表達式及其構成者和數組標識符，被稱為擁有值。各種「類型」即integer、real和Boolean，指稱（denote）值的基本的屬性。

在左圓括號和匹配的右圓括號之間的表達式（parenthesized expression）自行求值，而這個值被用於後續的計算之中；因此通過適當的圓括號放置，總是可以在表達式之內安排出想要的運算次序。

ALGOL 60將語句分為三類：無條件語句、條件語句和for語句。賦值語句擔負將表達式的值，指派（assign）到一個或多個變量，或者在定義函數指定式的值的過程主體中指派到過程標識符；在作為指派目標的下標變量中出現的任何下標表達式，先於得出所指派之值的表達式，而按從左至右順序求值。空無的虛設（dummy）語句不執行任何運算。過程語句負擔實施調用一個過程主體的執行。

控制流程語句包括：go to跳轉語句、條件語句、for循環語句。go to語句結合了無條件go to和計算go to二者，goto語句不能從塊外跳轉到塊內的標籤，但可以跳轉進入複合語句。條件語句包括if語句（即if <布尔表达式> then <无条件语句>），和if語句經由關鍵字else與隨後的語句聯合在一起的形式（即<if语句> else <语句>）。ALGOL 60在if語句和for語句中介入了子句概念，算術表達式、布爾表達式和指定表達式，可以是條件表達式（即if ~ then ~ else ~）[27]。

由於變量和函數指定式二者的語法定義都包含表達式，表達式及其構成者的定義必須是遞歸的。由於成序列的語句，可以被組織成複合語句和塊，語句的定義必需是遞歸的。ALGOL 60採用了左遞歸的巴科斯範式（BNF）。

過程

在ALGOL 60中，過程聲明擔負定義過程標識符所關聯的過程，其主要構成者是過程主體，它是一個語句或一段代碼。過程主體總是表現得如同一個塊，不管它是否有着塊的形式；故而標記了在過程主體內語句或者主體自身的標籤的作用域，永遠不能延伸超出這個過程主體[28]。

過程主體關聯着一個頭部，它規定了出現在過程主體內的代表形式參數的特定標識符。過程的參數傳遞有兩種求值策略：傳名調用和傳值調用。在過程聲明中，通過對形式參數名字前導value來指定傳值調用，缺省為傳名調用。在過程主體是用ALGOL語言寫的語句的情況下，過程語句執行它的效果，等價於在程序上進行下列操作的效果：

  • 聲明為傳值調用的形式參數，都要被賦值即指派上對應的實際參數的值，這些指派被認為是在進入過程主體之前顯式進行的。其效果如同創建了包圍着這個過程主體的一個額外的塊，在其中所做的這些指派針對的是局部於這個虛構塊的變量，它們具有在相應規定中給出的類型。作為結論，傳值調用的變量，被認為非局部（英語：Non-local variable）於過程主體，但是局部於這個虛構塊。
  • 聲明為傳名調用的形式參數，在整個過程主體內，要被替代為對應的實際參數，並且只要語法上可能就對這些實際參數包圍上圓括號。在通過這個名字替代處理而插入的標識符，和已經存在於過程主體之內的其他標識符，二者之間的可能衝突，將憑藉對涉及到的（這個過程主體的）形式標識符或局部標識符的適合的系統性變更來避免[29]。
  • 最終經過上述修改後的過程主體，被插入到過程語句的位置上並被執行。如果調用這個過程的位置，處在這個過程主體的任何非局部量[30]的作用域的外面，在通過這個過程主體替代處理而插入的標識符，和在這個過程語句或函數指定式所在位置上其聲明有效的標識符，二者之間的可能衝突，將通過（在發起調用的這個層級上）對後者標識符的適合的系統性變更來避免[31]。

對於定義函數指定式的值的過程聲明，在其過程主體中，必須出現具有過程標識符在其左側部份中的一個或多個賦值語句，其中至少有一個必須被執行；並且這個過程標識符所關聯的類型，必須通過以類型聲明符作為其過程聲明的最先符號的樣貌來聲明。最後那個這樣指派的值，被用來繼續此函數指定式在其中出現的表達式的求值。在這個過程主體中，這個過程標識符的不在賦值語句左側部份中的任何出現，指示了這個過程的激活（activation）。

兩個傳名調用形式參數，其對應的實際參數之間可能存在依賴關係，比如第一個是整數變量i，而第二個是下標變量A[i]，從而導致後者形式參數也依賴於前者形式參數，利用傳名調用和這種副作用可以實現Jensen設備（英語：Jensen's Device）[32]；它典型的用於定義對應於的級數過程Sum(k, l, u, ak)，它有兩個傳名調用的形式參數：索引變量k和通項（general）表達式ak。

對於交換兩個參數的值的swap(x, y)過程，其過程主體定義為：t:=x; x:=y; y:=t，這種依賴性副作用會導致可能出現異常行為，由於名字替代機制相當於宏展開（expansion），過程語句swap(i, A[i])中下標變量A[i]的下標i未經求值，對應的過程主體就轉換成為：t:=i; i:=A[i]; A[i]:=t。1964年IFIP（英語：International Federation for Information Processing）工作組2.1（英語：IFIP Working Group 2.1）制定了《SUBSET ALGOL 60報告》，在這個子集語言中對「完全的名字概念」（full name-concept）增加了一項限制：在名字替代（傳名調用）中，實際參數只能是一個標識符或字符串。

在過程的參數列表( … <参数分界符> … )中，有可選的「) <字母串>: (」樣式的參數分界符（英語：Delimiter）[33]。眾所周知的傳名調用實現採用了thunk（英語：Thunk）[a][35]。Donald Knuth設計了「男人抑或男孩測試」，來區分編譯器是否正確的實現了「遞歸和非局部引用」，這個測試用到了傳名調用。

例子

下面是語言報告中過程聲明的一個例子[b]： 

procedure Absmax(a) Size:(n, m) Re​sult:(y) Subscripts:(i, k);
    value n, m; array a; integer n, m, i, k; real y;
    comment 矩阵a，其大小为n乘m，其绝对值最大的
        元素被传送到y，并且这个元素的下标是i和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

在1976年修改版語言報告的環境塊中，定義了輸入輸出過程：inchar、outchar、length、outstring、outterminator、ininteger、outinteger、inreal和outreal，下面以其中的outinteger作為演示例子： 

procedure outinteger(channel, int);
    value channel, int;
    integer channel, int;
    comment 将表示int的值的那些字符，
        加上尾随的终结符传递到channel。 ;
begin
    procedure digits(int);
        value int; integer int;
    begin
        integer j;
        comment 使用递归从右至左求值数字， 
            但从左至右打印它们。 ;
        j := int ÷ 10;
        int := int - 10 × j;
        if j ≠ 0 then
            di​gits(j);
        outchar(channel, ‘0123456789’, int + 1)
    end digits;
    if int < 0 then
    begin
        outchar(channel, ‘-’, 1);
        int := -int
    end;
    di​gits(int); outterminator(channel)
end outinteger

這裏調用到的outchar(channel, str, int)，將在字符串str中對應整數int的值的那個字符，傳遞到通道channel；outterminator(channel)，用於輸出在數值之後的終結符（即空格、換行或分號）。此外，IFIP（英語：International Federation for Information Processing）工作組2.1（英語：IFIP Working Group 2.1）在1964年曾制定《ALGOL 60輸入輸出過程報告》，其中定義了insymbol、outsymbol、length、inreal、outreal、inarray和outarray，這裏的多維數組採用了橫行為主（英語：Row- and column-major order）（Row major）次序[36]。

參見

註釋與引用

外部連結

Wikiwand - on

Seamless Wikipedia browsing. On steroids.