consume(num_bottles, num_drunk) { 5. // 条件表达式 6. if num_bottles >= num_exchange { 7. // 数据绑定 8. let num_bottles = num_bottles - num_exchange + 1 9. let num_drunk = num_drunk + num_exchange 为了写出正确的程序，我们需要知道程序是如何被运算的：我们需要建⽴计算模型 来理解程序的运算过程 ⽉兔程序可以通过⾯向值编程来描述 ⾯向值编程：定义是什么 我们写的⽉兔代码都是表达⼀个值的表达式 命令式编程⻛格：定义做什么 程序由修改程序状态的命令组成 创建名为x的变量 令x为5 令y指向x …… 10 类型、值与表达式 类型 值 运算 表达式 Int -1 0 1 2 + - * / 5 (3 + y * x) "Moonbit" + "Hello, " + "MoonBit" Bool true false && || not() not(b1) || b2 每⼀个类型对应⼀个值的集合 每⼀个表达式由基于值的运算构成，并且可以简化为⼀个值（或已经是⼀个值） 可以使⽤括号来嵌套表达式 11 静态 vs 动态 �静态�指在程序运⾏之前的事物 �动态�指在程序运⾏之时的事物 ⽉兔拥有静态类型系统：在程序运

到此为⽌，我们介绍的可以归类于函数式编程的范畴 对每⼀个输⼊，有着固定的输出 对于标识符，我们可以直接⽤它所对应的值进⾏替代⸺引⽤透明性 开发实⽤的程序，我们需要⼀些计算之外的�副作⽤� 进⾏输⼊输出 修改内存中的数据等 这些副作⽤可能导致多次执⾏的结果不⼀致 2 引⽤透明性 我们可以定义如下数据绑定和函数 1. let x: Int = 1 + 1 2. fn square(x: Int) -> -> Int { x * x } 3. let z: Int = square(x) // 4 我们可以将 square 与 x 直接⽤对应的值替换⽽不改变结果 1. let z: Int = { 2 * 2 } // 4 引⽤透明性可以易于理解 3 命令 函数 print 允许我们输出⼀个字符串，例如 print("hello moonbit") ⽉兔中可以通过 init 代码块来定义初始化指令 Int = { 4. println("hello moonbit") // <-- 我们⾸先执⾏命令，进⾏输出 5. 1 + 1 // <-- 之后，我们以表达式块最后的值作为表达式块的值 6. } 7. let z: Int = square(x) // 4, 输出⼀次 8. } 5 命令与副作⽤ 我们不⼀定可以放⼼替换，因此会增⼤程序理解难度 1. fn init

"oonbit") 应⽤函数时，表达式与函数定义时的参数数量应当相同，且类型⼀⼀对应 这是错误的： add_char("oonbit", 'm') 计算应⽤函数的表达式时 从左到右计算定义了参数的表达式的值 替换函数内部参数 简化表达式 6 函数的应⽤与计算 1. fn add_char(ch: Char, str: String) -> String { 2. ch.to_string() 对于这种函数，我们称为部分函数（Partial Function）；相对的，函数对类型的每个值定 义了输出的，我们称为完全函数（Total Function） 为了避免程序运⾏时因不被允许的操作中⽌，也为了区分对应合理与不合理输⼊的输 出，我们使⽤ Option[T] 这⼀数据结构 8 Option的定义 Option[T] 分为两种情况： ⽆值： None 有值： Some(value: T) 例如，我们可以⽤ Option else { Some(a / b) } 3. } [T] 代表 Option 是⼀个泛型类型，包含的数值类型为类型参数 T ，如 Option[Int] ：可能有的值类型为整数 我们将在稍后看到如何获得 Some 中的值 9 局部函数的定义 局部函数定义⼤多数时候可以省略参数类型和返回类型，亦可以省略名称（匿名函数） 1. let answer: () -> Int = fn ()

} struct PersonalInfo { name: String; age: Int} 定义结构体的值时，形如 { <字段名>: <值> , ... } let info: PersonalInfo = { name: "Moonbit", age: 1, } 结构体的值的定义不在意顺序： { age: 1, name: "Moonbit", } 如遇到字段名相同的定义⽆法区分时，可在后⾯加上类型声明以作区分 10 模式匹配 模式匹配可以匹配值（逻辑值、数字、字符、字符串）或者构造器 1. fn is_zero(i: Int) -> Bool { 2. match i { 3. 0 => true 4. 1 | 2 | 3 => false 5. _ => false 6. } 7. } 构造器中可以嵌套模式进⾏匹配，或定义标识符绑定对应结构 1. fn contains_zero(l: hd2), zip(tl, tl2)) 6. } 7. } 14 本地定义中的匹配 我们还可以在本地定义中利⽤模式进⾏匹配 let <模式> = <表达式> 此时会根据模式将表达式的值的⼦结构绑定到定义的标识符上，如： let (first, second) = (1, 2) // first == 1, second == 2 let Cons(1, x) = List::Cons(1

