布尔函数和逻辑门 Boolean Functions and Gate Logic

布尔逻辑 Boolean Logic

与或非

布尔函数合成 Boolean Functions Synthesis

不同的布尔函数能表达相同的意思

所有布尔函数都可以用“与或非”表示

进一步，都可以用“与非”表示 (x OR y) = NOT(NOT(x) AND NOT(y))

更进一步，可以用 NAND （AND 的否定）表示（NOR 也可以）：

NOT(x) = (x NAND x)
(x AND y) = NOT(x NAND y)

故可以仅使用 NAND 构造整个逻辑

逻辑门 Logic Gates

基本逻辑门，复合逻辑门

将复合逻辑门看作黑盒，关心接口，不关心实现

硬件描述语言 Hardware Description Language

// 接口
CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // 实现
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=a, b=notb, out=aAndNotb);
    And(a=b, b=nota, out=bAndNota);
    Or(a=aAndNotb, b=bAndNota, out=out);
}

HDL 是一种函数式语言
HDL 的顺序不重要
想要使用芯片，必须了解其接口，如 Not(in= , out= )
partName(a=a, out=out) 之类的写法很常见

常见的 HDL：VHDL，Verilog

硬件模拟 Hardware Simulation

老师专门为该课程编写的一个程序，用于测试。虽然简陋，但五脏俱全，设计非常精巧

在实际的硬件开发中，一般分两种岗位：

系统架构师
开发者

架构师决定使用的芯片，对于每块芯片，架构师创造：

API
测试脚本
比较文件

开发者根据这些要求制作

多比特总线 Multi-bit Buses

使用起来类似数组

支持分成子总线，如 a[0..7]=lsb, a[8..15]=msb

注意，a[0] 表示最右边的位

布尔代数和 ALU Boolean Arithmetic and the ALU

二进制数字 Binary Numbers

二进制的表示，与十进制的转换等

二进制加法 Binary Addition

半加器：

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b
        carry;  // Left bit of a + b
}

全加器：

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c
}

16 位加法：

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];
}

负数 Negative Numbers

将 $-x$ 表示为 $2^n-x$ ，化简得 $1 + (2^n - 1) - x$ ，即取反加一

保证了正负零一致

算术逻辑单元 ALU

计算两个输入的函数，并输出结果

接受一些控制位：

if (zx == 1) set x = 0     // 16-bit constant

if (nx == 1) set x = !x    // bitwise not

if (zy == 1) set y = 0     // 16-bit constant

if (ny == 1) set y = !y    // bitwise not

if (f == 1)  set out = x + y  // integer 2's complement addition

if (f == 0)  set out = x & y  // bitwise and

if (no == 1) set out = !out  // bitwise no

除了结果外，还有两个位输出一些有用的信息：

if (out == 0) set zr = 1

if (out < 0) set ng = 1

通过那些控制位，可以实现计算

$x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y, x+1, y+1, x-1, y-1, x\&y, x\|y$

内存 Memory

序列逻辑 Sequential Logic

把时间离散化，可以忽略延迟

组合逻辑：out[t] = function(in[t])

序列逻辑：state[t] = function(state[t-1])

触发器 Flip Flops

有两种状态：记忆 0 和记忆 1

时钟数据触发器（DFF）：out[t] = in[t-1]

所以序列逻辑的实现如图：

序列逻辑实现

如果是时钟，则组合逻辑为 +1

1 bit 的寄存器，load 控制读写

内存单元 Memory Units

最基本的内存元素：register

输入数据长度 w

RAM 的抽象：

n 个寄存器序列
每次只有一个寄存器选中
地址长度 $k = \log_2n$
RAM 就是一个有时钟表现的序列芯片

随机访问：无论 RAM 大小如何，每个寄存器都可以在相同的时间被访问

计时器 Counters

因为计算机需要跟踪获取的指令并执行下一个，此控制可以通过程序计时器实现

CHIP PC {
    IN in[16],load,inc,reset;
    OUT out[16];
}

机器语言 Machine Language

元素 Elements

内存层次结构，CPU 中有寄存器

控制流，如循环

黑客计算机和机器语言 The Hack Computer and Machine Language

构成：

