发表于   |   分类于

第一章 构造过程抽象

1.3 用高阶函数做抽象

EX 1.40

1
2
3
;定义过程cubic
(define (cubic a b c)
  (lambda (x) (+ (cube x) (* a (square x)) (* b x) c)))

EX 1.41

1
2
3
(define (double f)
  (lambda (x)
    (f (f x))))
1
(((double (double double)) inc) 5)  ;答案是21

分析:
((double inc) 5) 将inc应用2^1次,结果为7
(((double double) inc) 5) 将inc应用2^2次,结果为9
((double (double double)) inc) 5) 将inc应用(2^2)^2次,结果为21

EX 1.42

1
2
3
(define (compose f g)
  (lambda (x)
    (f (g x))))

EX 1.43

1
2
3
4
5
6
7
8
9
10
11
12
13
;递归版本
(define (repeated f n)
  (if (= n 1)
      f
      (lambda (x)
        (f ((repeated f (- n 1)) x)))))
;迭代版本
(define (re-iter f n)
  (define (iter i f-result)
    (if (= i n)
        f-result
        (iter (+ i 1) (lambda (x) (f (f-result x))))))
  (iter 1 f))

根据提示,可以使用EX 1.42的compose过程,省去了使用lambda

1
2
3
4
5
6
7
8
9
10
11
12
;使用compose的递归版本
(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))
;使用compose的迭代版本
(define (repeated f n)
  (define (iter i f-result)
    (if (= i n)
        f-result
        (iter (+ i 1) (compose f f-result))))
  (iter 1 f))

EX 1.44

1
2
3
4
5
6
7
8
;一次平滑
(define (smooth f)
  (define dx 0.000001)
  (lambda (x)
    (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3))) 
;n次平滑
(define (n-smooth f n)
  (re1 smooth n) f)

发表于   |   分类于

第一章 构造过程抽象

1.3 用高阶函数做抽象

EX 1.32

a)

1
2
3
4
5
6
7
8
9
10
11
12
13
;accumulate递归版本
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))
;sum测试,计算立方和
(define (cube-sum a b)
  (accumulate + 0 cube a next b))
;product测试,计算阶乘
(define (factorial n)
  (define (f x) x)
  (accumulate * 1 f 1 next n))
(cube-sum 1 10)
(factorial 6)

结果
“1-32”

b)

1
2
3
4
5
6
7
;accumulate迭代版本
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

EX 1.33

a)

1
2
3
4
5
6
7
8
9
10
11
12
;相比EX 1.32,增加参数filter,用于过滤一些项
(define (filtered-accumulate combiner null-value filter f a next b)
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (f a) (filtered-accumulate combiner null-value filter f (next a) next b))
          (filtered-accumulate combiner null-value filter f (next a) next b))))
;计算a到b之间素数和
(define (prime-sum a b)
  (define (f x) x)
  (filtered-accumulate + 0 prime? f a next b))
;prime?见书P33页

其实可以使用let来定义剩余项,因为按照书中课后习题的学习顺序,这里并没有使用let

(let rest (filtered-accumulate combiner null-value filter f (next a) next b))

b)

1
2
3
4
(define (gcd-product n)
  (define (f x) x)
  (define (its-prime? x) (= (gcd x n) 1))
  (filtered-accumulate * 1 its-prime? f 1 next n))

EX 1.34

(f f)        -> 
(f 2)        ->
(2 2)        -> 解释器无法解释(2 2),因为2并不是一个过程(not a procedure)

EX 1.35

1
2
3
;fixed-point见书P46页
(define golden-ratio
  (fixed-point (lambda (x) (+ (/ 1 x) 1)) 1.0))
golden-ratio is 1.6180327868852458

EX 1.36

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;可以打印近似值序列的new-fixed-point, close-enough见书P45页
(define (new-fixed-point f first-guess)
  (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance))
  (define (try guess step)
    (let ((next (f guess)))
      (cond ((close-enough? guess next) next)
            (else
             (display "step: ")
             (display step)
             (display ", ")
             (display next)
             (newline)
             (try next (+ step 1))))))
  (try first-guess 1))
