Sep 7

本Blog已停止更新

(其实也没怎么更新)

请移步至:deathking.github.io

Nov 6

最近在学习《数据结构与算法分析》,由于老师是用C语言授课,而C语言实现各种数据结构和算法早就已经被写烂了。恰巧在学习Scheme,就试下如何用Scheme来实现这些数据结构和算法。

一个优雅的实现

下面的这段代码是坦佩雷理工大学的Juha Heinanen教授或者是Pertti Kellom教授编写的,看到下面的代码,我基本上没有再实现一次的欲望了。这个博文,就姑且来剖析一下这段代码是如何实现栈的。

;;;;
;;;; A stack implementation.
;;;;

(define (make-stack) 
  (define stack '()) 
  (define (empty?) (null? stack)) 

  (define (top) 
    (if (null? stack) 
        (error "Stack is empty -- TOP"
               stack) 
        (car stack))) 

  (define (push! object) 
    (set! stack (cons object stack)) 
    object) 

  (define (pop!) 
    (if (null? stack) 
        (error "Stack underflow -- POP!"
               stack) 
        (let ((object (car stack))) 
          (set! stack (cdr stack)) 
          object))) 

  (define (dispatch op . args) 
    (case op 
      ((empty?) (apply empty? args)) 
      ((top) (apply top args)) 
      ((push!) (apply push! args)) 
      ((pop!) (apply pop! args)) 
      (else 
        (error "Unknown stack operation --"
          " DISPATCH" op)))) 
  dispatch) 

栈内容

(define stack '()) 

栈内容是一个状态量。在这个实现中,变量stack代表了栈内容。最初,栈为空,故stack与空表`()进行了绑定。

谓词:栈是否为空

(define (empty?) (null? stack)) 

简单判断stack是否为空表即可。

元素入栈

(define (push! object) 
  (set! stack (cons object stack)) 
  object)

注意这个操作需要改变状态量,也就是因为引入了赋值而带来了副作用。函数push!会将新入栈元素和原栈堆给cons起来,并让新入栈的元素作为car部分,这是为了方便后面的出栈操作。

元素入栈操作push!返回新入栈的元素。

元素弹出

(define (pop!) 
  (if (null? stack) 
      (error "Stack underflow -- POP!"
              stack) 
      (let ((object (car stack))) 
         (set! stack (cdr stack)) 
         object))) 

显然空表无法弹出。为了弹出栈顶元素,首先先让一个局部变量obejectstackcar部分绑定(注意到stackcar部分就是栈顶元素),然后再将stack赋值为原stackcdr部分,再返回局部变量object,这就实现了元素的弹出。

返回栈顶元素

(define (top) 
  (if (null? stack) 
      (error "Stack is empty -- TOP"
             stack) 
      (car stack))) 

注意到栈顶元素就是stackcar部分,实现top过程就非常容易了。这个过程甚至不涉及到任何状态操作。

消息分派(实现面向对象机制)

(define (dispatch op . args) 
  (case op 
    ((empty?) (apply empty? args)) 
    ((top) (apply top args)) 
    ((push!) (apply push! args)) 
    ((pop!) (apply pop! args)) 
    (else 
      (error "Unknown stack operation --"
             " DISPATCH" op))))

这个stack实现最妙的部分就在此处。dispatch函数实现了一个简单但是有效的面向对象编程机制,对堆栈的操作实质上是对这个dispatch发送了一个“消息”,dispatch中得case来判断执行什么操作。

由于Scheme的闭包性,它的状态量(OO中的成员变量)和操作函数(OO中的方法)都封装在一个黑盒子中(其实一个lambda就是一个context),非常美妙。

Apr 18

从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,故事是说:“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,故事是说:‘从前有座山,……’”

——传说

要理解递归,你先要理解递归。

——你需要理解递归

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

 

递归,我们到底知道多少?

  暂且搁置一下,过几天来填坑。

递归产生迭代的计算

尾递归

 

Feb 10

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

——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]的所有正整数乘起来}\)

↑名字                           ↑思想

黑箱抽象

  

 

Feb 4

于此来说,计算机科学是个很糟糕的名字。

首先,它不是一门科学。它或许是一门工程或者一种艺术。但我们会发现计算机被叫做所谓的科学 ,是因为它有很多与魔法一致的地方。这些将在本课中体现 。

——Harold Abelson

 

缘起

  记得那是在高一信息技术课上,我从老师的口中听到了两个来自于上古的名字:PrologLisp。而在高二与朋友的闲聊中,又听闻到了Scheme——这个由MIT主导开发的Lisp方言,以及Scheme界的“The Bibble”——魔法书Structure and Interpretation of Computer Programs

Structure and Interpretation of Computer Program

《计算机程序的结构与解释》

  《算法导论》《编译原理》C程序设计语言》甚至《计算机程序设计艺术》毫无疑问都是计算机学界的瑰宝,然而这本《计算机程序的构造和解释》,却凭借与其自身的独特魅力,或者说魔力,在这个群魔乱舞的神坛里面独树一帜。我们也很想跟随SICP,跟随两位作者,去不一样的世界冒险,去追寻那神秘的魔法之力。偶然的机会,我得知SICP有公开课视频,这是两位作者Harold AbelsonGerald Jay Sussman19867月给Hewlett-Packard公司员工培训时所录制的视频。于是,怀着对SICP以及两位作者的崇高敬意,我和@ChingfanTson师兄开始了这段艰难的漫长翻译路。

 

视频、字幕和SICP中译版

Harold Abelson

  首先要再次说明,SICP公开课的系列视频录制于1986年,并作为HP公司的内部资料。而HP公司为响应Harold Abelson教授的MIT OCW建设,也于惠普影视部后制处理之后大方地公开。由于当时的录制条件所限,分辨率只有320X240,并且画质也非常糟糕。这对我们的字幕制作带来了很大的影响,我们也尝试着将分辨率提高到640X480(否则小分辨率显示字幕非常糟糕),并使用一些商业软件略微修补画质,但效果不太理想。

  而就字幕来说,我和@ChingfanTson之前都没有做过类似的工作,因此这次也是硬着头皮来完成这个系列的翻译。以前看电影时从没考虑过字幕组会付出多少心血,如今亲身实践,才发现此中不易!一节课的视频只有一个小时,但完成划句、翻译、审校、做时间轴花了我们不下30个小时的功夫,期间的种种酸甜苦辣,也只有我们才知道。个别句子,甚至要花上好些时间理解,有时还得热烈讨论一番才能得出结果。有些句子,为了使翻译符合中文习惯,不得不苦心孤诣,再三斟酌。还有的句子,在参考了资料后,又不得不改了又改。而最后的结果也难以令人满意。除了已经把这个项目托管到了GitHub,我还希望能有时间再细细的磨下,把措辞再变得准确一点、优雅一点。

Gerald Jay Sussman

  SICP的中译版,也就是《计算机程序的结构和解释》,是由北京大学的裘宗燕教授翻译的,虽然网路上有一部分人不太认可他的翻译,但我觉得,这个译本是非常棒的(尤其是序言的翻译,非常精彩)。在翻译SICP公开课的时候,很多地方也采用了他的译法。另外,出于统一的考虑,公开课出现的术语都朝裘书中的译法靠拢,比如:

  • Operator,操作符→运算符;
  • Operand,操作数→运算对象;

  出于忠于上下文的考虑,仔细理解后,Lec1a中有一处我们保留了我们的译法:

  • Conventional Interfaces,约定的接口,约定的界面(裘书)

  还有的术语出于跟上时代的考虑,翻译成了当下的叫法,比如:

  • Black Box,黑箱→黑盒
  • Syntactic Sugar,语法糖衣→语法糖;

  还有的词,再与裘宗燕教授交流一番后,我们终于从几种不同的译法中择出了最优:

  • Imperative Knowledge,行动性知识→指令性知识;

  虽然我们的翻译不能确保100%的准确,而且能够用中文表达作者的神韵,但我们的确是用心在做这件事。

 

Lisp\Scheme

C Lisp 一个就像红外线,一个就像紫外线,它们分布在光谱的最两端。它俩一个牛逼的地方刚好是另一个傻逼了的地方。

—— Steve Yegge ,Tour De Babel

  我承认,正因为之前有一点其它程序设计语言的基础,接触到PrologLisp的时候着实给吓傻了。一个不需要“for”语句,不需要“do-while”语句的语言,你这是想说Edsger W. Dijkstra提出的计算机程序的结构“顺序、分支、循环”中的“循环”是多余的么?Lisp告诉你,对,我们不需要它。我们可以用迭代或者递归来完成(SICP中会告诉你递归和迭代在某种程度上是一致的)。于是在SICP书中你就可以看到用递归完成的求平方根法。

  Lisp\Scheme之美,在于它能够模糊数据与代码的边界。代码和数据,在Lisp的世界中,就如道家的阴和阳,相互对立又相互转化,十分和谐。这是什么意思呢?我们假设在代码中,我们有一个叫a的变量,如果我们只是简单的使用它,那么编译器/解释器就会对其求值,以Ruby作喻:

a = 5
a #=> 5

  然而,我们如果想表示,叫a的这个变量的名字,也就是“a”这个符号,那么我可以用“符号”这个东西

a = 5
:a #=> :a

  Ruby只是从Lisp那里继承了一点东西,所以才会看起来更Lisp有异曲同工之妙,Lisp\Scheme通过一个单引号就将代码变成了数据:

(define atom?   
  (lambda (x)  
    (and (not (pair? x)) (not (null? x)))))  

(atom? (atom? 'a))    ; #t
(atom? '(atom? 'a))   ; #f

  由于Lisp写出下面的代码也不奇怪,运算符也可以作为返回值——因为它们都是复合过程——这是Lisp/Scheme神奇的组合以及抽象手段:

(define my-opr
    (lambda (x)
        ((cond ((> x 0) *)
                (else +)) x x)))

(my-opr 3)  ; 9
(my-opr -3) ; -6

  就此打住,Lisp\Scheme的奥秘还请各位自行在这个魔法世界里探索。

彩蛋

  公开课中播放的音乐是Johann S. BachJesus, Joy of Man's Desiring

  Harold Abelson教授是左撇子

视频

  正在后期制作,估计年三十那天应该能正式看到吧,算是送给各位虔诚的\(\lambda\)教信徒的新年贺礼吧!