主編寄語
《大眾科學》雜誌正在慶祝其166週年。鑑於它是美國持續出版時間最長的雜誌，它觸動了許多讀者的生活和職業道路也就不足為奇了——包括為我們撰寫文章的科學家以及我們報道其工作的科學家。所以，就像經常發生的那樣，當我在谷歌科學展覽會上擔任評委時遇到了谷歌的研究主管彼得·諾維格，我們開始聊起了《大眾科學》。他提到這本雜誌對他個人影響深遠。雖然對他最具啟發性的文章在很多方面都被證明是正確的，但在其他方面最終卻是錯誤的。我說了類似這樣的話：“這真的很有趣。我想知道那些是什麼——而且我敢打賭其他人也會想知道。你願意為我們寫一篇關於這個的文章嗎？”
這是啟發諾維格的文章。看完之後，您可以閱讀諾維格在這篇部落格中令人著迷的想法。
關於支援科學新聞業
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞業 訂閱。透過購買訂閱，您正在幫助確保關於塑造我們當今世界的發現和想法的具有影響力的故事的未來。
我們不時會提供關於《大眾科學》雜誌的其他見解——既來自在研究領域工作的科學家（該雜誌與讀者分享這個領域），也來自我們的工作人員和撰稿人，他們可以向您提供關於我們正在進行的新專案的內幕訊息。一如既往，我們很樂意收到您的評論和反饋。如果您受到《大眾科學》的啟發，請與我們分享您的故事：submit@sciam.com —瑪麗埃特·迪克里斯蒂娜
最初發表於1966年9月刊的《大眾科學》。
一句被所有的習字帖和名人在演講時重複的深刻而錯誤的陳詞濫調是，我們應該培養思考我們正在做什麼的習慣。事實恰恰相反。文明的進步是透過擴充套件我們可以不經思考就能執行的重要操作的數量來實現的。思想的運作就像戰鬥中的騎兵衝鋒——它們的數量嚴格限制，它們需要新鮮的馬匹，並且只能在決定性的時刻進行。 - 阿爾弗雷德·諾思·懷特海德
本文是關於如何讓計算機做你想做的事情，以及為什麼它幾乎總是比你預期的要花費更長的時間。以下內容不是關於程式設計技術發展水平的詳細報告，而是試圖展示如何開始編寫程式。編寫程式的過程主要是直覺的，而不是形式化的；因此，我們將更關注程式設計的指導原則，而不是將程式呈現給機器的特定語言。
我們將從一個具體的程式設計問題示例開始，這個問題顯然是不平凡的，但又足夠簡單，無需任何先前的程式設計知識即可理解。我選擇瞭解決這個問題的非正統方法，對於許多專業程式設計師來說，這種方法看起來會很奇怪。這種方法使我們能夠處理一個例子，否則這個例子會過於複雜而無法解釋。
我們的問題是編寫一個程式，讓計算機下跳棋。我們應該如何著手呢？這個問題主要有兩個方面。為了使計算機能夠處理這個遊戲，我們必須找到一種方法來表示棋盤和棋盤上的位置，併為計算機提供一個程式，用於識別合法走法並進行走棋。這是一個程式設計問題。其次，我們必須為機器提供一種從可用的走法中選擇合適的走法的方法。這主要是一個博弈問題。國際商業機器公司的亞瑟·L·塞繆爾對博弈方面進行了廣泛而相當成功的研究。然而，由於我們關注的是程式設計而不是博弈，我們將滿足於一個簡單的通用策略，並將大部分細節留待解決。
編寫程式的常用方法，特別是對於複雜的問題，是將過程分為兩個階段。第一個階段稱為系統分析。它包括分析任務，以確定確切需要做什麼，並制定總體計劃。一旦決定了要執行工作的總體綱要，第二個階段就是以適合計算機的形式編寫所需的操作。這涉及大量更詳細的決策（例如，如何在機器中表示資訊以及如何儲存表示）。程式的詳細形式將取決於要使用的特定計算機。
關於這兩個階段的命名，已經產生了混淆。一些程式設計師將術語“程式設計”保留給第二階段；另一些人稱第一階段為“程式設計”，第二階段為“編碼”；還有一些人使用術語“程式設計”來表示整個過程——第一階段和第二階段。我自己的觀點是，系統分析和程式設計之間的區別不是很有用。如果系統分析能夠深入到用比目前使用的語言稍微嚴格的語言來描述程式概要，那麼應該可以將生成機器語言詳細程式的剩餘整個過程委託給計算機本身。
讓我們繼續討論編寫程式讓計算機與對手下跳棋的問題。我們應該如何表示遊戲的相關特徵，以及我們希望能夠對它們執行哪些型別的操作？一個好的工作規則是從操作開始，讓操作決定你需要表示在機器中的內容。在這種情況下，我們顯然需要從表示位置和走法以及與它們相關的值開始。
我們可以透過使用函式符號來接近計算機所需的精度，同時避免陷入過早的細節。我們用P表示一個位置，並同意將P不僅包括棋盤上棋子的數量和排列，還包括各種其他重要事實，例如輪到哪個玩家走棋。一個位置的價值可以用函式PositionValue(P)來表示。任何走法（例如M）的價值顯然取決於它所處的起始位置；因此，在編寫函式MoveValue(M,P)時，我們必須指定位置。接下來，為了能夠展望未來並檢查走法的可能後果，計算機將需要第三個函式：MakeMove(M,P)，其中P表示走法所處的起始位置。此函式的結果是走法產生的新位置。最後，程式需要第四個函式來查詢可以從給定位置進行的所有合法走法：LegalMovesFrom(P)。此函式的結果是一個走法列表。
這四個函式，以及兩種型別的物件（P和M），足以指定我們的跳棋程式的核心。跳棋遊戲中有兩個玩家（在我們的例子中是機器及其對手），對一個玩家有利的位置對另一個玩家不利。因此，我們必須使我們對位置價值的理解更加精確，即PositionValue(P)給出位置P對於必須從該位置走棋的玩家的價值。我們可以合理地假設位置P對於另一個玩家的價值是這個價值的負數；也就是說，如果一個位置對一個玩家的價值是v，那麼它對另一個玩家的價值將是-v。（這個假設在博弈論中用跳棋是零和博弈來表達。）
接下來，我們可以將走法對於執行走法的玩家的價值定義為結果位置對他/她的價值。假設從位置P執行走法M的結果是位置P。記住對手必須從P開始走棋，我們可以看到走法M對於執行走法的玩家的價值將是-PositionValue(P)。因此，在我們的符號中，我們可以將走法的價值定義如下：MoveValue(M,P) = -Position Value [MakeMove(M,P) ]。這個正式的陳述可以解釋為，為了評估你自己的走法，你執行它，找到結果位置對你的對手的價值，並改變它的符號。
我們應該如何找到一個位置的價值？遊戲的基本程式是探索你所有可能的走法和對手對一些深度的所有可能回覆，並評估結果位置。讓我們將這些稱為“終局”位置，並說它們的價值是由函式TerminalValue(P)產生的。此函式對位置進行即時評估（可能根據諸如仍在遊戲中的棋子數量、它們的移動性、對棋盤中心的控制等因素），而無需進一步展望未來。我們現在可以說，如果P是終局位置，則其價值為TerminaIValue(P)，如果不是，則其價值是可能從中進行的最佳合法走法的價值。請注意，位置是否為終局位置可能不僅取決於位置本身，還取決於展望未來的深度（el）。為了限制機器展望未來的深度，這是必要的。
我們一直在編寫的定義實際上是迴圈的（例如，Position Value的定義涉及MoveValue的使用，反之亦然），這些函式被稱為遞迴函式，因為每個函式都是根據其他函式定義的。這種迴圈性沒有缺點；實際上，它使得可以直接從中間開始，設定許多函式，這些函式的目的在一開始僅憑直覺理解，並將它們中的每一個都根據其他函式定義。這種遞迴或分層的程式設計方法是處理複雜操作的最簡單方法，因為它允許將它們分解為可以單獨考慮的較小單元。
我們現在構建了一個通用的博弈方案，而沒有決定策略的細節或遊戲本身的結構。我們可以透過決定位置和走法的表示形式並定義四個函式來完成我們程式的概要。函式Legal- MovesFrom(P)和MakeMove(M,P)，以及P和M的形式，將決定遊戲的性質，而函式Terminal(P,d)和TerminalValue(P)之間將決定策略。
選擇在計算機中表示物件的方式是一門藝術，我們在系統地決定最佳方式方面幾乎無能為力。主要要求是表示形式應儘可能緊湊，並且儘可能易於操作。為了表示跳棋盤上的各種位置，我們有兩種不同的可能性。為了描述一個特定的位置，我們可以指定棋盤上32個可用方格中的每一個是否被佔用，如果是，則被什麼佔用，或者我們可以僅給出仍在遊戲中的棋子的位置。從查詢合法走法的角度來看，第一種選擇更方便，因為它更容易發現哪些方格是未被佔用的。
當我們詳細考慮走法的表示時，我們發現普通棋盤上的方格編號很不方便，因為有兩種型別的方格（在交替的行上）需要不同的規則。塞繆爾設計了一種巧妙的方法來避免這種困難。透過用未使用的行和列擴充套件棋盤並重新編號方格，他產生了一個方案，在該方案中，對於實際使用的棋盤部分上的所有方格，可能的走法都是相似的。
所有可能的走法（除了那些棋子被吃掉的走法）都分為四種類型，每種型別都可以用一個字（由45位或二進位制數字組成）表示，該字可以指定其型別的任何走法。在我們一直在使用的符號方案框架內，表示吃子走法和將兵晉升為王也很簡單。
討論工作跳棋程式的所有細節將超出本文的範圍。然而，編寫此類程式的過程的主要輪廓現在應該很明顯了。第一步是對如何解決問題有一個模糊的想法。第二步是指定執行此初始計劃所需的操作，透過命名這些操作要作用的物件來使其形式化。第三步是澄清物件的定義並確定每個物件的表示形式。這些表示形式應主要由要對物件執行的操作決定。一旦確定了表示形式，就可以根據它們更精確地定義元件操作。然後，可以繼續完善程式，更正可能在表示形式中顯示的錯誤或缺陷，並相應地調整操作。
在這個階段，程式的主要智力工作似乎已經完成。我們已經精確地指定了我們希望計算機做什麼。其餘的——將程式轉換為計算機的指令——應該只是例行公事。不幸的是，事情並非完全如此，任何沒有使用計算機經驗的人都會對仍然需要的時間和精力感到不愉快地驚訝。
首先，計算機無法直接接受我們希望給它的相當複雜的指令型別。幾乎可以肯定的是，我們將使用對於任何計算機來說都太過分的操作。為了繞過機器無法直接執行我們想要的操作，我們可以用標準程式語言編寫我們的程式，並讓機器將其翻譯成它自己的更簡單的程式碼。這似乎是很好地利用計算機為我們做苦力，但不幸的是，它並沒有消除所有的勞動。我們必須做大量的看似無關緊要和臨時的工作，以迫使程式進入適合現有程式語言的形式。
現在有相當多的這些程式語言：FORTRAN、ALGOL和MAD（主要用於科學問題）；JOVIAL（用於軍事應用）；COBOL；SIM SCRIPT；LI SP；PL/I；CPL等等。為了指示語言的不同風格，給出了三個示例：一個簡單的程式（用於查詢數學函式eX）分別用CPL、ALGOL和FORTRAN編寫。
大約九年前出現的這種型別的程式語言極大地豐富了程式設計藝術。在此之前，包含5,000條指令的程式被認為相當大，只有最有經驗或最魯莽的程式設計師才會嘗試。今天，一個人可以處理大約大10倍的程式；一個團隊透過合作努力可以產生仍然大五到十倍的程式。
到目前為止，最重要的新程式語言是FORTRAN；據估計，直到最近，超過90%的科學和工程程式都是用它編寫的。在過去的幾年中，逐漸清楚的是，當前的程式語言絕非完美，FORTRAN的巨大成功是由於其相對優點而不是絕對優點。諸如ALGOL和LISP之類的其他程式語言表明，至少在計算機上執行某些操作有更簡單的方法。
回到我們的跳棋程式：我已經用CPL（代表“組合程式語言”）的非正式且有些擴充套件的版本編寫了完整的程式（除了某些細節，包括輸入和輸出安排）。程式以符號形式以及使用的術語列表及其定義顯示在上一頁。該程式絕不是最終形式；它尚未在機器上執行，因此，根據下面表達的觀點，可能仍然包含一些錯誤。感興趣的讀者可能想尋找它們。
在計算機程式設計的早期——比如15年前——數學家們曾經認為，只要足夠小心，他們就能夠編寫出正確的程式。令他們非常驚訝和懊惱的是，他們發現情況並非如此，並且除了極少數例外，編寫的程式都包含大量錯誤。事實證明，發現、定位和糾正這些錯誤的過程非常困難，通常比首先編寫程式花費的時間要長得多，並且使用了大量的機器時間。
儘管自早期以來程式設計技術已經得到了極大的改進，但查詢和糾正程式中的錯誤的過程——如果說不優雅的話，也生動地被稱為“除錯”——仍然是最困難、最混亂和最令人不滿意的操作。這種情況的主要影響是心理上的。儘管我們都很樂意口頭上贊同“人非聖賢，孰能無過”的格言，但我們大多數人喜歡在真正嘗試的特殊場合對自己的表現保留一點私人保留意見。當機器公開且無可辯駁地表明，即使我們確實嘗試了，我們實際上犯的錯誤也與其他人的錯誤一樣多時，這有點令人洩氣。如果你的驕傲無法從這種打擊中恢復過來，你永遠不會成為程式設計師。
事實上，人類的本性並非完美準確，並且不現實地相信他們永遠會是。獲得正確程式的唯一合理方法是假設它最初會包含錯誤，並採取步驟來發現這些錯誤並糾正它們。這種態度對於任何接觸過任何大規模操作計劃的人來說都非常熟悉，但對於大多數沒有接觸過的人來說卻完全陌生。
我認為問題在於，太多的教育過程都非常重視第一次獲得正確答案。如果你在考試題中給出了錯誤的答案，你就會失去你的分數，事情就到此為止了。如果你在編寫程式時犯了錯誤——或者，實際上，在課堂外的許多其他生活情況中——這絕不是一場災難；但是，你必須找到你的錯誤並糾正它。也許更多的學術教學也採用這種態度會更好。
當我們第一次開始接觸計算機並實際嘗試執行程式時，無論是為了測試它還是為了獲得一些有用的結果，我們才真正開始感到沮喪。儘管機器本身的速度備受讚譽，但通常需要幾個小時，有時甚至幾天才能真正得到即使是最短程式的答案。當這種延遲加上計算機及其程式語言和編譯器通常非常無助的事實，以至於你在一天等待結束時收到的唯一資訊可能是你的程式仍然是錯誤的，很容易理解為什麼這麼多人認為使用計算機更多的是與機器和系統作鬥爭，而不是合作。
造成這種奇怪情況的原因是希望使計算機（這是一種非常昂貴的機器）儘可能長時間地充分運轉。計算機外部的組織（通常僱用相當多的操作人員）幾乎佔了所有的“週轉時間”和相當一部分的挫敗感。時間共享系統的引入應該消除這種挫敗感的來源，但代價是大大增加了作業系統的大小和複雜性。
實際執行程式所涉及的大部分工作可以由計算機本身完成。諸如將程式語言翻譯成詳細的機器程式碼、在計算機內部分配儲存空間、保留記錄以協助診斷程式錯誤、組織來自不同使用者的短作業序列的排程和核算等操作正是計算機可以處理的高階例行文書工作，因此期望機器來完成它是合理的。
使機器執行這些操作的程式非常重要。大多數計算機使用者與它們的接觸將遠遠多於與計算機本身的接觸，因此，作業系統程式被稱為系統的軟體（與計算機本身（稱為硬體）相對）。實際上，系統的效能在很大程度上取決於其軟體及其硬體，而軟體系統的規劃和編寫正在迅速成為計算機制造商的主要問題。整個程式集，稱為軟體包，可能很容易花費機器製造商與生產和除錯機器本身一樣多的成本。結果，即使在許多方面它們嚴重不足，也存在不更改程式語言或作業系統的強大壓力。
為什麼從程式的構思到機器的執行之路如此漫長而乏味？為什麼今天的作業系統——軟體——如此昂貴且令人不滿意？我們是否可能達到了人類編寫複雜程式的能力極限，而當前的軟體危機是否真的是試圖完成人類不可能完成的任務的結果？任何今天與大型計算機系統打交道的人都知道，整個事情是多麼接近在自身複雜性的重壓下崩潰。
毫無疑問，使用當前的技術，我們幾乎達到了程式設計的極限。但是，我們難道不能改進技術嗎？我們在本文中考慮的跳棋示例強烈暗示，簡化的方法和程式語言的改進將使事情變得容易得多。如果存在合適的程式語言，那麼顯然應該可以按照上述概述的方式編寫整個跳棋程式，並將幾乎所有剩餘階段留給計算機執行。事實上，現在幾乎可以做到這一點，並且構建一種可以實現這一目標的語言可能並不太困難。
建立一個大型而複雜的程式的唯一合理方法是使用分層方法。由於我們一次可以掌握在頭腦中的問題的大小和複雜性是有限的，因此擴充套件我們能力的最佳方法似乎是將相對較大且複雜的操作視為單個單元，並將這些單元分層組合。當前的程式語言都至少在口頭上對這個想法表示贊同，但是許多語言不允許真正的和無限的分層結構——程式設計師必須同時考慮的只有兩到三個操作級別（例如“本地”和“全域性”）。那些允許真正分層處理問題的語言在處理表示形式方面只有有限的能力。
當今的計算機本身是使用分層（或遞迴）編寫的程式的絆腳石。由於計算機不適合這種組織，因此執行此類程式比以傳統方式編寫和編碼的程式慢得多。但是，我深信，這種程式設計方式的優點將遠遠超過可能需要的任何機器時間的增加。這些優點是如此之大，以至於我相信分層方法最終將被普遍採用。畢竟，任何機器的主要目的都是為了節省人類的麻煩；因此，我們不應過分擔心讓計算機承擔更多的人的工作。此外，我們有充分的理由期望可以設計出能夠更自然、更有效地處理深度分層程式的計算機。這些機器可能會比目前的機器稍微複雜一些，但是成本上的差異將是非常值得的。
我把在我看來是最困難，但也是最有趣和最有潛在回報的問題留到了最後，這個問題是關於程式語言的。這是為構建程式的層次系統奠定堅實的數學基礎，並開發用於操作它們的微積分。
困難主要源於這樣一個事實，即程式設計向我們提出了某些新的問題，這些問題在數學的任何其他分支中都不存在，或者至少不重要。數學問題有兩個方面。第一個方面是如何顯式且詳細地處理複雜的結構（涉及資料表示），不僅要給出整個結構的名稱，而且還要給出其組成部分的名稱併為其分配值。困難的第二個方面是在程式設計中使用命令（01' 命令）引入變數，而一般數學不承認這種意義上的變數的存在，即值隨時間變化。在其傳統分支中，數學僅處理靜態情況。即使是微積分，它也關注物件接近極限，也是根據一系列固定值來處理這個主題。通常，數學家稱之為變數的東西要麼是值尚未知的常數，要麼是為了邏輯語法目的而引入的不存在的量（例如“沒有人”）。另一方面，在程式設計中，我們透過過程的本質來處理隨時間變化的變數；程式本質上是一個更改計劃。
一位經驗豐富的程式設計師在閱讀本文時會注意到，在跳棋程式的制定中，我沒有使用任何命令，尤其是程式不包含任何賦值語句（將值分配給名稱或物件的語句）。這樣做的原因是，我們只知道如何在沒有賦值語句的情況下將遞迴定義的函式組合成層次結構。如果包含它們，仍然沒有令人滿意的方法來做同樣的事情。
我已經討論過的數學問題的研究現在已經開始。一開始就很清楚，要探索的領域幾乎是全新的，沒有像數學研究的大多數其他領域那樣的既定指導方針。同樣明顯的是，第一個也是最困難的任務是澄清在程式設計上下文中，我們所說的“名稱”和“值”是什麼意思。主要的麻煩是，賦值（值隨情況變化而變化）的引入使得術語的含義從它們在數學中通常使用的方式來看是模稜兩可的，因此似乎我們可能需要生成新的概念，以便牢牢把握住情況。
現在在程式語言領域中完成的大部分理論工作都與語言語法有關。本質上，這意味著研究關注的不是語言說什麼，而是它如何說。這種方法似乎在形成新概念的道路上設定了幾乎無法逾越的障礙——至少就語言含義而言是這樣。我相信，對於程式設計師來說，進步之路在於研究含義而不是語法。主要透過對含義的研究，我們將開發出構建層次結構所需的概念。