程序原本(五十三):程序设计的核心思想——执行体与它在执行过程中的环境(没有更多的技巧——排序,然后顺序执行)

阅读数:32 2019 年 10 月 1 日 16:07

程序原本(五十三):程序设计的核心思想——执行体与它在执行过程中的环境(没有更多的技巧——排序,然后顺序执行)

所谓翻译(编译与解释)无非是将一系列的源代码文本(所对应的计算行为)排列成一个顺序序列,而最终的执行器——无论是机器还是解释器——只是从这个顺序序列的起始位置开始处理,一直到结束9。正是因为这个缘故,所以依据什么排序才会是翻译中的一个关键问题。

9 这种结束有两种可能,其一是序列完全计算完毕,我们通常理解为“退出”;其二是序列进入一个无休止的循环过程,我们通常理解为“等待—就绪”。对于执行器来说,这个顺序的代码序列(静态文本的翻译结果)所代表的执行逻辑(动态的处理)既可能是操作系统所调度的 CPU 执行权限的入口,也可能是一个解释器的执行片段的起始——不幸的是两种情况都被称为 process,只是前者通常译为进程,后者则译为处理。

语法树是对语法元素进行排序的一个方案。这一方案将语法元素解析为不同类型的树结点,例如操作符结点、操作数结点等。以下面的代码为例:

复制代码
a, i = 100, v = i + 100;

它可能被解析成如图 15 所示的语法树10

10 本例是 JavaScript 解释器引擎的一个实际解析结果。需要留意的是:不同的语言以及其翻译器在解析细节上可能会有不同,因而可能产生别的结果。

图 15 语法树:对语法元素进行的排序

程序原本(五十三):程序设计的核心思想——执行体与它在执行过程中的环境(没有更多的技巧——排序,然后顺序执行)

在该语法树中,所有叶子结点都是标识或直接的值——它们代表数据,而非叶子结点则是操作,亦即逻辑;如果是逻辑,则计算的结果可以作为其他计算所需的数据,例如图中的结点 8 的计算结果是结点 4 操作数。

当如上的语法树形成之后,顺序扫描树中所有结点的方法有两个:深度优先遍历与广度优先遍历——理论上说存在无数种可能的方法,这取决于形成该树时所使用的算法。以使用深度优先遍历算法为例,我们将得到下面这样一个处理顺序:

复制代码
2,5,6,3,7,9,10,8,4,1

去除掉标识和数据部分,我们看到的是:

复制代码
_,_,_,3,_,_,__,8,4,1

这几个操作的顺序,即我们对“顺序计算(逻辑)”在语法树上的重现。

那么,以数据排序又会是怎样的一种情形呢?例如,下面的代码:

复制代码
i := 100;
y := "hi";
x := 5;
i := x*2 + i;

可以产生一个类似的语法树,如图 16 所示。

图 16 生成的语法树(为分析“基于数据的排序”而进行了排版变化)

程序原本(五十三):程序设计的核心思想——执行体与它在执行过程中的环境(没有更多的技巧——排序,然后顺序执行)

(除了版式上的不同)这个图与此前的图并没有本质的区别,我们仍然可以按上述遍历规则得到一个执行顺序——如果你将这个图理解为基于运算的排序的话。但是,我们这里要讨论的是基于数据的排序,即:运算影响到哪些数据,以及其影响先后的问题。基于此前的讨论,我们可以将“数据”理解为运算所需的参考——上下文环境,然后

  • 将图 6 中树的每一个运算放到它所需的上下文环境中,并
  • 将这些环境用框图及其层次表达出来11

11 内层的环境是外层的环境的一个参考,或称之为历史环境的一个映像。

如图 17 所示。12

12 其一,图中的 1~4 为代码行号。其二,为方便绘制,图中省去了直接值结点,只留下表示数据依赖关系的标识。

图 17 基于数据的排序:将“数据”理解为运算所需的参考

程序原本(五十三):程序设计的核心思想——执行体与它在执行过程中的环境(没有更多的技巧——排序,然后顺序执行)

可见,本质上来说,我们要正确处理此前的代码文本,则意味着我们将对上下文环境的相关性进行排序:内层是被依赖的,因此排序优先级更高;同层不存在数据 / 上下文环境依赖,因此优先级相等(例如 1 与 3,以及 2 与 4)13

13 注意由于优先级相等表明了不存在同层相互间的依赖,也就意味着同层的代码文本是可以并行执行的;当以类似闭包(scope)这样的方式来解析代码并表达它们的层次关系时,是原生支持并行语言的。

比较两种方案:以数据为顺序时,标识符的作用域(亦即是上下文环境)问题将会绑定在语法树上;而以逻辑为顺序时,作用域问题与语法树是无关的。

评论

发布