note-math

自然语言的例子

数字电路表示 bool

这里不处理数字电路的硬件实现. 我也不知道细节

• 且, , and, 逻辑合取 (conjunction)
• 或, , or, 逻辑析取 (disjunction)
• 非, , not, 逻辑反取 (negation)

自然语言的例子

形式语言

的数字电路和逻辑门 (gate) 的表示

gate 设计为不允许反向电流?

not gate 将低电平转到高电平, 说明 gate 的硬件实现需要外部能量, 需要通电

是 “冗余” 的, e.g. 逻辑等价地, 我们可以用 表示

电路 gate 实现是用 not,nand, 也即 作为开始. 但我觉得保持 的对称性是有用的, 无论是认知上, 还是 对于 的对偶上

可用逻辑门制造任何 函数

(image from p.85 of ref-1)

分别考虑 函数的输入 和输出

• 输入的构造

对于输出, 我们先讨论 输出

• 输出的构造

在 输入中, 将想要输出到 的电线接到 or gate

Example not xor 函数. 将输入 接入输出的 or gate

xor 叫做互斥或, . 这个函数的真值表

1	1	0
1	0	1
0	1	1
0	0	0

• 输出的构造. 可以认为是 个 作为其分量

如果不需要完整的 函数, 电路计算元件不一定要按这种固定方式来构建. 可以根据情况, 进一步简化, 减少 gate 数量的使用. 但这里不进入细节

bool 代数记为 或者

[bool-distributive-law] 分配律

[bool-commutative-law] 交换律 . same for

[bool-associative-law] 结合律 . same for

黑箱模型

可能的实现

• 图中间使用环电路重用上一个周期的 Bool 值. 如果关闭 write control, 则 的值不变
• 反相器 (not gate) 确保电流方向并防止衰减 (通过外部能量)
• 假设环电路中黄色部分的值是 , 蓝色部分的值是 . 为了将 写入已有的 , 需要比环电路里的电压更高的写入电压来覆盖循环电路, i.e. 用更高电压 从而 来覆盖已有的

[finite-machine] 有限状态机

[i/o] 电路的输入可能来自外界 (e.g. 传感器, 键盘), 电路的输出也可能到达外界 (e.g. 信号灯, 屏幕)

外界输入的节奏通常不一致于计算机内部周期电路的节奏, 因此需要让外界输入先经过同步元件

Example 就是从 000, 001, 010 数到 111 时经过的步数, 虽然这假设了我们能识别三位 bit. ,

用多位 bit 包含的自然数范围, 例如 3 bit 的 作为参数, 去对应到真实世界的内容. Example 计算机的字符的表示方式 e.g. ASCII, Unicode, 屏幕的发光点位置和颜色

(image modified from wiki media about ASCII. Hex 是指十六进制)

在实际应用中, 每个地址多个 bit 好于每个地址 1 bit, 或者说, 二维内存阵列比一维高效

(p. 265 of ref-1)

通过指令来控制计算机完成一些电路任务. 指令也由二进制 (多位 bit 的数据) 表示. 指令流由编译器根据源代码生成并存放在内存中, 被读取然后被 CPU 执行

一些常用电路任务

• 自然数的加法
• 判断 bit 数据是否满足所需条件, 例如判断
• 跳转到其它指令的执行

假设一个指令在一个电路周期内完成 (单周期计算机)

Example add 指令. add x_1 x_2. 指令的 bit 数据位分为三个区域, 表示不同类型的信息

1. 读取 add 指令

   • add 指令在 adress_0 (add x_1 x_2 以及 adress_1, adress 2 来自源代码和编译器的生成)
   • 固定的内存地址 adress_of_instruction 存储的值 adress_0 被读出, add 指令的 index 区的数据被送到控制信号元件 (control unit), 然后计算出控制信号并输出 (细节太多, 见 ref-1)

2. 执行 add 指令

   • 输出的控制信号输入到内存的控制电路元件, 读出内存的 x_1 in adress_1 和 x_2 in adress_2, 将它们输入到算术元件 (ALU)
   • 根据输出控制信号, 算术元件的输出 x_1 + x_2 被写到 adress_1 (覆盖了 x_1 的值)

3. 进入和读取下一个周期的指令

   • adress_of_instruction 存储的值 adress_0 被已经设计好的电路送到算术元件, 计算出 adress_0 + 1 i.e. 下一个指令地址, 被写到 adress_of_instruction 里面的数据. adress_0 + 1 将在下一个电路周期被执行

其它指令可能有多于两个的数据区 (非指令 index 区)

周期电路的速度远远高过人类速度 (1 GHz = 每秒 10^9 次周期)

高级编程语言的循环

let i : int = 0;

while (i < 10) {

    i = i + 1;

} // result = 10

let i : int = 0;

while (i < 10) {

    i = i + 1;

} // result = 10

1. 读取指令

   bgt (branch_grater_than) 指令存储在 adress_0. (指令从源代码和编译器生成.) 10 在 bgt 的一个数据区, while loop 需要的指令数量 3 在 bgt 的另一个数据区

2. 执行指令

   执行条件判断

   读出 i 和 10, 在算术元件中比较大小, 根据结果给出控制信号, 结合指令 bgt index 区给出的控制信号

   根据条件判断的结果, 执行不同的任务

   • 时

   算术元件根据此判断输出控制信号, 将 adress_of_instruction 存储的值改变为下一条指令的地址 adress_0 + 1

   • adress_0 + 1 的指令要执行任务

     用 add 指令计算 i + 1, 写回 adress_1

   • 执行完 add 后, 要回到下一次循环的判断

     add 指令的下一条指令是 jump 指令, 在 adress_0 + 2, 执行结果是, 修改 adress_of_instruction 的值为 adress_of_instruction - 2 = (adress_0 + 2) - 2 = adress_0, 实现指令的跳转, 进行下一次循环的判断

   • 时
   算术元件根据此 bgt 判断, 输出控制信号, 将 adress_of_instruction 存储的值改变为 adress_0 + 3 而不是 adress_0 + 1, 跳出 while 循环, 执行后面的指令

用 parser or compiler (编译器) 验证 token 流语言正确性, 本质上是遍历所有语言规则, 然后在内存中存储为带结构的数据 (一些形象的描述: 表格, 结点, 树)

一种实现方法是递归下降, enum + match (或 if else) + 递归

如果想要让软件在计算机上运行, 就要将源代码的 token 流转为带结构的数据, 再转为指令流

如果语言规则很复杂, 可以对语言规则进行 (多次) 分类和分解, 先遍历分类, 再遍历分类里面的规则. Example 分开为 “syntax 检查” 和 “semantics 检查”