;计算公式
(define loglog (lambda (x) (/ (log 1000) (log x))))
;平均阻尼计算过程,见书P48页
(define (average-damp f) (lambda (x) (average x (f x))))
;不使用平均阻尼
(define (no-damp-loglog x) (new-fixed-point loglog x))
;使用平均阻尼
(define (damp-loglog x) (new-fixed-point (average-damp loglog) x))

使用平均阻尼，可以使过程更快的收敛，因此计算步数更少。

结果
“1-36-1”
“1-36-2”

EX 1.37

a)

1
2
3
4
5
6
7
8
9
10
11
12
;递归版本
(define (cont-frac n d k)
  (define (f i)
    (if (= k i)
        (/ (n i) (d i))
        (/ (n i) (+ (f (+ i 1)) (d i)))))
  (f 1))
;测试是否逼近
(define (check-cont-frac k)
  (cont-frac (lambda (i) 1.0)
             (lambda (i) 1.0)
             k))

需要至少k=11，具有十进制的4位精度

结果
“1-37”

b)

1
2
3
4
5
6
7
;迭代版本
(define (cont-frac n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1) (/ (n i) (+ (d i) result)))))
  (iter (- k 1) (/ (n k) (d k))))

EX 1.38

1
2
3
4
5
6
(define (e k)
  (define (di i)
    (if (= (remainder i 3) 2)
        (* (/ (+ i 1) 3) 2)
        1))
  (+ (cont-frac (lambda (ni) 1.0) di k) 2.0))

问题的关键在于找到Di序列的规律,发现三个数为一组,发现mod 3 = 2时,Di不等于1。随着k的增大，e的值精确度越高

结果
“1-38”

EX 1.39

1
2
3
4
5
6
7
8
9
10
(define (tan-cf x k)
  (define (di i)
    (if (= i 1)
        1
        (- (* i 2) 1)))
  (define (ni i)
    (if (= i 1)
        x
        (- (square x))))
  (cont-frac ni di k))

问题的关键在于生成奇数序列Di和x序列Ni

发表于   |   分类于

电信竞争与管制——阚凯力老师

今天终于看到了阚凯力老师的真人，老师昨天才从摩洛哥开会回来，一开始就普及了一下ICANN。

百度了一下阚老师的履历，清华无线电系，因为文革中断学业，后来又考上北邮研究生，之后成为新中国成立后第一批留美学生，去斯坦福读了博士，在太平洋贝尔工作了一段时间，个人经历也是很传奇。

聆听这位经历过许多事情的老师授课，感触颇深。抛开其针对体制的一些看法，让我感触最深的是这位老人的对教育的一些思考。斯坦福给他所带来的，除了一个博士头衔之外，更重要的是两点

  • 有信心敢于承认自己不懂
  • 技术是为经济服务的

有关第一点，阚老师关于自己与休斯公司的故事令人记忆深刻。美国企业的航天计划被一个中国留学生所指导，说起来只因为一个词——common sense。因为敢于承认自己不懂，从自身常识来分析，指出运载飞船的高成本和高风险而丢失市场这一事实背后所体现出来的技术和体制的不合理。

有关第二点，阚老师作为一位有技术背景的人才，后来转而去学习管理、学习经济学，也是因为他看到了真正能变革的推动力，并不是技术，而是思想。这也是斯坦福之所以是硅谷摇篮的关键，师生们思考的是一种新技术能有什么作用？能为社会带来怎样的变革？进而将其产业化，投入市场经济中验证其合理性，反过来再改进技术，而非为技术而技术。反观我身边的大环境，应该改变的东西仍很多。

发表于   |   分类于

第一章 构造过程抽象

1.3 用高阶函数做抽象

