复习 Perl

今天我去报名下一次托福模考，顺便去了书店转转——很长时间没关心计算机方面的书籍了，我唯一想看到只是《精通正则表达式》，也算是 “门当户对”。不过还是留意了一下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 用心良苦啊~`

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

我看 D 语言

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

各个语言编程的风格

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

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

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

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

Re: 各个语言社区的风格

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

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

本文作者还是那个无名小辈 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 数据

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语言的书里讲的很详细。

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

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

• 诶，我的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)
  

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

学过数据结构的人都知道，一棵完全二叉树（除去最低层元素从左到右排列，其它的层都为满的）可以保存在一个数组中 这个完全二叉树存储在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数组

（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（转）

使用 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数据结构——简单二叉树

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

Scheme学习笔记（五）

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

八. 宏

• 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学习笔记（四）

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

四. 流程控制

• 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学习笔记（三）

（另一些参考资料：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不变。