note-math

自然语言的例子

数字电路表示 bool

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

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

自然语言的例子

形式语言

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

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

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

"冗余性" e.g. 我们可以用 表示

电路 gate 实现是用 not,nand or 作为开始. 但我觉得保持 的对称性是有用的, 认知上或者 negetive dual 上

可用逻辑门制造任何 函数

(image from p.85 of ref-1)

• 输入的构造

• 输出的构造

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

Example not xor

互斥或, , xor

• 输出的构造. 只需将需要的电线组合接到 个 or game

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

bool 代数记为 或者

[bool-distributive-law] 分配律

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

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

黑箱模型

可能的实现

• 使用环电路重用上一个周期的 的 1/0 值
• 反相器 (not gate) 确保电流方向并防止 1 衰减 (通过外部能量)
• 为了将 0 写入已有的 1, 需要在 写入 1 得到 , 然后反转为
• 需要比循环里的电压更高的写入电压来覆盖循环中的先前已有的 ? e.g. 用更高电压 来覆盖已有的

[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)

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

通常由内存里一个地址中写着的多位 bit 数据来表示某些电路任务

一些常用电路任务

• 自然数的加法
• 判断 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

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_of_instruction 的值为 adress_0, 实现指令的跳转, 进行下一次循环的判断

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

用 parser or compiler (编译器) 验证 token 流语言正确性, 本质上是遍历所有语言规则 i.e. match + 递归, 用编程语言或电路语言. 或使用 (生成的) 有限状态机

parser 的运行需要生成内存中大型复杂的数据结构 (一些形象的描述: 表格, 结点, 树)

如果数据流是高级编程语言源代码, 还可以根据这个数据结构生成指令流. 此时称为 compile (编译), 但 parse 和 compile 经常混用

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