作者：John Backus
傳統程式語言增長的越來越大，不過沒有越來越強。在最基本層次的固有缺陷使得它們既臃腫且弱小：它們最初的一次一個單詞比程式設計風格遺傳自其共同祖先 —— 馮·諾依曼計算機，它們将語義密切的連接配接到狀态轉換，它們将程式設計分割到一個表達式的世界（a world of expressions）和一個陳述句的世界（a world of statements），它們不能有效的使用有力的組合形式去從存在的那些建構出新程式，而且它們缺乏有用的數學屬性去對程式作推理。
程式設計的一個替代函數風格可在對就生成程式而言的組合形式的使用中找到。函數式程式設計處理結構化資料，通常是非重複和非遞歸的，是分層構造的，不會命名它們的參數，并且讓過程聲明變得一般上可以應用是不需要複雜機制的。組合形式可以使用進階程式去“以一種在傳統語言中不可能的風格”構造更進階的程式。
和函數風格相聯系的是程式代數，其變量遍布程式之上，其操作是組合的形式。這種代數可用來轉換程式并解方程，其“未知量”是這麼一些程式，非常類似于某人在高中代數中變換方程的方式。這些轉換是由代數學定律給出的，而且在和程式被寫出來的同一種語言中得到執行。組合形式的選擇不單單是為了它們的程式設計力量，也是為了它們和代數學定律相關的力量。代數的一般定理就程式的大類給出了詳細的行為和終止條件。
計算系統的一種新類不但在其程式設計語言中使用函數式程式設計風格，而且也在其狀态轉換規則（state transition rules）中使用之。不似 馮·諾依曼語言，這些系統語義上和狀态是松耦合的 —— 每次主要的計算隻發生有一個狀态轉換。
關鍵詞和短語：函數式程式設計，程式設計代數，組合形式，函數式形式，程式設計語言，馮·諾依曼計算機，馮·諾依曼語言，計算系統模型，可用計算系統，可用狀态轉換系統，程式轉換，程式正确性， 程式終止，元構成（metacomposition）。
CR 分類： 程式設計->程式設計語言->總論, 程式設計->程式設計語言->雜論, 計算數學->元理論 ->總論,計算數學->元理論 ->程式設計理論,
介紹（Introduction）
我深深的感謝 ACM 邀請 1977年圖靈演講所給予的，以及這種在演講中伴随許諾細節談論的榮譽。那些希望看到該論文總結的讀者可以翻到節16，最後一節。
程式設計語言表現出了一點麻煩。每個成功的語言都吸收了，伴随一點點清理，其前任的所有特征加上的了一點點。某些語言的手冊超過了500頁；其它的通過使用稠密的形式主義将一個複雜的描述塞入更短的手冊。國防部最近就一個委員會設計的語言标準作出的計劃可能需要超過1千頁的一份手冊。每一門新的語言都宣稱新而時髦的特征，諸如強類型（strong typing）或結構化控制陳述句（structured control statements），但樸素的事實是，很少有語言讓程式設計對“有理由去說生産和學習使用它們的成本是值得的”來說足夠便宜或更可靠（the plain fact is that few languages make programming sufficiently cheaper or more reliable to justify the cost of producing and learning to use them）。
由于大小上的大量增長僅帶來了能力上小的增長，是以更小或更精緻的語言，比如 Pascal 将繼續流行。但有對“一個有力量的方法論來幫助我們思考程式”的極度需要，而且甚至沒有傳統的語言開始滿足這個需要。實際上，傳統的語言在我們思考程式時産生了毫無必要的混淆。
程式設計語言持續朝向它們目前的臃腫條件邁進有二十年了；作為一個結果，研究和發明程式設計語言已經失去了太多其激動人心的東西。取而代之，其現在是那些“更喜歡和厚厚的詳細概略工作（who prefer to work with thick compendia of details）”人的領域，而不是“與新觀念相搏鬥的（wrestle with new ideas）”人的領域。讨論程式設計語言類似于中世紀關于“有多少個天使可以在一個針尖上跳舞（the number of angels that can dance on the head of a pin）”的讨論，而取代令人激動的介于本質上概念不同的辯論。
許多有創造力的計算機科學家從發明語言退到發明工具去描述那些語言。不幸的是，他們主要滿足于應用他們的精緻新工具去研究已經存在的語言之缺點。在檢驗了傳統語言令人震驚的類型結構後，使用由Dana Scott 開發的精緻工具，非常叫人吃驚的是，我們中這麼多人仍舊被動的滿足于取代“積極的搜尋新結構”的那種結構。
這篇文章的目的有兩方面；首先，建議在傳統語言架構中的基本缺陷使得它們的表現弱小且它們癌一般的增長是不可避免的，第二，建議朝向探索設計一種新的語言的一些替代路線。
第二節 計算系統的模型（Models of Computing Systems）
在每一門程式設計語言背後有一個其程式控制着的計算系統模型。一些模型是純抽象的，有些是由硬體來表達的，另外一些是通過編譯或解釋程式來表達的。在我們更緊密的檢查傳統語言之前，對“現存模型，作為對目前普遍替換的一個介紹”做一個簡單概覽是有用的。現存模型可以粗略的用一下概括的标準去分。
2.1 模型标準（Criteria for Models）
- 2.1.1 基礎（Foundations）。該模型有一個精緻而緊湊的數學描述麼？在證明關于模型行為的有用事實放方面它有用麼？或者這個模型是否過于複雜以至于其描述很龐大并沒什麼數學性的使用？
- 2.1.2 曆史敏感（ History sensitivity ）這個模型是否包含了存儲的一個主張，以至于一個程式可以儲存“會影響一個後來程式的行為”那種資訊？就是說，這個模型對曆史敏感麼？
- 2.1.3 語義類型（Type of semantics）一個程式直到一個終止狀态達到前會連續的轉換狀态（其不是程式）麼？陳述是簡單的還是複雜的?或者一個“程式”可以相繼的被規約到更簡單的“程式”以衍生一個最終是結果的（規約語義學）“規範形式的程式（normal form program）”？
- 2.1.4 程式的清晰和概念上的有用性（Clarity and conceptual usefulness of programs ）程式設計模型清楚的表達了一個程序或計算麼？它們展現了那種“幫助我們關于程序的形式化和推理”概念麼？
2.2 模型分類（Classification of Models）
使用上述的标準，我們就能大概刻畫對計算系統而言的三類模型 ——簡單操作模型（simple operational models），應用模型（applicative models），以及馮·諾依曼模型（von Neumann models）。
- 2.2.1 簡單操作模型（simple operational models） 例子：圖靈機，各種自動機。基礎（Foundations）：精确和有用。 曆史敏感（ History sensitivity ）：有存儲，是曆史敏感的。語義（Semantics）：伴随非常簡單狀态的狀态轉換。程式清晰度（ Program clarity）：程式不清晰，而且概念上沒有幫助。
- 2.2.2 應用模型（applicative models）例子： Church 的 lambda 微積分【參見5】， Curry 的 combinators 系統【參見6】， 純 Lisp 【參見17】，在本文獻中描述的函數式程式設計語言。基礎（Foundations）：精确和有用。曆史敏感（ History sensitivity ）：沒有存儲，曆史不敏感的。語義（Semantics）：規約語義，無狀态。程式清晰度（ Program clarity）：程式清晰，而且概念上有幫助。
- 2.2.3 馮·諾依曼模型（Von Neumann models ）例子：馮·諾依曼計算機（von Neumann computers），傳統程式設計語言。基礎（Foundations）：複雜，龐大，沒有。曆史敏感（ History sensitivity ）：有存儲，曆史敏感。語義（Semantics）：帶有複雜狀态的狀态轉換。程式清晰度（ Program clarity）：程式可以适度的清晰，概念上不是很有用。
上述的分類無可否認是粗燥且可辯論的。一些最近的模型不是很容易嵌入這些範疇中的任何一個。比如，由 Arvind 和Gostelow【參見1】，Dennis 【參見7】，Kosinski 【參見13】開發的資料流語言(data-flow languages )和其它部分的和簡單操作模型相契合，不過它們的程式要比在這個類中的那些更早模型更清楚，而且有可能認為某些有規約語義。無論如何作為該領域的一份粗糙地圖的這種分類值得讨論。我們隻關心 應用模型（applicative models）和馮·諾依曼模型（Von Neumann models ）。
第三節 馮·諾依曼計算機（Von Neumann Computers）
為了了解傳統程式設計語言的問題，我們首先來檢驗一下它們的智力親種，馮·諾依曼計算機。什麼是馮·諾依曼計算機？當馮·諾依曼和其它人在三十年前（譯注：指上世紀40年代）設想出該東西時，其是一個精緻實際統一的觀念，其簡化了那時存在的若幹工程學和程式設計問題。雖然産生其體系架構的條件有了劇烈的改變，毫無疑問我們仍舊用這個三十年的舊概念來識别“計算機”這個看法。
一台馮·諾依曼計算機在其最簡單的形式中有三個部分：一個中央處理器單元（CPU），一個存儲，以及一個連接配接管，其可以将一個單獨的字在 CPU 和存儲之間作傳輸（并發送位址給存儲）。我建議把這個管子叫做馮·諾依曼瓶頸。一程式的任務是，以某種主要的方式去改變存儲的内容；當某人認為這個任務必須“通過把單個字來回的在馮·諾依曼瓶頸中抽取”完全完成，那麼它名字的原因就變得明顯了。
諷刺的是，在該瓶頸中的一大部分通信量不是有用的資料，隻是資料的名字，同時操作和資料隻是用來計算這樣的名字。在一個字可以通過這個管子得到發送前，其位址必須已經在CPU中了；是以它必須要麼通過來自存儲的管子發送，要麼它是通過某種CPU操作來形成的。如果位址是從存儲發送的，那麼其位址必須要麼已經從存儲發送了，要麼已經在CPU中形成了，諸如此類。如果，另一方面，位址是在 CPU 中形成的，它就必須要麼是通過固定規則（比如，“給程式計數器加1”）形成的，要麼是通過“一個通過該管子被發送的指令，于其中其位址必須已經被發送了（by an instruction that was sent through the tube, in which case its address must have been sent）”形成的，諸如此類。
當然在存儲中進行大的改變必須有較之“在馮·諾依曼瓶頸中來回的推送巨量的單詞（pushing vast numbers of words back and forth through the von Neumann bottleneck）”更少的簡單方式。不單單是說，就一個問題的資料通信量而言，這個管子是一個文字瓶頸，而且，更重要的是，其是一個“保持我們去和一次一個字的思考相關聯，取代鼓勵我們以在手邊的任務的更大概念單元術語去思考（that has kept us tied to word- at- a-time thinking instead of encouraging us to think in terms of the larger conceptual units of the task at hand）”的智力瓶頸。是以程式設計就在本質上對“通過馮·諾依曼瓶頸的單詞的龐大通信量”是規劃的和詳述的，那種通信量的大多數關注的不是重要資料本身，而是哪裡去找到它。
第四節 馮·諾依曼語言（ Von Neumann Languages）
傳統程式設計語言本質上是馮·諾依曼計算機的進階别複雜版本。我們三十年老的信仰“隻有一種計算機（there is only one kind of computer）”，這是我們的信仰“隻有一種程式設計語言（there is only one kind of programming language）——馮·諾依曼語言”的基礎。Fortran 和 Algol 68之間的差別，雖然很明顯，不過要比“兩者都基于馮·諾依曼計算機程式設計風格（both are based on the programming style of the von Neumann computer）”這樣的事實更少具有重要性。雖然我将傳統程式設計語言指為“馮·諾依曼語言”來取代它們的起源和風格，當然，我不會因為它們的複雜性就責怪偉大的數學家。實際上，有人可能會說我要為那個問題承擔一些責任。
馮·諾依曼程式設計語言使用變量去模拟計算機的存儲單元；控制語句（control statements）精心描述了它的跳轉以測試指令；指派語句（assignment statement）模拟了它的擷取、存儲和算數運算。指派語句是程式設計語言的馮·諾依曼瓶頸，并讓我們保持和計算機瓶頸所在做的是非常類似的一次一個單詞的思考方式。
考慮一個典型的程式；在它的中央是若幹指派語句，包含有一些下标變量。各指派語句産生一個字的結果。程式必須使這些語句得到許多次執行，當改變下标變量時，為了在存儲中有期望的總體改變，因為它必須一次隻完成一個字。當程式員設計一組控制語句以引起必要的重複時，他是以要關注經過指派瓶頸的字流（The programmer is thus concerned with the flow of words through the assignment bottleneck as he designs the nest of control statements to cause the necessary repetitions）。
還有，指派語句将程式設計分割為兩個世界（the assignment statement splits programming into two worlds）。第一個世界包括了指派語句的右半邊（the right sides of assignment statements）。這是表達式的一個整齊有序的世界，這個世界有有用的代數學屬性（除了那些經常被副作用所毀壞的屬性外 ）。最有用的計算就發生在這個世界中（It is the world in which most useful computation takes place） 。
傳統程式設計語言的第二個世界是陳述句的世界（the world of statements）。那個世界中的主要狀态是指派語句本身。該語言的所有其它狀态之存在，是為了使執行一種必須基于這種原始構造“指派語句”的計算成為可能。
狀态說明是一個無序的世界，隻有不多的數學屬性。結構化程式設計可以被視作是對“在這個混沌世界中引入一些秩序（introduce some order into this chaotic world）”的審慎努力，不過在處理“由一次一個字的馮·諾依曼程式設計風格生成的，伴随原始性的使用循環，下标，控制分支流”本質問題時，它成就不多。
我們對在馮·諾依曼語言上的定位繼續了馮·諾依曼計算機的首要地位，且我們對它的依賴使得非馮·諾依曼語言不經濟，并限制了它們的開發。全景的基于非馮·諾依曼原理有效程式設計風格的缺位，剝奪了設計師就新計算機體系結構而言的一個智力基礎。（就那個主題的簡單讨論，見節15。）
應用計算系統對存儲和曆史敏感的缺乏是“它們沒有為計算機設計提供一個基礎（they have not provided a foundation for computer design）”的基本原因。還有，大多數的應用系統采用了lambda 微積分的替換操作來作為它們的基本操作。這個操作的能力幾乎沒有限制，但是對它的完全有效認識對機器的設計師顯示出巨大困難。還有，試圖對它們引入存儲和試圖改進其在馮·諾依曼計算機上的效率，應用系統已經趨向于變為沉浸在一個大型馮·諾依曼系統中了。比如，純 Lisp 常常被埋在有馮·諾依曼特征的大型擴充中。結果的這個複雜系統對機器設計師來說沒什麼幫助。
第五節 馮·諾依曼和函數式程式的比較（Comparison of von Neumann and Functional Programs）
為了就 馮·諾依曼語言的某些缺陷取得一個更詳細圖像，讓我們用“将進一步細化的一門簡單語言寫出的一個函數式語言”去比較下内積（let us compare a conventional program for inner product with a functional one written in a simple language to be detailed further on）。
5.1 内積的馮·諾依曼程式（A von Neumann Program for Inner Product）
c := 0
for i:= 1 step 1 until n do
c:= c + a[i] × b[i]
這段程式的幾個屬性值的關注：
a)其在根據複雜的不可見“狀态”上的語句操作。
b)其不是繼承的。除了指派語句的右半邊外，其并不從更簡單的東西構造起複雜的實體。（然而，更大的程式常常是這樣的。）
c)其是動态且重複的。必須要從智力上去了解它的執行。
d)其一次一個字進行的計算是重複的（複值的）以及修改的（變量i）
e)資料的一部分 n 在程式中；是以缺少一般性并隻能對長度為 n 的向量工作。
f)它的名字是參數：僅可以用的向量是 a 和 b。為一般化，需要一個過程聲明（a procedure declaration）。這些設計複雜的議題（比如，傳參 對比 傳值）。
g)其“日常開支”操作是由在分散區域（在 for 語句中以及指派中的下标）的符号來代表的。
這使得不可能将日常開支操作，所有操作中最通常的，加強（consolidate）到單獨的、有力的、廣泛有用操作中去。是以在程式設計中這些操作必須總在第一步重新開始（start again at square one），寫下 “for i：= ... ” 和 “for j := ... ” 然後指派語句會撒上 i's 和j's 。
5.2 内積的一個函數式程式（A Functional Program for Inner Product）
Def Innerproduct
≡ (Insert +)°(ApplyToAll × )° Transpose
Or, in abbreviated form:
Def IP ≡ (/+)°(α × )°Trans.
合成（Composition ）（°），插入（Insert）（/）， 應用到所有（ApplyToAll）(α)是函數形式，其将現存函數組合以形成新的東西。是以 f ° g 是由首先應用 g 然後是 f而得到的函數，αf 是由 f 應用到參數的所有成員而得到的函數。如果對将 f 應用到對象 x之後的結果，我們寫下了 f :x ，那麼我們就可以解釋“在評估内積到向量對<<1, 2, 3>, <6, 5, 4>> 的應用”的每一步了，如下：
IP: << 1,2,3>, <6,5,4>> =
Definition of IP ⇒ (/+)°(α ×)° Trans: << 1,2,3>, <6,5,4>>
Effect of composition, ° ⇒ (/+)::((α ×):(Trans:<<1,2,3>, <6,5,4>>))
Applying Transpose ⇒ (/+):((α ×): <<1,6>, <2,5>, <3,4>>)
Effect of ApplyToAll, α ⇒(/+): <x: <1,6>, x: <2,5>, x: <3,4>>
Applying × ⇒(/+): <6,10,12>
Effect of Insert, / ⇒ +: <6, +: <10,12>>
Applying + ⇒ +: <6,22>
Applying + again ⇒ 28
讓我們用馮·諾依曼程式來比較一下這個程式的屬性。
a)其僅僅是在它的參數上運作。沒有隐含的狀态或複雜的轉換條件。隻有兩種規則，一種用來将一個函數應用到其參數，另一種用來擷取由一個諸如“合成 f ° g ，或 應用到所有 α f ”函數形式标記的函數，當一個人了解函數 f 和 g ，形式的參數時。
b) 其是層級的，從三個簡單的函數（+, ×, Trans）建構起來，以及三個函數形式 f ° g , αf 和 /f 。
c)其是靜态和非重複的，這是在“其結構有助于無需為了了解它而在智力上去執行”意義上說的。
比如說，如果了解了形式 f ° g 和 α f 的動作及函數 × 和 Trans 的動作，那麼就了解了α × 和 (α ×)°Trans的動作 了，諸如此類。
d) 其是操作在整個概念單元上的，不是在字上操作的；其有三步；沒有一步是重複的。
e) 其沒有吸收資料；其是完全一般的；其能就任何一對适當的向量去工作。
f) 其沒有命名它的變量；其可以被應用到任何對向量，無任何過程聲明或複雜的替換條件。
g) 其使用了在許多其它程式中一般有用的日常開銷形式和函數；實際上，隻有 + 和 × 不關心日常開銷。這些形式和函數可以和其它組合以生成更進階别的日常開銷運算符。
節14 概括了一類系統，設計用來使上述的帶一個簡單架構的函數風格程式設計在一個曆史敏感的系統中可用，但是在上述的應用風格可以變為精緻而實際的程式語言的基礎之前，還需要做許多工作。就目前而言，上述的比較展示了馮·諾依曼程式設計語言中存在的一系列嚴重缺陷，并可以作為“一種對它們的肥胖和孱弱條件負責的努力（in an effort to account for their presentfat and flabby condition）”的一個開始點。
第六節. 語言架構對比可變部分（Language Frameworks versus Changeable Parts）
讓我們比較一下程式設計語言的兩個部分。首先，其架構（framework ）給出了系統總體規則，其二，它的可變部分（changeable parts），其存在是受到架構期望的，但是其特定行為并沒有為架構所說明。比如，for 語句，以及幾乎所有其它語句，是 Algol 架構的一部分，但是函數庫和使用者定義的那些過程是可變部分。是以一門語言的架構描述了其固有的特征，并對其可變特征提供了一個一般環境。
現在假設有一門其有一個“其可容納作為可變部分的有極大差異的能力特性”的小架構的語言。那麼這樣的一個架構無需改變自己就可以支援許多不同特征和風格。與這個适宜的可能性形成對照的是，馮·諾依曼語言總是看上去有一個巨大的架構和非常有限的可變部分。是什麼讓這發生的？回答關注 馮·諾依曼語言的兩個問題。
第一個問題源自馮·諾依曼風格的一次一個字程式設計，其要求字流來回以達狀态，就像流通過馮·諾依曼瓶頸。馮·諾依曼語言必須在語義上和狀态密切耦合，于其中計算的每一次細節都會改變狀态。這種“在語義上和狀态密切的耦合”之結果就是，每個特性的每個細節都要建構到狀态和其轉換規則中去。
是以在研究架構内的細節時，必須明确一馮·諾依曼語言的每個特性。還有，需要許多複雜的特性以支援基本的弱一次一個字的風格。結果就是一門馮·諾依曼語言“不可避免的死闆而龐大的”架構。
第七節.可變部分群組合形式（Changeable Parts and Combining Forms ）
馮·諾依曼語言的第二個問題是，它們可變部分的表達能力是如此弱小。它們龐大的規模就是這個的明證；畢竟，如果設計師知道所有這些“他現在建構到架構中的”複雜特征，是可以作為可變部分後來添加到進去的，他就不會這般渴望将它們建構到架構中去了。
可能在“提供在一門語言中有力的可變部分”裡最重要的元素是“那種‘可一般被使用以從舊的建構出新的過程’的組合形式之可用性（the availability of combining forms that can be generally used to build new procedures from old ones）”。馮·諾依曼語言隻提供原始組合形式，而且馮·諾依曼架構對它們的使用設定了障礙。
對使用組合形式的一個障礙就是，在馮·諾依曼語言中表達式世界和陳述句世界之間的分裂（the split between the expression world and the statement world in von Neumann languages）。函數形式自然的屬于表達式世界；但是無論它們多麼有力，它們隻可以建構結果是産生一個字的那些表達式。而在陳述句世界中（ statement world ），這些一個字的結果必須并合并到整個結果中。對一個字的組合不是我們真當應該考慮的，但這卻是對任何任務以馮·諾依曼語言程式設計中的一大部分。為了幫助從單獨的字中裝配出整個結果，這些語言在陳述句世界（statement world）中提供了一些原始組合形式——for ，while ，if-then-else 陳述句——但這兩個世界之間的分裂“阻礙了在任何一個世界中的組合形式去獲得它們在一個沒有分裂的世界中可以達到的完全能力（prevents the combining forms in either world from attaining the full power they can achieve in an undivided world）”。
在馮·諾依曼語言中使用組合形式的第二個障礙是“在那些語言中使用的精緻命名約定，其通過為過程調用所需的替換規則被進一步複雜化（their use of elaborate naming conventions, which are further complicated by the substitution rules required in calling procedures）”。這些都需要在架構中建構一個複雜，進而變量、下标變量、指針、檔案名、過程名、傳值形參、傳名形參、諸如此類，可以合适的得到解釋。所有這些名字、約定及規則都和“使用簡單的組合形式（the use of simple combining forms）”相沖突。
第八節. APL 對比 一次一個字的程式設計（APL versus Word-at-a-Time Programming）
由于我關于一次一個字程式設計已經說了這麼多，我現在必需對APL【參見12】 說一下。我們欠 Kenneth Iverson 很多，因為他給我們顯示了“有這樣的程式，其既不是一次一個字也不依賴于 lambda 表達式，并對我們引入了新的函數形式（there are programs that are neither word-at-atime nor dependent on lambda expressions, and for introducing us to the use of new functional forms）”。而且由于APL指派語句可以存儲數組，其函數形式的效應就被擴充到超越了一個單獨指派所能有的效應。
不幸的是，然而，APL還是将程式設計分隔為一個表達式世界和一個陳述句世界。是以寫一行程式的努力部分是由“希望駐留在更有序的表達式世界中（the desire to stay in the more orderly world of expressions）”激發的。APL正好有三個函數形式，叫做内積（inner product），外積（outer product），和約減（reduction）。這些有時候使用困難，它們還不足夠，它們的使用被限制在了表達式世界。
最後，APL語義還是和狀态過于緊密耦合了。結果就是，雖然該語言有更大的簡潔性和能力，其架構仍有馮·諾依曼語言固有的複雜性和刻闆特性。
******(譯者略)
第十五節. 對計算機設計的評論（Remarks About Computer Design）
馮·諾依曼語言的統攝沒有給設計師留下多少智力模型去實際的設計超越馮·諾依曼計算機變種的那種計算機。資料流模型【參見1，7，13】是曆史敏感模型的一個替代。基于lambda微積分的替代規則的語言對計算機設計設提出了嚴肅的問題。Berkling【參見3】已經開發了一種改進的 lambda 微積分，其有三種應用，其讓變量的重命名變得沒有必要了。他為評估這種語言的表達能力開發了一種機器。為顯示“這種語言為有效程式設計風格打了怎麼樣的基礎，他的機器可以多有效（how sound a basis this language is for an effective programming style and how efficient his machine can be）”的進一步經曆是需要的。
Mago【參見15】已經開發了從相同元件（兩種）中構造出的一種全新應用機器。它會自底向上的直接評估類似 FP 和其它的應用表達式。其沒有馮·諾依曼存儲沒有位址寄存器，是以也就沒有瓶頸；其能并行的評估許多應用；其内置的操作較之“馮·諾依曼計算機操作”更類似FP操作。其是我見到過的和馮·諾依曼計算機最遠的分離。
有許多迹象說，程式設計應用風格可以變得比馮·諾依曼風格更加有力。是以程式員開發出就“一類新的曆史敏感的計算機系統模型，其展現了這樣的一個風格，并避免了看上去附着到基于lambda微積分的 系統上的那些内在效率問題（a new class of history-sensitive models of computing systems that embody such a style and avoid the inherent efficiency problems that seem to attach to lambda-calculus based systems）”很重要了。隻有當這些模型和它們的應用語言已經證明其對于傳統語言的優越性後，我們才會有經濟基礎去開發新種類的那種可以最好實作它們的計算機。隻有在那時，可能，我們才能夠在一個不受限于馮·諾依曼瓶頸的計算機設計中完全利用大規模內建電路。
第十六節. 總結（Summary）
本文前面的十五節可以總結如下。
第一節。傳統程式設計語言是大而複雜的，并且不靈活。它們受限的表達能力不足以成為它們的大小和花費的理由。
第二節。基于程式設計語言背後的計算系統模型大概分為三類：(a)簡單操作模型（比如，圖靈機），(b)應用模型（比如，lambda 微積分），以及(c)馮·諾依曼模型（比如，傳統計算機和程式設計語言）。每一類模型都有一個重要的困難：對類型(a)程式設計是不可思議的；類型（b）模型不可以從一個程式到另一個程式去儲存資訊；類型(c) 模型有無用的基礎和程式，概念上沒什麼幫助。
第三節。馮·諾依曼是圍繞一個瓶頸來造的：一次一個字的管子連接配接了CPU 和存儲。因為一個程式必須“通過馮·諾依曼瓶頸來回泵取巨量字（pumping vast numbers of words back and forth through the von Neumann bottleneck）”在存儲中作出完全的改變，我們就長出了一種程式設計風格，其本身關注一次一字經過瓶頸的通訊量，而不是我們問題的更大概念單元。
第四節。傳統程式設計語言是基于過馮·諾依曼計算機的程式設計風格。變量 = 存儲了元胞；複制語句 =撿取，存儲，和算術；控制語句 =跳轉和測試指令。符号“：=”是語言上的馮·諾依曼瓶頸。在傳統馮·諾依曼語言中的程式設計仍舊關注“通過這個有些更複雜的瓶頸的”一次一個字的通訊量。馮·諾依曼語言同樣将程式設計分為一個表達式的世界和一個陳述句的世界；第一個是在一個有序的世界，第二個是馄饨的世界，這是一個結構化程式在某重程度上簡化了的世界，但是沒有觸及基本的分裂自身問題，以及一次一個字風格的傳統語言。
第五節。本節比較了馮·諾依曼程式和有關内積的一個基本程式設計。其顯示了前者的若幹問題以及後者的優勢：比如，馮·諾依曼程式是重複的，并且一次一個字，僅僅和兩個叫做 a 和 b 的長度為n的向量工作，而且僅可通過使用“其有複雜語義的”一個過程聲明來一般使用。函數式程式設計是不重複的，将向量作為單元來處理，更分層的來建構，是完全一般的，并且通過組合為進階日常工作操作來生成“整理工作（housekeeping）”操作。它不用命名其參數，是以就不需要過程聲明。
第六節。一種程式設計語言組成了一個有一些可變部分的架構。一門馮·諾依曼的架構需要大多數特征建構到裡面去；它隻可以适應有限的可變部分（比如，使用者定義過程）因為在狀态中必須有詳細的規定，且其轉換規則對所有需要改變的部分，如同所有特性要建構到架構中。馮·諾依曼架構如此不靈活的原因在于“其語義太過精密耦合于狀态了（its semantics is too closely coupled to the state）”：一次計算改變狀态的每一個細節。
第七節。馮·諾依曼語言的可變部分沒有太多的表達能力；這是為何該語言大部分必須建構到架構中的原因。缺乏表現力是由“馮·諾依曼語言在有效使用組合形式去構造程式時的無能（the inability of von Neumann languages to effectively use combining forms for building programs）”造成的，這反過來是由于“表達式和陳述句之間的分裂（the split between expressions and statements）”。組合形式在表達式中正是最好的，不過在馮·諾依曼語言中，一個表達式隻可以産生一個單獨的字；是以在表達式世界中的表達能力大多數喪失了。使用組合形式的進一步障礙在于“命名約定的複雜（the elaborate use of naming conventions）”。
第八節。APL是不基于lambda 微積分的第一門“不是一次一個字，并使用函數組合形式 (that is not word-at-a-time and uses functional combining forms)”語言。不過它還是保留了馮·諾依曼語言的許多問題。
第九節。馮·諾依曼語言沒有關于程式推理的有用屬性。公理化的和訓示化的語義對“描述和了解傳統程式設計（describing and understanding conventional programs）”是精确工具，不過它們隻談論它們并且不可以改變它們的笨拙屬性。不似馮·諾依曼語言，普通代數的語言對“陳述其律則以及将一個等式轉化到其解決方案（for stating its laws and for transforming an equation into its solution）”兩者都是合适的，所有都在“語言”之中。
第十節。在一門曆史敏感的語言中，一段程式可以通過“改變一些由系統儲存的存儲（changing some store which is saved by the system）”去影響後程式來的行為。任何這樣的語言都需要某種狀态轉換語義（state transition semantics）。但是其不需要語義密切的耦合到“于其中狀态随計算的每個細節而改變”狀态。提出的“應用狀态轉換（Applicative state transition，AST）”系統作為對馮·諾依曼系統的一種曆史敏感替代。這些是：(a)松耦合狀态轉換語義，于其中每次一個主要計算發生一次轉換；(b)簡單的狀态和轉換規則；(c) 一個帶簡單“規約”語義的基本應用系統；以及（d）一門程式設計語言和狀态轉換規則，兩者都基于基本的應用系統和其語義。下面四節描述了這種方式到馮·諾依曼語言和系統設計的元素。
第十一節。描述了一類非正式的函數程式設計（functional programming ，FP）系統，其不使用變量。各個系統是從“對象，函數，函數形式，以及定義”建構起來的。函數将對象隐射到對象中。函數式将已經存在的函數組合以形成新的函數。這一節列出了“原語函數和函數式（primitive functions and functional forms）”例子并給了樣例程式。該節讨論了 FP 系統的限制和優勢。
十二節。描述了一門“代數程式設計（algebra of programs）”，其變量範圍對從一個FP 系統的函數到 其操作 是一個系統的函數式作了涵蓋（whose variables range over the functions of an FP system and whose "operations" are the functional forms of the system）。代數二十四法則清單跟在一個例子後面，證明了“一個非重複矩陣乘法程式等價于一個遞歸程式（the equivalence of a nonrepetitive matrix multiplication program and a recursive one）”。下一子節陳述了“解”兩類方程式的兩個“擴充理論的”結果。這些解将在這種方程式中的“未知”函數表達為“組成對其行為的一個逐條描述，并立即就終止給出充分必要條件（constitutes a case-by-case description of its behavior and immediately gives the necessary and sufficient conditions for termination）”無限條件擴充。這些結果用于衍生一種“遞歸理論”以及一種“疊代理論”，其對“某些适度一般和有用的線性等式類（for some moderately general and useful classes of "linear" equations）”提供了現成的擴充。使用這些定理的例子有：(a)對遞歸和疊代階乘函數的正确性證明，(b)證明兩個疊代程式的等價。一個最後的例子處理“二次方程”，并證明其解是一個幂函數。下一子節給出了兩個擴充程式的證明。
相關于 FP 系統的代數與“對lambda 微積分 和其他應用系統相應的代數（the corresponding algebras for the lambda calculus and other applicative systems）”相比較。這種比較顯示了，當相比較于多得多的有力的傳統系統時，優勢來自于多個受限的 FP 系統。提出了一些關于函數到“無限擴充（infinite expansions）”的算法規約問題，并提出了一些關于“在各種‘惰性評估’中使用代數（the use of the algebra in various ‘lazy evaluation’ schemes）”的問題。
第十三節。這一節描述了形式化的函數程式設計（formal functional programming ，FFP）的，擴充了并使用FP系統的精确行為的系統。它們的語義要比傳統系統的更簡單，并可通過一個簡單的不動點參數來顯示一緻。
第十四節。這一節比較了Algol 的結構和應用狀态轉換系統（applicative state transition ，AST）的結構。其使用FFP系統 将一AST 系統描述為其應用子系統。其描述了簡單的狀态及對系統的轉換規則。描述了對AST 系統的一個小的自防護系統程式，以及它如何才能被裝入并被“為了檔案維護以及為了運作使用者程式（for file maintenance and for running user programs）”使用。該節簡要的讨論了 AST 系統及以及“可以被定義和在一個AST系統中使用的”函數命名系統的變種。
第十五節。這一節簡要的讨論了在“應用計算機設計，及需要開發并測試更多的實際應用系統模型以作為這樣設計的未來基礎”上的工作。
感謝（Acknowledgments）
（譯者略）
參考（References）
I. Arvind, and Gostelow, K.P.
A new interpreter for data flow schemas and its implications for computer architecture.
Tech. Rep.No. 72, Dept. Comptr. Sci., U. of California, Irvine, Oct. 1975.
2. Backus, J.
Programming language semantics and closed applicative languages.
Conf. Record ACM Symp. on Principles of Programming Languages, Boston, Oct. 1973, 71-86.
3. Berkling, K.J.
Reduction languages for reduction machines.
Interner Bericht ISF-76-8, Gesellschaft f'dr Mathematik und Datenverarbeitung MBH, Bonn, Sept. 1976.
4. Burge, W.H.
Recursive Programming Techniques.
Addison- Wesley, Reading, Mass., 1975.
5. Church, A.
The Calculi of Lambda-Conversion.
Princeton U. Press, Princeton, N.J., 1941.
6. Curry, H.B., and Feys, R.
Combinatory Logic, Vol. 1.
North Holland Pub. Co., Amsterdam, 1958.
7. Dennis, J.B.
First version of a data flow procedure language.
Tech. Mem. No. 61, Lab. for Comptr. Sci., M.I.T., Cambridge, Mass.,May 1973.
8. Dijkstra, E.W. ,
4 Discipline of Programming.
Prentice-Hall,Englewood Cliffs, N.J., 1976.
9. Friedman, D.P., and Wise,
D.S. CONS should not evaluate its arguments.
In Automata, Languages and Programming, S. Michaelson and R. Milner, Eds., Edinburgh U. Press, Edinburgh, 1976, pp.257-284.
10. Henderson, P., and Morris, J.H. Jr.
A lazy evaluator.
Conf.Record Third ACM Symp. on Principles of Programming Languages,Atlanta, Ga., Jan. 1976, pp. 95-103.
11. Hoare, C.A.R.
An axiomatic basis for computer programming.
Comm. ,4CM 12, 10 (Oct. 1969), 576-583.
12. Iverson, K.
A Programming Language.
Wiley, New York, 1962.
13. Kosinski, P.
A data flow programming language.
Rep. RC 4264, IBM T.J. Watson Research Ctr., Yorktown Heights, N.Y., March1973.
14. Landin, P.J.
The mechanical evaluation of expressions.
Computer J. 6, 4 (1964), 308-320.
15. Mago, G.A.
A network of microprocessors to execute reduction languages.
To appear in Int. J. Comptr. and Inform. Sci.16. Manna, Z., Ness, S., and Vuillemin, J.
Inductive methods for proving properties of programs.
Comm..4 CM 16,8 (Aug. 1973) 491-502.
17. McCarthy, J.
Recursive functions of symbolic expressions and their computation by machine
Pt. 1. Comm. ,4CM 3, 4 (April 1960), 184-195.
18. Me Jones, P.
A Church-Rosser property of closed applicative languages.
Rep. RJ 1589, IBM Res. Lab., San Jose, Calif., May 1975.
19. Reynolds, J.C.
GEDANKEN--a simple typeless language based on the principle of completeness and the reference concept.
Comm.ACM 13, 5 (May 1970), 308-318.
20. Reynolds, J..C.
Notes on a lattice-theoretic approach to the theory of computation.
Dept. Syst. and Inform. Sci., Syracuse U., Syracuse,N.Y., 1972.
21. Scott, D.
Outline of a mathematical theory of computation.
Proc. 4th Princeton Conf. on Inform. Sci. and Syst., 1970.
22. Scott, D.
Lattice-theoretic models for various type-free calculi.
Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972.
23. Scott, D., and Strachey, C.
Towards a mathematical semantics for computer languages.
Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn, 1971.
![寫在工作13周年[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)