EX 1.29

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
;38页递归版本sum
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a) (sum term (next a) next b))))
(define (simpson f a b n)
  (define h (/ (- b a) n))
  (define (yk k) (f (+ a (* k h))))
  (define (next k) (+ k 1))
  (define (coefficient k)
    (cond ((or (= k 0) (= k n)) 1)
          ((odd? k) 4)
          (else 2)))
  (define (term k)
    (* (coefficient k) (yk k)))
  (* (sum term 0 next n) (/ h 3)))

结果
“1-29”

EX 1.30

1
2
3
4
5
6
7
;sum的迭代版本
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))

EX 1.31

a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;类似于sum的过程product,递归版本
(define (product f a next b)
  (if (> a b)
      1
      (* (f a) (product f (next a) next b))))
;用product定义阶乘过程factorial
(define (factorial n)
  (define (f x) x)
  (define (next i) (+ i 1))
  (product f
           1
           next
           n))
;计算pi值,首先计算每一个分数
(define (fraction i)
  (if (odd? i)
      (/ (+ i 1) (+ i 2))
      (/ (+ i 2) (+ i 1))))
;计算pi值,n是精确度
(define (pi n)
  (define (next i) (+ i 1))
  (* (product fraction 1.0 next n) 4.0))

结果
“1-31a”

b)

1
2
3
4
5
6
7
;product的迭代版本
(define (product f a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (f a) result))))
  (iter a 1))

发表于   |   分类于

Play Framework 笔记(1)

从去年七月开始进入实验室，一直使用的就是Play Framework来进行Web开发，慢慢的应该总结一些东西，免得以后忘记。

先说说Play这个框架吧，使用了一段时间，直观的感觉是：

  • MVC架构很清晰，Model层针对数据封装、数据库操作，Controller层负责响应各个请求，View层主要就是一些Html的东西来呈现在浏览器上。
  • Debug之后可以在浏览器上直接看到error

以下援引自Wiki

Play is an open source web application framework, written in Scala and Java, which follows the model–view–controller (mvc) architectural pattern. It aims to optimize developer productivity by using convention over configuration, hot code reloading and display of errors in the browser.
Support for the Scala programming language has been available since version 1.1 of the framework.In version 2.0, the framework core was rewritten in Scala. Build and deployment was migrated to SBT, and templates use Scala instead of Groovy.

一个软件工程的术语convention over configuration

约定优于配置(convention over configuration)，也称作按约定编程，是一种软件设计范式，旨在减少软件开发人员需做决定的数量，获得简单的好处，而又不失灵活性。
本质是说，开发人员仅需规定应用中不符约定的部分。例如，如果模型中有个名为Sale的类，那么数据库中对应的表就会默认命名为sales。只有在偏离这一约定时，例如将该表命名为”products_sold”，才需写有关这个名字的配置。

一开始配环境的时候，被人告知应该装一个typesafe-activator，很懵逼的是不知道这个玩意儿和Play框架有什么关系，继续google。发现typesafe这公司已经更名为Lightbend了，当然这并没有什么影响。继续看看他们的Activator

Activator is the Lightbend Reactive Platform’s build and tutorial tool

看起来Activator是一个构建工具的样子，在Play可以看到教程，如何使用Lightbend Activator安装Play，以及一些相关的配置需求。最开始接触的Play 2.2,现在version已经到了2.5，感觉已经有点跟不上节奏了快。大致扫了一眼新版本的配置，相比之前越来越简洁了，activator也有UI界面，可以新建各个项目，当然Play项目也是可以的。
看了一下Lightbend的官网，这个公司做的东西也有一点意思，他们的产品Lightbend Reactive Platform包括以下几个

  • ConductR
  • Monitoring
  • Lagom
  • Apache Spark

Spark还算知道一点点，前三个完全是很陌生的东西了，随便查了一下，有这样的内容

《Lagom：一个新的微服务框架》——Lightbend，也就是Akka背后的公司，最近发布了一款开源的微服务框架Lagom，它构建在他们的Reactive平台之上，尤其是使用了Play框架和Akka的家族产品，并添加了ConductR用于部署。

