基于消息传递的 Scheme OOP

续上次的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)

　;; 纯属写着玩儿，尚未最终决定的版本已经与此差别很大，比方说 第二章。
　;; 因为修改麻烦，本博客有关 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 修订稿

这次把 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 第一稿

我设计的 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 二者的结合，列表领悟也有了；
其它一些纯属使语言更“漂亮”的小改动不值一提，感兴趣的自己看吧。

OOP 诡异教程（下）

这是最终确定的 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 介绍及源码分析

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

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

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

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

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

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

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

1. 全局操作，绑定在全局对象 Functional 上，主要是高阶函数操作和列表操作，所谓库安装即把这些内容可选的、安全地复制到全局环境
   
2. 函数扩展，实现特殊高阶函数特性的工具（特供内部）
   
3. 语法扩展，绑定在 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 的命名，它们是：

1. map(f, [x1, x2...]) = [f(x, 0), f(x2, 1), ...]
   
2. foldl, reduce(f, init, [x0, x1, x2]) == f(f(f(init, x0), x1), x2)
   
3. filer, select('%2', [1,2,3,4]) -> [1, 3]
   
4. foldr(f, init, [x0, x1, x2]) == fn(x0, f(x1, f(x2, init)))
   
5. some(f, [x1, x2, x3, ...]) == f(x1) || f(x2) || f(x3)...
   
6. every(f, [x1, x2, x3, ...]) == f(x1) &&amp;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 的表现。

Mazy 编程语言介绍

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

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ō是什么意思。

> 删除

我评编程语言（chap1）

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那样全是严禁的数学概念世界上还能剩几个程序员。

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

终于把用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))))

Scheme数据结构——神奇的pair

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构成的，不典型，暂且不提。

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

上篇中 ，我给出了一些解决数组元素左移问题的不符合要求或很慢的解法。在下篇中，我将讲解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），书中自有黄金物，早日摆脱索然无趣的代码！

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

本来要继续写数组左旋下篇（上篇在此）的，今天在课堂上忽然想到一个新办法 ：既然可以证明每一个元素的新位置是((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的接口

代码还没有测试完，先把接口并注释发一下，将来和着代码一起发看起来很不方便。
设计参考了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，再使用函数代理访问下标，玩“虚拟下标”即可！

《称球问题》的完整代码

晕死，上次发的那篇文章居然忘了给代码。现在把它贴出来，顺便加点注释。
（最近拼命写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写了一个排列组合算法

--昨天想了半个小时才想到的一个不错的方法。
--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

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

终于把《编程珠玑》那本书给买来了。第一章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)级的。

一个线形复杂度的菲波那契函数

所谓菲波那契数列，就是这个东西：1,1,2,3,5,8...题目为，写一个函数fib(int n)给出数列中某个数的下标，返回这个数。
菲波那契函数的数学定义为fib(x)，x=1 ? fib(x)=1 : fib(x)=fib(x-1)+fib(x-2)。
只用这个就可以给出解答：
unsigned long fib (int x) {
if (x > 2) {
return fib(x - 1) + fib(x - 2);
} else {
return 1;
}
}
测试函数如下：
int main () {
int arg;
printf("Input the length:");
scanf("%d", &arg);
printf("fibonacci(%d)=%lu\n", arg, fib(arg));
return 0;
}
但是，学过算法的人都知道，这个算法的时间复杂度是O(n2)级的，慢的要命。教科书上给出了循环方法的解答。（注：这个解答有一个超变态的一句话版本，知道的人请跟贴）
事实上，确实可以给出线形复杂度的菲波那契函数，原理来源于数列本身的性质。我大概写了一下，程序本身不好看，但肯定不会更快了：
#include
int i = 3;
unsigned long fib (int x, int y, int n) {
if (i <= n) { i++; return fib(y, x + y, n); } else { return y; } } int main () { int arg; printf("Input the length:"); scanf("%d", &arg); printf("fibonacci(%d)=%lu\n", arg, fib(1, 1, arg)); return 0; } 觉得怎么样？是不是很直白？

附：菲波那契数列有通项公式...
#python代码
import math
q = math.sqrt
def fib ( n ) :#看清楚了，这可是O( 1 )级的哦~~
return ((1 + q(5) / 2) ** n / q(5) - ((1 - 1(5)) / 2) ** n / q(5)

《称球问题》的 python 版解答

《程序员》杂志第8期上讲解了这样一个问题：在N个球中，有一个球重量与其他球重不同（偏重或偏轻），在没有砝码的天平上进行k（N<=(3^k-1)/2）次称量，得到这个球的编号，并判断它比其它球轻或重。

《程序员》上使用了将球分为0～n-1，n～2n-1，2n～N-1（n=(N%3)?(N/3+1):(N/3)）两两递归比较的方法。但由于在整个比较过程中，这个球到底偏轻还是偏重一直没有确定而进行了多次无效的比较，而且使用C++描述，对于这个需要大量出来数组的算法来说十分繁琐。我采用了支持函数式编程的Python语言优化了这个算法，脚本和测试用数据文件（举例）在附件中有下载。

主要思想与《程序员》中的类似，不过对球的列表的分片有所不同：
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
保证3片球数相同。确定是那一片出了问题后返回它时，最后一片由于可能不是balls[2*n:3*n]（len(balls)%3!=0），所以返回balls[2*n:]。

球包括号码和质量两个属性，类定义如下：
class Ball:
def __init__ (self, weight):
self.weight = weight
self.number = 0
（注：number的默认值0是无效的，号码从1开始）
sum()用于给质量求和：
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp
天平函数，返回比较结果——HEAVY = 1，LIGHT = -1，EQUAL = 0：
def metage (leftBalls, rightBalls):
left = sum(leftBalls)
right = sum(rightBalls)
if left > right: return HEAVY
if left < right: return LIGHT
return EQUAL

用全局变量QUESTION保存问题球是轻是重，这由预测量函数pre()给出，它工作后还返回有问题的分片。这样test()函数在工作时可以少一半比较次数。

test函数递归调用自身，可以采用折半比较的方式。但那样会提供算法的时间复杂度。假设n个质量数据求和要进行n次运算，折3片比较共需p=2*(x/3+x/3^2+...x/3^(N-1))次运算，化简得p=x-x/3^n，即求和运算次数不会大于球总个数。而折半比较则需(2^(N+1)-1)x（不准）次运算，明显多于使用分3片比较。

具体比较的条件详见代码，自行阅读。

最后解释一下数据文件的读入情况。数据文件是普通文本文件，每行一个数字，其中一个与其它不同。open(sys.argv[1]).readlines()返回一个由每行的字符串构成的列表，weight_list = map(string.atoi, open(sys.argv[1]).readlines())对这个列表中的每一项进行转数字操作并存入weight_list。ball_list = map(Ball, weight_list)把表中每一项创建Ball对象，最后test(pre(ball_list)计算返回球的编号。

关于python的函数式编程请初学者自己参考教材理解。感谢网友孔辉GID2257990(Lava-Lava平台)在程序调试方面给予的帮助。