首先要解釋一下：
“極致之美”不是說月兒的這篇文章，因?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的簡(jiǎn)潔靈活和Lisp的優(yōu)美。
或許這里接觸Lisp的人不多，因此不少人一定會(huì)對(duì)以下的內(nèi)容或形式感到奇怪，如果你完全沒有接觸過它，不必過分驚訝，Lisp的確與以前你見過得所有編程語言不同，因?yàn)椋?，它是Lisp，獨(dú)一無二的Lisp，一段優(yōu)雅、簡(jiǎn)潔、完整、獨(dú)立的奇妙思想，也許你會(huì)覺得它很難懂，但是一旦你懂了，你會(huì)喜歡上它的。
好了，下面開始我們的LispScript之旅~
最近在網(wǎng)上偶然看到一篇文章，說javascript = C+Lisp，于是思考這樣的問題，既然javascript包含著部分Lisp的血統(tǒng)，那么用javascript來實(shí)現(xiàn)一個(gè)類似于Lisp的人工智能腳本又會(huì)是什么樣子？
LISt Processing語系作為一種“函數(shù)式”語系，自從誕生之日起便以其簡(jiǎn)單優(yōu)美的風(fēng)格和簡(jiǎn)潔高效的結(jié)構(gòu)征服了許許多多的研究者和愛好者。
目前這種古老的語言和文法仍然被許許多多的人使用著并熱愛著，而且在人工智能等領(lǐng)域發(fā)揮著非常巨大的作用。
我認(rèn)為，javascript的靈活加上Lisp的簡(jiǎn)潔，應(yīng)該能夠創(chuàng)造出一種非常優(yōu)美的語言，不過這種語言是什么樣子的呢？相信大家也很想知道，那么下面我們一起來研究一下這個(gè)非常吸引人的問題。
（在仔細(xì)閱讀下面的內(nèi)容之前，建議大家先倒杯熱茶，坐下來平靜一下自己的心情，深呼吸一下，集中起精神來，因?yàn)橄旅娴倪^程將是有趣而又頗耗腦細(xì)胞的...^^）
在進(jìn)入Lisp王國(guó)之前，讓我們先來做一些javascrip的準(zhǔn)備工作...請(qǐng)仔細(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();

以上這段簡(jiǎn)簡(jiǎn)單單不過數(shù)十行的javascript代碼由三個(gè)輔助函數(shù)、一個(gè)主體對(duì)象、一個(gè)常量NIL（后面我們會(huì)知道它表示一個(gè)空表或者邏輯false），以及一個(gè)存放函數(shù)名稱的堆棧組成。
LispScript靜態(tài)對(duì)象構(gòu)成了LispScript解析器的主體，它只有一個(gè)Run方法，該方法用向下遞歸的方式解析傳遞進(jìn)來的LispScript代碼，代碼的類型——相信細(xì)心的讀者已經(jīng)發(fā)現(xiàn)了——直接用的是javascript的數(shù)組，也就是一系列“[”、“]”和分隔符“,”構(gòu)成的序列。
用javascript天然的數(shù)組特性，使得我們的解析器可以設(shè)計(jì)得十分簡(jiǎn)潔——不用去拆分和解析每一個(gè)token，于是一段簡(jiǎn)短到不到50行的代碼驚人地實(shí)現(xiàn)了整個(gè)LispScript解析器的核心！
三個(gè)輔助函數(shù)的作用分別是為函數(shù)迭代提供解析（toEvalString），檢測(cè)序列異常（Assert，后面的具體實(shí)現(xiàn)中其實(shí)并沒有用到），以及解析指令單詞（Element）
接下來我們先定義表達(dá)式.表達(dá)式或是一個(gè)原子[atom],它是一個(gè)字母序列(如 foo),或是一個(gè)由零個(gè)或多個(gè)表達(dá)式組成的表(list), 表達(dá)式之間用逗號(hào)分開, 放入一對(duì)中括號(hào)中. 以下是一些表達(dá)式: 
（注：原Lisp語法的表達(dá)式用空格隔開，放入一對(duì)括號(hào)中。因是javascript的實(shí)現(xiàn)，所以用中括號(hào)和逗號(hào)較為簡(jiǎn)潔）
foo
[]
[foo]
[foo,bar]
[a,b,[c],d]
最后一個(gè)表達(dá)式是由四個(gè)元素組成的表, 第三個(gè)元素本身是由一個(gè)元素組成的表. 
在算術(shù)中表達(dá)式 1 + 1 得出值2. 正確的Lisp表達(dá)式也有值. 如果表達(dá)式e得出值v,我們說e返回v. 下一步我們將定義幾種表達(dá)式以及它們的返回值. 
如果一個(gè)表達(dá)式是表,我們稱第一個(gè)元素為操作符,其余的元素為自變量.我們將定義七個(gè)原始(從公理的意義上說)操作符: quote,atom,eq,car,cdr,cons,和 cond. 
[quote,x] 返回x. 我們把[quote,x]簡(jiǎn)記為[_,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的值是一個(gè)原子或是空表,否則返回[]. 在Lisp中我們按慣例用原子true表示真, 而用空表表示假. 
> [atom,[_,a]]
true
> [atom,[_,[a,b,c]]]
[]
> [atom,[_,[]]]
true
atom = function(arg)
{
 var tmp = LispScript.Run(arg); //先對(duì)參數(shù)求值
 if(!(tmp instanceof Array) || tmp.length <= 0)
  return true;
 else
  return [];
};

既然有了一個(gè)自變量需要求值的操作符, 我們可以看一下quote的作用. 通過引用(quote)一個(gè)表,我們避免它被求值. 一個(gè)未被引用的表作為自變量傳給象 atom這樣的操作符將被視為代碼: 
> [atom,[atom,[_,a]]]
true
反之一個(gè)被引用的表僅被視為表, 在此例中就是有兩個(gè)元素的表: 
> [atom,[_,[atom,[_,a]]]]
[]
這與我們?cè)谟⒄Z中使用引號(hào)的方式一致. Cambridge(劍橋)是一個(gè)位于麻薩諸塞州有90000人口的城鎮(zhèn). 而"Cambridge"是一個(gè)由9個(gè)字母組成的單詞. 
引用看上去可能有點(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的值是同一個(gè)原子或都是空表, 否則返回[]. 
> [eq,[_,a],[_,a]]
true
> [eq,[_,a],[_,b]]
[]
> [eq,[_,[]],[_,[]]]
true
equal = eq = function(arg1, arg2)
{
 var tmp1 = LispScript.Run(arg1);
 var tmp2 = LispScript.Run(arg2);   //先對(duì)參數(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的值是一個(gè)表并且返回x的第一個(gè)元素. 
> [car,[_,[a b c]]]
a
car = function(arg)
{
 var tmp = LispScript.Run(arg);  //先對(duì)參數(shù)求值
 if(tmp instanceof Array && tmp.length > 0)
  return tmp[0];
 else
  return [];
};

[cdr,x]期望x的值是一個(gè)表并且返回x的第一個(gè)元素之后的所有元素. 
> [cdr,[_,[a b c]]]
[b,c]
cdr = function(arg)
{
 var tmp = LispScript.Run(arg);  //先對(duì)參數(shù)求值
 if(tmp instanceof Array && tmp.length > 0)
  return tmp.slice(1);
 else
  return []; 
};

[cons,x,y]期望y的值是一個(gè)表并且返回一個(gè)新表,它的第一個(gè)元素是x的值, 后面跟著y的值的各個(gè)元素. 
> [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);   //先對(duì)參數(shù)求值
 if(tmp2 instanceof Array)
 {
  var list = new Array();
  list.push(tmp1);
  return list.concat(tmp2);
 }
 else
  return [];
};

[cond [...] ...[...]] 的求值規(guī)則如下. p表達(dá)式依次求值直到有一個(gè)返回t. 如果能找到這樣的p表達(dá)式,相應(yīng)的e表達(dá)式的值作為整個(gè)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]);  //先對(duì)參數(shù)求值
   //alert(cond);
   if(cond == true && arguments[i][1] != null)
    return LispScript.Run(arguments[i][1]);
  }
 }
 return [];
};

