日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
90分鐘實(shí)現(xiàn)一門編程語言——極簡(jiǎn)解釋器教程

關(guān)鍵字

解釋器, C#, Scheme, 函數(shù)式編程

成都創(chuàng)新互聯(lián)公司專注于企業(yè)營銷型網(wǎng)站建設(shè)、網(wǎng)站重做改版、久治網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5頁面制作、商城網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為久治等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

關(guān)于

本文介紹了如何使用C#實(shí)現(xiàn)一個(gè)簡(jiǎn)化但全功能的Scheme方言——iScheme及其解釋器，通過從零開始逐步構(gòu)建，展示了編程語言/解釋器的工作原理。

作者

Lucida a.k.a Luc

如果你是通過移動(dòng)設(shè)備閱讀本教程，或者認(rèn)為本文的代碼字體太小的，請(qǐng)使用該鏈接以獲得更好的可讀性（博客園的markdown解析器實(shí)在詭異，這里就不多吐槽了）。

提示

如果你對(duì)下面的內(nèi)容感興趣：

  • 實(shí)現(xiàn)基本的詞法分析，語法分析并生成抽象語法樹。
  • 實(shí)現(xiàn)嵌套作用域和函數(shù)調(diào)用。
  • 解釋器的基本原理。
  • 以及一些C#編程技巧。

那么請(qǐng)繼續(xù)閱讀。

如果你對(duì)以下內(nèi)容感興趣：

  • 高級(jí)的詞法/語法分析技術(shù)。
  • 類型推導(dǎo)/分析。
  • 目標(biāo)代碼優(yōu)化。

本文則過于初級(jí)，你可以跳過本文，但歡迎指出本文的錯(cuò)誤 ????

代碼樣例

代碼示例

 
 
    
  
  
  1. public static int Add(int a, int b) {  
    2. 
  
  
  2.     return a + b;  
    3. 
  
  
  3. }  
    4. 
  
  
  4.  
    5. 
  
  
  5. >> Add(3, 4)  
    6. 
  
  
  6. >> 7  
    7. 
  
  
  7.  
    8. 
  
  
  8. >> Add(5, 5)  
    9. 
  
  
  9. >> 10 
    10.

這段代碼定義了Add函數(shù)，接下來的>>符號(hào)表示對(duì)Add(3, 4)進(jìn)行求值，再下一行的>> 7表示上一行的求值結(jié)果，不同的求值用換行分開。可以把這里的>>理解成控制臺(tái)提示符（即Terminal中的PS）。

什么是解釋器

解釋器（Interpreter）是一種程序，能夠讀入程序并直接輸出結(jié)果，如上圖。相對(duì)于編譯器（Compiler），解釋器并不會(huì)生成目標(biāo)機(jī)器代碼，而是直接運(yùn)行源程序，簡(jiǎn)單來說：

 解釋器是運(yùn)行程序的程序。

計(jì)算器就是一個(gè)典型的解釋器，我們把數(shù)學(xué)公式（源程序）給它，它通過運(yùn)行它內(nèi)部的"解釋器"給我們答案。

iScheme編程語言

iScheme是什么？

  • Scheme語言的一個(gè)極簡(jiǎn)子集。
  • 雖然小，但變量，算術(shù)|比較|邏輯運(yùn)算，列表，函數(shù)和遞歸這些編程語言元素一應(yīng)俱全。
  • 非常非常慢——可以說它只是為演示本文的概念而存在。

OK，那么Scheme是什么？

  • 一種函數(shù)式程序設(shè)計(jì)語言。
  • 一種Lisp方言。
  • 麻省理工學(xué)院程序設(shè)計(jì)入門課程使用的語言（參見MIT 6.001和《計(jì)算機(jī)程序的構(gòu)造與解釋》）。

  • 使用波蘭表達(dá)式（Polish Notation）。
  • 更多的介紹參見Scheme編程語言。

以計(jì)算階乘為例：

C#版階乘

 
 
    
  
  
  1. public static int Factorial(int n) {  
    2. 
  
  
  2.     if (n == 1) {  
    3. 
  
  
  3.         return 1;  
    4. 
  
  
  4.     } else {  
    5. 
  
  
  5.         return n * Factorial(n - 1);  
    6. 
  
  
  6.     }  
    7. 
  
  
  7. } 
    8.

iScheme版階乘

 
 
    
  
  
  1. (def factorial (lambda (n) (  
    2. 
  
  
  2.     if (= n 1)  
    3. 
  
  
  3.        1  
    4. 
  
  
  4.        (* n (factorial (- n 1)))))) 
    5.

數(shù)值類型

由于iScheme只是一個(gè)用于演示的語言，所以目前只提供對(duì)整數(shù)的支持。iScheme使用C#的Int64類型作為其內(nèi)部的數(shù)值表示方法。

定義變量