数据内存 RAM
指令内存 ROM
CPU
指令、数据、地址总线

三个寄存器：

D 保存一个 16 bit 的值
A 保存一个 16 bit 的值
M 代表地址为 A 的 16 bit RAM 寄存器

A 指令：@value，其中 value 是一个非负十进制常数或一个代表常数的符号

效果：

将 A 寄存器设为 value
将 RAM[A] 变成选定的 RAM 寄存器

C 指令：dest = comp ; jump 其中 dest 和 jump 是可选的

comp = 0, 1, -1, D, A, ...
dest = null, M, D, MD, A, AM, AD, AMD
jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP

黑客语言详述 Hack Language Specification

A 指令对应二进制数

C 指令分为三段，一一对应

输入-输出 Input-Output

屏幕内存映射：

将像素 (row, col) 开关：

word = Screen[32*row +col/16]
word = RAM[16384 + 32*row + col/16]
将 word 的 (col % 16) 位变为 0 或 1
将 word 放到 RAM 中

键盘内存映射：

当键被按下，代码出现在其中，为相应的 ASCII 码；若没有键被按下，则为 0

黑客编程 Hack Programming

处理寄存器和内存

// RAM[17] = 10
@10
D=A
@17
M=D

由于数字和内存写法一致，可采用以下写法区分：

// RAM[17] = 10
@10
D=A
@R17
M=D

还有一些特殊的记号，如 SCREEN,KBD 等

终止程序：写一个死循环

@END
0;JMP

分支

// if R0 > 0
//	  R1 = 1
// else
//	  R1 = 0
	@R0
	D = M

	@POSITIVE
	D;JGT

	@R1
	M = 0
	@END
	0; JMP

(POSITIVE)
	@R1
	M = 1

(END)
	@END
	0; JMP

变量

// temp = R1
@R1
D = M
@temp
M = D

迭代

// RAM[1] = 1 + 2 + ... + n
@R0
D = M
@n
M = D
@i
M = 1
@sum
M = 0
(LOOP)
	@i
	D = M
	@n
	D=D-M
	@STOP
	D;JGT // if i > n goto STOP

	@sum
	D = M
	@i
	D = D + M
	@sum
	M = D // sum = sum + 1
	@i
	M = M + 1 // i = i + 1
	@LOOP
	0; JMP

(STOP)
	@sum
	D = M
	@R1
	M = D // RAM[1] = sum

(END)
	@END
	0; JMP

指针

需要用指针访问内存时，使用 A=M，如

@i
A = D + M
M = -1

计算机结构 Computer Architecture

冯诺依曼结构 Von Neumann Architecture

冯诺依曼结构

信息流

获取-执行循环 The Fetch-Execute Cycle

基本 CPU 循环：从程序内存中获取一个指令并执行它

通过 PC 控制指令的顺序执行或跳出

程序和数据存在一起，可能产生冲突，其中一个解决方法是用多路复用器：

但是这里使用的是简单的将程序和数据放在内存的不同部分

中央处理器 Central Processing Unit

CPU接口

CPU内部结构

指令分为 A 和 C 两种

具体的控制位详见代码：

