怎樣設計一套程序設計語言？

01-06

我曾經設計並實現過一門編程語言，作為我的畢業設計。

這非常有趣，儘管存在一些挑戰，但事實上並沒有想像中那麼難。

基本上，你需要解決的第一個問題並非來自技術層面，而是概念層面——為什麼你要設計一門新的編程語言？

我當初的動機是因為我對現有編程語言基於的一些編程思想心存疑惑，特別是我對class-based的編程語言持有異議。同樣是實現Object-Oriented，prototype-based方式更加符合人的思維，而且更簡單。

Javascript就是一個典型的例子。

但是Javascript本身又引入了一大堆的缺陷（語法和實現機制方面）。

於是我想這就是我想做的事情——設計並實現一門新的漂亮的prototype-based的編程語言。

當解決了概念層次上這個最大的，也是最重要的問題後，我便開始著手考慮細節。

這並不簡單，問題逐漸浮現出來。

簡單來說，定義一門語言，有點像定義一個宇宙。一開始，宇宙空空如也。為了讓這個宇宙能夠開始運轉，並衍生出超越我們想像的複雜世界，我們作為「造物主」，需要準備好兩種東西：一是元素——就是提供一些基本的數據類型；二是規則——基本元素之間的運演算法則。

以上兩種東西合起來，就是這門語言的「類型系統」。數學一點而言，就是定義一個基本集合，並定義在這個集合之上的運算。

這看起來沒什麼了不起。常常被人們忽略，但事實上，我們複雜的世界本質上也不過是由一些簡單的基本單元基於一些基本規則運動的結果。語言設計也遵循這一原則。

可以說，類型系統是一門語言的核心。因為一門編程語言，本質而言，主要做兩件事情：一是描述信息；二是處理信息。

描述信息需要使用存儲空間，而處理信息需要使用運算。問題是運算本身對存儲空間會進行特別的解釋和假設，這就導致了我們的存儲空間儘管都是位元組或之類的看起來別無二致的通用的空間，但從語言角度來看必須對這些空間進行特別的限定和理解，於是便產生了」類型「的概念。

例如C語言有double和long，本質而言兩種類型都是使用位元組進行存儲。但由於運算時採取完全不同的解釋（甚至會採用cpu內部不同的運算器件），因此有必要對他們進行區分。

設計類型系統，特別是小而強大的類型系統，非常不容易！實際上我一開始以為這是很簡單的一件事情，因為自己編程也有幾年了，對編程很熟悉。但是很快我就發現事情不是那麼簡單。你需要做許多工作，而且一些細微的決策改變會深刻的影響這門語言。

這方面我不太打算給出什麼建議，因為有許多論文和專著可供參考。相信如果你有興趣，可以自己弄明白。

除了基本的類型系統之外，語言還需要有一些流程式控制制機制。和代碼組織機制。這些都需要設計。可以借鑒現有的編程語言，也可以創造獨一無二的新方式。隨你自由。

至於對象、變數什麼的，其實之前設計類型系統的時候就已經涵蓋了。函數之類的在類型系統中也會涉及，同時也會影響代碼組織機制等等。

我建議你參考這本書《程序設計語言——實踐之路》。

我參考了許多編譯方面的書籍，包括國外的經典著作。獲得了很多幫助，不過看那些書你會發現總是離真正想要的「細節」尚有距離。給你推薦的這本書就彌補了這一細節上的缺失。是一門真正的實踐教材。缺點是封面設計得太糟糕，知道的人不多，以及銷量太少。但我必須強調這本書給我很大的幫助。（我甚至專門聯繫過書的作者，向他抱怨書的封面實在設計得太糟糕了，難道出版社不能找一個會設計的人來做這件事嗎？他回答說他沒有辦法，因為出版社打算把這本書和其他基本不同的書一起組成一個系列，所以採用了一致的封面設計。我只能深表遺憾）

另外，《現代編譯原理——C語言描述》這本書也很不錯，會有一些比較新的和高階一些的技術。（不過再新也不可能有論文新，只有看論文才能知道業界最新進展）

《編譯器構造（英文版）》很棒，適合初學者。我買的是英文版，因為更容易看懂。

希望羅嗦了一大堆，對你有一丁點兒的幫助。

前面說得很多了。這裡給個不同的例子（基於λ演算）。7行代碼，3分鐘，從0開始實現一個圖靈等價的編程語言。

7 lines of code, 3 minutes: Implement a programminglanguage from scratch

http:// http://matt.might.net/articles/implementing-a-programming-language/

（不知道怎麼可以貼代碼，貼圖吧）

無事莫跳語言坑

LL、LR之類的語法分析只是繁雜，而語義分析的各種細節才是繁難，而且不好測試；

實現複雜的type system（譬如Haskell、Scala這樣的）需要相當的功底，所以業餘愛好者開發的語言（譬如Python、PHP）很多是動態類型的，且早期版本往往比較低效；

