前言

许久未写博客,最近将环境迁移到linux之后在看课程的时候想要记一点笔记,就拾起了Markdown,在尝试了各种的Markdown编辑器都不是很称心之后又想起了自己的博客,就打算着把博客重用起来顺便拿来保存笔记也是个不错的想法,但又想着只用来记笔记有点浪费就想着写一些杂事在上面,正好最近开始了一个Group的讨论,在看完之后又冒出了很多的想法和讨论,就有了这篇杂想.

由一篇博客说起

本文是由对于代码之谜（一）- 有限与无限的讨论所引起的一些想法的记录,在博客中作者提出了一个问题: 负数的绝对值可能等于自己吗? 当然既然作者提出了这个问题,肯定不能轻易的说不或者是了,

我要告诉你方法,而不是答案

在看完之后当然会有一种恍然大悟的感觉,但是所依据的概念和方法又是如此的简单:计算机数的表示,而最小的负数的反码和补码相同这个结论的得出也是自然而然的,但是在没有人提问的情况下,却很难把这二者结合在一起来看.

有限和无限

这篇文章的标题中便提到了这个关键词:有限和无限,作者在文中也抛出了关于在经典数学中的绝对值的定义:

从原点到点A的距离，称为A的绝对值，它是一个非负数

在下面的讨论中,看到了一个能与之对应的关于计算机的绝对值的理解:

其实这整数可以理解成是一个环，取绝对值可以看成把这个环压扁，把其中两面的数都映射到正数的那一面上

很有意思不是吗,我记得在大一的导论课上,我也在书本上看到过类似的图片,一个由数字构成的环,从0开始到8结束又回到了0,当时的图片是为了说明计算机的数字这一个概念,和这个解释如此的一致,我们现在当然可以想当然的说:计算机中的数字是有限的,而数学中的数字是无限的,从而结束这一个讨论,但是为什么从一开始进入计算机的世界的时候,就被人告知,计算机的数字表示是有限的,但是在实际的coding中,我们却自然而然的把计算机的世界和数学世界等同起来.

计算机这个上帝

这个话题是由最近在看的MIT的CS入门课上,教授在讲到关于浮点数的精度的时候提到的,他说:

我们在计算机的世界中创造事物,甚至把计算机(解释器)当成了上帝,想当然的以为他是对的,然后在其之上工作,但是我们不应该仔细想想:为什么他是对的

似乎就像是一场哲学思辨一样,我们似乎也进入了计算机的哲学世界,开始考虑这个上帝,他真的如我们所想一样吗,还是说,我们所想的上帝和真实存在的上帝是不一致的呢?我更倾向于后者,所以这也使我在很多原本自己为的不容置喙的事情上开始了一些思考,我的代码这么写一定是对的吗?为什么是对的呢?我想这就是MIT的教授和这篇博客所要传达给我们的一些理念,仔细想想为什么.在不断的质疑的过程中不断的重塑自己的知识体系和对计算机的认识,似乎就和科学的发展一样,在不断的质疑,提出观点和继续的质疑中才能得到不断的进步.

有限和无限

这当然不是上面的标题的重复(当然也算是),我想来讨论的是计算机所处的有限的世界和数学所代表的无限的世界的不统一之处,当然人类在数学上从有限走向无限也花费了很多的时间,但是计算机作为(可能吧)数学发展比较成熟的时期的产物,却没有获得在抽象层面上的优雅,当然这是因为物理世界的限制,也可能是人类认知上的限制,所以我们似乎也有理由来幻想这样的计算机,像数学一样可以走向无穷和抽象.

(似乎有点扯远)这里讲的有限和无限似乎更像是一种程序员的方法论(或者说计算机观)和现实世界的一种冲突,在讨论中无限和有限也确实有很多可以深究的地方,但是我们确实还做不到用计算机来讨论无穷小,无穷大之类的有很高的抽象层面的东西(我们只能用更高的精度来模拟:exp),所以似乎计算机或是程序员,在用代码也好解释器也好这样有限的东西来对抗物理世界中的无限的数据或者对象,在大数据的今天更甚(似乎在今天已经离不开大数据这个词了,虽然我个人比较抵触,但是这里还是用了一下).我眼前似乎展现了这么一副景象:程序员就如同斯巴达三百勇士一样拿着自己的武器站在温泉关,抵挡着在他们看来无穷的敌人.

无限和有限,似乎是不可调和的一对,但在SICP课程的学习中,却使我在现在有了一些联想:Stream,我们不应该把数据或者对象看成是一块或者是一堆,而应该看成是流,河流,在我们需要的时候,从数据链的一头抽出一个我们需要的数据,另一头就会自动填充:

1
2
3

         -------     -------     --------  
数据---->|  proc|--->|proc  |--->|   proc|---->抽出         
         -------    --------     --------

这似乎是一个很不错的解决方案(看起来).

之所以会写上面的这些文字,是因为在讨论开始的问题的时候,我就发现,无限和有限这一对,不仅会在数字的表示方法这一点上来刁难(或者说折磨)我们,似乎他体现在计算机的方方面面,我们能处理的始终是一个有限的对象,而我们的工具也是有限的,虽然我们无法设想几百年之后的人是怎么编程的,可能就像几千年前的人也无法理解无穷大一样,但是我想的是:在我们使用有限的工具处理有限的问题的时候,我们应该要仔细的思考一下.我们很容易将数学的思维代入计算机,这当然是好的,会帮助我们解决问题,可是似乎也会在某些地方,在那些并不那么和谐统一互相协调的地方,让我们坠入矛盾的深渊.

总结

• 写博客确实是一种锻炼,在行文和构思甚至表达上,总是会感觉词不达意,或者说脑中是思维风暴,但是写出来却是一潭死水,但是练习还是有益处的.
• 就像一开始说的,数学是一条无限延伸的轴,而计算机是一个会头尾相接的环,两者都有其美的地方(现在我很着迷的一点在于fixed point[不动点]).
• 这场讨论和思辨使得我更加审慎的来看待与我相伴的计算机,使我在coding的时候更加多的进行思考.
• 还有一点就是,在看过了足够多的事物之后,发现他们的本质是想通的,CS入门课,SICP,上面提到的文章,这也使得我更深思于计算机的本质:什么是几十年的发展以来没有变的.

呓语到此也完结了.

Lec4.

• Decomposition(分解)
• Abstraction(抽象)

Function

• block up into modules
• suppress detail
• create “new primitive”(原语)

抽象和规格化在模块化和构造函数时的重要性

作用域和值绑定

Interpretes: -> golbal binding
call function-> local table

穷举算法(brute force algorithm)

遍历每一种情况找到答案

Recursion(递归)

-> base case: -simplest possible solution
-> induction step: break problem into a simple version

Lec5 & Lec6.

• 大数
• 浮点数精度
• 浮点数的’==’
• 牛顿法求根号
• 逐次逼近法(guess, check, improve)
• 二分法(Bisection method)
• 回归测试
• 牛顿法和二分法对于求解sqrt问题的复杂度对比: 二分的迭代次数随着x的增加明显增加
• 浮点数的上溢和下溢问题

计算机科学及编程导论 Lec1.

什么是计算思维(computation)

知识：

• 陈述性知识(declarative):描述事实 Ex: 若sqrt(x)=y则y^2=x
• 程序性知识(imperative):对推论过程的描述 Ex:GCD求法

计算机:

fixed-program computer: 固定程序用来做特定的运算

• calculator(计算器)
• Atanasoff(解线性方程组)
• Turing bombe(破译代码-图灵)

stored-program computer: 提供一系列的指令,计算机来执行这些指令(现代计算机模型)

program is a recipe: given a fixed set of primitives -> can program anything

讨论语言的三个维度:

• High vs Low: 离计算机核心有多接近
• General vs targetted: 被设计为通用还是面向目标群体(领域语言)
• interpreted vs compiled: 编译型语言还是解释型语言

Python: High,General,Interpreted

Syntax(语法): 什么是这种语言中的合法表达

Semantics(语义):

• Static: 那些程序是有意义的
• Full:程序有什么意义(运行时意义)

Lec2.

程序运行2种方式:

• Interpret(直接解释)->eval&print

• script(存储脚本)-> no print unless explict

  类型检查:

• weak vs strong typing

  Typediscipline(代码规范)

• A:检查运算符或程序来看他们在不同条件下做的操作是什么

• B:约束参数的类型

  赋值

1 2	x = 3 + 5 y = 15

• 类型
• 类型转换
• 类型绑定(动态绑定)
  建议:Don’t change types arbitrary

Variable used any place it’s legal to required

Statements(声明):

legal commands that Python can Interpret

直线式(顺序)程序:

按照顺序一条条代码执行

分支式(条件)程序:

改变程序执行的顺序通过一些条件Test(一般是变量的值)

Lec3.

流程图

防卫性程序

程序要覆盖所有的可能路径

Tuple: 一系列有序的元素的集合

foo=(1, 2, 3, 4)