CHIP CPU {

    IN  inM[16],         // M value input  (M = contents of RAM[A])
        instruction[16], // Instruction for execution
        reset;           // Signals whether to re-start the current
                         // program (reset==1) or continue executing
                         // the current program (reset==0).

    OUT outM[16],        // M value output
        writeM,          // Write to M?
        addressM[15],    // Address in data memory (of M)
        pc[15];          // address of next instruction

    PARTS:
    // Put your code here:
    // 第一个 Mux16
    Mux16(a=instruction, b=ALUout, sel=instruction[15], out=ia);

    // ARegister
    And(a=instruction[15], b=instruction[5], out=a1);
    Not(in=instruction[15], out=a2);
    Or(a=a1, b=a2, out=inARegister);
    ARegister(in=ia, load=inARegister, out=ARegisterOut, out[0..14]=addressM);

    // 第二个 Mux16
    And(a=instruction[15], b=instruction[12], out=mux2);
    Mux16(a=ARegisterOut, b=inM, sel=mux2, out=ALUin);

    // DRegister
    And(a=instruction[15], b=instruction[4], out=inDRegister);
    DRegister(in=ALUout, load=inDRegister, out=DRegisterOut);

    // ALU
    And(a=instruction[15], b=instruction[11], out=zx);
    And(a=instruction[15], b=instruction[10], out=nx);
    And(a=instruction[15], b=instruction[9], out=zy);
    And(a=instruction[15], b=instruction[8], out=ny);
    And(a=instruction[15], b=instruction[7], out=f);
    And(a=instruction[15], b=instruction[6], out=no);
    ALU(x=DRegisterOut, y=ALUin, zx=zx, nx=nx, zy=zy, ny=ny, f=f, no=no, out=ALUout, out=outM, zr=zr, ng=ng);

    // write
    And(a=instruction[15], b=instruction[3], out=writeM);

    // PC
    // 分解出大于、小于、等于
    And(a=instruction[15], b=instruction[0], out=greater);
    And(a=instruction[15], b=instruction[1], out=equal);
    And(a=instruction[15], b=instruction[2], out=less);

    // 正数
    Not(in=ng, out=nng);
    Not(in=zr, out=nzr);
    And(a=nng, b=nzr, out=ps);

    // 分别判断是否满足条件
    And(a=less, b=ng, out=isLess);
    And(a=equal, b=zr, out=isEqual);
    And(a=greater, b=ps, out=isGreater);

    Or(a=isLess, b=isEqual, out=part);
    Or(a=part, b=isGreater, out=load);

    PC(in=ARegisterOut, load=load, inc=true, reset=reset, out[0..14]=pc);
}

黑客计算机 The Hack Computer

内存实现

黑客计算机

课程结构

汇编器 Assembler

汇编语言和汇编器 Assembly Languages and Assemblers

汇编器是软件，是硬件上的第一层软件

重复直到文件结束：

读取下一个汇编语言命令
分成不同域
对每个域查找二进制代码
把代码组合成一个简单的机器语言命令
输出机器语言命令

用符号表将变量名和预先定义的常量映射为数字地址

黑客汇编语言：一个翻译者的立场 The Hack Assembly Language: A Translator's Perspective

空格：
- 空行 / 缩进
- 行内注释
- 行间注释
指令：
- A 指令
- C 指令
符号：
- 预先定义的符号
- 标签声明 (label)
- 变量声明 @variableName

汇编过程：处理指令 The Assembly Process: Handling Instructions

A 指令 @value：

如果是一个数字，则生成等价的 15 bit 二进制常数
如果是符号，则见后

C 指令：

翻译C指令

汇编过程：处理符号 The Assembly Process: Handling Symbols

一图胜千言

开发一个黑客汇编器：建议软件结构 Developing a Hack Assembler: Proposed Software Architecture

parsing

coding

虚拟机 I：栈算术 Virtual Machine I: Stack Arithmetic

课程计划

程序编译预览 Program Compilation Preview

两层编译

虚拟机抽象：栈 VM Abstraction: the Stack

push,pop 操作

对栈使用函数：

pop 参数
计算 $f$
push 结果

虚拟机抽象：内存段 VM Abstraction: Memory Segments

因为变量有多种，故内存也有分段：

push segment i：

segment：argument, local, static, constant, this, that, pointer, temp
i：非负正数（该内存段中的地址）

pop segment i：

segment：argument, local, static, this, that, pointer, temp
i：非负正数（该内存段中的地址）

虚拟机实现：栈 VM Implementation: the Stack

指针操作：

D = *p 	// D = 23

p--    	// RAM[0] = 256
D = *p 	// D = 19

简单来说，就是 push constant i -> *SP = i, SP++

虚拟机实现：内存段 VM Implementation: Memory Segments

对于 local 之类，存储一个指向该内存段首地址的指针 LCL

pop local i -> addr = LCL + i, SP--, *addr = *SP

push local i -> addr = LCL + i, *SP = *addr, SP++

argument, this, that 同理

const 比较简单：push constant i -> *SP = i, SP++

static 要存在全局，所以 static i -> Foo.i

temp 只有 8 个，push temp i -> addr = 5 + i, *SP = *addr, SP++，pop 同理

pointer 用于区分 this 和 that：push pointer 0/1 -> *SP = THIS/THAT, SP++

