Overview
数字电路与状态机
include
include
define REGSFOREACH() (X) (Y)
define OUTSFOREACH() (A) (B) (C) (D) (E) (F) _(G)
define RUN_LOGIC X1 = !X && Y; \
define DEFINE(X) static int X, X##1;
define UPDATE(X) X = X##1;
define PRINT(X) printf(#X “ = %d; “, X);
什么是程序 (源代码视角)
define call(…) ({ *(++top) = (Frame) { .pc = 0, VA_ARGS }; })
define ret() ({ top—; })
define goto(loc) ({ f->pc = (loc) - 1; })

Overview

复习：操作系统

应用视角 (设计): 一组对象 (进程/文件/…) + API
硬件视角 (实现): 一个 C 程序

本次课回答的问题

Q: 到底什么是 “程序”？

本次课主要内容

程序的状态机模型 (和编译器)
操作系统上的 {最小/一般/图形} 程序

数字电路与状态机

数字电路与状态机
数字逻辑电路
状态 = 寄存器保存的值 (flip-flop)
初始状态 = RESET (implementation dependent)
迁移 = 组合逻辑电路计算寄存器下一周期的值

前置课程: 计算机系统基础操作系统与数字电路的等价性

计数器
计数器跳转: 状态的迁移为一个时钟周期
通过逻辑公式, 算出下一个计数器

例子：
X′=¬X∧Y
Y′=¬X∧¬Y

数字逻辑电路：模拟器

#include <stdio.h>
#include <unistd.h>
// 定义2个寄存器:X, Y
#define REGS_FOREACH(_)  _(X) _(Y)
// 组合\运算逻辑
#define RUN_LOGIC        X1 = !X && Y; \
                         Y1 = !X && !Y;
// 定义一个寄存器
#define DEFINE(X)        static int X, X##1;
// 更新一个寄存器
#define UPDATE(X)        X = X##1;
// 打印一个寄存器
#define PRINT(X)         printf(#X " = %d; ", X);
int main() {
  REGS_FOREACH(DEFINE);
  while (1) { // clock
    RUN_LOGIC;
    REGS_FOREACH(PRINT);
    REGS_FOREACH(UPDATE);
    putchar('\n');
    sleep(1);
  }
}

用#include <unistd.h>找不到头文件, cygwin有头文件, 但就是找不到

gcc -E a.c: 宏展开

int main() {
  static int X, X1; static int Y, Y1;;
  while (1) {
    X1 = !X && Y; Y1 = !X && !Y;;
    printf("X" " = %d; ", X); printf("Y" " = %d; ", Y);;
    X = X1; Y = Y1;;
    putchar('\n');
    sleep(1);
  }
}

更完整的实现：数码管显示

输出数码管的配置信号

logisim.c
会编程，你就拥有全世界！
- seven-seg.py
- 同样的方式可以模拟任何数字系统
  - 当然，也包括计算机系统 ```c
    include
    include

define REGSFOREACH() (X) (Y)

define OUTSFOREACH() (A) (B) (C) (D) (E) (F) _(G)

define RUN_LOGIC X1 = !X && Y; \

                     Y1 = !X && !Y; \
                     A  = (!X && !Y) || (X && !Y); \
                     B  = 1; \
                     C  = (!X && !Y) || (!X && Y); \
                     D  = (!X && !Y) || (X && !Y); \
                     E  = (!X && !Y) || (X && !Y); \
                     F  = (!X && !Y); \
                     G  = (X && !Y);

define DEFINE(X) static int X, X##1;

define UPDATE(X) X = X##1;

define PRINT(X) printf(#X “ = %d; “, X);

int main() { REGS_FOREACH(DEFINE); OUTS_FOREACH(DEFINE); while (1) { // clock RUN_LOGIC; OUTS_FOREACH(PRINT); REGS_FOREACH(UPDATE); putchar(‘\n’); fflush(stdout); sleep(1); } }

输出7段数码管
```shell
A = 1; B = 1; C = 1; D = 1; E = 1; F = 1; G = 0; 
A = 0; B = 1; C = 1; D = 0; E = 0; F = 0; G = 0; 
A = 1; B = 1; C = 0; D = 1; E = 1; F = 0; G = 1; 
A = 1; B = 1; C = 1; D = 1; E = 1; F = 1; G = 0; 
A = 0; B = 1; C = 1; D = 0; E = 0; F = 0; G = 0; 
A = 1; B = 1; C = 0; D = 1; E = 1; F = 0; G = 1; 
A = 1; B = 1; C = 1; D = 1; E = 1; F = 1; G = 0; 
A = 0; B = 1; C = 1; D = 0; E = 0; F = 0; G = 0; 
A = 1; B = 1; C = 0; D = 1; E = 1; F = 0; G = 1; 
...

加入后端处理

import fileinput
TEMPLATE = '''
\033[2J\033[1;1f
     AAAAAAAAA
    FF       BB
    FF       BB
    FF       BB
    FF       BB
    GGGGGGGGGG
   EE       CC
   EE       CC
   EE       CC
   EE       CC
    DDDDDDDDD
''' 
BLOCK = {
    0: '\033[37m░\033[0m', # STFW: ANSI Escape Code
    1: '\033[31m█\033[0m',
}
VARS = 'ABCDEFG'
for v in VARS:
    globals()[v] = 0
stdin = fileinput.input()
while True:
    exec(stdin.readline())
    pic = TEMPLATE
    for v in VARS:
        pic = pic.replace(v, BLOCK[globals()[v]]) # 'A' -> BLOCK[A], ...
    print(pic)

# python3 seven-seg.py 
A = 1
    █████████
    ░░       ░░
    ░░       ░░
    ░░       ░░
    ░░       ░░
    ░░░░░░░░░░
   ░░       ░░
   ░░       ░░
   ░░       ░░
   ░░       ░░
    ░░░░░░░░░

./a.out | python3 seven-seg.py
动画.gif
1.2 操作系统上的程序 - 图3

你还体验了 UNIX 哲学

Make each program do one thing well
Expect the output of every program to become the input to another

什么是程序 (源代码视角)

什么是程序？

Hmm….

你需要《程序设计语言的形式语义》

by 梁红瑾 🎩
λ-calculus, operational semantics, Hoare logic, separation logic
入围 “你在南京大学上过最牛的课是什么？” 知乎高票答案
- ~~当然，我也厚颜无耻地入围了~~

不，你不需要

程序就是状态机 (你在 gdb 里看到的)

试试程序吧 hanoi-r.c

void hanoi(int n, char from, char to, char via) {
if (n == 1) printf("%c -> %c\n", from, to);
else {
  hanoi(n - 1, from, via, to);
  hanoi(1,     from, to,  via);
  hanoi(n - 1, via,  to,  from);
}
return;
}

理解这个递归并不容易

#include <stdio.h>
#include "hanoi-r.c"
int main()
{
  hanoi(3, 'A', 'B', 'C');
  return 0;
}

GDB运行 >所指向的亮条就是PC

> gcc -g main.c -o main
> gdb -tui main
(gdb) start

(gdb) s

info frame: 查看栈帧信息

递归

(gdb) s
(gdb) s
(gdb) info frame

C 程序的状态机模型 (语义，semantics)

状态 = 堆 + 栈
初始状态 = main 的第一条语句
迁移 = 执行一条简单语句
- 任何 C 程序都可以改写成 “非复合语句” 的 C 代码
- 真的有这种工具 (C Intermediate Language) 和解释器

(这还只是 “粗浅” 的理解)

Talk is cheap. Show me the code. (Linus Torvalds): 任何真正的理解都应该落到可以执行的代码

写一个C语言的解释器

C 程序的语义

C语言的状态到底是什么函数调用是什么? 函数返回是什么? 能说明白吗?

C 程序的状态机模型 (语义，semantics)

状态 = stack frame 的列表 (每个 frame 有 PC) + 全局变量
初始状态 = main(argc, argv), 全局变量初始化
迁移 = 执行 top stack frame PC 的语句; PC++
- 函数调用 = push frame (frame.PC = 入口)
- 函数返回 = pop frame
  
  懵逼中…

应用：将任何递归程序就地转为非递归

汉诺塔难不倒你 hanoi-nr.c
A → B, B → A 的也难不倒你
- 还是一样的 call()，但放入不同的 Frame ```c // 栈帧 typedef struct { int pc, n; char from, to, via; } Frame;

define call(…) ({ *(++top) = (Frame) { .pc = 0, VA_ARGS }; })

define ret() ({ top—; })

define goto(loc) ({ f->pc = (loc) - 1; })

void hanoi(int n, char from, char to, char via) { Frame stk[64], top = stk - 1; call(n, from, to, via); for (Frame f; (f = top) >= stk; f->pc++) { switch (f->pc) { case 0: if (f->n == 1) { printf(“%c -> %c\n”, f->from, f->to); goto(4); } break; case 1: call(f->n - 1, f->from, f->via, f->to); break; case 2: call( 1, f->from, f->to, f->via); break; case 3: call(f->n - 1, f->via, f->to, f->from); break; case 4: ret(); break; default: assert(0); } } }

```c
#include <stdio.h>
#include <assert.h>
#include "hanoi-nr.c"
int main()
{
  hanoi(3, 'A', 'B', 'C');
  return 0;
}

与递归版本对比

GDB调试, 查看状态转换

1.2 操作系统上的程序