RSS Feed

Posts Tagged ‘scheme’

  1. 关于lisp解释器

    September 28, 2012 by xudifsd

    在上个月重新看了《SICP》第四章后觉得写个lisp解释器也不是很困难,甚至我发现只要理解了其中的原理整个解释器其实非常简单。我觉得书中理解原理的关键一段就在4.1节

    The metacircular evaluator is essentially a Scheme formulation of the environment model of evaluation described in section 3.2. Recall that the model has two basic parts:

    1. To evaluate a combination (a compound expression other than a special form), evaluate the subexpressions and then apply the value of the operator subexpression to the values of the operand subexpressions.

    2. To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment. To construct this environment, extend the environment part of the procedure object by a frame in which the formal parameters of the procedure are bound to the arguments to which the procedure is applied.

    These two rules describe the essence of the evaluation process, a basic cycle in which expressions to be evaluated in environments are reduced to procedures to be applied to arguments, which in turn are reduced to new expressions to be evaluated in new environments, and so on, until we get down to symbols, whose values are looked up in the environment, and to primitive procedures, which are applied directly.

    也就是说eval和apply是相互递归的,eval会调用apply去产生结果,而apply会调用eval解释整个程序的子句。

    apply的基本作用就是在调用函数之前创造出一个环境帧,这个帧中包含解析函数子句所必需的变量绑定,而被apply调用的eval会在这个新的环境中解析函数子句。

    而eval则是负责在环境中查找符号的绑定,根据表达式中的第一个符号的内容(也就是表达式的operator),来决定下一步行动,如果是普通函数则调用apply,如果是宏则调用macroexpand,宏扩展之后再调用eval去解析扩展后的表达式。这样说可能有些难以理解,具体可以看我以前写的一篇关于lisp环境帧的文章。在理解了这个原理之后再看SICP的就好理解了。

    总的来说,整个解释器也就这些东西了。而且由于lisp基本上都内置了read函数直接返回读到的表达式,而且由于表达式就是列表,所以用lisp来解释lisp简直没什么技术含量,所以我也就花了几天时间就写出了个lisp解释器。我实现的基本上是scheme的函数,并且支持call/cc,不过宏却是CL类的宏,因为scheme的宏虽然干净但是感觉还是太难用了,还是觉得defmacro用起来舒服,所以我也就只实现了defmacro宏。

    关于lisp解释器

    虽然lisp版的解释器已经实现了,但是完成后却发现没什么技术含量,不过由于使用高阶语言完成了一个项目,那么整体的思路也已经掌握,所以我还是想用C实现一个解释器,这样一想其实会多很多工作量:内存管理,垃圾收集,符号查找,链表的读入等这些在lisp实现中完全不需要考虑的细节全部冒出水面了。

    不过即使是使用高阶语言来实现我也发现自己对难度的判断有些错误(看来别人说的“要把程序员估计的困难提高几个数量级才能得出正确值”是对的):本来以为call/cc实现起来非常困难,但是实际上直接使用原生的call/cc就能非常轻松地把这个功能提供给使用者。就算是使用C实现起来也不会困难,只是一个setjmp和一个longjmp而已,但是实现之前想做的的干净宏却异常困难,最后不得以,只能拿CL的defmacro(由于没有支持gensym,所以一些高级宏没办法支持)的语义来充数了。

    如果有人对lisp实现感兴趣以下是一些提示:

    这个解释器所支持的语法虽然混合了CL的和scheme,但是只能由scheme解释器当宿主解释器。推荐使用chicken scheme,因为我用的就是这个,使用时直接用csi main.scm就能进入repl,现在支持的一些函数和基本语法见eval.scm和setup.scm,其中setup.scm中直接导入了宿主解释器的基本函数,还定义了let和cond宏,这样你也可以照着写一个由scheme来解释的CL宏(个人觉得好帅)。

    关于C实现的lisp解释器

    基本功能已经在lisp实现中实现了。但是我仍然想用C来解释lisp,这样更有挑战性也更有意思。准备实现的基本解释器其实应该算是个库,它提供接口让所有链接到该库的软件可以直接解释lisp,这个接口应该包括:

    • 允许让用户自己加入primitive procedure:比如库本身不提供打开文件的接口,但是应该允许用户自己拿C语言实现这个函数,并能将其加入到环境中就好像库本身提供一样,这样用户可以自己扩展该库而不需要改变库。
    • 提供类似eval-string的C语言接口,让用户可以eval外部提供的lisp语言。从这个意义上来说:repl本身就是该库的一个thin wrapper。

    希望最终能完成这个项目,现在还有很多的困难需要克服,最大的困难就是garbage collection,实在不知道应该怎么解决这个问题,还需要调查很久,而且一旦这个地方出现bug将会非常难找到。而性能问题也将是一个头痛的问题,因为从来没写过一个性能需求很高的软件,很多次的优化最终常常被证明还不如不优化。所以,成品估计也只能当作是一个勉强能用的东西吧。


  2. SICP练习题1.45——求n次方根

    December 19, 2011 by xudifsd

    SICP》第一章最后有个练习非常有意思:求n次方根。书的第一章几乎用了所有的篇幅来讲一些算法和抽象,并且在第一章第一节就说到了用牛顿迭代法来求一个数的平方根,在第一章最后一节的练习中要求一个数的n次方根。

    根据书上前面几节的说法,求x的平方根就是求函数y->x/y的不动点,而不动点的求法就相当简单了,随便猜一个数带入函数,如果结果不好再将结果带入函数,最终函数总会得到不动点。但是如果直接这样求平方根会有一个问题:函数并不收敛(假设最开始猜y,那么带入函数会得到x/y,将结果再带入函数又得到y),补救办法就是使用一个叫average damp的方法(实在找不到中文的翻译,直译过来就是平均阻尼),average-damp可以直接用下面函数定义出来:

    (define (average-damp f)
        (lambda (x)
            (average x (f x))))

    这个函数的作用就是取函数返回值和函数参数的平均数,这样先对y->x/y这个函数取average damp,再对结果取不动点就能得到平方根了。我们也能用同样的方法取一个数的三次方根,只要将函数换为y->x/y2即可,但是对于四次方根无法得到结果,原因也是不收敛,而解决办法竟然是对原始函数取两次average damp。题目要求我们做实验得出为了取n次方根而必须取average damp次数的规律,这样我们可以定义下面的函数:

    (define (fixed-point f guess)
     (define (close-enough? a b)
      (< (abs (- a b)) 0.0001))
     (let ((guess-value (f guess)))
      (if (close-enough? guess guess-value)
       guess
       (fixed-point f guess-value))))
    
    (define (repeated f n)
     (define (iter f n result)
      (if (< n 1)
       result
       (iter f (- n 1) (lambda (x) (f (result x))))))
     (iter f n identity))
    
    (define (average-damp f)
     (lambda (x)
      (average x (f x))))
    
    (define (average a b)
     (/ (+ a b) 2))
    
    (define (square x)
     (* x x))
    
    (define (nth-root x n)
     (fixed-point
      ((repeated average-damp 2)
       (lambda (y) (/ x (expt y (- n 1)))))
      1))

    其中fixed-point需要一个函数f,和一个最初的猜测数,返回满足要求的不动点;而repeated将带入的函数f迭代n次。
    实验结果如下:

    #;1> (nth-root 8 3)
    2.00003461276416
    #;2> (nth-root 128 7)
    1.9999526734277

    但是一到8次方根以上程序便会在两个数之间跳转,因此需要再将函数average damp一次,而函数到了16次方后又需要average damp一次。这样看基本上得出了规律:只需要将所求的根数取log2即可,但是scheme只提供了以自然对数为底的log函数,不过只需要定义下面的函数就可以求以2为底的log了:

    (define (log2 x)
     (/ (log x) (log 2)))

    这样我们就能够解决1.45的习题了:

    (define (nth-root x n)
     (fixed-point
      ((repeated average-damp (floor (log2 n)))
       (lambda (y) (/ x (expt y (- n 1)))))
      1))

    由于数学能力有限实在是无法证明为什么结果是这样,而且对于average damp这样一种方法维基百科上竟然没有!以前的数学实在学得不怎么样啊。不过《SICP》的习题做起来确实很有意思,还教你直接求tan、黄金分割数还有e的方法。


  3. scheme的宏

    December 5, 2011 by xudifsd

    Paul的把lisp的宏夸到了无以附加的地步,但是作为一本闲聊的书它并没有深入介绍lisp的宏,甚至连基本概念都没提到。这对于学习lisp的人非常有害——它会造成一种莫名的崇拜,并且这种崇拜还是对于未知的崇拜,读者根本没有理解任何东西。这样的崇拜让我在读第一本lisp书时就找宏看,结果在没有理解其他部分时就接触到宏,当时就看得一头雾水。而且一些强大的东西往往也会有很麻烦的副作用,宏也一样,但是Paul并没有把这些问题讲明白,其实在一些其他正经介绍lisp的书中都是非常小心地强调宏的危害——良好定义的宏会有非常强大的力量,但是一些垃圾宏会让整个程序变得难以理解并且混乱不堪。

    其实我看懂宏是由于篇文章,这文章没有任何对宏的赞扬,但是一旦你读懂你就会发现宏真正伟大的地方,它是从实用的角度来介绍宏,这种实用就是把宏当成代码生成器,并且文章还将宏与编译器以及一些其他技术进行对比来突出宏的优点。宏的基本概念在那篇文章中已经说得很清楚了,在这里就不罗嗦了。在这里我就只说一下为什么宏在scheme中非常好写,以及它的危害。

    scheme的宏的实现

    几乎所有的scheme实现都支持R5RS标准,这个标准定义了syntax-rules宏,在R6RS标准中定义了syntax-case宏,但是由于几乎所有的主流scheme实现都没有支持R6RS,很多也没有支持的打算,所以我就没去学。相对于Common Lisp的宏scheme的是相当的高阶,scheme的syntax-rules基于的是Patterns/Templates,也就是说在scheme中写宏只需要定义宏匹配的模式以及模式对应的模板就能实现干净的宏了。但是Common Lisp却没有这实现,只能用更加底层的宏。具体syntax-rules用法可以看本书,这里也不说了。

    宏的匹配

    根据前面篇文章,宏本身是用来生成代码的,这样说就是把编写宏和编写编译器进行比较了,只是宏更加简单,因为lisp整个语言表示就是基于链表的,而链表可以实现更加复杂的树型结构,这就类似于编译原理常常提到的语法树,是的,这也就是为什么Paul说写lisp程序就是直接写语法树了,而scheme宏的Patterns匹配的很大程度上就依赖于这一点。

    使用syntax-rules可以让我们非常好地理解lisp相对于其他语言的优势:假设我们要实现and的短路效应,我们可以按照下面的方法进行定义:

    (define-syntax and
      (syntax-rules ()
        ((and e1 e2)
         (if e1 e2 #f))))

    在定义了and宏之后我们用如下方法使用:

    (and (not (= x 0)) (/ 1 x))

    这是一个经典的避免被除数为0的方法,我们直接匹配了and宏,然后宏帮我们扩展成原始的语法。其中e1匹配了(not (= x 0)),e2匹配了(/ 1 x),之后宏再将and表达式扩展成(if (not (= x 0)) (/ 1 x) #f),这样前面对于and宏的调用就能按照预计的去执行。这一切最值得惊奇的是宏竟然能恰如预想的让e1匹配(not (= x 0)),而不是(或not等,这是因为你在写这代码时已经用括号指明了(not (= x 0))是一个表达式,他们是不能再分的了,假如lisp没有这些括号那么这样表达力超强的宏也就没有了用武之地。用任何其他语言都无法实现这样高效的宏。

    为什么要小心宏?

    lisp最为核心的一些函数就是lambda,car,cdr,eval,apply等,这些函数都是非常简单的,如果只有这些那么lisp是真正的没有任何语法了。这些基本的函数以及用户定义的函数运行方式由下面两个规则定义,这就是eval函数遵循的规则:

    1. 先解析表达式的子表达式。
    2. 整个表达式最左边子表达式的值就是操作符,其他子表达式的值就是操作数,将操作数作为参数调用操作符。

    所以对于下面的表达式:
    (+ (- 3 1) (* 2 3) 2)
    lisp是先eval(- 3 1)和(* 2 3),再将这些表达式的返回值当作参数传给+函数。

    在你写上面的表达式时你根本不需要考虑任何语法,甚至连算符的优先级都不需要考虑!所以说lisp是几乎没有语法的,正是由于这一点lisp可以说是非常容易学习的语言,你不需要像学其他语言一样去记住所有的语法,对于基本函数的调用规则只需要记住eval函数的两个规则就行。在开发软件时也一样,只使用最核心的函数可以让整个软件变得容易理解。宏一般是作为扩展lisp的语法而存在的,也就是说你定义一个宏就相当于定义了一个语法,这些语法会增加整个程序的复杂度,让软件变得更加难以理解。所以对于大型的软件要尽量少用宏,如果能用函数尽量用函数,不要用宏。


  4. 学习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的重点讲完,不过总的来说这本书非常好,能学到很多语言的细节,并且题目的设计也不错。


  5. 闭包,词法作用域和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属性,但这完全是通过函数的闭包特性来实现的,而不需要动摇整个语言,增加语言解析器的复杂度。