对Typesafe(Lightbend)这个公司看了一下

Typesafe (now Lightbend) is a company founded by Martin Odersky, the creator of the Scala programming language, Jonas Bonér, the creator of the Akka middleware, and Paul Phillips in 2011. It provides an Open source platform for building Reactive applications for the JVM, consisting of the Play Framework, Akka middleware and Scala programming language—with additional supporting products and development tools such as the Scala IDE for Eclipse, the Slick database query and access library for Scala and the sbt build tool. Typesafe also provides training, consulting and commercial support on the platform.
Typesafe is one of the main contributors of Reactive Streams.

这里有几个点值得关注

  • Akka: 简化并发问题的开源工具包
  • Reactive: Reactive Programming, 一种面向数据流和变化传播的编程范式
  • sbt: 构建Scala和Java项目的工具，类似于Maven和Ant

言归正传，Play的工程结构这样的，MVC层次分明。
“play”

在一开始配置play2.2的时候，遇到的主要的问题有

  • 集成在Intellij 13中
  • 依赖的jar包很多

我采用的办法是使用Activator直接new play application，再导入Intellij中。所依赖的jar包很多，只能从公司的服务器上把ivy仓库全部download下来覆盖本地。
后来用了intellij 14、15版本，对于Scala、playframework的集成好多了，直接装个Scala plugin，ivy一覆盖就行。

发表于   |   分类于

随笔

就记录两句话吧，“急事缓办”，“切勿交浅言深”

好像几年过去了还是到了这个日子会有紧张与不安，也说不清是为什么，也许更多的是内心的挣扎作祟吧。越来越多的自我怀疑，放弃一件坚持很久但却不可能的事情仿佛像是戒毒一般，刚刚狠狠下定的决心，转眼间就被抹去。然而深究这样反复不定的原因，竟然还只与自己有关，并无他人之故。每当想到这里便也释怀一些，从一开始就是自己的肆意妄为但又连累他人，沉迷于幻想之中难以自拔。

再次见面内心仍然会起波澜，表面上的平静如水只是掩盖了底下的波澜起伏。好奇对方的变化，关切近日的踪迹，但其实都是无济于事的，只是需要反复告诉自己这些，加深记忆吧。

也不知道为什么会有逃避的冲动，不敢直面，恐惧？紧张？担心？还没有分清，换而言之，问题还是不够了解自己，又关对方何事，苦笑一声便就此作罢吧。

还会起波澜，便是未曾放下；仍会想起，便是存于心间。可悲可叹，解铃还须系铃人，但是自己却系了死结。

无论是弱懦、害怕、紧张、胆怯、痴情、懒惰亦或是其他什么样子的，都是在这具肉体上所承载的，接纳自己的软肋，面对它们，内心反而更轻松一些，而这就是人，优点与缺点都很明显的生物。

发表于   |   分类于

第一章 构造过程抽象

1.2 过程与它们所产生的计算

EX 1.21

smallest-divisor程序如下

1
2
3
4
5
6
7
8
(define (smallest-divisor n)
	(find-divisor n 2))
