C++博客-编程语言杂谈

迭代器的设计

呜呜 — Sat, 11 Oct 2014 09:10:00 GMT

对于一个编程语言来说，定制各种需要的数据结构是一项重要的能力，如果定制的手段非常精简，将会获得极大的开发效率提升，而构建的手段针对当前计算机底层很贴合，则可以有机会获得非常高的性能。
对于定制数据结构来说，最基础的一项操作就是，遍历所有内容，因为有了遍历，基本上就有了“读”的功能。
大家都知道，不同的数据结构无论是外在形态还是内部结构都相差甚远，有什么办法能提供一个统一的接口对内部所有数据进行便利呢？这就是所谓“迭代器”。
以C++为例，遍历一个vector：

我们可以看到，它定义了一个新类型，叫std::vector::iterator，这么个类型就是迭代器类型。从直觉上看他就是给访问数据提供个类似指针的接口而已，实际上这个迭代器变量还有另一个重要功能，就是“保存状态”，有了这个状态，才能知道下一次迭代能得到什么结果。
后来C++11标准出来后在语法方面进行了加强，淡化了保存状态这么个过程，写出的代码显得更加简洁：

#include <iostream>
#include <vector>

int main(int argc, char *argv[])
{
    std::vector<int> a = {1, 2, 3};
    for (auto iter : a)
    {
        std::cout << iter << std::endl;
    }
    return 0;
}

当然底层该有的操作是不会少的。

有了“保存状态”这个概念，实现编程语言的时候，就可以快速排除掉一些不靠谱的方案。
比如，不要迭代器而把状态保存在数据结构内部行不行？当然不行，考虑以下代码：

#include <iostream>
#include <vector>