iScheme使用def關(guān)鍵字定義變量

 
 
    
  
  
  1. >> (def a 3)  
    2. 
  
  
  2. >> 3  
    3. 
  
  
  3.  
    4. 
  
  
  4. >> a  
    5. 
  
  
  5. >> 3 
    6.

算術(shù)|邏輯|比較操作

與常見的編程語言（C#, Java, C++, C）不同，Scheme使用波蘭表達(dá)式，即前綴表示法。例如：

C#中的算術(shù)|邏輯|比較操作

 
 
    
  
  
  1. // Arithmetic ops  
    2. 
  
  
  2. a + b * c  
    3. 
  
  
  3. a / (b + c + d)  
    4. 
  
  
  4. // Logical ops  
    5. 
  
  
  5. (cond1 && cond2) || cond3  
    6. 
  
  
  6. // Comparing ops  
    7. 
  
  
  7. a == b  
    8. 
  
  
  8. 1 < a && a < 3 
    9.

對(duì)應(yīng)的iScheme代碼

 
 
    
  
  
  1. ; Arithmetic ops  
    2. 
  
  
  2. (+ a (* b c))  
    3. 
  
  
  3. (/ a (+ b c d))  
    4. 
  
  
  4. ; Logical ops  
    5. 
  
  
  5. (or (and cond1 cond2) cond3)  
    6. 
  
  
  6. ; Comparing ops  
    7. 
  
  
  7. (= a b)  
    8. 
  
  
  8. (< 1 a 3) 
    9.

需要注意的幾點(diǎn)：

  1. iScheme中的操作符可以接受不止兩個(gè)參數(shù)——這在一定程度上控制了括號(hào)的數(shù)量。
  2. iScheme邏輯操作使用and, or和not代替了常見的&&, ||和!——這在一定程度上增強(qiáng)了程序的可讀性。

順序語句

iScheme使用begin關(guān)鍵字標(biāo)識(shí)順序語句，并以最后一條語句的值作為返回結(jié)果。以求兩個(gè)數(shù)的平均值為例：

C#的順序語句

 
 
    
  
  
  1. int a = 3;  
    2. 
  
  
  2. int b = 5;  
    3. 
  
  
  3. int c = (a + b) / 2; 
    4.

iScheme的順序語句

 
 
    
  
  
  1. (def c (begin  
    2. 
  
  
  2.     (def a 3)  
    3. 
  
  
  3.     (def b 5)  
    4. 
  
  
  4.     (/ (+ a b) 2))) 
    5.

控制流操作

iScheme中的控制流操作只包含if。

if語句示例

 
 
    
  
  
  1. >> (define a (if (> 3 2) 1 2))  
    2. 
  
  
  2. >> 1  
    3. 
  
  
  3.  
    4. 
  
  
  4. >> a  
    5. 
  
  
  5. >> 1 
    6.

列表類型

iScheme使用list關(guān)鍵字定義列表，并提供first關(guān)鍵字獲取列表的第一個(gè)元素；提供rest關(guān)鍵字獲取列表除第一個(gè)元素外的元素。

iScheme的列表示例

 
 
    
  
  
  1. >> (define alist (list 1 2 3 4))  
    2. 
  
  
  2. >> (list 1 2 3 4)  
    3. 
  
  
  3.  
    4. 
  
  
  4. >> (first alist)  
    5. 
  
  
  5. >> 1  
    6. 
  
  
  6.  
    7. 
  
  
  7. >> (rest alist)  
    8. 
  
  
  8. >> (2 3 4) 
    9.

定義函數(shù)

iScheme使用func關(guān)鍵字定義函數(shù)：

iScheme的函數(shù)定義

 
 
    
  
  
  1. (def square (func (x) (* x x)))  
    2. 
  
  
  2.  
    3. 
  
  
  3. (def sum_square (func (a b) (+ (square a) (square b)))) 
    4.

對(duì)應(yīng)的C#代碼

 
 
    
  
  
  1. public static int Square (int x) {  
    2. 
  
  
  2.     return x * x;  
    3. 
  
  
  3. }  
    4. 
  
  
  4.  
    5. 
  
  
  5. public static int SumSquare(int a, int b) {  
    6. 
  
  
  6.     return Square(a) + Square(b);  
    7. 
  
  
  7. } 
    8.

遞歸

由于iScheme中沒有for或while這種命令式語言（Imperative Programming Language）的循環(huán)結(jié)構(gòu)，遞歸成了重復(fù)操作的唯一選擇。

以計(jì)算最大公約數(shù)為例：

iScheme計(jì)算最大公約數(shù)

 
 
    
  
  
  1. (def gcd (func (a b)  
    2. 
  
  
  2.     (if (= b 0)  
    3. 
  
  
  3.         a  
    4. 
  
  
  4.         (func (b (% a b)))))) 
    5.

對(duì)應(yīng)的C#代碼

 
 
    
  
  
  1. public static int GCD (int a, int b) {  
    2. 
  
  
  2.     if (b == 0) {  
    3. 
  
  
  3.         return a;  
    4. 
  
  
  4.     } else {  
    5. 
  
  
  5.         return GCD(b, a % b);  
    6. 
  
  
  6.     }  
    7. 
  
  
  7. } 
    8.