(define (find-divisor n test-divisor)
	(cond ((> (square test-divisor) n) n)
		  ((divides? test-divisor n) test-divisor)
		  (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
	(= (remainder b a) 0))
(smallest-divisor 199)        ;answer is 199
(smallest-divisor 1999)        ;answer is 1999
(smallest-divisor 19999)    ;answer is 7

EX 1.22

解决这个问题，可以把问题划分成几个子问题来解决，这也是SICP这本书所教授的核心问题职业——如何将复杂问题分解

如何生成连续奇数？
如何描述大于某数x的前i个素数？
如何判断素数？
如何计算程序运行时间？

1
2
3
4
5
;生成奇数
(define (odd-generator x)
	(if (odd? x)
		(+ x 2)
		(+ x 1)))
1
2
3
4
5
6
7
8
;大于x的前i个素数
(define (continue-prime i x)
	(cond ((= i 0) (display "These are all primes"))
		  ((prime? x)
			(display x)
			(newline)
			(continue-prime (- i 1) (odd-generator x)))
		  (else (continue-prime i (odd-generator x)))))
1
2
3
4
5
6
7
8
9
10
11
;判断素数,可以采用33页最基本的方法
(define (prime? n)
	(define (smallest-divisor n)
		(find-divisor n 2))
	(define (find-divisor n test-divisor)
		(cond ((> (square test-divisor) n) n)
			  ((divides? test-divisor n) test-divisor)
			  (else (find-divisor n (+ test-divisor 1)))))
	(define (divides? a b)
		(= (remainder b a) 0))
	(= n (smallest-divisor n)))
1
2
3
4
5
6
7
;运行时间计算
;(runtime)返回的是秒,(real-time-clock)返回毫秒
;最终的search-for程序:
(define (search-for-primes x)
	(let ((start-time (real-time-clock)))
	(continue-prime 3 x)
	(- (real-time-clock) start-time)))

结果
“1-22”

结果分析放在1.24，显然并不遵循预期的结果

EX 1.23

首先定义一个新的prime过程——new prime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (new-prime? n)
	(define (next x)
		(if (= x 2)
		    3
		    (+ x 2)))
	(define (smallest-divisor n)
		(find-divisor n 2))
	(define (find-divisor n test-divisor)
		(cond ((> (square test-divisor) n) n)
			  ((divides? test-divisor n) test-divisor)
			  (else (find-divisor n (next test-divisor)))))
	(define (divides? a b)
		(= (remainder b a) 0))
	(= n (smallest-divisor n)))

然后用这个新的素数判断过程重写continue-prime

1
2
3
4
5
6
7
(define (continue-newprime i x)
	(cond ((= i 0) (display "These are all primes"))
		  ((new-prime? x)
			(display x)
			(newline)
			(continue-prime (- i 1) (odd-generator x)))
		  (else (continue-prime i (odd-generator x)))))

最后重写search-for方法

1
2
3
4
(define (search-for-newprimes x)
	(let ((start-time (real-time-clock)))
	(continue-newprime 3 x)
	(- (real-time-clock) start-time)))

当然，scheme里新绑定的过程会覆盖原来的，可以局部替换为新的过程，为了更明显一些，都重写了这些过程
结果
“1-23”

结果分析放在1.24，显然也并不遵循预期的结果

EX 1.24

同1.23。使用费马定理来判断是否为素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (fast-prime? n times)
  (define (expmod base exp m)
    (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))
  (define (fermat-test n)
    (define (try-it a)
      (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1)))))
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))

重写continue-prime和search-for

1
2
3
4
5
6
7
8
9
10
11
(define (continue-fastprime i x)
	(cond ((= i 0) (display "These are all primes"))
		  ((fast-prime? x 100)
			(display x)
			(newline)
			(continue-prime (- i 1) (odd-generator x)))
		  (else (continue-prime i (odd-generator x)))))
(define (search-for-fastprimes x)
	(let ((start-time (real-time-clock)))
	(continue-fastprime 3 x)
	(- (real-time-clock) start-time)))

结果
“1-24”

结果分析,1.22,1.23,1.24三个例子中，可以明显看到，随着问题复杂度的增加，用时并不按照理论耗时增长。结果可能有以下原因，机器的差异，运行环境的差异，资源的占用情况，编译器优化等等，都会影响到程序的运行速度。然而，随着复杂度逐渐加大，可以看到，复杂度更低的算法效率更高。

EX 1.25

Alyssa的程序理论上更快，但是实际操作中发现，当底数和幂都很大的时候，使用fast-expt计算速度非常慢，而且占用大量CPU资源。究其原因，书中34页的expmod程序，每一次幂的结果都会进行remainder操作，从而将幂控制在一个合理的范围内，防止溢出。

EX 1.26

显然，Louis的程序在偶次幂时，两次调用expmod。也看到有这样的分析：

