Learning Notes of Concepts, Techniques and Models of Programming Language

2016-08-07
TPL
   

声明

本译作只为个人英语练习之作,并未在任何平台发布。本网站乃是个人笔记汇编,不得以任何形式传播。

本译作保留了大量英语原词,这是学习编程语言所应该掌握的词汇。翻译为中文反而晦涩难懂。

翻译原则

  1. 若某英文专有词汇对应的中文翻译,没有较好的凭直觉获知的意义,则仅仅给出中文翻译,在正文中保留英文用法。

计算机程序设计的概念,技术和模型

作者:Peter Van Roy, Seif Haridi

第一章 程序设计概念简介

1.1 计算器

Mozart OZ中函数用大括号包括。Browse函数打开一个显示其参数求值结果的窗口。

{Browse 9999*9999}

1.2 变量

定义变量:

declare
V=9999*9999

{Browse V*V} % 显示V*V的值

一个变量涉及两个概念:标识符(V),其储存的值(99980001)。

1.3 函数

定义函数:

% N的阶乘
declare
fun {Fact N}
    if N==0 then 1 else N*{Fact N-1} end
end

函数支持在其定义中调用自己,即Recursion(递归)。用已有的函数可以更方便地定义新的函数。将操作、事件或实体用函数表达并命名,以方便后续调用,称为函数抽象。

1.4 列表

列表定n义和操作:

% 列表
L=[5 6 7 8]

% 空列表(不是[])
nil

% 列表链接符(H是新元素,T是列表的后续部分)
H|T

% 访问列表的第一个元素或者剩余部分
L.1 % 5,元素
L.2 % [6 7 8],列表

模式识别

TODO:

1.5 列表相关的函数

TODO:

1.6 正确性

TODO:

1.7 复杂度

TODO:

1.8 惰性求值

TODO:

1.9 高阶编程

TODO:

1.10 并发性

TODO:

1.11 数据流

TODO:

1.12 显性状态

TODO:

1.13 对象

TODO:

1.14 类

TODO:

1.15 不确定性和时间

TODO:

1.16 原子性

TODO:

1.17 下一步是什么?

TODO:

1.18 练习

TODO:

第二章

TODO:

2.1 定义实用的编程语言

编程语言比自然语言简单,但是仍旧可能由极其丰富的语法、一系列抽象和库构成。特别是用于解决现实问题的语言(Practical Languages)。实用语言就像熟练的工人的工具箱,有很多为不同目的而设计的工具。

本节解释了如何表达实用语言的Syntax(语法)和Semantics(语义),这是本书其余部分的基础。在此基础上引入了本书第一个模型:声明式计算模型。这些内容也用于定义本书介绍的其他模型。

2.1.1 语言的语法

语言的语法决定了何为“合法程序”(可以成功运行的程序)。本节不关心程序究竟做了什么——那由Semantics决定(2.1.2节)。

语法

语法是用“词”构成“句子”的一系列规则。自然语言(如英语,瑞典语)和人造语言都有语法。对于编程语言来说,“句子”通常是“statement“,“词”通常是“token”。词由字母促成,token由character组成。这是两层结构:

statement = token的序列
token = character的序列

编程语言的语法定义了statement和token。图2.1是输入character被转化为statement的例子。这个例子定义了Fact函数:

fun {Fact N}
    if N==0 then 1
    else N*{Fact N-1} end
end

输入是character的序列,其中” “代表空格,”\n“代表换行。它先被转化为token的序列,再被转化为parse tree。图中的syntax序列与本书中的list syntax兼容。序列是“扁平的”,而parse tree现实了statement的结构。Tokenizer(或称lexical analyzer)接受character序列,并返回token序列。

2.1.2 语言的语义

形式语义

语言的创造者可由任意方法定义核心语言的语义。语言语义有四种常用方法:

  • 操作语义(Operational Semantics): 表示statement根据抽象机器运行的方式。这种方法总是有效,因为所有语言最终都运行在计算机上。
  • 公理语义(Axiomatic Semantics):将statement定义为输入状态和输出状态的关系。(输入状态是在statement运行之前的状态,输出状态是statement输入之后的状态)。这种关系是逻辑断言(Logical Assertion)的形式。这可以用于分析statement序列:因为一个satement的输出断言,是下一个statement的输入断言。这对stateful模型也同样有效,因为state是值的序列。(见6.6节)
  • 指称语义(Denotational Semantics):将statement定义为一个抽象值域上的函数。这对declarative model尤其有效。(2.8.1节和4.9.2节解释了与指称语义非常近似的函数式编程。)
  • 逻辑语义(Logicial Semantics):将statement定义为逻辑理论的模型。这对declarative和relational computation model尤其有效,但是很难应用于其他模型。(见9.3节)

