极致之美——百行代码实现全新智能语言
首先要解释一下：
“极致之美”不是说月儿的这篇文章，因为本人还没有自大到这种程度: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]
«
»