程序是个状态机

• 程序在计算机上运行的本质：

  • 给定一个程序，将其放到计算机的内存中
    • 相当于在状态数量为N的状态转移图中指定了一个初始状态
  • 程序的运行过程时这个处室状态开始，每执行完一条指令，就回进行一次确定的状态转移

    [!note] 也就是说，程序也可以看成一个状态机

• 对于1+2+...+99+100的指令序列：

  // PC: instruction    | // label: statement
  0: mov  r1, 0         |  pc0: r1 = 0;
  1: mov  r2, 0         |  pc1: r2 = 0;
  2: addi r2, r2, 1     |  pc2: r2 = r2 + 1;
  3: add  r1, r1, r2    |  pc3: r1 = r1 + r2;
  4: blt  r2, 100, 2    |  pc4: if (r2 < 100) goto pc2;   // branch if less than
  5: jmp 5              |  pc5: goto pc5;
  

  • 状态机：(PC,r1,r2)
  • 状态转移过程：(0, x, x) -> (1, 0, x) -> (2, 0, 0) -> (3, 0, 1) -> (4, 1, 2) -> (5, 3, 3) -> ()

• 从两个视角来看同一个程序：

  • 从代码为表现形式的静态视角：
    • 写程序/看代码
    • 好处：描述精简、分支、循环和函数调用的组合使我们可以通过少量的代码实现出很复杂的功能
    • 款能会使我们对于程序行为的理解造成困难
  • 以状态机的转态转移为运行效果的动态视角
    • 刻画了“程序在计算机上运行”的本质
    • 状态数量非常大，程序代码中的所有循环和函数调用都以指令的粒度被完全展开，使得我们难以掌握程序的整体语义
    • 但是对于程序的局部行为，尤其是从静态的视角来看难以理解的行为，状态机的视角可以让我们更加清除的了解到相应的细节