當(dāng)表達(dá)式以七個(gè)原始操作符中的五個(gè)開頭時(shí),它的自變量總是要求值的.2 我們稱這樣 的操作符為函數(shù). 
接著我們定義一個(gè)記號(hào)來描述函數(shù).函數(shù)表示為[lambda, [...], e],其中 ...是原子(叫做參數(shù)),e是表達(dá)式. 如果表達(dá)式的第一個(gè)元素形式如上 
[[lambda,[...],e],...]
則稱為函數(shù)調(diào)用.它的值計(jì)算如下.每一個(gè)表達(dá)式先求值,然后e再求值.在e的求值過程中,每個(gè)出現(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 [];
};

如果一個(gè)表達(dá)式的第一個(gè)元素f是原子且f不是原始操作符 
[f ...] 
并且f的值是一個(gè)函數(shù)[lambda,[...]],則以上表達(dá)式的值就是 
[[lambda,[...],e],...]
的值. 換句話說,參數(shù)在表達(dá)式中不但可以作為自變量也可以作為操作符使用: 
> [[lambda,[f],[f,[_,[b,c]]],[_,[lambda,[x],[cons,[_,a],x]]]
[a,b,c]
有另外一個(gè)函數(shù)記號(hào)使得函數(shù)能提及它本身,這樣我們就能方便地定義遞歸函數(shù).記號(hào) 
[label,f,[lambda,[...],e]] 
表示一個(gè)象[lambda,[...],e]那樣的函數(shù),加上這樣的特性: 任何出現(xiàn)在e中的f將求值為此label表達(dá)式, 就好象f是此函數(shù)的參數(shù). 
假設(shè)我們要定義函數(shù)[subst,x,y,z], 它取表達(dá)式x,原子y和表z做參數(shù),返回一個(gè)象z那樣的表, 不過z中出現(xiàn)的y(在任何嵌套層次上)被x代替. 
> [subst,[_,m],[_,b],[_,[a,b,[a,b,c],d]]]
[a,m,[a,m,c],d]

最新評(píng)論