#p#

高階函數(shù)

和Scheme一樣，函數(shù)在iScheme中是頭等對(duì)象，這意味著：

  • 可以定義一個(gè)變量為函數(shù)。
  • 函數(shù)可以接受一個(gè)函數(shù)作為參數(shù)。
  • 函數(shù)返回一個(gè)函數(shù)。

iScheme的高階函數(shù)示例

 
 
    
  
  
  1. ; Defines a multiply function.  
    2. 
  
  
  2. (def mul (func (a b) (* a b)))  
    3. 
  
  
  3. ; Defines a list map function.  
    4. 
  
  
  4. (def map (func (f alist)  
    5. 
  
  
  5.     (if (empty? alist)  
    6. 
  
  
  6.         (list )  
    7. 
  
  
  7.         (append (list (f (first alist))) (map f (rest alist)))  
    8. 
  
  
  8.         )))  
    9. 
  
  
  9. ; Doubles a list using map and mul.  
    10. 
  
  
  10. >> (map (mul 2) (list 1 2 3))  
    11. 
  
  
  11. >> (list 2 4 6) 
    12.

小結(jié)

對(duì)iScheme的介紹就到這里——事實(shí)上這就是iScheme的所有元素，會(huì)不會(huì)太簡(jiǎn)單了？ -_-

接下來進(jìn)入正題——從頭開始構(gòu)造iScheme的解釋程序。

解釋器構(gòu)造

iScheme解釋器主要分為兩部分，解析（Parse）和求值（Evaluation）：

  • 解析（Parse）：解析源程序，并生成解釋器可以理解的中間（Intermediate）結(jié)構(gòu)。這部分包含詞法分析，語法分析，語義分析，生成語法樹。
  • 求值（Evaluation）：執(zhí)行解析階段得到的中介結(jié)構(gòu)然后得到運(yùn)行結(jié)果。這部分包含作用域，類型系統(tǒng)設(shè)計(jì)和語法樹遍歷。

詞法分析

詞法分析負(fù)責(zé)把源程序解析成一個(gè)個(gè)詞法單元（Lex），以便之后的處理。

iScheme的詞法分析極其簡(jiǎn)單——由于iScheme的詞法元素只包含括號(hào)，空白，數(shù)字和變量名，因此C#自帶的String#Split就足夠。