int main(int argc, char *argv[])
{
    std::vector<int> a = {1, 2, 3};
    for (std::vector<int>::iterator iter = a.begin(); iter != a.end(); ++iter)
    {
        std::cout << *iter << ": ";
        for (std::vector<int>::iterator iter2 = a.begin(); iter2 != a.end(); ++iter2)
        {
            std::cout << *iter2 << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

我们就知道，访问状态有时候是需要保存多份的，而对于引用类型的对象来说，状态要想在内部保存多份会更加复杂，还不如用显式的状态保存。
直接修改数据结构内部呢？比如用类似car和cdr循环赋值的方式进行遍历。这一样行不通，如果复制保存的引用类型真实数据，则代价太大，看不出引用类型的好处，而直接修改则会破坏数据本身，而数据可能之后还要使用。

以下Python作为例子如何创建一个可迭代的，Range对象：

class Range:
    def __init__(self, low, high):
        self.cur = low
        self.high = high

    def __iter__(self):
        return self

    def next(self):
        if self.cur >= self.high:
            raise StopIteration
        else:
            v = self.cur
            self.cur += 1
            return v

for item in Range(1, 3):
    print item

创建对象的时候，执行了初始化方法和__iter__方法，在迭代的过程中则执行了和next方法，并且以StopIteration异常作为迭代结束的标志。

呜呜 2014-10-11 17:10 发表评论

高级语言与低级语言交互的若干问题--引言

呜呜 — Sun, 27 Jul 2014 19:58:00 GMT

首先定义一下题目中出现的“高级语言”和“低级语言”，这里的高级和低级指的不是语言特性的丰富程度区别、也不是开发环境和工具的区别，既然谈编译，我打算说的是编程语言实现中很常见的一种模式，即用相对原生的（比如可以方便灵活地构造复杂的数据结构，和操作系统交互极其容易），来实现一个相对高级的运行时环境（例如有垃圾回收等比较复杂的特性）以及运行在这个运行时环境的编程语言。一个很典型的实例就是，用C/C++来实现一个小型的编程语言虚拟机，有自己的指令集，以及其上的编程语言（例如Python的最原始实现CPython和Lua的官方实现这样的模式）。这样的编程语言实现模式相对简单，可以暂时跳过后端繁琐的事务，但是又不至于过分依赖高级工具（例如某些支持JIT的成品虚拟机或者LLVM）以至于让自己觉得好像略过了很多工作自己做得不够。

我们知道，哪怕是C语言这样的比较“原生”的语言，自带的标准库功能都是相当原始的。如果一个人从头包办所有的工作用C语言开发，在现在这个社会对应用快速开发的要求下，首先是很困难，因为不少该是库完成的功能要全部自己做工作量将会非常大，然后是有时候这样的愿望根本不可能实现。比如实现一个程序，你需要加密功能，那么得首先花一段时间熟悉数据加密方面的知识、研究到公钥方面甚至可能还得看看数论；而开发一个游戏程序、可能得学习不少图形知识，在没有任何库的辅助下自己实现一个类似“软渲染”的东西，中间一堆矩阵变换什么的……那么多知识，一般人根本应付不来。好在可以调用外部库，加密库由密码学专家开发，图形库由图形学专家开发，这样避免了重复工作，我们可以把精力集中在最重要的业务上。原生库，往往和那些原生的编程语言实现（比如C/C++）本质上一样，都是一些二进制机器码，通过操作系统给出的接口调用即可，实在没有操作系统自己也可以做个简单的加载器实现类似的效果。而前文提到的那类高级语言，实现上就不能简单地照搬原生低级语言的模式了，这里面牵涉了很多微妙的问题和技巧。

我策划了5篇文章围绕这个主题讲我的一些经验，这些主题涵盖了设计高级语言虚拟机和低级语言交互的若干初级话题：
一：操作系统接口
二：高级语言调用原生语言
三：原生语言调用高级语言
四：外部事件
五：线程与全局锁

以后也许也会补充更多的文章，希望这些文章能给读者解释一些疑惑，也给预备实现编程语言的朋友防止“踩坑”做一些提示，也非常欢迎读者和我进行交流。

呜呜 2014-07-28 03:58 发表评论

JIT 实践 (Practice Just In Time)

呜呜 — Mon, 21 Jul 2014 15:53:00 GMT

JIT全称Just In Time，也就是“即时”的意思，即时做什么事情呢？即时编译，它被广泛应用在编译器、编程语言实现、虚拟机、模拟器等等产品上。这篇文章就从头讲一下JIT是怎么回事以及为自己动手实现JIT做一个简单引导。

大家都知道，生产处理器芯片的公司有很多家，比较流行的处理器体系按粗略的分法都有x86、ARM、MIPS、PowerPC等等很多种，而且每一种下又可以进一步细分，比如x86除了基本的8086指令集之外还添加了32位扩展、64位扩展、还有一系列针对多媒体和多数据流等等应用的专门的指令集，如MMX、SSE等等，这些指令集能执行的程序，往往只能包含它支持指令的子集，比如你购买了一个64位的程序就不能用一个ARM的处理器来运行。

在有源代码并且源代码是语言实现是编译型的情况下，可以使用编译器针对多个平台分别编译，但是，两三个平台还可以，10个平台呢？每个平台之后又出现了新的扩展指令集呢？未来出现的新平台呢？没完没了。

于是有人采取这样一种做法，就是假想一个不存在的体系结构，包含一些栈或寄存器，以及对应的指令集，然后编译生成针对这个假想机器生成代码，又被称作“字节码”。以实现编程语言为例，这样的做法在直接解释编程语言源代码和完全的编译到机器码再执行之间，取了一个平衡点。这个平衡点相对于完全编译，获得了“一次编译到处运行”的好处；相对于直接解释执行，又获得了节省每次运行时都要做词法语法分析和简单优化的时间。这样的做法最著名的例子就是Java，Java开发时包含一个编程语言标准和一个虚拟机标准，虚拟机标准为以上这种执行模式打下了基础。要注意的是，不要以为Java是第一个想到这种做法的人，早在Java诞生之前的20世纪80年代甚至更早之前就有人这么做过，只是那时候的计算机性能非常差，差到不足以支撑这种模式的流行。

人们对性能的追求是无限的，但是又不甘心舍弃“一次编译到处运行”的优点，有什么办法能在字节码解释运行和编译到机器码之间再取一个平衡点呢？于是JIT也就是即时编译技术产生了。它的思想是，在保证字节码能通过解释运行在很多平台的基础上，针对个别流行的平台（比如x86和ARM），再进行一次编译，编译到机器码后再执行。这个再编译的过程确实要消耗一点点时间，但是想象一下，每一条指令都由虚拟机解释执行变为直接由CPU的电路执行，性能提升是非常显著的。

Java实现JIT后，据说.NET设计时还特地以实现JIT作为目标之一，除了编译器和运行时/虚拟机之外，JIT还被广泛应用在游戏机模拟器这样的真实硬件虚拟软件上，以获得更好的性能。

接下来是动手时间，需要的知识包括对C语言的基本理解和对操作系统的基本理解、会在终端下输入一点命令就可以了。

假设我们有以下C程序：

int inc(int a)
{
return a + 1;
}

我们的目标就是“即时编译”这段程序并且执行。

这个程序的功能显而易见就是输入一个整数参数，将其加上1后返回。将这个程序保存为obj1.c，进行编译。

在x86 32bit的环境下，使用GCC编译：

$ gcc -c obj1.c -o obj1.o -g

我们就会得到一个带有调试符号的目标文件，如果是x86_64的机器，我们为了下文统一，指定输出32位的代码：

$ gcc -c obj1.c -o obj1.o -g -m32

这样我们就会得到一个32bit的带有上面C程序功能的目标文件，看看这个文件的属性：

$ file obj1.o
obj1.o: ELF 32-bit LSB relocatable, Intel 80386, version 1 (SYSV), not stripped

ELF是Linux下流行的可执行文件格式，类似Windows下的PE。32-bit说明我们正确得到了32bit的目标文件。

接下来使用objdump指令解析刚才得到的目标文件：

$ objdump -S obj1.o

obj1.o:     file format elf32-i386

Disassembly of section .text:

00000000 :
int inc(int a)
{
   0:    55                       push   %ebp
   1:    89 e5                    mov    %esp,%ebp
    return a + 1;
   3:    8b 45 08                 mov    0x8(%ebp),%eax
   6:    83 c0 01                 add    $0x1,%eax
}
   9:    5d                       pop    %ebp
   a:    c3                       ret

看到了吗，我们得到了源代码和汇编指令的参照，更加方便的是，我们直接得到了每一条汇编指令对应的机器码，这些机器码在CPU中直接得到执行，执行性能是最好的。

如果你要问，不是即时“编译”吗？怎么不讲机器码是如何产生的？嗯……这篇文章的内容还是集中在描述JIT的原理，至于输出针对寄存器机器的机器码，那学问就大了，不过在这里可以稍微提一下，这些代码浅显的规律。如果你经常看这种编译器生成的x86汇编，就可以发现，通常进入一个函数，都会有以下两条指令：

0: 55 push %ebp
1: 89 e5 mov %esp,%ebp

这两条指令的意思是，先把%ebp寄存器压进栈，然后把%esp的值覆盖进%ebp，这么做的结果是，EBP里直接存放了当前栈帧的“底部”，这样我们可以轻易根据%ebp（实际上就是%esp）引用传入的参数。

之后的：

3: 8b 45 08 mov 0x8(%ebp),%eax

你要问为什么传入的变量a的位置在0x8(%ebp)的位置，其实不为什么，这就是编译器默认的参数传递约定，对于这个版本的GCC来说，第一个参数就在这个位置上。

接下来是给%eax增加1，这个没什么好解释的：

6: 83 c0 01 add $0x1,%eax

最后是：

9: 5d pop %ebp
a: c3 ret

也就是把之前压入栈以保护的%ebp的值弹出放回到%ebp上，最后ret返回，需要说的是，把eax寄存器里的值作为每个函数的返回值，这也是默认的调用约定。

为了实现这么个函数，我们用到的机器码装进数组里，就是：

uint8_t machine_code[] = {
    0x55,
    0x89, 0xe5,
    0x8b, 0x45, 0x08,
    0x83, 0xc0, 0x01,
    0x5d,
    0xc3 };

接下来是一些人直觉上想不明白的问题，这些代码放进数组里，不是数据吗？数据不是代码如何能执行？再原始一点的模型来说，只要CPU的IP（指令指针）或者PC（程序计数器）指向的地方的数据，都会被当作指令执行，但是我们目前的计算机有所不同，真实的内存被操作系统用虚拟内存包装起来，哪些地址的内存放的数据能被当作指令执行是操作系统说了算，所以你需要申请一段内存，明确告诉操作系统“我需要一段内存，请将这段内存给我并且标记为可执行”。

在Linux上，可以用mmap函数申请这样的可执行的内存，该函数的原型是：

#include

void *mmap(void *addr, size_t length, int prot, int flags,
int fd, off_t offset);

其中flags参数要带有PROT_EXEC标记即可执行了，比如：

mmap(0, size, PROT_READ|PROT_WRITE|PROT_EXEC, MAP_PRIVATE|MAP_ANON, -1, 0);

释放mmap得到的内存使用munmap函数。

Windows也有类似的函数VirtualAlloc，原型是：

LPVOID WINAPI VirtualAlloc(
  _In_opt_  LPVOID lpAddress,
  _In_      SIZE_T dwSize,
  _In_      DWORD flAllocationType,
  _In_      DWORD flProtect
);
比如：
VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT,
                        PAGE_EXECUTE_READWRITE);

释放VirtualAlloc得到的内存使用VirtualFree函数。

得到了可执行的内存后，我们将之前准备好的机器码复制进去就行了：

memcpy(executable_code, machine_code, sizeof(machine_code));

接下来，要使用C语言函数指针，将指向一段代码的内存空间指针的类型，强行转换为一个函数并且执行：

int (*func)(int) = (int (*)(int))executable_code;

复杂的C类型表示方法有时候是有点奇怪，但它就是这么写的。

以整数2为参数运行这段代码：

int result = (*func)(2);

需要再说明一点的是，因为以上我们生成的是32bit的机器码，如果你的操作系统是64bit的，编译后运行可能会缺乏一些32bit的库，以Debian GNU/Linux为例，用以下命令安装32bit的库：

# dpkg --add-architecture i386
# apt-get update
# apt-get install ia32-libs
# apt-get install libc6-dev-i386

最后，别忘了释放申请的内存：

munmap(executable_code, 0);

下面列出最终的完整程序：

#include
#include
#include <string.h>
#include
#include

int main(int argc, char *argv[])
{
    uint8_t machine_code[] = {
        0x55,
        0x89, 0xe5,
        0x8b, 0x45, 0x08,
        0x83, 0xc0, 0x01,
        0x5d,
        0xc3 };

    uint8_t *executable_code = NULL;

    executable_code = (uint8_t *)mmap(0, sizeof(machine_code), PROT_READ|PROT_WRITE|PROT_EXEC, MAP_PRIVATE|MAP_ANON, -1, 0);
    if (executable_code == NULL)
    {
        fprintf(stderr, "mmap failed\n");
        exit(1);
    }

    memcpy(executable_code, machine_code, sizeof(machine_code));

    int (*func)(int) = (int (*)(int))executable_code;

    int result = (*func)(2);

    printf("%d\n", result);

    munmap(executable_code, 0);

    return 0;
}

接下来编译并运行该程序，保存为jit.c：

$ gcc jit.c -o jit
$ ./jit
3

看来已经执行成功了。

这就是JIT的雏形了，实际应用中的JIT还需要做什么工作呢？以一个编程语言实现为例，已经开发出了能生成字节码的编译器，还要做的事情有：把字节码再一次编译为x86或者其它指令集的机器码，而这其中又包括寄存器分配，指令的选择以及其它一系列常见的编译器后端优化，而进一步深入挖掘还有程序热点统计这样就可以实现根据运行时信息优化，这么多话题可能可以写好几本书。

呜呜 2014-07-21 23:53 发表评论

简评中文编程语言

呜呜 — Tue, 15 Jul 2014 18:03:00 GMT

中文编程，或者汉语编程，不是什么新鲜事物，用“非英语编程语言”来进行编程也并非只有中国才有，这里有个叫“nadeshiko”的日语编程开发工具：https://code.google.com/p/nadesiko/，我相信还有很多其它“非英语”编程语言，有兴趣的可以看看。

没用过中文编程语言可以试试，国内有很多类似的东西，要指出的一点是，中文编程语言的所谓“输入的问题”没有想象中的困难，它们往往自带一个开发环境，只需要输入一个词语的拼音首字母即可完成输入（比如输入b就会弹出一个补全菜单，里面有“播放音乐“、”保存页面”等等选项，和你在常见IDE里按下.看到的一样）。

编程语言

计算机本不认识语言，而仅仅认识数字，然后根据一定的规则在存储器之间传输处理好的数字，人类按照机器底层的特性进行编程难度是非常大的，但是按照自然语言指示机器该做什么可以吗？首先是机器无法识别人类的自然语言，其次大部分人类自然语言无法表达清晰的逻辑。所以一些人进行了折中，设计了所谓编程语言的东西。编程语言是一种形式语言，用一系列的符号在计算机识别能力范围内和人类表达逻辑范围内寻找不同的平衡点。根据编程语言所处环境不同、设计目标的不同、编译器实现者能力不同等等因素，不同的变成语言所取的这个平衡点也不同。
以C语言为例，C语言所处的环境是，软件用汇编语言开发无法在各个不同硬件上移植，但是那个时期的硬件往往性能都比较低下，所以出现了刚好计算机编译器（早期是解释器）能识别（编译或解释），同时满足了当时开发操作系统直接操作内存的需求（具备有算术运算能力的指针）。如果你细心点可以发现C语言的很多特征迎合了那个时代的需求，C语言里有register、auto、inline关键字，说明当时的编译器水平很差，还不能做到高效处理寄存器分配和内联。int、short、long、char、unsigned、signed等等也恰恰描述了那个时代寄存器处理的数字常见类型有哪些。

中文编程语言

再以某个中文编程语言为例，写一个Hello World程序：

#包含 "某语言系统.接口"

整数类型主函数()
{
输出("你好世界");
返回 0;
}

其实本质和C语言：

#include <stdio.h>

int main()
{
printf("Hello World");
return 0;
}

外形几乎没有区别，能看得到的区别也就在关键字和标志符被“汉化”了。那么这些汉化到底能对“不懂英语”的人起到多少帮助呢？可以尝试拿上面的“中文版C语言程序”给一个没学过编程的人看，他几乎是不可能看懂的，也不可能立即用这种语言写个其他类似的程序，因为汉化了的那几个关键字和标志符尽管写成了汉字，但还是没有描述他们在实际的计算机程序中表示的是什么。比如#include ，#开头的往往是预处理宏，而预处理宏程序的功能是在编译前对程序进行的所谓预处理，比如include功能就类似与把stdio.h里声明的东西都“复制”到当前文件，使得当前文件可以看到stdio.h里的函数原型等等内容。而int表示的是整数类型，或者说当前计算机系统C语言编译器认为的默认宽度的整数类型，而不是无限精度的任意整数类型。那么把这两个换成“包含”和“整数”类型之后呢？包含的含义和include的含义还是相同，理解了include处理过程的人（或者仅仅理解它有什么作用的人）固然是会毫无顾忌地写下这行代码，而不懂的人还是不会写，其他的标识符和关键字的汉化也是一样，说到底，关于写程序的人，不是因为理解了这些符号在中文或者英文中的含义所以才会用中文或者英文编程语言写程序，而是因为他理解了这些符号在这个计算机系统和编程语言环境里的含义。
不要觉得这两种语句几乎一模一样语言对应起来很搞笑，其实很多所谓“中文编程语言”真的就是在预处理器上改改，把关键字和标准库的一些函数弄成中文，然后做个图形界面的开发环境就发布了，没有什么非常重大的科技含量。它们的底层（尤其是后端）本质还是现有常见编程语言的常见实现（比如GCC或者Mono之类的），有的甚至在不遵循自己引用的开源软件许可证的情况下，闭源还卖钱。

编程语言的目的

我们为什么要使用编程语言？因为用机器能识别的机器语言写代码太痛苦、而且没有移植性。我们想用编程语言做到的是什么？是在一个更高层次清晰地描述希望计算机执行的逻辑。而描述逻辑的过程无论是使用“整数”还是“Int”、或者“int”、“Int32”、“Integer”，难度并不会降低，中文编程仅仅是让一些脑子中有定势“我不会英文、所以中文能帮我学会编程”的人第一眼看上去害怕的程度稍微降低一点点，一旦学会了那几个关键字或者业务相关标识符相关的中文，之后的整理和表达逻辑的过程难度丝毫不会减轻，而这个“之后”，也就是学习这几个关键字和标识符的时间可能占整个编程的时间的99.99%，我们可以说中文编程仅仅减轻了这部分人0.01%的负担。

中文编程的害处

有人说减轻了一部分人0.01%的负担还不错，还算是改进，但是为了这0.01%的“改进”，又产生了其它更加严重的问题。
（1）：编程语言实现的匮乏
这些所谓中文编程语言的实现和维护者往往是个人和非常小的公司，而且以自己的实现来定义语言，他们往往不会开源，一旦这些个人不打算继续维护、或者该公司倒闭，则该语言写出的代码能运行的平台就仅仅被锁定在最后一个实现的发布，而且以后也不会再添加新特性和新功能了，用该语言写的代码几乎没有未来的发展余地。
（2）：库和其他支持的匮乏
中文编程语言用户少，而且仅有的用户还往往连那普通编程语言的几个英文关键词都害怕学习，更不可能开发高质量的、尤其是底层的库，于是编程语言的维护者和少量的高级用户只能担起开发库的重担，大部分库来自封装操作系统的API、常见功能的库（比如MP3播放、XML解析）的封装，但是这些库是非常不够的。
（3）：交流的困难
就如我们在国际性的论坛和irc交流使用英语一样，这些论坛和irc的用户除了中国人之外还有大量非英语国家的人，我们使用英语不是因为英语这语言非常精确、非常优美，而仅仅是因为英语用户多，已经几乎是国际语言了，大家都多少会点，交流起来非常方便。而使用这些非主流的中文编程语言则会使得自己和大家交流“没有共同语言”。

结语

我到这里结论已经很明显了，总结一下就是：所谓“中文编程语言”解决的问题不多，但是带了很多麻烦。如果有读者属于仅仅是因为认为自己不会英文而选择这些“中文编程语言”，请理解“编程语言的目的和编程的真正的难度在于描述逻辑，而不是关键字和标识符字面上所对应的自然语言”，然后尝试一下自己害怕的“英文编程语言”，买一本优质的学习该编程语言的图书，相信会很快发现，英语真的不是问题。

呜呜 2014-07-16 02:03 发表评论

Lisp概况与学习方法

呜呜 — Mon, 07 Jul 2014 14:51:00 GMT

Lisp名字来源于LISt Processor，也就是列表处理的意思。初学者第一眼见到Lisp往往印象最深的也就是里面成堆的括号。的确没错，括号就是该语言最显著的特点。整个语言的源代码也是以括号作为构造其语法树的依据。
很多初学者有考古的爱好，听闻了传说中的7公理，所谓7个操作符可以构造一切，并且为止着迷。且不说这7公理是不是真的能构造出目前很多应用上所需要的一切，就算真的能，性能也必定很低，因为具备的材料太少，很多基础的东西也要从头开始构造。而精简的构造似乎并没有为实际应用带来多少好处，图灵机的构造比这几个公理更简单，但是你不会看到有多少人用图灵机编程。制造计算机系统就是一个寻找扩展性、成本、体积、功耗等等参考的平衡点的过程，不在那个平衡点则很容易被淘汰。

最初版的Lisp早已没人使用，取而代之的是无数人基于Lisp的特点构造出的一系列类似Lisp的语言，无论他们名字里有没有Lisp，他们已经不是Lisp了，但是他们又是带有Lisp特点的语言，所以又被叫做Lisp的方言。所以看到某本书里介绍的某个Lisp的源代码，里面无数的括号的组织和括号之间关键字，千万不要觉得很神秘，因为那已经完全是个人或者某个组织定义的，不是非得那么设计的，如果你愿意，你也可以实现一个自己的Lisp方言。

Lisp以括号的简洁形态激励了无数人和无数组织制定和实现自己的Lisp方言、一旦有后来者不满意又会对之前存在的Lisp标准和实现进行“总结”而开发新的Lisp，加上开发新的Lisp的确简单（因为其语法简单，非常繁琐的语法分析部分很容易写），则更是激励无数初学者实现自己的Lisp，甚至有教科书的作业就是实现Lisp，所以到目前，已经根本无法统计到底存在多少种Lisp或者说Lisp的方言了。但是总的来说，目前还是有一些名气比较大的Lisp分类，用户比较多、实现比较多、资料也比较多，学习的时候可以优先选择下面三种：

Scheme：非常小型的Lisp方言，内容少至早期标准也仅仅有几十页，非常适合初学者学习。由于早期似乎被用作教学语言，所以并没有针对项目开发设计一些必要的措施，包括模块、名字空间等等。最新的标准正在尝试弥补这个缺陷但是进展似乎比较缓慢。目前来说比较好的实现有：
1. DrRacket，开源实现，自带IDE，有高亮、调试功能，支持Scheme相关的几种方言，自带手册比较完备，适合初学者。
2. Chez Scheme，传说中的异常高效的Scheme实现，支持最新标准，且作者是Scheme实现的权威，品质有保证。但是该软件为专有软件，需要购买使用。作者在其首页提供免费精简版Petite Chez Scheme。
3. Guile，GNU的扩展语言，一些GNU的软件就是用这个实现进行扩展的。
等等……
当然，因为Scheme语言的确比较精简，自己实现一个Scheme也是不错的选择。难度并没有想象中的大，实现后还可以嵌入在自己的项目中于扩展用。
Scheme学习资料非常多，包括
《The Scheme Programming Language》这本书是之前介绍的Chez Scheme的作者R. Kent Dybvig写的，内容详尽、语言的每个特性都给出示例。
《Structure and Interpretation of Computer Programs》这本书又叫做“计算机程序的构造和解释”，虽然通常被认为是一本入门书，但是实际上内容涵盖很广，包括计算机原理、编译器构造、符号计算、电子电路等等，编程语言成了描述这些内容的无关紧要的工具，做完大部分习题很有挑战性。
《Revised5 Report on the Algorithmic Language Scheme》又被叫做“R5RS”，初看这个题目有点莫名其妙，实际上这是一份类似Scheme标准的东西，里面最直接的描述了Scheme的关键特性，甚至有点面向语言实现者的意味。该标准之后还在不断地出第六份第七份等等，增加了一些标准库的内容。读通这本可以几乎完全掌握Scheme了。
因为Scheme的资料太多，暂时就列出上面三份，能看完这些掌握得就差不多了。

Common Lisp：又被叫做CL，是一个典型的“总结性”Lisp方言，也就是一次把各个Lisp方言的特性进行总结的尝试，并且获得了一定的成功。该语言极其复杂以至于很少有实现能比较完整实现其标准（虽然不少CL的实现都自称自己完整实现了标准）。比较常见的实现有：
1. SBCL，开源实现，来自与CMUCL，编译到原生码执行性能有保障。
2. CLISP，一些教科书推荐的Common Lisp实现，性能比较差。
等等……
PS：据Common Lisp界著名人物小妮补充的部分CL实现现状：

Allegro Cl, Lispworks, CCL, SBCL, ECL, CMUCL(已死)，CLISP（垂死），ABCL，MKCL（半主流，这个是从ECL改过来的），mocl（小众），Corman Lisp（已死）

常见的教材有：
《ANSI Common Lisp》传统风格的编程语言教科书，内容详尽。
《Practical Common Lisp》据说得了Jolt大奖，里面以一系列所谓现实生活中的例子来推进教学，喜欢这种类型教材的可以看看。

Emacs Lisp：
这算是一种专用Lisp，也就是说它并不是通用编程语言，而仅仅是用于扩展一个叫Emacs的文本编辑器。这个文本编辑器历史悠久，按键绑定灵活，用这种编程语言进行扩展后实现一些比较简单的功能可以简化文本编辑工作（当然本身还有其它问题，是否值得专门学习有很大争议）。学习Emacs Lisp是在对Emacs这个文本编辑器产生兴趣并且初步掌握后，想进一步探索和扩展的很自然的选择。
比较常见的实现有……当然是GNU Emacs，本身就是内嵌在Emacs编辑器中的。而最好的教材，毫无疑问就是自带的手册。推荐学习过程为
第一步：初步掌握Emacs编辑器的操作
第二步：学会一些基本的语法
第三部：尝试写一些扩展，需要的功能就去查找手册，找到该功能的接口后用之前学到的基本语法组合起来。

正如之前介绍的Lisp的特性，仅仅以括号作为明显的特征，激励无数人不断总结和发明自己的方言，这些方言没法介绍完，具体哪些值得学习观察。有一些现代的Lisp方言和实现挺有价值，比如Clojure，可以运行在JVM上，丰富的语法，还能运行在JVM上，重复利用之前用别的运行在JVM上的语言写的程序，这就是一个不错的选择。

参考资料：
LISP：http://zh.wikipedia.org/zh-cn/LISP
图灵机：http://zh.wikipedia.org/zh-cn/%E5%9B%BE%E7%81%B5%E6%9C%BA

呜呜 2014-07-07 22:51 发表评论

一步一步讲解Y组合子 (Y-Combinator Explained Step by Step)

呜呜 — Mon, 07 Jul 2014 08:54:00 GMT

你也许听说过Y组合子（又叫Y Combinator），也查过一些资料看过一些示例代码，但就是不明白什么意思，可能是因为自己平常使用的开发语言先入为主阻碍了对函数式独特的运算规则和一些细节没想清楚。

一：Lambda演算（Lambda Calculus）

Lambda又写作希腊字母λ，Lambda演算由Alonzo Church引入以定义“可计算函数”。该演算影响了一系列所谓函数式编程语言，如Lisp、ML系列。

一个Lambda表达式用以下格式定义：

λ变量.表达式体

Scheme里要这么写：

(lambda (变量)
表达式体)

比如，传入一个数后返回加1的结果，Lambda表达式写作：

λa.a+1

Scheme可以写作：

(lambda (a)
(+ a 1))

当然，变量可以是多个，比如求两个数之和的Lambda表达式可以写作：

λa b.a+b

用Scheme语言可以写作：

(lambda (a b)
(+ a b))

原始的Lambda演算甚至连逻辑和算术运算和数字都没有，所有的一切都是可以用Lambda演算定义出来的，当然在现代的编程语言中没必要做到那么“纯粹”，包括各种数据类型和运算该用都能用。

比如判断一个数字是否大于3，Scheme里写作：

(lambda (a)
  (if (> a 3)
    "Yes"
    "No"))

具体Lambda函数是怎么工作的呢，答案是归约。

归约有三种规则：

α-转换(α-conversion)

α读作alpha。alpha转换的意思是变量名不影响函数含义的意思。比如：

λa b.a+b

把变量名的a和b换为x和y：

λx y.x+y

该函数的功能并没有发生改变，不管传哪两个数字进去，都会得到一样的结果即两者的和。

β归约(β-reduction)

β读作beta。beta归约的规则是把函数“应用”到传入的参数上。

比如这么个Lambda函数：

λa b.a+b

应用在传入的两个参数1和2，那么a和b分别就替换成1和2，表达式体中的a和b的位置也分别被替换成1和2：

1+2

结果为3.

Scheme该这么写：

((lambda (a) (+ a b)) 1 2)

η变换(η-conversion)

β读作eta，eta转换表达的意思是，如果两个函数对于所有相同的传入的参数都能得到一样的结果，则两个函数相等。

二：循环与递归

现在看一个稍微复杂一点的问题，假设要求n!，也就是1*2*3*4*5*...*n该如何编写程序？

一种想法用所谓循环，比如用最常见的C语言，可以这么写：

int i;
int s = 1;
for (i = 1; i != n; i++)
{
s *= i;
}

但是普通的函数式语言是不提倡甚至不允许这么写的，原因就在于上面的写法有一个保存状态的行为，也就是给一些变量赋值，保存了中间结果，而函数式语言则基于Lambda演算，Lambda演算可没有“保存状态”这种行为。

你可能会想到使用递归来实现类似循环的效果，比如Scheme里:

(define factorial
  (lambda (n)
    (if (> n 0)
        (* n (factorial (- n 1)))
        1)))

这样做运行起来是没有问题的，可是我们给这个函数绑定了一个名字Lambda运算本身不支持这种做法，也就是说第一行得擦掉

(lambda (n)
  (if (> n 0)
      (* n (factorial (- n 1)))
      1))

但是这样factorial则不再存在了，调用它是不会有结果的，我们只能调用点别的东西：

(lambda (n)
  (if (> n 0)
      (* n (??? (- n 1)))
      1))

此时对于常用普通的非函数式语言的程序员比较费解的一点来了，就是函数也是一种“值”或者“对象”，它不但可以绑定到一个变量上，而且还能调用某函数时作为实际参数传入、并且在被调用的函数内部通过参数列表绑定的名字把传入的函数取出来。这么听上去似乎和函数指针之类的东西比较也没什么了不起，但是流行的函数式语言或者常被用于举例解释Y-Combinator的函数式语言往往是动态类型的或者有一定类型推导能力的，写起来十分简洁，看上去就似乎特别神奇。

以Scheme为例，定义一个返回两数和函数是：

(define (add a b)
(+ a b))

但是这只是一种缩略的写法，Scheme里所有函数都是Lambda函数，本质上它等同于:

(define add
(lambda (a b)
(+ a b)))

含义是，有那么个Lambda函数，功能是返回两数的和，然后把这个函数绑定在add这个变量上，或者说“赋值”给add变量。

我们可以直接调用这个add函数：

(add 1 2)

但是实际上add不是这个函数，只是这个函数绑定的名字，实际执行时会根据绑定的名字取出原来的Lambda函数：

((lambda (a b)
(+ a b)) 1 2)

然后把函数应用在1和2上，得到结果3

还可以把一个函数作为参数传给另一个函数：

(define (foo f)
  (f 1 2))
(define add
  (lambda (a b)
    (+ a b)))
(foo add)

这个程序就是把add函数作为参数传给foo函数，foo函数内部则取出绑定在f变量的传入的add函数，将该函数应用在1和2上，执行得到3后返回。

当然我们传入的函数不一定要绑定add这个名字，直接传入lambda函数也是一样的效果：

(define (foo f)
(f 1 2))
(foo (lambda (a b)
(+ a b)))

既然能把Lambda传入一个绑定名字的函数，那能不能不要绑定名字而是直接把Lambda函数传递到另一个Lambda函数中呢？当然可以。我们可以看到上面的foo函数本质上就是Lambda函数，也就是：

(define (foo f)
(f 1 2))

和：

(define foo
(lambda (f)
(f 1 2)))

是等价的。我们继续做上面做过的类似C语言的inline操作，也就是手工把函数“展开”，可以得到

((lambda (f)
(f 1 2)) (lambda (a b)
(+ a b)))

此时原本清晰的程序已经非常难看了，但是运行的结果也是一样的。经过上面这一系列示例，你对Lambda演算有初步的概念了吗？

三：传入自己

回到之前的求阶乘的问题上：

(lambda (n)
  (if (> n 0)
      (* n (??? (- n 1)))
      1))

lambda变量里不能调用一个外部的绑定名字的函数，当然Lambda函数本身也不能有名字（所以在某些编程语言里Lambda函数这个概念又叫做“匿名函数”）,既然自己没有名字那如何调用自己呢？通过上一节的讨论结论很明显了，就是把“自己”或者说跟自己功能一样的函数作为参数传给自己，然后自己就可以从参数列表中取出“自己”或者说跟自己功能一样的函数进行调用。

程序修改为：

(lambda (f)
  (lambda (n)
    (if (= n 0)
        1
        (* n (f (- n 1))))))

其中f为“跟‘自己’功能一样的函数”，上面写的函数是阶乘函数吗？不是，他本身是一个Lambda函数，接受了一个f参数，并且返回了一个使用f参数的Lambda函数。有人觉得很奇怪为什么返回的另一个函数居然能使用f这个参数，这就涉及函数式编程语言中流行的另一个概念，叫“闭包”。关于闭包的更多信息请参考**这篇文章**。可见，以上的函数不是阶乘函数而是“阶乘函数生成器”，为了方便下面解释暂时绑定一个名字。

(define factorial-maker
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

那么传入的“跟自己功能一样的函数”是一个什么样的函数呢？是一个阶乘函数，阶乘函数的写法是：

(define factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1))))))

