let focus = 'computing' in here

本博客再度关闭

2008-01-01T16:50:00.001+08:00

最近一直不很顺。先是 SAT 考了个 1570，几乎无效的分数，对于需要 SAT 成绩的学校而言；然后最重要的 TOEFL 考了个 63，折合老托福 500 分，几乎无效的分数。看来今年国是出不成了，现在只能寄希望于高考考上个能叫做学校的东西，然后设法大一就以访问学者的身份出国。
给东大的申请当然是告吹了。想写的程序一直没写，打不起精神；ML 的书也没有接着看下去。下围棋被一同学的父亲（一个高个儿老头）击败。Windows XP 中了个特傻的病毒，但删它时误删了盗版 Win 用的 OEM 信息，一怒之下装回自己的 OEM 的 Home 版。MBR 被重写，重装 FreeBSD 内核，误选了 Toggle NewFs 选项，Slices 被清空，丢失 400M 书和 500M 歌，所幸我的 Greation 已备份，否则就是倾家荡产。
我现在需要安静，虽然还有很多计算机方面的文章想写。于是我轻轻地走了，正如我轻轻地来~`此番闭博，不知何时再见。
留下未完成的个人主页一个：Yue Time
doubanclaimaeeca142b1906978

致东大·个人陈述

2007-12-12T00:44:00.000+08:00

To 贵校教授：
我是南京人，来自南京市第三十四中学，计划申请贵校的计算机科学方向本科（计算机科学与工程学院或数学系）。以下是我的个人陈述。

学术部分：
我首次接触电脑是在2000年。那时我去参加一个奥数班，班上教授一种叫“CL”的编程语言。很多年之后，我才知道那是 Common Lisp 的简称。细数起来，也许是从那时起，我就和函数式编程结下了不解之缘。
2003年，我拥有了自己的第一台电脑。下旬，开始学习编程。从那时起，我每天保证看1个小时电脑书，掌握了 Java 和 C 编程语言。直到现在我仍在坚持看书。
2004年，我开始学习算法和数据结构。掌握了不少使用 Java 语言描述数据结构的知识，小到链表大到红黑树都有能力构造；之后在算法方面小有长进，掌握了基本的算法设计思想。
2005年，我开始写博客，并尝试着使用新学习的 Python 语言解决《程序员》杂志上的算法题。产生了未来做一名计算机科学家的梦想，但不得要领，只是在学习离散数学和图论初步。这时，我听说了一种叫 Scheme 的编程语言。
Scheme 语言本身并不是特别强大，用它开发软件也并非首选，但是，它背后的那本书却是计算机科学的入门宝典——《计算机程序的构造和解释》(SICP)，包容了几十年来计算机科学界研究成果的思想，众多80后计算机科学家的启蒙书，MIT 6.001课程教材；但也是 Scheme 入门书籍中最难的一本，吓退了无数感到“智商受到了挑战”的读者。但是我要攻克它。
2006年我学习 SICP。书难，题目更难。每天晚自习，我1个小时写作业，2个小时做 SICP 上的题目，而且是几乎题题都做，硬是凭着从前的基础，坚持做完大半本书，书上满是我做的笔记和写出的解答。
有人这样评价 Scheme：Scheme 本身不是具体的技术，但学了它，就能十步杀一人，千里不留行。功夫不负有心人，之后我就开始在计算机科学各方面大口吞噬知识，因为我了解了计算的本质，头脑可以迅速理解、重组新知识；使用函数式编程思想写程序思路异常清晰，似乎能看见数据在函数间流动。此前我学过编译原理，但唯一一次和同学合写一个新语言 S-dict 的语法分析器却项目失控了；但2007年初，我设计了编程语言 Mazy，写出它到 JavaScript 的上千行的核心翻译器只用了4个晚上。中旬，我写 S-dict 第二版的递归下降语法分析器只用了6个小时。我还学习 SICP 背后的论文，自己设计并实现了基于智能对象的面向对象系统。我顺便拾起了博客，在国内最具实力的技术网站 JavaEye 上发了几篇用以教学的文章，很快在窜上搜索引擎首页，博客日浏览量超过500。
在选择自己计算机科学的发展方向时，我对编程语言本身的原理显示出极大的兴趣（事实上，我2006年后学了近30种编程语言）。我在编译原理方面的功底和英语水平使我在翻译以佶屈聱牙著称的 ECMA-262 语言规范时十分轻松，研习各个语言的标准定义也不甚困难。我没有满足于此，转而学习元语言抽象和形式语义，在数理逻辑和 Lambda 演算方面略有小成，并设计了更优秀的纯函数式语言，目前正在学习指称语义的相关证明。
当然，只发展单一方向是不够的。最近一个很偶然的机会使我开始了人工智能方面的探索。一个留学美国的中国网友请我帮他完成一个使用贝叶斯算法过滤垃圾邮件的作业。我出色地完成了工作之后也对 AI 产生了一定兴趣。尽管 AI 的基础部分很枯燥，但我还是会学下去。
也许你会问我为什么没有取得过计算机方面的任何奖项。关于参赛，我当然也想过。但比赛教科书上用 Pascal 语言写成的冗长的代码我吃惊非小：这些代码都只是在很低的抽象层次上工作。信息学竞赛只是因为能提供报送资格而被人关注的，我很怀疑参赛者的计算机科学素养。4个小时做4道题是不可能让你临场设计算法的，对应的题型必须做熟了才能胜出。但这不是在学习科学。我认为仅仅为了熟练而花时间并不值得，我有设计算法的能力并能对它进行足够的优化，这就够了。

个人部分：
我的学习史几乎可以归结为失败史。我是小学时的前三名，但初中还是没有读到最好的学校；在初中是前十名，但中考再流落到三流高中；在高中只当了半年第一名，排名就不断下滑。高考复习开始时，我请了三个月假去准备申请国外大学的考试，回来后发现在班上成绩垫底。
语文应该是我的强项，每个我遇到的语文老师都看好我，初中作文写得就不错，高中参加作文竞赛还获过几次奖但偏偏中考作文走题。数学曾经是我的最爱，初中还获过市级的奖项但高中之后就渐渐松懈了（但却自学了计算机要用到理论数学）；物理也是如此。也许我唯一高歌猛进的一“门”就是计算机了可高考里没有这一项。现在想来，如果我未来不能计算机科学方面有所成就，那我就真成了一个笑话。
体育我一直不很擅长，唯独长跑倒是不错。乒乓球羽毛球都会一点。剩下的就只有围棋了，尽管那可能算不上“体”育。我的围棋接近业余初段水平，此外就没什么爱好了。
由于从小受到中国古代士子阶层思想的影响，我在人际关系方面一直不很擅长。但也居然有了几个可以推心置腹的朋友，这样我就很满足了。

未来规划：
如果我如愿进入贵校计算机科学方向的专业，我计划补全高等数学及计算方法方面的基础知识，主攻编译原理的高级优化技术，研究人工智能的机器学习方面的内容，可能学习操作系统理论或者计算机图形学。一年之内设计并实现远比 Ruby 先进的编程语言，帮助贵校开展与国外大学编程语言原理方面的交流与合作。四年内对自己的最低要求是拥有在数理逻辑方面的研究成果。期间也可以适当地参加比赛，这可能是贵校对自主招生学生最现实的要求吧？

此致

袁秩昊
二零零七年十二月

Re(8):无题

2007-12-04T00:02:00.000+08:00

apple说:
　| 哦，原来你也是用windows的，那你学的那些语言都用在什么地方？我总觉得学一个东西总要是用出来的吧，如：某个程序、某个网站、某个系统？不可能总停留在某一个函数和算法的研究上啊？
　| 而要发布或部署一个系统，又要用到windows平台，那你写代码总要ide帮助才行啊，如果用记事本写程序的话，完成一个系统那得花多长时间啊？所以好的ide帮助你处理了那些和部署相关的啰嗦的东西，然后你才能安心的处理程序逻辑~
　| 而且你的动态语言，我真的不理解，现在流行的python，及perl，这些语言自身是不可存在的吧，他们需要借助某种环境，如必须放在网页中，perl 好像还需在*nix下吧。so，我在windows下就很迷惑，我想写段python或perl代码，却找不到该在哪写？然后就算写好了，确不知道该如何运行~
　| 而在大学时也曾想转到nix下，装了freebsd，然后却发现用的很不适应，它里面的编写程序的环境也不是很友好，对着黑黑的窗口和界面普通的kde，感觉无所适从，觉得他不像传说中的那样充满吸引力~
　| 于是，在周围同学的CS枪声中我又装回了windows。
　| 现在，偶然，碰到你，我又对nix找回写兴趣，我觉得我骨子里还是希望能对nix有比较深入的了解的~
　
　我其实不算是用win的，因为很早开始我就在用*nix的方式工作。这个星期装上了freebsd，甚爽，发现以前学的知识都有了充分的发挥，bash/term好用的不行，再也不用忍受连行编辑都不支持的cmd.exe了。
　所谓“学东西拿出来用”，我是这样理解的：写程序，做网站，核心的部分、难的部分不超过20%（除非你写的就是算法库）；但这部分却要花去你 80%的时间。剩下来那80%的代码呢？普通的逻辑和简单的调用而已。就知识而言，前者是活的，后者是死的。所以我懒得去搞应用，因为我知道，凭我的能力，到时候对照着文档写都来得及。平时重在练“内功”，以期用兵一时啊。
　关于ide，这样跟你说吧。我肯定不会去用ide，但也不可能去用notepad。我们prefer高级编辑器。只要你不用java、c+ +、.net这些特别费话的语言，没怎么配置过的vim，emacs这些东西绝对比ide高效（当然，也可以把emacs弄得比eclipse还拉风，但我不用，就没兴趣了）。它们的指导思想是：让你在写程序的时候用100%的精力思考程序逻辑，用0%的时间输入代码。所以，1. 不帮助你思考。需要有程序帮你思考的语言就不是好语言；2. 不阻碍你思考。敢和人类作对的程序应该去死；3. 使你更快地输入代码。这是高级编辑器提供效率的关键，也是不阻碍你思考的一部分。你觉得ide的代码完成高效吗？vim也有，但不会没事干地帮你匹配文件里没有的单词。而其它的地方ide就没什么戏了。如果你要修改前面第4个单词，你刚把手从键盘上撤下来还没放到鼠标上，vim的用户按3个键esc,3, b就定位到了。举个对你应该特别熟悉的例子：你可能经常需要把程序中的两行并成一行，你常常把光标移过去，然后删除所有自动缩进；vim用户用数字建、k 定位到行，按下shift+j就搞定了。速度，永远不是从帮你输入废话上得来的。
　编译、发布、部署、打包程序，这种事情你可能经常让ide代劳。不过你也可能从未想过ide怎么会这么清楚的。它们的能力来源很简单，就是跟*nix学的。make程序，提供了组织程序的一条龙服务的终极武器，每个ide的必备抄袭作品。vs再怎么发展，也不会少了它的nmake.exe，否则它就成了史上最大记事本了。但李鬼终究还是敌不过李逵，nmake这样的东西怎么能敌得过新时代的gnu-make？别说是m$麾下的东西了，就是 ant在它面前也得退避三舍啊，复杂的xml怎么能比一个领域特定编程语言强大？连写makefile都嫌烦，没事还有automake、patch，好了只要把目录组织一下就行了，而且连打补丁都不用你操心了。
　这些事关ide的存在价值的东西都在*nix小工具面前黯然失色，其它的东西就更没得比了：gnu下有最强大的编译器、汇编器、调试器，各种dsl程序遍地爬，grep不行上awk，再不行上perl，连接它们的管道四通八达，你可以随心所欲地在编辑器里查看从最底层的gcc那儿传上来的经过数层处理后的信息。
　不过懒得出奇的*nixr也有嫌这个也烦的时候，如果有什么语言不用编译不要调试不用部署就更好了。动态语言就是这样的东西。在任意一个平台下装上解释器，一条命令就能执行；高阶函数的出错信息可以跟踪出调用轨迹，不需要调试器；文件间互相说声引用谁就行了，不用部署。写好了代码不知道怎么运行？把相应解释器装上运行一句 <语言名> <文件名> 就行啦！
　黑黑的窗口，闪动的光标下是行编辑库，让你在输入命令时获得相当于使用emacs的编辑效率；kde当然没什么意思，仿win仿着玩儿的大玩具一个；试试看怎么把wmaker调成Mac第二，把fvwm做成外星OS，我觉得这个比较有意思。我现在的freebsd就是用的wmaker窗口管理器，装上几个顺手的gtk程序，剩下来的让vte终端全包。性能好到不行，启动图形界面4秒钟。Unix的重点不在于刚装好时的配置如何，而在于极限的能力是否能满足你的意图。就拿winer们常指责*nix的驱动程序一项来说，其实os里这些驱动都有了，你所要做的只不过是修改某个配置文件中的一两行。这帮winer自己数典忘祖，忘了win装完后必须下载驱动才有全屏显示和声卡支持，而且如果你没有网卡驱动就只能哭去了！
　再如装软件。win装软件要搜索多长时间才能下到，还得提防有没有恶意软件，点多少个next才能装完，装完想删掉还卸不干净，装着装着注册表就破50M了。pkg、yum、apt这些东西多方便，你只要知道软件名，输一行命令就能全搞定。有些不明事理的人还指责*nix软件怎么会对其它软件包有依赖。其实这才是*nix的魅力所在：开发出来的东西大家用，做的好的就是库。事实上，只有本地安装命令才会指出依赖性问题，使用自动安装连这些被依赖的软件也一并装了，反正想删就删，*nix分区只要有5%的空间就能保证没有磁盘碎片，多装没坏处。
　最后想说的是玩游戏。我用win的时候打了一年魔兽，现在在班上几乎无敌；但又能怎么样呢？我下围棋估计能全灭学校的人，然而没什么人知道。由此我意识到，游戏终究是一种逃避，想把在其它地方失去的虚荣心找回来。领悟了这一点，我也就不再玩游戏了；有时间就下围棋，没时间下就国际象棋， *nix下的gnugo和gnuchess都是普通棋类程序中的强者（不过围棋程序现在的算法还做不了太强，前者还不是我的对手），杀败了它们还可以上 igs和ics，生活很幸福~`

复习 Perl

2007-11-08T20:18:00.000+08:00

今天我去报名下一次托福模考，顺便去了书店转转——很长时间没关心计算机方面的书籍了，我唯一想看到只是《精通正则表达式》，也算是 “门当户对”。不过还是留意了一下Perl方面的书籍。《Perl入门》是一本小书，42块钱买来不值，于是我干脆发挥一下我在编程语言方面的功底，当场看完了事。

学习了更多编程语言原理方面的知识之后再来考察Perl语言果然有一些新感受。Perl关键字众多，但其实并不复杂：undef 好记还是 undefined？也没有 NULL 啦 nil 啦什么令人混淆的东西。空变量就是没定义，空表就是空表嘛。其它的关键字设定，如果你能忍受shell的fi什么的恶心东西那有什么理由不能忍受 Perl？

字符串用常量替换和括号代换体现是Perl的首创。学习前者的有PHP，后者有Ruby，不过弄来弄去还是不能取代Perl强大的上下文精神——到目前为止的语言都不能在字符串代换时展开列表甚至是展开列表切片就是一个证明。Ruby照抄了括号体系，但还是不敢抄Perl太多东西。在正则表达式里展开变量，IO描述符呢？它会和别的“纯”的语言一样露出叫你服从安排的嘴脸。

Perl的正则表达式已经红的发紫了——正如《学习Perl》一书骄傲的自夸——“很多语言和库都会以‘支持Perl风格正则表达式’作为卖点”。$` $& $' 这三个变量的设计更是叫我拍案叫绝！一方面，这三个变量对于实现不修改原数据的函数式编程来说是至关重要的，它可以把匹配过程表述为“过去，现在，将来”；另一方面，英语中常常使用`号作为应用开头以区别'x缩写形式，所以这种命名十分清晰，意思就是“开头，和，结尾”！（Perl使用的这种“命名推导”的体系和我早期设计的Mazy(t)是类似的:)）

最后谈一点语义方面的东西。Perl的函数参数传递，本质上是只传递了一个变量（这与Ruby、Groovy之流的简单模仿具有核心上的不同），然后靠类似模式匹配的语法对它们进行命名。这个机制和我的Mazy (i)语言的做法是相同的；只不过我扩展了模式匹配的能力并把它提高到Lambda演算兼容的层次罢了。至于这种手法的优势——你不需要再去思考是用 max(a,b,c)还是max([a,b,c])甚至是apply(max,[a,b,c])了！Perl懒人们笑哈哈...由此可见，Python3 新加入的取代apply的语法，只能说明Guido大学课程没学好~~`

付：由Perl想到的Unix法则

不知道应该称为“法则”还是“通病”——概念充分实例化，尽可能地自圆其说。以Vim为例，普通模式，各种命令一套意思；换个环境或者开头控制符（这是Emacs吧？），命令不变，变成表达相反含义或对不同视角的对象应用合理解释后的命令；实在不能合理解释，怎么着也要凑一个上去。Perl也是这样。三种上下文标记，换成默认变量没法解释了，还要凑个类似的；散列怎么会有切片？《Perl入门》还强词夺理；while(<STDIN>) 这样的用法没意义，就凑一个方便的意义上去。不过还是那句话，“倒也门当户对”就是了。为了让大家能在看人打字手抽筋的时候安心喝茶，Larry Wall 用心良苦啊~`

基于消息传递的 Scheme OOP

2007-09-22T10:45:00.000+08:00

续上次的OOP 诡异教程，我用 Scheme 宏写了一个类似的系统，拿来晒晒。

;; 这里只有部分定义，快速排序和二分法查找的代码就不帖在这儿了
;; 这里是 slot 类型的定义，Scheme 中不能动态 eval，只能用点别的招数
(define (make-slot name act) (cons name act))
(define (slot-name s) (car s))
(define (slot-act s) (cdr s))
(define (slotstring a) (symbol->string b)))