虚拟机 II：程序控制 Virtual Machine II: Program Control

程序控制 Program Control

分支控制：

goto label
if-goto label
label label

函数控制：

call functionName nArgs
function functionName nVars
return

分支 Branching

其中 if-goto label 是当 cond = pop 时，跳转到 label

函数：抽象 Functions: Abstraction

从 caller 来看，相当于把参数转化为了一个结果

从 callee 来看，相当于创造了一个新的空间，argument 和 local 预先分配好了，栈起初是空的

故：

call：

把参数传递给被调函数
决定在 caller 代码中返回的地址
保存 caller 的返回地址，栈，内存段
跳到执行被调函数

return：

返回计算出的值给 caller
循环利用被调函数使用的内存资源
恢复 caller 的栈和内存段
跳到 caller 代码的返回地址

函数调用和返回：实现预览 Function Call and Return: Implementation Preview

函数的调用链：栈

函数调用的三个过程对内存的操作

call

function

return

全局栈实现了调用链

函数调用和返回：运行模拟 Function Call and Return: Run-time Simulation

函数调用和返回：实现 Function Call and Return: Implementation

处理 call functionName nArgs：

push returnAddress
push LCL
push ARG
push THIS
push THAT
ARG = SP-5-nArgs
LCL = SP
goto functionName
(returnAddress)

call实现

处理 function functionName nVars：

(functionName)
	repeat nVars times:
	push 0

function实现

处理 return：

endFrame = LCL
retAddr = *(endFrame - 5)
*ARG = pop()
SP = ARG + 1
THAT = *(endFrame - 1)
THIS = *(endFrame - 2)
ARG = *(endFrame - 3)
LCL = *(endFrame - 4)
goto retAddr

return实现

在黑客平台上的 VM 实现 VM Implementation on the Hack Platform

引导：

VM 程序中其中一个叫 Main.vm，该文件中的一个函数叫 main
当 VM 实现运行时，第一个执行无参数的函数 Sys.init
Sys.init 调用 Main.main，进入无限循环

高级语言 High-Level Language

Jack 语言概论 The Jack Language in a nutshell

Jack 语言是类似 Java 的语言，面向对象，但不支持继承

必须有一个类 Main，其必须有 main 函数，程序的进入点是 Main.main

Jack 中的 Array 是没有类型的

操作系统：

Keyboard.readInt
Output.printString
Output.printInt

数据类型：

原始：
- int
- char
- boolean
类的类型：
- 操作系统：Array、String
- 程序扩展

基于对象编程 Object-Based Programming

/** Represents the Fraction type and related operations. */
class Fraction {
   field int numerator, denominator;  // field = property = member variable.

   /** Constructs a (reduced) fraction from the given numerator and denominator. */
   constructor Fraction new(int x, int y) {
      let numerator = x;
      let denominator = y;
      do reduce();   // reduces the fraction
      return this;   // a constructor is expected to return a reference to the new object
   }

   // Reduces this fraction.
   method void reduce() {
      var int g;
      let g = Fraction.gcd(numerator, denominator);
      if (g > 1) {
         let numerator = numerator / g;
         let denominator = denominator / g;
      }
      return;
   }

   /** Accessors. */
   method int getNumerator() { return numerator; }
   method int getDenominator() { return denominator; }

   /** Returns the sum of this fraction and the other one. */
   method Fraction plus(Fraction other) {
      var int sum;
      let sum = (numerator * other.getDenominator()) + (other.getNumerator() * denominator);
      return Fraction.new(sum, denominator * other.getDenominator());
   }

   // More fraction-related methods (minus, times, div, etc.) can be added here.

   /** Disposes this fraction. */
   method void dispose() {
      do Memory.deAlloc(this);  // uses an OS routine to recycle the memory held by the object
      return;
   }

   /** Prints this fraction in the format x/y. */
   method void print() {
      do Output.printInt(numerator);
      do Output.printString("/");
      do Output.printInt(denominator);
      return;
   }

   // Computes the greatest common divisor of the given integers.
   function int gcd(int a, int b) {
      var int r;
      while (~(b = 0)) {             // applies Euclid's algorithm
         let r = a - (b * (a / b));  // r = remainder of the integer division a/b
         let a = b; let b = r;
      }
      return a;
   }
}

