心智的活动，除了尽力产生各种简单的认知之外，主要表现为如下三个方面：(1)将若干简单认知组合为一个复合的认识，由此产出各种复杂的认知。(2)将两个认知放在一起对照，不管他们如何简单或者复杂，在这样做时，并不能将他们合而为一。由此得到有关他们的相互关系的认知。(3)将有关认识与那些在实际中和它们同在的所有其他认识隔离开，这就是抽象。
所有普遍的认识都是这样得到的。
--John Locke 有关人类理解的随笔，1960
本文为SICP的一些笔记，用于记录一些对计算机程序不同的看法，旨在通过数学计算的思路入门程序设计。SCIP是一本关于计算过程的书，计算过程关心数据的操作，创建程序的目的也是为了数据的处理，表现在代码中便是符号表达式的精心编排，计算过程精密而准确地执行相应程序，初学程序设计的人们就像巫师的徒弟们，学习如何理解和预测咒语的效果，学习并验证结果，不过，学习程序的危险性远远小于巫术。SICP中所有的代码实践为scheme(scheme为Lisp的某个版本，Lisp仍是AI领域中拥有理论上最高演算能力的语言)，执行过程为解释器的代码交互过程，依据同样的解释器运行程序原理，也可以用python实现书上的练习题。
程序设计的基本元素
每一种编程语言都有三种机制：
- 基本的表达形式
- 组合的方法
- 抽象的方法
基本表达式为程序语言所关心的最简单的个体，而组合的方法即组合这些简单的个体成为复杂的元素。再将复杂的元素进行抽象，便可得到一个单元，单元也可以作为一个简单的个体继续组合，层层递进便组成了完整的程序，这也是为什么许多书中一定会提到递归。
在程序中，有两类基本要素：过程和数据，数据为用户希望操作的“东西”，而过程就是有关操作这些规则的描述，任何强有力程序设计语言必须表述基本的数据和基本过程，还需提供对过程和数据进行组合和抽象的方法。
表达式
最简单的程序入门，观看代码与解释器交互，假设键盘输入了一个表达式，解释器将表达式的求值结果显示出来，最基本的表达式就是数，例如，给一个数486:
mt@mt-P243:~$ python
Python 2.7.17 (default)
[GCC 7.5.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 486
486
将表示数的表达式组合起来，形成复合表达式
Python 2.7.17 (default)
[GCC 7.5.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 1000-7
993
>>> 993-7
986
>>> (3*((2*4)+(3+5)))+((10-7)+6)
57
对于复杂的算术式，解释其也按照基本循环进行操作，读入-求值-打印
命名和环境
通过给数据命名，通过使用名字进行运算，将名称标识符称为变量，将数据存到变量中。解决好命名问题，程序就完成一大半，最基本的表达式为变量赋值,此时数据到变量的过程也是一种抽象：
>>> size = 2
>>> size
2
组合
评估组合的过程有两步：
- 评估子过程
- 将表达式的值应用到新的过程
例如：
>>> (3*((2*4)+(3+5)))
可用树结构
root["3*((2*4)+(3+5))"]--> LT["3"]
root["3*((2*4)+(3+5))"]--> RT["((2*4)+(3+5))"]
RT["((2*4)+(3+5))"]-->RTL["(2*4)"]
RT["((2*4)+(3+5))"]-->RTR["(3+5)"]
RTL["(2*4)"] -->RTLL["2"]
RTL["(2*4)"] -->RTLR["4"]
RTR["(3+5)"] -->RTRL["3"]
RTR["(3+5)"] -->RTRR["5"]
过程的组合
- 数字和算术运算是原始数据和过程。
- 组合嵌套提供了一种组合操作的方法。
- 将名称与值相关联的定义提供了有限的限制抽象手段
a = (3*((2*4)+(3+5)))+((10-7)+6)
实例：采用牛顿法求平方根
\]
计算步骤：
| 步骤1 | 猜测 | 商 | 平均值 |
|---|---|---|---|
| (1) | 1 | 2/1=2 | (2+1)/2=1.5 |
| (2) | 1.5 | 2/1.5 = 1.333 | (1.333+1.5)/2=1.4165 |
| (3) | 1.4165 | 2/1.4165 = 1.412 | (1.4165+1.412)/2=1.41425 |
| (4) | 1.41425 | 2/1.41425 = 1.4142 | (1.41425+1.4142)/2=1.414225 |
如果不限制条件，计算将一直进行下去，所以为了设计程序来计算平方根考虑计算步骤
1)先猜值
2)计算商
3)计算平均值作为下一轮的猜值
如果不加停止条件，那么将会一直计算下去，观察计算结果可以发现猜测值、商还有平均值越来越接近，如果约定一个误差范围，就可作为计算的停止条件(good_enough)。
1)猜值的终止条件
def square(x):
return x*x
def good_enough(guess,x):
if abs(square(guess)-square(x))<0.001:
return True
else:
return False
2)和3)计算平均，作为下一轮猜值的起始，如果结果很好，立即结束，否则继续猜，迭代过程可写为
def improve_guess(guess,x):
return (x/guess + guess)/2
def sqrt_iter(guess,x):
print(guess,x)
if good_enough(guess,improve_guess(guess,x)):
print('guess:'+str(guess))
return guess
else:
return sqrt_iter(improve_guess(guess,x),x)
程序可写为
def sqrt(x):
return sqrt_iter(1.0,x)
程序分解[原问题到子问题的分解]：
root["sqrt"]--> Node["sqrt_iter"]
Node["sqrt_iter"]-->LT["good_enough"]
Node["sqrt_iter"]-->RT["improve"]
RT["improve"] --> improve_guess
LT["good_enough"] --> square
LT["good_enough"] --> abs
「使用许多基本的算术操作，对操作进行组合，通过定义各种复合过程，然后对复合过程进行抽象」
线性迭代和递归
考虑阶乘
\]
与牛顿法求平方根一样的思路，为了计算第n次迭代，需要考虑n-1次的结果，阶乘可写为
\]
那么就知道两种情况的编码思路：
- 第1次 n为1
2)第n次 到 (n-1) 的迭代
def factorial1(n):
if n==1:
return 1
else:
return n* factorial(n-1)
用另一种观点看待问题，1*2然后将结果 *3，再次 *4，直到 n，那么利用一个计数器counter 即可写成如下迭代：
counter \leftarrow counter + 1
\]
def fact_iter(product, counter, max_count):
if counter>max_count:
return product
else:
return fact_iter(counter*product, counter+1, max_count)
def factorial2(n):
return fact_iter(1,1,n)
factorial1采用了先展开后计算的思路，而factorial2采用了先计算后展开的思路，factorial1称为递归计算过程(表达式越写越长)，而factorial2计算过程中表达式未发生改变，factorial2多了一个变量用于保存中间的结果，这种迭代过程有时也和计算理论中提到的状态变量类似，计算过程即状态转换的过程，同时还有一个(可能有)的停机过程。
最大公约数
两个整数的最大公约数(GCD)定义为能除尽这两个数的最大整数，算法基于以下观察：如果r是a除以b的余数，那么a和b的公约数正好是b和r的公约数：
\]
此时，一个GCD的计算问题连续地归约到越来越小的整数对，例如
=GCD(40,6)\\
=GCD(6,4)\\
=GCD(4,2)\\
=GCD(2,0)\\
=2
\]
def remainder(a,b):
return a%b
def gcd(a,b):
if b==0:
return a
else:
return gcd(b, remainder(a,b))
用高阶函数做抽象
上述的过程也就是一类抽象，描述了一些对于数的符合操作，但是同时又不依赖于特定的数--将数作为参数传入函数。人们对功能强大的程序设计语言有一个必然要求，就是能为公共模式命名，建立抽象，而后直接在抽象的层次上工作。
过程作为参数，
(1)计算从a到b的各个整数之和：
def sum_integers(a,b):
if a > b:
return 0
else:
return a + sum_integers(a+1,b)
(2)计算从a到b的各个整数立方和：
def sum_cubes(a,b):
if a > b:
return 0
else:
return cube(a) + sum_cubes(a+1,b)
(3)计算下面的序列之和：
\]
def pi_sum(a,b):
if a > b:
return 0
else:
return 1/(a*(a+2)) + pi_sum(a+4,b)
明显看出，三个过程共享着一种公共的基础模式：从a算出需要加的项的函数，还有用于提供下一个a值的函数，可以通过一个模板描述
def sum_term(term, a, next, b):
if a>b:
return 0
else:
return term(a)+sum_term(term, next(a), next, b)
而计算立方和时，term(a)为cube(a),next(a)为下一项，根据这个过程，可以改写上述(1)~(3)的例子
def inc(n):
return n+1
def cube(a):
return a*a*a
def sum_cubes(a,b):
return sum_term(cube,a,inc,b)
有了上面这个模板sum_term，将其作为基本单元，可以形式化其他概念，例如在a和b之间计算定积分的近似值
\]
其中dx是一个很小的值，可以将公式转化为
def integral(f, a, b, dx):
def add_dx(x):
return x + dx
return sum_term(f, a+dx/2, add_dx, b)*dx
用lambda构造过程
在原先写的pi_sum函数式，返回了“其输入值加4的过程”和“其输入值加2的乘积倒数的过程”，这个过程可以使用辅助函数，也可以使用lambda表达式，python中的labmda表达式格式为 lambda <表达式的返回值>: 表达式
lambda x:x+4
lambda x: 1/(x*(x+4))
为了实现和原来pi_sum的过程，可以使用lambda表达式和模板sum_term实现一样的功能
def pi_sum(a,b):
return sum_term(lambda x: 1.0 / (x * (x + 2)),a,
lambda x: x+4,b)
寻找函数的不动点
函数调用函数的过程，类似于数学上定义的复合函数的概念，如果f(x)=x无限套娃，可以找到一个不动点：
\]
例如黄金分割率就是下面函数的不动点
\]
利用程序计算过程如下：
tolerance = 0.00001
def fixed_point(f, first_guess):
def close_enough(v1,v2):
return True if abs(v1-v2)<tolerance else False
def try_guess(guess):
next_guess = f(guess)
if close_enough(next_guess,guess):
return next_guess
else:
return try_guess(next_guess)
return try_guess(first_guess)
print(fixed_point(lambda x:1+1/x, 1))