但是慢着，factorial函数可不能调用自己啊，那不能调用自己调用谁呢？可以调用之前写的“阶乘生成器”，于是阶乘函数改为：

(define factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n ((factorial-maker factorial) (- n 1))))))

这里用到的参数factorial还是不存在的，那么如何得到factorial呢？还是得调用factorial-maker产生：

(define factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n ((factorial-maker (factorial-maker factorial)) (- n 1))))))

这似乎要无数次调用factorial-maker，没完没了……

四：不动点

从上一节引出的问题是，虽然factorial-maker能生成factorial，但是还是需要以factorial作为参数传入，而这与转而使用factorial-maker的目的相违背，所以我们得引入一个概念，叫“不动点”。

不动点的概念以前大家都应该接触过，维基百科里解释“在数学中，函数的不动点或定点是指被这个函数映射到其自身一个点。”

举例解释，比如函数：

f(x) = x * x

当x分别为0或1时，函数的值也分别为0或1即原来的数，则0和1为函数f的不动点，也就是：

x = f(x) = f(f(x)) = f(f(f(x)))

在编程语言里，这个概念又要进一步扩展，因为函数也可以作为输入。

假设有函数f(fn)，fn为函数f的输入参数，并且

fn = f(fn)

很容易发现f应用在fn上不管多少次，结果都一样：