还有调用：

// Computes the sum of 2/3 and 1/5.
class Main {
   function void main() {
      var Fraction a, b, c;
      let a = Fraction.new(2,3);
      let b = Fraction.new(1,5);
      let c = a.plus(b);  // Computes c = a + b
      do c.print();       // Prints "13/15"
      return;
   }
}

已经比较详细了，不必多说

注意几点：

field 相当于私有的成员变量
function 相当于 Java 中的 static 函数
this 是地址，constructor 必须显式返回 this
任何函数都必须 return，其中 void 函数必须显式 return
由于没有垃圾收集，所以必须显式 dispose

列表处理 List Processing

定义：

null
或一个元素 + list

Jack 语言规范：语法 Jack Language Specification: Syntax

语法元素：

空格，注释
关键字
符号
常数
标识符

Jack 语言规范：数据类型 Jack Language Specification: Data Types

类型转换：

字符和整数可以相互转换
整数可赋值给数组名，被当成内存地址对待
一个对象可以转化为一个数组，反之亦然

Jack 语言规范：类 Jack Language Specification: Classes

Jack 的标准库/OS 有 8 个类：Math、String、Array、Output、Screen、Keyboard、Memory、Sys

Jack 语言规范：方法 Jack Language Specification: Methods

let：必须在赋值中使用：let x = 0

do：必须被用于在表达式外调用函数或方法：do reduce()

语句的主体必须在括号内，即使只有一条语句

所有的子过程都必须以 return 结尾

运算符没有优先级： 2 + 3 * 4 = 20，2 + (3 * 4) = 14

弱类型

使用 Jack 语言和 OS 来开发应用程序 Developing Apps using the Jack Language and OS

文字输出：23 行，每行 64 个字符

详见官网的手册

编译器 I：语法分析 Compiler I: Syntax Analysis

语法分析 Syntax Analysis

Jack编译器开发步骤

词汇分析 Lexical Analysis

将输入的代码分解成一个个基本组成（tokens），如

tokenizer

语法 Grammars

语法是描述 tokens 是如何组合的规则，如

Jack grammar

解析树 Parse Trees

解析树

解析器逻辑 Parser Logic

遵守规则的右边，解析对应的输入
如果右边是一个不终止的规则 xxx，则调用 compileXXX
递归调用

LL grammar：可以被递归下降的解析器没有回调解析（简单来说就是没有“歧义”）

LL(k) parser：需要看最多 k 个 tokens 才能确定规则的解析器

Jack 语法 The Jack Grammar

注意如果一个 token 是 varName 时，要向后看，因为可能有多种情况

Jack 分析 The Jack Analysis

当碰到极个别非终止元素（type、class name、subroutine name、variable name、statement、subroutine call）时，不需要标记，因为 varName: identifier

编译器 II：代码生成 Compiler II: Code Generation

代码生成 Code Generation

处理变量 Handling Variables

在变量声明时，对类中的变量和函数中的变量分别生成一张符号表，注意任何函数符号表中都会自带一个 this 指针

符号表

在变量使用时，先在子过程层级的符号表中查找，若找不到，则查找类层级

对于嵌套的作用域，可以把符号表连成一个链表

处理表达式 Handling Expressions

表达式

可以看出，后缀表达式是最适合的

但是我们不需要建立表达式树，观察中缀表达式和后缀表达式的关系，可以得出：

codeWrite(exp):

如果 exp 是整数 n -> push n
变量 var -> push var
exp1 op exp2 -> codeWrite(exp1); codeWrite(exp2); op
op exp -> codeWrite(exp); op
f(exp1, exp2, ...) -> codeWrite(exp1); codeWrite(exp1); ... call f

再次重申 Jack 语言是没有操作符优先级的

处理控制流 Handling Flow of Control

编译if语句

while 则更简单：

编译while语句

注意处理多个 if-while 和嵌套 if-while

处理对象：低层级方面 Handling Objects: Low-Level Aspects

高级 OO 程序创建和操作对象和数组
中级 VM 程序在虚拟内存段上操作
低级机器程序直接在 RAM 上操作

