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