S-Lisp與循環

什麼是圖靈完備？如何證明一種語言圖靈完備？反正像C/JS等語言能解決大多數問題的是完備的，而像SQL/正則表達式/XML等則不是。圖靈完備的標識是能自舉。我不是科班出生的，對這個術語只有一個模糊的印象。經常勸誡別人寫Java時用內置的JS引擎而不是XML理由為JS是圖靈完備的，而XML總會遇到難以解決的問題（任何系統複雜到一定程度都會內含一個複雜的BUG奇出的Lisp），經常只是在薅這個術語的羊毛而已，佔別人的名氣的便宜（彷彿自己就是潮流本身）。有一天，我在知乎上看到 @vczh 的回答（具體不再去翻了）「能寫出死循環的語言大概就圖靈完備了」（大致是這個意思），有點醍醐灌頂的意思。所以今天就談談S-Lisp的循環吧。

C系語言中有很多種循環，for語句、while語句還有遞歸，它們都有相互可替代的部分，創作S-Lisp我一直在思考最簡語法核心，似乎遞歸是最強大的，而其它循環並不能覆蓋它，而它可以模擬其它循環。話說別的語言循環語法這麼多，是因為語法複雜，都想找一種更簡單的書寫方法，而S-Lisp只有S表達式，翻過來翻過去都是這樣，似乎恰合python的「唯一」呢（當然我不喜歡縮進作為語義）。傳統的Lisp不說了，太多宏看不懂，S-Lisp裏只有函數。但遞歸會出現爆棧的情況。我曾嘗試在C#/C++實現S-Lisp時使用遞歸，可以避免副作用嘛，最後真實出現過爆棧，於是不得不轉為while語句（while其實是C系語言裏最純粹的循環）因此函數式語言裏又強調一個尾遞歸優化，比如clojure的recur（應該是這個。其實正因為看不懂，纔去創造自己的簡單語言S-Lisp...流淚...），尾遞歸也沒看懂，但現在有個方向，在宿主語言裏轉化成while語句就好，而轉化成while語句的，似乎就是隻在函數的最後一句調用自身那種。

前面提到的reduce就是一種循環，有限的循環，對列表的遍歷。想想當初學ruby，各種遍歷語法如何讓人頭痛...，語法說是簡化書寫，可是每一樣都得學都得記啊，並不是亂寫都能執行成功....只記一個卻不一定看得懂別人寫的....淚...。還有什麼生成序列...為什麼感覺並不是很實用....就像學一句」this is an apple.「一樣。那麼reduce用S-Lisp自身是如何定義的呢？

(let reduce { (let (xs run init) args reduce this) (if-run (exist? xs) { (let (x ...xs) xs) (let init (run init x)) (reduce xs run init) } {init} ) } )

如果看到readme和前一篇文章，不是很複雜。

將其轉化成宿主語言，應該如何表達呢？這裡用JS來簡單描述一下

var list=args.First();
args=args.Rest();
return ReduceFun.base_run(list,args);

},
ftype:function(){
return this.Function_type.user;
}
});

主要就是base_run部分。

C++稍複雜一點：

class ReduceFun: public LibFunction { private: static ReduceFun * _in_; public: static ReduceFun*instance(){ return _in_; } string toString(){ return "{(let (xs run init ) args reduce this ) (if-run (exist? xs ) {(let (x ...xs ) xs ) (let init (run init x ) ) (reduce xs run init ) } {init } ) }"; } Fun_Type ftype(){ return Function::fUser; }

protected:
Base * run(Node * args){

Node *list=static_cast<Node*>(args->First());
args=args->Rest();
Function *f=static_cast<Function*>(args->First());
args=args->Rest();
Base * init=args->First();
while(list!=NULL){
Base * x=list->First();
Node *nargs=new Node(init,new Node(x,NULL));
nargs->retain();
Base* n_init=f->exec(nargs);
nargs->release();
if(n_init!=NULL){
n_init->eval_release();
}
init=n_init;
list=list->Rest();
}
return init;

}
};
ReduceFun* ReduceFun::_in_=new ReduceFun();

因為在C++內部調用S-Lisp的函數，執行完為了清理作用域，會對返回值retain，所以在取得返回值後，要eval_release()，是將計數置0但不清除的方式。

reduce只是有限的循環，傳遞給reduce的Lambda執行了N次。reduce是從頭遍歷，直接收集則得到一個反轉的列表。但如果要用reduce-right呢？S-Lisp的遞歸好表達，但不是尾遞歸，似乎存在爆棧情況（個人對爆棧的內部原理無所知），如果要內部優化，可能仍然是reduce與reverse的組合。

