Concepts, Techniques, and Models of Computer Programming

一种语言的语义（semantics）说的是程序执行时的所作所为。理想状态下，程序语义应该由一个简单的数学结构定义，通过数学结构我们可以容易地对程序的正确性、执行时间、内存使用状况等等进行推理。这是我们使用核心语言（kernel language）进行教学的原因之一，即使用一种语义相对简单却又实用的语言。

选择核心语言进行教学背后的另一动力是，现代编程语言在经过半个世纪的解决现实世界复杂问题的实践中，其代码规模（百万甚至千万行）以及程序语义的复杂程度早已超乎任何个人想象—我们说一门scale到如此复杂程度的语言是“成功的”因为它成功地对如何建构复杂程序的一些关键方面进行了建模，而这种建模方式不是任意的—因此我们想通过核心语言方法，通过一些简单的建模理解这些“成功的”编程语言背后的原理。

形式化语义（formal semantics）

1. operational semantics 由一台抽象机如何执行一条语句来定义程序语义。由于最终所有程序都必须由计算机执行，这种语义定义方式很实用。

2. axiomatic semantics 定义语义为语句的输入状态（执行语句之前的程序状态）和输出状态（执行语句之后的程序状态）之间的关系。这种关系以逻辑断言的方式给出。

3. denotational semantics 定义一条语句的语义为一个抽象域上的函数。这种定义方式与声明式计算模型较为契合；与并发式语言较为不契合。

4. logical semantics 定义语句的语义为逻辑定理的模型。这种定义方式与声明式和关系式计算模型较为契合。

核心语言使用的是1. operational semantics。

在核心语言方法中，所有的语言建构都会被翻译到核心语言。主要有两种翻译方式：1. 语言抽象（linguistic abstraction）2. 语法糖（syntactic sugar）。

语言抽象。定义一个新的语言抽象分两步走：1. 定义新的语法建构；2. 把它翻译到核心语言。某些语言在语言层面内置了一些常用的语言抽象，例如C的宏，循环体，结构体等等。语言抽象的好处有1. 增加语言的表达性（expressiveness）2. 通过封装实现细节来增强语言的正确性、安全性、执行效率—语法框定了语言抽象的使用方式，编译器可以根据语言抽象的信息来检查程序正确性并生成更高效的代码。

值得一提的是核心语言选择了过程（procedure）而不是函数（function）作为其一部分，其原因部分是过程允许多个输出，更深层的原因将在后面介绍；换言之函数是作为语言抽象加入到核心语言中的—函数定义被翻译成为过程定义，函数调用被翻译成为过程调用。

语法糖。同语言抽象一样，它的定义方式是先定义语法建构然后翻译到核心语言；与语言抽象不同的是，语法糖并不提供新的抽象，它的作用仅仅是精简代码和提高程序可读性。

与核心语言语言方法并列的翻译方法。

1. 基本方法（the foundational approach）将程序语句翻译到数学模型：图灵机，Lambda演算，一阶逻辑，m演算等等。

2. 抽象机方法（the abstract machine approach）将语句翻译到抽象机或虚拟机上，再将它们翻译到真实机器上。

与这两种方法相比，核心语言方法通过谨慎地选择所讨论的概念来避免陷入关于语言机制的大量技术细节。

（与翻译方法并列的）解释器方法：语言的语义由实现一个该语言的解释器来定义。语言L2的解释器是一个由语言L1写成的接受并执行语言L2的程序的程序。该方法被SICP的作者Abelson和Sussman所使用。在SICP中，解释器是元循环（metacircular）的，即L1和L2为同一种语言L，因此添加新的语言特性只需要扩展L的解释器即可。解释器方法的优势在于它展示了一个自包含的语言抽象实现。本书不使用解释器方法的原因在于1. 我们无法从解释器中简单地直接推理程序的执行时间复杂度，以及 2. 在解释器中各种基本概念相互耦合难以理解。

（为了不纠结中文译名，特定术语不再翻译）

Syntax（句法）决定了什么样的程序可以被成功执行。

Grammar（语法）是一套定义了如何由“词”组成“句”的规则的集合。对于编程语言来说，句往往被叫做语句（statement）。词往往被叫做符号（tokens）。规则叫做语法规则（Grammar Rule）一个接受字符串并将它解析为一个符号的序列的程序叫做tokenizer或lexical analyzer。一个接受符号的序列并将它解析为抽象语法树（Abstract Syntax Tree，AST）的程序叫做parser。

Formal Language（形式化语言）。任何一个由良定义的语句组成的集合称作一门形式化语言，简称语言。

Extended Bakus-Naur Form ，EBNF。一种常用的Grammar表示方法，区分了terminal符号和非terminal符号。非terminal符号可以根据一条语法规则展开为若干个terminal符号或非terminal符号。

Context-free Grammar（上下文无关语法）和Context-sensitive Grammar（上下文有关语法）。一条语句的Grammar rule与它在程序中所在的位置无关的Grammar称作Context-free Grammar，反之则为Context-sensitive Grammar，例如许多语言要求变量必须在使用前对它进行定义（define-before-use）。

Syntax = Context-free Grammar + 由语言给定的额外条件的集合（各种上下文相关性）

这种Syntax定义方式利用了Context-free Grammar的locality（局部性）特性，即对于一个non-terminal符号，我们仅需要看它对应的Grammar rule而不需要其它上下文信息就能理解它的意思。

二义性（Ambiguity）。Context-free Grammar是可能产生歧义的。考虑以下语法：

<exp> ::= <int> | <exp> <op> <exp>

<op> ::= + | *

which means 一个表达式可以是一个整数或者由操作符连接的两个表达式，一个操作符可以是加号或者乘号。那么对于以下表达式 2 * 3 + 4 是有歧义的。

读过了前言。前言给出了“计算模型”的定义。 安装了mozart。我的系统是64-bit，没有对应的安装包。解决方法是从 http://www.mozart-oz.org/download/mozart-ftp/store/1.4.0-2008-07-02-tar/mozart-1.4.0.20080704-linux-i486.tar.gz 下载二进制的包，解压，然后把platform目录下的liunx-i486重名为unknown-unknown。这样就可以运行bin/oz来启动基于emacs的oz开发环境了。

difference list有点像用两个指针表示list，一个指向队头，一个指向队尾 不过list是嵌套的结构，所以是一个指向最外层，一个指向最内层 最内层指向的是一个unbound的variable，所以bound这个variable到另一个list就等于连接两个list 比如 1 | 2 | X # X = A # X 3 | 4 | Y # Y = B # Y X是unbound的，如果X = B，也就是X bound到3 | 4 | Y 那么 1 | 2 | 3 | 4 | Y # X = A # X 1 | 2 | 3 | 4 | Y = A A仍然指向最外层，但内层已经链接起来了，最内层的unbound variable是Y 于是A和Y又可以产生另一个difference list A # Y 把difference list当queue用，过程如下 创建队列的时候，两个variable identifier是指向同一个variable的，也就是q(0 X X)，这个X指向的variable是unbound的 从指针的角度看，就是队首队尾指针指向同一个位置 然后是插入，首先创建一个unbound的variable，也就是E1，然后将要插入的值X和它组成一个tuple X | E1 再将这个tuple bound到当前队列里那个unbound的variable，也就是E E = X | E1 也就是原来的 S # E （这个S和E应该就是Start和End的缩写了 成了 S # X | E1 相当于队尾指针指向了一个新的值X 于是E1成了队尾， 所以返回的队列是q(N + 1, S, E1) 出队时，S = X | S1，相当于X指向队首元素，S1作为新的队首，所以返回的队列是 q(N - 1, S1, E)