🕷️
SetupAI
EN
🐯最新收集於 52m

價值十億美元的錯誤，如何造福程式設計師

PostLinkedIn
🐯閱讀原文： 虎嗅
#formal-verification#program-correctness#coding-agents#software-complexityhoare-logic-and-quicksorttony-hoarequicksorthoare-logicalgolmicrosoft

💡AI 能更快產生程式碼，但 Hoare 的研究揭示如何維持程式碼的可理解性與正確性。

⚡ 30-Second TL;DR

有什麼變化

Tony Hoare 在機器翻譯專案中發展 Quicksort，當時電腦記憶體極為有限，必須高效排序詞彙。

為什麼重要

隨著 AI 程式設計工具提高程式碼產量，瓶頸正轉向理解、驗證與維護。Hoare 的研究提醒 AI 開發流程應將程式碼生成與明確規格、自動化測試、靜態分析及適當的形式化推理結合。

下一步行動

為 Coding Agent 生成的關鍵函式加入契約式前置條件與後置條件，並搭配基於屬性的測試。

誰應關注：Researchers & Academics

關鍵要點

  • •Tony Hoare 在機器翻譯專案中發展 Quicksort，當時電腦記憶體極為有限，必須高效排序詞彙。
  • •Hoare logic 透過前置條件、後置條件與不變量，提供推理程式正確性的形式化框架。
  • •他主張簡潔的程式語言設計，並與 Niklaus Wirth 提交 ALGOL W，但提案最終遭到否決。
  • •他後來的研究還包括通信順序進程（Communicating Sequential Processes）與統一程式語義理論。
  • •當程式碼生成日益自動化時，Hoare 的思想可作為驗證 AI 生成程式碼的理論基礎。

🧠 深度解析

背景與延伸：來自公開資料，非原文內容。引用 38 個來源。

🔑 增強重點摘要

  • •Tony Hoare 的大學教育背景是牛津大學的古典文學與哲學（「Greats」），他在學習統計學和電腦程式設計之前，就已培養了對邏輯的理解。
  • •他在莫斯科國立大學參與機器翻譯專案時開發了 Quicksort 演算法，當時他需要為儲存在磁帶上的俄語-英語字典對俄語單詞進行排序。
  • •Hoare logic 的原始概念受到 Robert W. Floyd 早期為流程圖開發的類似系統的啟發。
  • •他所稱的「十億美元的錯誤」特指在 1965 年設計 ALGOL W 的類型系統時引入空值引用，儘管其目標是確保絕對安全，但他為了實施的便利性而加入了這一特性。
  • •通信順序進程（CSP）對 occam 程式語言的設計產生了深遠影響，並啟發了 Go、Erlang 和 Crystal 等現代程式語言的設計。

🛠️ 技術深入

  • Quicksort 演算法
    • 採用「分而治之」（divide-and-conquer）策略，透過遞迴方式排序元素。
    • 選擇一個「基準點」（pivot）元素，並將其他元素分為兩個子陣列：小於基準點的元素和大於基準點的元素。
    • 遞迴地對這兩個子陣列重複上述過程，直到所有元素排序完成。
    • 平均時間複雜度為 O(n log n)，使其在實踐中非常高效。
    • 最壞情況時間複雜度為 O(n^2)，通常發生在基準點選擇不當（例如，陣列已排序且總是選擇第一個或最後一個元素）時。
    • 空間複雜度在精心實現的原地（in-place）版本中為 O(log n)（透過尾遞迴或優先排序較小的分區），但在未優化的最壞情況下，呼叫堆疊可能導致 O(n) 的空間複雜度。
    • Hoare 提出的原始分區方案使用兩個從陣列兩端向中間移動的指標，當檢測到逆序對時交換元素，通常比 Lomuto 的分區方案更有效率。
  • Hoare logic
    • 一個用於嚴格推理電腦程式正確性的形式化系統。
    • 核心特徵是 Hoare 三元組：{P} C {Q}，其中 P 是前置條件（precondition），C 是命令（程式碼），Q 是後置條件（postcondition）。
    • P 描述了 C 執行前的程式狀態，而 Q 描述了 C 執行（如果終止）後的程式狀態。
    • 包含一系列公理（例如，空語句公理、賦值公理）和推導規則（例如，複合規則、條件規則、while 迴圈規則、推論規則）。
    • while 迴圈規則利用了迴圈不變量（loop invariant），這是一個在每次迭代前後都保持為真的斷言。
    • Hoare logic 支援對部分正確性（如果程式終止，則結果正確）和完全正確性（程式終止且結果正確）的推理。

🔮 前景展望AI analysis grounded in cited sources

AI生成程式碼的可靠性將大幅提升，因為形式化驗證工具將更廣泛地整合到開發流程中。
Hoare 對簡潔和形式化驗證的重視，為驗證 AI 生成程式碼提供了理論基礎，促使開發者將形式化方法應用於確保 AI 生成程式碼的正確性。
未來的程式語言設計將更普遍地避免空值引用，或提供更安全的處理機制，以減少相關錯誤。
Hoare 將空值引用稱為「十億美元的錯誤」，這一教訓促使現代語言（如 Rust、Swift）和 AI 輔助編碼工具（如 TypeScript 的 Cursor Rules）積極設計以避免或靜態處理空值，從而提高軟體可靠性。

⏳ 時間線

1934-01
Tony Hoare 出生於錫蘭（今斯里蘭卡）。
1959-1960
在莫斯科國立大學期間開發 Quicksort 演算法。
1960
加入 Elliott Brothers Ltd.，並領導開發了首個 ALGOL 60 編譯器。
1965
在設計 ALGOL W 時引入了空值引用，後來稱之為「十億美元的錯誤」。
1969
提出 Hoare logic，為程式正確性提供公理化基礎。
1978
發表關於通信順序進程（CSP）的文章。
1980
榮獲 ACM 圖靈獎，表彰其對程式語言定義與設計的貢獻。
1999
從牛津大學退休，隨後加入微軟研究院擔任首席研究員。
2000
因對教育和電腦科學的貢獻被授予爵士稱號，並獲得京都獎。
2026-03
Tony Hoare 逝世，享年92歲。
🐯閱讀原文： 虎嗅
📰

AI 週報

閱讀本週精選 AI 大事摘要 →

👉相關動態

同主題

探索 #formal-verification

同產品

更多關於 hoare-logic-and-quicksort

同來源

最新來自 虎嗅

節制外送、重押 AI：Alibaba 開始算帳

節制外送、重押 AI：Alibaba 開始算帳

虎嗅•Aug 21
Harness：將 AI 智慧變成生產標準件

Harness：將 AI 智慧變成生產標準件

虎嗅•Aug 21
🐯

上海法院重罰 AI 偽造證據

虎嗅•Aug 21

AI 策展新聞聚合。所有內容版權歸原始發布者所有。
原始來源： 虎嗅 ↗

這是摘要，不是原文。去看原站，或訂閱每週簡報。

每週 AI 簡報

每週一封，可隨時退訂。