`reverse的S-Lisp定義` (let reverse { (let (vs) args) (reduce vs { (let (init v) args) (extend v init) } [] ) } )

由reduce啟發，對非列表的，可能自增長的循環，應該怎麼做呢？lambda函數需要一個控制，返回true則繼續循環，false則停止循環並返回上一層。暫將定命名為loop

(let loop { (let (f init) args loop this) (let (will init) (f init)) (if-run will { (loop f init) } {init} ) } )

Lambda返回的必須是列表，第1個是是否繼續循環的Boolean類型，第2個作為下次循環的初始值，或終止循環的返回值。這是對reduce的簡單改造。loop默認會執行一次函數體

但實踐中，感覺操作有點複雜。

既然Lambda部分返回的是列表，何不直接將初始值作為列表呢？反正可以列表解構，很方便。於是改造一下：

(let loop { (let (f ...init) args loop this) (let (will ...init) (apply f init)) (if-run will { (apply loop (extend f init)) } {init} ) } )

apply函數，其實就是類似JS中的apply函數。

用宿主語言進行尾遞歸優化，以JS為例

function LoopFun(){} LoopFun.prototype=new Fun(); mb.Object.ember(LoopFun.prototype,{ toString:function(){ return "{(let (f ...init ) args loop this ) (let (will ...init ) (apply f init ) ) (if-run will {(apply loop (extend f init ) ) } {init } ) }"; }, exec:function(args){

var f=args.First();
args=args.Rest();
var will=true;
while(will){
args=f.exec(args);
will=args.First();
args=args.Rest();
}
return args;

},
ftype:function(){
return this.Function_type.user;
}
});

C++代碼也可以看一下

class LoopFun: public LibFunction { private: static LoopFun * _in_; public: static LoopFun*instance(){ return _in_; } string toString(){ return "{(let (f ...init ) args loop this ) (let (will ...init ) (apply f init ) ) (if-run will {(apply loop (extend f init ) ) } {init } ) }"; } Fun_Type ftype(){ return Function::fUser; }

protected:
Base * run(Node * args){

Function * f=static_cast<Function*>(args->First());
args=args->Rest();
if(args!=NULL){
args->retain();/*第一次作參數，需要retain*/
}
bool will=true;
while(will){
Node* o=static_cast<Node*>(f->exec(args));
if(args!=NULL){
args->release();/*每次當完參數，需要release*/
}
will=static_cast<Bool*>(o->First())->Value();
args=o->Rest();
if(args!=NULL){
args->retain();/*保持在o->release時不銷毀，同時作為下一次函數執行的參數也需要retain*/
}
o->release();
};
if(args!=NULL){
args->eval_release();
}
return args;

}
};
LoopFun* LoopFun::_in_=new LoopFun();

這樣一來，也解決了另外一個問題，比如想到列表中尋找，找到便中止循環，而不是reduce完全循環。

舉例

(let indexOf { (let (vs k is_eq) args) (loop { (let ((v ...vs)i) args) (if-run (is_eq v k) { (list false i ) } { (if-run (empty? vs) { (list false [] ) } { (list true vs (+ i 1) ) } ) } ) } vs 0 ) } )

最後一個函數，是判斷二者是否相等，因為不同的類型，有不同的判斷方式。（上述用C#的shell來測試的，C++自行研究吧）

注意它返回的是一個列表，準確來說應該取第一個，即應該是(first (loop .....))，不再貼代碼。

while語句本身是副作用（管它呢，是宿主語言的事，反正爆棧也是宿主語言的事）

反過來，reduce也可以用loop定義的。因此S-Lisp的循環大致分為三部分，尾遞歸，loop，reduce（其實仍然帶來很多個性化）

---附loop實現斐不拉契數列---

(let Fibonacci { (let (n) args) (if-run (< n 3) {1} { (first (loop { (let (r_n-2 r_n-1 i) args r_n (+ r_n-2 r_n-1) ) (if-run (= i n) { (list false r_n ) } { (list true r_n-1 r_n (+ i 1) ) } ) } 1 1 3 ) ) } ) } ) `測試` (apply log (loop { (let (i result) args) (if-run (< i 24) { (list true (+ i 1) (extend (Fibonacci i) result) ) } { (list false result ) } ) } 1 [] ) )