;; 主要的转换宏，语法比较丰富，但至少要带有一个 that 块
;; 语法可以只给出 that 块：(class (that (slot-name1 slot-act1) ...))
;; 也可以指定继承，要求在 class 关键字后出现原型对象：
　　;;(class extended-obj (that (slot-name1 slot-act1) ...))
;; 在 that 块之后还可以加入 where 块，这样可以指定不对外可见的类属性
;; 需要注意的是，where 块中的定义不能引用 self 等特殊命名，that 才行
;; 另外外部只能引用 origin, has-slot?, slot-names 3个特殊命名
(define-syntax class
(syntax-rules (that where)
　((_ that-block)
　 (class (absobj) that-block))
　((_ org that-block (where def ...))
　　(letrec (def ...) (class (absobj) that-block)))
　((_ org (that (slot val) ...))
　　(lambda ()
　　 (letrec ((slot val) ...)
　　　(let* ((origin org)
　　　　　　 (slots (list-qsort slotvector (map slot-name slots)))
　　　　　　 (slot-acts (list->vector (map slot-act slots)))
　　　　　　 (has-slot? (lambda (v)
　　　　　　　　　　　　 (vector-bsearch symbol index -1)
　　　　　　　　　　　(vector-ref slot-acts index)
　　　　　　　　　　　(case verb
　　　　　　　　　　　 ('origin origin)
　　　　　　　　　　　 ('slot-names slot-names)
　　　　　　　　　　　 ('has-slot? has-slot?)
　　　　　　　　　　　 (else (origin verb))))))))
　　　 self))))
　((_ that-block where-block)
　 (class (absobj) that-block where-block))))

;; 这里需要注意的是，因为嫌烦，absobj 被实现为了一个空壳子
(define (absobj)
(lambda (verb)
　(display "This object can't handle ")
　(display verb)
　(newline)))

测试一下：
> (define c1 (class (that (x 10))))
; no values returned
> (define c2 (class (c1) (that (z 16) (y 12))))
; no values returned
> (define o2 (c2))
; no values returned
> (o2 'x)
10
> (o2 'non-slot)
This object can't handle non-slot
#{Unspecific}
> (o2 'slot-names)
'#(y z)
> (o2 'origin)
#{Procedure 8647 (self##497 in c1)}

输出好像很古怪的样子~`我用的环境是 Scheme 48 虚拟机。
这儿的例子只覆盖了一小部分，剩下的比如 where 就自己慢慢玩吧。
Scheme 的“卫生宏”不但强大，还能制止你设计不好的语法，有意思。
消息传递真的很有意思。留个小题目，增加一个特殊方法 clone，把继承机制调整为差异继承+纯基于对象，类似 IO 语言的面向对象机制。
这个“系统”的完整代码在此下载，升级版本就算了吧 :)

Mazy i 编程语言定义 (1,2)

2007-09-16T01:09:00.000+08:00

　;; 纯属写着玩儿，尚未最终决定的版本已经与此差别很大，比方说第二章。
　;; 因为修改麻烦，本博客有关 Mazy(i) 设计方面的文章从此只发表第一稿。

1. 前言
Mazy i 编程语言，是一种用一阶λ演算的观点解决普通数学问题的纯函数式编程语言，具有极其简洁的语法和一定的通过数学表示推导解决数学问题的能力。它被设计为一种附合熟悉普通数学记法的用户在思考函数式编程时使用的简记记法的语言。它在语法、语义、实现方面的设计必须附合这一要求。第2章对此给出了概述性的解释。
第3章具体描述 Mazy i 的所有语法，每个语法后有用 Mazy i 扩展记法给出的语义描述，某些语法可能附上实现指导。
第4章描述了 Mazy i 程序文件中位于代码之前的文件说明区块，以及程序文件的加载、执行方式。
第5章描述了 Mazy i 内置库中的所有函数和宏，重点概念会给出 Mazy i 扩展记法的描述。
附录A总结第3章给出的用简化的 BNF 表示的 Mazy i 形式语法。
附录B列出了部分参考文献。
Mazy i 指的是 Mazy 语言第三版。Mazy 代表数学和懒惰，不是混乱和忙碌。字母 i 源自 Mazy 语言的版本命名传统，从第一到第七版分别为 s-t-i-n-g-e-r，排版字体为斜体，下标。Stinger 这个单词是作者姓氏，此外没有其它含义。
以下用 Mazy 代指 Mazy i。

2. 概述
编程语言必须对其设计意图有强大的表现力。强大基于完备，完备基于简单。
Mazy 的设计意图是作为一种可执行的简记记法帮助熟悉简单数学表示法的用户思考、编程或教学。也就是说，Mazy 试图用程序的观点去解释范围不超过基本函数、数列的数学记法。当然，作为基于λ演算的编程语言，Mazy 还有足够的表现力去解决更复杂的问题。
例如，Mazy 中的列表可以作数列解释。对于给定的列表 l，其第 n 项在 Mazy 中可直接表示为 l n。同时，使用递推的观点可以写出求列表长度的函数。下面的函数就是一个合法的 Mazy 程序：
　len ls =
　　　0, ls = ()
　　　len(tail ls) + 1.
Mazy 可以把列表看作是第一项 x 与剩余项 xs 的组合 x:xs，所谓 tail 函数不过是：
　tail (x:xs) = xs
那么 len 函数就可以直接写成：
　len () = 0
　len (x:xs) = len xs + 1
以上是 Mazy 在语法方面试图实现其设计意图的一个例子，用到了单一控制结构和函数单参数的语法特性。其它语法，包括块结构、列表领悟、λ形式等，以及为保证这些语法的等效性而设计的 Mazy 编程语言语义，例如完全无副作用，单一数据类型，单一数据结构，完全基于模式匹配等，都会在本文档中给出详细描述；附加的实现指导，例如尾递归优化，列表、元组共存模型，缓存机制等，则用于指导 Mazy 的实现人员更好地保证基于这些语义的程序高效地执行，以防止用户被迫转用其它语义思考和编程。

Mazy(i) plain-BNF 修订稿

2007-09-12T22:56:00.000+08:00

这次把 Bug 基本上都修掉了，语法完备化的同时去掉了一些容易引起混淆的运算符。毕竟 Mazy means Math & Lazy, not Mess or Busy.

comment :: ;;.*(?=\n)
Number :: \d+(\.\d+)?(_[+-]?\d+)?
Identifier :: [\$]\w*[\?']?
program ::
　　sentence
　　sentence \n program
sentence ::
　　functionDefinition
　　patternMatching
functionDefinition ::
　　Identifier pattern = Experssion
　　Identifier pattern = \n block .
block ::
　　Experssion
　　program \n Experssion
　　Experssion ; whereBlock
　　program \n Experssion ; whereBlock
　　clause
　　program \n clause
　　clause ; whereBlock
　　program \n clause ; whereBlock
clause ::
　　subClause
　　subClause \n Expression
subClause ::
　　Expression , Expression
　　Expression , Expression \n subClause
whereBlock ::
　　patternMatching
　　patternMatching \n whereBlock
patternMatching :: pattern = Experssion
Expression ::
　　Number
　　Identifier
　　Lambda
　　Compound
　　Operation
　　Comprehension
　　List
　　( Expression )
Lambda :: [ pattern -> block ]
Compound :: [ block ]
Operation ::
　　Expression Expression
　　prefix Expression
　　Expression midfix Expression
prefix :: oneof
　　+ - ~ #
midfix :: oneof
　　midSymbol
　　% = ~= < > >= <= & | . .. : ++ <-
midSymbol :: oneof
　　+ - * / ^ ** //
Comprehension :: ( Expression => sequence )
List ::
　　( )
　　( Expression , )
　　( sequence )
sequence ::
　　Expression , Expression
　　Expression , sequence
pattern ::
　　_
　　Number
　　Identifier
　　patternOperation
　　patternList
　　( pattern )
patternOperation ::
　　pattern : patternList
　　pattern midSymbol Number
　　Number midSymbol pattern
patternList ::
　　( )
　　( pattern , )
　　( patternSequence )
patternSequence ::
　　pattern , pattern
　　pattern , patternSequence

最重要的变更还是新增了 block 抽象语法，没想到的时候是很痛苦的。
为语法分析增加的额外产生式也有了，这样语法和语义基本上就定下来了，下面开始写词法分析器——相当好写，输出的数据结构上用点技巧（平衡符号的开始符号指出平衡点），连带 AST 生成器一并好写。
Ray 语录：做语言要做到什么地步才叫绝？想再加1条产生式时，烦于必须再加一系列产生式；想再减1条产生式时，苦于必须再减一系列产生式——这就是所谓的“精益求精”。

Mazy(i) BNF 第一稿

2007-09-08T20:51:00.000+08:00

我设计的 Mazy 语言第三版，意淫了一下，把 BNF 给磨出来了。28条 plain-BNF，即使算上语法分析的额外要求也不算多。

Digits :: [0-9]+
Identifier :: [a-zA-Z]+_*'*
Comment :: ".*?"
Program ::
　Sentence
　Sentence \n Program
Sentence ::
　FunctionDefinition
　PatternMatching
FunctionDefinition ::
　Identifier Pattern = Experssion
　Identifier Pattern = \n Clause .
　Identifier Pattern = \n Clause ; WhereBlock .
　Identifier Pattern = \n Program Clause ; WhereBlock .
WhereBlock ::
　PatternMatching
　PatternMatching \n WhereBlock
PatternMatching ::
　Pattern = Experssion
Expression ::
　Number
　List
　Identifier
　Operation
　Condition
　Lambda
　( Expression )
Number ::
　Digits
　Digits.Digits
　Digits_Digits
　Digits.Digits_Digits
List ::
　( )
　( Expression , )
　( Sequence )
　Comprehension
Comprehension :: ( Expression => Sequence )
Sequence ::
　Expression
　Expression , Sequence
Operation ::
　Expression Expression
　Prefix Expression
　Expression Midfix Expression
　Expression Postfix
Condition ::
　[Clause]
　[Expression ; WhereBlock]
　[Clause ; WhereBlock]
Clause ::
　SubClause
　SubClause \n Expression
SubClause ::
　Expression , Expression
　Expression , Expression \n SubClause
Lambda ::
　\ Pattern -> Expression .
　\ Pattern -> Expression ; WhereBlock .
Prefix :: oneof
　+ - ~ #
Midfix :: oneof
　+ - * / % ^ ** // : ++ -- = ~= < > >= <= & | ! !! $ .. <-
Postfix :: oneof
　++ -- !

Pattern ::
　PatternAtom
　PatternList
　Pattern : PatternList
　PatternPreOpt Pattern
　Pattern PatternMidOpt PatternAtom
　PatternAtom PatternMidOpt Pattern
　Pattern PatternPostOpt
PatternList ::
　( )
　( PatternAtom , )
　( PatternSequence )
PatternSequence ::
　PatternAtom
　PatternAtom \n PatternSequence
PatternAtom :: oneof
　Identifier Number _
PatternPreOpt :: oneof
　- ~
PatternMidOpt :: oneof
　+ - * / ^ ** // :
PatternPostOpt :: oneof
　++ --

新语言想设计成为基于模式匹配的语言，于是进行了模式匹配完备化的努力，最后搞出了一个带有推导功能的东西，这样函数就可以只接受一个参数，同时满足了参数之间“关系”表达的要求——终于找到可以超过 Haskell 的地方了 :)
加入了 Lambda 表达式，且带有作用域的语法都有了一个 WhereBlock，但功能其实相当于 Scheme 中的 let* 而不是 Haskell 中的 where；
列表相当于 tuple 和 list 二者的结合，列表领悟也有了；
其它一些纯属使语言更“漂亮”的小改动不值一提，感兴趣的自己看吧。

我看 D 语言

2007-09-06T09:43:00.000+08:00

初，语言只能用有限的特性发挥有限的力量，那时有个语言自命简单(Basic)，其实是弱；真正强大的语言，能用有限的特性发挥出无限的力量，但它们的老大说话总是听不清(Lisp)，所以总是有人想取代它的地位；当然了，要使用无限的特性才能发挥出无限的力量的语言也是有的，只是太重了，比珍珠岩(Perlite)还重。然而还有这样一种语言，它们被设计拥有无限的特性，却只能发挥出十分有限的力量，这样的语言在被每个时代抛弃之后仍然不思悔改，现在它们那个以罩杯号码(D)命名的新任老大就是一个典型的例子。

用 Python 写了个背单词小工具

2007-08-25T17:56:00.000+08:00

注：此“软件”已被作者开为 Google Code 项目 Rewords 。

背单词关键在于重复，单词能不能背得取决于你看了它多少遍。把一个单词表(wordlist)中的每个 list 分成许多个 section，反复地浏览记忆就能记住。基于此，昨晚我用 Python 写了一个背单词的小工具，暂定名 Rewords 。

#!/usr/bin/python
# Filename: rw.py

import sys

def locate (f, i, n = 1):
　　if n == i:
　　　　print f.readline()
　　　　return f
　　if f.readline() == "\n":
　　　　return locate(f, i, n+1)
　　return locate(f, i, n)

def struct (f, st = []):
　　ln = f.readline()[:-1]
　　if ln == "":
　　　　return st
　　return struct(f, st+[ln])

def conmat (ls, l, tmp = []):
　　if len(tmp) == l:
　　　　return [tmp]+conmat(ls, l)
　　if len(ls) <= l and tmp == []: 　　　　return [ls] 　　return conmat(ls[1:], l, tmp+[ls[0]]) def inter (st): 　　'''usage: `Enter`
-
n : next word
p : prev word
d : down to next section
u : up to prev section
: jump to section
l : jump to list '''
　　def term (rt, lt = [], n = 0, cur = 'n'):
　　　　def help ():
　　　　　　print inter.func_doc
　　　　　　term(rt, lt, n, cur)

　　　　def next ():
　　　　　　if rt == []:
　　　　　　　　term(lt , rt, n, 'n')
　　　　　　print rt[0]
　　　　　　term(rt[1:] , lt+[rt[0]], n, 'n')

　　　　def prev ():
　　　　　　if lt == []:
　　　　　　　　term(lt , rt, n, 'p')
　　　　　　print lt[-1]
　　　　　　term([lt[-1]]+rt, lt[:-1], n, 'p')

　　　　def down ():
　　　　　　if n == len(st)-1:
　　　　　　　　term(st[0], n=0)
　　　　　　term(st[n+1], n = n+1)
　　
　　　　def up ():
　　　　　　if n == 0:
　　　　　　　　term(st[len(st)-1], n=len(st)-1)
　　　　　　term(st[n-1], n = n-1)

　　　　def to (p = 1):
　　　　　　num = (p-1)%len(st)
　　　　　　term(st[num], n = num)

　　　　def err ():
　　　　　　print " # unsupported command"
　　　　　　term(rt, lt, n, cur)

　　　　cmd = sys.stdin.readline()[:-1]
　　　　if cmd == "q": quit()
　　　　if cmd == "h": help()
　　　　elif cmd == "":
　　　　　　if cur == 'n': next()
　　　　　　elif cur == 'p': prev()
　　　　elif cmd == "n": next()
　　　　elif cmd == "p": prev()
　　　　elif cmd == "d": down()
　　　　elif cmd == "u": up()
　　　　elif cmd.isdigit(): to(int(cmd))
　　　　elif cmd[0] == 'l' and cmd[1:].isdigit():
　　　　　　start(int(cmd[1:]))
　　　　else: err()
　　term(st[0])

def quit (m = ""):
　　if m:
　　　　print m
　　　　sys.exit(1)
　　sys.exit(0)

def start (wl = 1):
　　'''usage: python rw.py [list] [section]
The wordlist named must be separated by blank lines;
program will start with the [list] or first part of the wordlist;
the each section will contain [section] or 8 words. '''
　　inter(conmat(struct(locate( \
　　　　open(sys.argv[1] if len(sys.argv) > 1 \
　　　　　　else quit(start.func_doc)), wl)), \
　　　　int(sys.argv[3] if len(sys.argv) > 3 else 8)))

print "rw.py - Rewords 0.1a by lichray\n"
start(int(sys.argv[2] if len(sys.argv) > 2 else 1))

程序是自省的，用起来应该没问题。无参数运行 python rw.py 显示帮助。
参数1 是单词表文件名，这个文件需要被空行分解为多个 list，每个 list 的第一行是标题；
参数2 是启动时加载的 list 编号，默认为 1；
参数3 是每个 section 包含的单词数，默认为 8；
进入互交描述后参考帮助，输入 h 命令，回车。
我这儿有一个可用的单词表——Barron SAT 词表，但存在一个小 Bug，不知为什么这个词表只能加载前13个 list，想帮忙的人留个邮箱地址，我把东西都发过去。
另外 locate() 函数还不能处理 readline() 越界的情况，这部分没完成。
最后根据我的代码风格，猜猜看我最近什么语言用的比较多？

OOP 诡异教程（下）

2007-08-18T19:58:00.000+08:00

这是最终确定的 JavaScript 基于消息传递编程风格的文章“OOP 诡异教程（上）”的下篇。原文地址：http://let-in.blogspot.com/2007/06/oop.html。原来的想法是以风格开头，谈到 JavaScript 的内部机制，但作者 lichray 迟迟没有动键盘，认为不如利用已有的风格做一套机制出来，这样可能更有意义。于是，就有了这个更加“诡异”的下篇。

四. 扩展的实现
上文最后给出了一个“看上去很美”的基于消息传递的编程风格，比如构造一个 People 类的代码类似：

function People () {
　　var money = 0
　　function setMoney (dollars) {
　　　　money = dollars
　　}
　　function pay (dollars) {
　　　　money -= dollars
　　}
　　return (function (verb) {
　　　　return eval(verb)
　　})
}

有了这样的语法我们就可以描述不少句子了。但是存在一个问题：现实中的 Objects 之间是存在关系的——比如，forrest 是个 IQ 为 75 的傻子，傻子是 People 的一种。而我们仅仅是生搬硬套了一种语法而割裂了这种 "is-a" 关系。现在我们的工作，目的之一就是让这样一个“真切”的世界从我们已有的编程风格的地基上拔地而起。
到底应该怎样做才能使 Fool 产生的对象都能响应 People 的消息呢？我们要给 Fool 产生的对象（也就是返回的那个匿名函数啦）都添加这样一种能力：如果在 Fool 中响应不了消息，那就反馈给 People 响应。

function Fool (iq) {
　　var IQ = iq || 0
　　function init (iq) {
　　　　IQ = iq
　　}
　　return (function (verb) {
　　　　try {
　　　　　　return eval(verb)
　　　　} catch (e) {
　　　　　　return People()(verb)
　　　　}
　　})
}

js> forrest = Fool()
js> forrest('init')(75)
js> forrest('IQ')
75
js> forrest('money')
0

五. 语法扩展和代码生成
这下代码量增加了很多，强迫潜在的使用者们在创建每个类时都这样写那实在是令人抓狂。本来这篇文章应该不提此类问题的解决，但考虑到有益于读者理解“机制”这个抽象概念，这里给出一个可行的方案——把普通的类代码用 Function() 函数重编译为可用的 JavaScript 函数。也就是说，我们能给出类扩展的代码并指定被扩展的类来获取类似上文的代码：

Fool = extend('People()', function (iq){
　　var IQ = iq || 0
　　function init (iq) {
　　　　IQ = iq
　　}
})

为了方便字符串操作，我们希望编译后的代码的参数部分（如 People()）都集中出现在一个位置且尽可能便于定位。在函数头添加一句

var origin = People()

当然是可行的，这样还能使 Fool 内部显式引用到其超类。但这样还不够漂亮。我们修改编译后的样例代码为：

function () {
　　return (function (origin) {
　　　　var IQ = 0
　　　　function init (iq) {
　　　　　　IQ = iq
　　　　}
　　　　return (function (verb) {
　　　　　　try {
　　　　　　　　return eval(verb)
　　　　　　} catch (e) {
　　　　　　　　return origin(verb)
　　　　　　}
　　　　})
　　})(People())
}

这个利用参数传递变量的小技巧不值得学习，实际效率不高。但在这篇文章中，这样绑定特殊变量的技术是标准方案。
那么，extend() 函数的实现为：

function extend (originc, code) {
　　function argsArea (code) {
　　　　// 题外话，正则表达式也有不值得使用的时候
　　　　return code.slice(code.indexOf('(')+1, code.indexOf(')'))
　　}
　　function bodyCode (code) {
　　　　// 不用 trim() 了，没事儿找事儿
　　　　return code.slice(code.indexOf('{')+1, code.lastIndexOf('}'))
　　}
　　function format (body) {
　　　　var objc = bodyCode(function () {
　　　　　　return (function (verb) {
　　　　　　　　try {
　　　　　　　　　　return eval(verb)
　　　　　　　　} catch (e) {
　　　　　　　　return origin(verb)
　　　　　　　　}
　　　　　　})
　　　　}.toString())
　　　　return 'return (function (origin) {'+body+objc+'})('+originc+')'
　　}
　　var $ = code.toString()
　　return Function(argsArea($), format(bodyCode($)))
}

这样前文提到过的 extend 的实例代码就可以正常运行了，测试代码不再重复。

六. 机制完备化
这样，我们的基于消息传递编程风格的一套面向对象机制就确定下来了。机制是宪法，是语言的根本大法，有了它，我们就可以通过修改代码生成器，很快地给这套机制进行完备化。
想法有很多，例子只举两个。
第一个例子：类的定义中应该能直接引用到将产生的对象 self。答案只有一句话：把返回的那个作为对象的匿名函数命名为 self。
第二个例子：既然是单继承模式，应当存在一个顶层类 AbsObj，使没有指定继承的类自动继承它。答案也只有一句话：在 extend 函数体第一行添加代码：

if (arguments.length == 1) {
　　code = originc
　　originc = 'AbsObj()'
}

然后手工构造设计 AbsObj 类，为空也无所谓。不过当然了，一般都会给顶层类添加一些全局性质的消息绑定。由于是“底层操作”，基本上都需要修改 extend 函数。做了一个简单的：

function AbsObj () {
　　//检测是否能响应此 verb，要再用一次异常处理
　　function canHandle(verb){
　　　　try {
　　　　　　// 别担心这里的 self 会传递不过去
　　　　　　self(verb)
　　　　} catch (e) {
　　　　　　return false
　　　　}
　　　　return true
　　}
　　function toString() {} // 这个搞起来其实很麻烦~`
　　var self = function (verb) {
　　　　return eval(verb)
　　}
　　return self
}

js> Obj=extend(function(){x=5})
js> o=Obj()
js> o('canHandle')('x')
true
js> o('canHandle')('y')
false

文章写完了，小结一下。消息传递的编程不仅仅是一种代码风格，还可以成长为一种完备的机制。这种完备性远不只是这两篇加起来不到300行的文章所能覆盖的（例如非常彻底的“万物皆对象”，因为只要是能响应消息的函数，连接一下 AbsObj 就是合法对象了；类，函数都可以），大家可以试着玩一玩，顺便体会一下这个计算模型的透明和强大。
另外，熟悉函数式编程的朋友可以帮忙思考一下：这样一个基于闭包变换的计算模型实质上是函数式的，再配合动态的函数式的对象级继承（用一个匿名类代换一下）就能在纯 FP 真正下实现 OOP 了。可惜的是每一次更新操作都要重新生成对象，性能代价大了点，不知道大家有什么好想法。

functional.js 介绍及源码分析

2007-07-27T17:22:00.000+08:00

作者 lichray 对刚刚在网络上现身的 JavaScript 函数式编程库 functional.js 进行了详尽的解读。

functional.js 是模仿 Haskell 语言标准库 Prelude 制作的函数式编程库，主要实现了：

扩展的克里化函数
运算符函数化
紧缩的匿名函数语法
无须指定参数的匿名函数语法
函数向导语法
基本的通用列表操作
部分扩展基于对象化

其中，扩展语法由字符串表示。未能实现的特性有：

尾递归优化
模式匹配（包括参数匹配、列表匹配、情况分析）
惰性运算（包括无穷列表）
列表领悟
扩展绑定、同时绑定
其它列表操作（以及对于列表操作的基于对象化）

下面我们一边分析源代码，一边讲解库的用法。

一、库安装和概览
functional.js 库的所有用户级操作分为3个部分：

全局操作，绑定在全局对象 Functional 上，主要是高阶函数操作和列表操作，所谓库安装即把这些内容可选的、安全地复制到全局环境
函数扩展，实现特殊高阶函数特性的工具（特供内部）
语法扩展，绑定在 String.prototype 上，负责将字符串表示的 lambda 语法翻译为相应的高阶函数（特供内部）

下面是安装函数 Functional.install 的源代码（中文注释为笔者所加，下同）：

Functional.install = function(except) { // except 参数是一个对象，不加载这些操作
var source = Functional,
　　 target = window; // 复制操作到全局环境 window，仅限于浏览器环境
for (var name in source)
　　 name == 'install' // 当然，不能把 install 复制到 source
　　 || name.charAt(0) == '_' // 命名开头为 _，私有属性
　　 || except && name in except
　　 || {}[name] // work around Prototype
　　 || (target[name] = source[name]);
}

一般只要执行 Functional.install() 一句即可。

二、高阶函数操作
1. Functional.compose ([Function]) // 匿名的参数类型指的是 arguments 的类型，下同
　　接受一列参数个数被认为相等的（允许 Currying 算子）函数为参数，返回一个函数，它接受一定的参数，能够对它们累积倒序 apply 那列函数。
　　示例：compose('1+', '2*')(2) => 5
　　
2. Functional.sequence ([Function])
　　累积 apply 的顺序为参数顺序，为 compose 的反序。
　　示例：sequence('1+', '2*')(2) => 6

以上两个操作亦可见于 Function.prototype，用法：'1+'.lambda().sequence('2*')(2) ==> 6

3. Function.prototype.flip ()
　　返回一个函数，是原函数对象 this 参数接受顺序颠倒后的版本，不应属于函数扩展类。
　　示例：flip('a/b')(1, 2) => 2
　　
4. Function.prototype.saturate ([]) {
　　返回一个函数，是原函数对象 this 忽略自己接受的参数，仅接受指定参数的版本。
　　形式：f.saturate(args...)(args2...) == f(args...)
　　
5. Function.prototype.aritize (n::Number) // 有名的参数类型由 :: 指定，下同
　　返回一个函数，是原函数对象 this 忽略自己接受的参数列表中下标为 n 的参数的版本。
　　
6. Function.S (f, g::Function)
　　以单个大写字母命名的是函数的原子操作，应被收入 Functional 对象，这个很奇怪。
　　形式：S(f, g)(args...) == f(g(args...), args...)
　　
三、通用列表操作
1. 绑定在 Functional 对象上的部分完全照抄 Haskell Prelude 以及 Clean 的命名，它们是：

map(f, [x1, x2...]) = [f(x, 0), f(x2, 1), ...]
foldl, reduce(f, init, [x0, x1, x2]) == f(f(f(init, x0), x1), x2)
filer, select('%2', [1,2,3,4]) -> [1, 3]
foldr(f, init, [x0, x1, x2]) == fn(x0, f(x1, f(x2, init)))
some(f, [x1, x2, x3, ...]) == f(x1) || f(x2) || f(x3)...
every(f, [x1, x2, x3, ...]) == f(x1) &&amp;amp;amp;amp; f(x2) && f(x3)...

以上操作的介绍网上到处都是，不再赘述；但有一点不同，即它们除了接受正常参数之外，还在最后接受一个可选参数 object::Object，它被用于指定操作执行的对象/环境。
另外，这些操作全部基于命令式风格实现，对于没有尾递归优化的 JavaScript 来说，效率有保障。

四、群体谓词操作
1. Functional.and ([Function])
　　接受一列函数为参数，返回一个函数，它接受一个参数，对该参数 apply 那列函数，如结果全为 true，返回 true；否则返回 false。
　　形式：and(f1, f2...)(args...) == f1(args...) && f2(args...)...
　　示例：and('>1', '>2')(2) => false
　　
2. Functional.or ([Function])
　　接受一列函数为参数，返回一个函数，它接受一个参数，对该参数 apply 那列函数，如结果全为 false，返回 false；否则返回 true。
　　形式：or(f1, f2...)(args...) == f1(args...) || f2(args...)...
　　示例：or('>1', '>2')(2) => true
　　
3. Functional.not = function(fn::Function)
　　返回一个函数，是参数返回的布尔值的函数（谓词，下同） fn 取否的版本。
　　形式：f.not()(args...) == !f(args...)
　　
4. Functional.equal ([Function])
　　接受一列函数为参数，返回一个函数，它接受一个参数，对该参数 apply 那列函数，如结果全部 == ，返回 true；否则返回 false。
　　形式：equal(f1, f2...)(args...) == f1(args...) == f2(args...)...
　　示例：equal()() => true // 特殊情况

五、函数扩展
　　这一章仅仅是介绍内部实现。
1. Function.prototype.bind (object::Object,[])
　　返回一个函数，作为 this 函数对象的副本，使其将在 object 环境下执行，并额外携带参数。
　　形式：f.bind(obj, args...)(args2...) == f.apply(obj, [args..., args2...])
　　
2. Function.prototype.curry ([])
这是实现克里化特性的关键函数，思想来自网络。

Function.prototype.curry = function(/*args...*/) {
var fn = this;
var args = [].slice.call(arguments, 0);
return function() {
　　 return fn.apply(this, args.concat([].slice.call(arguments, 0)));
};
}

　　返回那个传说中的可在参数不足时分步调用的函数——Currying 算子。
　　形式：f.curry(args1...)(args2...) == f(args1..., args2...)

其它的 curry 类函数有：

rcurry，对从右边开始缺少参数的函数作克里化
ncurry，不接受全部参数就不 apply 参数的版本
rncurry，前者的反序版本
uncurry，作者一再强调，这不是 curry 的反转版本。它会拆分出第一个已得参数，形式为：f.uncurry(a, b...) == f(a)(b...)

3. Function.prototype.partial ([])
　　在此函数定义之前，有定义 _ = Function._ = {} 。结合它们可以允许你像在 Haskell 中那样在参数列表中用 _ 忽略参数。但现在空谈是没用的，要结合第七章的语法扩展。
　　
4. Function.prototype.guard (guard:>Function, otherwise)
　　类似的，是一个允许在函数定义中使用向导功能的工具，尚缺少语法扩展支持。
　　形式：f.guard(g, h)(args...) == f(args...), when g(args...) is true
　　　　f.guard(g ,h)(args...) == h(args...), when g(args...) is false

六、工具函数
1. Functional.invoke (methodName::String, [])
　　示例：invoke('toString')(123) => "123"
　　
2. Functional.pluck (name::String)
　　示例：pluck('length')("abc") => 3
　　
3. Functional.until (pred:>Function, fn:>Function) // 用 :> 表示将参数强制转换类型

Functional.until = function(pred, fn) {
　　// 使用时参数会被强制转为 Functional 的函数，参数可为字符串
fn = Function.toFunction(fn);
pred = Function.toFunction(pred);
　　// 返回一个接受一个参数的函数，
return function(value) {
　　　　// 它不断对此参数 apply 函数 pred，
　　 while (!pred.call(null, value))
　　　　　　// 并用 fn(value) 的值更新 value，
　　　　 value = fn.call(null, value);
　　 return value; // 直到测试结果为 true。
}
}

　　类似 Haskell 的 until，是一种函数式的循环，用命令式风格实现。
　　
4. Functional.zip ([])
　　特别注意，此 zip 并非 Haskell 中的 zip，它接受可变参数列表而不是列表的列表。
　　形式：zip(a, b...) == [[a0, b0], [a1, b1], ...]

以上的章节中绑定在 Functional 上函数都可作为 Function 的对象方法直接使用，我们看这一行：

Functional.__initalFunctionState =
Functional._startRecordingMethodChanges(Function.prototype);

前文对它们作出了定义，这里忽略。用法：name(arg, args...) == arg.name(args...)。

七、语法扩展
1. String.prototype.lambda ()
　　把字符串表示的字符串翻译为函数扩展可接受的函数，进一步转为 JavaScript 函数。

String.prototype.lambda = function() {
var params = []; // 存储字符串形式的参数的列表
var expr = this;
　　// ECMAsplit 是作者为兼容 IE6.0 所写的 split 版本
var sections = expr.ECMAsplit(/\s*->\s*/m); // 使字符串被 '->' 分割
　　/* 注意，分割的结果支持超过任意个 '->'，下面会发现，
　　　　-> 9 或者
　　　　x -> y -> x+y 这样的代码也会被正确理解。
　　*/
if (sections.length > 1) {
　　　　// 这就是所谓的“正确理解”了
　　 while (sections.length) {
　　　　 expr = sections.pop();
　　　　　　// 然后把参数打碎，再重组为 JS 可识别的参数语法
　　　　　　/* 也就是说，x y -> x*y+2 和
　　　　　　　　x,y -> x*y+2 都可被接受。
　　　　　　*/
　　　　 params = sections.pop().split(/\s*,\s*|\s+/m);
　　　　　　// 装配成代码，顺便支持尾递归语法
　　　　 sections.length && sections.push('(function('+params+'){return ('+expr+')})');
　　 }
} else if (expr.match(/\b_\b/)) {
　　 params = '_'; // 忽略参数的前奏，下文判断
} else {
　　　　// 这里处理运算符表达式参数缺失的情况，相当于运算符函数化
　　　　// 分为前缺失和后缺失两种情况，
　　 var leftSection = expr.match(/^\s*(?:[+*\/%&|\^\.=<>]|!=)/m);
　　 var rightSection = expr.match(/[+\-*\/%&|\^\.=<>!]\s*$/m);
　　　　/* 注意，前缺失类似 *2，后缺失类似 2*，复杂表达式同样支持
　　　　　　此外，前后都缺失也可以，比如 * 甚至是 *3*
　　　　*/
　　 if (leftSection || rightSection) {
　　　　　　// 翻译缺失代码的技术：用 $1、$2 代换参数
　　　　 if (leftSection) {
　　　　　　 params.push('$1');
　　　　　　 expr = '$1' + expr;
　　　　 }
　　　　 if (rightSection) {
　　　　　　 params.push('$2');
　　　　　　 expr = expr + '$2';
　　　　 }
　　 } else {
　　　　　　// 这个地方就有点意思了；它使得函数支持参数指定缺失
　　　　　　/* 比如 x*y 就已经是一个函数了，相当于 x y->x*y
　　　　　　　　作者还特别防止了一个 bug，即对象属性访问语法中，
　　　　　　　　属性部分不被认为是未指定的参数。例如
　　　　　　　　obj.pro + 4 这个函数，只有 obj 一个参数
　　　　　　　　而且，this 和 arguments 不会被认为是未知数。
　　　　　　*/
　　　　 var vars = this.replace(/(?:\b[A-Z]|\.[a-zA-Z_$])[a-zA-Z_$\d]*|[a-zA-Z_$][a-zA-Z_$\d]*:|this|arguments|'(?:[^'\\]|\\.)*'|"(?:[^"\\]|\\.)*"/g, '')
.match(/([a-z_$][a-z_$\d]*)/gi) || [];
　　　　 for (var i = 0, v; v = vars[i++]; )
　　　　　　 params.indexOf(v) >= 0 || params.push(v);
　　 }
}
return new Function(params, 'return (' + expr + ')'); // 把代码装配成函数对象
}

八、过滤器生成器
　　仅供特别好学的同志们参考。
1. Function.prototype.prefilterObject (filter::Function)
　　形式：fn.prefilterObject(filter).apply(object, args...) == fn.apply(filter(object), args...)
　　
2. Function.prototype.prefilterAt (index::Number, filter::Function)
　　形式：fn.prefilterAt(i, filter)(a1, a2, ..., a_{n}) == fn(a1, a2, ..., filter(a_{i}), ..., a_{n})
　　
3. Function.prototype.prefilterSlice (filter::Function, start, end::Number)
　　形式：fn.prefilterSlice(i0, i1, filter)(a1, a2, ..., a_{n}) == fn(a1, a2, ..., filter(args_{i0}, ..., args_{i1}), ..., a_{n})

九、其它用户级函数
1. Functional.id = Functional.I = function(x) {return x};

2. Functional.constfn = Functional.K = function(x) {return function() {return x}};

3. .toFunction ()
　　在 String.prototype，Function.prototype，Function（需要参数 fn::Function）上都有绑定，把对象转换为一个合适的 Functional 函数。但你不需要把代码写这样，map('*2'.toFunction(),alist)，因为全局用户级函数都会对应为函数的参数自动执行 toFunction()，只要 map('*2',alist) 就行了。另外，String.prototype 上还有 JavaScript-Like 的 call、apply 方法。

十、结语
　　functional.js 很强，很有用，很牛X；但同时也很年轻（7.20 发布），很多可以实现的功能还不完善，不说列表领悟什么的吧，至少应该把 Haskell Prelude 库在通用列表操作方面的函数的移植工作完成。我们期待 Oliver Steele 的表现。

新人报到！

2007-07-14T08:32:00.000+08:00

大家好，我叫Ｂ...不是不是，我姓叶，叫Ｂ哥葉。我是氷の鋭同班同学，他教我学 Python 几个月了，前天我终于第一次在仅有师父提示的情况下自己写出了一个程序，耶！
原题是这样的：

一个六位数，分别用2，3，4，5，6乘它，得到的五个新数仍是由原数中的六个数字组成，只是位置不同，则此六位数是多少？

我把这题给做出来了！

def pcb(i):
　　if a(i)==a(i*2):
return pcb_3(i)

def pcb_3(i):
　　if a(i)==a(i*3):
　　　　return pcb_4(i)

def pcb_4(i):
　　if a(i)==a(i*4):
　　　　return pcb_5(i)

def pcb_5(i):
　　if a(i)==a(i*5):
　　　　return pcb_6(i)

def pcb_6(i):
　　if a(i)==a(i*6):
　　　　return i

def a(i):
　　c=b(i)
　　c.sort()
　　return c

def b(i):
　　return list(str(i))

# 这个原来我写的是错的，后来师父改滴——其实改滴也不好！
for i in range(100000,1000000):
　　if i and pcb(i):
　　　　print i
　　　　break

师父在学校那台破电脑上输代码滴时候抱怨说我的程序可以用程序写唠。这有什么关系，反正我的代码的速度超过师父的啦！

def list_equ (ls):
　　for cond in map(lambda x: ls[0] == x, ls):
　　　　if not cond:
　　　　　　return False
　　　　return True

def sort (ls):
　　ls.sort()
　　return ls

def test_num (num):
　　return list_equ(map(lambda x: reduce( \
　　　　lambda i,j: i+j, sort(list(str(x * num)))), range(2,7)))

def give_rst ():
　　return filter(test_num, range(100000,1000000))

for i in range(100000,100000):
　　if (test_num(i)):
　　　　　　print i

但是，最后师父使出了杀手锏，把这题用数学方法解出来唠，他个DB。。。
以后一定要超过他！

难得骂人

2007-07-05T14:32:00.000+08:00

2007-07-05 12:26:51 gcd0318 (北京)

　　汇编是SB？这话谁说的？注意看原文，我对汇编的判断是：
　　什么都能干，无敌
　　但是对汇编程序员的要求是：
　　把自己当SB，像机器一样的SB，像SB一样思维，一次只会走一步的SB，从来不知飞跃是何物的SB
　　具体原因前面解释过了
　　至于JAVASCRIPT是玩具的理由，娱乐眼球和浅薄，两者之间不矛盾，而且也没有本质区别。娱乐眼球的东西能深刻到哪去？这就是JS和 C、汇编的区别之一——注意，只是之一。当然，汇编和C也可以娱乐眼球——相信我，它们都有这个功能，JS、PYTHON能干的它们都能干，毫无问题，只是对程序员的要求高了点而已，一个求平方的计算，在PYTHON里是两句话，到了汇编里需要百十行，但最后也能算出来
　　你若真想知道PYTHON是什么，那我告诉你，PYTHON和汇编的区别就是圆珠笔和毛笔的区别，圆珠笔好学好用，却罕见有圆珠笔写出来的书法作品
　　眼看就2008了，谁还学毛笔字呀

2007-07-05 13:21:48 氷の鋭 (南京)

　　扛不住楼上了，这么恶心的话说一遍不够再说一遍...我都厌恶地没法儿引用了，免得再污染一次别人。只有SB程序员才会以SB的思维一次只走一步地用汇编！你不是自称看过《计算机编程艺术》吗？
　　PS: 2008 年奥运会会徽就是篆刻，不知道楼上在兴奋什么。

2007-07-05 13:53:46 氷の鋭 (南京)

　　而且再说了，什么人才有资格批评汇编？Scheme 程序员；而 JavaScript 正是 Scheme 思想的实用化体现。LSS 一会儿说汇编 XX，一会儿又说 JavaScript 玩具，心想这人那叫一个牛啊，让人肃然起敬；弄了半天是一 C/C++ 程序员，你不觉得你批评汇编是在狗咬自己人吗？还看不起 ECMAScript 标准委员会 IEEE，一看，又肃然起敬，心想这牛人又创造了一打编程语言了；弄了半天是一搞自然语言处理的还看不起这个看不起那个，啊？楼上下不觉得这个笑话很冷吗？！
　　说你举的例子可笑还不信，还敢回个“这个问题问的好”。来看看你说了些什么吧：“发明乐器的都是不会演奏乐器的，那么发明编程语言的，应该是不会用编程语言的。”不会演奏乐器你发明什么乐器啊？！你不知道鼓面撑起来可以响，不知道撑起来的鼓面要敲了才会响你发明出来之后教别人摩擦鼓面发声是不是？最后还像模像样地得出一结论叫“你学了几十种编程语言，看来你和发明新编程语言无缘了。”除了 Fortran 发明人在天之灵之外早期的每个语言发明人都是有多少优秀语言会多少——没看过几十书的人写的书，没奏过十几年乐的人奏的乐，没学过一打编程语言的人设计的语言，谁要看啊？！杜甫有句话说的好：读书破万卷，下笔如有神。不学习别人的思想出来闭门造破车之外还能怎样？说你不知道别人在说什么还有错了？
　　有些事情人家老惯着你您老还真就买起乖来了，我的妈呀！

（整个讨论）

各个语言编程的风格

2007-06-25T11:07:00.000+08:00

续 Re: 各个语言社区的风格。

不和任何编程风格相绑定的语言是玩具，例如 Lisp/Scheme、Perl、JavaScript，就好比法杖，拿来敲人不行，但往往可以拿来放魔法；
和两种编程风格相绑定的语言是怪玩具，例如 E、Ruby，就好比竹剑，拿来劈人吧，勉强；拿来放魔法吧，凑合；
只和特定的一种编程风格相绑定的语言才是常规的武器，这你可能会想到很多，但也有些区别：

和一种与设计原意相背离的编程风格相绑定的语言是怪武器，例如 C++、就好比吴钩，杀人的动作既不是砍又不是刺，是拉，用起来很别扭；
和一种与设计原意相符合但是过时了的编程风格相绑定的语言是笨重的武器，例如 C、Java/.Net，就好比铡刀，那边要杀人了，非得把敌人逮着绑好了推到你手边才能动手，步骤繁琐；
和一种与设计原意相符合并且有理论支持的编程风格相绑定的语言才是好武器，例如 Haskell、ML/OCaml、Erlang、Python，就好比刀剑，拿起来就能用，用的时候不是砍就是刺，干净利索。

一般来说，我倾向于两种极端：彻底的玩具和优秀的武器。

Re: 各个语言社区的风格

2007-06-24T11:54:00.000+08:00

Scheme/Lisp：我们是研究空气动力学的。
Smalltalk/Self：我们是设计飞机的。
Lua/JavaScript：我们是修理飞机的。
C/C++：我们是造飞机的。
Prolog/Planner：我们是开飞机的。
Python/Ruby：我们是卖飞机的。
Java/.Net：我们是打飞机的...

FP 做数学统计题

2007-06-24T09:46:00.000+08:00

今天布置的家庭作业还真是烦人！做完《数学之友》上“统计案例”一章所有习题。我的妈呀，算什么卡方、线性回归，公式繁琐地要命，按计算器都能把人按死。还是让电脑帮我做吧。
不用什么 GNUplot、Mathematica，俺用 Haskell，自己动手，丰衣足食！

一. 独立性检验
卡方就是一个公式：
　　
kaf a b c d =
　　((sqr ((a * d) - (b * c))) * (a + b + c + d)) /
　　　　((a + b) * (c + d) * (a + c) * (d + b))

-- sqr 函数是用来求一个数的平方的，再实现一下：
sqr n = n * n
　　
这样就搞定一种题了！以后算卡方不要太简单，把要检测独立性的四个数据按顺序作为 kaf 函数的参数输入 Hugs 就搞定了！
Main> kaf 184 61 91 9
11.097807845216 :: Double

二. 线性回归分析
其实就是求一个 y = a + bx 中的 a，b。把 xn 值、yn 值各表示为一个列表，像这样来使用：
Main> lrb [1..8] [5.54, 7.52, 10.02, 11.73, 15.69, 16.12, 16.98, 21.06]
2.12142857142857 :: Double
Main> lra [1..8] [5.54, 7.52, 10.02, 11.73, 15.69, 16.12, 16.98, 21.06]
3.53607142857143 :: Double
那么，就可以根据公式把它们抄出来：
　　
lrb xl yl =
　　-- 这里要注意一下，数学中的 sigma 是一种记法而非函数
　　(sigma
　　 (\(x, y) -> (x - xp) * (y - yp)) (zip xl yl)) /
　　　　sigma (\x -> sqr (x - xp)) xl
　　where
　　　　xp = avg xl
　　　　yp = avg yl

lra xl yl = avg yl - (lrb xl yl) * avg xl
　　
其中，avg 函数用来求一个列表的平均值（这里也就是所有 x 取值的平均值啦），它需要知道列表长度：
　　
avg ls = sum ls / len ls

len [] = 0
len (x:xl) = (len xl) + 1
　　
最后一个 sigma 函数的实现也很简单，就是累加嘛，只是写地有些不好看罢了：
　　
sigma f (x:xl) =
　　if xl == []
　　then f x
　　else f x + sigma f xl
　　
重申一遍，这里的 sigma 被表示为函数而非数学形式。那么，猜猜下面的 sigma 的数学形式是什么？
Main> sigma (\(x, y) -> x * y) [(1,4), (5,3), (3,8), (2,4)]
51 :: Integer

三. 线性相关系数
线性相关系数 r 的求法也只是个函数，再抄一遍：
　　
lrr xl yl =
　　　　(sigma
　　 (\(x, y) -> (x - xp) * (y - yp)) (zip xl yl)) /
　　　　sqrt ((sigma (\x -> sqr (x - xp)) xl) *
　　　　 (sigma (\y -> sqr (y - yp)) yl))
　　where
　　　　xp = avg xl
　　　　yp = avg yl
　　
以后这样用就行了：
Main> lrr [1..8] [5.54, 7.52, 10.02, 11.73, 15.69, 16.12, 16.98, 21.06]
0.987345979074916 :: Double
哇！这组数据的线性相关性接近 1，好高啊！

四. 结语
现在发现 Haskell 还真是实用，这个周末数学作业不愁了，打魔兽去喽！
最后给楼下的看客留一个与 FP 没什么关系的小题目：
对于一组线性相关数据，往往要求它的所有产生数据—— a、b、r，还有线性回归函数，顺便还要用这个函数再求一下对未来的预期。我如果当真输入 3 遍数据然后手工计算预期岂不是很傻？！想想看怎么让我只输入一遍数据就得到所有的产生数据（设计一下数据结构而已）还有线性回归函数（其实只有这个才有那么一点点技术含量）。

胡侃：面向对象思想的进化

2007-06-12T12:19:00.000+08:00

本文作者还是那个无名小辈 lichray。他在考查了一些语言和历史之后，觉得有必要谈一谈自己对面向对象思想的一些诡异的想法。文中会提到许多编程语言，不过当然了，重点在于思想，文章不是用来推销语言的。

面向对象编程思想的提出已经不是几年而是几十年了，考查其思想的变化，一方面是对现有语言的一些评判，另一方面，也算是对前辈计算机科学家的缅怀。 ——题记

Kristen Nygaard在1962年发明的 Simula 语言现在被认同为世界上第一种明确实现面向对象编程中某些“必要”元素（比如 class）的语言。Simula 是从 Algol 发展来的，可以说，是一种增加了 class 这个数据类型的 Algol，并将参数传递的默认模式从“按名调用”换成了“按引用调用”，还提出了根据类型确定初始化过程的方法。
从 Simula 的时代开始，科学家们在解决软件复杂度方面的思路开始“异常开阔”——当然也有资深的老派牛人们不这么认为。比方说 Peter Norvig，写了[url="http://norvig.com/design-patterns/"]Design Patterns in Dynamic Programming[/url]一书来反驳。他认为设计模式早已体现在以 Lisp 为首的一批语言中了，根本不需要什么面向对象。但我还是跟从偶像 Alan Kay 的观点。某些时候，把一种特定的编程风格做进语言里也是必要的。
言归正传。Simula 之后的语言开始试图把 class 作为编程的基础，并提出了一系列出色的、基于类的编程风格，最终确定了“万物皆对象”这一面向对象理论的“终极思想”。于是，Alan Kay 的 Smalltalk 在 70年代诞生了。它是世界上第一个真正把面向对象作为程序组织基础手段的编程语言。它首次明确实现了“消息”和“继承”这两个重要概念，对于“封装”和“多态”也给出了里程碑式的解决方案。在 Smalltalk 程序中，一切程序元素（除了词法元素）都是对象，一切操作都是消息。而且，Smalltalk 的实现本身就是用 Smalltalk 写成的，这也就意味着，对于一个 Smalltalk 程序来说，它的底层也是以面向对象为基础的。直到现在，也只有 Self 语言有资格在面向对象的程度方面与 Smalltalk 一较高下。
Smalltalk 在成为里程碑的同时，也成为了分水岭。Smalltalk 之后的面向对象语言的发展方向分成了两条路：一是继续把 Smalltalk 中封装的概念扩大化，为程序员添置更多的约束，以支持所谓的“大规模开发”的需要；另一方面，一些人主张继续理解面向对象的原理，为这一思想添加数学上解释，而不仅仅是“拿来主义”，使程序员更不易出错或“分神”。
正像大家所猜测的那样，前者指的是以 C++ 为代表的、坚持以命令式语言风格去实现面向对象的“有类”语言，后者是以 Self 为代表的、准备以函数式语言风格去理解面向对象的“无类”语言。
有类语言中，C++ 是曾经的“蔚然大宗”。它最初的名字是 C with class，很显然，一开始只是想对 C 作出像 Simula 之于 Algol 那样的修改。但是，C++ 诞生的时候（1983年），也是 Smalltalk 80 产生的时代，也是 Ada 语言正在开发的时代。在享受了 Smalltalk 提出的类方法、对象方法、私有方法等等语言设施之后，C++ 提出了3个为后来的有类语言广泛采用的关键字：private，public，protected。不避讳的话，可以简称3P。这种区分相对于 Smalltalk 来说略少了一点，但事实证明，在实际的抽象中是够用的。另外，C++ 还从 Algol68 （这只是一个失败的旧事物罢了）那儿学来了运算符重载，还有 Ada 中的泛型和程序包。堆砌了太多特性的 C++ 显得有些不堪重负，而且失败的教育（总是拿它当 C 的升级版讲解！）、失败的实现（尤以 Visual C++ 为甚）也是它后来在开源界不那么受欢迎的重要原因。C++ 之后的有类语言开始了消减多余特性，理清思路的努力。
紧接着 C++ 之后出现的语言主要有 Objective Pascal 和 Objective-C。后者是 Mac 公司的拳头开发语言，前者是什么？就是 Turbo Pacal 中的 Pascal 语言。二者试着给古老的语言们添加新的元素。前者只是很客气的添加了 new 和 unit，特性不足；后者的转型是成功的，但说句题外话：想象一下 C 的基础上直接加上 Smalltalk 的消息传递语法，这就是 Objective-C 的语法设计。
Java，原名 Oak。这个名字现在已经处于“无敌”状态，去年已经在语言排行榜上 K 掉 C 当上了老大。Java 没有什么新东西，正如上文所说，只是一个消除了多余特性后的产物。成功的原因，一是时代的召唤，而是官方实现的基于虚拟机的跨平台特性。虚拟机早已不是什么新事物了，不过有大公司出来宣传确实是新鲜事。也许是受了微软的影响，大多数普通程序员更愿意那种喜欢被某个大公司“罩着”的感觉，于是纷纷用起了 Java。历史就是这样，听不到你的嗟呀。
Java 火起来了，各大计算机方面的媒体上充斥着 Java、OOP 等等的字眼，仿佛面向对象只剩下 Java 一种模式。各种语言纷纷改头换面，以适应“新时代”的要求：Perl 加上了4P（package 也算一个）；Objective Pascal 摇身一变成了 Boject Pascal，再改名 Delphi；Basic 名字前加上了 Visual，后来后面又加了 .Net；C++ 把 ++ 改成了 # 号；就连一向对面向对象嗤之以鼻的 PHP 都被迫升到了 4.0、5.0；我的“母语”Action Script”版本也升到了2.0、3.0。
在有些人眼中，这是一场“意义重大”的变革；但在我眼中，这是一场灾难。
因为，在某个角落，无类语言们正在为寻找面向对象的数学理论基础而努力。为什么要寻找数学理论基础？这个问题早在70吗=年代就已经不是个问题了，而现在居然还有人不明所以。有类语言和无类语言的区别，就像是命令式与函数式之间的区别，就像是图灵机和 Lambda 演算之间的区别，就是一字一次的编程和面向整体操作的区别，就是 Bug 多和少之间的区别，就是单线程与高效并发之间的区别，就是必将灭亡的旧事物和必将走向辉煌的新事物之间的区别……这么多，还不够吗？
无类语言从已有的 lambda 演算理论中寻找适合解释面向对象思想的部分。1986 年研究完成的 Self 语言首先抛弃了 class 关键字，从对类和对象这两个基本问题上做文章。“万物皆对象”，类就是对象，但用它可以产生对象；怎么产生？通过复制已有对象产生。这种手段称为“基于原型的面向对象程序设计”。Self 之于无类语言，相对于 C++ 之于有类语言。它是无类语言中的蔚然大宗。但可惜的是，Sun 公司的 Self 实现几乎没有进步；Smalltalk 可能因为受够了 Java 之流自称继承了自己，认为 Self 是它唯一的“知心朋友”，发起了一个叫做 Morphic 新体系，算是对经典的延续。
Self 之后，1993年出现了 Lua。Lua 是无类语言的一个特别“函数式”的版本，在继承了 Scheme 所有思想之后，消灭了专有 List 这一数据结构，全以哈希表代之，并出色地解释了许多程序表示上的一些不太明朗的问题，还区分了消息发送和普通函数调用。Lua 不论从那个角度（科学或者商业）来看都是成功的，是无类语言中的佼佼者。
Lua 之后出现了 JavaScript，原名 LiveScript（1995），国际标准收录名为 ECMAScript。JavaScript 与 Java 诞生于同一时代，生不逢时的同时又生而逢时。说它生不逢时，是因为在 Java 的盛名之下，不负众多程序员的“众望”，被他们指责为“假面向对象”；说它生而逢时，是因为，它总算没在一浪高过一浪的 class + 4P 的嚷嚷中倒下，成为我们最为熟知无类语言。它实在是太优秀然而又太谦虚了：它秉承了 Lisp 家族的一贯传统，能够用数据表示程序本身（JSO）；它又有足够的函数式编程特性，但它谦虚地称之为 function；它用复制对象再用 new 关键字 apply 构造函数的方式漂亮地解释了类和对象的关系；相对于 Lua 取消了消息发送和函数调用之间的界限；在没有任何 4P 关键字的情况下还能用逃逸变量理论实现 4P 的所有特性（不要被 dojo 之类的库蒙蔽了双眼）。几乎是一个完美的 Self 的继任者，但还是那句话，真正会 JavaScript 的人不多啊。
至此，无类语言的发展似乎已经很令人满意了，理论似乎已经成熟，只剩下一个问题：函数本身是一个什么样的对象？E 语言（1987，提出很早，实现太晚）回答了这个问题。答案很简单。函数是对象的一种，对象和方法都是 lambda 算子，如果你愿意，又可以把函数的函数体再表示为对象的一个方法！看起来这个答案不那么起眼，但它确实让人们领教了 lambda 演算在抽象层次上的嚣张。同时，E 语言还大胆地加入了对象继承的概念——一个对象可以像类继承一样继承其它对象的属性——因为这仅仅是 lambda 算子的扩展罢了！
但是，无类语言的进步不会就此结束，还有更多、跟有力量的无类语言产生，比如 Scala，一个给无类语言添加了 ML 中的静态多态类型判定和惰性运算的变态……
历史就是这样一个聋子，听不到你的嗟呀。不过，但愿后人会从这些嗟呀中借鉴到很多。

注：还有两个很牛语言没提到：Ruby 和 Python。其中前者学 Smalltalk 学地精神分裂，去掉了 Smalltalk 的强大 IDE 之后居然一炮走红；Python 是个不知道该站在那一边的语言，既没有 3P 又知道逃逸变量或 block 是什么，惨兮兮的。

Haskell：函数 or 数据

2007-06-08T17:55:00.000+08:00

haskell里面是不是所有的函数都是lambda实现的？不然为什么 :t 操作符所返回的都是 lambda的表示,也就是说都是用lambda解释的.
呵呵，最好讲下haskell里的type.和java或c里面的不同.

是。只是语法上不太像。也可以说不是，因为那是lambda的"1.5版"（我的“术语”，Scheme中的是1.0版，学名“一阶lambda演算”） ——Curry化算子。Curry化算子认为，一切都是函数（包括普通数据），但如果这个数据的产生式中每一项都是严格的（比如 num = 4 + 3， 3、4都是可以直接推导而不需要进行惰性化的），那么这个数据可以免除其作为函数的义务。对于产生式中有需要推导的数据，Haskell仍将其表示为普通数据（因为类型可以直接推导来确定。只要产生它的表达式中函数调用存在，那么就会被认作函数；但是它的类型只需要一步即可推导，所以在Haskell中，它“看上去”是普通数据。）。
fact 0 = 1
fact n = n * fact (n-1) -- 这是函数，要推导
num = 5 + fact 4 -- 这个是事实上是函数，但类型上看不出来
另外，之所以haskell中的函数全是lambda的表示，和它的类型系统也有关系。前面说了，Haskell中对函数的理解已经超越了数学映射1.5倍，重点在于对参数列表的理解。数学映射和一阶lambda都认为参数是连续的、一次传递一批，就像Scheme中那样：
(function arg1 arg2)
但Curry化算子认为参数是不连续的、可以分段传递（前提是个数事先固定），每当传递结束而参数不够是，自动转换为一个期待余下参数的函数。这就意味着，如果用Scheme的语法来说明Curry化算子就成了这样：
((+ 1) 2) ;调用一个固定参数个数为两个的函数
这句代码都将行得通！
(map (+ 1) '(1 4 2 5 2))
这对于Scheme来说是非常荒唐的（用宏另当别论），但对于Haskell这是基础：
map (+1) [1, 4, 2, 5, 2]
所以，Haskell的类型系统中对于函数类型的表示才会是那么多个箭头：因为，只要需要推导，就有函数：
Main> :t (+1)
flip (+) 1 :: Num a => a -> a
看出来了吗？不连续的类型导出过程，和java/c等等等等最大的不同点。
至于Haskell类型系统的核心力量——静态多态类型推断，讲起来是在很麻烦。去看中文版的ML语言的书里讲的很详细。

OOP 诡异教程（上）

2007-06-08T17:49:00.000+08:00

本文分上、下两篇，站在一个难以名状的角度上研究了 JavaScript 语言中面向对象机制的起源、内涵和发展，带领读者从原始森林走向高楼大厦。文章作者 lichray 是个 ECMAScript 的狂热追随者，mozilla.org 邮件列表里的无名潜水员。
文章中使用了 Rhino 解释器，行开头有 "js>" 表示那是输入，输入下一行没有这个标记的表示解释器回馈消息。
PS: 读懂本文需要对 JavaScript 闭包和逃逸变量有较深入的了解。

一. 对象和消息
考虑一下我们平常怎么说话的。我们叫某某人做某事，用下面的句式：
forest run!
其中"!"是语气的标志，对于编程语言来说是没有意义的，全部换成"."：
forrest run.
不知道如果我告诉大家上面这句话就是 Smalltalk 语言中一个合法语句大家会怎么想。好了，不谈这个。这样我们就得到了一种语法，"宾"谓结构：
ObjectVerb ::
　　Object Verb.
如果让它支持多个 Verb，比如
forrest run, jump, stop.
可以扩展成这样：
ObjectVerb ::
　　Object VerbList.
VerbList ::
　　Verb
　　Verb , VerbList
很明显，对于 JavaScript 来说，上面的 BNF 不可能和任何一个产生式匹配。问题出在哪儿？我们要帮 JavaScript 指定，谁是 Object，谁是 Verb。鉴于 Object 只有一个，Verb 有多个，我们可以用括号来区分它们，然后把最后那个句号去掉：
ObjectVerb ::
　　Object ( VerbList )
这样上面的那句话就变成了下面的形式：
forrest (run, jump, stop)
很像函数调用，是吧？不过还有一个问题，现在这些 Verb(s) 对于 JavaScript 来说是“裸词”（Perl 语），我们可以避开再去定义这些标识符，用字符串代替；最后再说明一下 Object 是什么：
forrest ('run', 'jump', 'stop')
那么现在我们第一个“模仿”自然语言的程序版本出现了，加上下面针对 JavaScript 的文法：
Object ::
　　Identifier
Verb ::
　　StringLiteral

二. 实现消息传递
有了文法，一切都好办。看得出来，我们下面的工作是定义能创建一个新 Object 的函数，函数中有一些动作，产生的新 Object 是一个能处理这些消息的函数。创建 Forrest Gump 的函数还可以创建 Tom，Mike 等等；他们都是 People：
function People () {
　　function run () {
　　　　print("I'm running!")
　　}
　　function jump () {
　　　　print("I'm jumping!")
　　}
　　function stop () {
　　　　print("I can't stop!")
　　}　　
　　return (function (verb) {
　　　　switch (verb) {
　　　　　　case 'run': run(); break
　　　　　　case 'jump': jump() ;break
　　　　　　case 'stop': stop() ;break
　　　　}
　　})
}
为了简单起见还可以把返回的那个函数写成这样：
　　　　(function (verb) {
　　　　　　eval(verb)();
　　　　}
　　})
Ok。现在我们来试一试这个智商低于 85 的 Forrest Gump 怎么样：
js> forrest = People()
js> forrest('run')
I'm running!
js> forrest('jump')
I'm jumping!
js> forrest('stop')
I can't stop!
事情就是这样。我们成功地创造了对象，还让他做动作、说话。
不过，这个实现并不是我们上文中最后一个文法所指出的。它不支持连续发送指令。改一改。要加入顺序执行指令的办法：
function People () {
　　function run () {
　　　　print("I'm running!")
　　}
　　function jump () {
　　　　print("I'm jumping!")
　　}
　　function stop () {
　　　　print("I can't stop!")
　　}
　　function _do_verbs_ (verblist) {
　　　　for (var i=0; i <> forrest = People()
js> forrest('jump','run','jump','stop')
I'm jumping!
I'm running!
I'm jumping!
I can't stop!

三. 利用消息传递处理状态
什么是状态？我们在进行面向对象编程时，把状态表示为对象的一组数据，我们称之为“属性(property)”。在我们的消息传递编程风格中，可以直接把这些数据堆到产生对象的那个函数中去。下面给 Forrest 加入一个状态，Forrest 口袋里的钱。先得声明原先有多少钱：
forrest = People(1000)
然后，我们希望可以执行这样的代码，让 forrest 支出 200 美元：
forrest('pay', 200)
但很明显，我们无法分清 200 是 Verb 还是 'pay' 所要求的数据。我们只得简化文法，只允许一次发送一个消息，以保全我们的脑细胞：
forrest('pay')(200)
也就是说，我们需要让 forrest('pay') 这一表达式返回一个能改变状态的函数，而不仅仅是调用函数来显示一句话。也就是说，如果我们想让 Forrest 急得跳起来，我们先得跳起来：
forrest('jump')()
新时代的 Forrest 实现如下（省略了一点多余的代码）：
function People (money) {
　　//var money = money
　　function pay (dollars) {
　　　　money -= dollars
　　}
　　function restMoney () {
　　　　return money
　　}
　　function run () {
　　　　print("I'm running!")
　　}
　　return (function (verb) {
　　　　return eval(verb)
　　})
}
试一下。先支出 200 美元，然后看看他还剩多少钱：
js> forrest=People(1000)
js> forrest('restMoney')()
1000
js> forrest('pay')(200)
js> forrest('restMoney')()
800
当然，我们的 Forrest 还可以赚钱。下面这个版本比较彻底地说明了消息传递编程风格的一切。可以直接修改钱之后，我们可以不需要在创建 Object 的时候就说明原有多少钱；当然，使用注释中的版本更自然：
function People (/* money */) {
　　var money = 0; // var money = money ? money : 0;
　　function setMoney (dollars) {
　　　　money = dollars
　　}
　　function addMoney (dollars) {
　　　　money += dollars
　　}
　　function pay (dollars) {
　　　　money -= dollars
　　}
　　function restMoney () {
　　　　return money
　　}
　　return (function (verb) {
　　　　return eval(verb)
　　})
}
试一下吧：
js> forrest = People()
js> forrest('addMoney')(1000)
js> forrest('restMoney')()
1000
js> forrest('pay')(200)
js> forrest('restMoney')()
800
上篇完。小结一下：消息传递的编程风格指的是，把函数 A 的执行上下文当作对象的数据环境，在此定义对象的动词（函数），然后从此上下文中返回一个可以接受、处理消息的函数（常为匿名）。用函数 A 产生消息处理器作为对象，向此对象传递参数作为消息，以此执行函数 A 环境中定义的动作，这些动作还可能改变所在上下文中用一组数据定义的对象状态。

(To be continue)

翻译工作转移阵地

2007-06-01T00:09:00.000+08:00

ECMA-262的翻译工作开始的翻译对实际编程非常重要的东东（第8章之后），需要更多协作，反对我博客变成翻译垃圾堆，所以，今起转移阵地，使用Google文件。
这是 RSS供稿地址。

ECMA-262试译：7.9 Automatic Semicolon Insertion

2007-05-30T22:27:00.001+08:00

7.9 自动分号插入

空语句，变量语句，表达式语句，do-while 语句，continue 语句，break 语句，return 语句，以及 throw 语句，这些确定的 ECMAScript 语句必须以分号结束。这些分号可以总是明确地出现在源代码文本中。为方便起见，在特定的情况下，源代码文本中的这些分号可以被省略。在下面描述的这些情况中，分号被自动插入源代码托肯流。

7.9.1 自动分号插入的规则

从左到右解析程序时，若遇到不被任何产生式允许的托肯（被称为 违规托肯），于是，在下列情况一个或多个为真的违规托肯之前自动插入一个分号：

该违规托肯与前一个托肯之间以至少一个行结束符分隔开。
该违规托肯是 }。

从左到右解析程序时，若遇到输入托肯流的结尾，且解析器无法把此输入的托肯流解析为单个完整的 ECMAScript ，程序，于是在这个输入流的结束处自动插入一个分号。
从左到右解析程序时，若遇到的托肯被一些文法的产生式允许，但该产生式是非严格产生式，且此托肯是终结符或非终结符的第一个托肯，此终结符或非终结符后紧跟着的是非严格产生式中的记法"[no 行结束符 here]"（因此这样的托肯被称为非严格托肯）。当非严格托肯与前一个托肯之间以至少一个行结束符分隔开时，在此非严格托肯前自动插入一个分号。

不过，有一种附加的情况凌驾于优先规则：如果此分号将被解析为空语句，或那个分号将成为一个 for 语句头中的两个分号之一，决不自动插入分号（参见12.6.3）。

NOTE
这些是文法中仅有的非严格产生式。

后缀表达式 :
左侧表达式 [no LineTerminator here] ++
左侧表达式 [no 行结束符 here] --

Continue语句 :
continue [no 行结束符 here] 标识符_opt ;

Break语句 :
break [no 行结束符 here] 标识符_opt ;

Return语句 :
return [no 行结束符 here] 表达式_opt ;

Throw语句 :
throw [no 行结束符 here] 表达式 ;

这些非严格产生式的实际效果如下所示：

若遇到托肯 ++ 或 -- ，解析器将视其为一个后缀运算符时，且在提前托肯与托肯 ++ 或 -- 之间有至少一个行结束符，则在托肯 ++ 或 -- 前自动插入一个分号。
若遇到托肯 continue, break, return, 或 throw，且在下一个托肯之前遇到一个 行结束符，在 continue, break, return, 或 throw 之后自动插入一个分号。

最后给 ECMAScript 程序员一些忠告：

++ 或 -- 应和其操作数出现在同一行。
return 或 throw 语句中的表达式应和托肯 return 或 throw 出现在同一行。
break 或 continue 语句中的标签应和托肯 break 或 continue 出现在同一行。

7.9.2 自动分号插入的例子

源代码

{ 1 2 } 3

即使应用自动分号插入规则，它也不是 ECMAScript 文法中的合法句子。作为对比，源代码

{ 1 2 } 3

同样不是 ECMAScript 中的合法句子，却会被自动分号插入变形为下面的形式：

{ 1 ;2 ;} 3;

这就是一个回复的 ECMAScript 句子了。

源代码

for (a; b )

不是合法的 ECMAScript 句子，且因 for 语句头需要分号，句子无法被自动分号插入调整。自动分号插入决不插入 for 语句头中的两个分号之一。

源代码

return a + b

被自动分号插入变形为下面的形式：

return; a + b;
NOTE
这里的表达式 a + b 不被作为 return 语句的值返回，因为'行结束符'把它和托肯 return 分隔开了。

源代码

a = b ++c

被自动分号插入变形为下面的形式：

a = b; ++c; NOTE
这里的托肯 ++ 不被视为应用于变量 b 的后缀运算符，因为在 b 和 ++ 之间存在一个'行结束符'。

源代码

if (a > b) else c = d

不是合法的 ECMAScript 句子，且即使没有文法产生式引用于此，在 else 托肯之前的句子无法被自动分号插入调整，因为被自动插入的分号将被解析为一个空语句。

源代码

a = b + c (d + e).print()

不被自动分号插入变形，因为第二行开始的括号表达式可以解释为函数调用的参数列表：

a = b +c(d + e).print()

在这种状况下，赋值表达式必须以一个左括号为开始。在提前的语句结尾处提供一个清晰的分号而不依赖于自动分号插入，对于程序员来说是个好想法。

//这一篇好像很有用的样子~~

ECMA-262试译：7.9 Automatic Semicolon Insertion

2007-05-30T22:27:00.000+08:00

7.9 自动分号插入

空语句，变量语句，表达式语句，do-while 语句，continue statement，break 语句，return 语句，以及 throw 语句，这些确定的 ECMAScript 语句必须以分号结束。这些分号可以总是明确地出现在源代码文本中。为方便起见，在特定的情况下，源代码文本中的这些分号可以被省略。在下面描述的这些情况中，分号被自动插入源代码托肯流。

7.9.1 自动分号插入的规则

从左到右解析程序时，若遇到不被任何产生式允许的托肯（被称为 违规托肯），于是，在下列情况一个或多个为真的违规托肯之前自动插入一个分号：

该违规托肯与前一个托肯之间以至少一个行结束符分隔开。
该违规托肯是 }。

从左到右解析程序时，若遇到输入托肯流的结尾，且解析器无法把此输入的托肯流解析为单个完整的 ECMAScript ，程序，于是在这个输入流的结束处自动插入一个分号。
从左到右解析程序时，若遇到的托肯被一些文法的产生式允许，但该产生式是非严格产生式，且此托肯是终结符或非终结符的第一个托肯，此终结符或非终结符后紧跟着的是非严格产生式中的记法"[no 行结束符 here]"（因此这样的托肯被称为非严格托肯）。当非严格托肯与前一个托肯之间以至少一个行结束符分隔开时，在此非严格托肯前自动插入一个分号。

NOTE
这些是文法中仅有的非严格产生式。

后缀表达式 :
左侧表达式 [no LineTerminator here] ++
左侧表达式 [no 行结束符 here] --

Continue语句 :
continue [no 行结束符 here] 标识符_opt ;

Break语句 :
break [no 行结束符 here] 标识符_opt ;

Return语句 :
return [no 行结束符 here] 表达式_opt ;

Throw语句 :
throw [no 行结束符 here] 表达式 ;

这些非严格产生式的实际效果如下所示：

若遇到托肯 ++ 或 -- ，解析器将视其为一个后缀运算符时，且在提前托肯与托肯 ++ 或 -- 之间有至少一个行结束符，则在托肯 ++ 或 -- 前自动插入一个分号。
若遇到托肯 continue, break, return, 或 throw，且在下一个托肯之前遇到一个 行结束符，在 continue, break, return, 或 throw 之后自动插入一个分号。

最后给 ECMAScript 程序员一些忠告：

++ 或 -- 应和其操作数出现在同一行。
return 或 throw 语句中的表达式应和托肯 return 或 throw 出现在同一行。
break 或 continue 语句中的标签应和托肯 break 或 continue 出现在同一行。

7.9.2 自动分号插入的例子

源代码

{ 1 2 } 3

即使应用自动分号插入规则，它也不是 ECMAScript 文法中的合法句子。作为对比，源代码

{ 1 2 } 3

同样不是 ECMAScript 中的合法句子，却会被自动分号插入变形为下面的形式：

{ 1 ;2 ;} 3;

这就是一个回复的 ECMAScript 句子了。

源代码

for (a; b )

不是合法的 ECMAScript 句子，且因 for 语句头需要分号，句子无法被自动分号插入调整。自动分号插入决不插入 for 语句头中的两个分号之一。

源代码

return a + b

被自动分号插入变形为下面的形式：

return; a + b;
NOTE
这里的表达式 a + b 不被作为 return 语句的值返回，因为'行结束符'把它和托肯 return 分隔开了。

源代码

a = b ++c

被自动分号插入变形为下面的形式：

a = b; ++c; NOTE
这里的托肯 ++ 不被视为应用于变量 b 的后缀运算符，因为在 b 和 ++ 之间存在一个'行结束符'。

源代码

if (a > b) else c = d

源代码

a = b + c (d + e).print()

不被自动分号插入变形，因为第二行开始的括号表达式可以解释为函数调用的参数列表：

a = b +c(d + e).print()

//这一篇好像很有用的样子~~

ECMA-262试译：7.8 Literals（下）

2007-05-29T22:31:00.000+08:00

语义

数值常量代表数值类型的值。用两个步骤来确定这个值：首先，从常量中获得数学值；然后，用下面所描述的方式舍入这个数学值。

数值常量的MV :: 十进制常量的MV 是 十进制常量的MV。
数值常量的MV :: 十六进制整数常量的MV 是 十六进制整数常量的MV。
十进制常量的MV :: 十进制整数常量 . 是 十进制整数常量的MV。
十进制常量的MV :: 十进制整数常量 . 十进制数 是 十进制整数常量的MV 加 ( 十进制数的MV 乘以 10 ^-n ), 这里的 n 是 十进制数中的字符数。
十进制常量的MV :: 十进制整数常量 . 指数部分 是 十进制整数常量的MV 乘以 10 ^e的MV ,这里的 e的MV 是 指数部分的MV。
十进制常量的MV :: 十进制整数常量 . 十进制数指数部分 是 ( 十进制整数常量的MV 加 ( 十进制数的MV 乘以 10^-n )) 乘以 10^e, 这里的 n 是 十进制数中的字符数和 e的MV 是 指数部分的MV。
十进制常量的MV ::. 十进制数 是 十进制数的MV 乘以 10^-n, 这里的 n 是 十进制数中的字符数。
十进制常量的MV :: . 十进制数指数部分的MV 是 十进制数的MV 乘以 10^e-n,这里的 n 是 十进制数中的字符数且 e 是 指数部分的MV。
十进制常量的MV :: 十进制整数常量 是 十进制整数常量的MV。
十进制常量的MV :: 十进制整数常量指数部分 是 十进制整数常量的MV 乘以 10^e的MV, 这里的 e 是 指数部分的MV。
十进制整数常量的MV :: 0 是 0。
十进制整数常量的MV :: 非零数字十进制数 是 ( 非零数字的MV 乘以 10^n的MV ) 加 十进制数的MV, 这里的 n 是 十进制数中的字符数。
十进制数的MV :: 十进制数字 是 十进制数字的MV.
十进制数的MV :: 十进制数十进制数字 是 ( 十进制数的MV 乘以 10) 加 十进制数字的MV。
指数部分的MV :: 指数指示符有符号整数 是 有符号整数的MV。
有符号整数的MV :: 十进制数 是 十进制数的MV.
有符号整数的MV :: + 十进制数 是 十进制数的MV.
有符号整数的MV :: - 十进制数的MV 是 十进制数的负MV.
十进制数字的MV :: 0 or of 十六进制数字 :: 0 是 0.
十进制数字的MV :: 1 or of 非零数字 :: 1 or of 十六进制数字 :: 1 是 1. 十进制数字的MV :: 2 or of 非零数字 :: 2 or of 十六进制数字 :: 2 是 2.
十进制数字的MV :: 3 or of 非零数字 :: 3 or of 十六进制数字 :: 3 是 3.
十进制数字的MV :: 4 or of 非零数字 :: 4 or of 十六进制数字 :: 4 是 4.
十进制数字的MV :: 5 or of 非零数字 :: 5 or of 十六进制数字 :: 5 是 5. 十进制数字的MV :: 6 or of 非零数字 :: 6 or of 十六进制数字 :: 6 是 6.
十进制数字的MV :: 7 or of 非零数字 :: 7 or of 十六进制数字 :: 7 是 7.
十进制数字的MV :: 8 or of 非零数字 :: 8 or of 十六进制数字 :: 8 是 8.
十进制数字的MV :: 9 or of 非零数字 :: 9 or of 十六进制数字 :: 9 是 9. 十六进制数字的MV :: a or of 十六进制数字 :: A 是 10.
十六进制数字的MV :: b or of 十六进制数字 :: B 是 11.
十六进制数字的MV :: c or of 十六进制数字 :: C 是 12.
十六进制数字的MV :: d or of 十六进制数字 :: D 是 13.
十六进制数字的MV :: e or of 十六进制数字 :: E 是 14.
十六进制数字的MV :: f or of 十六进制数字 :: F 是 15.
十六进制整数常量的MV :: 0x 十六进制数字 是 十六进制数字的MV。
十六进制整数常量的MV :: 0X 十六进制数字十六进制数字的MV。
十六进制整数常量的MV :: 十六进制整数常量十六进制数字 是 ( 十六进制整数常量的MV 乘以 16) 加 十六进制数字的MV。

一旦数值常量的 MV 被精确地确定，接下来就会被舍入为数值类型的一个值。如果 MV 是0，那么舍入值为 +0；否则，舍入值必须正是 MV 的值（在8.5中定义），除非该常量是一个有效数字超过20位的十进制常量——在这种情况下，此数字的值是下面两种之一：一是将其20位之后的每个有效数字用0替换，产生此常量的 MV；二是将其20位之后的每个有效数字用0替换，并在20位有效数字之后增加数字位，产生此常量的 MV 值。判断一个数字是否为有效数字，首先它不能是指数部分的一部分，且

它不是0；或
它的左边是一个非零值，右边是一个不在指数部分中的非零值。

7.8.4 字符串常量

字符串常量是被单引号或双引号括起的零个或多个字符。每个字符都可以呈现为转义序列。

语法

字符串常量 :: " 双字符串字符集_opt " ' 单字符串字符s_opt '

双字符串字符集 :: 双字符串字符双字符串字符集_opt

单字符串字符s :: 单字符串字符单字符串字符s_opt

双字符串字符 :: 源代码字符 but not 双引号 " or 反斜杠 \ or 行结束符
\ 转义序列

单字符串字符 :: 源代码字符 but not 单引号 ' or 反斜杠 \ or 行结束符
\ 转义序列

转义序列 :: 字符转义序列
0 [lookahead ? 十进制数字]
十六进制转义序列
Unicode转义序列

字符转义序列 :: 单个转义字符
非转义字符

单个转义字符 :: one of ' " \ b f n r t v

非转义字符 :: 源代码字符 but not 转义字符 or 行结束符

转义字符 :: 单个转义字符
十进制数字
x u

十六进制转义序列 :: x 十六进制数字十六进制数字

Unicode转义序列 :: u 十六进制数字十六进制数字十六进制数字十六进制数字

非终止十六进制数字的定义在7.8.3节中给出。源代码字符的描述在章节2、6中。

字符串常量代表字符串类型的值。该常量的字符串值(SV)的描述，取决于字符串常量各个部分提供的字符值(CV)。作为此过程的一部分，一些字符串常量中的字符被解释为拥有数学值(MV)，正如下文和章节7.8.3中所描述的。

字符串常量的SV :: "" 是空字符序列
字符串常量的SV :: '' 是空字符序列
字符串常量的SV :: " 双字符串字符集 " 是 the SV of 双字符串字符集.
字符串常量的SV :: ' 单字符串字符s ' 是 单字符串字符s的SV.
双字符串字符集的SV :: 双字符串字符 是一个字符的序列,双字符串字符的SV.
双字符串字符集的SV :: 双字符串字符双字符串字符集 是 双字符串字符的SV 的序列后跟所有双字符串字符集的SV 中的有序字符
单字符串字符集的SV :: 单字符串字符 是一个字符的序列, 单字符串字符的SV.
单字符串字符s :: 单字符串字符单字符串字符s 是 单字符串字符后跟所有单字符串字符集的SV 中的有序字符
双字符串字符 :: 源代码字符 but not 双引号 " or 反斜杠 \ or 行结束符 是 the 源代码字符 字符本身。
双字符串字符 :: \ 转义序列 是 转义序列. 单字符串字符 :: 源代码字符 but not 单引号 ' or 反斜杠 \ or 行结束符 是 源代码字符 字符本身。
单字符串字符 :: \ 转义序列 是 转义序列.
转义序列 :: 字符转义序列 是 the 字符转义序列.
转义序列 :: 0 [lookahead ? 十进制数字] 是 a 字符 (Unicode 值 0000).
转义序列 :: 十六进制转义序列 是 十六进制转义序列.
转义序列 :: Unicode转义序列 是 Unicode转义序列.
字符转义序列 :: 单个转义字符 是由单个转义字符根据下表确定的代码点值的字符:

//此处表格不发，blogger支持不好。

字符转义序列 :: 非转义字符 是 the 非转义字符.
非转义字符 :: 源代码字符 but not 转义字符 or 行结束符 是 the 源代码字符 字符本身。
十六进制转义序列 :: x 十六进制数字十六进制数字 是以 (第一个十六进制数字的 MV 值的16倍) 加 (第二个 十六进制数字的 MV 值) 为代码点值的字符。
Unicode转义序列 :: u 十六进制数字十六进制数字十六进制数字十六进制数字 是以 (第一个 十六进制数字)的 MV 的 (4096 (即, 16³ )倍) 加 (第二个 十六进制数字)的 MV 的(256 (即 , 16² )倍) 加 (第三个 十六进制数字的 16 倍) 加 (第四个 十六进制数字的 MV) 为代码点值的字符。

NOTE
“行结束”字符不能出现在字符串常量中，即使在它前面有一个反斜杠 \。使行结束字符成为字符串常量的值一部分的正确方法是，使用转义序列，如 \n 或 \u000A。

7.8.5 正则表达式常量

正则表达式常量被扫描后，转换为 RegExp 对象的输入元素（章节15.10）。此对象在包含它的程序或函数开始求值之前被创建。求值此常量产生一个到那个对象的引用；这不产生新对象。决不能用 === 比较被程序求值为正则表达式对象的两个正则表达式常量，即使两个常量内容相同。在运行时创建RegExp 对象，可以用 new RegExp （章节15.10.4），或者以函数的方式调用 RegExp 构造函数（章节15.10.3）。

下面的产生式描述了正则表达式常量的语法，以及输入元素扫描器查找正则表达式常量结尾的方法。给正则表达式构造函数传递包含正则表达式体和正则表达式徽标的、不被解释的字符串，将以更严厉的文法，根据它们自己解释它们。实现可以扩展正则表达式构造函数的文法，但不应扩展正则表达式体和正则表达式徽标的产生式，以及被它们使用的产生式。

语法

正则表达式常量 :: / 正则表达式体 / 正则表达式徽标

正则表达式体 :: 正则表达式首字符正则表达式字符集

正则表达式字符集 :: [empty]
正则表达式字符集正则表达式字符

正则表达式首字符 :: 非结束符 but not * or \ or /
反斜杠序列

正则表达式字符 :: 非结束符 but not \ or /
反斜杠序列

反斜杠序列 :: \ 非结束符

非结束符 :: 源代码字符 but not 行结束符

正则表达式徽标 :: [empty]
正则表达式徽标标识部分

NOTE
正则表达式常量不可为空；// 开始一个单行注释而非表示空正则表达式。描述空正则表达式，使用 /(?:)/。

语义

正则表达式常量代表一个 Object 类型的值。确定该值要两个步骤：首先，包含和的产生式延伸的字符，只收集、不解释地转为两个字符串，分别为 Pattern 和 Flags。然后，用参数 Pattern 和 Flags 两个参数调用 new RegExp 构造函数，结果是 正则表达式常量 的值。如果调用 new RegExp 产生了错误，可能的实现是，作为其判断力，在扫描程序时立即报错，或推迟报错，直到该正则表达式常量在出现执行的轨迹中被求值。

ECMA-262试译：7.8 Literals（上）

2007-05-28T22:54:00.000+08:00

7.8 常量

语法

常量 ::
空值常量
布尔值常量
数值常量
字符串常量
正则表达式常量①

7.8.1 空值常量

语法

空值常量 ::
null

语义

空值常量 null 的值是空类型唯一的值，也就是 null。

7.8.3 布尔值常量

语法

布尔值常量 ::
true false

语义

布尔值常量值 true 是布尔值类型的值，也就是 true。

布尔值常量值 false 是布尔值类型的值，也就是 false。

7.8.3 数值常量

语法

数值常量 ::
十进制常量
十六进制整数常量

十进制常量 ::
十进制整数常量 . 十进制数_opt 指数部分_opt
. 十进制数 指数部分_opt
十进制整数常量 指数部分_opt

十进制整数常量 ::
0
非零数字十进制数_opt

十进制数 ::
十进制数字
十进制数 十进制数字

十进制数字 :: one of
0 1 2 3 4 5 6 7 8 9

非零数字 :: one of
1 2 3 4 5 6 7 8 9

指数部分 ::
指数指示符有符号整数

指数指示符 :: one of
e E

有符号整数 ::
十进制数 + 十进制数
- 十进制数

十六进制整数常量 ::
0x 十六进制数字0X 十六进制数字
十六进制整数常量十六进制数字

紧跟在数值常量后的源代码字符既不是标识符开始也不是十进制数。

NOTE
例如： 3in
不是两个输入元素3和 in，而是一个错误。

①原书此处无此句，有误。

//7.7节没有话，就不放在这儿了
//前文所有的文法、注释格式都已经过调整
//下面要翻文字有大量重复单词，准备采取自动化翻译手段

ECMA-262试译：7.6 Identifiers

2007-05-28T18:36:00.000+08:00

7.6 标识符

描述

解释标识符的文法根据在章节5.16中给出，对于 Unicode 标准的升级版3.0有一些小更正。此文法同时基于 Unicode 标准所具体指明的常规及非常规字符类别。在 Unicode 标准2.1版中具体指明的类别中的字符，必须被所有符合标准的 ECMAScript 实现认作是其它类别中的字符；不过，符合标准的 ECMAScript 实现可以允许附加那些基于 Unicode 早期版本中的类别分配的、合法的标识符字符集。

本标准具体指明了一个背离给定的 Unicode 标准的文法：允许美元号($)和下划线 (_)出现在标识符的任何位置。美元号仅应在机械生成的代码中使用。

标识符中同样允许有 Unicode 转义序列，它们在此处给标识符提供单个字符，由 Unicode转义序列的 CV 算法计算（参见7.8.4）。在 Unicode转义序列之前提前出现的 \ 不为标识符提供字符。Unicode转义序列不能被用于向标识符中放置一个字符，否则是违法的。换句话说，如果 \ Unicode 转义序列的序列被它的Unicode转义序列的 CV 替换，结果必定仍是合法的标识符，与原始的标识符有完全相同的字符序列。

根据 Unicode 标准来判断两个标识符不相等时，不考虑它们是否被呈现为完全相同的代码点序列（换句话说，仅要求符合标准的 ECMAScript 实现对标识符作以比特为单位的比较）。这意味着，所得到的源代码文本在到达编译器之前就已经被转化成常规的形式 C。

语法
标识符 ::
标识符名 but not保留字
标识符名 ::
标识符开始
标识符名标识符体
标识符开始 ::
Unicode字母
$ _
\Unicode转义序列
标识符体 ::
标识符开始
Unicode联合标记
Unicode数字
Unicode连接标点符号
\Unicode转义序列
Unicode字母
以下 Unicode 分类中的任何字符： "Uppercase letter(Lu，大写字母)", "Lower caseletter(Ll，小写字母)", "Titlecase letter(Lt，标题字母)", "Modifier letter (Lm，修饰字母)","Other etter(Lo，其它字母)", 或 "Letter number(Nl，字母数字)"。
Unicode联合标记
以下 Unicode 分类中的任何字符： "Non-spacing mark(Mn，非空格标记)" 或 "Combining spacing mark(Mc，联合空格标记)"。
Unicode数字
以下 Unicode 分类中的任何字符："Decimal number(Nd，十进制数)"。
Unicode连接标点符号
以下 Unicode 分类中的任何字符："Connector punctuation (Pc，连接标点符号)"。
Unicode转义序列
参见7.8.4
十六进制数字:: one of
0 1 2 3 4 5 6 7 8 9 a b c d e f A B C D E F

ECMA-262试译：7.5 Tokens

2007-05-27T22:36:00.000+08:00

7.5 托肯

语法
托肯 ::

保留字
标识符
标点符号
数字常量
字符串常量

7.5.1 保留字

描述

保留字不能被用作标识符。

语法
保留字 ::

关键字
未来保留字
空值常量
布尔值常量

7.5.2 关键字

下列托肯是 ECMAScript 关键字，且不能被用作 ECMAScript 程序中的标识符。

语法
关键字 :: one of

break else new var case finally return void catch for switch while continue function this with default if throw delete in try do instanceof typeof

7.5.3 未来保留字

下面的单词被用作将来可能出现的扩展的关键字，因此，为了让它们被将来采用的这些扩展所允许，它们被保留。

语法
未来保留字 :: one of

abstract enum int short boolean export interface static byte extends long super char final native synchronized class float package throws const goto private transient debugger implements protected volatile double import public

ECMA-262试译：7.4 Comments

2007-05-27T22:32:00.000+08:00

7.4 注释

描述

注释可以是单行或多行的。多行注释不能自包含。

由于单行注释可以包含除行结束符之外的任何字符①。根据常规，托肯总是进行最长匹配，所以单行注释总是由从 // 开始到行末结束的所有字符组成。不过，行尾的行结束符不被识别为单行注释的一部分；它被词法文法识别为分隔符，并成为给语法文法提供的输入元素流的一部分。这一点非常重要，因为这意味着单行注释的存在与否对自动分号插入的过程没有影响。

除非多行注释中包含有一个行结束字符，导致整个注释被语法文法解析为一个行结束符，否则抛弃注释，行为类似空白字符。

语法

注释::
多行注释
单行注释

多行注释:: /*多行注释字符集_opt */

多行注释字符集::
多行注释非星号字符多行注释字符集_opt * 后置星号注释字符_opt

后置星号注释字符::
多行非正斜杠或星号字符 多行注释字符集_opt * 后星号注释字符_opt

多行非星号字符::
源代码字符 but not 星号 *

多行非正斜杠或星号字符::
源代码字符 but not 正斜杠 /or 星号*

单行注释:: // 单行注释字符集_opt

单行注释字符集::
单行注释字符 单行注释字符集_opt

单行注释字符::
源代码字符 but not 行结束符

①此句有歧义，正确意思是"单行注释直到行末"。

ECMA-262试译：7.3 Line Terminators

2007-05-27T16:07:00.000+08:00

7.3 行结束符

与空白字符类似，行结束字符被用于提升源代码文本的可读性，以及把托肯（不可分割的词法单元）互相分隔开来。不过，与空白字符不同的
是，行结束符对语法文法的行为有影响。一般说来，行结束符可以出现在两个托肯之间，不过有少数地方，语法文法禁止它的出现。行结束符不能出现在任何托肯之
间，即使是字符串也不行。行结束符还对自动分号插入过程有影响。

下面的字符被认为是行结束符：

代码点值	名称	正式名称
`\u000A`	换行	<LF>
`\u000D`	行末	<CR>
`\u2028`	行分隔符	<LS>
`\u2029`	段落分隔符	<PS>

语法

行结束符 ::

<LF>
<CR>
<LS>
<PS>

//原文件地址

ECMA-262试译：7.2 White Space

2007-05-27T15:38:00.000+08:00

7.2 White Space

空白字符被用于提升源代码文本的可读性，以及把托肯（不可分割的词法单元）互相分隔开来，在其它方面是无关紧要的。空白字符允许出现在两个托肯之间，也允许出现在字符串中（在这个地方，它们会被看成是有意义的字符，成为字符串常量的一部分）。但空白字符不能出现在其它任何托肯之间。

下面的字符被认为是空白字符：

代码点值	名称	正式名称
\u0009	制表符	<TAB>
\u000B	垂直制表符	<VT>
\u000B	表单结束符	<FF>
\u0020	空格	<SP>
\u00A0	非阻断空格	<NBSP>
其它类别"Zs"	其它任何Unicode“空白分隔符”	<USP>

语法
空白字符 ::

//原文地址

ECMA-262试译：7.1 Unicode Format-Control Characters

2007-05-27T09:00:00.000+08:00

7.1 Unicode 格式控制字符

Unicode 格式控制字符（Unicode 字符数据库"Cf"分类，比如 LEFT-TO-RIGHT 标记、RIGHT-TO-LEFT 标记）被用于控制范围内的文本格式化，以使文本被相对于此的高阶协议（如标记语言）忽略。在源代码文本中允许出现这些字符也是有用的，便于查看和编辑。

格式控制字符可以在 ECMAScript 程序的任何位置出现。这些字符将在应用词法文法之前从源代码文本中被移除。因为这些字符将在处理字符串常量和正则表达式常量之前被移除，所以必须使用 Unicode 转义序列(7.6)，以使字符串和正则表达式常量中包含 Unicode 格式控制字符。

ECMA-262试译：7 Lexical Conventions

2007-05-26T23:28:00.000+08:00

7 词法约定

ECMAScript 程序的源代码文本首先被转换为一个输入元素的序列，其中的每一项是托肯、行结束符、注释或空白中的一个。源代码文本被从左到右扫描，重复地把最长的可能的字符序列作为下一个输入元素。

词法文法中有两个目标符。符号输入分隔元素在其它语法文法中上下文中可以是一个除号(/) 或除法赋值(/=)运算符。符号输入元素正则表达式在其它语法文法上下文中使用。

需要注意的是，除号和正则表达式常量存在于语法文法中的上下文中，且都被语法文法允许；不论如何，在斜线号不被识别为正则表达式常量的开始这一情况下，词法文法使用输入分隔元素目标符。为了使它能在任何情况下正常工作，可以把正则表达式常量用括号括起。

语法
输入分隔元素 ::

空白
行结束符
注释
托肯
分隔符

输入元素正则表达式 ::

空白
行结束符
注释
托肯
正则表达式常量

ECMA-262试译：6 Source Text

2007-05-26T22:23:00.000+08:00

6 源代码文本

ECMAScript 源代码文本被表示为一个 Unicode 编码的字符序列，Unicode 版本2.1或更新，使用 UTF-16 转换格式。我们期望文本已被 Unicode 规范化形式 C(canonical composition)规范化，Unicode 技术报告 #15中描述了它。合乎标准的 ECMAScript 实现不要求展示任何文本的规范化形式，做出它们展示规范化文本的行为，只需展示文本自身。

源文件字符 ::

任何 Unicode 字符

ECMAScript 源文件文本可以包含任何 Unicode 字符。所有的 Unicode 空白字符都被视为空格，所有 Unicode 行、段分隔符都被视为行分隔符。Unicode 非拉丁文字符允许出现在标识符，字符串常量，正则表达式常量和注释中。

贯穿此文档的剩余部分，短语"代码点"和单词"字符"将被用于代指16位无符号值，用来呈现单个 UTF-16的16位单元。短语"Unicode 字符"将被用于代指抽象语言学或排版单元，呈现为单个 Unicode 标量值（可能长于16位，将被呈现为多于一个的代码点）。这儿仅代指单个以 Unicode 标量值形式呈现的实体：组合字符得到的字符序列仍是独立的“Unicode 字符”，即使用户认为整个序列是单个字符。

在字符串常量、正则表达式常量和标识符中，任何字符（代码点）也可以被表示为一个由六个字符组成的 Unicode 转义序列，形式为 \u 加上四个十六进制数字。事实上，在注释中，这样的转义序列被当作注释的一部分忽略掉。在字符串常量或正则表达式常量中，Unicode 转义序列向常量的值提供一个字符。在标识符中，转义序列给标识符提供一个字符。

NOTE 1
虽然这篇文档常常提到在“字符串”中的“字符”和16位无符号整数（该字符的 UTF-16 编码）之间的“转换”，但事实上，这种转换是不存在的，因为“字符串& rdquo;中的“字符”其实正是用那个16位无符号整数表示的。
NOTE 2
在对待 Unicode 转义序列的行为方面，ECMAScript 语言与 Java 语言不同。例如，在 Java 程序中，Unicode 转义序列 \u000A 在单行注释中出现，它将被解释为一个行结束符（Unicode 字符000A代表换行），因此下一个字符不再是注释的一部分。类似地，如果在 Java 程序中，Unicode 转义序列 \u000A 出现在字符串常量中，将被同样解释为一个行结束符，所以它不能允许出现在字符串常量中——要把换行作为字符串常量的值的一部分，必须写成 \n 而不是 \u000A。在 ECMAScript 程序中，在注释中出现的 Unicode 转义序列决不会被解释，因此不能使注释结束。类似地，在 ECMAScript 程序中，在字符串常量中出现的 Unicode 转义序列总是为字符串常量的值提供字符，而决不会被解释成行结束符或引号，这使 Unicode 转义序列不可能结束一个字符串常量。

ECMA-262试译：5.2 Algorithm

2007-05-26T19:55:00.000+08:00

5.2 算法约定

本规范中常会用到一种标有数字序号的列表来详细指明一个算法的步骤。这些算法是用来说明语义的。实际操作中，具体实现可能会对给定的特性给出更有效率的算法。

若算法要产生一个值作为结果，使用说明"返回 x"来指明算法的结果是 x 的值，此时算法结束。记法 Result(n) 被用作"第n步的结果" 的缩写。Type(x) 被用作"x的类型"的缩写。

加法、减法、取负、乘法、除法这些数学运算，以及这一节稍后定义的数学函数应被理解为总是使用实数做精确的数学计算，这不包括无穷大或负零。本标准中的算法在适当的地方会建模浮点数运算，描述其步骤，处理无穷大和有符号零并进行舍入。如果数学运算或函数应用于一个浮点数，应被理解为应用于此浮点数所代表的精确的数学值；比如，浮点数必须是有限的，若为+0或-0则简单地取与之相符的数学值0。

数学函数 abs(x) 返回 x 的绝对值，即如果 x 为负（小于零）则是 -x，否则是 x 本身。

若为 x 正，数学函数 sign(x) 返回1；为负则返回-1。在本标准中，对于 x 为零的情况，不使用函数 sign。

记法"x modulo y"（y 必须为有限的非零值）计算 k 值，它与 y 同号（或同为零），使得 abs(k) < y) 且对于同样的整数 q 有 x-k = q × y。

数学函数 floor(x) 返回不大于 x 的最大的整数（可接近正无穷）。

NOTE
floor(x) = x-(x modilo 1).
若定义一个"抛出异常"的算法，执行此算法结束后没有返回结果。调用这个算法，直到算法步骤到达了明确地处理这个异常的时候，此过程也会结束，处理异常的术语有"如果一个异常被抛出..."。一旦某个算法步骤遭遇异常，就不再认为此异常发生过。

ECMA-262试译：5.1 Syntatic and Lexical Grammars（下）

2007-05-26T17:20:00.000+08:00

5.1.5 文法记法

词法和字符串文法的终结符，以及有些语法文法的终结符，将以等宽(fixed width)字体显示在文法的产生式中，贯穿本规范中该文本被直接引用为一个终结符的全过程。它们可出现在写成的程序中。所有的非终结字符以这种特定的方式，作为恰当的、ASCII 范围内的 Unicode 字符被识别，以区别其它 Unicode 范围内看上去相似的 Unicode 字符。

非终结符以斜体(italic)显示。非终结符的定义由其被定义的名字后跟一个或更多冒号引入（冒号的数量指出产生式所属的文法）。非终结符中一个或多个可变的右式紧跟在下一行。例如，文法语法的定义：

With语句 :

with ( 表达式 ) 语句

这说明非终结符With语句表示 with 托肯，后跟一个左括号托肯，再跟随一个表达式，其后是一个右括号托肯，再后面是一个语句。出现的表达式和语句它们自身都是非终结符。作为另一个例子，有文法定义：

参数列表 :

赋值表达式
参数列表 , 赋值表达式

这说明一个参数列表可以表现为单个赋值表达式，或一个参数列表后跟一个逗号，再跟一个赋值表达式。参数列表的定义是递归的(recursive)，也就是说，它的定义中借用了它本身。结果是参数列表可以包含任意数量为正的参数，以逗号隔开，每个参数表达式都是一个赋值表达式。像这样的非终结符的递归定义很常见。

出现在终结符或非终结符后面的下标后缀"opt"，指出这是一个可选符号(optional symbol)。包含可选符号的可变部分其实可以细分为两个右式，其一忽略可选元素，而另一个包括它。这意味着：

变量声明 :

标识符 初始化器opt

是下述产生式的简略形式：

变量声明 :

标识符
标识符 初始化器

再如：

迭代语句 :

for ( 入口表达式opt ; 表达式opt ; 表达式opt) 语句

是下述产生式的简略形式：

迭代语句 :

for ( ; 表达式opt ; 表达式opt)
for ( 入口表达式 ; 表达式opt ; 表达式opt) 语句

它是由下面的产生式的简略形式转变得到的：

迭代语句 :

for ( ; ; 表达式opt) 语句
for ( ; 表达式 ; 表达式opt) 语句
for ( 入口表达式 ; ; 表达式opt) 语句
for ( 入口表达式 ; 表达式 ; 表达式opt) 语句

它是由下面的产生式的简略形式转变得到的：

迭代语句 :

for ( ; ; ) 语句
for ( ; ; 表达式 ) 语句
for ( ; 表达式 ; ) 语句
for ( ; 表达式 ; 表达式 ) 语句
for ( 入口表达式 ; ; ) 语句
for ( 入口表达式 ; ; 表达式 ) 语句
for ( 入口表达式 ; 表达式 ; ) 语句
for ( 入口表达式 ; 表达式 ; 表达式 ) 语句

所以说，迭代语句其实有八个可变右式。

如果产生式右式出现了短语"[lookahead ∉ set]"，指的是如果紧接着的输入终结符不是所给集合 set 的成员，则不使用此产生式。集合 set 可以被写成克里闭包中的非闭合终结符组成的列表。为方便起见，这个集合也可写成一个非终结符，这使它代表除去此非终结符的所有终结符构成的集合。例如，给出下列定义：

十进制数字 :: one of

0 1 2 3 4 5 6 7 8 9

十进制数 ::

十进制数字
十进制数 十进制数字

定义

Lookahead示例 ::

n [lookahead ∉ {1,3,5,7,9}] 十进制数
十进制数字 [lookahead ∉ 十进制数]

当字母 n 后跟一个或多个首位是偶数的十进制数，或后跟一个后面没有另一个十进制数字的数字时，完成匹配。

如果语法文法的产生式右式出现了短语"[no LineTerminator here]"，它指出了该产生式是一个受约束产生式(restricted production)：如果行结束符出现在输入流的指定位置上，这个产生式不被使用。例如，下面的产生式：

返回语句 :

return [no LineTerminator here] 表达式opt ;

这里指出了，如果在 return 托肯和 表达式 之间出现了行结束符，则不使用此产生式。

直到出现的行结束符被受限产生式禁止之前，在输入的元素流中，行结束符允许在两个连续托肯之间出现任意次数但对程序的语法可接受性没有影响。

如果在语法定义的冒号之后出现了单词"one of"，它表示随后的行中的所有终结符被当作一个可变定义。例如，在 ECMAScript 的词法文法中包含下面的产生式：

非零数字 :: one of

1 2 3 4 5 6 7 8 9

这只不过是下面的产生式的简略形式：

非零数字 ::①

1
2
3
4
5
6
7
8
9

当词法文法或数字化字符串文法的产生式可变部分中出现了多字符托肯，表示这个字符序列构成一个托肯。

使用短语"but not"可具体指明产生式的某些特定扩充是不允许的，这样可以把指定的扩充排除在外。例如，下面的产生式：

标识符 ::

标识符名 but not 保留字

意思是，非终结符标识符可以被任意可以替换标识符名的字符序列替换，同一序列不能被保留字替换。

最后，对于实际上不可能列出全部可变元的少量非终结符，我们用普通字体写出描述性的短语来描述它们：

源文件字符 ::

任何 Unicode 字符

①原书此处有 one of，错误。

ECMA-262试译：5.1 Syntatic and Lexical Grammars（上）

2007-05-26T13:41:00.000+08:00

5.1 语法和词法文法

这一节描述了本规范中使用的上下文无关文法，这是 ECMAScript 程序语法结构的定义。

5.1.1 上下文无关文法(Context-Free Grammars)

一个上下文无关文法由许多产生式(productions)组成。每个产生式都拥有一个抽象符号作为其左式(left-hand side)，被称为非终结符(nonterminal)，以及一个由零个或多个非终结符和终结符(terminal)组成的右式(right-hand side)。对于每个文法而言，终结符是从一个特定的字母表中抽取的。

句子的开始由单个显式的非终结符组成，被称为目标符(goal symbol)，一个给定的上下文无关文法规定了这样一种语言，它被表示为可能的终结符序列组成的集合（有可能是无限集），这是用产生式左式重复替换序列中一切非终结符得到的，替换时所用的产生式的左式要和被替换的非终结符一致。

5.1.2 词法文法和正则表达式文法

ECMAScript 的词法文法(lexical grammar)在条款7中给出。此文法以 Unicode 字符集中的字符作为其终结符。它定义了一个产生式集合，其中的产生式以目标符输入分隔元素 (InputElementDiv)或输入正则表达式元素(InputElementRegExp)开始，这描述了 Unicode 字符是如何被翻译成输入元素序列的。

为 ECMAScript 语法文法提供的除空白和注释之外的输入元素被称为 ECMAScript 托肯 (token)。这些托肯即 ECMAScript 语言中的保留字、标识符、常量和标点符号。此外，行结束符即使不被认为是托肯，它同样是输入的元素流中的一部分，并指导自动插入分号的过程 (7.8.5)。普通的空白和单行注释被丢弃，且不出现在为语法文法提供的输入元素流中。对于多行注释 (MultiLineComment)（即形如 "/*...*/"的注释，不论它跨越了多少行），如果它没有包含行结束符，就被简单地丢弃；假使多行注释包含一个以上行结束符，则用单个行结束符替换它，使之成为为语法文法提供的输入元素流的一部分。

ECMAScript 的正则表达式文法(RegExp grammar)在15.10 中给出。此文法同样以 Unicode 字符集中的字符作为其终结符。它定义了一个产生式集合，其中的产生式以目标符的模式(Pattern)为起始，描述了 Unicode 字符是如何被翻译成正则表达式模式的。

词法文法和正则表达式文法的产生式被识别为被两个冒号"::"分割的产生式。词法文法和正则表达式文法共享某些产生式。

5.1.3 数字化字符串文法

第二个文法被用于将字符串翻译为数值量。此文法类似词法文法中与数字常量有关的部分，以 Unicode 字符集中的字符作为其终结符。此文法在9.3.1中出现。数字化字符串文法的产生式被识别为被三个冒号":::"分割的产生式。

5.1.4 语法文法

ECMAScript 的语法文法在条款11，12，13和14中给出。此文法以词法文法定义的 ECMAScript 托肯作为其终结符(5.1.2)。它定义了一个产生式集合，其中的产生式以目标符 Program 开始，描述了托肯序列是如何构成语法正确的 ECMAScript 程序的。

若将一个 Unicode 字符流被解析为一个 ECMAScript 程序，首先，通过重复应用词法文法，它被转化为一个输入元素流；通过一次应用语法文法，这个输入元素流继续被解析。如果输入元素流中已不再留有托肯，而托肯仍无法被解析为单个目标非终结符 Program，则这个程序语法出错。

语法文法的产生式被识别为仅被一个冒号":"分割的产生式。

语法文法被表示为0,0,0的分段，0其实不是能被正确的 ECMAScript 程序接受的托肯序列中的一员。确定的额外托肯序列同样会被接受，也就是说，即使只有冒号被加入序列中的某个位置（比如在行结束字符之前），这些托肯也会被文法所描述。深入说来，即便终结字符出现在某些“尴尬”的位置上，被文法描述的、确定的托肯序列也不考虑其是否能被接受。

//全文太长，先发的这部分是说明部分
//最后一段没看懂，晕

ECMA-262试译：4.3 Definitions

2007-05-26T09:12:00.000+08:00

4.3 定义

下面给出了与 ECMAScript 有关的关键术语的非正式定义。

4.3.1 类型

类型是数据取值的集合。

4.3.2 原语值

原语值是类型 Undefined，Null，Number，Boolean 或 String 的一个成员。原语值是直接表示语言实现的底层数据。

4.3.3 对象

对象是未排序的属性的集合，其中每个属性包含一个原语值、对象或函数。被作为属性保存的函数被称为方法。

4.3.4 构造函数

构造函数是一种创建并初始化对象的函数对象。每个工作；构造函数都拥有一个相关联的原型对象，用它来实现继承和共享属性。

4.3.5 原型

原型是一种对象，被用在 ECMAScript 中实现继承结构、状态和行为。当构造函数创建对象时，那个对象隐含引用构造函数的关联原型，以此分解属性引用。通过程序中的表达式 constructor.prototype 可以引用到构造函数的关联原型，通过继承，添加给对象的属性会被所有共享此原型的对象共享。

4.3.6 本地对象

本地对象指的是由 ECMAScript 实现提供并独立于宿主环境的任何对象。这篇规范定义了标准本地对象。有些本地对象是内置的；其余的可能在 ECMAScript 程序执行的过程中被构造。

4.3.7 内置对象

内置对象指的是由 ECMAScript 实现提供的，独立于宿主环境的，并在 ECMAScript 程序刚开始执行时就出现的对象。这篇规范定义了标准内置对象，一个 ECMAScript 实现也可能指明并定义其它的内置对象。所有的内置对象都是本地对象。

4.3.8 宿主对象

宿主对象指的是由 ECMAScript 实现提供的，使 ECMAScript 的执行环境变得完备的对象。所有非本地对象都是宿主对象。

4.3.9 未定义值

未定义值是一种原语值，当一个变量未被赋值时被使用。

4.3.10 Undefined 类型

类型 Undefined 仅有一个值，叫做 undefined。

4.3.11 空值

空值是一种原语值，用来代表0，空或不存在的引用。

4.3.12 Null 类型

类型 Null 仅有一个值，叫做 null。

4.3.13 布尔值

布尔值是 Boolean 的成员，它是两个特殊的值之一，true 和 false。

4.3.14 Boolean 类型

Boolean 类型仅用两个特殊的值表示逻辑实体。其一被称为 true 另一个被称为 false。

4.3.15 Boolean 对象

Boolean 对象是 Object 类型的一个成员，内置 Boolean 对象的实例。也就是说，在 new 表达式中使用 Boolean 构造函数提供一个布尔值参数创建出 Boolean 对象。结果对象拥有一个隐含（无命名的）属性是那个布尔值。一个 Boolean 对象可被强制为一个布尔值。

4.3.16 字符串值

字符串值是 String 类型的一个成员，它是一个有序的、长度有限的的列表，包含零个或更多16位无符号整数。

NOTE 即使每个值常常表示单个16位 UTF-16文本，语言也不给出关于期望这些值被表示为16位无符号整数的限制或要求。

4.3.17 String 类型

String 类型是所有字符串值的集合。

4.3.18 String 对象

String 对象是 Object类型的一个成员，内置 String 对象的实例。也就是说，在 new 表达式中使用 String 构造函数提供一个字符串参数创建出 String 对象。结果对象拥有一个隐含（无命名的）属性是那个字符串值。通过以函数的方式调用 String 构造函数可以把一个 String 对象强制为一个字符串值。

4.3.19 数值

数值是 Number 类型的一个成员，是数字的直接表示。

4.3.20 Number 类型

Number 类型是表示数字的值的集合。在 ECMAScript 中，表示双精度64位格式（IEEE 754）的值的集合包含特殊值“Not-a-Number”（非数字，NaN），正无穷和负无穷。

4.3.21 Number 对象

Number 对象是 Object类型的一个成员，内置 Number 对象的实例。也就是说，在 new 表达式中使用 Number 构造函数提供一个数值参数创建出 Number 对象。结果对象拥有一个隐含（无命名的）属性是那个数值。通过以函数的方式调用 Number 构造函数可以把一个 Number 对象强制为一个数值(15.7.1)。

4.3.22 Infinity（无穷）

原语值 Infinity 表示正无穷数值。这个值是 Number 类型的一个成员。

4.3.23 NaN

原语值 NaN 表示 IEEE 标准“非数字”值。这个值是 Number 类型的一个成员。

//重新调整了文档结构，这篇可以发了。

ECMA-262试译：4.2.1 Objects

2007-05-25T21:43:00.000+08:00

4.2.1 对象

ECMAScript 并没有严格意义上的类，在这一点上不同于 C++、Smalltalk 或者 Java，不过作为替代，它支持构造函数(constructors)，利用它，可通过执行代码创建对象：给对象分配存储，然后通过赋初始值来初始化对象属性的全部或部分。所有的构造函数都是对象，但并非所有的对象都是构造函数。每个构造函数都有一个 Prototype（原型）属性，被用于实现基于原型继承(prototype-based inheritance)和共享属性(shared properties)。使用构造函数来创建对象要用到 new（新建）表达句；举个例子，new String("A String") 创建了一个新的字符串对象。不使用 new 调用构造函数的后果取决于这个构造函数本身。举个例子，String("A String") 产生一个原语字符串而非对象。

ECMAScript 支持基于原型继承。每一个构造函数都有一个相关联的原型，它创建的所有对象都拥有一个隐含的引用指向那个与其构造函数相关联的原型（所谓的对象的原型）。更深一步讲，原型还可能会拥有到它的原型的隐含的非空引用，依此类推；这被称为原型链(prototypechain)。当引用被作为对象中的属性时，在原型链中第一个包含以这个引用的属性名为名的属性的对象，它的那个属性就是被引用者。换句话说，首先检查被直接提及的对象是否包含某个属性；如果那个对象包含同名属性，被引用指向的就是这个属性；如果那个对象并没有包含同名属性，接下来检查它的原型，如此继续下去。

通常，在基于类的面向对象语言中，实例装载状态，类装载方法，且继承的仅仅是结构和行为。而在 ECMAScript 中，状态和方法均由对象装载，且结构、行为、状态都会被继承。

所有没有直接包含某个它们的原型所包含的特定属性的对象，与它们的原型共享那个属性和它的值。下面的图表阐述了一切：

CF 是一个构造函数（当然也是一个对象）。使用 new 表达式，我们创建了五个对象：cf1，cf2，cf3，cf4 和 cf5。这些对象中的每一个都包含了名为 q1 和 q2 的属性。虚线表示隐含的原型关系；比方说，cf3 的原型是 CFp。构造函数 CF自己拥有两个属性，名为 P1 和 P2，它们对于 CFp，cf1，cf2，cf3，cf4 或 cf5 而言都是不可见的。CFp 中名为 CFP1 的属性被 cf1，cf2，cf3，cf4 和 cf5 （除了 CF）共享，这样，CFp 的隐含原型链中的所有属性没有名为 q1，q2 或 CFP1 的。需要注意的是，CF 和 CFp 之间没有隐含的原型关联。

不同于基于类的面向对象语言，ECMAScript 中的属性可以通过给它们赋值的方式，把它们动态添加给对象。也就是说，构造函数不需要给所构造的对象的部分或全部属性命名或赋值。在上面的图表中，通过给 CFp 中的属性赋新值就可以给 cf1，cf2，cf3，cf4 和 cf5 添加新的共享属性。

//觉得这篇是我到目前为止翻的最好的 :)

ECMA-262试译：4.2 Language Overview

2007-05-25T19:41:00.000+08:00

4.2 语言概述

接下来是一个 ECMAScript 语言的非正式概述——这个语言的所有部分的描述。严格说来，这个概述不是标准的一部分。

ECMAScript 是基于对象的：语言的基本部分和宿主设施由对象提供，一个 ECMAScript 程序是一组可通信的对象。ECMAScript 对象(object)是一个未排序的属性 (properties)的聚集，每个特征由零个或多个特征(attributes)来确定它们如何被使用——举个例子：当某个属性的 ReadOnly（只读）特征被设为真(true)时，任何通过执行 ECMAScript 代码来改变这个属性值的企图都不会生效。属性是装载其它对象的容器，如原语值 (primitive values)或方法(methods)。原语值是下列内置类型的一个成员：未定义(Undefined)，空值(Null)，数值(Number)，布尔值(Boolean)和字符串(String)；对象是保持内置类型对象(Object)的一个成员；方法是一种通过属性来访问对象的函数。

ECMAScript 定义了一集勾勒出 ECMAScript 定义实体的内置对象(built-in object)，它们包括Global（全局）对象、Object 对象、Function （函数）对象、Array（数组）对象、String对象、Number对象、Math（数学库）对象、Date（日期）对象、RegExp（正则表达式）对象以及其它 Error 类对象：Error，EvalError（求值错误），RangeError（数组下标范围错误），ReferenceError（引用错误），SyntaxError（语法错误），TypeError（类型错误），URIError（唯一资源定位符错误）。

ECMAScript 还定义了一个内置运算符(operators)集合。严格地说，它们可能不是函数或方法。ECMAScript 运算符包含了各种各样的操作：乘法运算符，加法运算符，位移运算符，关系运算符，相等关系运算符，二元位操作运算符，二元逻辑运算符，分配运算符，逗号运算符。

ECMAScript 语法被特意设计成类似 Java 的语法。ECMAScript 的语法设计能使其作为一种易于使用的脚本语言提供服务。例如，一个变量不需要拥有自己的类型声明或与其关联的属性的类型，定义函数时不需要在它们被调用的上文中出现它们的声明。

//这个翻译的意义不亚于词汇表

ECMA-262试译 - 阶段patch

2007-05-25T18:11:00.000+08:00

Brief History 首句现译为："本 ECMA 标准基于一系列原创技术，其中最著名的是Netscape 公司的 JavaScript 和 Microsoft 公司的JScript。"
Conformance 中去掉共计4个"一个"，首句中"这个"改为"本"，最后一段首句第二字句现译为"在此规范描述之外的类型"
Web Scripting 第一段最后一句去掉"一个"，修改输入错误一处，最后一段首句现译为"与浏览器不同，网页服务器为服务器端提供了另一种宿主环境..."；虽然与原文不同，但没办法，英文的指代往往过于突兀~~

最后感谢网友lonelyfox的支持，虽然不明其豆瓣马甲是who...

ECMA-262试译：4.1 Web Scripting

2007-05-24T23:56:00.000+08:00

4.1 网页脚本

网页浏览器为 ECMAScript 提供了一个主机环境以进行客户端的计算，例如：代表窗口、菜单、浮动条、对话框、文本区域、锚点、框架、历史、cookies，以及输入/输出功能的对象。深入说来，主机环境提供的一套向事件上附加脚本代码的方法，这些事件有焦点的改变，页面和图像的载入、卸载，出错和异常结束，点选，提交表单以及鼠标动作等。脚本代码在 HTML 之间出现，被显示的页面是一个用户界面元素和固定或处理后的文本和图像的组合。这种脚本语言会响应用户的互交从而不需要一个主程序。

一个网页服务器为服务器端提供了一个不同的主机环境，这包括代表请求、客户端、文件的对象；以及锁定或共享数据的机制。通过同时使用浏览器端和客户端脚本，在客户端与服务器之间分配计算将成为可能，这样就能为基于网页的应用提供一个自定义化的用户界面。

ECMA-262试译：4 Overview

2007-05-24T23:55:00.000+08:00

4 概述

这一节包含一个 ECMAScript 语言的非正式概述。

ECMAScript 是面向对象的编程语言，被用来演示计算技术和操控主机环境下的计算机对象。这里定义的 ECMAScript 没有被设计成计算性自足的语言；事实上，在这篇规范中，没有为输入外部数据或输出计算结果给出任何条款。取而代之的是，我们期望 ECMAScript 程序的计算机环境可提供除了这篇规范中所描述的对象和其它语言设施之外的、某些特定环境下的 主机 (host) 对象，它们的描述和行为将超出此规范的所指出的范围，即它们可提供某些可被访问的属性和某些可从 ECMAScript 程序中调用的函数。

脚本语言(script language)是一类被用于操控、自定义和自动控制现有系统设施的编程语言。在这些系统中，实用的功能可通过一个用户界面来使用，脚本语言就是一种通过程序控制那些功能的机制。于是，我们就说此系统为对象和设施提供了一个主机环境，它们使得脚本语言的能力变得完备。脚本语言是为了能被专业或非专业程序员所使用而设计的。为了适应非专业程序员，语言的一些方面会多少有些不严格。

ECMAScript 从一开始就被设计成一个网页脚本语言(Web scripting language)作为基于网页的、客户端—服务器端(C/S)构架的建筑师，它能提供一种机制，用来使浏览器中的网站页面更加活跃，并展示服务器端的处理情况。ECMAScript 能够为各种主机环境，以及这个文档所描述的核心脚本编程语言之外任何特定的主机环境，提供基本的脚本编程能力。

ECMAScript 中的有些语言设施类似其它编程语言；尤其是 Java 和 Self，下列文献描述了它们：

Gosling,James,Bill Joy and GuySteele. The Java Language Specification. Addison Wesley Publishing Co.,1996.
Ungar,David,and Smith,Randall B. Self: The Power of Simplicity. OOPSLA '87 Conference Proceedings,pp. 227-C241,Orlando,FL,October 1987.

ECMA-262试译：2 Conformance

2007-05-24T23:46:00.000+08:00

2 前言

一个符合标准的 ECMAScript 实现必须提供并支持这个规范中所描述的所有类型，值，对象，属性，函数，程序语法和语义。

一个符合这个国际标准的实现应当能解释前言中提到的字符集：Unicode 标准，2.1版或更新版本，使用 UCS-2 或 UTF-16 作为被采纳的编码格式的 ISO/IEC 10646-1 第3级实现。如果被采纳的 ISO/IEC 10646-1 子集没有额外指明，则被认定为组号是300的 BMP 子集。如果被采纳的编码格式没有额外指明，则被认定为 UTF-16 编码格式。

一个符合标准的 ECMAScript 实现被允许提供额外的、在这个规范的描述之外的类型，值，对象，属性和函数。特别的，一个符合标准的 ECMAScript 实现被允许给那些此规范中所描述的对象提供此规范所没有描述的属性，以及那些属性的值。

//第一节只有一句话，不贴了；第三节是参考文献，不用翻。

ECMA-262试译：Brief History

2007-05-23T23:38:00.000+08:00

Brief History

此ECMA 标准基于著名的 JavaScript（Netscape 公司）和 JScript（Microsoft 公司）中的一些原创技术。该语言由 Netscape 公司的 Brendan Eich 发明并首先出现在该公司的 Navigator 2.0 浏览器中。该语言至今已经在所有来自 Netscape 的全部子系列浏览器和从 Internet Explorer3.0 开始所有来自 Microsoft 的浏览器中出现。

该标准的研发起始于1996年11月。ECMA 标准的首个版本于1997年6月被 ECMA 公共协会接受。

此 ECMA 标准曾被提交 ISO/IECJTC1 以“快速通道”审批过程的方式进行审批，并于1998年8月被批准成为 ISO/IEC16262 国际标准。1998年6月，ECMA 公共协会批准了 ECMA-262 标准的第二版以保持它与 ISO/IEC16262 的完全协调。第一版和第二版之间存在着重大的性质上的变更。

目前的文档定义了该标准的第三版，这包含了强大的正则表达式，更优秀的字符串处理，新的流程控制语句，try/catch 异常处理，更严密的出错定义，数字式输出格式以及对于即将到来的国际化设施和语言未来发展的预期而做出的次要变更。

关于这个语言的工作并没有结束。技术委员会正在为了作出意义重大的优化而工作，这包括脚本在互联网上创建和使用的机制，以及与其它标准实体（如万维网联盟(W3C)及无线应用协议论坛的等团体）间更紧密的协作。

//试译稿，有不妥之处请高手指正。

//原文地址（pdf文档）

恶搞 qsort 测试代码

2007-05-22T12:28:00.000+08:00

//Array类的交换和判断是否有序的方法
Array.prototype.swap = function (a, b) {
var tmp = this[a];
this[a] = this[b];
this[b] = tmp;
}

Array.prototype.isInOrder = function () {
for (var i =0; i <> this[i+1]) return false;
return true;
}

//简短的快速排序，只需一个数组作参数
function qsort (arr, l, u) {
l = l || 0;
u = ((u != 0) && (u == undefined)) ? arr.length : u;
if (l >= u) return;
var m = l;
for (var i = l+1; i <= u; i++)
if (arr[i] < arr[l])
arr.swap(++m, i);
arr.swap(l, m);
qsort(arr, l, m-1);
qsort(arr, m+1, u);
}

Math.rand = function (start, end) {
if (end == undefined) {
end = start;
start = 0;
}
return start+Math.random()*(end-start);
}

Math.randInt = function (start, end) {
return Math.round(Math.rand(start, end));
}

//生成待排序的大规模随机整数数组
function randRange (len, start, end) {
var range = new Array(len);
for (var i = 0; i < len; i++)
range[i] = Math.randInt(start, end);
return range;
}

//把测试代码绑定在qsort()函数上
qsort.test = function (len, start, end) {
var tmpArr = randRange(len, start, end);
this(tmpArr);
return tmpArr.isInOrder();
}

PS: 我一个同学在电脑课上用Firefox玩randRange(10000)之类的东西玩了半节课……

Mazy 编程语言介绍

2007-05-20T08:22:00.000+08:00

豆瓣网上的讨论，还真“激烈”，废话请读者自行略过。

2007-05-16 22:11:52 　　来自: 冰の銳 (南京)

　　因为我在网上首次提到我设计的Mazy语言是在这个小组 & 这个小组人还比较多，所以在这儿“大肆”宣传我的东东。
　　
　　以下摘自我给其初期实现 WebMazy 所写的文档：
　　"WebMazy 是一个开放源代码的 Mazy 语言环境，提供用纯JavaScript实现的网页式界面。它还提供了使用JavaScript来扩展Mazy库的方法。
　　
　　Mazy 语言是作者独立设计的、面向基础数学问题的函数式编程语言(functional programming language)，具有极其简洁的语法和一定的直接通过数学表示解决数学问题的能力。"
　　
　　有需要源程序者发我豆邮付上您的邮件地址。

> 修改　

2007-05-16 22:19:42 冰の銳 (南京)

　　以下摘自文档的入门部分，"Hi, I'm Mazy!" ：
　　
　　
　　$一个计算器
　　
　　Mazy 最基本的用途是作计算器——表达方式和你平常在纸上写的那种基本没什么区别。例如（直接的一行指的是在interpretation中的输入，以 > 开头的一行指的是trace中的返回情况）：
　　
　　2+2
　　> 4
　　(50-5*6)/4 ;这是一个补充型注释
　　> 5
　　7/3 ;不能整除，返回小数
　　> 2.3333333333333335
　　pow(2,1000) ;内置函数，这里取2的1000次方
　　> 1.0715086071862673e+301
　　18%4 ; '%'是取模运算符，简单地说就是返回余数
　　> 2
　　
　　平心而论，Mazy 在简单运算方面并没有太多亮点，和 Haskell 之内的支持无限长整数和复数运算的东西全然不能相比；不过人家毕竟是“世界上最先进的语言”，要知足，要知足~~
　　
　　
　　$带变量支持的计算器
　　
　　变量是什么？一个静态的定义而已，给一个值一个名字而已：
　　
　　x = 34 ;现在x这个名字就代表34
　　> 34
　　x*x
　　> 1156
　　
　　数学上好像只有“代数”这个概念而没有“变量”这个概念，况且 Mazy 是函数式编程语言，变量一经申明就不可在同一环境下改变其值，应该叫“不变量”还差不多；
　　
　　x = 34 ;重复申明试试，
　　> RuntimeError: The name x already has a definition in this level.
　　
　　这句话是我写的，我很自豪啊^_^
　　
　　完了，变量值不可改变，难道说每次求一个数的平方都要输一下xx*xx吗？！
　　
　　$可以定义函数的计算器
　　
　　函数是什么？在Mazy中，我可以负责地完全使用数学上的定义来回答这个问题：函数是一个确定的、多对一映射。完全不同与C等命令式语言的函数——他们不但状态可变而且行为恶劣。好了，多说无益，看看怎么解决上面的问题：
　　这是一个标签型注释，下面我们定义这个返回参数值平方的函数: sqr (x)=x*x
　　> function()
　　sqr(23) ;23的平方
　　> 529
　　sqr'2(x)= 2*sqr(x) ;再试一个（注意''和"等效，都可用作命名；Mazy中没有字符串。）
　　> function()
　　sqr'2(5) > 50
　　
　　$能作判断的计算器？！
　　
　　憋死我啦！终于到了展现Mazy力量的时候啦！来看看这个求阶乘的 C 语言程序：
　　int fact (int n) {
　　 int result = 0;
　　for (int i = 1; i <= n; i++) { 　　result *= i; 　　} 　　 return result; 　　} 　　　　这个是Mazy版的（在inter中深入多行程序时可以用Shift+Enter来输入换行；或者在definition中定义（自己写一遍，不要CC+CV），然后在inter中使用。(*...*)之间是一个文档型注释）：　　(* 把阶乘的数学定义照抄一遍，最后加个英文句点就行了 *) fact (n) = 　　1, n=0 n * fact(n-1). 　　　　接着在inter中计算：　　fact(10) > 3628800
　　
　　如果你现在有一种身陷迷宫的感觉，那我的目的就达到了——Mazy意为迷宫般的。
　　
　　还是说一下这是怎么回事吧！Mazy中，一个函数必须有且只在最后有一个返回表达式（正则尾递归，有了它，程序就不需要循环结构了）；在多行申明下的单行中出现了用,分割的两个表达式时，就认为这种情况分析表达式开始，每行的第二个子式分析条件，一旦满足就返回该行的子表达式，直到函数体以. 结束（思想来源于ML）。很明显，这里申明语句是无效的，所以所有的=号执行比较运算，返回布尔值true或 false（Note:布尔值运算符：与& 或| 非! ）。
　　
　　所以，求一个数绝对值的函数就可以写成这样（这只是个说明用法的例子而已）：
　　abs' (n) =
;加'是因为内置库中已有定义，最好不要覆盖
;顺便提一句：函数的这个位置可以填入属于它的内部申明
;这就是所谓的“块结构”，其本质见于《计算机程序的构造与解释》
普通变量也可以用条件分析句申明，但没有“块结构”
　　n, n>0
　　0, n=0
　　-n, n<0.> 5050
　　
　　我再来带你们走过迷宫吧！函数参数域中全是常数或者'*'符号的本质上不是函数，他们不允许有“块结构”，他们是函数的“常量”版本，学名叫做 “槽”(chunk)（来自于Haskell, ErLang等FPL），他们常常可以起到支持能通过数学归纳法证明的函数停止的作用。比如这个求n阶等差数列第m项的公式：
　　ff(1,*) = 1
　　ff(*,1) = 1
　　ff(n,m) = ff(n-1,m) + ff(n,m-1)
　　
　　很多后现代的语言都配备这这个东西，但对于 Mazy，它是有重大意义的。
　　
　　
　　$形式与内容高度同一的自动计算机
　　
　　C语言吃了大亏了，它总是成为我的反面教材。来看看这个“臭名昭著”的、在无数算法书中被指责为“极其低效”的求菲波那契数列第n项的函数：
　　int fib (int n) {

　　 if (n <= 2) { 　　 return 1; 　　} 　　return fib(n-1) + fib(n-2); 　　} 　　　　就一个字：慢，奇慢无比，算法复杂度O(2^n)级，算到40多就彻底崩溃了；但它是到公式的直接翻译，使用了十分清晰递归。我写了一个O(n)级的递归版本：　　　　int i = 3; 　　unsigned long fib_iter (int x, int y, int n) { 　　if (i <= n) { 　　i++; 　　return fib_iter(y, x + y, n); 　　} else { 　　return y; 　　} 　　} 　　//这是被调用的函数　　unsigned long fib (int n) { 　　return fib_iter(1,1,n); 　　} 　　　　然而老师们更希望我们使用更丑、更恶劣的纯循环来完成这个程序；不如干脆我们学习汇编语言吧！那个更快。（我以为，我们现有的计算机教育真的正在歧途中越走越深）　　　　还是让我们回头看看我们美丽的迷宫吧！在Mazy中，使用完整的数学定义直译或者给出某些递归下降点的办法直接写出程序就能获得O(n)级的线性算法复杂度：　　fib(1) = 1 　　fib(2) = 1 　　fib(n) = fib(n-1) + fib(n-2) 　　　　算着玩儿吧，算到100都只是弹指间的事；　　fib(100) > 354224848179262000000
　　
　　如果你是个对于算法有所了解的，此时一定已经从电脑椅上翻下去了；不过，如果你确实对于算法很了解，此刻一定已经想到了一个词——动态规划。
　　
　　对，动态规划！fib的数学定义为什么慢？充分的计算占到了总计算量的绝大部分；采用一个动态记录计算中已得到的值的标格问题就解决了；再细想下去，基本的、仅针对函数参数进行判断的动态规划是非常机械的，为什么不能成为语言的一种函数调用机制呢？
　　
　　这种机制叫做“带有自动记忆的按需调用槽”，Mazy 实现了它。
　　
　　于是，Mazy 带着0个关键字，一系列优雅的、数学语言直译化的语法，破除了使用这些东西可能带来的性能的降低，上路了——一种非常罕见的形式与内容高度同一的自动计算机就此诞生了。
　　
　　还有什么？
　　
　　还有什么？Mazy 还有几个成体现的重要特性，但这儿是“初学者课堂”，语法到目前为止基本讲完了，那些“重要特性”的真正有效的使用可不是这样短的一篇文章就能覆盖的。就好比下棋，规则就那么几句，但不是谁都能领略其中的端倪。Mazy 就是这样的一种语言。
　　
　　最后列出一点东西，作为文章的结束。
　　
　　 * 一元前置运算符：- + !
　　 * 一元后置运算符：
　　 o ++（增量位置，相当于Lisp中的car，取出一个列表(list)的首项）
　　 o --（减量位置，相当于Lisp中的cdr，取出一个list除去第一项后余下的项）
　　 * 二元运算符：+ - * \ % ，= != > |
　　 * 行末语法：
　　 o 一行中存在‘:’的，该行是一个标签型注释；
　　 o 以‘?’结束的行，该行除去?的表达式是一个前置require断言；
　　 o 以‘!’结束的行，该行除去!的表达式是一个前置ensure断言。
　　 * 表申明：作为值出现 [项0, 项1, 项2...]
　　 * 常量：none（未定义值） nil（空表） NaN（非数字） Infinity（无穷大，除0的返回值）
　　
　　
　　习题
　　
　　关于列表(list)操作我只提到一个++--；但其实只有这些就够了；Mazy 是面向数学的，不赞成你常常手动构筑表（虽然语言library本身提供了此类支持）。来挑战一下自己的智商吧，下面这个函数可以求出一个list的长度，想想它是怎么工作的：
　　len' (ls) =
　　 0, nil len(ls--) + 1.

> 删除

2007-05-17 01:05:15 AlbertLee (北京)

　　和
　　len' [] = 0
　　len' (_:xs) = 1 + len'(xs)
　　
　　一样了。
　　
　　不过 fib 那个例子确实是个亮点。

> 删除

2007-05-17 12:09:23 冰の銳 (南京)

　　不好意思，最后一个例子少个换行：
　　len' (ls) =
　　　0, nil
　　 len(ls--) + 1.
　　
　　可惜现在的实现还不能得像Haskell一样。

> 删除

2007-05-17 16:40:47 AlbertLee (北京)

　　fib 的那个“动态规划” 是什么原理？

> 删除

2007-05-17 16:50:21 codeplayer (武汉)

　　动态规划是一种算法了，不过语言自动完成倒是第一次见过。
　　没玩过 FP，不过貌似很是有点意思哈。

> 删除

2007-05-17 17:34:57 冰の銳 (南京)

　　"fib 的那个“动态规划” 是什么原理？"
　　把已计算过的参数、值对应保存在哈希表中；因为函数式语言变量的绑定不变，所以对于一个函数，参数到值是数学上的映射关系，可以直接调出结果。

> 删除

2007-05-17 19:56:59 HYRY

　　那么获得O(n)级的算法复杂度的同时，是否增加了空间复杂度了呢？既然用哈希表保存中间值，那么这个哈希表是否有一定的大小限制，总不能无穷大吧。如何知道表中的某个内容不会再被用到，而把它释放掉？
　　如果不释放的话，fib(1000000)会不会很占空间？
　　

> 删除

2007-05-17 20:48:17 AlbertLee (北京)

　　被“动态规划”这个词误导了。
　　用哈希表保存中间结果，确实是用空间换时间的一种办法。
　　如果能通过程序自动把 fib (n-1) + fib(n-2) 这中类型的递归优化到O(n)的复杂度，那确实是太牛了（近似于妖了），不过我显然低估了这个的困难程度了。
　　

> 删除

2007-05-17 21:27:46 冰の銳 (南京)

　　这种纯优化的想法是可以实现的，但在解释器环境下就不划算了。
　　"如果不释放的话，fib(1000000)会不会很占空间？"
　　
　　对于目前的实现来说是的。但最终实现大概还要再等两三年吧，我打算优化内存分配来消解哈希表空间消耗。

> 删除

2007-05-17 21:39:27 AlbertLee (北京)

　　我直觉上感觉无法根本解决这个问题，只能是通过一些优化手段对特定的问题进行近似的优化。无法获得一个算法能通用的优化这个问题。

> 删除

2007-05-17 21:44:44 AlbertLee (北京)

　　感觉真是一句废话！。。。

> 删除

2007-05-17 21:57:54 小豆包-习惯了ubuntu…… (广州)

　　想要达到线性复杂度，只要保留前两个元素就好了

> 删除

2007-05-17 22:08:23 HYRY

　　用哈希表保存函数的运算结果,使得下次运算时可以直接使用,这个想法和CPU硬件的cache差不多.不过因为没有限制内存使用量,这样就相当于 cache无穷大,实际运用上是不现实的. 如果限制了cache的大小,就会出现很多算法上的细节问题. 软件来实现那种set associative cache算法的话,本身就好耗费很多时间.

> 删除

2007-05-18 12:10:31 冰の銳 (南京)

　　"想要达到线性复杂度，只要保留前两个元素就好了"
　　这只能解决特定问题啊...
　　
　　我有个想法，向虚拟机学习，设定heap大小，把所有产生的结果放在共有堆中，用户给定的函数特定值保存在私有堆，这样共有堆的删除就可以随意进行了！
　　
　　其实我还想听听大家对语法设计方面的看法。

> 删除

2007-05-18 13:34:56 codeplayer (武汉)

　　其实要是能够智能判断保存中间结果的数量就更好了，
　　比如 f(n) = f(n-1) + f(n-2) 只需要保存两个中间结果就够了。
　　f(n) = f(n-1) + f(n-3) 就需要三个了。
　　f(n, m) = f(n-1, m) + f(n, m-1) ，这个想了一下，貌似有效中间结果最多差不多也就是是 m+n 左右，而不需要保存所有 m*n 个中间结果。

> 删除

2007-05-18 16:38:41 小豆包-习惯了ubuntu…… (广州)

　　我的意思是，可以通过代码分析，有限度缓冲数据。保存所有中间结果没有太大意义。比如f(n) = f(n-1)+f(n+1)，完全可以从代码中分析中需要缓冲的回溯级数。

> 删除

2007-05-18 17:42:33 冰の銳 (南京)

　　"其实要是能够智能判断保存中间结果的数量就更好了"
　　这种技术只能用在编译器上，对于解释器来说绝对浪费...
　　
　　"从代码中分析中需要缓冲的回溯级数"
　　只可惜真正的递归复杂程度远不止于此，有很多论文但都不可行。目前解释器技术能分析正则尾递归我觉得已经很高级了。

> 删除

2007-05-19 10:59:14 仨儿 (北京)

　　咔咔咔！国人作品，应该关注！

> 删除

2007-05-19 11:08:10 ookami (Tōkyō)

　　任何语言都能写出O(n)的fib算法出来
　　这是算法层的问题，而不是语言层的问题。
　　时间换空间和空间换时间，都是算法的需要，或者说是业务的需要，在语言上不应该武断地替用户做这种选择。

> 删除

2007-05-19 11:58:14 冰の銳 (南京)

　　
　　首先请楼上看清楚，Mazy是为了能让数学形式直译的函数都能完美执行而设计的，不像某些语言是为了让用户在想用它们了解计算机科学和数学式成天面对指针和内存而设计的！
　　
　　"任何语言都能写出O(n)的fib算法出来
　　这是算法层的问题，而不是语言层的问题。"
　　
　　这话说的真的太残忍了...看看我们的小学、中学那些学编程的孩子们，有几个不是为了竞赛，不是为了升学？学的那些Pascal、C，不能说语言本身不好，TMD叫这些孩子在把已有知识转化为能力多么困难啊！而国外呢？小学有用Smalltalk的，中学学习Scheme，10岁小儿就能用 Scheme编写出Adventure游戏，这TMD叫差距啊！为什么啊？我们的教育者成天关注的都是些什么啊？！且不说函数式编程的重要性，就算是 Pascal、C，写那种代码也配叫编程啊？
　　计算机教育必须以提升被教育者的思维能力为目的而不是其它！

> 删除

2007-05-19 14:47:11 ookami (Tōkyō)

　　　　不想扯太远，就事论事。
　　
　　　　听说lz的lua已经出神入化了，比精通还要精通，就帖一段lua源代码test里面的那个fib吧，我认为你应该看过的
　　
　　-- very inefficient fibonacci function
　　function fib(n)
　　　　if n<2 c="{}" y="c[x]" y="f(x)" fib="cache(fib)"> 删除

2007-05-19 15:21:05 冰の銳 (南京)

　　“你的O(n)级的递归版本里面的那个全局变量i用的可真是，，，，，，”
　　所以说嘛！
　　
　　你那个是
　　SICP里的原版代码，但不是仍然要求用户思考吗？
　　再者，对于既没有赋值又没有宏的函数式语言来说就更不行啦。
　　把这个机制做到语言里就是Mazy的当前实现手段。

> 删除

2007-05-19 17:43:09 ookami (Tōkyō)

　　--但不是仍然要求用户思考吗？
　　难道你觉得用户不应该思考吗？
　　
　　打住吧，等你的Mazy稍微成熟一些的时候再讨论这个问题，说不定到那个时候你的想法也发生变化了。

> 删除

2007-05-19 18:17:18 冰の銳 (南京)

　　--"难道你觉得用户不应该思考吗？"
　　啊对对对...我现在就在上高二，你可能不知道我们中国的计算机教育现状。XXXX。不知者无过。
　　等着吧，等我一切安定下来了把Mazy i的C语言实现给写了，"你的想法也发生变化了"。
　　
　　PS: 你的所在地上显示个Tōkyō我不知道是什么意思。

> 删除

2007-05-20 00:35:20 ookami (Tōkyō)

　　我不知道中学的计算机教育情况，事实上在我上中学的时候还没有接触过计算机。不过这不重要。
　　等着吧，看谁的想法先变。
　　PS:你应该是个聪明的人，所以应该有办法知道Tōkyō是什么意思。

> 删除

读《ACM图灵奖演讲集》有感

2007-05-19T08:53:00.000+08:00

最近我在读一本似乎和编程没太大关系的计算机书籍，叫《ACM图灵奖演讲集 - 前20年》（以下简称《ACM演讲集》）。这本书收录了1966-1985年这20年间图灵奖获奖者们的演讲。相对于计算机的普及速度，文章已经很古老了，中文版出版也很久了，但并不像那些纷扰而嘈杂的电脑书刊那样稍纵即逝。普通的电脑书，充斥着看似先进的技术；普通的编程书，充斥着不知为什么而生的代码。而它，就像一位智者，静坐在书店那些已经满是垃圾文字的书架上，看着“畅销书排行榜”上的风云变幻，嘴角一丝不易察觉的坏笑。
“看一本好书，就是在和许多伟大的灵魂对话”。如果《ACM演讲集》仅仅保存着一位作者的灵魂，不可能被我如此看重。事实上，它收录了23位获奖者的22篇文章。代码寥寥无几，甚至是作为反面教材的多于实例；除了一两篇纯属学术论文的文章，余者也没有复杂的数学推导。然而就是这样一本似乎只是在空谈的书，让我了解到了计算机科学发展的黄金时代的情况和“上古”的计算机前辈科学家们的不朽的思想与伟大的探索。约翰·巴克斯（BNF范式设计者、Algol语言发明人），唐纳德·E·克努特（《计算机编程艺术》作者、Tex系统设计者），约翰·麦卡锡（人工智能先驱，Lisp语言发明人），看着这些熟悉的名字，阅读着他们充满智慧和神性的演讲稿，研究前辈们思想的结晶，真是乐事。
我对当代计算机的发展（尤其是国内）失望久矣：教育者们误人子弟，学生们急功近利，程序员们心浮气躁，整个国内软件业不成体统。步入计算机科学的殿堂后，我头脑中一直盘旋着许多疑惑——计算机科学是怎样发展的？科学家们都是怎样探索的？我应该如何学习？《ACM演讲集》给了我答案。其中每一篇文章都在总结前人努力的基础上打开崭新的视界，向我展示了前辈们创世纪般的工作。事实上，80年代之后，商业的发展严重阻碍了计算机科学的发展以及编程语言的进步，半个世纪前的文章仍然有着重要意义，人们仍然可以窥见大师们惊人的高瞻远瞩。

我评编程语言（chap1）

2007-05-18T12:40:00.000+08:00

2007-05-03 09:59:37 绛洞花主 (上海)

　　你牛，顶你一下。
　　问下豆瓣是用什么语言作的，有什么优缺点。

2007-05-03 11:51:01 guotie (南京)

　　c, python

2007-05-03 20:59:11 氷の鋭 (南京)

　　"问下豆瓣是用什么语言作的，有什么优缺点。"
　　
　　底层有C语言写的Cache。关于C语言我觉得没什么可说的——高山仰止，景行行止。表面上是所谓的“底层语言”“中级语言”，然而事实上它具有很强的抽象能力，几乎是Lisp思想的底层反映——这包括宏vs语法变换，函数指针vs lambda算子等等。运行效率没的说，开发效率其实也不像某些动态语言的支持者们所说的那样低下（你也不想想，那个语言的解释器、编译器不是用C实现的），开源社区有足够的工具（g字开头的一大堆啦）、经验、系统（比如sourceforge.net）支持，对于开源项目绝对可以大胆使用。
　　
　　前台页面服务器用的是Python。“实用主义”是Python的哲学。但这里的“使用”二字仅仅针对程序员（不像Smalltalk之流是针对所有人），如果你想在Python上找到归宿感，你必须首先是那些比Python还差的语言的程序员（也就是说，首先你得会编程，其次没学过Lisp 之类的变态）。然后你就可以充分享受Python带来的，自由（主要来自出色的语法设计）、高效（想想那300多个从C时代发展过来的内置库）的开发了。
　　但Python也是有缺点的，它并不是那种从语法层面上无所不能的语言（这也是它比Ruby弱的地方之一）。它的语法基于“人性化的”换行缩进，没有语句块的概念，词法定界也只是被迫加上的，在玩儿Lambda演算方面有实际的困难（虽然它几乎支持高阶函数）。不过人家说了，“实用主义” 吗，这点小毛病对于实际项目来说无所谓的啦；如果每个语言都像ML那样全是严禁的数学概念世界上还能剩几个程序员。

此博客重新开始更新

2007-05-17T21:37:00.000+08:00

此博客重新开始更新。名字换成"let focus='computer science' in here"，意为“把计算机科学绑定在这儿”。
改版后的博客将关注计算机科学更广泛的部分而不仅仅局限于算法和数据结构。主要关注编程语言设计和编译原理。接下来的文章将对我在“沉默期”设计的 Mazy 函数式编程语言进行介绍和讨论，以及自己阅读经典书籍的笔记。

此Blog已停止更新

2006-12-09T12:04:00.000+08:00

因为www.blogger.com技术水平有限，本博客已停止更新，新博客见
lichray.blogspot.com
新博客将成为lichray的全方位日志，已经建立完成。但以前发表在本博客上的文章不会随之移动，下面是其中一部分自觉优秀的原创文章列表：

Scheme语言

C语言

Python语言

Lua语言

软件工程

上帝是个程序员

献给新访客的一则笑话——古老，但很神奇

2006-10-21T19:44:00.000+08:00

诶，我的Blog已经很久没更新了——得菌痢住院5天啦，今天终于出来啦！
Lava-Lava平台上“科技自主创新网”部落的同仁们可能已经看到了我的Blog荣幸进入你们的“酋长推荐”标签页，但似乎没有人给我的文章留下评论。我估计这是大家都没有接触过Scheme语言的缘故。所以我决定写一篇这样的文章，让新来的访客们看一看Scheme时间的精彩——当然，我没有要贬低其它语言（除了Java）的意思，事实上我最喜欢的语言之一就是C。好了，不罗嗦了，让我们一起来推开Scheme那道门吧。

人物：XX大学计算机系的社友Go4——8呆，F1，老农和小四。
时间：“晚汇报”时间…
（老农在计算机系混的时间不短了，可惜技术一直没长进——连打电脑游戏都“不上档次”（小四语）。这不，昨天打CS又被F1欺负了，现在正郁闷着呢。）

老农（上网无聊中）：这年头，电脑好的人就是吃香啊~~（旁白）俺编程也差，游戏也差，废啦~~有了，上CSDN.net，找点文章进修一下。
F1：老农，怎么样，CS技术不行啊！好好练啊！
小四（推推眼镜）：老农伯伯！算了吧，我看你还是把编程学学好吧，哈哈，你那本《数据结构》好像还是新的吧？
（老农翻着最新的Blog文章，忽然眼睛一亮。）
小四：嘿，发现什么了？
老农（连忙把Firefox最小化）：没什么，又不是黄网激动什么？！
老农（旁白）：不错，就用这篇文章K.O.他们。
老农（满脸堆笑）：嘿，你们仨过来，我在网上发现一道数据结构方面的面试题目，想不想试试？
（正在上铺捧着SICP发呆的8呆忽然从发呆状态切换到亢奋状态，人啊~~）
8呆：废话，快说！
老农（奸笑中）：设计一个函数visit_tail，要求通过一次遍历找到链表中倒数第n个节点，然后从它开始用函数func例遍后面的所有链表元素，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。还有，不需要给出链表的其它操作函数。
8呆（再次切换回发呆状态）：无聊…这也能叫题目…
老农（怒）：那你做啊！
（8呆在他的SICP上写了点什么，然后很潇洒地离开了寝室）
老农（专向另两个人）：既然他不参加，那我们三个比吧。
小四、F1（信心实足）：那现在开始计时吧。
……
（老农把刚才背下来的代码改了改，花了3分钟抄在终端里）
老农（觉得时机移到）：我好了，你们呢？
小四（大喊）：解决解决！
F1：恩，我也好了，只是还没做单元测试。
（老农、小四：寒~~）
（3个人凑在老农的电脑上开始比拼）
老农：你们看，我是用C写的，已经测试过的，思想是，用两根指针，第一根先出发，相距n步后第二根出发。然后同时步进，直到第一根指针达到末尾，然后用func()函数对第二个指针开始的子链表进行例遍。
（小四和F1仔细一看，大笑不止。老农的代码如下（注释是笔者所加，其实是F1和小四看到各句时的反应）：）

typedef struct{ //哟，终于不用struct Node了，
int data;
Node * next;
} Node;
Node * visit_tail(iNode * head,int n,void (* func)(int cur)){ //K&R时代的函数指针，见到老佛爷啦！！

Node *pfirst; //吓，终于用到匈牙利命名法了（老农：寒~）
Node *psecond;

pfirst=head;

for(int i=0;inext;
}
psecond=head;
while(pfirst!=NULL) {
pfirst=pfirst->next;
psecond=psecond->next;
} //什么破编程风格，真实版初学者啊
for(int i=0;idata)
psecond=psecond->next;
}
} //靠，一个函数解决所有问题，高耦合啊！

老农（再怒）：小四少罗嗦！你的呢！
小四：在这儿，好好学学吧！
（大家一看，小四也用了C，但…好漂亮啊。代码如下（注释是小四的解释）：）

typedef int int
//没有C++一样“泛型”！
typedef struct {
T data;
Node * next;
} Node;

typedef struct {
Node * pre;
Node * curr; //当前结点与List绑定，不但可以分步例遍，还能保证正确初始化
} List;

void init_curr (List * l) {
l->curr = l->pre; //什么叫“编程风格”，知道不？！
}

void visit (List *l, void (* func)(T data)) {
while (l-curr) { //少用!=NULL
(* func)(l-curr->data);
l-curr = l->curr->next;
}
} //使用内联结点的公用访问函数，降低耦合

void index (List * l, int n) {
if (n) return NULL; //结点下标从1开始
init_curr(l);
if (n > 0) {
for (int i = 0; i <>curr = l->curr->next;
} //小四（自我陶醉）：漂亮啊
if (n < n =" -n;" tmp =" l-">curr;
for (int i = 0; i < tmp =" tmp-">next;
}
while (tmp) {
l->curr = l->curr->next;
tmp = tmp->next;
}
}
return l->curr; //方便用户，增强鲁棒性能
}

void visit_tail (List * l, int n, void (* func)(T data)) {
index(l, -n);
visit(l, func);
} //多清爽

老农（倒）：我的挽回面子计划就这么，完了…
小四（偷笑）：你还是面对现实吧…
F1：小四你先别得意，我的你们还没拜读过呢！
（大家跑到F1电脑前一看，先是被长度吓了一跳，然后，无语。）

package datastruct.fifi.com.baidu.hi; //加入我的数据结构Java包

//当然只有包内成员才能创建Node对象
protected class Node {
private Object data; //多态性，让你们的typedef去死吧！
private Node next;

//构造函数
Node (data) {
this.data = data;
}

//获取下一个元素
public Node next () {
return this.next;
}

//变换下一个元素，用户不能调用
protected void setNext (o) {
this.next = o;
}

//取数据
public Object getData () {
return this.data;
}

//换数据
public void setData (data) {
this.data = data;
}

//根据Effective Java的最高指导，要重写toString()方法
public String toString () {
return this.data.toString();
}

//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}

//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}

public class List {
private Node preFix;
private Node current;
private int size;

List () {
current = preFix = new Node();
size = 0;
}

//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}

//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}
}

public class List {
private Node preFix;
private Node current;
private int size;

List () {
current = preFix = new Node();
size = 0;
}

//定位函数
private void index (int i) throws IndexOutOfRangeException {
if (i > size || i < -size-1) { thows new IndexOutOfRangeException(0, size+1, i); } this.init(); if (i >= 0) {
for (int j=0; j < current =" current.next();" i =" -" j="0;" current =" current.next();" current =" current.next();">_< 。。。 F1：we得意。（3人正在争执着，忽然门“吱”的一声（什么破门）开了，8呆走了进来。） 8呆：吵什么呢，比完了没？我是第一吧？ F1、小四、老农：什么啊，你不是自顾自走了啦？！ 8呆（诧异）：我走之前已经写好啦。（8呆拿来他的SICP，只见上面写了一行Scheme代码：） (define (list-visit-tail l n func) (for-each (list-tail l n) func)) （编辑公曰：上面这段Scheme代码滴意思斯酱紫滴：先定义一个名为list-visit-tail的过程，然后用内置宏list-tail取list的后n位组成list返回，再用操作for-each进行例遍。）（完）结语：这个题目其实对于任何函数式编程语言来说都是一两句话。Scheme、Haskell它们都来自于世界上第二古老的语言Lisp，但它们的思想博大精深——基于lambda演算理论的函数式编程，古老，但很神奇。参考资料：

老农说的“这篇文章”：一次遍历找链表倒数第n个节点
8呆的书SICP：Structure and Interpretation of Computer Programs
命令式语言的劣势：为何 Java（以及很多其他编程语言）令人不爽
函数式语言的优势：为什么函数式编程至关重要？
Scheme入门推荐书：Teach Yourself Scheme in Fixnum Days
如果你还没学过编程的话：How to Design Programs
其它有关Scheme的东东详见：我的Scheme学习笔记(1 2 3 4 5)

上帝是个程序员——从《黑客帝国》看软件设计

2006-10-20T19:26:00.000+08:00

上个星期我把《黑客帝国(The Matrix)》三步曲完完整整看了一遍，联想到《UNIX程序设计的艺术》一书中所说的17条UNIX哲学，深感古老的UNIX确实是软件设计思想的集中体现。Robert Metaclf说过：“如果将来有什么技术取代了以太网，那么它仍会叫以太网。”也许，The Matrix的内部开发代号中就有"UNIX"这个单词吧！

模块性原则：写简单的，通过干净的接口可被连接的部件。相比UNIX，The Matrix绝对是一个超巨大的软件，它的设计中也充分体现了模块化思想：整个系统有后台数据库（这可是墨菲斯说的）用来存储任何物件；前台有和人脑后插座相连的输入/输出接口，当然程序还可以使用电话工作；前后台之间有由知情者们组成的控制程序，标准的MVC模式。
清楚原则：清楚要比小聪明好。The Matrix的源代码我们是没法儿研究啦。不过，整个人类世界居然能被显示在3个小小的液晶屏里，而且接线员告诉我们…他能…知道这儿有个金发美女，从这一点你应该能想像出The Matrix有多么的清晰。
合并原则：设计能被其它程序连接的程序。这个还用的着多罗嗦吗？天哪，与人类的物理接口，用手机可以和真实世界交流，通过固定电话进行接入和切断，还有那个设计近乎完美的、和外界传输意识的火车站，真是一应俱全
分离原则：从机制分离从策略，从实现分离出接口。The Matrix的实现相当复杂，但设计了很好的接口；看看墨菲斯他们使用的训练场吧，它其实是早期The Matrix版本的一个变型，程序员能很轻松地控制它（最拉风的是第一部中凭空制造的那两排枪，无敌了）这说明了The Matrix的接口设计非常简洁而有序。
简单原则：设计要简单；只有当你需要的时候，增加复杂性。The Matrix的简单恐怕初看电影的人体会不深：看这那些标志性的绿色字符就烦。但你仔细想想，这可是一个时间啊！从接线员的一些操作细节也能感受到The Matrix的简单——火线教学只需要搜索内容然后按下LOAD按钮，我晕。
节俭原则：只有当被证实是清晰，其它什么也不做的时候，才写大的程序。The Matrix的的在节俭上下的功夫我们很难研究，毕竟这只存在于源代码中。个人感觉，至少从电影上看是非常华丽的，不过那是为了票房而下的功夫。
透明原则：为使检查和调试明显更容易而设计。The Matrix的调试只提供了输出部分（安全的需要吗，设计师本人是不能搬演上帝的），在每艘飞船上都有一个GUI程序来检索它的调试信息，黑客们用它作了GIS，哈哈。
健壮性原则：健壮性是透明和简单的追随者。没有一个软件没有Bugs，但有的软件可以让Bug在关键时刻失去用武之地，比如那个火车站，即便是尼奥这样的超人也无能为力啊，只能从这个出口跑会另一个出口啊。
表现原则：把知识整理成资料，于是程序逻辑能变得易理解和精力充沛的。不知道设计师是怎样开发The Matrix的，不过从它那5个前世可以看出它的进步是卓有成效的。犯错误不要紧，把经验记下来是最重要的，不是吗？
最小意外原则：在接口设计中，总是做最小意外事情。当然The Matrix也有让人超意外的时候，比如莫罗恩手下那些打不死的程序们。但别忘了他们来自于黑客帝国的早期版本。后来的莫罗恩自己和开锁人不都是普通人吗？
沉默原则：当一个程序令人吃惊什么也不说的时候，他应该就是什么也不说。《UNIX程序设计的艺术》的作者对这个原则的解释有问题（或者是翻译问题）。沉默原则应当是这样：当一个程序按照用户已有的知识完成了工作是，他应该什么也不说。UNIX命令行的程序通通是这样，尤其是gcc。The Matrix是不是为一群人按照自己的意志控制另一群人而设计的，也不存在除维护人员以外的用户，当然不会“说”什么。
修补补救：当你必须失败的时候，尽可能快的吵闹地失败。这也就是The Matrix中偶尔出现的幻象、上帝、狼人的出现了就很快消失的原因。
经济原则：程序员的时间是宝贵的；优先机器时间节约它。无语了，The Matrix工作的硬件系统都是算法设计复杂度度量是使用的“理想计算机”，感觉起来一切都是原子操作，只有与人传输数据时有忽略不计的延迟。
产生原则：避免手工堆砌；当你可能的时候，编写可以写程序的程序。这个原则的前提是，系统本身必须是可以被自描述的，就像Lisp语言。The Matrix也是被高度自描述的，那些维护程序不都是用The Matrix本身创建的吗即便是莫罗恩或史密斯这样的大拿？利用系统本身工作可是黑客帝国的一大特色啊。
优化原则：在雕琢之前先有原型；在你优化它之前，先让他可以运行。这就是The Matrix有6个版本的原因——事实上人们讨论的最多的第一个版本就是一个原型，设计师自己也说，仅仅用作测试，后来“庄稼全死了”。
差异原则：怀疑所有声称的“唯一真理“。最后这个The Matrix版本有它的“唯一真理”，可惜设计师在努力之后仍然留下了尼奥这个“余数bug”。设计师是绝对的马克思主义者，也只有在他的眼中，世界是物质的。
可扩展原则：为将来做设计，因为它可能比你认为来的要快。The Matrix的可扩展能力具体有多强我们不得而知，不过在电影中它确实被扩展了：希安的程序员们为他们的训练场程序编写了原本不存在的应急保护模块，能让可能损坏人体的元素失去真实（什么是真实？）质地，否则尼奥第一次“跳楼”就要被摔死了。:)

《黑客帝国》绝对是一部不看人生不完整的电影，不但充满了哲理，而且对于UNIX/Linux的爱好者们而言很有感召力，不是吗？:)

Scheme数据结构——向量也疯狂

2006-10-19T19:24:00.000+08:00

学过数据结构的人都知道，一棵完全二叉树（除去最低层元素从左到右排列，其它的层都为满的）可以保存在一个数组中这个完全二叉树存储在vector中就像这样：#(4 6 2 8 7 3) 可以看出一个结点下标 i 与它的左右孩子结点下标 j1，j2具有如下关系： j2 = 2*i+1，j2 = 2*i +2 然后，我们通过调整数组上结点的排列，把它变成一个“二叉堆”。这里显示的是一个最大堆，即：对于(vector-length a) => n，当(< (+ (* 2 i) 1) n) => #t时，有(> (vector-ref a (+ (* 2 i) 1)) (vector-ref a i) => #t；当(< (+ (* 2 i) 2) n) => #t时，有(> (vector-ref a (+ (* 2 i) 2)) (vector-ref a i) => #t。
这么复杂的S-exp，说白了，就是每个结点的左右孩子结点（如果有的话）都小于这个结点。 知道了这些，我们就可以来考虑一下怎么把完全二叉树转成最大堆了。方法是，先根据公式求出第一个非叶结点下标(define n (/ (- n 1) 2))，然后比较左孩子结点(vector-ref a (+ (* 2 i)与右孩子结点(vector-ref a (+ (* 2 i)的大小，将较大者与(vector-ref a i)比较，如果更大就互换。然后对于(- i 1)，(- i 2)完成以上步骤，于是，最大堆就构造完成了。

调整结点8：

调整结点3：

调整结点8：最后，最大堆有什么用呢？废话，当然是堆排序了；我最喜欢的排序算法就是它，因为它充分体现了“数形结合”的思想。因为排序过程中整个堆都在大规模地变化（当然反应到数组上不是这么回事），所有就不再进行图解了；大致将一下即可：先将整个vector调整为最大堆，然后将堆顶的那个最大的元素与堆中最后一个元素互换，接着调整前 (- n 1) 个元素为最大堆，再将堆顶元素与堆中最后一个元素互换。。。如此反复（其实就是逐个排出最大元素），时间复杂度为O(n*log2 n)。

大致代码（缺少heep的实现）：
(define (heep-sort a)
(let* ((n (vector-length a))(tmp 0) (i (- n 1)))
(begin (make-heep a) ;调整a为最大堆
(when (> i 0)(set! tmp (vector-ref a 0))
(vector-set! a 0 (vector-ref a 1))
(vector-set! a 1 tmp)
(heep a i 0) ;在向量a上从下标0开始调整长度为i的一段为最大堆
(set! i (- i 1)))))) ;最好用尾递归代替循环

Scheme数据结构——list数组

2006-10-18T18:10:00.000+08:00

（By the way，我终于知道如何删除list的头节点了。必须要使符号指向一个头节点，再由它确定当前节点，否则无非实现元素“脱链”）

list数组，顾名思义，由list构成的数组（或矩阵），学名不明。它不是一种具体的数据结构，但常被用作表示其它数据结构。它的一般形式如下：
当然，这里的vector也可以是一个矩阵。用Scheme实现时，注意list不需要随机插入元素的功能，但能随机脱链，且只能从尾部插入（技巧：(set-cdr! (list-tail l (- (length l) 1)) obj)）——list中的数据往往是无序的。可以把它设计得更强，但并不实用。
下面讲它的两种典型应用。

一. 图的邻接表存储结构

用矩阵的第一列存储结点，第二列存储结点的号码，第三列保存此行所对应结点链接的边的结束结点号码（当然还可以再用一列保存权值）。这样说有点绕人，我们看个例子好了：
这是一个有向图。让我们看看它是怎样用邻接表存储的：
复杂吗？吓，一点也不。它可以用来对付边较稀疏的有向图。

二. 链表法解决哈希冲突

讲解哈希表关键字冲突的一般思路是建立哈希函数组，逐个调用。但这个方法有个明显缺点：如果把哈希表作为一种服务提供给操作对象的话用户就麻烦大了。用向量上链接的list来保存hash code相同的元素是个不错的办法。
例子：这个哈希表的元素是 a={16, 54, 66, 43, 29, 55...}，m=13，哈希函数为 h(K)=K mod m（省略了其它7个元素）：
用矩阵的第一列存储基本元素，多于的“同位素”保存在临时开辟的list中。这样的设计重点考虑了效率，比较使用，但会给元素的删除带精神分裂般的麻烦，插入元素也够戗；如果你追求程序的“漂亮”，可以把所有元都平起平坐地存储在list里，不使用矩阵，元素的删除操作全是脱链。

从上面两个例子可以看出，list数组主要用于解决稀疏的“同位素”的存储问题。确定“同位素”的同位存储性质（比如同hash code元素的平等地位）和必要性（比如有向图结点拥有边与其起始结点的偏序关系），是使用它的重要前提。

let, let* 和 letrec（转）

2006-10-17T18:35:00.000+08:00

使用 let, let*, letrec 都可以在当前环境中构造局部变量。这种变量的生命会延续到这个环境消失为止。

这就像 C 语言里的

{  int x = 10;
int y = 20;

foo(x,y);
}

但是有一点不同就是，Scheme 的 let 生成的环境是分配在堆里而不是像 C 那样分配在栈里的。所以 let 的局部变量有可能在 let 的 block 执行完毕以后还继续存在，只要有某些东西引用到它们。

这样我们可以制造一些返回函数的函数，这些函数拥有自己的状态记忆，而这些记忆并不是全局变量，它们有点像 C 函数的 static 变量。

下面是几个例子：

(define (function-gen n)
(let ((local-var 0))
 (lambda ()
   (display "The local-var is ")
   (display local-var)
   (newline)
   (set! local-var (+ 1 local-var)))))

(define f1 (function-gen 0))
(define f2 (function-gen 100))

(f1)
(f2)

函数 function-gen 接受一个参数 n，并且把它保存到自己的局部变量 local-var. 它返回一个新的函数，这个函数被调用就会打印 local-var 的值，并且把 local-var 的值加 1.

我们用 0 和 100 作为参数传递给 function-gen，生成了两个函数 f1 和 f2. 这是两个起点不同的计数器。f1 从 0 开始，而 f2 从 100 开始。每次被调用两个函数都打印自己的数字，并且加 1.

可见，f1 和 f2 所见到的 local-var 是两个不同的空间。也就是说，每次调用 function-gen，都会由 let 生成一个新的变量 local-var, 这个变量将一直伴随新生成的函数。

注意 let 里的 binding 是这样产生的。首先，进入 let 时，我们只看到外层的绑定，然后每个 let 绑定的右边被 eval，然后这些值被放到临时的一些空间，所有的右边都求值完毕后，这些值被一一赋给左边的名字。

如果我们的代码不是那么简单，我们在 let 里生成了一个函数。比如这样：

(define (func-gen)
(let ((x 10) (y 20))
 (lambda (a b)
       (+ x y a b))))

(define bar (func-gen))

func-gen 函数中被调用时，它在 let 空间中生成了一个函数，并且作为 func-gen 的返回值送到外层，它被绑定到最外层的环境中的 bar 变量。那么这个函数引用了这个环境，这个 let frame 不会被回收。

bar 如果在外层层环境被调用，那么它的名字绑定环境仍然是 let 里面的环境。也就是说，它仍然可以使用局部变量 x 和 y!

如果我们调用

(f 1 2)

就得到结果 33.

这相当于同时赋值。

所以在下面这种情况里，内层的 let 绑定 b 时，实际上使用的是外层的 x 在计算。

(let ((x 10)    ; bindings of x
   (a 20)))  ; and a
+----------------------------------------------------------+
| (foo x)                                 scope of outer x |
| (let ((x (bar))                           and a          |
|       (b (baz x x)))                                     |
|  +------------------------------------------------+      |
|  | (quux x a)                    scope of inner x |      |
|  | (quux y b)                    and b            | )    |
|  +------------------------------------------------+      |
| (baz x a)                                                |
| (baz x b)                                                |
+----------------------------------------------------------+

Scheme数据结构——简单二叉树

2006-10-15T18:27:00.000+08:00

终于把用Scheme写的二叉树发出来了，前两天网卡没钱拉。
层序例遍算法写出来了，可惜用不了——没法儿用Scheme实现队列！我折腾了半天，写出这么一个怪物：
(define queue list)
(define (queue-push! q o)
(set-cdr! (list-tail q (- (length q) 1)) (cons o null)))

可pop还是实现不了——不知道怎么删除pair，于是放弃。
把简单二叉树的实现贴在这儿吧，虽然没有一点实用价值。

(define null '()) ;用null代替空list

(define (child data left right) ;用它来申明一个“孩子”
(cons data (cons left right)))
(define (child? o)
(and (pair? o) (pair? (cdr o))))
(define (child.data o)
(if (child? o)
(car o)))
(define (set-child.data! o data)
(if (child? o)
(set-car! o data)))
(define (child.left o)
(if (child? o)
(cadr o)))
(define (set-child.left! o p)
(if (child? o)
(set-car! (cdr o)) p))
(define (child.right o)
(if (child? o)
(cddr o)))
(define (set-child.right! o p)
(if (child? o)
(set-cdr! (cdr o) p)))

;先序例遍递归版，用一句(if (not (null? o)...)省了不少判断
(define (child-tree-pre o func)
(if (not (null? o))
(begin
(func (child.data o))
(child-tree-pre (child.left o) func)
(child-tree-pre (child.right o) func))))
;后序例遍
(define (child-tree-post o func)
(if (not (null? o))
(begin
(child-tree-post (child.left o) func)
(child-tree-post (child.right o) func)
(func (child.data o)))))
;。。。中序~~可怜没有层序和分步例遍~~
(define (child-tree-mid o func)
(if (not (null? o))
(begin
(child-tree-mid (child.left o) func)
(func (child.data o))
(child-tree-mid (child.right o) func))))

比Boyer-Moore更快的字符串查找算法（转）

2006-10-11T22:15:00.000+08:00

字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。但是BM算法还不是最快的算法，这里介绍一种比BM算法更快一些的查找算法。

例如我们要在"substring searching algorithm"查找"search"，刚开始时，把子串与文本左边对齐：

substring searching algorithm
search
^

结果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的 'i')。

显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下一步匹配到了，这个字符必须在子串内。所以，可以移动子串，使子串中的最右边的这个字符与它对齐。现在子串'search'中并不存在'i'，则说明可以直接跳过一大片，从'i'之后的那个字符开始作下一步的比较，如下图：

substring searching algorithm
　　　　search
　　　　^

比较的结果，第一个字符就不匹配，再看子串后面的那个字符，是'r',它在子串中出现在倒数第三位，于是把子串向前移动三位，使两个'r'对齐，如下：

substring searching algorithm
　　　　　 search
　　　　　　　^

哈！这次匹配成功了！回顾整个过程，我们只移动了两次子串就找到了匹配位置，是不是很神啊?!可以证明，用这个算法，每一步的移动量都比BM算法要大，所以肯定比BM算法更快。

下面是这个算法的c代码。注意我假设了每个字符的值都介于0-127之间（即纯ascii码）。

char *qsearch(const char *text, int n, const char *patt, int m)
{
// get the length of the text and the pattern, if necessary
if (n < 0)
n = strlen(text);
if (m < 0)
m = strlen(patt);
if (m == 0)
return (char*)text;

// construct delta shift table
int td[128];
for (int c = 0; c < 128; c++)
td[c] = m + 1;
const char* p;
for (p=patt; *p; p++)
td[*p] = m - (p - patt);

// start searching...
const char *t, *tx = text;

// the main searching loop
while (tx + m <= text + n) {
for (p = patt, t = tx; *p; ++p, ++t) {
if (*p != *t) // found a mismatch
break;
}
if (*p == 0) // Yes! we found it!
return (char*)tx;
tx += td[tx[m]]; // move the pattern by a distance
}
return NULL;
}

注：这个查找算法称为Sunday算法，它是BM算法的一种改进型。

Scheme数据结构——神奇的pair

2006-10-09T21:15:00.000+08:00

Scheme中提供了两种可以存储泛型数据的数据结构——list和vector。list其实是一个链表，它是由pair实现的。学了Scheme很久才发现，原来pair其实是其它语言中我们超常用的Node（节点）！这下我总算理解了Scheme是怎样架起数据结构的了。

一. 链表（内部已实现）

每个pair的左值存储数据，右值存放指针（Scheme中cons值即引用）：
然后用指针指向（其实是赋值）下一个pair，链中最后一个为null（空值）：
这个语法树转换成Scheme代码就是(value . (value . (value . null)));当然只是“意思”一下，实际不可能有同名符号。

二. 二叉树（正在编写中…）

又一个用节点连起来的基本数据结构。每个二叉树child（孩子）可以这样设计，用第一个pair的左值保存数据，右值为另一个pair，它的左右值表示孩子的指针：
代码为(value . (left . right))
然后，n个这样的child组合为一棵二叉树。同样，没有孩子时指针为null：

上面这棵树的代码大致是这样：(value . ((value . ((value . (null . null)) . (value . (null . null)))) . (value . (null . null))))。
我的二叉树实现正在写着，面前至少可以用(child)代替(cons(cons))申明孩子节点，下一步编写tree的整个数据结构支持，最好能支持一次例遍。

有了链表和二叉树，队列，栈，线索二叉树之类就都能直接实现了。其它的数据结构如集合，树，图，HashTable等等多是由向量＋pair构成的，不典型，暂且不提。

谈谈数组元素左旋问题（下）

2006-10-07T18:01:00.000+08:00

上篇中，我给出了一些解决数组元素左移问题的不符合要求或很慢的解法。在下篇中，我将讲解3个很有“来头”（至少出现在《编程珠玑》里了:)）的O(n)级算法。
第一个算法思想上和我曾经想到的一个直接插入元素的算法基本相同，也是通过递归地逐个放置数组元素来左旋数组的。只不过我使用的方法是逐个临时测试是否可以按照公式放置，而这个算法经过周密计算，直接给出了符合各种情况的通用下标计算方法：
对于任意的元素下标 i，它的新下标 i` = ((k - m) + i ) % k。
代码如下：

//先求最大公约数，其实有很多方法，这个叫“辗转相除法”
int facter (int i, int j) {
while (i != j) {
if (i > j) {
i -=j;
} else {
j -= i;
}
}
return i;
}
//元素互换函数，无聊。。。
void swap (int *n1, int *n2) {
int tmp;
tmp = *n1;
*n1 = *n2;
*n2 = *tmp;
}
void turn_left (int *a, int m, int k) {
int i, tmp, f;
k = k % m;
if (k == 0) {
return;
}
f = facter(m, k);
if (f == 1) {
i = 0;
do {
i = (i+k)%m;
swap(a, a+1);
} while (i != 0);
} else {
for (i = 0; i < tmp =" i;" tmp =" (tmp+k)%m;" href="http://lichray.blogspot.com/2006/09/blog-post_25.html">那篇文章中用图示详细分析了数组元素的位移过程。如果你想找到一点新的灵感，可以把一些代表元素的卡片（凯库勒？！）用线穿起来反复地排，看看开始时和结束时，数组产生了哪些变化：
似乎看不出什么端倪。。。但如果把每种颜色的线都反序一下，
呵，很漂亮啊。再分析一下——原来，要让数组元素左旋m位，只需先将数组全部反序，然后将下标0~m-1和m~k-1的两部分分别反序就行了！最快的算法居然就这么简单！
用Python表示一下（这个代码是可运行的）：

def turn_left (a, m):
a.reverse()
a[:m].reverse()
a[m:].reverse()
return

C代码就不用写了吧，用上面那个swap()函数＋循环将数组反序而已啊。
最后一个方法，说真的，我没看懂。。。据说利用了数论知识，也很快，原理和本文第一个其实区别不大，只是计算新下标的算法更先进了：

/*照抄编程珠玑，伪代码（汗~），懒得翻译。n是数组长度，r是左旋位数，gcd()函数计算最大公约数，for后面的式子表示i的取值范围。*/
for i = [0, gcd(r, n))
t = x[i]
j = i
loop
k = j + r
if k >= i
k -= n
if k == i
break
x[j] = x[k]
j = k
x[j] = t

还得好好学数学啊！理解这个会有时！
真希望所有的程序员（代码书写er就算了）人手一本《编程珠玑》（Programming Pearls），书中自有黄金物，早日摆脱索然无趣的代码！

Scheme学习笔记（五）

2006-10-01T17:47:00.000+08:00

（这应当是最后一篇了，明天来继续数组左旋...）

八. 宏

MIT-Scheme的宏定义：

(define-syntax 宏名
(syntax-rules()
((模板) 操作))
. . . ))

在操作时，先用let绑定参数，然后用lambda定义过程：

(let ((本地操作 (lambda 参数 宏主体 ...)))
(lambda (e r)
 (apply 本地操作 (cdr e))))

(define-syntax start
 (syntax-rules ()
     ((start exp1)
         exp1)
      ((start exp1 exp2 ...)
 (let ((temp exp1)) (start exp2 ...))) ))

实现的短小的定义：

(define-macro MACRO-NAME
(lambda MACRO-ARGS
MACRO-BODY ...))

九. 结构

结构模板定义：(defstruct 结构名属性（不构成list）)

(defstruct tree height girth age leaf-shape leaf-color)

新建结构：(make-结构名属性符号值符号值)

(define coconut
(make-tree ’height 30
’leaf-shape ’frond
’age 5))

使用结构：(结构名.属性名结构对象);返回属性值，(set!结构名.属性名结构对象新属性值);更改属性值

(tree.leaf-shape coconut) => frond
(set!tree.height coconut 40)
(tree.height coconut) => 40

defstruct本身未提供，需要宏来定义，具体不再写出。

十. 面向对象

Scheme标准默认未提供！我看也用不着。

祝所有Sceme的爱好者们早日摆脱无聊和世俗的coder世界！

Scheme学习笔记（四）

2006-09-29T19:03:00.000+08:00

（下一篇是最后一篇，讨论宏，结构和面向对象（其实没什么用））

四. 流程控制

Scheme中只有if操作是内置的，其它用宏实现。
应尽量用尾递归代替循环。

(if (测试表达式) (操作) (else操作))
由多个语句构成的操作用(begin)语句组合

(when (测试表达式) (多个操作))
(when (非测试表达式) (多个操作))
其它的操作式不必用begin组合
case语句：

(case c
((#\a) 1)
((#\b) 2)
((#\c) 3)
(else 4)) => 3

逻辑表达式操作：
and在无非比较时返回后一个值：(and 1 2) => 2
(and #f 1) => #f
r在无非比较时返回前一个值：(or 1 2) => 1
(or #f 1) => 1

六. 递归

不能工作的代码，因为let或let*会将操作名绑定到各自的词法定界，导致互相递归调用的函数不能互访：

(let ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))

把绑定操作换成letrec即可。
由begin引导的语句序列返回最后一个语句的值。
命名let可简化局部递归调用：

(let countdown ((i 10))
(if (= i 0) ’liftoff
(begin
(display i)
(newline)
(countdown (- i 1))))) ;输出一个整数递减过程中的每个值

迭代器(for-each 操作 (被操作list))
迭代器(map 操作 (被操作list))，返回list中每一个被操作项构成的list（python里的那个函数的同名被复制品）。

Scheme学习笔记（三）

2006-09-28T17:34:00.000+08:00

（另一些参考资料：Scheme语言介绍，语言概要（上）（下））

三. 过程

lambda形式：((lambda 参数 (过程)) 可选的实际参数)

((lambda (x) (+ x 2)) 5) => 7

带括号时为形式参数，否则被认为是一个参数list

((lambda someFriends ; 参数周围没有括号 ! (DisplayLine "hi there " someFriends)) 'mole 'bear 'tiger)

定义函数用define：(define add2 (lambda (x) (+ x 2)))，省略lambda：(define (add6 x) (+ x 6))
谓词(procedure?)来测试一个对象实际上是否为过程
函数名即操作名：(add2 9) => 11
(apply 函数名参数列表)强制调用。
过程的套嵌定义遵循词法定界。

五. 词法定界（下篇讲“四”）

define定义当前定界以下对象。
(set!)仅改变当前定界中的对象：

(define counter 0)
(define bump-counter (lambda ()
(set! counter (+ counter 1))
counter))

(bump-counter) => 1
(bump-counter) => 2
(bump-counter) => 3

相对define，(let (定义局部变量) (其它代码))绑定局部变量到过程：

(let ((x 2) (y 5)) (* x y))  =>  10

let*内的定义不改变上级定界定义的局部变量
```
letrec的定义可互交引用？
```

(letrec ((even?
             (lambda(x)
             (if (= x 0) #t
                     (odd? (- x 1)))))
         (odd?
             (lambda(x)
             (if (= x 0) #f
                     (even? (- x 1))))))
(even? 88))  =>  #t

```
letrec帮助局部过程实现递归。
```
非标准的(fluid-let)不改变上级定界变量却引作当前定界局部变量——无聊。。。

(fluid-let ((counter 99))
(display (bump-counter)) (newline)
(display (bump-counter)) (newline)
(display (bump-counter)) (newline))
输出100，101，102，但原counter不变。

Scheme学习笔记（二）

2006-09-27T18:18:00.000+08:00

（都忘了说了，我复习用的教材是Teach Yourself Scheme in Fixnum Days，还有一本The Scheme Programming Language也很好，但太长，没看过）

2. 复合类型

比较谓词：

(eqv?   (list 'a) (list 'a)) ; 它们 "看起来一样"，
;()
(eq?    (list 'a) (list 'a)) ; 存储在不同的内存单元中。
;()
(equal? (list 'a) (list 'a))
;#t

字符串：申明(define str "This is a string.")
用字符申明：(string #\h #\e #\l #\l #\o) => "hello"
(string-ref 字符串位置（整数）)返回字符串该位置上的字符
(string-append "E " "Pluribus " "Unum") => "E Pluribus Unum"
改变字符串（重新赋值）(string-set!)
(string-length "mumble") => 6

向量（貌似数组）：值以"#"开头
申明(vector 0 1 2 3 4) => #(0 1 2 3 4)或(make-vector 长度)

对（不知道怎么翻译pairs这个词~~）
分为左右值，左值叫car，右值叫cdr，用他们作操作符获取左右值
申明(cons 左值右值)
(cons 1 #t) => ’(1 . #t)
(set-car!)，(set-cdr!)
重要！经常右值套嵌！(cons 1 (cons 2 (cons 3 (cons 4 ’()))))形成list：(list 1 2 3 4)

list（太有名，懒得翻译）

list操作：取值(list-ref)
list-tail 通过除去前面的 n 个元素来获得一个子表
添加元素(append)
(null?) 检查它的操作对象是否是空表。
长度(length)
member 和 memq 将返回它的 car 是一个指定元素的一个子表。
查找(assoc 'LittleBear '((HappyMole vampire) (LittleBear banshee) (LittleTiger troll))) => (LittleBear banshee)

类型转换：(原类型-新类型对象)
类型转换方式非常自由：

(string->number "16") => 16
(symbol->string ’symbol) => "symbol"
尤其是这个：
(string->list "hello") => (#\h #\e #\l #\l #\o)

Scheme学习笔记（一）

2006-09-26T18:55:00.000+08:00

（写这个文档并非我初学Scheme，只是为开始全面使用它作点复习准备）

一. HelloWorld

Scheme语法即抽象语法树，只有仅有的几个内部语法支持。
;开启一行注释
用括号进行文法定界，第一项为操作，空格（换行）分割操作对象，如：

(diplay "hello, world!")
即对"hello, world!"字符串进行 display 操作。

Scheme和Lisp一样是自描述的，脚本用 .scm 作为后缀，进入解释器后，使用(load "文件名字符串")启动程序，用(exit)退出解释器。

完整程序：

(begin (display "hello, world!") (newline));newline用来刷新缓存

二. 数据类型
1. 简单类型

布尔值：有两个取值，#t和#f
操作(类型名? 变量)返回一个布尔值，确认该变量是否为此类型。如：

(boolean? #t) => #t
(boolean? 32) => #f

宏(not 布尔值)返回这个布尔值的反取值。如：

（not (boolean? #t)) => #f

数字：分为complex，rational，real，integer，但申明时不必指出。
(= 操作对象1 操作对象2)操作仅用于比较类型相同的变量值是否相同；(= 43 43) => #t，但(= 43 "ok")会报错。
(eqv?)操作是(=)的范型版本
指数运算(expt 2 3) => 8，取绝对值(abs -7) => 7
字符：以#\开头的单个字符

(char=? #\a #\a) ? #t
(char=? #\a #\b) ? #f

忽略大小写比较：(char-ci=? #\a #\A) => #t
大小写转换（不影响原值）(char-downcase #\A) => #\a，(char-upcase #\a) => #\A
符号：编译原理中的东西，可作变量名，用(quote)申明，(quote a) => 'a
变量不与其类型绑定：

(quote abc) (define xyz 9) (set! xyz #\c)

关于数组左移问题的一个新想法

2006-09-25T17:39:00.000+08:00

本来要继续写数组左旋下篇（上篇在此）的，今天在课堂上忽然想到一个新办法：既然可以证明每一个元素的新位置是((k - m) + i ) % k，我何不再仔细分析一下数组的直接移动过程？
对于k = 5，m = 2：
#注：蓝色线表示元素向右的移动过程，绿色表示向左的移动过程。
不难发现，向右移动时，元素下标从 i 改变到 i + k - m，而向左移动时是 i - m（显然）。
再验证一下吧：为什么这个用了两次直接移动？似乎 k % m == 0 时就需要做 m 次，否则要做1次。
没错。但算法写得可不能如此精神分裂——这个现象肯定有更深层次的原因。
再演算一下，终于弄明白了：每种方向的移动其实是个循环过程，每次寻找 k 中可存放元素的下标位置；当期望的下标大于 k 时，元素就要向反方向找位置了。
理清了算法的操作过程，大致的想法也就成型了：有一个分两种情况找位置的递归函数，当 k % m == 0 时循环调用它 m 次，当 k % m == 1时一次即可。比如：
显然这个算法只进行了 k 次赋值（计算次数可以忽略不计），效率应当非常高。
具体代码等我写完《谈谈数组左旋问题（下）》再说吧！

我设计的Lua数据结构List的接口

2006-09-23T20:54:00.000+08:00

代码还没有测试完，先把接口并注释发一下，将来和着代码一起发看起来很不方便。
设计参考了Python的相关函数，但比Python更强。不过python中的数组分片功能不知道能否真的实现，如果不行我只好用其它函数对分片功能的支持来代替。

--域，没有多余的域
List = {n = 0}

--静态方法接口
function List.new (...) end --构造函数，将整个参数列表转为List
local function List.cons (table) end --内部构造函数，将表转为List

--成员方法接口
function List:insert (item, n) end --在位置n之前插入item，默认插在List头部
function List:append (item) end --在list尾部插入item，等价于insert(item, list.n)
function List:remove (item) end --弹出第一个等于item的项并返回
function List:pop (n) end --弹出下标为n的项并返回，默认弹出末项，pop(0)等价于pop(1)
function List:index (item) end --返回第一个值为item的项的下标
function List:qindex (item) end --对于已排序list使用二分法查找
function List:count (item) end --返回list中该item的出现次数
function List:sub (from, to) end --返回从from到to的子list，下标为from的项不包括在内；from默认为0，to默认为list.n
function List:subl (from, l) end --等价于sub(from, from+l)
function List:cut (from, to) end --从list删除下标从from到to的子list并返回...
function List:cutl (from, l) end --等价于cut(from, from+l)
function List:extend (list) end --直接在self后添加list子列表
function List:reverse () end --倒排这个list
--function List:reverse (from, to) end #如果sub函数不能实现，这个功能就十分必要了
function List:sort (func) end --接受一个函数，它比较两个参数arg1
function List:qsort (func) end --sort()的快速排序版本
function List:bsort (func) end --sort()的基数排序版本，要求所有项都为正整数
--下面3个函数是python中的同名函数，充作迭代器
local function List:map(func)
local function UNM () end --每项取负访问器
local function EXP2 () end --每项取平方访问器
local function EXP3 () end --每项取立方访问器
end
local function List:filter(func)
local function DEL (item) end --返回并删除所有等于item的项的过滤器
local function EQUAL (item) end --返回所有等于item的项的过滤器
local function MORE (item) end--返回所有大于item的项的过滤器
local function LESS (item) end--返回所有小于item的项的过滤器
end
local function List:reduce(func)
local function MAX (pre, next) end --求最大递归访问器
local function MIX (pre, next) end --求最小递归访问器
local function MUL (pre, next) end --求list各项之积递归访问器
local function SUM (pre, next) end --求list各项之和递归访问器
local function SUM_MAX (pre, next) end --求最大子序列递归访问器
end

赶快写~~赶快写~~
×补充：我已经有办法解决数组分片问题了——给list加两个域：_stat和_end，再使用函数代理访问下标，玩“虚拟下标”即可！

极度经典的二分法搜索

2006-09-22T18:12:00.000+08:00

很easy。闲着无聊写出来。建议背下来。

#define datatype
#define ERROR -1

int bsearch (datatype * arr, int n, datatype obj) {
int l = 0;
int u = n-1;
int m;
while (l <= u) {
m = (l+u)/2;
if (arr[m] <>
l = m+1;
} else if (arr[m] == obj) {
return m;
} else {
u = m-1;
}
}
return ERROR;
}
这么简单注释就免了吧，哈哈~~

《称球问题》的完整代码

2006-09-21T18:09:00.000+08:00

晕死，上次发的那篇文章居然忘了给代码。现在把它贴出来，顺便加点注释。
（最近拼命写Lua数据结构实现中...）

#metga.py
#useage: python metga.py datefile
import sys
import string

#比较结果代码（左盘?右盘）
HEAVY = 1
LIGHT = -1
EQUAL = 0
QUESTION = 0 #问题球的问题
ANSWER = ""

#球的数据结构
class Ball:
def __init__ (self, weight):
self.weight = weight
self.number = 0

#求总质量
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp

#天平函数，计算左右盘质量返回比较结果
def metage (leftBalls, rightBalls):
left = sum(leftBalls)
right = sum(rightBalls)
if left > right: return HEAVY
if left < style="color: rgb(51, 51, 255);">return LIGHT
return EQUAL

#对球进行预处理，判断问题球是轻是重
def pre (balls):
global QUESTION
n = len(balls) / 3
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
statu = metage(parts[0], parts[1])
if statu == EQUAL:
QUESTION = metage(parts[2], parts[0])
return balls[2*n:]
QUESTION = statu
if metage(parts[0], parts[2]) == EQUAL:
return parts[1]
else:
return parts[0]

#递归地分3片称球
def test (balls):
l = len(balls)
if l == 1:
return balls[0].number
n = l / 3
if l < n =" 1" parts =" [balls[:n]," statu =" metage(parts[0]," style="color: rgb(51, 51, 255);">if statu == EQUAL:
return test(balls[2*n:])
elif statu == QUESTION:
return test(balls[:n])
else:
return test(balls[n:2*n])

#读取数据文件（内容为n个数字，每个一行，其中有一个与其它不等）
weight_list = map(string.atoi, open(sys.argv[1]).readlines())
ball_list = map(Ball, weight_list) #创建球组成的list
i = 1
for ball in ball_list: #初始化下标
ball.number = i
i += 1
if QUESTION == 1:
ANSWER = "heavier"
else:
ANSWER = "lighter"
print "The No.%d ball is %s than others." % (test(pre(ball_list)), ANSWER)

可恶的Blogger对于程序的排版支持约等于无，忙死我了。等我学完编译原理，我一定要开发一个JavaScript实现的词法分析器！

参考AllStartFromGame写了一个排列组合算法

2006-09-20T17:56:00.000+08:00

--昨天想了半个小时才想到的一个不错的方法。
--Lua果然号称“只用表的Scheme”，库基本没有。
--代码写得很零乱，还有问题——该死的Lua默认变量为全局，搞得递归有问题。
--不过想法还是很强的，把书本上的知识扩展了一下。
--下次我来扩充一下库，顺便把这个东西改写一下，至少让它能跑起来。

function turn_left (list) --数组左移函数
table.insert(list, list[1])
table.remove(list, 1)
end
function table.extend (t1, t2) --Python中的同名函数
for i = 1, table.getn(t2) do
table.insert(t1, t2[i])
end
end
function list_all (...) --启动函数，接受n个参数作为待排列的项
h_result = list_half(arg)
table.extend(h_result, reverse(h_result))
return h_result
end
function reverse (list) --数组假反序（返回一个新数组）
temp = {}
for i = 0, table.getn(list)-1 do
table.insert(temp, list[table.getn(list)-i])
end
return temp
end
function list_half (list, n) --列表半个排列组合
result = {} or result --保存结果的二维数组
tmp = {list[1], list[2]} or tmp
if n == nil then --处理起始情况
list_half(tmp, table.getn(list)-1)
end
if n == 1 then --处理基准情况——最终排序
for i = 1, table.getn(tmp) do
turn_left(tmp)
table.insert(result, tmp)
end
return result
else --递归列出最一般的排序
table.insert(tmp, list[table.getn(list)-n])
for i = 1, n do
turn_left(tmp)
list_half(tmp, n-1)
end
return result
end
end

找到的一个八皇后问题Python版解法

2006-09-18T18:27:00.000+08:00

原文称参考了All Start From A Game。
觉得有参考价值，虽然好像还不够快和简洁。以后我来自己写一个递归版的罢。
排版了一下，加了点注释。

size = 8 # 棋盘大小
EMPTY = "O" # 空位
QUEEN = "X" # 皇后

# 查看棋盘的信息
def show_board(cols):
for i in range(size):
for j in range(size):
if j == int(cols[i]) - 1:
print QUEEN,
else:
print EMPTY,
print "\n",

# 检测棋盘上皇后摆法是否合法
# return:
# True(不冲突), False(有冲突)
def check_board(cols):
for i in range(size - 1):
for j in range(i + 1, size):
if j - i == abs(int(cols[j]) - int(cols[i])):
return False
return True

# 得到全排列
def permute(seq):
seqn = [ seq.pop() ]
while seq:
newseq = []
new = seq.pop()
#print "seq:",seq,'seqn', seqn ,'new', new
for i in range(len(seqn)):
item = seqn[i]
for j in range(len(item)+1):
newseq.append(''.join([item[:j],new,item[j:]]))
seqn = newseq
#print 'newseq',newseq
return seqn

#测试代码
if __name__ == "__main__":
solve_count = 0
numbers = ''.join([str(i) for i in range(1, size + 1)])

for x in permute(list(numbers)):
y = list(x)
if check_board(y):
solve_count += 1
show_board(y)
print "\n",

print "found %i solves." % solve_count

谈谈数组元素左旋问题（上）

2006-09-17T22:23:00.000+08:00

终于把《编程珠玑》那本书给买来了。第一章2.3提出了一个“数组元素左旋问题”，《程序员》杂志上出过，描述如下：
对于有K个元素的数组int a[K] = {...}，写一个高效算法将数组内容循环左移m位。比如：int a[6] = {1,2,3,4,5,6}循环左移3位结果是{4,5,6,1,2,3}。注：不允许返回其它内存空间，但可使用少许变量。
《程序员》上面给的解答抄自书后答案，网友给出的两次倒排算法抄自书上解法1~~晕死。
对于这个问题有已经有不少解决办法了。我上个星期教网友算法时讲到了这个问题，现在把这些算法整理出来罢。
先将一个不符合要求但很基本的想法：先在数组后扩充数组的前一部分，然后再删掉数组自己的前一部分。用Python表示一下：
def move(a,m):
a.extend(a[:m])
return a[m:]
这个算法用C来实现我用了溢出的方法获得了更多内存（没必要管它能否通过编译），然后直接返回一个假的数组首地址。
int * move (int *a, int k, int m){
for (int i = 0; i <>
*(a+k+i) = *(a+i);
}
return (a+m-1);
}
很甩是不是？太猥琐了（但它说明了一个问题：大家都赞扬动态语言灵活，其实C也很灵活）。
更合适一点的做法是用一个线形数据结构保存前半部，再将原数组左移，最后将前半部分加回去。用Python表示一下（其实和上面那个也没多大区别）：
def move (a, m):
j = i = 0
tmp = []
while i <>
tmp[i] = a[i]
a[i] = a[i+m]
i += 1
while j <>
a[j+m] = tmp[j]
i += 1
return a #其实数组已改变，这句可以不要
后悔了——实在是没有比这更别扭的Python代码了~~改成C就免了吧，初始化tmp是把长度设为m，编译时要加这个参数：-std=c99（gcc）。
好了，我就不再无聊了，开始讲点正经的吧：在原数组上操作。
先回忆一下冒泡排序法：当处理一个处在最左边但又是最大的项时，这个项是怎样移动的？
在纸上画一画——哦，它和每个元素交换，然后到了最右边……等等，呓？其它的项的顺序都没有变？！整个数组左移了！
那么，我们第一个符合要求的答案就出来了：把数组当成是反排序的，从最左边进行m次冒泡即可！
吸取教训，我还是写C代码吧：
int * move (int a[], int k, iny m) {
for (int j = 0, j <>
for (int i = 0; i <>
int tmp = a[i+1];
a[i+1] = a[i];
a[i] = tmp;
}
} //算了，不写返回语句了
}
嗯，两层循环，照书上的说法这个算法的时间复杂度应当是O(n2)——但是，那个m好像不足k吧？可以认为是O(n*m)，但这样说是不严密的，因为O()仅处理上界情况。
好了，不多罗嗦了，下篇将揭晓真正有效率的算法——3个都是O(n)级的。