|
|
“極致之美”不是說月兒的這篇文章，因為本人還沒有自大到這種程度:P，它形容的是Lisp和Javascript結合的優美形態。
本來以下內容是要在無優首發的，但是不巧完成文章的當天忽然發現無優“彈”了，直到上周末才恢復=.=，由于不能等那么久，所以就先放到月兒在CSDN上的博客里去了。
正如標題所描述的，下文是關于用Javascript實現類Lisp語言的技巧，然而重點不在于如何實現一門編程語言，而是在于通過思考和實現過程展示Javascript的簡潔靈活和Lisp的優美。
或許這里接觸Lisp的人不多，因此不少人一定會對以下的內容或形式感到奇怪，如果你完全沒有接觸過它，不必過分驚訝，Lisp的確與以前你見過得所有編程語言不同，因為，呃，它是Lisp，獨一無二的Lisp，一段優雅、簡潔、完整、獨立的奇妙思想，也許你會覺得它很難懂，但是一旦你懂了，你會喜歡上它的。
好了，下面開始我們的LispScript之旅~
最近在網上偶然看到一篇文章，說Javascript = C+Lisp，于是思考這樣的問題，既然Javascript包含著部分Lisp的血統，那么用Javascript來實現一個類似于Lisp的人工智能腳本又會是什么樣子？
LISt Processing語系作為一種“函數式”語系，自從誕生之日起便以其簡單優美的風格和簡潔高效的結構征服了許許多多的研究者和愛好者。
目前這種古老的語言和文法仍然被許許多多的人使用著并熱愛著，而且在人工智能等領域發揮著非常巨大的作用。
我認為，Javascript的靈活加上Lisp的簡潔，應該能夠創造出一種非常優美的語言，不過這種語言是什么樣子的呢？相信大家也很想知道，那么下面我們一起來研究一下這個非常吸引人的問題。
（在仔細閱讀下面的內容之前，建議大家先倒杯熱茶，坐下來平靜一下自己的心情，深呼吸一下，集中起精神來，因為下面的過程將是有趣而又頗耗腦細胞的...^^）
在進入Lisp王國之前，讓我們先來做一些Javascrip的準備工作...請仔細閱讀下面的代碼
NIL = [];
Array.prototype.toEvalString = function()
{
if(this.length <= 0) return "NIL";
var str = "";
for (var i = 0; i < this.length; i++)
{
if(this[i] instanceof Array)
str += "," + this[i].toEvalString();
else str += "," + this[i];
}
return "[" + str.slice(1) + "]";
};
(function(){
LispScript = {
Run : run
};
function run(code)
{
if(code instanceof Array)
{
var elements = new Array();
for (var i = 0; i < code.length; i++)
{
code[i] = run(code[i]); //遞歸向下讀取
if(code[i] instanceof Function) //解析表達式
{
if(code[i].length <= 0) //無參函數可省略[]直接以函數名稱調用
{
code[i] = code[i].call(null);
}
else if(i == 0) //調用帶參數的函數[funcall,args...]
{
return code[i].apply(null, code.slice(1));
}
}
}
return code;
}
return Element(code);
};
})();
function Assert(msg, cond)
{
if(cond)
return true;
else
{
alert(msg);
throw new Error(msg);
}
};
function Element(arg)
{
if(arg == null)
return [];
else if(arg instanceof Function && arg.length <= 0)
return arg.call(null);
else
return arg;
};
__funList = new Array();
以上這段簡簡單單不過數十行的Javascript代碼由三個輔助函數、一個主體對象、一個常量NIL（后面我們會知道它表示一個空表或者邏輯false），以及一個存放函數名稱的堆棧組成。
LispScript靜態對象構成了LispScript解析器的主體，它只有一個Run方法，該方法用向下遞歸的方式解析傳遞進來的LispScript代碼，代碼的類型――相信細心的讀者已經發現了――直接用的是Javascript的數組，也就是一系列“[”、“]”和分隔符“,”構成的序列。
用Javascript天然的數組特性，使得我們的解析器可以設計得十分簡潔――不用去拆分和解析每一個token，于是一段簡短到不到50行的代碼驚人地實現了整個LispScript解析器的核心！
三個輔助函數的作用分別是為函數迭代提供解析（toEvalString），檢測序列異常（Assert，后面的具體實現中其實并沒有用到），以及解析指令單詞（Element）
接下來我們先定義表達式.表達式或是一個原子[atom],它是一個字母序列(如 foo),或是一個由零個或多個表達式組成的表(list), 表達式之間用逗號分開, 放入一對中括號中. 以下是一些表達式:
（注：原Lisp語法的表達式用空格隔開，放入一對括號中。因是Javascript的實現，所以用中括號和逗號較為簡潔）
foo
[]
[foo]
[foo,bar]
[a,b,[c],d]
最后一個表達式是由四個元素組成的表, 第三個元素本身是由一個元素組成的表.
在算術中表達式 1 + 1 得出值2. 正確的Lisp表達式也有值. 如果表達式e得出值v,我們說e返回v. 下一步我們將定義幾種表達式以及它們的返回值.
如果一個表達式是表,我們稱第一個元素為操作符,其余的元素為自變量.我們將定義七個原始(從公理的意義上說)操作符: quote,atom,eq,car,cdr,cons,和 cond.
[quote,x] 返回x. 我們把[quote,x]簡記為[_,x].
> [quote,a]
a
> [_,a]
a
> [quote,[a b c]]
[a,b,c]
quote = _ = function(args)
{
if(arguments.length < 1)
return [];
else if(arguments.length >= 1)
{
return arguments[0];
}
};
[atom,x]返回原子true如果x的值是一個原子或是空表,否則返回[]. 在Lisp中我們按慣例用原子true表示真, 而用空表表示假.
> [atom,[_,a]]
true
> [atom,[_,[a,b,c]]]
[]
> [atom,[_,[]]]
true
atom = function(arg)
{
var tmp = LispScript.Run(arg); //先對參數求值
if(!(tmp instanceof Array) || tmp.length <= 0)
return true;
else
return [];
};
既然有了一個自變量需要求值的操作符, 我們可以看一下quote的作用. 通過引用(quote)一個表,我們避免它被求值. 一個未被引用的表作為自變量傳給象 atom這樣的操作符將被視為代碼:
> [atom,[atom,[_,a]]]
true
反之一個被引用的表僅被視為表, 在此例中就是有兩個元素的表:
> [atom,[_,[atom,[_,a]]]]
[]
這與我們在英語中使用引號的方式一致. Cambridge(劍橋)是一個位于麻薩諸塞州有90000人口的城鎮. 而"Cambridge"是一個由9個字母組成的單詞.
引用看上去可能有點奇怪因為極少有其它語言有類似的概念. 它和Lisp最與眾不同的特征緊密聯系:代碼和數據由相同的數據結構構成, 而我們用quote操作符來區分它們.
[eq,x,y]返回t如果x和y的值是同一個原子或都是空表, 否則返回[].
> [eq,[_,a],[_,a]]
true
> [eq,[_,a],[_,b]]
[]
> [eq,[_,[]],[_,[]]]
true
equal = eq = function(arg1, arg2)
{
var tmp1 = LispScript.Run(arg1);
var tmp2 = LispScript.Run(arg2); //先對參數求值
if(!(tmp1 instanceof Array) && !(tmp2 instanceof Array) &&
tmp1.toString() == tmp2.toString() ||
(tmp1 instanceof Function) && (tmp2 instanceof Function) && tmp1.toString() == tmp2.toString() ||
(tmp1 instanceof Array) && (tmp2 instanceof Array) && (tmp1.length == 0) && (tmp2.length == 0))
return true;
else
return [];
};
[car,x]期望x的值是一個表并且返回x的第一個元素.
> [car,[_,[a b c]]]
a
car = function(arg)
{
var tmp = LispScript.Run(arg); //先對參數求值
if(tmp instanceof Array && tmp.length > 0)
return tmp[0];
else
return [];
};
[cdr,x]期望x的值是一個表并且返回x的第一個元素之后的所有元素.
> [cdr,[_,[a b c]]]
[b,c]
cdr = function(arg)
{
var tmp = LispScript.Run(arg); //先對參數求值
if(tmp instanceof Array && tmp.length > 0)
return tmp.slice(1);
else
return [];
};
[cons,x,y]期望y的值是一個表并且返回一個新表,它的第一個元素是x的值, 后面跟著y的值的各個元素.
> [cons,[_,a],[_,[b,c]]]
[a,b,c]
> [cons,[_,a],[cons,[_,b],[cons,[_,c],[_,[]]]]]
[a,b,c]
> [car,[cons,[_,a],[_,[b c]]]]
a
> [cdr,[cons,[_,a],[_,[b,c]]]]
[b,c]
cons = function(arg1, arg2)
{
var tmp1 = LispScript.Run(arg1);
var tmp2 = LispScript.Run(arg2); //先對參數求值
if(tmp2 instanceof Array)
{
var list = new Array();
list.push(tmp1);
return list.concat(tmp2);
}
else
return [];
};
[cond [...] ...[...]] 的求值規則如下. p表達式依次求值直到有一個返回t. 如果能找到這樣的p表達式,相應的e表達式的值作為整個cond表達式的返回值.
> [cond,[[eq,[_,a],[_,b]],[_,first]],
[,[atom,[_,a]], [_,second]]]
second
cond = function(args)
{
for (var i = 0; i < arguments.length; i++)
{
if(arguments[i] instanceof Array)
{
var cond = LispScript.Run(arguments[i][0]); //先對參數求值
//alert(cond);
if(cond == true && arguments[i][1] != null)
return LispScript.Run(arguments[i][1]);
}
}
return [];
};
當表達式以七個原始操作符中的五個開頭時,它的自變量總是要求值的.2 我們稱這樣 的操作符為函數.
接著我們定義一個記號來描述函數.函數表示為[lambda, [...], e],其中 ...是原子(叫做參數),e是表達式. 如果表達式的第一個元素形式如上
[[lambda,[...],e],...]
則稱為函數調用.它的值計算如下.每一個表達式先求值,然后e再求值.在e的求值過程中,每個出現在e中的的值是相應的在最近一次的函數調用中的值.
> [[lambda,['x'],[cons,'x',[_,[c]]]],[_,a]]
[a,c]
> [[lambda,['x','y'],[cons,'x',[cdr,'y']]],[_,z],[_,[a,b,c]]]
[z,b,c]
lambda = function(args, code)
{
if(code instanceof Array)
{
var fun = new Function(args,
"for(var i = 0; i < arguments.length; i++) arguments[i] = LispScript.Run(arguments[i]);return LispScript.Run("+code.toEvalString()+");");
var globalFuncName = __funList.pop();
fun._funName = globalFuncName;
if(globalFuncName != null)
self[globalFuncName] = fun;
return fun;
}
return [];
};
如果一個表達式的第一個元素f是原子且f不是原始操作符
[f ...]
并且f的值是一個函數[lambda,[...]],則以上表達式的值就是
[[lambda,[...],e],...]
的值. 換句話說,參數在表達式中不但可以作為自變量也可以作為操作符使用:
> [[lambda,[f],[f,[_,[b,c]]],[_,[lambda,[x],[cons,[_,a],x]]]
[a,b,c]
有另外一個函數記號使得函數能提及它本身,這樣我們就能方便地定義遞歸函數.記號
[label,f,[lambda,[...],e]]
表示一個象[lambda,[...],e]那樣的函數,加上這樣的特性: 任何出現在e中的f將求值為此label表達式, 就好象f是此函數的參數.
假設我們要定義函數[subst,x,y,z], 它取表達式x,原子y和表z做參數,返回一個象z那樣的表, 不過z中出現的y(在任何嵌套層次上)被x代替.
> [subst,[_,m],[_,b],[_,[a,b,[a,b,c],d]]]
[a,m,[a,m,c],d]
JavaScript技術：極致之美――百行代碼實現全新智能語言第1/6頁，轉載需保留來源！
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。