優化要考慮的東西特別多，即便有了LLVM等工具，還是需要自己做High Level的優化以及Runtime的設計；

。。。

大哉問。讓我試試從最簡單的概念角度回答一下：

首先要有愛。純粹的，不屈的，傾注全心的愛。對於一個語言所塑造，只存在你想像之中的完美世界的愛……

……呃，然後你要決定你想設計的語言應該解決什麼問題。雖然阿達·愛蕾絲女士[1]作為世界上第一個程序員，並沒有使用任何特定的人造語言來編程，但現如今世風日下、人心不古，人們不再滿足於用計算機算個伯努利數列，還要它解決登月、模擬核爆、設計氣動外形、乃至用紅鳥炸綠豬這樣棘手的技術問題。面對不同的領域、不同的需求、不同的抽象層級、不同的思考範式，也就產生了各有特長的編程語言。專註於高效、便捷地解決某特定範疇之內問題的語言，叫做領域專用語言（Domain Specific Language，DSL）[2]，而可以跨越若干領域解決問題的語言，叫做泛用語言（General-Purpose Language，GPL）[3]。常見的 DSL 比如 MATLAB、SQL 等等；常見的 GPL 自然就是那些 C 啦 Python 啦什麼的。哦還有彙編。當然，兩類語言之間的分界並不是很明顯，有些語言一開始是作為 DSL 設計的，後來漸漸朝著 GPL 的方向發展，比如 PHP 和 JavaScript；反過來也有大量基於 GPL 開發而來的 DSL。注意也不是所有的計算機語言都可以歸入這兩類，有些語言被創造出來的理由很簡單——「因為我們可以做到」，或者「就是為了好玩」，所以它們喚作「蛋痛編程語言」（Esoteric Programming Language）。

當然你的第一個自製語言也許只是為了嘗試一下這件事情是否可行。嘗試可行性，其實已經接近於「就是為了好玩」的境界了，所以要有蛋痛的覺悟，因為從頭設計一套編程語言是頗為蛋痛的事情，幾乎要事必躬親，花費幾天時間來實現微不足道的功能，展示給別人看時卻招來「這有什麼稀奇？」的茫然一問。如果不能樂在其中，如果愛意不夠純粹、不屈、傾注全心，是沒辦法做成的。

從最基本的角度看，一種編程語言就是：把一組特定的辭彙，按照一組特定的語法規則組合到一起，形成計算機可以通過某種方式「理解」的東西，可以讓計算機據此執行特定的動作。

先看看這件事情的最底層。所謂「計算機執行動作」，其實只是「把一個二進位數字傳入 CPU，然後等待什麼事情發生」的形而上描述。二進位計算機所能理解的唯一東西就是二進位數字，稱為「機器碼」[5]。比如：

10110 000 01100001

這串數字，對於某顆 CPU 來說，就是「把 01100001 放到 000 號寄存器里」的指令，其中「10110」的部分，就是 CPU 能懂得的「放入」指令。這樣的指還有許許多多，比如做加法、求邏輯「與」，跳轉，加密等等，全都只是一些二進位數字而已。

對人類來說，這種純數字的寫法太難記憶，就把它轉寫成：

MOV AL, 97

其中 MOV 代表「10110」，AL 代表 000 號寄存器，97 則是二進位數 01100001 的十進位表示。其他的數字指令也一併用這種簡記法來轉寫，比如[6]。使用這樣的一種轉寫方法來寫程序，就是彙編語言（當然，這是一種極度簡化的說法）。彙編語言談不上太多設計，其實幾乎就是在直接告訴 CPU 應該做什麼。把彙編語言轉化為機器碼的程序，稱為「彙編器（Assembler）「。

彙編語言的優勢是很低級，你能直接控制 CPU 的行為；彙編語言的缺點也是它太低級，你必須直接控制 CPU 的行為。看看「把 A 的值放進甲寄存器；B 的值放進乙寄存器；把乙寄存器的值放進 A；把甲寄存器的值放進 B。」這段彙編指令——它想幹什麼？運行一下之後會看到，A 和 B 的值互換了。那麼，能不能直接寫「交換變數 A 和 B 的值」，然後由計算機來分解為一串機器碼的組合呢？

所謂的「高級」編程語言就是這樣的原理。將高級編程語言翻譯成機器碼（或者其他更接近機器碼的形式）的過程，也就是計算機「理解」語言的過程，叫做「編譯」，而完成這一工作的程序，叫做「編譯器（compiler）」或者「解釋器（interpreter）」，兩者的區別是，編譯器一次性解析所有代碼並轉換成機器碼（但通常不會運行），而解釋器則每解析一小部分就運行一小部分。