Int // 查看当前头元素 7. fn length(self: Queue) -> Int // 查看列表⻓度 其中 push 与 pop 均将修改 self ，为了⽅便起⻅，我们将本身作为返回值传回 1. make().push(1).push(2).push(3).pop().pop().length() // 1 3 循环队列 我们可以利⽤⼀个数组来代表队列 数组是⼀个连续的存储空间，每⼀个字段均可被修改 Queue[T] { 2. { 3. array: Array::make(5, ???), 4. start: 0, end: 0, length: 0 5. } 6. } 默认值应该是什么？ Option::None T::default() 10 单向链表 每个数据结构都指向下⼀个数据结构 像锁链⼀样相连 1. struct Node[T] { 2. val: = list.push(i) 6. } 7. println(list.length()) 8. } 16 函数调⽤栈 当我们调⽤函数时，我们进⼊⼀个新的计算环境 新的环境定义了参数的绑定 旧的环境被保留在堆栈上，在调⽤函数返回后继续进⾏运算 当我们调⽤链表⻓度函数，堆栈将会不断增⾼，直到超出内存限制 如果我们能够让旧的环境⽆需被保留，则可以解决问题 17 尾调⽤ 我们确保函数的最后⼀个运算是函数调⽤

后序遍历：先访问左⼦树，再访问右⼦树，再访问根节点 [3, 5, 4, 1, 2, 0] ⼴度优先遍历： [0, 1, 2, 3, 4, 5] 11 深度优先遍历：查找为例 我们想要在树的节点中查找是否有特定的值 结构化递归 先对基本情形进⾏处理：空树 再对递归情形进⾏处理，并递归 1. fn dfs_search(target: Int, tree: IntTree) -> Bool { 2. match 前序、中序、后序遍历只是改变顺序 12 逻辑值的短路运算 短路运算：当发现当前求解值可以被确定，则中断计算并返回结果 let x = true || { abort("程序中⽌") } ：因为 true || 任何值 均为真，因 此不会计算 || 右侧表达式 let y = false && { abort("程序中⽌") } ：因为 false && 任何值 均为假， 因此不会计算 && 右侧表达式 assert(head == Some(1)) 4. assert(tail == enqueue(empty(), 2)) 16 ⼴度优先遍历：查找为例 我们想要在树的节点中查找是否有特定的值 1. fn bfs_search(target: Int, queue: Queue[IntTree]) -> Bool { 2. match pop(queue) { 3. (None

Array[(Key, Value)], key: Key, value: Value 2. let index = key.hash().mod_u(a.length()) // 键值--哈希-->哈希值--取模-->数组索引 3. a[ index ] = value // 添加或更新 4. let value = a[ index ] // 查询 理想情况下，操作均为常数时间（⼆叉平衡树操作均为对数时间） 当发⽣哈希/索引冲突时，将相同索引的数据装进⼀个数据结构中 例：添加0、5（哈希值分别为0、5）⾄⻓度为5的数组中时： 0 5 5 哈希表：直接寻址 哈希表结构 1. struct Entry[K, V] { // 存储键值对 2. key : K 3. mut value : V // 允许原地修改值 4. } 5. 6. struct Bucket[V] { // 存储键值对的集合 mut size : Int // 哈希表键值对数量，动态维护 14. } 6 哈希表：直接寻址 添加/更新操作 添加时，根据键的哈希计算出应当存放的位置 遍历集合查找键 如果找到，修改值 否则，添加键值对 删除操作类同 0 3 1. 计算对应数组索引 4 9 2.遍历对应数据结构 7 哈希表：直接寻址 添加/更新操作 1. fn put[K : Hash + Eq

我们定义⼀个更⼀般的⼆叉搜索树，允许存放任意类型的数据 1. enum Tree[T] { 2. Empty 3. Node(T, Tree[T], Tree[T]) 4. } 5. 6. // 我们需要⼀个⽐较函数来⽐较值的⼤⼩以了解顺序 7. // 负数表示⼩于，0表示等于，正数表示⼤于 8. fn insert[T](self: Tree[T], value: T, compare: (T, T) -> Int) -> Tree[T] 9. fn delete[T](self: Tree[T], value: T, compare: (T, T) -> Int) -> Tree[T] 第⼋课：定义循环队列 我们需要类型的默认值来初始化数组 1. fn make[T](default: T) -> Queue[T] { 2. { array: Array::make(5, default), start: 0, end: 0, length: 0 } 3. } 2 ⽅法 我们注意到⼀些与类型相关联的函数 类型的⽐较： fn T::compare(self: T, other: T) -> Int 类型的默认值： fn T::default() -> T 类型的输出： fn T::to_string(self: T) -> String …… 我们将这类函数称为⽅法 3 接⼝ Trait 我们通过接⼝定义⼀系列⽅法的实现需求

堆栈虚拟机：运算数存储在栈上，数据遵循先进后出原则 寄存器虚拟机：运算数存储在寄存器中 3 寄存器虚拟机 例：Lua VM (The Implementation of Lua 5.0) 取最⼤值 MOVE 2 0 0 ; R(2) = R(0) LT 0 0 1 ; R(0) < R(1)? JMP 1 ; JUMP -> 5 (4 + 1) MOVE 2 1 R(1) RETURN 2 2 0 ; return R(2) RETURN 0 1 0 ; return 4 堆栈虚拟机 例：WebAssembly Virtual Machine 取最⼤值 fn max(a : Int, b : Int) -> Int 1. local.get $a local.set $m ;; let mut m = a 2 4. Call(String) // 函数调⽤ 5. Local_Get(String); Local_Set(String) // 取值、设值 6. If(Int, List[Instruction], List[Instruction]) // 条件判断 7. } 8 类型定义 函数 1. struct Function { 2

⽜顿迭代法求函数解： 我们今天研究简单的函数组合 例： 12 微分 函数微分的⼏种⽅式 ⼿动微分：纯天然计算器 缺点：对于复杂表达式容易出错 数值微分： 缺点：计算机⽆法精准表达⼩数，且绝对值越⼤，越不精准 符号微分： Mul(Const(2), Var(1)) -> Const(2) 缺点：计算结果可能复杂；可能重复计算；难以直接利⽤语⾔原⽣控制流 1. // 需要额外定义原⽣算⼦以实现相同效果 value() { x } else { y } 4. } 13 微分 函数微分的⼏种⽅式 ⼿动微分：纯天然计算器 缺点：对于复杂表达式容易出错 数值微分： 缺点：计算机⽆法精准表达⼩数，且绝对值越⼤，越不精准 符号微分： Mul(Const(2), Var(1)) -> Const(2) 缺点：计算结果可能复杂；可能重复计算；难以直接利⽤语⾔原⽣控制流 ⾃动微分：利⽤复合函数求导法则、由基本运算组合进⾏微分 op_add(Self, Self) -> Self 4. op_mul(Self, Self) -> Self 5. value(Self) -> Double // 获取当前计算值 6. } 可以利⽤语⾔原⽣的控制流计算，动态⽣成计算图 1. fn max[N : Number](x : N, y : N) -> N { 2. if x.value() > y