本书基于操作语义,给出了每一个语言结构的非形式语义。

语言内抽象

语言内抽象(linguistic abstraction)是实用语言中,为了增强语言表达力而设置的结构。定义Linguisitic Abstraction时,先约定其语法结构,再将其翻译为核心语言。一些常用的Linguisitic Abstraction如:function,loop,lazy function,class,reentrant lock。

有的语言提供了自定义Linguisitic Abstraction的工具,如Lisp Macro。Lisp Macro是生成代码的函数。(由于Lisp语法简单,所以Lisp Macro尤为成功。详见[72,200])

例如:在procedure之上的function。制作function时,需要指明定义function的方法,function call和向procedure定义、procedure call转译的方法。翻译的方式需要考虑到所有内容,比如嵌套函数{F1 {F2 X} {F3 Y}}中,F2和F3的执行顺序。有些语言不对其进行定义,而是假设在调用F1时,所有参数已经被求值;有些语言在用到参数时才对其进行求值。简洁如嵌套函数,也没有一个明显的语义——这在定义语义时,由转译的方式决定。

为什么要用Linguisitic Abstraction?它们可以以复杂度为代价,提高语言的正确性,安全性和效率。如果将Linguisitic Abstraction的实现与程序员隔离,编译器可以运行错误的代码,然后给出更多有用的信息。

语法糖 TODO:

语言设计 linguisitic abstraction是语言设计的基础工具。

一个abstraction在其life cycle中由三个阶段:a.定义它时,没有语言内的支持,也就是说,语言没有设计使它可以使用的语法;b.若某一情况下,语言设计者推测它极其基础且实用,就可以给它语言内的支持——此时,它成为了linguistic abstraction——这是一个探索阶段,此linguisitc abstraction并无法确保可以成为语言的一部分;c.如果这个linguistic abstraction非常成功,它简化了语言,对编程者来说非常有用,就变成了语言的一部分。

其他转译实现

核心语言实现(kernel language approach)是semantics的translation approach的一个例子,基于一种语言向另外一种语言的转译。图2.5展示了translation approach用于定义编程语言的三种方式:

TODO: figure 2.5

TODO: mermaid is not supported correctly.

graph TD;
A{Prgramming language} |转译| -->  B[Kernel Language] |Aid the|;
A -->  C[语言的基础演算];
A -->  D[Abstract machine];
  • 贯穿本书的核心语言实现是为给编程者所用的,其中的概念与编程中的概念一一对应。
  • 基础实现是为数学家所用的。例如:图灵机,λ-calculus(lambda演算,函数式编程的基础),first-order logic(一阶逻辑,逻辑式编程的基础)和π calculus(pi演算,用于建模并发)。因为这些形式系统是用于形式化数学研究的,它们拥有尽可能少的构成元素。
  • Abstract machine是为语言的实现者所用的。程序被翻译成一个理想化的机器,被称为abstract machine或者virtual machine(虚拟机)。

2.2 单次赋值存储

2.3 核心语言

2.4 核心语言的语义

2.5 内存管理

2.6 从核心语言到使用语言

2.7 异常

2.8 高阶话题

2.9 练习

第三章 声明式程序设计的技术

3.1 什么是可声明性

3.2 迭代计算

3.3 递归计算

3.4 递归程序设计

3.5 时间和空间的高效性

3.6 高阶编程

3.7 抽象数据类型

3.8 Nondeclarative needs~

3.9 Program design in the small

3.10 练习

第四章 声明式并发

4.1 数据驱动的并发模型

4.2 线程编程技术基础

4.3 流

4.4 直接使用声明式并发模型

4.5 惰性运行

4.6 软实时编程

4.7 Haskell语言

4.8 声明式编程的限制和扩展

4.9 高级话题