接下來就要考慮兩個問題：高級語言要讓人寫起來方便；也要讓計算機易懂。因為人類是難搞的物種，所以前者通常是語言設計的重點。畢竟，只要懂些編程的基本知識，任何人都可以在三天時間裡設計出一門計算機語言，並且讓計算機讀懂它（也就是寫出編譯器），但要讓一種計算機語言寫起來舒服、讀起來易懂、管理起來方便，所需耗費的心力和時間則相去不可以道里計。探尋這一問題的種種思潮所引發的範式轉換和生產力革命，是計算機歷史的永恆主題之一。計算機語言越來越高級，使用起來越來越簡單，實現卻越來越複雜；許多編程觀念比如面向對象（object orientation）、函數編程（functional programming）、事件驅動（event driven）之誕生、沉寂、重現、興盛和定型，都經由編程語言有所體現。

當然這並不是說編譯部分就不重要。可靠、高效、靈活的編譯器是一切編程工作的基石。我們日常所用的編譯器都是如此千錘百鍊的東西，以至於你很少會意識到它們本身也是複雜的軟體工程項目，也有可能出問題，也在不斷地發展著。十年前和現在的編譯器，從架構理念到實現都有不小的差別。好在這種差別算不上天翻地覆，計算機語言編譯的大致過程一直都是如下幾個步驟：

高級語言的源代碼經過詞法分析（lexical analysis）成為一堆符記（token）
符記經過句法分析（syntactic analysis）成為語法樹（abstract syntax tree, AST）
語法樹經過優化，比如去除冗餘的部分，最後映射成為機器碼（machine code）

第一步，詞法分析，根據的是語言設計者所規定的辭彙規則。比如 PHP 規定變數前頭必須加個 $ 符號，就是這樣的規則。通常通過正則表達式（regular expression）給出這些規則。根據規則來分析源代碼的編譯器組件叫做詞法分析器（lexer）或者掃描器（scanner）。掃描器可以自己手寫，也可以讓叫做 scanner generator 的程序讀取一個正則表達式，然後幫你生成一個 scanner，比如 lex [7] 就是這樣一個工具。詞法分析的目的是判斷人類寫下的每個詞是不是合乎拼寫規則，如果不符的話，顯然也就無法編譯了。

第二步，句法分析，根據的是語言設計者所規定的語法規則。關於形式語言的語法理論，涉及到語言學和數理邏輯，是一個複雜而艱深的領域，好在對於設計一門計算機語言來說，只需要知道，計算機語言的語法通常是上下文無關文法（context-free grammar）[8] 即可：生成一條計算機語句的規則與這一規則所處的環境無關。這樣一來，解析一條編程語句的過程就是確定的無二的。根據規則來將上一步驟獲得的辭彙解析為特定的數據結構——比如語法樹——的工具，叫做句法分析器（parser）。同樣，句法分析器可以自己寫，也可以用特定的方法（最常見的是巴克斯範式（BNF）[9]）給出下上下文無關文法的形式語言描述，然後用所謂 parser generator 來生成。可以說，語法樹（或者類似的中間產物）代表了從編程語句中提煉出來的意義，這是整個編譯過程的核心所在。

第三步，語法樹或者其他的語義表示方法經由優化器（optimizer）的修剪，送入負責將特定結構轉化為目標機器代碼的程序生成可以運行的二進位程序。這一步必須考慮執行效率優化和目標架構的特點，與高級編程語言本身已經並無太大關聯了。

了解以上步驟之後，就可以設計編程語言了。相關的指導書籍有很經典的幾本，分別是：

龍書（Dragon Book）： Compilers: Principles, Techniques, Tools

虎書（Tiger Book）：Compiler Implementation in C

鯨書（Whale Book）：Advanced Compiler Design and Implementation

橡書（Ark Book) ：Engineering a Compiler

還有魔法書（Wizard Book）：Structure and Interpretation of Computer Programs

[1] http://en.wikipedia.org/wiki/Ada_Lovelace

[2] http://en.wikipedia.org/wiki/Domain-specific_language ，注意 DSL 並不一定是編程語言，有些 DSL 只用來描述數據

[3] http://en.wikipedia.org/wiki/General-purpose_programming_language

[4] http://en.wikipedia.org/wiki/Esoteric_programming_languages

[5] http://en.wikipedia.org/wiki/Machine_code

[6] http://en.wikipedia.org/wiki/X86_instruction_listings

[7] http://en.wikipedia.org/wiki/Lex_(software)

[8] http://en.wikipedia.org/wiki/Context-free_grammar

[9] http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

從類型系統開始：

分類型嗎？
有積類型嗎？
有和類型嗎？
有遞歸類型嗎？
有參數多態嗎？
有依存類型嗎？
有子類型關係嗎？
能居留皮爾士律（Pierce Law）嗎？

我覺得任何語言都可以編譯為機器可讀的2進位命令，包括一切解釋語言。對於不能切離運行時的語言解釋，那麼要做的就是把運行時和低級指令也一起編譯而已。