RSS Feed

December, 2011

  1. 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的方法。


  2. 理性和快乐

    December 11, 2011 by xudifsd

    人不是可以机械化处理的机器,他的生命尊严来源于他的非理性的情感。——许知远

    以前我总是认为人区别于动物就是因为人的理性,正是因为理性人类的科技才会如此发达,人们才可以使用各种各样的人造物品,也正是因为理性人们的社会才有秩序,而不像动物群体一样需要靠暴力来进行统治。因此我也就想当然地觉得作为正常的人应该抵制自己的非理性,也就是抵制自己内心的“兽性”。因此我尽量让自己变成一个理性的人,理解所有的事情,根据这些了解再去决定,尽量避免无意义的谈话,只做自己认为有价值的事。这样的做法在很大程度上让我做事和学习变得非常有效率,但是随之而来的是不快乐。这是一件非常矛盾的事情——我可以让自己做事非常高效,尽快地得出结果,并且也是最优的结果。但是很可笑的是我对此并不感到快乐,相反如果我发现自己做错了会非常后悔为什么当初没考虑这一点。

    我本以为这是我个人的问题,但是看了许知远的《那些忧伤的年轻人》之后我发现这是一个社会问题。书中谈到了很多社会的变化,许知远站在很高的高度上看从15世纪到现在社会的变化。下面就摘自这本书:

    人不是可以机械化处理的机器,他的生命尊严来源于他的非理性的情感;而世界也不是可以依靠科学定律简单描绘的,它是断裂的、无连续的和经常绝望的,而非完整的理性的秩序的和令人乐观的;我们隐藏于内心世界的欲望比外在的世界更难以征服。弗洛伊德在《文明及其不满》中说过:“我们所谓的文明充满着这样多的苦难和不幸,其本身就应该受到谴责,我们如果将它全部抛弃,回复到原始状态,我们会更加幸福。”

    书中说道在工业革命之后人们越来越像一个没有思想的机器,人性在整个社会分工细化的大背景下表现出极度的萎缩,之后的社会的特点就是人的特性在不断遭到蚕食,我们越来越像实现社会目的的工具。社会越来越进步,但是社会上的人也越来越不快乐。我们抑制自己的人性,抑制能让自己真正快乐的情感。去当社会的螺丝钉,去实现社会的目的。其实理性在很大程度上是阻碍我们快乐的原因,我们真正的快乐是源自于本能,但是为了更加有效率的工作我们又必须抑制自己的情感,做一个理性的人。

    哈佛大学有一门非常热门的公开课——幸福课,课堂上说道了幸福的原因:

    在现代社会,我们不准许自己为人(We don’t give ourselves the permission to be human),并且不给自己体会自己情绪的自由。我们为这些生而有之的事实付出高昂代价。但是当我们还是婴儿时我们准许自己为人,我们知道那是自然的,我们根本不去考虑它,自然而然地经历起起落落。但是当我们开始发觉其他人在看我们,时刻评价我们时,我们停止准许自己为人,不轻易表达自己的情感。

    如果我们在这个社会上时刻表现自己的情感那么别人就会认为我们是不理智的,也就是不可靠的,所以这个社会要求我们压制自己的本能,这样社会才能有效率运转,我们才能更加有效地生产和生活。但是我们为此付出代价就是我们压抑了自己的人性,而这种人性正是我们幸福的原因。

    一定的理性能让我们生活得更好,这是我们区别于兽的原因,但是过度的理性只会让我们陷入泥潭,如果我们完全理性,压抑自己的情感,那么我们也便和机器毫无差别,也就没有了生命的尊严。


  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的语法而存在的,也就是说你定义一个宏就相当于定义了一个语法,这些语法会增加整个程序的复杂度,让软件变得更加难以理解。所以对于大型的软件要尽量少用宏,如果能用函数尽量用函数,不要用宏。