SICP公开课翻译小记(一)

DeathKing posted @ 2013年2月10日 11:47 in Scheme with tags lisp mit Scheme SICP 计算机程序的结构和解释 , 3086 阅读

如果说艺术解释了我们的梦想,那么计算机就是以程序的名义执行着它们。

——Alan J.Perlis,《计算机程序的结构和解释》之序

计算机程序的构造和解释,Lec1a

 

计算机科学究竟是什么?

  国内计算机专业有个统一的名字,“计算机科学与技术”。我对此充满疑问,我相信很多人也和我有同样的疑问:

  • 计算机为什么科学?
  • 技术体现在了哪里?

  我天真的以为我找到了答案,刚上大一时,我是这么认为的:

  • 就如数学、物理一样,计算机有它自己的一套完备的系统——一套研究问题的形式化方法;
  • 我们有各种各样的技术,比如各种算法、各种语言以及各种架构;

  然而,Abelson教授却给了我当头一棒,他说:“于此来说,计算机科学是个很糟糕的名字。首先,它不是一门科学。它或许是一门工程或者一种艺术。……正如它不是一门科学,它和计算机也没有太多的关系。”其次,在《计算机程序的结构和解释》中,这一席话也使我深受启发:

我们所设计的这门计算机科学导引课程反映了两方面的主要考虑。首先,我们希望建立起一种看法:一个计算机语言并不仅仅是让计算机去执行操作的一种方式,更重要的,它是一种表述有关方法学的思想的新颖的形式化媒介。因此,程序必须写得能够供人们阅读,偶尔地去供计算机执行。其次,我们相信,在这一层次的课程里,最基本的材料并不是特定程序设计语言的语法,不是有效计算某种功能的巧妙算法,也不是算法的数学分析或者计算本质基础,而是一些能够用于控制大型软件系统的智力复杂性的技术。

——Harold AbelsonGerald Jay Sussman,《计算机程序的结构和解释》之第一版前言

  从这点来说,计算机科学更像是一门工程。在工程中,我们有工程学的技术,比如在构建大型项目时控制复杂度的技术。而我们所使用的工具——程序设计语言,并不仅仅是为了实现我们的愿望。重要的是,表达计算的思想,关于通用计算的思想。如果能够表达这种思想,那么任何语言都是没有区别的,以及,任何计算机也是没有区别的(图灵等价)。因此,计算机科学也关于计算的思想。计算机科学也讨论抽象的方法,从具象的问题到抽象的问题,从5的平方到任意数的平方;从两个正整数相加,到任意事物相加,它都是研究事物的普遍规律。然而,如果再越过软件和硬件的鸿沟,你会发现,我们还需要考虑如何去实现一个计算“机”,这个才是计算机科学关乎“计算机”,而前面都是“计算”。于是,我重新补充了一下我所认知到的计算机科学与技术:

  • 计算(数学)
    • 算法
    • 通用计算思想
    • 用于表达计算的语言
  • 机(物理)
    • 电路与布尔代数
    • 物理元件
    • 低级控制指令
  • 科学(元数学)
    • 形式化的方法
    • 公理化的方法
  • 技术(工程学)
    • 组合的技术
    • 抽象的技术
    • 控制复杂度的技术
    • 设计结构的技术
    • 设计系统的思想与技术

 

“计算”与“机”

按照我的理解,我们可以对中文“计算机”这个词语做一次咬文嚼字的分拆,Lisp代表着“计算”,而C语言则代表“机”。

——Lox关于编程语言学习的一些思考

  如果让我们仔细回味一下C语言的代码,这个抽象层仅仅比汇编语言高的程序设计语言,它代码的本质意义:

#include <stdio.h>

int main()
{
  int a = 5;
  char str[] = "C is about computER!\n";
  struct student {
    long id;
    char name[5];
  } john = { 56234, "John" };

  printf("The value of symbol a is: %d.\n", a);
  printf("%s", str);
  printf("John's id is %ld.\n", john.id);
  return 0;
}

  所有的这些代码,反映的都是对硬件的操作,虽然它有一层包装,但很薄,你可以轻易的戳破。首先,声明变量以及初始化,这开辟一段内存空间,并为这些内存的电位进行了合理的修改,使得它能够代表我们是所指定的数据。就连如字符数组和结构体,都是为了说明我应该如何去划分这些内存区域。函数调用呢?它也只是CPU、内存的一系列操作而已,还是用到了栈结构。我们不难发现,C语言仅仅是对硬件操作的一层简单包装而已。我们如果用它来表达一些计算思想,可能会遇到一点麻烦。C语言并不支持“高阶函数”——之所以这样说,并不是C语言不能实现高阶函数,而是高阶函数并不是C的设计思想,因为“函数”在C语言中是所谓的“二等公民”:函数没办法作为一个参数直接传递,而是通过指针。我可以很轻易的写出下面的代码:

(define (g f x)
  (+ (f (+ x 1))
     (f (- x 1))))

(display (g (lambda (x) (* x x)) 5 ))
; 6^6 + 4^4 => 52

  当然,我们也可以写出“等效”的C语言代码:

#include <stdio.h>

int f(int x)
{
	return x * x;
}

