SICP公开课翻译小记(一)

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

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

——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

johnyking 说:
2021年10月04日 04:12

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. write for us

johnyking 说:
2021年10月06日 23:00

Thanks for a wonderful share. Your article has proved your hard work and experience you have got in this field. Brilliant .i love it reading. selling payment processing services

johnyking 说:
2021年10月17日 23:22

This particular papers fabulous, and My spouse and i enjoy each of the perform that you have placed into this. I’m sure that you will be making a really useful place. I has been additionally pleased. Good perform! vaporizer

Manipur Board 12th Q 说:
2021年10月20日 16:03

The Council of Higher Secondary Education, Manipur (COHSEM) is in charge of the annual examination for the Higher Secondary School Leaving Certificate (HSSLC). Wednesday, March 20, 2022 is the start date. Manipur Board 12th Question Paper 2022 Manipur Council, the +2 courses in the state were conducted by the Board of Secondary Education, Manipur as Higher Secondary School Leaving Certificate course in the Higher Secondary Schools and Pre-University course by the Manipur University in the College., End of Exam 20 April 2022, Manipur Council, the +2 courses in the state were conducted by the Board of Secondary Education, Manipur as Higher Secondary School Leaving Certificate course in the Higher Secondary Schools and Pre-University course by the Manipur University in the

johnyking 说:
2021年12月30日 14:20 Excellent and very exciting site. Love to watch. Keep Rocking. 메이저사이트
johnyking 说:
2022年3月29日 03:30

Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post. Gamik

SEO 说:
2022年3月30日 23:49

<p>
This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. <a href="https://www.pawsandfurs.com/can-dogs-eat-watermelons/">can dogs eat watermelon rind</a></p>

SEO 说:
2022年3月30日 23:56

I think that thanks for the valuabe information and insights you have so provided here. Golden Revive Plus Reviews

johnyking 说:
2022年4月04日 00:27

Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too. make google photos default on iphone

jackseo 说:
2022年4月06日 07:09

Pretty good post. I have just stumbled upon your blog and enjoyed reading your blog posts very much. I am looking for new posts to get more precious info. Big thanks for the useful info. Rudn Enclave

jackseo 说:
2022年4月07日 18:51

Great post but I was wondering if you could write a little more on this subject? I’d be very thankful if you could elaborate a little bit further. Thanks in advance! detectives Málaga

jackseo 说:
2022年4月08日 18:04

Thanks for the blog filled with so many information. Stopping by your blog helped me to get what I was looking for. Now my task has become as easy as ABC. golden revive plus review

jackseo 说:
2022年4月11日 09:24

I can’t believe focusing long enough to research; much less write this kind of article. You’ve outdone yourself with this material without a doubt. It is one of the greatest contents. kingdom valley islamabad latest news

jackseo 说:
2022年4月12日 17:52

Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. kingdom valley islamabad payment plan

jackseo 说:
2022年4月17日 18:29

This is a smart blog. I mean it. You have so much knowledge about this issue, and so much passion. You also know how to make people rally behind it, obviously from the responses. สมัครสล็อต

jackseo 说:
2022年4月20日 09:26

This content is written very well. Your use of formatting when making your points makes your observations very clear and easy to understand. Thank you. https://seedandspark.com/user/mega-blue

johny 说:
2022年4月26日 06:22

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. smilz cbd gummies supplement

Assam 11th Syllabus 说:
2022年5月07日 19:40

Assam HS Syllabus 2023 will be released in the final week of May 2023 by the Assam Higher Secondary Education Council. On this website, you may get the AHSEC 11th Syllabus 2023 Arts/Commerce/Science. Download the Assam Board 11th Class Syllabus 2023 from the AHSEC. Assam 11th Syllabus 2023 Those exceptional applicants who excelled in the Assam HS Exam 2023 should feel relieved now that they have received this timely information. As we all know, everyone who took the AHSEC 11th Examination is looking for the Assam HS Final Syllabus 2023.

narrowsecurity 说:
2022年6月26日 02:17

I have learned huge knowledge from here. I am waiting for your updates
Regards: <a href="https://narrowsecurity.com/">fire guard services nyc</a>

uaecarpet 说:
2022年8月06日 16:36

<a href='https://uaecarpet.com/dubai-carpet-cleaning-services/' title='carpet shop in deira dubai' target='_blank'>carpet shop in deira dubai</a>
<a href='https://uaecarpet.com/carpet-shops-and-stores-in-dubai-and-uae/' title='dubai carpet market' target='_blank'>dubai carpet market</a>

johny 说:
2022年9月14日 20:18

Awesome dispatch! I am indeed getting apt to over this info, is truly neighborly my buddy. Likewise fantastic blog here among many of the costly info you acquire. Reserve up the beneficial process you are doing here. Organische zoekmachine optimalisatie specialist in Veenendaal

AP 10th Science Mode 说:
2022年9月19日 00:24

AP 10th Class Science Model Paper 2023 Pdf Download may useful to both Telugu Medium, English Medium and Urdu Medium 10th class students of the state board to score better marks in the exams like SA-1, SA-2, FA-1, FA-2, FA-3, FA-4. AP 10th Science Model PaperThese practice model papers not only helped in getting marks but also improve the student’s knowledge of science.AP 10th Science Model Paper 2023 Pdf with answers suggested for all kinds of exams held under BSEAP along with assignments were made with the instructions of Leading educational institutes, Education portals of the state such as Sakshi Education, Eenadu Pratibha.

johny 说:
2022年9月20日 22:51

I am always searching online for storys that can accommodate me. There is obviously a multiple to understand about this. I feel you made few salubrious points in Attributes moreover. Detain busy, awesome career! Sparkassen

johny 说:
2022年9月22日 02:27

Welcome to the party of my life here you will learn everything about me. جيست بوست

johny 说:
2022年9月22日 21:19

Hmm… I interpret blogs on a analogous issue, however i never visited your blog. I added it to populars also i’ll be your faithful primer. سوق السيارات

johny 说:
2022年9月22日 21:42

So lot to occur over your amazing blog. Your blog procures me a fantastic transaction of enjoyable.. Salubrious lot beside the scene. حلى كيتو

johny 说:
2022年9月22日 22:15

I prefer merely excellent resources - you will see these people in: ابر التنحيف

johny 说:
2022年9月28日 03:07

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me. 英文補習邊個好

johny 说:
2022年9月28日 21:42

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. free diamonds in mobile legends legit

johny 说:
2022年9月29日 15:08

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! baccarat99th

Johny 说:
2022年9月30日 00:49

You there, this is really good post here. Thanks for taking the time to post such valuable information. Quality content is what always gets the visitors coming. poke ricetta

johny 说:
2022年9月30日 20:07

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! InventHelp George Foreman Commercials

johny 说:
2022年10月01日 01:31

Wow! Such an amazing and helpful post this is. I really really love it. It's so good and so awesome. I am just amazed. I hope that you continue to do your work like this in the future also Short-let Abuja


登录 *


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