而编译的难题就在于建立桥梁

对象数据通过 this 段访问
数组数据通过 that 段访问
在使用这些段之前，必须先用 pointer 锚定

处理对象：构造 Handling Objects: Construction

编译构造函数

处理对象：操作 Handling Objects: Manipulation

将 OO 风格转为过程风格：p1.distance(p2) -> distance(p1, p2)

因为每个方法都需要访问对象的 fields，即通过 this i 访问第 i 个 field

编译方法

对于 void 方法，返回一个 constant 0，并在调用后立刻 pop temp 0 释放掉

处理数组 Handling Arrays

将数组名赋予内存地址，使用 that 访问数组的位置，如

// arr[2] = 17
push arr
push 2
add
pop pointer 1
push 17
pop that 0

注意和对象不同，that 指向的是数组中的某一个元素

对于更复杂一些的情况（例如两边都有数组），则使用 temp 暂存右边的值，所以正确的写法是：

//arr[expression1]=expression2,
push arr
计算并 push expression1 的值
add
计算并 push expression2 的值
pop temp 0 // temp 0 = expression2, 栈顶值为 arr[expression1] 的地址
pop pointer1
push temp 0
pop that e

这个方案也适用于多重数组嵌套

对虚拟机的标准映射 Standard Mapping Over the Virtual Machine

文件和子过程：

每个文件 fileName.jack 被编译为 fileName.vm
每个 fileName.jack 中的子过程 subName 被编译为 VM 函数 fileName.subName
一个 k 个参数的 constructor 或 function 被编译为有 k 个参数的 VM 函数
一个有 k 个参数的 Jack method被编译为有 k+1 个参数的 VM 函数

变量：

local 变量映射到虚拟段 local
argument 变量映射到虚拟段 argument
static 变量映射到虚拟段 static
field 变量：
- 假设 pointer 0 为 this 对象
- 该对象的第 i 个 field 映射到 this i

数组：

将 pointer 1 设为地址 arr + i
通过 this 0 访问

编译子过程：

method：设置 this 段的地址为 argument 0
constructor：
- 对新的对象分配空间，设置 this 为新的对象地址
- 返回 this
void：返回 constant 0

调用子过程：将参数放入栈中，调用子过程

如果是 method，则先将该对象的引用放入，再放入参数并调用
如果是 void，则在结束后 pop 掉

常数：

null -> constant 0
false -> constant 0
true -> constant -1

操作系统 Operating System

包括的内容：

游戏时间分析
资源管理
处理输入
向量图形
文字输出
类型转换
字符串处理

效率很重要 Efficiency Matters

对于乘法，使用二进制的乘法竖式计算：

// 计算 x * y
multiply(x, y):
	sum = 0
	shiftedX = x
	for i = 0 ... w - 1 do
		if ((y 的第 i 位) == 1)
			sum = sum + shiftedX
		shiftedX = shiftedX * 2
	return sum

该算法正比于 $w = \log_2 N$
对于负数，该算法同样有效
对于溢出，该算法总是返回正确答案 $\mod 2^{16}$

对于其中的获取第 i 位的操作，定义一个函数：

function boolean bit(int x, int i)

初始化 Math 类时生成一个数组，存入 $2^i$ ，使用该数组来实现 bit(x, i)

数学操作 Mathematical Operations

对于除法，一种方法同样是模拟除法的竖式

这里给出第二种方法：

// 计算 x / y
divide(x, y):
	if (y > x) return 0
	q = divide(x, 2 * y)
	if ((x - 2 * q * y) < y)
		return 2 * q
	else
		return 2 * q + 1

该算法的基本思想是 $100 / 7 = 2 * (50 / 7) = 2 * (2 * (25 / 7)) = ...$

运行时间正比于 $\log_2 N$
处理负数时，计算 $|x| / |y|$ ，再设置符号
处理溢出：当 y 变成负数时，溢出可以被检测到，故将第一句改为 if (y > x || y < 0) return 0

平方根：反函数 $x^2$ 很容易计算，故策略为找到一个使得 $y^2 ≤ x < (y+1)^2$ ，通过二分搜索 $0 … 2^{n/2} - 1$