fn = f(fn) = f(f(fn)) = f(f(f(fn)))

函数可以作为参数传递、返回值也可以是个函数，说起来容易但是对于平常不使用“函数式语言”的程序员理解起来总是不太顺畅。

五：Y函数

有了不动点的概念，再考虑上面的问题，我们有了factorial-maker，也就是可以生成factorial的函数，但是需要的是factorial本身作为参数传入，那么如何获得factorial本身？假设我们有一个函数叫Y，这个函数的作用是输入一个函数的生成器也就是factorial-maker输出该函数本身如factorial：

factorial = Y(factorial-maker) (1)

用Scheme的语法写作(Y factorial-maker)可以得到我们想要的factorial。而且：

factorial = factorial-maker(factorial) = factorial-maker(factorial-maker(factorial)) = (2)

对于函数factorial应用任意次factorial-maker函数，都得到factorial本身，说明factorial本身是函数factorial-maker的不动点。

结合(1)和(2)可以得到：

Y(factorial-maker) = factorial-maker(factorial) (3)

(1)代入(3)的右边得到：

Y(factorial-maker) = factorial-maker(Y(factorial-maker))

于是我们需要的Y就出来了，用Scheme语言写出来就是：

(define Y
(lambda (f)
(f (Y f))))

整个程序则为：

