【苏联计算机往事】R-技术

译自 R-Techonology。除非特殊声明，下文中「我」指原文作者 Oleg Kiselyov。

「R-技术（R-Technology）」是一种设计和图形化表示程序的方法，由 V.M. Glushkov 领导的基辅控制论研究所开发。该技术是自 20 世纪 50 年代末及 60 年代初，苏联弹道导弹和后来的太空火箭的航空电子软件设计中发展起来的。（有趣的是，大约二十年后，David Harel 在担任以色列飞机工业公司航空电子软件工程顾问时，发明了一种相当类似的技术－－Harel 状态图。）Glushkov 研究所大量使用并推广 R-技术：据说他们在该领域发表了 600 多篇论文（大部份是俄语的），就这一主题举办了三次全联盟会议和一次国际会议。它们甚至把 R-技术标准化了－－R-chart，ISO/IEC 8631。

20 世纪 80 年代初，我从控制论研究所研究人员出版的几本书和发表的几篇文章中了解到了 R-技术。Glushkov 研究所出版的所有东西都给人一种和 R-技术有关的印象。我还记得当时看到了画在一张大纸上的完整 Pascal 编译器的图表（R-图表）。

R-技术基于一种描绘程序控制流的图表。节点是程序的状态，有向边（弧）代表状态转换。弧的上下方都有文字或图形的注释，上方代表转移条件/守卫（guard），下方则描述了该弧将要执行的动作（action），弧是水平的线条。当程序处于特定状态时，我们从上到下查找对应转移条件为真的弧，并执行弧表示的操作，然后把程序状态更新为弧的目标节点。R-技术与流程图密切相关，不过流程图中的一个节点在 R-技术图表中是一条带有注释的弧（在 Harel 的状态图中也是如此）。我们称 R-技术图表为 R-图表，它所描述的抽象机器/自动机则称为 R-机器或者 R-tran（RTRAN）。

上面对 R-机器的描述可能会令人联想到状态机。这种相似性并非偶然：Glushkov 是著名的自动机理论研究者，他第一个提出了把正则表达式转化为非确定性有限自动机的算法，还撰写了《Synthesis of Digital Automata》（该著作为他带来了列宁奖和苏联科学院院士资格）。与有限状态自动机不同的是，R-机器转换状态的条件可以不只是对输入的测试，可以是任意复杂的。稍后可以看到一个例子：那 R-机器名义上只有两个状态，但它还有可变状态，其动作会更新可变状态，因此实际状态的数量是无限制的。在我看来，R-机器看起来总是像图灵机，但 R-机器「控制」实际事物，其动作不仅是读写和移动磁带。

通常把 R-技术图表绘制成图像，因此也称该技术为可视化编程技术。不过，用（风格化的）纯文本表示图表也是可行的。我记得在某本书中看到表示 R-程序的表格，看起来有点像 FORTRAN 或 COBOL 程序输入到打孔机上打孔的样子。表格有四列，分别是当前状态标签、转移条件、动作和目标状态标签。可以按以下方法输入 R-程序：

statelabelA   condition1   action1     statelabelA
              true         action2     statelabelB
statelabelB   condition3   action3     statelabelA
...

对我而言，这种风格化的纯文本记号最吸引我：它可以用于组织关于程序的状态的思考，对于一个状态，强制程序员考虑该状态所有可能的转变。

下面以我在 1987 或 1988 年用 Algol-98 编写的列车调度程序为例。程序中的（候选）列车时刻表用一株树结构表示，我用 R-技术编写了对树结构的各种遍历和变换算法。其中最简单的是打印树：深度优先遍历树并打印树节点的数据。遍历不使用栈，是在恒定的空间内迭代完成的。列车调度程序运行于 ES-1033（IBM S\360 主机的苏联仿制版），主机内存只有 1 MB，在其上编程必须对深的递归慎之又慎。

为了让现代的读者更易于理解和打印 R-程序，我用 C 重写了它，如下所示。树是一个链接数据结构，树节点指向右侧兄弟节点，父节点和第一个子节点。换言之，树是单链表（兄弟方向）和双链表（父子方向）的杂交产物，这点与原始 Algol-68 代码一样。不同的是，本例中，节点的载荷只有一个整数（原始调度程序中放入了更多数据）。

typedef struct _node node;    /* forward declaration */

struct _node {
  node * up;                  /* parent pointer */
  node * down;                /* first-born child */
  node * right;               /* brother */
  int data;                   /* payload: just an int in our example */
};

const node * const nil = (node *)NULL;

下面把打印树函数编写为 R-机器。它会深度优先遍历树，在遍历的过程中打印节点的载荷。这个机器只有两个状态（不算 finish 标签），但有一个可变状态，即指向当前节点 n 的指针。机器定义的动作会更新 n，将其改为其相邻的节点。因此，实际状态是无限制的。

void dump(const node * const tree) {
  const node * n = tree;        /* current node */
  enum {finish,down,right_up} state = down;

  /* The R-machine execution, with two states */
  while(state != finish)
    switch(state) {
    case down:
      /*   condition            action                              next-state */
      if(n->down == nil) {printf("data %d----- leaf\n",n->data);
                                                            state = right_up;}
      else               {printf("data %d\n",n->data); n = n->down;
                                                            state = down;}
      break;

    case right_up:
      if      (n->right != nil) {n = n->right; state=down;}
      else if (n->up == nil)    {n = nil;      state=finish;}
      else                      {n = n->up;    state=right_up;}
      break;

    case finish: break;
    }
}

Algol-68 中有序列和匿名函数的表示记号。因此在 Algol-68 中，用普通的例程就可以表示 R-机器，R-程序则用内联在例程里的序列表示，序列元素为函数组成的元组。读者可以回顾上面提到的某书中的 4 列表格格式。C 代码也可以写成类似的样子。

附带的 C 代码中还包含一个更有趣的 R-程序：在不使用栈的情况下迭代构建一棵完整的二叉树，如果不计算已分配的树节点的话，该程序消耗的内存是恒定的。C 代码中还包含了更复杂的树生成器，我第一次尝试编写这个生成器时就成功了。不过我必须说明，思考该树生成器（之前的 Algol-68 代码中没有这个生成器）确实花了一些心思：需要多少个 R-状态？某个状态的意义是什么？多少可变状态才足够？使用 50 年前的技术写这段 C 程序的经历也证实了 R-技术给我上过的一课：写代码时多思考，以后调试没烦恼。

引用资料

Igor V. Velbitskiy. Graphical Programming and Program Correctness Proof

http://glushkov.org/wp-content/131120CSITeng.pdf

Ushakov I., Velbitskiy I. (1993) Visual programming in R-technology: Concepts, systems and perspectives

In: Bass L.J., Gornostaev J., Unger C. (eds) Human-Computer Interaction. EWHCI 1993. Lecture Notes in Computer Science, vol 753. Springer, Berlin, Heidelberg. doi:10.1007/3-540-57433-6_48

V.M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 1961, v16:5, 1-53. (English version) doi:10.1070/RM1961v016n05ABEH004112
bldg.bld

Algol-68 中的 R-机器（的一种实现）。