极致之美——百行代码实现全新智能语言Lisp（7）

上面的那些放在文本区域里的代码并不是可以运行的，只是为了让大家看得清楚些

要试着体验LispScript的话，可以运行下面的代码：
<script>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);elsereturn arg;};__funList = new Array();//七个原始操作符 //开始我们先定义表达式.表达式或是一个原子[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]返回原子t如果x的值是一个原子或是空表,否则返回[]. 在Lisp中我们按惯例用原子t表示真, 而用空表表示假. //> [atom,[_,a]]//t//> [atom,[_,[a,b,c]]]//[]//> [atom,[_,[]]]//tatom = function(arg){var tmp = LispScript.Run(arg); //先对参数求值if(!(tmp instanceof Array) || tmp.length <= 0)return true;elsereturn [];};//既然有了一个自变量需要求值的操作符, 我们可以看一下quote的作用. 通过引用(quote)一个表,我们避免它被求值. 一个未被引用的表作为自变量传给象 atom这样的操作符将被视为代码: //> [atom,[atom,[_,a]]]//t//反之一个被引用的表仅被视为表, 在此例中就是有两个元素的表: //> [atom,[_,[atom,[_,a]]]]//[]//这与我们在英语中使用引号的方式一致. Cambridge(剑桥)是一个位于麻萨诸塞州有90000人口的城镇. 而"Cambridge"是一个由9个字母组成的单词. //引用看上去可能有点奇怪因为极少有其它语言有类似的概念. 它和Lisp最与众不同的特征紧密联系:代码和数据由相同的数据结构构成, 而我们用quote操作符来区分它们. //[eq,x,y]返回t如果x和y的值是同一个原子或都是空表, 否则返回[]. //> [eq,[_,a],[_,a]]//t//> [eq,[_,a],[_,b]]//[]//> [eq,[_,[]],[_,[]]]//tequal = 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;elsereturn [];};//[car,x]期望x的值是一个表并且返回x的第一个元素. //> [car,[_,[a b c]]]//acar = function(arg){var tmp = LispScript.Run(arg);  //先对参数求值if(tmp instanceof Array && tmp.length > 0)return tmp[0];elsereturn [];};//[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);elsereturn [];};//[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);}elsereturn [];};//[cond [...] ...[...]] 的求值规则如下. p表达式依次求值直到有一个返回t. 如果能找到这样的p表达式,相应的e表达式的值作为整个cond表达式的返回值. //> [cond,[[eq,[_,a],[_,b]],[_,first]],//      [,[atom,[_,a]], [_,second]]]//secondcond = 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',[_,[b]]]],[_,a]]//[a,b]//> [[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]//我们可以这样表示此函数 //[label,subst,[lambda,[x,y,z],//               [cond,[[atom,z],//                      [cond,[[eq,z,y],x],//                            [_,t],z]]],//                     [[_,t],[cons,[subst,x,y,[car,z]],//                               [subst,x,y,[cdr,z]]]]]]]label = function(funName, funDef){__funList.push(funName);return LispScript.Run(funDef);};//我们简记f=[label,f,[lambda,[...],e]]为 //[defun,f,[...],e] defun = function(funName, args, code){__funList.push(funName);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 [];};//于是 //[defun,subst,[x,y,z],//  [cond,[[atom,z],//         [cond,[[eq,z,y],x],//               [[_,t],z]]],//[[_,t],[cons,[subst,x,y,[car,z]],//                  [subst,x,y,[cdr,z]]]]]]//偶然地我们在这儿看到如何写cond表达式的缺省子句. 第一个元素是't的子句总是会成功的. 于是 //[cond,[x,y],[[_,true],z]]//等同于我们在某些语言中写的 //if x then y else z //现在我们可以直接用LispScript定义一些新函数了：//对于函数调用，具有如下结构：[FunName,[_,args]]//其中FunName是函数名称，[_,args]是指定参数引用列表args//注意[FunName,args]也是合法的，但是和[FunName,[_,args]]有所区别，对于前者，指令在被调用之前先计算args的值，把计算出的值作为参数列表代入函数计算（期望args计算结果为List），而后者的args参数列表在函数指令调用时才被计算//函数：[null,x]测试它的自变量是否是空表. LispScript.Run([defun,'isNull',['x'],[eq,'x',[_,NIL]]]);//> [null,[_,a]]//[]//> [null. [_,[]]]//t//函数:[and,x,y]返回t如果它的两个自变量都是t, 否则返回[]. LispScript.Run([defun,'and',['x','y'],[cond,['x',[cond,['y',true],[true,NIL]],[true,NIL]]]]);//> [and,[atom,[_,a]],[eq,[_,a],[_,a]]]//t//> [and,[atom,[_,a]],[eq,[_,a],[_,b]]]//[]//函数：[not,x]返回t如果它的自变量返回[],返回[]如果它的自变量返回t. LispScript.Run([defun,'not',['x'],[cond,['x',NIL],        [true,true]]]);//> [not,[eq,[_,a],[_,a]]]//[]//> [not,[eq,[_,a],[_,b]]]//t//函数：[append,x,y]取两个表并返回它们的连结. LispScript.Run([defun,'append',['x','y'],[cond,[[isNull,'x'],'y'], [true,[cons,[car,'x'],['append',[cdr,'x'],'y']]]]]);//> [append,[_,[a,b]],[_,[c,d]]]//[a,b,c,d]//> [append,[], [_,[c,d]]]//[c,d]//函数：[pair,x,y]取两个相同长度的表,返回一个由双元素表构成的表,双元素表是相应位置的x,y的元素对. LispScript.Run([defun,'pair',['x','y'],[cond,[[and,[isNull,'x'],[isNull,'y']],NIL],[[and,[not,[atom,'x']],[not,[atom,'y']]], [append,[[[car,'x'],[car,'y']]],['pair',[cdr,'x'],[cdr,'y']]]]]]);//> [pair,[_,[x,y,z]],[_,[a,b,c]]]//[[x,a],[y,b],[z,c]]//[assoc,x,y]取原子x和形如pair函数所返回的表y,返回y中第一个符合如下条件的表的第二个元素:它的第一个元素是x. LispScript.Run([defun,'assoc',['x','y'],[cond,[[eq,[car,[car,'y']],'x'],[car,[cdr,[car,'y']]]],[[isNull,'y'],NIL],[true,['assoc','x',[cdr,'y']]]]]);//> [assoc,[_,x],[_,[[x,a],[y,b]]]]//a//> [assoc,[_,x],[_,[[x,new],[x,a],[y,b]]]]//new//[ret,e]返回表达式计算结果LispScript.Run([defun,'ret',['e'],[car,['e']]]);//[str,e]返回表达式计算结果的引用LispScript.Run([defun,'str',['e'],[_,[_,'e']]]);//我们来看一下为什么要定义ret函数：//我想通过前面的解释和实际应用大家已经理解了引用(quote)的重要性，并且很容易证明：[[_,e]] = [e]//现在的问题是我们必须要定义一个引用的反函数f，令[f,[_,e]] = e//而显然地ret正是这样一个函数//[map,x,y]期望x是原子，y是一个表，如果[assoc,x,y]非空返回[assoc,x,y]的值否则返回xLispScript.Run([defun,'map',['x','y'],[cond,[[isNull,[assoc,'x','y']],'x'],[true,[assoc,'x','y']]]]);//[maplist,x,y]期望x和y都是表，返回由x中的每个元素t求[map,t,y]的结果构成的表LispScript.Run([defun,'maplist',['x','y'],[cond,[[atom,[_,'x']],[map,'x','y']],[true,[cons,['maplist',[car,[_,'x']],'y'],['maplist',[cdr,[_,'x']],'y']]]]]);//一个惊喜 //因此我们能够定义函数来连接表,替换表达式等等.也许算是一个优美的表示法, 那下一步呢? 现在惊喜来了. 我们可以写一个函数作为我们语言的解释器:此函数取任意Lisp表达式作自变量并返回它的值. 如下所示: LispScript.Run([defun,'_eval',['e','a'],[ret,[maplist,[_,'e'],'a']]]);//_eval.的简洁程度或许超出了我们原先的预想，于是这样我们获得了LispScrip实现的一个完整的自身的解析器！//让我们回过头考虑一下这意味着什么. 我们在这儿得到了一个非常优美的计算模型. 仅用quote,atom,eq,car,cdr,cons,和cond, 我们定义了函数_eval.,它事实上实现了我们的语言,用它可以定义和（或）动态生成任何我们想要的额外的函数和各种文法（这一点比较重要） //其他的扩展//下面我们定义变量的赋值操作[setq,paraName,paraValue]LispScript.Run([defun,'setq',['para','val'],[ret,[defun,'para',[],[_eval,'val']]]]);//增加逻辑操作符or，[or,x,y]返回t如果它的自变量有一个为t，否则返回[]LispScript.Run([defun,'or',['x','y'],[not,[and,[not,'x'],[not,'y']]]]);//增加循环控制foreach，[foreach,v,[list],[expr]]//foreach期望list是一个表，依次取表中的每一个原子作为expr的参数进行计算，返回计算结果的表LispScript.Run([defun,'foreach',['v','list','expr'],[cond,[[isNull,'list'],[]],[true,[cons,[_eval,[_,'expr'],[['v',[car,'list']]]],['foreach','v',[cdr,'list'],[_,'expr']]]]]]);//增加批量赋值操作let，[let,[[a1,v1],[a2,v2]...]]LispScript.Run([defun,'let',['paralist'],[foreach,"'v'",'paralist',[_,[setq,[car,"'v'"],[car,[cdr,"'v'"]]]]]]);//总结//现在该回过头来看看我们究竟做了什么，以及这么做有什么意义了。//首先我们用javascript实现了一个简单的向下递归的词法分析器，它能对嵌套数组的每个原子进行简单处理，加上几个辅助函数(toEvalString(),Assert(),Element()和一个存放函数名称的堆栈...简单来说我们仅用了数十行代码实现了一种全新的“函数式”语言??LispScript的完整内核。//接着我们定义了7种原始操作，它们分别是quote,atom,eq,car,cdr,cons和cond//然后（相对较复杂地），我们定义了三种用来描述和调用函数的标记，它们分别是lambda, label以及defun，于是我们成功地用另外不到百行代码实现了LispScript语言的核心环境。//接着（接下来的部分已经可以完全独立于javascript）我们用7种原始操作符和函数定义标记defun定义出一些新的函数，分别是：isNull,and,not,append,pair,assoc,ret和str//然后我们惊喜地发现，可以仅用一行LispScript指令定义出自身的“解析器”??_eval函数//最后我们在此基础上定义出一些略为复杂的函数，它们包括：or,setq,foreach和let，其中一些新函数带给我们的新语言定义变量和处理循环的能力，加上前面实现的一些函数，一个比较完善的基础环境就搭建成了。//写在最后：LispScript和Lisp//事实上我们依照[ref. Paul Graham.]的精彩描述用javascript实现了LispScript，毫无疑问，它是一种Lisp（或者Lisp风格的函数式语言），尽管功能上还十分简陋，但它确实是符合Lisp的基本思想和拥有Lisp的基本特性。由于javascript数组文法的特点，我用[]取代了[ref. Paul Graham]中的()，用逗号取代了空格作为分隔符。同[ref. Paul Graham]的文章以及目前一些标准（或者相对标准）的Lisp不同的是，我根据javascript灵活的特点有意弱化了LispScript的语法结构，这样使得LispScript更加灵活，也更加方便实现，然而代价是一小部分的可维护性和安全性。//最后，LispScript还有许多需要完善的内容，例如，最明显地是它基本上还不具有基本的数值运算能力（相对而言，符号操作能力已经比较完善），另外对原子操作参数合法性的检验、副作用, 连续执行 (它得和副作用在一起才有用), 动态可视域、复杂数据结构支持以及注释文法（这相当重要！）也都是它所欠缺的，不过这些功能“都可以令人惊讶地用极少的额外代码来补救”。//感谢约翰麦卡锡，这位天才早在数十年前就向我们展示了一种程序设计领域内至今无人能超越的“极致的美”，他于1960年发表了一篇非凡的论文,他在这篇论文中对编程的贡献有如欧几里德对几何的贡献.1 他向我们展示了,在只给定几个简单的操作符和一个表示函数的记号的基础上, 如何构造出一个完整的编程语言. 麦卡锡称这种语言为Lisp, 意为List Processing, 因为他的主要思想之一是用一种简单的数据结构表(list)来代表代码和数据. //感谢保罗格雷厄姆，他用浅显易懂的语言将Lisp的根源和实质展现在我们面前，令我们能够幸运地零距离体验Lisp的这种“超凡的美”//如果你理解了约翰麦卡锡的eval, 那你就不仅仅是理解了程序语言历史中的一个阶段. 这些思想至今仍是Lisp的语义核心. 所以从某种意义上, 学习约翰麦卡锡的原著向我们展示了Lisp究竟是什么. 与其说Lisp是麦卡锡的设计,不如说是他的发现. 它不是生来就是一门用于人工智能, 快速原型开发或同等层次任务的语言. 它是你试图公理化计算的结果(之一). //随着时间的推移, 中级语言, 即被中间层程序员使用的语言, 正一致地向Lisp靠近. 因此通过理解eval你正在明白将来的主流计算模式会是什么样.//References//The Roots of Lisp Paul Graham. Draft, January 18, 2002.//LISt Primer Colin Allen & Maneesh Dhagat.Tue Feb 6, 2001.(http://mypage.iu.edu/~colallen/lp/lp.html)</script>LispScript指令：（以分号分隔每条指令）<br><textarea cols="80" rows="20" id="code"></textarea><br>运行结果：<br><textarea cols="80" rows="5" readonly id="result"></textarea><br><input type="button" value="运行" onclick="RunCode()"><script>function RunCode(){var codes = code.value.split(';');result.value = "";for (var i = 0; i < codes.length; i++){try{var res = LispScript.Run(eval(codes[i]));}catch(e){result.value += "错误的LispScript语法!(" + e.message + ")";continue;}if(res instanceof Array)result.value += res.toEvalString() + "\n";else if(res instanceof Function)result.value += "Function " + res._funName + "\n";elseresult.value += res + "\n";}}</script>

你可以在这个简易的运行环境中输入LispScript的语句，多条语句请用分号分开

例如：你可以输入
[cons,1,[2,3]]
然后运行，结果是[1,2,3]

你可以输入
[setq,'x',1];
[setq,'y',[2,3]];
[cons,x,y]
然后运行，结果仍然是[1,2,3]

你可以输入
[defun,'mycons',['x','y'],[cons,'x','y']];
[mycons,1,[2,3]]
然后运行，结果也仍然是[1,2,3]