Structure and Interpretation of Computer Programs 1.3

看了这么久，终于把这本书的第一章看完了，估计第三节看的时间比前两节加起来还长了。不过第三节确实讲了很多东西。这一节主要讲的就是抽象，抽象，抽象，再抽象。。。最后你也变得抽象了。

1.3.1讲了把procedure作为参数传个另外的procedure[在scheme里面procedure的参数可以使任何你想传的东西，返回值也是任何你想返回的东西]。主要是把类似功能的procedure写成一个模板，然后参数是procedure，这样多个功能的procedure都可以用这个procedure来实现了。简单地说就是一个procedure计算a+b，另外一个procedure计算a*b，第三个procedure计算a-b。那么我们就可以写一个procedure，参数是运算符和相应的两个参数，这样就可以省去了很多重复的操作。

1.3.2主要介绍了lambda和let。为了后面做准备，lambda就是匿名procedure，define也会用到它。let是作为局部变量用的。

1.3.3这一小节也是说抽象，主要是用匿名表达式来写代码和let来表示局部变量。这一节里面说到了求一个函数的零点和一个函数的不动点。求f(x)零点的时候就是假设f(a)>0 f(b)<0那么在[a,b]中间至少存在一个零点，可以通过不停的二分来找到这个零点(当然f(x)是连续的，所以不能找到一个很准确的值，只能找一个误差比较小的)。求不动点的时候，就是首先猜测一个值，然后不停的计算当前值的函数值，知道函数值和自变量的差很小为止(关于这个比较的时候，如果自变量很小或者很大都不能直接用(x-f(x))来比较这样是很可能造成死循环，可以用比值来代替简单的减法)，还有就是有些函数，如果你直接用f(x)去替换x的话，也会造成死循环，这样你可以用average(x,f(x))来代替x，当然有些函数你一次average还不行，就必须用到多次average，这个在习题里面有体现。

1.3.4这一小节看上去很厉害的样子，看了我好久啊，现在我都变得抽象了，有木有啊！！！

这一节中主要讲的知识是procedure作为procedure的返回值，这个就比较有意思了，这样我们又可以把procedure再一次抽象化 了。这样我们也可以把procedure更加的分离开来，这样所有的procedure之间的耦合度就再次降低了有木有啊。把一个procedure作为返回值的话，需要用到lambda这一匿名过程表达式。比如下面这个

这个procedure的返回值是一个procedure，返回的这个procedure的返回值是average( x,f(x)),这样如果我们需要计算不同函数的average的话，那么我们只需要把相应的procedure作为参数传进去就行了

然后这一小节讲了Newton’s method，具体看这个链接吧。可以通过不动点就零点，同样可以反过来求，里面用到微分，微分的具体区间得自己取。然后最后面又讲了一种抽象(我表示现在看到神马都是抽象啊！！！)，把average和f函数分开传个相应的procedure。具体见下面这个procedure:

这里(transform g)就是fixed-point中的转移函数，我们这里又可以定义不同的转移方式。scheme最后表示反正你想怎么搞，它都能实现出来，无论你长得多抽象，它都不嫌弃了！！！

下面是习题的相关分析和解答：

1.29 计算，其中h = (b - a)/n，y_k = f(a + k__h)，a和b是这个区间，这个用1.3.1里面的sum函数可以很好的求出结果，分成4块，第一项，最后一项，剩下的按奇数偶数分开就成

1.30 把1.3.1节中的sum写成iterative的，这个比较简单，都写了好多次了

1.31要求仿照sum写product的procedure。然后要求计算，product的procedure完全可以照着sum的procedure写就行了。后面的也好写。接着你需要把你当product的procedure改成iterative的(如果你一开始的是recursive的)，反之亦反。

1.32再次抽象sum和product的procedure，写一个更加抽象的procedure，形如(accumulate combiner null-value term a next b)，其中accumulate是名字，combiner是组合器，null-value是最末尾的值(递归的终止条件下的值) 剩下的和sum中的几个意思一样。这里也可以仿照sum来写，不过把相应的改成抽象就行了。

1.33把上一题中的procedure再加一个参数，即filter。表示从a到b中满足filter条件的才计算。这个只需要在上面一题的procedure中判断下是否满足条件即可。然后写filter的时候自己仔细写

