2013年重读这篇笔记，错误很多，对定义的理解有很多混淆；作为自己学习和成长的记录不再将其中的错误一一纠正了

刚刚开始学lisp，还只是开始熟悉他的语法。但是学lisp确实是开阔眼界的一个好办法，能从更高的角度来看程序语言。

至今为止任何类型的程序语言其实都是图灵机的一个实现。比如说经典的x86 CPU吧，他就是一个图灵机。这个问题我其实还是想了好久才想出来的。可能是我太愚钝了吧。。图灵机的一种描述是这样的，存在一个两边都无穷长的纸带，一个含有一系列状态和命令的指针。这个指针一次执行一个命令，或者向前或向后移动一格，或者在纸带上读取或写入一个符号，命令有可能改变指针的状态。而读取到的符号会根据指针的当前状态产生一个新的指令。循环往复。直至到达某个特定的状态（终态）停止下来。

一开始我觉得CPU的寄存器表示状态。可这样的话，寄存器的值是不确定的，于是似乎不能模拟确定有限自动机。静下心来想想，其实应该认为所有寄存器的一种取值组合就是一个状态，所以假如有m个寄存器，每个寄存器的取值数量是ni，则总的状态数量就是i从1取到m, 将所有的ni相乘。（不能打公式郁闷。。）然后应该认为汇编代码就是那个带子上的符号。这样比如

ADD a, a, b ;a=a+b

这样的一条指令，应该看作是一个符号（所有可能的汇编指令应该是有限的，可以认为每一个都给编了唯一确定的符号）。这个符号对应CPU的不同状态，（例如这里的a和b的所有不同状态组合），可以看作每个状态都有接受了这个符号之后指向一个新的状态的箭头。使得寄存器状态改变。比如对于a=1,b=3这组状态(1, 3)，这个箭头就应该指向(4, 3)，当然这里没有考虑溢出位啦。同时又存在一些其他的操作，例如处理内存或中断的操作，可以看作是向纸带上的特定位置写入字符（由于内存和中断的数量也是有限的，所以可以给他们的每一个地址对应纸带上的一个位置）。

那么lisp呢，lisp是怎样实现图灵机的呢？

根据lisp1的自解释逻辑，可以认为lisp是一个不断扫描输入纸带的一个指针。他的状态则由输入中给定的“环境”决定。可以认为lisp仅有函数定义和函数调用两种语法。对于函数定义，其实是增加了新的状态组，把它的所有形参的所有取值组合看作是一组状态加入到自动机中。而函数调用，就是将实参值带入形参，计算函数结果的过程，对应于状态接受一个输入指向另一个状态的一个箭头，即在此实参情况下，如何应该进入什么样的下一个状态（次态）。

不过很有趣的是，鉴于lisp的递归定义，可以认为他的状态机也是递归的。在运行的最初，该状态机仅有函数定义及函数调用的最基本语法。指针扫描纸带（程序源代码）一遍，生成了最外层的函数定义，这是状态机为这些新函数增加新的状态，之后指针移动到该函数调用的起始位置，第二遍扫描源码，生成新一层次的函数定义，向状态机添加新的状态，直至最终所有的函数定义全部生成结束，递归到最底层，所有的实参都被计算成为原子，再依次递回，直至最上层。

从这个角度看lisp的有趣之处在于他用自己的规则定义自己，不断充实自己。不过也因为这种灵活性，使得用c实现一个高效的lisp编译器变得有些困难。一开始我在考虑的是lisp只有递归没有循环，确实不符合c语言的常规思路。不过转念一想，尾递归优化成循环其实倒反而是一件轻松的事情，只需要将形参改成自变量，把递归调用的那一句改成goto到函数开头就可以了。然后再改成while循环即可。麻烦就麻烦在这个函数的动态声明。有没有可能一次扫描完lisp文本之后就确定全部的函数定义呢？给定两个附加条件，一是所有的函数定义必须在他的调用的同一级或外层（注意这里指的是定义这个函数的外层，而不是调用这个函数的外层），二是函数定义必须在函数调用的前面。这样就可以逐级求值而避免递归了（相当于首递归）。当然这里避免的仅仅是（相当于）编译期的递归，在（相当于）运行期的递归仍然是避免不了的（也不可能避免）。当然对于lisp而言，编译和运行是交叉进行的，也没法分得这么仔细啦。（所以才说是解释型语言嘛。。汗）当然话说回来，将lisp先编译成机器码再运行也是可能的。只是编译时间会比较长而已，而且对于变量类型可能要做一些处理。（最简单的想法是用链表，不管是树也好，字符串也好，数字也好，都可以用链式结构存，以适应lisp的list结构。）

好吧，先做这些记录，下次有了感想再写了。

呼，因为结束实习，搬家，赶毕设，一下子好久没有写博了呢。。今天终于补了一篇。。证明我这段时间也没有荒废时间啊。。以后还是要经常写博客自勉啊。。回头看了一下大半夜的逻辑有点混乱估计有写错的地方。。不过天色晚了没心情挑错了，改天再回来改吧。。