心智的活动,除了尽力产生各种简单的认知之外,主要表现为如下三个方面:(1)将若干简单认知组合为一个复合的认识,由此产出各种复杂的认知。(2)将两个认知放在一起对照,不管他们如何简单或者复杂,在这样做时,并不能将他们合而为一。由此得到有关他们的相互关系的认知。(3)将有关认识与那些在实际中和它们同在的所有其他认识隔离开,这就是抽象。

所有普遍的认识都是这样得到的。

--John Locke 有关人类理解的随笔,1960

本文为SICP的一些笔记,用于记录一些对计算机程序不同的看法,旨在通过数学计算的思路入门程序设计。SCIP是一本关于计算过程的书,计算过程关心数据的操作,创建程序的目的也是为了数据的处理,表现在代码中便是符号表达式的精心编排,计算过程精密而准确地执行相应程序,初学程序设计的人们就像巫师的徒弟们,学习如何理解和预测咒语的效果,学习并验证结果,不过,学习程序的危险性远远小于巫术。SICP中所有的代码实践为scheme(scheme为Lisp的某个版本,Lisp仍是AI领域中拥有理论上最高演算能力的语言),执行过程为解释器的代码交互过程,依据同样的解释器运行程序原理,也可以用python实现书上的练习题。

程序设计的基本元素

每一种编程语言都有三种机制:

  1. 基本的表达形式
  2. 组合的方法
  3. 抽象的方法

基本表达式为程序语言所关心的最简单的个体,而组合的方法即组合这些简单的个体成为复杂的元素。再将复杂的元素进行抽象,便可得到一个单元,单元也可以作为一个简单的个体继续组合,层层递进便组成了完整的程序,这也是为什么许多书中一定会提到递归

在程序中,有两类基本要素:过程和数据,数据为用户希望操作的“东西”,而过程就是有关操作这些规则的描述,任何强有力程序设计语言必须表述基本的数据和基本过程,还需提供对过程和数据进行组合和抽象的方法。

表达式

最简单的程序入门,观看代码与解释器交互,假设键盘输入了一个表达式,解释器将表达式的求值结果显示出来,最基本的表达式就是数,例如,给一个数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
组合

评估组合的过程有两步:

  1. 评估子过程
  2. 将表达式的值应用到新的过程

    例如:
>>> (3*((2*4)+(3+5)))

可用树结构

graph TD
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"]

过程的组合

  1. 数字和算术运算是原始数据和过程。
  2. 组合嵌套提供了一种组合操作的方法。
  3. 将名称与值相关联的定义提供了有限的限制抽象手段
a = (3*((2*4)+(3+5)))+((10-7)+6)

实例:采用牛顿法求平方根

\[\sqrt 2 \approx 1.414
\]

计算步骤:

步骤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)

程序分解[原问题到子问题的分解]:

graph TD
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·(n-1)·(n-2)···3·2·1
\]

与牛顿法求平方根一样的思路,为了计算第n次迭代,需要考虑n-1次的结果,阶乘可写为

\[n!=n·(n-1)!
\]

那么就知道两种情况的编码思路:

  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 即可写成如下迭代:

\[product \leftarrow counter \times product \\
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(a,b)=GCD(b,r)
\]

此时,一个GCD的计算问题连续地归约到越来越小的整数对,例如

\[GCD(206,40)\\
=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)计算下面的序列之和:

\[\frac{1}{1·3}+\frac{1}{5·7}+\frac{1}{9·11}+···\approx \frac{\pi}{8}
\]
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之间计算定积分的近似值

\[\int_{a}^{b}f dx=[f(a+\frac{dx}{2})+f(a+dx+\frac{dx}{2})+f(a+2dx+\frac{dx}{2})+···]dx
\]

其中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无限套娃,可以找到一个不动点:

\[f(x),f(f(x)),f(f(f(x))),...
\]

例如黄金分割率就是下面函数的不动点

\[f(x)=1+\frac{1}{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))