1.34给一个procedure：

然后你求(f f)的值，给出说明。首先结果是会出错。然后说明：(f f)–>(f 2)->(2 2)然后就出错了。

1.35用1.3小节中的fixed-point procedure来计算黄金分割率。这个只要写出相应的变换函数就行了，如下

1.36首先修改fixed-point，从而可以打印出所有的guess数，这个好办，直接display就行了。另外写一个procedure，计算x^x=N,其中N是给定的数，求x，这个也即是求x->log_x{N}的的一个不动点。函数关系出来之后，procedure就好写了，对于log_x{N}可以用log_e{N}/log_e{x}，刚好scheme里面的log就是log_e的。

1.37给出连分数的形式，然后写一个procedure来计算k层连分数的值，而且所有的分子分母不一定是一样的，然后接着改成iterative的(如果一开始是recurrence的)，反之亦然。我的代码如下：

1.38用连分数求出e - 2的值，其中e是自然对数的底。题中给出了连分数相应的分子分母值的函数，具体实现还是比较容易的。

1.39给出这么个东西，然后需要你写一个procedure，而且由用户确定深度，这个就是连分数的变形，不过相应的分子分母通项需要自己求出来而已。

1.40写一个cubic的procedure，通过用(newtons-method (cubic a b c) 1)来计算x^3+ax^2+bx+c=0的解。这个只需要写那个procedure容易了。就是传入a，b，c返回x^3+ax^2+bx+c就行了

1.41定义一个叫做double的procedure。传入一个procedure，返回执行这个procedure两次之后的procedure。这个定义还算好写：

接下来的就纠结了。求(((double (double double)) inc) 5)的值，其中inc是把一个数加1的procedure。一开始想着是13(=5+8)，可以运行出来结果是21(=5+16)。想不通啊想不通，调试也没找到什么理由，最后在网上找了答案，这里写的很详细，自己照着手动执行一次，就会清楚很多东西，而且遇到类似的也再也不怕了。最后还知道了如果把inc放最里面的话，结果是13.此题强烈建议手动执行

1.42写一个compose的procedure，传入两个procedure，分别是f和g，然后先执行f，再执行g，这个可以仿照double的写法来上一个。

1.43写一个名叫repeated的procedure，传入一个procedure，和一个数值n，表示把传入的procedure执行n次，最后让你用写出来的repeated的procedure来计算((repeated square 2) 5)，从而验证。

提示给出了可以用compose，当然也可以用double了。也就是前两个习题的的procedure。不过也可以不用前两个东西:

关于log_2{N}的写法就是不等于1的时候，可以利用double来进行加速，类似快速幂的方法。

1.44写一个smooth的procedure，参数是一个叫做f的procedure，然后返回(f(x)+f(x-dx)+f(x+dx))/3的一个procedure。然后利用smooth和上一题的repeated来写一个nth-smooth，表示smootn次。写第一个procedure的时候比较简单，一下就出来了，第二个也不难，就写成(repeated smooth n)就变成了nth-smooth了。最后自己再检测下写的是否正确。

1.45 给出一系列说明，说求sqrt和3次根的时候，average-damp只需要用一次，然后求4次根的时候用2次，让你通过实验得出一个求n次根的抽象procedure。这里首先你必须得知道对于n次根，需要用多少次average-damp。实验4,5,6,7的时候都是2次，但是8的时候是3次，大致可以猜测需要的是floor(log_2{n})次average-damp。算出这个次数之后，程序就变得非常好写了。如下

其中log2是一个自定义的procedure，表示以2为底n的对数，pow也是一个自定义的procedure，计算y的(n-1)次。

1.46因为前面有很多procedure是传入两个procedure，其中一个是good-enough?，因外一个是improve，现在你需要写一个抽象的procedure，传入这两个procedure，然后传回一个procedure，传回的procedure有一个参数guess。这个过程还是比较绕的，不过在做过前面的几个习题之后，会发现这个习题也是可做的。代码如下：

这个procedure，看起来很简单,但是写起来不那么简单，不过题目已经给你打好框架了，你只需要填写lambda里面的东西。写了前面的一些题，会发现，差不多都是这样，里面调用一个procedure，然后多次调用这个里面的procedure就完事了。

终于把第一章看完了，继续加油。好好学习，天天向上。