(define Y
  (lambda (f)
    (f (Y f))))
(define factorial-maker
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))
(display ((Y factorial-maker) 5))

这个程序从字面上是正确的，但一旦运行则会根据运行环境的不同有不同的运行结果，卡死直至消耗完计算机资源、提示栈溢出、运行得到正确的120，都是有可能的。原因在于Y函数内部的Lambda函数可能会调用Y不断增加新的栈帧，还来不及执行函数f。

当然一个更明显的问题是，这个程序仍然没有仅仅借用Lambda运算完成重复的操作。

六：Y函数（改进）

接下来的推导就比较困难了，我现在还没能完全弄清楚怎么到我们常见的最终形式。

Y组合子常见的最终形式是：

Y = λf.(λx.f (x x)) (λx.f (x x))

用Scheme写出来则是：

(define y-combinator
  (lambda (f)
    ((lambda (x) (f (lambda (y) ((x x) y))))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

这个最终形式的Y组合子可以工作在非Lazy的正确实现的Scheme里。

七：用途

在“大多数”普通的命令式编程语言里、甚至某些支持函数式编程的不标榜函数式的编程语言里，的确很难想象到为什么表达一个重复的过程，非得求助于Y，正如前面的例子所描述，绑定一个名字往往就可以直接解决问题。不过大部分函数式编程语言既然构建在Lambda演算的基础上，底层通常也是把我们看到的高级语言的假象展开为Lambda演算，对于这些编程语言的实现者来说Y组合子是实现一些特殊语法的必要设施。

参考资料：

Lambda calculus：http://en.wikipedia.org/wiki/Lambda_calculus

不动点：http://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9

呜呜 2014-07-07 16:54 发表评论