SICP公开课翻译小记(一)

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

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

——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演算.

SmithSeo 说:
2021年4月21日 06:44

Pretty nice post. I just stumbled upon your weblog and wanted to say that I have really enjoyed browsing your blog posts. After all I’ll be subscribing to your feed and I hope you write again soon! like

smithseo 说:
2021年4月28日 21:58

Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. บาคาร่า SA

John 111 说:
2021年5月18日 23:10

I was surfing the Internet for information and came across your blog. I am impressed by the information you have on this blog. It shows how well you understand this subject. 안전놀이터

John 111 说:
2021年5月31日 00:54 Wow i can say that this is another great article as expected of this blog.Bookmarked this site.. https://www.smore.com/9afn3-testogen-review-omg-this-is-crazy
jackjohnny 说:
2021年6月02日 16:46

I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article... indian business visa

johnyking 说:
2021年6月16日 19:02

Thanks for another wonderful post. Where else could anybody get that type of info in such an ideal way of writing? 토토사이트

John 111 说:
2021年6月17日 12:24

Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed, but also entertained! earthhershop

jackjohnny 说:
2021年6月17日 23:08

This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article. 토토사이트

John 111 说:
2021年6月21日 13:59 Excellent article. Very interesting to read. I really love to read such a nice article. Thanks! keep rocking. nextclippingpath
nordic giant 说:
2021年6月25日 18:45

This is helpful, nonetheless it can be crucial so that you can check out the following website:

John 111 说:
2021年6月25日 19:51

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. 먹튀검증

jackjohnny 说:
2021年6月26日 22:04

Wow i can say that this is another great article as expected of this blog.Bookmarked this site.. 안전놀이터

jackjohnny 说:
2021年6月27日 17:17

I haven’t any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. Smm

jackjohnny 说:
2021年6月28日 16:33

Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. voyance-telephone-gaia.com

jackjohnny 说:
2021年6月29日 18:48

I have read all the comments and suggestions posted by the visitors for this article are very fine,We will wait for your next article so only.Thanks! indisk visum

jackjohnny 说:
2021年7月05日 19:22

I think that thanks for the valuable information and insights you have so provided here. สล็อต

jackjohnny 说:
2021年7月11日 20:20

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much. 토토사이트

johnyking 说:
2021年7月15日 23:19

I think this is a really good article. You make this information interesting and engaging. You give readers a lot to think about and I appreciate that kind of writing. scarlett johansson measurement

Rafay 说:
2021年8月09日 04:28

Web host bahrain
<a href="https://www.propassion.net">web host bahrain</a>

johnyking 说:
2021年8月21日 19:38

I am continually amazed by the amount of information available on this subject. What you presented was well researched and well worded in order to get your stand on this across to all your readers. 메이저사이트

johnyking 说:
2021年8月22日 19:45

I felt very happy while reading this site. This was really very informative site for me. I really liked it. This was really a cordial post. Thanks a lot!. สล็อตโจ๊กเกอร์

johnyking 说:
2021年8月23日 16:30

I know this is one of the most meaningful information for me. And I'm animated reading your article. But should remark on some general things, the website style is perfect; the articles are great. Thanks for the ton of tangible and attainable help. ufabet1688

officeseo 说:
2021年8月26日 16:06

Superb blog post, I have bookmarked this internet site so ideally, I’ll see much more on this subject in the foreseeable future! <a href="https://www.silvertechsolutions.net/blogs/">5 Benefits Of Using SEO</a>

johnyking 说:
2021年8月29日 17:23

New web site is looking good. Thanks for the great effort. uk student visa from bangladesh 2022

johnyking 说:
2021年8月29日 23:39

Most of the time I don't make comments on websites, but I'd like to say that this article really forced me to do so. Really nice post! Search Engine List

johnyking 说:
2021年9月12日 18:09

A very awesome blog post. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. Sexy baccarat

johnyking 说:
2021年9月16日 01:45

Great Information sharing .. I am very happy to read this article .. thanks for giving us go through info.Fantastic nice. I appreciate this post. Anitube

johnyking 说:
2021年9月16日 18:18

I appreciate everything you have added to my knowledge base.Admiring the time and effort you put into your blog and detailed information you offer.Thanks. สมัครเล่นเกมบาคาร่าด้ว

johnyking 说:
2021年9月20日 23:12

Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too. There tend to be not many people who can certainly write not so simple posts that artistically. Continue the nice writing merchant services representative


登录 *


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