4.10 历史性记录

4.11 练习

第五章 消息传递并发

5.1 消息传递并发模型

5.2 端口对象

5.3 简单消息协议

5.4 并发程序设计

5.5 升降控制系统

5.6 直接使用消息传递模型

5.7 Erlang编程语言

5.8 高级话题

5.9 练习

第六章 显式状态

6.1 什么是显式状态

6.2 状态和系统搭建

6.3 应用~显式状态的并发模型

6.4 数据抽象

6.5 Stateful Collection~

6.6 reasoning with state

6.7 宏观程序设计

6.8 案例学习

6.9 高级话题

6.10 练习

第七章 面向对象程序设计

7.1 继承

7.2 用作完全数据抽象的类

7.3 用作增量式数据抽象的类

7.4 用继承编程

7.5 和其他计算模型的关系

7.6 实现一个类型系统

7.7 Java编程语言

7.8 Active对象~

7.9 练习

第八章 共享状态并发

8.1 共享状态并发模型

8.2 并发编程

8.3 锁

8.4 监视器

8.5 事件

8.6 Java编程语言(并发部分)

8.7 练习

第九章 关系式编程

9.1 关系式计算模型

9.2 更多的例子

9.3 和逻辑编程的关系

9.4 自然语言句法分析

9.5 一个语法解释器

9.6 数据库

9.7 Prolog编程语言

9.8 练习

第十章 图形化用户界面编程

10.1 声明式/过程式实现

10.2 使用声明式/过程式实现

10.3 原型设计师交互学习工具

10.4 案例学习

10.5 实现GUI工具

10.6 练习

第十一章 分布式编程

11.1 分布式系统的分类

11.2 分布式模型

11.3 声明式数据的分布

11.4 状态的分布

11.5 网络awareness

11.6 一般的分布式编程模式

11.7 分布式协议

11.8 局部故障

11.9 安全性

11.10 构建应用

11.11 练习

第十二章 约束式编程

12.1 传播和搜索

12.2 编程技巧

12.3 基于约束的计算模型

12.4 定义和使用计算空间

12.5 实现关系式计算模型

12.6 练习

第十三章 语言的语义

13.1 一般的计算模型

13.2 声明式的一致性?并发性?

13.3 八个计算模型

13.4 一般抽象的语义

13.5 历史性讲义

13.6 练习

A Mozart系统开发环境

A.1 交互式界面

A.2 命令行界面

B 基本数据类型

B.1 Nunmber(Integer,Float,夯实基础

python编程从入门到精通,从单纯的语法理解到灵活应用解决实际问题,掌握Linux和Windows双系统开发环境,掌握常见数据结构和算法(时间复杂度计算,排序,搜索,栈,队列,二叉树),建立面向对象思维,能对问题进行抽象归类,了解设计模式,掌握单例模式和工厂Character)

B.2 Literal(atom和name)

B.3 Record和Tuple

B.4 Chunks(限制大小的Record)

B.5 List

B.6 String

B.7 Virtual String

C 语言的语法

C.1 交互式程序指令

C.2 程序指令和表达式

C.3 指令和表达式的非终止

C.4 操作符

C.5 关键字

C.6 构词句法

D 通用计算模型

D.1 有创造力的扩展规则

D.2 核心语言

D.3 概念

D.4 状态的不同形式

D.5 其他概念

D.6 层次化语言设计

引用

目录

简短目录

前言

运行示例程序

1. 程序设计简介

I 泛用计算模型

2. 声明式计算模型
3. 声明式程序设计技术
4. 声明式程序设计的并发性
5. 消息传递的并发性
6. 显式状态
7. 面向对象编程
8. 共享状态并发性
9. 关系型程序设计

II 特用计算模型

10. 图形用户界面程序设计
11. 分布式程序设计
12. 约束式程序设计

III 语义

13. 程序语言的语义

IV 附录

A. Mozart 系统开发环境

B. 基础数据类型

C. 程序语言的语法

D. 泛用计算模型

引用

索引

## 内容列表

**前言**

**运行示例程序**

第一章 程序设计概念简介

1.1 计算器
1.2 变量
1.3 函数
1.4 列表
1.5 列表相关的函数
1.6 正确性
1.7 复杂度
1.8 惰性求值
1.9 高阶编程
1.10 并发性
1.11 数据流
1.12 显性状态
1.13 对象
1.14 类
1.15 不确定性和时间
1.16 原子性
1.17 下一步是什么?
1.18 练习

第一部分 泛用计算模型

第二章 声明式计算模型

2.1 定义实用的程序设计语言
2.2 单次赋值存储
2.3 核心语言
2.4 核心语言的语义
2.5 内存管理
2.6 从核心语言到使用语言
2.7 异常
2.8 高阶话题
2.9 练习

第三章 声明式程序设计的技术

3.1 什么是可声明性
3.2 迭代计算
3.3 递归计算
3.4 递归程序设计
3.5 时间和空间的高效性
3.6 高阶编程
3.7 抽象数据类型
3.8 Nondeclarative needs~
3.9 Program design in the small
3.10 练习

第四章 声明式并发
4.1 数据驱动的并发模型
4.2 线程编程技术基础
4.3 流
4.4 直接使用声明式并发模型
4.5 惰性运行
4.6 软实时编程
4.7 Haskell语言
4.8 声明式编程的限制和扩展
4.9 高级话题
4.10 历史性记录
4.11 练习

第五章 消息传递并发
5.1 消息传递并发模型
5.2 端口对象
5.3 简单消息协议
5.4 并发程序设计
5.5 升降控制系统
5.6 直接使用消息传递模型
5.7 Erlang编程语言
5.8 高级话题
5.9 练习

第六章 显式状态
6.1 什么是显式状态
6.2 状态和系统搭建
6.3 应用~显式状态的并发模型
6.4 数据抽象
6.5 Stateful Collection~
6.6 reasoning with state
6.7 宏观程序设计
6.8 案例学习
6.9 高级话题
6.10 练习

第七章 面向对象程序设计
7.1 继承
7.2 用作完全数据抽象的类
7.3 用作增量式数据抽象的类
7.4 用继承编程
7.5 和其他计算模型的关系
7.6 实现一个类型系统
7.7 Java编程语言
7.8 Active对象~
7.9 练习

第八章 共享状态并发 
8.1 共享状态并发模型
8.2 并发编程
8.3 锁
8.4 监视器
8.5 事件
8.6 Java编程语言(并发部分)
8.7 练习

第九章 关系式编程
9.1 关系式计算模
9.2 更多的例子
9.3 和逻辑编程的关系
9.4 自然语言句法分析
9.5 一个语法解释器
9.6 数据库
9.7 Prolog编程语言
9.8 练习

第二部分 特用计算模型

第十章 图形化用户界面编程
10.1 声明式/过程式实现
10.2 使用声明式/过程式实现
10.3 原型设计师交互学习工具
10.4 案例学习
10.5 实现GUI工具
10.6 练习

第十一章 分布式编程
11.1 分布式系统的分类
11.2 分布式模型
11.3 声明式数据的分布
11.4 状态的分布
11.5 网络awareness
11.6 一般的分布式编程模式
11.7 分布式协议
11.8 局部故障
11.9 安全性
11.10 构建应用
11.11 练习

第十二章 约束式编程
12.1 传播和搜索
12.2 编程技巧
12.3 基于约束的计算模型
12.4 定义和使用计算空间
12.5 实现关系式计算模型
12.6 练习

第三部分 语义

第十三章 语言的语义
13.1 一般的计算模型
13.2 声明式的一致性?并发性?
13.3 八个计算模型
13.4 一般抽象的语义
13.5 历史性讲义
13.6 练习

第四部分 附录

A Mozart系统开发环境
A.1 交互式界面
A.2 命令行界面

B 基本数据类型
B.1 Nunmber(Integer,Float,Character)
B.2 Literal(atom和name)
B.3 Record和Tuple
B.4 Chunks(限制大小的Record)
B.5 List
B.6 String
B.7 Virtual String

C 语言的语法
C.1 交互式程序指令
C.2 程序指令和表达式
C.3 指令和表达式的非终止
C.4 操作符
C.5 关键字
C.6 构词句法

D 通用计算模型
D.1 有创造力的扩展规则
D.2 核心语言
D.3 概念
D.4 状态的不同形式
D.5 其他概念
D.6 层次化语言设计

引用

目录

Comments

CONTENT