Louis的expmod使得原来的线性递归变成了具有两个分支的树形递归
计算量是原来expmod复杂度的平方，即Θ(logn)的平方，即Θ(n)
而prime?的复杂度是Θ(sqrt n)，所以比prime?还慢

EX 1.27

1
2
3
4
5
6
7
8
9
10
;是否同余
(define (same-remainder? a n)
	(= (expmod a n n) a))

(define (carmichael n)
	(iter 1 n))
(define (iter a n)
	(cond ((= a n) "YES")
		  ((same-remainder? a n) (iter (+ a 1) n))
		  (else "NO")))
(carmichael 561)
(carmichael 1105)
(carmichael 1729)
(carmichael 2465)
(carmichael 2821)
(carmichael 6601)

以上几个数均骗过了费马检查

结果
“1-27”

EX 1.28

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
;求一个数是否是非凡平方根,即非零非n-1的数x，x平方模n结果为1
(define (special-square-root? x n)
	(and (= (remainder (square x) n) 1) 
		 (not (= x 0))
		 (not (= x (- n 1)))))

;改进expmod过程,增加判断非凡平方根
(define (expmod base exp m)
	(cond ((= exp 0) 1)
		  ((special-square-root? base m) 0)
		  ((even? exp)
			(remainder (square (expmod base (/ exp 2) m)) m))
		  (else
			(remainder (* (expmod base (- exp 1) m) base) m))))

;随机取一个数a,并且a<n
(define (rand-smaller-than-n n)
	(let ((x (random n)))
	(if (not (= x 0))
		x
		(rand-smaller-than-n n))))

;Miller-Rabin测试
(define (miller-rabin-test n)
	(let ((times n))
		(define (miller-prime? n times)
				  (cond ((= times 0) true)
				  ((= (expmod (rand-smaller-than-n n) (- n 1) n) 1) (miller-prime? n (- times 1)))
				  (else false)))
		(miller-prime? n times)))
(miller-rabin-test 561)
(miller-rabin-test 1105)
(miller-rabin-test 1729)
(miller-rabin-test 2465)
(miller-rabin-test 2821)
(miller-rabin-test 6601)
(miller-rabin-test 13)
(miller-rabin-test 19)
(miller-rabin-test 23)

结果
“1-28”

发表于   |   分类于

第一章 构造过程抽象

1.2 过程与它们所产生的计算

EX 1.9

过程1

(+ 4 5)                             ——>
(inc (+ 3 5))                         ——>
(inc (inc (+ 2 5)))                 ——>
(inc (inc (inc (+ 1 5))))             ——>
(inc (inc (inc (inc (+ 0 5)))))     ——>
(inc (inc (inc (inc 5))))             ——>
(inc (inc (inc 6)))                 ——>
(inc (inc 7))                         ——>
(inc 8)                             ——>
9

过程2

(+ 4 5)                ——>
(+ 3 6)                ——>
(+ 2 7)                ——>
(+ 1 8)                ——>
(+ 0 9)                ——>
9

明显，过程1是线性递归(Linear-Recursion)，过程2是迭代(Iteration)。如公开课(链接)Lec1b里讲到的那样，
对于过程1，时间复杂度和空间复杂度都随着问题规模的增大而增大

time = O(a)
space = O(a)
对于过程2，显然空间复杂度会是一个常数(当然这也并不完全准确，随着计算的数增大，所需要的空间也在变化)
time = O(a)
space = O(1)

EX 1.10

(A 1 10)     ;answer is 1024
(A 2 4)        ;answer is 65536
(A 3 3)        ;answer is 65536
(define (f n) (A 0 n))        ;f(n)=2n
(define (g n) (A 1 n))        ;g(n)=2^n
(define (k n) (A 2 n))        ;k(n)=2^2^2^…… 连续求n次平方

EX 1.11

递归版本
(define (f n)
    (if (< n 3)
          n
          (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

迭代版本
(define (f n)
    (define (iter n a b c i)
        (if (= i n)
            c
            (iter n 
                  (+ a (* 2 b) (* 3 c))
                  a
                  b
                  (+ i 1))))
    (iter n 2 1 0 0))

迭代版本需要观察
f(0)=0, f(1)=1, f(2)=2
f(3)=f(2)+2f(1)+3f(0)
f(4)=f(3)+2f(2)+3f(1)
f(5)=f(4)+2f(3)+3f(2)
a、b、c分别表示f(n-1) f(n-2) f(n-3)
这里的i，个人认为可以类比其他语言中循环语法里的计数变量i，而迭代器iter可以类比于for、while等循环

EX 1.12

1
2
3
4
(define (pascal r c)
	(cond ((or (= r c) (= c 0)) 1)
    	  ((> c r) "error")
    	  (else (+ (pascal (- r 1) (- c 1)) (pascal (- r 1) c)))))

EX 1.13 1.14略

EX 1.15

a) p将被使用五次
(sine 12.15)                        ——>
(p (sine 12.15/3))                    ——>
(p (p (sine 12.15/6)))                ——>
(p (p (p (sine 12.15/9))))            ——>
(p (p (p (p (p (sine 12.15/12)))))    ——>
(p (p (p (p (p (sine 0.0514……)))))    ——>
…………

b) 求值(sine a)时候，除以3.0，sine是递归程序，因此时间复杂度和空间复杂度都是O(log a)

EX 1.16

1
2
3
4
5
6
7
8
9
10
(define (even? x)
  (= (remainder x 2) 0))
(define (square x)
	(* x x))
(define (exp b n)
	(define (exp-iter b n p)
		(cond ((= n 0) p)
      		  ((even? n) (exp-iter (square b) (/ n 2) p))
      		  (else (exp-iter b (- n 1) (* b p)))))
	(exp-iter b n 1))

EX 1.17

1
2
3
4
5
6
7
8
9
10
(define (double x)
  (+ x x))
(define (halve x)
  (/ x 2))
(define (even? x)
  (= (remainder x 2) 0))
(define (expt b n)
  (cond ((= n 0) 0)
        ((even? n) (double (expt b (halve n))))
        (else (+ b (expt b (- n 1))))))

EX 1.18

1
2
3
4
5
6
7
8
9
10
11
12
(define (double x)
  (+ x x))
(define (halve x)
  (/ x 2))
(define (even? x)
  (= (remainder x 2) 0))
(define (multi a b)
  (define (multi-iter a b p)
    (cond ((= b 0) p)
          ((even? b) (multi-iter (double a) (halve b) p))
          (else (multi-iter a (- b 1) (+ a p)))))
  (multi-iter a b 0))

EX 1.19

通过两次变换，可以得到
p’ = p^2 + q^2
q’ = 2pq + q^2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (even? x)
  (= (remainder x 2) 0))
(define (fib n)
  (define (fib-iter a b p q count)
    (cond ((= count 0) b)
          ((even? count)
           (fib-iter a
                     b
                     (+ (square p) (square q))
                     (+ (* 2 p q) (square q))
                     (/ count 2)))
          (else (fib-iter (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))
                          p
                          q
                          (- count 1)))))
  (fib-iter 1 0 0 1 n))

EX 1.20

正则序
(gcd 206 40)        //a=206,b=60                ——>
(gcd 40 (r 206 40)) //a=40,b=6,r1=(r 206 40)    ——>r1:1
(gcd r1 (r 40 r1))  //a=6,b=4,r2=(r 40 r1)        ——>r2:1+1=2
(gcd r2 (r r1 r2))  //a=4,b=2,r3=(r r1 r2)        ——>r3:1+1+2=4
(gcd r3 (r r2 r3))  //a=2,b=0,r4=(r r2 r3)        ——>1+2+4=7
r3 = (r r1 r2)
    |
    V
(r (r 206 40) (r 40 (r 206 40))                    ——>1
    |
    V
(r (r 206 40) (r 40 6))
    |
    V
(r 6 4)                                            ——>2
2                                                ——>1

正则序执行了1+2+4+7+1+2+1=18次remainder运算

应用序
(gcd 206 40)
(gcd 40 (r 206 40))          ——>1
(gcd 40 6)
(gcd 6 (r 40 6))             ——>1
(gcd 6 4)
(gcd 4 (r 6 4))              ——>1
(gcd 4 2)
(gcd 2 (r 4 2))             ——>1
(gcd 2 0)
2

应用序执行了1+1+1+1次remainder运算

发表于   |   分类于

第一章 构造过程抽象

1.1 程序设计的基本元素

ex 1.1 ~ ex 1.4都比较容易理解，就不写出结果了

EX 1.5

1
2
3
4
5
6
(define (p) (p))

(define (test x y)
  (if (= x 0)
       0
       y))

求值

(test 0 (P))

分析：

采用应用序，先求参数值再应用， (p)无限递归调用自身，编译器停滞
采用正则序，先展开后规约求值，实参0和(p)不会先求值，解释到if之后，返回0

EX 1.6

1
2
3
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

对于这个程序题中演示的使用

(new-if (= 2 3) 0 5)
(new-if (= 1 1) 0 5)

都是没错的，但若用来重写sqrt程序的话
“error”

分析：错误原因是超过递归最大深度
new-if 作为定义的一个过程，由于scheme采用应用序，先求参数值再应用，调用顺序
*sqrt-iter -> new-if -> cond -> sqrt-iter -> new-if -> …… -> * 最终超出栈最大深度

EX 1.7

原始程序
“很大的数”
“很小的数”
当数字很大时，程序跑不动，当数字很小时，结果错误

修改过程good-enough为

1
2
3
4
(define (good-enough? guess x)
	(< 
	  (/ (abs (- x guess)) guess) 
	  0.001))

对于很大和很小的数字都可以计算平方根

EX 1.8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (square x)
  (* x x))
(define (cube x)
  (* x x x))
(define (cube-root x)
  (define (good-enough? guess)
    (< (abs (- (cube guess) x)) 0.001))
  (define (improve guess)
    (/ (+ (/ x (square guess)) (* 2 guess)) 3))
  (define (cube-iter guess)
    (if (good-enough? guess)
        guess
        (cube-iter (improve guess))))
  (cube-iter 1.0))

发表于   |   分类于

最近开始看SICP这本神书，先草草看了前三章半，看了一点题目，最近开始跟着两位作者的公开课学习。先说一下对这本书的整体感觉吧，抽象程度比较高，对于计算机程序的理解不再停留于语法的层面，而是剖开现象看本质，探讨计算机程序的本质内容——具象化人的思维。

如作者所言，对CS而言，关键在于

Techniques for controlling the complexity of large system —— 控制大型系统中的复杂度

而这，也是这本书所讨论的核心问题，如何降低复杂度，一层一层抽象过程，简化难度。概括下来方法有以下三点：

  1. Black-box abstraction ——黑盒抽象
  2. Establishing conventional interfaces ——按约定实现接口
  3. making new languages ——定义新的语言

而以上三点，也对应了书中前四章的内容，在控制复杂度的过程中，必然涉及到程序架构的问题，作者也给出了两个方向，operations on aggregates (stream)——聚集操作，和著名的object-oriented——面向对象。也许是因为MIT的CS专业是和EE紧密相连的，各种电气系统的概念总能看到。

OO编程中，各对象通过消息传递进行联系，也联想到OS里的信号量机制(伟大的Dijkstra)，对于流操作，作者又将其类比于大型电气系统，因为我本科也是EE的，对信号与系统，滤波器这些概念听起来还有些怀念。越发佩服这些作者融会贯通的能力。

另外一个收获是对于一种新语言的思考

General framework ——利用通用框架体系组织语言

对于新语言，探究

  1. Primitive Elements ——基本元素
  2. How to put together ——组合元素
  3. Means of abstraction ——如何抽象(黑盒)

而以上的这些，都是之前的书本没有了解到的，站在一个新的角度重新思考了计算机程序