C宏元編程:編譯期LISP解釋器（一）總體思路

這是一個超級神奇的項目 CSP GIt Repo

對！純粹用C宏-那個只支持字元串替換和粘貼的東西-寫的LISP解釋器！

（目前還沒有完成，最重要的lambda已經實現了，cond暫時還有問題嵌套會出錯x）

（想拉一些小夥伴一起玩一起燒腦呀！可惜似乎人類玩家直接看源碼大概率大腦爆棧，於是嘗試寫了一些文章之類。。原始wiki可以戳這裡 CSP Wiki

那麼現在就開始玩轉（abuse）C宏定義的神奇（ドM）之旅吧！

總體思路

C宏定義想必大家都熟悉，姑且展開最天馬行空的想像，進行LISP的列表操作（CAR CDR CONS之類）應該是可行的，First-class function某種程度上似乎也可行（傳遞宏名），比如這個例子：

#define E(...) __VA_ARGS__ //單位宏#define N(...) //零宏#define __test(something,k,...) k(do something)#define _test(something,...) __test(something,E)_test(testit) // => __test(testit,E) => E(do testit) => do testit_test(E(N,N)) // => __test(N,N,E) => N(do N) =>//_test(E(N,N))的輸出消失了！

這個例子中我們看到我們將零宏和單位宏作為參數傳入，並使得_test（封裝 __test）具有一個零點 E(N,N)。這個技巧（私貨！）在CSP的實現中經常用到！記筆記！

但是要實現lambda。。似乎純粹的C宏很難做到（比如要把參數代入匿名函數體。。咋整啊）。。

不過別忘了神奇的LISP是可以實現自解釋的！也就是可以用沒有lambda語義的LISP解釋器來實現完整的LISP解釋器。

CSP的實現就按照了這個思路，首先實現解釋器A（其實就是載入了一組實現LISP原語宏的C預處理器），然後再在解釋器A上實現完整的LISP自解釋器B。以下是自解釋器的源碼（不是最新的x 最新的在糾結那個有問題的cond）

//Line 176, csp.h#define $zipped_eval(e,a) COND( (ATOM e (EVAL_e $zipped_assoc(e,a))) (ATOM SAFE_CAR e COND(($eq(SAFE_CAR e (quote))EVAL_e(SAFE_CAR SAFE_CDR e)) ($eq(SAFE_CAR e (atom)) (EVAL_e ATOM DELAY_INT_23($zipped_eval_R)() (SAFE_CAR SAFE_CDR e,a))) ($eq(SAFE_CAR e (eq)) (EVAL_e $eq( DELAY_INT_25($zipped_eval_R)() (SAFE_CAR SAFE_CDR e,a) DELAY_INT_25($zipped_eval_R)() (SAFE_CAR SAFE_CDR SAFE_CDR e,a)))) ($eq(SAFE_CAR e (car)) (EVAL_e SAFE_CAR DELAY_INT_23($zipped_eval_R)() (SAFE_CAR SAFE_CDR e,a))) ($eq(SAFE_CAR e (cdr)) (EVAL_e SAFE_CDR DELAY_INT_23($zipped_eval_R)() (SAFE_CAR SAFE_CDR e,a))) ($eq(SAFE_CAR e (cons)) (EVAL_e CONS DELAY_INT_23($zipped_eval_R)() (SAFE_CAR SAFE_CDR e,a) DELAY_INT_23($zipped_eval_R)() (SAFE_CAR SAFE_CDR SAFE_CDR e,a))) ((T)(EVAL_e DELAY_INT_23($zipped_eval_R)() (($zipped_assoc(SAFE_CAR e,a) EVAL_e SAFE_CDR e),a))) ) ) ($eq(SAFE_CAR SAFE_CAR e (lambda)) (DELAY_INT_26(EVAL_e_R)() DELAY_INT_23($zipped_eval_R)()( EVAL_e(EVAL_e(EVAL_e(EVAL_e(SAFE_CAR SAFE_CDR SAFE_CDR SAFE_CAR e)))), EVAL_e(APPEND DELAY_INT_13($pair_R)()(EVAL_e(EVAL_e(EVAL_e(SAFE_CAR SAFE_CDR SAFE_CAR e))) (DELAY_INT_19($zipped_evlis_R)()(EVAL_e(_e EVAL_e(SAFE_CDR e)), a)))a))) ) )