// 计算函数 y = sqrt(x)
sqrt(x):
	y = 0
	for j = n / 2 - 1 ... 0 do
		if (y + 2^j)^2 <= x then y = y + 2^j
	return y

对于溢出，将 (y + 2^j)^2 <= x 改为 (y + 2^j)^2 <= x && (y + 2^j)^2 > 0

内存访问 Memory Access

直接设置数组名指针为 0

class Memory {
	static array ram;

	function void init() {
		let ram = 0;
	}
}

堆管理 Heap Management

将可用的内存段连成一个链表

alloc(size)：寻找合适大小的内存段，将其从段中移除，交给客户
dealloc(object)：将该对象连到链表中

当然，这样做到最后就会有很多碎片内存段

实现：

static Array heap;
let heap = 2048

使用 heap 数组实现，地址 arr 的内存段的 next 和 size 可以通过 heap[adr - 1] 和 heap[addr - 2] 实现

图形 Graphics

向量图保存图形的画法，放大后不失真；位图保存像素，放大后失真

设置某一个像素颜色的命令与之前的类似：

function void drawPixel(int x, int y) {
	address = 32 * y + x / 16
	value = Memory.peek[16384 + address]
	设置 value 的第 (x % 16) 位为当前颜色
	do Memory.poke(address, value)
}

画线 Line Drawing

大概是近似方格覆盖线，其中决定是向上覆盖方格还是向右覆盖方格由 $\frac{b}{a}$ 和 $\frac{dy}{dx}$ 的大小关系决定

但每次计算太耗时，令 diff = a * dy - b * dx，观察每次 a 和 b 的改变，可以得出 diff 的改变

a = 0; b = 0; diff = 0;
while ((a <= dx) && (b <= dy))
	drawPixel(x + a, y + b);
	if (diff < 0) {a = a + 1; diff = diff + dy;}
	else {b = b + 1; diff = diff - dx;}

画圆：将实心圆转化为从上往下画一条条水平线，线的左右端点位置可以通过勾股定理得出

drawCircle(x, y, r)
	for each dy = -r to r do:
		drawLine(x - sqrt(r^2 - dy^2), y + dy, x + sqrt(r^2 - dy^2), y + dy)

空心圆则只需要画两个像素点即可

注意：

屏幕的原点在左上角
将算法推广到能画任何方向的线段
对于水平和竖直方向的线做特殊优化
对于溢出，限制 $r ≤ 181$

处理文字输出 Handling Textual Output

每个字符占据了固定大小的 11px 高，8px 宽的框架
右边有两个空列，底部有一个空行

字符集

在初始化时预先加载到内存中

光标：

newLine：移动光标到下一行的开头
backspace：光标左移一列
字符：显示字符，光标右移一列

输入 Input

比较简单：

keyPressed():
	if 键盘被按下:
		return key 的代码
	else
		return 0

readChar():
	显示光标
	// 等待直到一个键被按下
	while (keyPressed() == 0):
		什么都不做
	c = 当前按下的键
	// 等待直到该键松开
	while (keyPressed() != 0):
		什么都不做
	在当前光标位置显示 c
	移动光标

readLine():
	str = 空字符串
	重复
		c = readChar()
		if (c == newLine):
			显示 newLine
			return str
		else if (c == backSpace):
			从 str 中移除最后的字符
			do Output.backspace()
		else
			str = str.append(c)
	return str

字符串处理 String Processing

// 将整数转化为字符串
int2String(val):
	lastDigit = val % 10
	c = 代表 lastDigit 的字符
	if (val < 10)
		return c
	else
		return int2String(val / 10).append(c)

// 将字符串转化为整数
string2Int(str):
	val = 0
	for (i = 0 ... str.length) do
		d = str[i] 的整数值
		val = val * 10 + d
	return val

字符串本身就是一个 Array

数组处理 Array Processing

Array.new 不要作为一个 constructor，而是作为一个 function，使用 Memory.alloc
Array.dispose 使用 Memory.deAlloc

Sys 类 The Sys Class

class Sys {
	function void init() {
		do Math.init();
		do Memory.init();
		do Screen.init();
		...
		do Main.main();
	}
}

Sys.halt：使用无限循环实现
Sys.wait：使用循环实现，和机器相关