C宏元編程:編譯期LISP解釋器（二）列表操作

目錄?

（一）總體思路

?（二）列表操作

外部鏈接?

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

純粹用C宏寫的LISP解釋器！

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

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

CSP Wiki

這次要開始分析真正的Interpreter A原語啦！坐穩啦！

列表結構

開始分析LISP操作前我們先來看看CSP中列表的表示：

(a) //我是原子( (a) (b) (c) (d) ) //我是列表

為什麼要這樣呢，用下面這種方式不會更自然嗎：

a //我才是原子(a,b,c,d) //我才是列表

首先第一種方式括弧更多，更符合LISP書寫傳統（劃掉

最重要的是第一種方式在迭代列表和安全操作上有很多優點，例如迭代列表我們可以這樣實現：

#define sth(x) dosth(x) sth_y#define sth_y(x) dosth(x) sthsth(a)(b)(c)(d) // => dosth(a) sth_y(b)(c)(d) ... // => dosth(a) dosth(b) ... sth 或 sth_y （最後剩下一個沒展開完的）

最後剩下的那個「尾巴」可以用零點構造或者以下方式「吃掉」：

#define _sth(list) CAT(sth list,_end)#define sth_end#define sth_y_end_sth((a)(b)(c)(d)) // => CAT( dosth(a) ... sth,_end) => dosth(a) ... sth_end => dosth(a)

不過零點構造技術在柯里化的多元迭代函數上有更多優點，所以CSP中兩者皆有採用。

至於安全性，接下來會提到。

基本操作：CAR

CAR：取一個列表第一個元素的操作，LISP基本原語之一

以下是樸素的CAR實現：

#define CAR(x) (_CAR x ))#define _CAR(x) x _n(CAR ( (a) (b) (c) ) //=>(_CAR (a) (b) (c) )) //=> (a _n( (b) (c) )) => (a)

這裡讓CAR定義式中的_CAR展開出一個_n(（未匹配左括弧），和後面CAR中的未匹配右括弧配對，構成一個零宏，從而將第一個元素後的內容都吃掉。

看起來很好是嗎？不過實際上完全不能用。因為在CPP中，由於似乎無法實現短路的邏輯判斷，條件分支中所有的clause都會先求值再遴選，這樣這些clause大部分都會接受非法輸入。

那麼看看上面的CAR接受非法輸入會發生什麼：

CAR(a) //=>(_CAR a)) 破壞括弧平衡！CAR() //=>(_CAR )) 破壞括弧平衡！

會將整個展開過程破壞掉！所以我們需要在非法輸入下安全的CAR宏。

實現如下：

#define COND_EAT(x) COND_EATY#define COND_EATY(x) COND_EAT#define COND_EAT_FIRST(x) COND_EATY#define SAFE_CAR_N(x) (())_n#define SAFE_CAR_EAT_CAR )SAFE_CAR_N((#define COND_EATY_SCEND (a)#define COND_EAT_SCEND (a)#define SAFE_CAR(a) _E(_e _SAFE_CAR(a))#define _SAFE_CAR(a) _e(_n _n()(CAT(SAFE_CAR_EAT,_E(_e CAR(CAT(COND_EAT_FIRST a,_SCEND)))))(CAR(a)))// ^ 對於非法輸入展開失敗，輸出 (_CAR ... ))// ^ _E(_e ...) （兩個單位宏名，一對括弧）會吞掉參數的一對括弧. => _CAR )// ^ 連接成 SAFE_CAR_EAT_CAR =========// v 非法輸入導致最後那個CAR同樣展開失敗. |// => _e(_n _n() () SAFE_CAR_N(() (_CAR ... )) ) <==/// => _e( (()) )// => (()) //代入 SAFE_CAR 中=> _E(_e (()) )=>()輸出一個合法的空列表！

解釋一下。_SAFE_CAR 宏大體分為前面的判斷體_n _n()(CAT(SAFE_CAR_EAT,_E(_e CAR(CAT(COND_EAT_FIRST a,_SCEND))))) 和後面的主體(CAR(a))，以及最外面增加一次掃描次數的單位宏。判斷體應當在輸入非法時吃掉主體，而合法時自身輸出空。

首先看到 CAT(COND_EAT_FIRST a,_SCEND)，這個目的是把所有形如(b)((c)(d))...之類的合法a值約化為(a)以方便判斷體邏輯（否則可能會有很多嵌套列表，難以操作），而將不合法輸入約化為一個不含括弧的字元串。

此後交由CAR，對於不合法輸入會輸出形如(_CAR ...))，吞掉一對括弧後與SAFE_CAR_EAT連成SAFE_CAR_EAT_CAR，再展開成熟悉的)SAFE_CAR_N((這種未匹配括弧形式影響展開過程（多出一個左括弧是為了和後面CAR展開失敗輸出的多餘右括弧匹配）。而對於合法輸入，則直接被_n _n() (...) 吞掉。

SAFE_CDR採用類似思路實現。

好累啊就主要部分先寫這麼多吧，接下來稍微扯一下CSP解釋器A中怎麼處理多元函數的

CSP解釋器A中的柯里化

之前提過的兩個宏交替展開非常好，但似乎無法處理需要兩個參數的do_sth。

其實可以通過柯里化解決，不過這樣展開次數始終會缺一次所以還是得外置一組單位宏來延遲展開。

柯里化技巧的核心：ZIP宏

#define _be(y) y)#define ZIP(x) _n() (x,_be //This _n() delays the expansion of do_sth macro, after _be is expanded. otherwise it will an unmatched bracket error. do_sth ZIP(a)(b) =>do_sth _n()(a,_be(b)

如果外面再加一個單位宏強制增加一次掃描，就會變成：

do_sth (a,b)

這樣，一個簽名為do_sth(a,b)的二元宏，就可以通過ZIP封裝為do_sth ZIP，一個接受一元輸入，輸出一個一元宏的宏，從而能夠處理一個CSP列表的前兩項。

在CSP實現中，通常將參數放在待迭代列表前：

(arg)(a)(b)(c)....

do_sth實現為處理(arg,a)，並將arg放在處理結果之後，然後進行遞歸：

do_sth (arg)=> real_do_sth(arg,a) do_sth_y (arg) do_sth (arg)(a)(b)(c)=> real_do_sth(arg,a) do_sth_y (arg) (b)(c)

這樣就實現了帶參數的迭代列表操作。