是不是似曾相識啊23333

典型的自解釋器實現。大家注意到這裡：

1）有很多SAFE_XXX之類的東西，將來會解釋。（C宏處理似乎難以實現短路condition，導致經常會對非法表達式進行求值，這種情況下使用naive的原語宏是會出事的-原地報錯／破壞括弧平衡-所以必須要很麻煩地一個一個實現為對於非法輸入仍能給出合法結果的宏）

2）很多EVAL_e。這是一個單位宏，單位宏和零宏在C宏展開中作用非常大，因為可以用它們微調宏的展開順序：

#define _CAT(x,y) x##y#define CAT(x,y) _CAT(x,y) //典型的連接//_e是一個單位宏，_n是一個零宏#define b() )x(_n(b()) //先展開_n再展開b，什麼都沒有了x_e(_n _n()(b())) // =>_n()x() => x()//先展開b再展開_n

因為CPP展開_e時對其括弧內字元串調用展開過程（所以單位宏可以用來增加一次展開掃描過程），這個時候b會被展開，但第一個_n後面沒有左括弧不會展開，所以會先展開中間的_n()，下一次掃描時才第一個_n和左括弧連起來被展開。

（是不是有些tricky？這是Lv0啦～等不及的可以自己看一下csp.h 2333如果能全部看懂幫我寫文章吧qwq）

3) DELAY_INT_xxx(xxx_R)()(...) 這個是著名的延遲展開技巧，DELAY_INT_xxx定義如下：

#define DELAY_REF(x) x _n()#define DELAY_REF_2(x) x _n()#define DELAY_INT_2(x) DELAY_REF(DELAY_REF_2)(x)#define DELAY_INT_3(x) DELAY_REF(DELAY_INT_2)(x)#define DELAY_INT_4(x) DELAY_REF(DELAY_INT_3)(x)#define DELAY_INT_5(x) DELAY_REF(DELAY_INT_4)(x)...

結合2）容易理解這樣 DELAY_INT_n(xxx_R)() 每次掃描n會減一，直到「露出」 xxx_R與後面的()結合，習慣上定義：

#define xxx_R() xxx

這樣xxx就被展開出來與參數列表結合，起到任意調節宏展開順序的作用。

此外這個還被用於宏的遞歸。由於藍色集合的限制，像這樣的宏是不能實現遞歸的：

#define I_want_recursion(x) do_it(x) I_want_recursion(x)I_want_recursion(x) //=>do_it(x) I_want_recursion(x)//CPP認為它屬於已經處理過的字元串於是就不會再展開了^_e(I_want_recursion(x))//=>do_it(x) I_want_recursion(x)//掃描多少遍都沒有用！

但是可以這樣：

#define I_want_recursion_R() I_want_recursion#define I_want_recursion(x) do_it(x) DELAY_REF(I_want_recursion_R)()(x)I_want_recursion(x) //=>do_it(x) I_want_recursion_R()(x)_e(I_want_recursion(x)) //=>do_it(x) do_it(x) I_want_recursion_R()(x)//因為這次I_want_recursion是由I_want_recursion_R()新造出來的token所以可以繼續展開下去

不過這樣需要在外面套足夠多的單位宏來進行足夠次數的掃描。。。CSP中有一部分使用零點構造技術更優雅地實現了遞歸，將來會寫的x

這次就先寫這些吧，下次寫解釋器A的列表操作實現和Currying？