int g(int (*func)(int), int x)
{
	return (*func)(x + 1) + (*func)(x - 1);
}

int main()
{
	printf("%d\n", g(f, 5));
	return 0;
}

我们来分析一下两种语言的思考方式。在Scheme中,我们认为函数是第一公民,所以我们可以把它当作参数传递,这没问题。但是在C语言中,函数是一段程序代码,它不是一个对象,函数名则是函数的地址,因此我们只能通过指针——通过传递地址的方式来解决。C语言这么做第一是出于效率的考虑,第二是因为计算机的结构本来就是这样。

 

程序是什么:陈述性知识和指令性知识

  在数学中,我们经常可以看到这样的定义:

\[ \boxed{定义(绝对值) 一个数的绝对值即是数轴上该点到原点的距离。} \]

  这个定义只告诉了你绝对值“是什么”,而没有告诉你“如何去求”绝对值。这种对事物做出陈述性描述的知识就是所谓的陈述性知识。而“指令性知识”或者说“过程性知识”则会告诉你如何去做:

\[ \boxed{定义(绝对值) 若x \ge 0则其绝对值为x;否则为-x。} \]

  我们想要表达这种关于“怎么做(How-to”的想法,而程序就是表达这个想法的工具。

前缀记法,S-表达式

  在数学中,我们有各种各样的符号和千奇百怪的记法,来表示运算或者关系。比如:

  • 有运算符在数据之前的记法,如\(\sin x\)和\( \arctan { \frac { \pi  }{ 2 }  }  \) ;
  • 有运算符在数据中间的记法,如\(a+b\)和\(p\rightarrow q\);
  • 有运算符在数据后面的记法,如\(n!\)和\(x^2\);
  • 有运算符在数据两边的记法,如\(\left| x \right| \)和\(\left\lceil x \right\rceil \);
  • 有运算符在数据周围的记法,如\(\sqrt [ n ]{ x }\);
  • 等等……

  我们用一种记法就可以了,因为:

  • 每一种运算符都代表一种关系,我们可以给这个关系取一个名字;
  • 无论何种记法,都是将运算符表示的运算用于运算对象,因此,只要我的记法能表达这个意图,就与原记法等效;
  • 前缀记法可以很容易扩充运算对象的个数,而其它记法似乎会有点困难;

  在Lisp中,这种记法形式与(operator operand1 operand2 ...),它代表将运算应用于各个运算对象。于是,他们说:

  • 我们可以用(+ a b)来表示a+b,这样,+是运算符,ab是运算对象;
  • 我们可以用(\(\left|  \right|\) \(x\))来表示\(\left| x \right| \),这样,\(\left|  \right|\) 这个符号代表取绝对值运算,\(x\)代表运算对象;
  • 我们可以用(abs x)来表示\(\left| x \right|\),这样使得我们可以在没有\(\left| \right|\)符号的机器上表示绝对值;
  • 我们可以用(rel s e t)来代表一个叫做rel的运算,set分别是它的运算对象;
  • 等等……

  于是,Lisp的世界就变得清爽了许多。SchemerLisper更喜欢称之为S-表达式S代表“符号的”)。这是抽象语法树(Abstract Syntax Tree)通常采用的结构,Lisp这样做,就可以省去词法分析的步骤了。

 

抽象与命名

; 为一个具例命名
(define A (* 5 5))

; 为一个思想命名
(define (square x) (* x x))
(square 5)

  为一个具例命名,和为一个思想命名,哪一个更好呢?显然,你定义A为5乘以5,是一个“用自己乘以自己”的一般性思想的具体实例。然而,你若要表述6的平方、7的平方、9999的平方、10000000000的平方呢?你还会写这样的代码么:

(define B (* 6 6))
(define C (* 7 7))
(define D (* 9999 9999))
(define E (* 10000000000 10000000000))
; ......

  实例是无穷的,思想却是唯一的。我们发现,如果我们定义好了这个思想,那么想要表达某个特殊的实例就非常容易了。这也是程序设计语言中“函数”的重要意义。

  那么,所谓抽象Abstraction)和命名Name/Define)是什么意思呢?抽象,可以通俗的认为是“从特殊到一般的过程”,亦即,“提取事物的共有规律”。

\[1!=1\\ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5\\ 100!=1\cdot 2\cdot \cdots 99\cdot 100\\ \vdots \\ x!=1\cdot 2\cdot \cdots (x-1)\cdot x\]

  我们通过大量的具体实例发现,“任何‘正整数\(x\)的叹号’,就是从\(1\)乘到\(x\)的积。”这就是一个抽象,它表达的是具有一般性、普遍性的想法。而所谓命名,就是给这种想法一个名字,方便我们表达这个想法。实际上,我们已经将这个想法描述为:“一个正整数的叹号。”如果我们给它一个书面一点的术语的话,那就是大家熟悉的“阶乘(factorial)”。因此,这个命名就像下面这样:

\(\boxed{一个正整数x的阶乘}\) 为 \(\boxed{将[1,x]的所有正整数乘起来}\)

↑名字                           ↑思想

黑箱抽象

  

 

Avatar_small
FTS 说:
2013年2月10日 13:13

计算模型的区别.
C语言是自动机,Lisp是Lambda演算.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter