RSS Feed

November, 2011

  1. 学习lisp的总结以及scheme和common lisp的比较

    November 24, 2011 by xudifsd

    似乎很少有人刚开始编程就使用lisp,一般常见编程入门语言主要是C,Java,python等非常流行的语言。许多学lisp的人应该都和我一样是半路迁移过来的,到现在为止我学lisp断断续续的有半年了,现在总结一下这半年来都做了什么,顺便帮助一些其他的想学lisp的人。我学lisp时看过的书见这个豆列

    学习lisp的痛苦和好处

    一般从其他语言迁移到lisp会经历各种痛苦,因为它有太多的其他语言不具有的概念:闭包,词法作用域,高阶函数,宏,即使撇开这些不谈一般人也会受不了lisp那么多的括号。其实括号这个问题也并不严重,最开始我刚从python迁到C就有很大的不适应:C竟然要求每个表达式后加分号!python用惯了后突然学C,每写一个程序编译时的错误都是没有最后的分号,当时跟同学讨论觉得这是C语言的一大失败啊。刚开始学lisp时也一样,在定义一个函数之后要想把剩余的括号都打完还要靠编辑器的匹配,否则绝对眼花。但是现在习惯之后问题也没什么大不了的了:只要你在括号的开始位置放对,中间括号的位置匹配对,定义一个函数之后的括号匹配简直就是一种享受:终于只要按着shift+0看着编辑器括号匹配的颜色正确就能完成一个函数了。

    而那些神秘的概念就更有意思了,使用这些别的语言没有的概念可以让你学会很多,而且一旦你学会就会发现这些正是lisp优美的原因。其中我觉得宏是lisp中最为奇特的特性,Paul在《黑客与画家》中就说到了“在lisp中编程就像直接修改语法树,这样的语法树在其他语言中本来应该是在编译程序是生成的,但是在lisp中可以直接修改。”这句话本来我一直没理解,就算是拿lisp编程很长一段时间如果你不接触宏也是无法体会这句话的。打个简单的比方:写宏在原理上非常类似于写一个编译器,编译器本质上就是将一个更简单的语言翻译成更复杂的语言,这样让人们可以用更简单的语法来编程,之后再用编译器将简单的语法翻译成更接近机器理解能力的语言就行:所谓的牺牲CPU时间来节省程序员时间。而宏做的就是这样的工作,编程人员定义一个具有简单语法的宏让它匹配宏的调用,之后宏就像普通函数一样将简单的语法翻译成更复杂的语法,而宏的匹配就是基于lisp的语法树特性,如果没有语法树的特点lisp也就是另一个Haskell而已。如果你能把宏用得很好那么你可以只靠宏来实现世界上的任意一种语言。这样的好处实际上很大程度上是由lisp程序中令人烦躁的括号带来的。

    选择lisp方言

    lisp和其他语言不同点之一就是它的方言众多,当初我听方言这词的时候都乐出来了:自然语言有方言那么编程语言当然也能有方言。其实lisp的每个方言也有很大的差别,虽然他们都大量使用括号,但是一些内部表示和基本函数也不一样。其实我觉得学lisp最重要的就是选择一个lisp的方言。lisp有三个使用最广泛的方言:Emacs Lisp, Common Lisp(以下称CL)和scheme,其中Emacs Lisp是专门服务于Emacs编辑器的,可以忽略不计。一般关注的是另外两种方言:CL和scheme。CL是用得最为广泛的Lisp标准,它本身也提供了很多标准的库,还有也有标准的IO库,而scheme则非常严格的贯彻了精简的原则,整个核心的被标准定义的函数不超过100个,其他的都由实现来决定。

    从上面的介绍来看就能够作出一些选择了:CL非常适合于严谨的软件开发,因为语言的标准库能够实现大部分的功能,如果使用它来开发会非常方便,但是scheme则完全相反,什么都需要从头开始,除非你使用的scheme实现提供了一些基本的库。这么一比较似乎先学CL比较好,但是我倒觉得先学scheme更好,因为CL有些太大了,整个标准有许多的函数,你根本不知道自己是不是学完了,而且最为奇怪的是CL的符号(也就是通常意义上的变量)允许存多个值,也就是说CL允许允许一个符号即是函数同时也包含值,这样的定义有些奇怪,我完全不知道为什么要这样定义,而正是这样的定义让你每次引用符号的函数时需要在前面加个#,否则你引用的是符号的值。而且CL的宏相当地低阶,不像scheme有自己的宏系统可以方便地实现干净的宏,从上面的意义上来说CL非常适合已经非常熟悉lisp的人去开发正经的程序,但是不适合初学者。

    相比于CL,scheme语言非常精简,标准的核心函数不到100个,其他由实现来决定的函数主要都是IO方面,所以说只要你将那不到100个核心函数学会你就基本上会了scheme了,并且IO库是相当简单的,可以在非常短的实际内学会。但是这样的后果就是scheme的除核心之外的函数十分混乱:有时你在一个scheme实现能用的函数再另一个就改名甚至根本就没定义。所以scheme非常适合于初学,但是并不是很适合开发,并且在学scheme时选择一个好的实现也非常重要,我觉得最好用的一个实现是Chicken

    学习的书籍

    学习lisp语言首先要推荐的就是计算机科学的神书《Structure and Interpretation of Computer Programs》,这书也是相当有争议的,这本书的作者就是scheme语言的发明者Sussman,他自己在MIT教学,当年就拿这书进行计算机科学的教学,MIT的开放课视频有当年课程的视频,可以免费下载。这课本来一直都是使用scheme和《SICP》进行教学,但是最近改成了使用python进行教学,并且书也换了。这样一换引起了很大的轰动,很多人都认为这是从教授计算机科学转向教授编程,直接将大学降级成职业学院的标志。而且这书在美国亚马逊的评价很有意思:呈现了两极分布,有一半的人给5星,也有一半的人给1星,几乎没有评价中等的,这样的评价分布足以证明这书的优秀:优秀的人看明白了并且学到了很多,所以打5星,并不优秀的人根本看不懂,所以打1星。这本书虽然是以scheme语言为基础但是根本不需要人们已经掌握scheme,就像书中说的:“既然lisp不是主流语言为什么还要拿它做框架讲课,就是因为lisp语言实际上根本没有语法,这样就能把大部分精力用于讲计算机科学而不是讲授特定语言的语法。”这本书讲到了很多的如何使程序更加优美,如何控制大型软件的复杂度,并且还讲到了很多的编程范式和编程模式:面向对象,事件驱动还有并发编程等。所以学这本书会非常有价值,不能只把它看成一本介绍语言的书。

    如果你想学习CL,Paul自己写的《ANSI Common LISP》就非常好,但是这也不是很适合初学着看,因为这虽然讲的是CL,但是继承了scheme的传统——简洁性,它用非常少的章节就把很多CL的重点讲完,不过总的来说这本书非常好,能学到很多语言的细节,并且题目的设计也不错。


  2. 记一次Linux grub恢复

    November 16, 2011 by xudifsd

    今天同学遇到了一个很多Linux使用者常见的问题:恢复grub。他的情况是这样的:硬盘上有两个操作系统,一个Windows 7,一个Ubuntu,由于Windows中毒(既然Windows容易坏为什么还要用。。),所以把Windows重装一遍,重装一遍后会发现在启动选项中没有Ubuntu了,这很正常,因为Windows的引导程序不能识别Ubuntu系统(这就是为什么Ubuntu要在Windows装后再装的原因),而重装系统会清掉原来的引导程序。为了能重新启动硬盘上的Ubuntu需要将Ubuntu的引导程序也就是grub装上。

    首先从Ubuntu安装盘启动,选择试用模式,启动好之后打开终端,输入以下命令:

    sudo fdisk -l

    它会列出当前硬盘的所有分区,如下图:fdisk -l结果

    我分了多个Linux分区,分别为/dev/sda{6..11},其中sda9是我的根目录,sda6是我的/boot目录

    由于是从CD启动的,硬盘上的分区都还没有挂载,所以先要将需要修改的一些分区挂载上来,执行以下命令:

    sudo mount /dev/sda9 /mnt
    sudo mount /dev/sda6 /mnt/boot

    其中第二个命令需要根据自己的情况运行,由于我将boot单独分一个区,所以我需要挂载boot分区来修改它,如果你没给boot单独分区,那么就不用执行第二条命令。

    之后需要将一些虚拟的文件系统挂载到/mnt目录下,这样是为了模拟出从硬盘启动的所有文件系统的环境:

    sudo mount --bind /proc /mnt/proc
    sudo mount --bind /dev /mnt/dev
    sudo mount --bind /sys /mnt/sys

    之后便是一条非常重要的命令,如果你在进行grub-install时出现了/usr/sbin/grub-probe: error: cannot stat ‘aufs’提示,那么很有可能就是因为你没有执行下面这条命令:

    sudo chroot /mnt

    执行了这条命令之后你的终端已经几乎完全模拟出从硬盘启动的终端了,之后你执行的命令都对应的修改硬盘而不是修改不会保存的CD虚拟的文件系统了(对于一些特殊情况就不满足这条件了,比如需要修改/etc但是你将etc单独分区并且没有挂载到/mnt)。
    之后执行以下命令:

    update-grub
    grub-install /dev/sdX	#sdX中的X对于你硬盘的号,一般是sda,注意不是sda7这样的分区号,而是直接指定整个硬盘,如果不是主硬盘就是sdb,以此类推

    之后直接重启就行了。

    联想

    最近总是在思考过程式编程和纯函数式编程有什么区别,我觉得这是一个很好的例子。在这个还原grub的过程中我们做了很多的mount,并且还用到了几乎不会用到的chroot,这么多多余的步骤就是为了创造出一个正确的文件系统环境,好让我们在这个模拟的环境中执行没有参数的update-grub。从编程的角度来讲update-grub是个函数,但是这个函数写得非常不好,它竟然不靠参数来运行而是依赖于全局变量,这个全局变量就是我们刚刚费了很大劲才创造出来的文件系统环境,如果update-grub靠参数来运行(也就是说update-grub类似于纯函数式编程只靠参数运行而不依赖于全局变量),我们就只需要挂载boot分区再指定boot分区的位置就行,而不用为了这个依赖全局变量的函数而模拟出整个环境。我觉得这也算是函数式编程的一个好处之一了吧。


  3. 闭包,词法作用域和lambda函数

    November 8, 2011 by xudifsd

    在学习编程时最重要的是了解程序解析器或编辑器的运行过程,有很多解析器模型可以用于模拟这些过程,在学习支持lambda函数的语言时有一个非常好用的解析器模型——环境解析模型,这个模型在《SICP》中提到,这方法对于学习lambda解析很有效。几乎所有支持lambda函数的都可以使用这种方法来模拟解析器运行,目前我知道的支持lambda函数的语言有JavaScript, Lisp和Haskell。

    环境

    想要理解环境解析方法就必须先理解环境。环境就类似于存储键值对的通用仓库,所有对变量值的查找都是在环境中查找,而环境则是由更小的帧对象组成,如何理解呢?下图显示了几个由帧组成的环境

    环境和帧

    上图有三个帧,分别为1、2、3,其中a、b、c分别指向这些帧,1是最底层的帧,2和3都指向帧1,用继承的语言来说就是帧1是帧2和帧3的父帧。从a来看,变量x、y的值都为100;从b来看x为2,y为100,z为5,x是2而不是100是由于从b看时帧2中的x会屏蔽帧1中的x,而从b也能找到y就是因为帧2指向帧1;同理从c来看x为100,y为10而z为100。这样我们可以总结出在环境中查找变量的规则:如果在当前帧没有找到变量的值,找当前帧的父帧,直到找值到或者当前帧没有指向其他帧。这种环境由帧组成的方法提供了很大的便利,这些便利可以从后面的讨论中看出。

    函数对象

    在任何支持lambda函数的语言中,函数都可以看作一个函数对象,这意味着函数是有属性的,他们有两个属性:函数代码和环境,函数代码就是定义函数时写的函数代码,而环境就是定义函数时的环境。函数对象可以用以下图形表示:

    从上图可以看出一个函数的结构,左边的菱形保存的是函数定义的代码(虽然在实现时出于效率的考虑不可能保存代码的文本,但这样可以集中思考),右边保存指向环境的指针。每次创建一个函数都会创建一个这样的函数对象。这与其他语言如C语言不同的就是支持lambda的语言都支持在运行时动态创建函数,这样创建的函数会捕捉到创建它时的环境,同时也允许将函数作为参数或返回值,这就是为什么在这些语言中函数被称为顶级对象(First Class Object)。

    环境解析的方法

    环境解析方法有两个规则,一个针对函数的定义,也就是lambda函数,另一个针对函数的调用。规则如下:

    1. 函数定义时会捕捉定义时的环境。
    2. 函数运行在它被定义的环境中。

    我们可以通过例子和图来模拟环境解析的方法,假设有如下代码:

    (define (make-acc base)
    	(lambda ()
    		(set! base (+ 1 base))
    		base))

    上面的代码定义了一个累加器,它接受一个参数作为累加器的基数,返回一个从这个基数进行累加的函数。定义了这个函数之后得到如下环境:

    在这之后运行如下代码:

    (define from-100 (make-acc 100))

    这会产生如下的环境:

    环境解析方法2

    这个图非常形象地描述了环境解析方法的规则,make-acc是个lambda函数,调用该函数会新建一个环境帧2,这个环境帧包括的就是形参和实参的对应关系,这个帧的父帧就是make-acc函数属性中的环境,这确保了函数中的自由变量也能得到正确的引用,在创建环境帧之后会运行lambda表达式,这会定义一个新的函数,而这个函数的环境属性就指向刚刚创建的这个环境,如果之后再调用from-100时from-100会在环境2上运行而不是环境1上运行,它会修改帧2中的base变量,让其自增1然后返回自增后的值。这种函数在定义的环境中运行而不是在调用它的环境中运行的特点就是词法作用域。而这样的特性也就产生了最为优美的闭包。在这个简单的例子中也产生了一个闭包:只有from-100函数能访问创建该函数时给的参数base,其他任何函数都无法访问base,这有些类似面向对象语言中的private属性,但这完全是通过函数的闭包特性来实现的,而不需要动摇整个语言,增加语言解析器的复杂度。