iScheme的詞法分析及測(cè)試

 
 
    
  
  
  1. public static String[] Tokenize(String text) {  
    2. 
  
  
  2.     String[] tokens = text.Replace("(", " ( ").Replace(")", " ) ").Split(" \t\r\n".ToArray(), StringSplitOptions.RemoveEmptyEntries);  
    3. 
  
  
  3.     return tokens;  
    4. 
  
  
  4. }  
    5. 
  
  
  5.  
    6. 
  
  
  6. // Extends String.Join for a smooth API.  
    7. 
  
  
  7. public static String Join(this String separator, IEnumerable values) {  
  
  
  8.     return String.Join(separator, values);  
    9. 
  
  
  9. }  
    10. 
  
  
  10.  
    11. 
  
  
  11. // Displays the lexes in a readable form.  
    12. 
  
  
  12. public static String PrettyPrint(String[] lexes) {  
    13. 
  
  
  13.     return "[" + ", ".Join(lexes.Select(s => "'" + s + "'") + "]";  
    14. 
  
  
  14. }  
    15. 
  
  
  15.  
    16. 
  
  
  16. // Some tests  
    17. 
  
  
  17. >> PrettyPrint(Tokenize("a"))  
    18. 
  
  
  18. >> ['a']  
    19. 
  
  
  19.  
    20. 
  
  
  20. >> PrettyPrint(Tokenize("(def a 3)"))  
    21. 
  
  
  21. >> ['(', 'def', 'a', '3', ')']  
    22. 
  
  
  22.  
    23. 
  
  
  23. >> PrettyPrint(Tokenize("(begin (def a 3) (* a a))"))  
    24. 
  
  
  24. >> ['begin', '(', 'def', 'a', '3', ')', '(', '*', 'a', 'a', ')', ')'] 
    25. 
 
 

    注意
    

      

    • 個(gè)人不喜歡String.Join這個(gè)靜態(tài)方法，所以這里使用C#的擴(kuò)展方法（Extension Methods）對(duì)String類型做了一個(gè)擴(kuò)展。
      • 

    • 相對(duì)于LINQ Syntax，我個(gè)人更喜歡LINQ Extension Methods，接下來的代碼也都會(huì)是這種風(fēng)格。
      • 

    • 不要以為詞法分析都是這么離譜般簡(jiǎn)單！vczh的詞法分析教程給出了一個(gè)完整編程語言的詞法分析教程。
    語法樹生成
    

    得到了詞素之后，接下來就是進(jìn)行語法分析。不過由于Lisp類語言的程序即是語法樹，所以語法分析可以直接跳過。
    以下面的程序?yàn)槔?/p>
    程序即語法樹
     
 
      
  
  
    1. ;  
      2. 
  
  
    2. (def x (if (> a 1) a 1))  
      3. 
  
  
    3. ; 換一個(gè)角度看的話：  
      4. 
  
  
    4. (  
      5. 
  
  
    5.     def  
      6. 
  
  
    6.     x  
      7. 
  
  
    7.     (  
      8. 
  
  
    8.         if 
      9. 
  
  
    9.         (  
      10. 
  
  
    10.             >  
      11. 
  
  
    11.             a  
      12. 
  
  
    12.             1  
      13. 
  
  
    13.         )  
      14. 
  
  
    14.         a  
      15. 
  
  
    15.         1  
      16. 
  
  
    16.     )  
      17. 
  
  
    17. ) 
      18. 
 
 
    更加直觀的圖片：
    這使得抽象語法樹（Abstract Syntax Tree）的構(gòu)建變得極其簡(jiǎn)單（無需考慮操作符優(yōu)先級(jí)等問題），我們使用SExpression類型定義iScheme的語法樹（事實(shí)上S Expression也是Lisp表達(dá)式的名字）。
    抽象語法樹的定義
     
 
      
  
  
    1. public class SExpression {  
      2. 
  
  
    2.     public String Value { get; private set; }  
      3. 
  
  
    3.     public List Children { get; private set; }  
      4. 
  
  
    4.     public SExpression Parent { get; private set; }  
      5. 
  
  
    5.  
      6. 
  
  
    6.     public SExpression(String value, SExpression parent) {  
      7. 
  
  
    7.         this.Value = value;  
      8. 
  
  
    8.         this.Children = new List();  
      9. 
  
  
    9.         this.Parent = parent;  
      10. 
  
  
    10.     }  
      11. 
  
  
    11.  
      12. 
  
  
    12.     public override String ToString() {  
      13. 
  
  
    13.         if (this.Value == "(") {  
      14. 
  
  
    14.             return "(" + " ".Join(Children) + ")";  
      15. 
  
  
    15.         } else {  
      16. 
  
  
    16.             return this.Value;  
      17. 
  
  
    17.         }  
      18. 
  
  
    18.     }  
      19. 
  
  
    19. } 
      20. 
 
 
    然后用下面的步驟構(gòu)建語法樹：
      

    1. 碰到左括號(hào)，創(chuàng)建一個(gè)新的節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)（current），然后重設(shè)當(dāng)前節(jié)點(diǎn)。
      2. 

    2. 碰到右括號(hào)，回退到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。
      3. 

    3. 否則把為當(dāng)前詞素創(chuàng)建節(jié)點(diǎn)，添加到當(dāng)前節(jié)點(diǎn)中。
      4. 

    

    抽象語法樹的構(gòu)建過程
     
 
      
  
  
    1. public static SExpression ParseAsIScheme(this String code) {  
      2. 
  
  
    2.     SExpression program = new SExpression(value: "", parent: null);  
      3. 
  
  
    3.     SExpression current = program;  
      4. 
  
  
    4.     foreach (var lex in Tokenize(code)) {  
      5. 
  
  
    5.         if (lex == "(") {  
      6. 
  
  
    6.             SExpression newNode = new SExpression(value: "(", parent: current);  
      7. 
  
  
    7.             current.Children.Add(newNode);  
      8. 
  
  
    8.             current = newNode;  
      9. 
  
  
    9.         } else if (lex == ")") {  
      10. 
  
  
    10.             current = current.Parent;  
      11. 
  
  
    11.         } else {  
      12. 
  
  
    12.             current.Children.Add(new SExpression(value: lex, parent: current));  
      13. 
  
  
    13.         }  
      14. 
  
  
    14.     }  
      15. 
  
  
    15.     return program.Children[0];  
      16. 
  
  
    16. } 
      17. 
 
 
    

    注意
    

      

    • 使用自動(dòng)屬性（Auto Property），從而避免重復(fù)編寫樣版代碼（Boilerplate Code）。
      • 

    • 使用命名參數(shù)（Named Parameters）提高代碼可讀性：new SExpression(value: "", parent: null)比new SExpression("", null)可讀。
      • 

    • 使用擴(kuò)展方法提高代碼流暢性：code.Tokenize().ParseAsIScheme比ParseAsIScheme(Tokenize(code))流暢。
      • 

    • 大多數(shù)編程語言的語法分析不會(huì)這么簡(jiǎn)單！如果打算實(shí)現(xiàn)一個(gè)類似C#的編程語言，你需要更強(qiáng)大的語法分析技術(shù)：

        

      • 如果打算手寫語法分析器，可以參考LL(k), Precedence Climbing和Top Down Operator Precedence。
        • 

      • 如果打算生成語法分析器，可以參考ANTLR或Bison。
        • 

      

    作用域
    

    作用域決定程序的運(yùn)行環(huán)境。iScheme使用嵌套作用域。
    以下面的程序?yàn)槔?/p>
     
 
      
  
  
    1. >> (def x 1)  
      2. 
  
  
    2. >> 1  
      3. 
  
  
    3.  
      4. 
  
  
    4. >> (def y (begin (def x 2) (* x x)))  
      5. 
  
  
    5. >> 4  
      6. 
  
  
    6.  
      7. 
  
  
    7. >> x  
      8. 
  
  
    8. >> 1 
      9. 
 
 
    利用C#提供的Dictionary類型，我們可以很容易的實(shí)現(xiàn)iScheme的作用域SScope：
    iScheme的作用域?qū)崿F(xiàn)
     
 
      
  
  
    1. public class SScope {  
      2. 
  
  
    2.     public SScope Parent { get; private set; }  
      3. 
  
  
    3.     private Dictionary variableTable;  
      4. 
  
  
    4.  
      5. 
  
  
    5.     public SScope(SScope parent) {  
      6. 
  
  
    6.         this.Parent = parent;  
      7. 
  
  
    7.         this.variableTable = new Dictionary();  
      8. 
  
  
    8.     }  
      9. 
  
  
    9.  
      10. 
  
  
    10.     public SObject Find(String name) {  
      11. 
  
  
    11.         SScope current = this;  
      12. 
  
  
    12.         while (current != null) {  
      13. 
  
  
    13.             if (current.variableTable.ContainsKey(name)) {  
      14. 
  
  
    14.                 return current.variableTable[name];  
      15. 
  
  
    15.             }  
      16. 
  
  
    16.             current = current.Parent;  
      17. 
  
  
    17.         }  
      18. 
  
  
    18.         throw new Exception(name + " is not defined.");  
      19. 
  
  
    19.     }  
      20. 
  
  
    20.  
      21. 
  
  
    21.     public SObject Define(String name, SObject value) {  
      22. 
  
  
    22.         this.variableTable.Add(name, value);  
      23. 
  
  
    23.         return value;  
      24. 
  
  
    24.     }  
      25. 
  
  
    25. } 
      26. 
 
 
    

    類型實(shí)現(xiàn)
    

    iScheme的類型系統(tǒng)極其簡(jiǎn)單——只有數(shù)值，Bool，列表和函數(shù)，考慮到他們都是iScheme里面的值對(duì)象（Value Object），為了便于對(duì)它們進(jìn)行統(tǒng)一處理，這里為它們?cè)O(shè)置一個(gè)統(tǒng)一的父類型SObject：
     
 
      
  
  
    1. public class SObject { } 
      2. 
 
 
    

    數(shù)值類型
    

    iScheme的數(shù)值類型只是對(duì).Net中Int64（即C#里的long）的簡(jiǎn)單封裝：
     
 
      
  
  
    1. public class SNumber : SObject {  
      2. 
  
  
    2.     private readonly Int64 value;  
      3. 
  
  
    3.     public SNumber(Int64 value) {  
      4. 
  
  
    4.         this.value = value;  
      5. 
  
  
    5.     }  
      6. 
  
  
    6.     public override String ToString() {  
      7. 
  
  
    7.         return this.value.ToString();  
      8. 
  
  
    8.     }  
      9. 
  
  
    9.     public static implicit operator Int64(SNumber number) {  
      10. 
  
  
    10.         return number.value;  
      11. 
  
  
    11.     }  
      12. 
  
  
    12.     public static implicit operator SNumber(Int64 value) {  
      13. 
  
  
    13.         return new SNumber(value);  
      14. 
  
  
    14.     }  
      15. 
  
  
    15. } 
      16. 
 
 
    注意這里使用了C#的隱式操作符重載，這使得我們可以：
     
 
      
  
  
    1. SNumber foo = 30;  
      2. 
  
  
    2. SNumber bar = 40;  
      3. 
  
  
    3. SNumber foobar = foo * bar; 
      4. 
 
 
    而不必：
     
 
      
  
  
    1. SNumber foo = new SNumber(value: 30);  
      2. 
  
  
    2. SNumber bar = new SNumber(value: 40);  
      3. 
  
  
    3. SNumber foobar = new SNumber(value: foo.Value * bar.Value); 
      4. 
 
 
    為了方便，這里也為SObject增加了隱式操作符重載（盡管Int64可以被轉(zhuǎn)換為SNumber且SNumber繼承自SObject，但.Net無法直接把Int64轉(zhuǎn)化為SObject）：
     
 
      
  
  
    1. public class SObject {  
      2. 
  
  
    2.     ...  
      3. 
  
  
    3.     public static implicit operator SObject(Int64 value) {  
      4. 
  
  
    4.         return (SNumber)value;  
      5. 
  
  
    5.     }  
      6. 
  
  
    6. } 
      7. 
 
 
    

    Bool類型
    

    由于Bool類型只有True和False，所以使用靜態(tài)對(duì)象就足矣。
     
 
      
  
  
    1. public class SBool : SObject {  
      2. 
  
  
    2.     public static readonly SBool False = new SBool();  
      3. 
  
  
    3.     public static readonly SBool True = new SBool();  
      4. 
  
  
    4.     public override String ToString() {  
      5. 
  
  
    5.         return ((Boolean)this).ToString();  
      6. 
  
  
    6.     }  
      7. 
  
  
    7.     public static implicit operator Boolean(SBool value) {  
      8. 
  
  
    8.         return value == SBool.True;  
      9. 
  
  
    9.     }  
      10. 
  
  
    10.     public static implicit operator SBool(Boolean value) {  
      11. 
  
  
    11.         return value ? True : False;  
      12. 
  
  
    12.     }  
      13. 
  
  
    13. } 
      14. 
 
 
    這里同樣使用了C#的隱式操作符重載，這使得我們可以：
     
 
      
  
  
    1. SBool foo = a > 1;  
      2. 
  
  
    2. if (foo) {  
      3. 
  
  
    3.     // Do something...  
      4. 
  
  
    4. } 
      5. 
 
 
    而不用
     
 
      
  
  
    1. SBool foo = a > 1 ? SBool.True: SBool.False;  
      2. 
  
  
    2. if (foo == SBool.True) {  
      3. 
  
  
    3.     // Do something...  
      4. 
  
  
    4. } 
      5. 
 
 
    同樣，為SObject增加隱式操作符重載：
     
 
      
  
  
    1. public class SObject {  
      2. 
  
  
    2.     ...  
      3. 
  
  
    3.     public static implicit operator SObject(Boolean value) {  
      4. 
  
  
    4.         return (SBool)value;  
      5. 
  
  
    5.     }  
      6. 
  
  
    6. } 
      7. 
 
 
    #p#
    列表類型
    

    iScheme使用.Net中的IEnumberable實(shí)現(xiàn)列表類型SList：
     
 
      
  
  
    1. public class SList : SObject, IEnumerable {  
      2. 
  
  
    2.     private readonly IEnumerable values;  
      3. 
  
  
    3.     public SList(IEnumerable values) {  
      4. 
  
  
    4.         this.values = values;  
      5. 
  
  
    5.     }  
      6. 
  
  
    6.     public override String ToString() {  
      7. 
  
  
    7.         return "(list " + " ".Join(this.values) + ")";  
      8. 
  
  
    8.     }  
      9. 
  
  
    9.     public IEnumerator GetEnumerator() {  
      10. 
  
  
    10.         return this.values.GetEnumerator();  
      11. 
  
  
    11.     }  
      12. 
  
  
    12.     IEnumerator IEnumerable.GetEnumerator() {  
      13. 
  
  
    13.         return this.values.GetEnumerator();  
      14. 
  
  
    14.     }  
      15. 
  
  
    15. } 
      16. 
 
 
    實(shí)現(xiàn)IEnumerable后，就可以直接使用LINQ的一系列擴(kuò)展方法，十分方便。
    函數(shù)類型
    

    iScheme的函數(shù)類型（SFunction）由三部分組成：
      

    • 函數(shù)體：即對(duì)應(yīng)的SExpression。
      • 

    • 參數(shù)列表。
      • 

    • 作用域：函數(shù)擁有自己的作用域
      • 

    

    SFunction的實(shí)現(xiàn)
     
 
      
  
  
    1. public class SFunction : SObject {  
      2. 
  
  
    2.     public SExpression Body { get; private set; }  
      3. 
  
  
    3.     public String[] Parameters { get; private set; }  
      4. 
  
  
    4.     public SScope Scope { get; private set; }  
      5. 
  
  
    5.     public Boolean IsPartial {  
      6. 
  
  
    6.         get {  
      7. 
  
  
    7.             return this.ComputeFilledParameters().Length.InBetween(1, this.Parameters.Length);  
      8. 
  
  
    8.         }  
      9. 
  
  
    9.     }  
      10. 
  
  
    10.  
      11. 
  
  
    11.     public SFunction(SExpression body, String[] parameters, SScope scope) {  
      12. 
  
  
    12.         this.Body = body;  
      13. 
  
  
    13.         this.Parameters = parameters;  
      14. 
  
  
    14.         this.Scope = scope;  
      15. 
  
  
    15.     }  
      16. 
  
  
    16.  
      17. 
  
  
    17.     public SObject Evaluate() {  
      18. 
  
  
    18.         String[] filledParameters = this.ComputeFilledParameters();  
      19. 
  
  
    19.         if (filledParameters.Length < Parameters.Length) {  
      20. 
  
  
    20.             return this;  
      21. 
  
  
    21.         } else {  
      22. 
  
  
    22.             return this.Body.Evaluate(this.Scope);  
      23. 
  
  
    23.         }  
      24. 
  
  
    24.     }  
      25. 
  
  
    25.  
      26. 
  
  
    26.     public override String ToString() {  
      27. 
  
  
    27.         return String.Format("(func ({0}) {1})",  
      28. 
  
  
    28.             " ".Join(this.Parameters.Select(p => {  
      29. 
  
  
    29.                 SObject value = null;  
      30. 
  
  
    30.                 if ((value = this.Scope.FindInTop(p)) != null) {  
      31. 
  
  
    31.                     return p + ":" + value;  
      32. 
  
  
    32.                 }  
      33. 
  
  
    33.                 return p;  
      34. 
  
  
    34.             })), this.Body);  
      35. 
  
  
    35.     }  
      36. 
  
  
    36.  
      37. 
  
  
    37.     private String[] ComputeFilledParameters() {  
      38. 
  
  
    38.         return this.Parameters.Where(p => Scope.FindInTop(p) != null).ToArray();  
      39. 
  
  
    39.     }  
      40. 
  
  
    40. } 
      41. 
 
 
    

    需要注意的幾點(diǎn)
    

      

    • iScheme支持部分求值（Partial Evaluation），這意味著：
      • 

    

    部分求值
     
 
      
  
  
    1. >> (def mul (func (a b) (* a b)))  
      2. 
  
  
    2. >> (func (a b) (* a b))  
      3. 
  
  
    3.  
      4. 
  
  
    4. >> (mul 3 4)  
      5. 
  
  
    5. >> 12  
      6. 
  
  
    6.  
      7. 
  
  
    7. >> (mul 3)  
      8. 
  
  
    8. >> (func (a:3 b) (* a b))  
      9. 
  
  
    9.  
      10. 
  
  
    10. >> ((mul 3) 4)  
      11. 
  
  
    11. >> 12 
      12. 
 
 
    也就是說，當(dāng)SFunction的實(shí)際參數(shù)（Argument）數(shù)量小于其形式參數(shù)（Parameter）的數(shù)量時(shí)，它依然是一個(gè)函數(shù)，無法被求值。
    這個(gè)功能有什么用呢？生成高階函數(shù)。有了部分求值，我們就可以使用
     
 
      
  
  
    1. (def mul (func (a b) (* a b)))  
      2. 
  
  
    2. (def mul3 (mul 3))  
      3. 
  
  
    3.  
      4. 
  
  
    4. >> (mul3 3)  
      5. 
  
  
    5. >> 9 
      6. 
 
 
    而不用專門定義一個(gè)生成函數(shù)：
     
 
      
  
  
    1. (def times (func (n) (func (n x) (* n x)) ) )  
      2. 
  
  
    2. (def mul3 (times 3))  
      3. 
  
  
    3.  
      4. 
  
  
    4. >> (mul3 3)  
      5. 
  
  
    5. >> 9 
      6. 
 
 
    

      

    • SFunction#ToString可以將其自身還原為源代碼——從而大大簡(jiǎn)化了iScheme的理解和測(cè)試。
    內(nèi)置操作
    

    iScheme的內(nèi)置操作有四種：算術(shù)|邏輯|比較|列表操作。
    我選擇了表達(dá)力（Expressiveness）強(qiáng)的lambda方法表來定義內(nèi)置操作：
    首先在SScope中添加靜態(tài)字段builtinFunctions，以及對(duì)應(yīng)的訪問屬性BuiltinFunctions和操作方法BuildIn。
     
 
      
  
  
    1. public class SScope {  
      2. 
  
  
    2.     private static Dictionary> builtinFunctions =  
      3. 
  
  
    3.         new Dictionary>();  
      4. 
  
  
    4.     public static Dictionary> BuiltinFunctions {  
      5. 
  
  
    5.         get { return builtinFunctions; }  
      6. 
  
  
    6.     }  
      7. 
  
  
    7.     // Dirty HACK for fluent API.  
      8. 
  
  
    8.     public SScope BuildIn(String name, Func builtinFuntion) {  
      9. 
  
  
    9.         SScope.builtinFunctions.Add(name, builtinFuntion);  
      10. 
  
  
    10.         return this;  
      11. 
  
  
    11.     }  
      12. 
  
  
    12. } 
      13. 
 
 
    注意：
      

    1. Func是C#提供的委托類型，表示一個(gè)接受T1和T2，返回TRESULT
      2. 

    2. 這里有一個(gè)小HACK，使用實(shí)例方法（Instance Method）修改靜態(tài)成員（Static Member），從而實(shí)現(xiàn)一套流暢的API（參見Fluent Interface）。
      3. 

    

    接下來就可以這樣定義內(nèi)置操作：
     
 
      
  
  
    1. new SScope(parent: null)  
      2. 
  
  
    2.     .BuildIn("+", addMethod)  
      3. 
  
  
    3.     .BuildIn("-", subMethod)  
      4. 
  
  
    4.     .BuildIn("*", mulMethod)  
      5. 
  
  
    5.     .BuildIn("/", divMethod); 
      6. 
 
 
    一目了然。
    斷言（Assertion）擴(kuò)展
    

    為了便于進(jìn)行斷言，我對(duì)Boolean類型做了一點(diǎn)點(diǎn)擴(kuò)展。
     
 
      
  
  
    1. public static void OrThrows(this Boolean condition, String message = null) {  
      2. 
  
  
    2.     if (!condition) { throw new Exception(message ?? "WTF"); }  
      3. 
  
  
    3. } 
      4. 
 
 
    從而可以寫出流暢的斷言：
     
 
      
  
  
    1. (a < 3).OrThrows("Value must be less than 3."); 
      2. 
 
 
    而不用
     
 
      
  
  
    1. if (a < 3) {  
      2. 
  
  
    2.         throw new Exception("Value must be less than 3.");  
      3. 
  
  
    3. } 
      4. 
 
 
    

    算術(shù)操作
    

    iScheme算術(shù)操作包含+ - * / %五個(gè)操作，它們僅應(yīng)用于數(shù)值類型（也就是SNumber）。
    從加減法開始：
     
 
      
  
  
    1. .BuildIn("+", (args, scope) => {  
      2. 
  
  
    2.     var numbers = args.Select(obj => obj.Evaluate(scope)).Cast();  
      3. 
  
  
    3.     return numbers.Sum(n => n);  
      4. 
  
  
    4. })  
      5. 
  
  
    5. .BuildIn("-", (args, scope) => {  
      6. 
  
  
    6.     var numbers = args.Select(obj => obj.Evaluate(scope)).Cast().ToArray();  
      7. 
  
  
    7.     Int64 firstValue = numbers[0];  
      8. 
  
  
    8.     if (numbers.Length == 1) {  
      9. 
  
  
    9.         return -firstValue;  
      10. 
  
  
    10.     }  
      11. 
  
  
    11.     return firstValue - numbers.Skip(1).Sum(s => s);  
      12. 
  
  
    12. }) 
      13. 
 
 
    注意到這里有一段重復(fù)邏輯負(fù)責(zé)轉(zhuǎn)型求值（Cast then Evaluation），考慮到接下來還有不少地方要用這個(gè)邏輯，我把這段邏輯抽象成擴(kuò)展方法：
     
 
      
  
  
    1. public static IEnumerable Evaluate(this IEnumerable expressions, SScope scope)  
      2. 
  
  
    2. where T : SObject {  
      3. 
  
  
    3.     return expressions.Evaluate(scope).Cast();  
      4. 
  
  
    4. }  
      5. 
  
  
    5. public static IEnumerable Evaluate(this IEnumerable expressions, SScope scope) {  
      6. 
  
  
    6.     return expressions.Select(exp => exp.Evaluate(scope));  
      7. 
  
  
    7. } 
      8. 
 
 
    然后加減法就可以如此定義：
     
 
      
  
  
    1. .BuildIn("+", (args, scope) => (args.Evaluate(scope).Sum(s => s)))  
      2. 
  
  
    2. .BuildIn("-", (args, scope) => {  
      3. 
  
  
    3.     var numbers = args.Evaluate(scope).ToArray();  
      4. 
  
  
    4.     Int64 firstValue = numbers[0];  
      5. 
  
  
    5.     if (numbers.Length == 1) {  
      6. 
  
  
    6.         return -firstValue;  
      7. 
  
  
    7.     }  
      8. 
  
  
    8.     return firstValue - numbers.Skip(1).Sum(s => s);  
      9. 
  
  
    9. }) 
      10. 
 
 
    乘法，除法和求模定義如下：
     
 
      
  
  
    1. .BuildIn("*", (args, scope) => args.Evaluate(scope).Aggregate((a, b) => a * b))  
      2. 
  
  
    2. .BuildIn("/", (args, scope) => {  
      3. 
  
  
    3.     var numbers = args.Evaluate(scope).ToArray();  
      4. 
  
  
    4.     Int64 firstValue = numbers[0];  
      5. 
  
  
    5.     return firstValue / numbers.Skip(1).Aggregate((a, b) => a * b);  
      6. 
  
  
    6. })  
      7. 
  
  
    7. .BuildIn("%", (args, scope) => {  
      8. 
  
  
    8.     (args.Length == 2).OrThrows("Parameters count in mod should be 2");  
      9. 
  
  
    9.     var numbers = args.Evaluate(scope).ToArray();  
      10. 
  
  
    10.     return numbers[0] % numbers[1];  
      11. 
  
  
    11. }) 
      12. 
 
 
    

    邏輯操作
    

    iScheme邏輯操作包括                                                
    
                                                網(wǎng)頁標(biāo)題：90分鐘實(shí)現(xiàn)一門編程語言——極簡(jiǎn)解釋器教程                                                
    
                                                當(dāng)前URL：http://www.5511xx.com/article/ccioesg.html