SCIP:构造过程抽象--面向对象的解释的更多相关文章

  1. SICP— 第一章 构造过程抽象

    SICP  Structure And Interpretation Of Computer Programs 中文第2版 分两部分  S 和 I 第一章 构造过程抽象 1,程序设计的基本元素 2,过 ...

  2. 从普通函数到对象方法 ------Windows窗口过程的面向对象封装

    原文地址:http://blog.csdn.net/linzhengqun/article/details/1451088 从普通函数到对象方法 ------Windows窗口过程的面向对象封装 开始 ...

  3. python 面向过程和面向对象比较

    面向过程 VS 面向对象 面向过程的程序设计:核心是过程二字,过程指的是解决问题的步骤,即先干什么再干什么......面向过程的设计就好比精心设计好一条流水线,是一种机械式的思维方式. 优点是:复杂度 ...

  4. 面向过程 vs 面向对象

    从网上摘录了一些面向过程vs.面向对象的分析,先简单记录如下,稍后会继续整理. 为什么会出现面向对象分析方法? 因为现实世界太复杂多变,面向过程的分析方法无法实现. 面向过程 采用面向过程必须了解整个 ...

  5. C++ 构造过程和析构过程

    1.C++构造和析构的过程,类似于穿衣脱衣的过程.穿衣是:先穿内衣,再穿外套.脱衣是:先脱外套,再脱内衣.C++构造过程:首先调用父类构造方法,再调用子类构造方法.C++析构过程:首先调用子类析构方法 ...

  6. 从C++对象内存布局和构造过程来具体分析C++中的封装、继承、多态

    一.封装模型的内存布局 常见类对象的成员可能包含以下元素: 内建类型.指针.引用.组合对象.虚函数. 另一个角度的分类: 数据成员:静态.非静态 成员函数:静态.非静态.虚函数 1.仅包含内建类型的场 ...

  7. JS是面向过程、面向对象还是基于对象?面向对象的代码体现

    一.问题 javascript是面向对象的,还是面向过程的?基于对象是什么意思? 对象: 指的是对某一类事物进行抽象,抽象出这一类事物共同的特征以及行为(也就是属性和方法),那些拥有这一共同属性和方法 ...

  8. C++笔记005:用面向过程和面向对象方法求解圆形面积

    原创笔记,转载请注明出处! 点击[关注],关注也是一种美德~ 结束了第一个hello world程序后,我们来用面向过程和面向对象两个方法来求解圆的面积这个问题,以能够更清晰的体会面向对象和面向过程. ...

  9. essential C++中关于面向过程和面向对象的说明

    昨天在阅读essential C++中看到了一个关于面向过程和面向对象的区别的例子,感觉挺好的.记录下来.... 这个例子是关于照相机的.照相机有三个性质,一个是控制位置:通常使用3个浮点数据来表示其 ...

  10. swift 笔记 (十四) —— 构造过程

    构造过程 为了生成类.结构体.枚举等的实例,而做的准备过程,叫做构造过程. 为了这个过程,我们一般会定义一个方法来完毕,这种方法叫做构造器.当然它的逆过程,叫做析构器,用于在实例被释放前做一些清理工作 ...

随机推荐

  1. [slim] Slim - Faster, lightweight, a enginer for Ruby

    URL: http://slim-lang.com/ Example: doctype html html head title Slim Examples meta name="keywo ...

  2. php 判断是否 是手机访问

    //判断是否属手机 function is_mobile() { $user_agent = $_SERVER['HTTP_USER_AGENT']; $mobile_agents = Array(& ...

  3. 【BZOJ】【3530】【SDOI2014】数数

    AC自动机/数位DP orz zyf 好题啊= =同时加深了我对AC自动机(这个应该可以叫Trie图了吧……出边补全!)和数位DP的理解……不过不能自己写出来还真是弱…… /************* ...

  4. 为什么要进行URL编码

    我们都知道Http协议中参数的传输是"key=value"这种简直对形式的,如果要传多个参数就需要用“&”符号对键值对进行分割.如"?name1=value1&a ...

  5. RandomAccessFile&amp;IO流&amp;排序&amp;方法论

    RandomAccessFile&IO流&排序&方法论 我们总觉得历史是极其遥远的东西,与我们并无关联,又觉得历史隐藏在图书馆的旧书之中. 然而,我们每个人都有真真切切的历史. ...

  6. 三级菜单python写法(递归写法)

    数据结构: menu = { '北京':{ '海淀':{ '五道口':{ 'soho':{}, '网易':{}, 'google':{} }, '中关村':{ '爱奇艺':{}, '汽车之家':{}, ...

  7. [我的理解]Javascript的原型与原型链

    一.原型与原型链的定义 原型:为其他对象提供共享属性的对象 注:当构造器创建一个对象,为了解决对象的属性引用,该对象会隐式引用构造器的"prototype"属性.程序通过const ...

  8. 【BZOJ5416】【NOI2018】冒泡排序(动态规划)

    [BZOJ5416][NOI2018]冒泡排序(动态规划) 题面 BZOJ 洛谷 UOJ 题解 考场推出了就是两个上升子序列,并且最长下降子序列长度不超过\(2\)...然后大力暴力状压\(dp\)混 ...

  9. IDEA创建SpringBoot项目

    创建SpringBoot有三种方式: 方式一:(常用方式)

  10. 【BZOJ4477】[JSOI2015]字符串树(Trie树)

    [BZOJ4477][JSOI2015]字符串树(Trie树) 题面 BZOJ 题解 对于每个点维护其到根节点的所有字符串构成的\(Trie\),显然可持久化一下就很好写了. 然后每次询问就是\(u+ ...