现代编程思想 函数, 列表与递归 Hongbo Zhang 1 基本数据类型：函数 2 函数 在数学上，描述对应关系的⼀种特殊集合 对于特定的输⼊，总是有特定的输出 在计算机中，对相同运算的抽象，避免⼤量重复定义 计算半径为1的圆的⾯积： 3.1415 * 1 * 1 计算半径为2的圆的⾯积： 3.1415 * 2 * 2 计算半径为3的圆的⾯积： 3.1415 * 3 * 11 数据类型：列表 12 列表：⼀个数据的序列 我们有时会收到⼀些数据，具备以下特征： 数据是有序的 数据是可以重复的 数据的数量是不定的 举例来说 ⼀句话中的⽂字：� '⼀' '句' '话' '中' '的' '⽂' '字' � DNA序列：� G A T T A C A � …… 13 列表的接⼝ 我们定义⼀个单向不可变列表 以整数的列表为例（暂名之 IntList 返回⼀个空列表 cons : (Int, IntList) -> IntList 向列表添加⼀项 解构 head_opt : IntList -> Option[Int] 获得第⼀项 tail : IntList -> IntList 获得除第⼀项以外的项 14 列表的接⼝ 测试案例 1. let empty_list:

部分计算：程序优化，根据已知信息，运算进⾏特化 已知源程序与解释器，进⾏部分运算，获得⽬标程序 ⽬标程序 x 输⼊数据 -> 输出数据 2 虚拟机 ⼀处编写，处处运⾏ 定义⼀个不基于任何平台的指令集 在不同平台上实现解释器 两种常⻅的虚拟机 堆栈虚拟机：运算数存储在栈上，数据遵循先进后出原则 寄存器虚拟机：运算数存储在寄存器中 3 寄存器虚拟机 例：Lua VM (The Implementation WebAssembly WebAssembly是什么？ ⼀个虚拟指令集 可以在浏览器以及其他运⾏时（Wasmtime WAMR WasmEdge等）中运⾏ MoonBit的第⼀个后端 WebAssembly指令集的⼦集为例 6 简单指令集 数据 只考虑32位有符号整数 ⾮零代表 true ，零代表 false 指令 数据操作： const add minus equal modulo 数据存储： local.get local.set 控制流： if/else call 7 类型定义 数据 1. enum Value { I32(Int) } // 只考虑32位有符号整数 指令 1. enum Instruction { 2. Const(Int) // 常数 3. Add; Sub; Modulo; Equal

2 } // 4 引⽤透明性可以易于理解 3 命令 函数 print 允许我们输出⼀个字符串，例如 print("hello moonbit") ⽉兔中可以通过 init 代码块来定义初始化指令 可以简单理解为程序主⼊⼝ 1. fn init { 2. println("hello moonbit") // 函数名中的ln代表换⾏ 3. } 4 命令与副作⽤ 输出命令可能会破坏引⽤透明性 loop_(i + 1) 5. } else { () } 6. } 7. loop_(0) 18 循环流的控制 循环的时候，可以提前中⽌循环，或是跳过后续命令的执⾏ break 指令可以中⽌循环 continue 指令可以跳过后续运⾏，直接进⼊下⼀次循环 1. fn print_first_3() { 2. let mut i = 0 3. while i < 10, i = i + 1 println(i.to_string()) 8. } 9. } 10. } 19 循环流的控制 循环的时候，可以提前中⽌循环，或是跳过后续命令的执⾏ break 指令可以中⽌循环 continue 指令可以跳过后续运⾏，直接进⼊下⼀次循环 1. fn print_skip_3() { 2. let mut i = 0 3. while i < 10, i = i + 1

WASM 特性，基本只当作 ISA（指令集） • 绕过 WASM 低级概念，转而使用语言的高级概念 • 牺牲语言互换性，换取 WASM 下立刻应用高级特性 关注点分离（1） 高级语言代码 （高级语言层面提供 内部互联与模块化） WASM 部署文件 （将指令集限制在 WASM 1.0 和有限几 个扩展的限度） 后端运行时 （WASM虚拟机 基础的指令集） 构建 内部 互联 运行

Empty => (None, Empty) 10. NonEmpty(top, rest) => (Some(top), rest) 11. } 12. } 事实上，⽉兔中的列表就是⼀个堆栈 6 字符串堆栈 除了存储整数，我们也会希望存储字符串 1. enum StringStack { 2. Empty 3. NonEmpty(String, StringStack) 尝试取出⼀个元素，并返回剩余队列；若为空则为本身 4. fn pop[T](q: Queue[T]) -> (Option[T], Queue[T]) 我们可以⽤⼀个列表（堆栈）模拟队列，但是效率低下 在队尾添加元素需要重新构建整个列表 Cons(1, Cons(2, Nil)) => Cons(1, Cons(2, Cons(3, Nil))) 10 泛型数据结构：队列 我们⽤两个堆栈模拟队列 省略实现 23. } 14 ⾼阶函数 15 ⼀些列表操作 我们要求⼀个整数列表的和 1. fn sum(list: List[Int]) -> Int { 2. match list { 3. Nil => 0 4. Cons(hd, tl) => hd + sum(tl) 5. } 6. } 我们要求⼀个列表⻓度 1. fn length[T](list: List[T])

身份信息： ("Bob", 2023, 10, 24): (String, Int, Int, Int) 成员访问： <多元组>.<索引> ： (2023, 10, 24).0 == 2023 列表：任意⻓度的相同类型数据的集合 例如： 字符的序列： Cons('H', Cons('i', Cons('!', Nil))) Cons ： construct 的缩写 3 笛卡尔积 ⼀ // DO NOT COMPILE 7. let accepted: Bool = accept(({other: 2, val: 1}: A)) 9 模式匹配 回顾：我们可以通过模式匹配查看列表和Option的结构 1. fn head_opt(list: List[Int]) -> Option[Int] { 2. match list { 3. Nil => None 4 3. { age: 0, .. } => None 4. { name, age } => Some(name) 5. } 6. } 12 缝合列表 我们试图缝合两个列表，⽣成⼀个数字与字符的⼆元组的列表，以最短者为准 1. fn zip(l1: List[Int], l2: List[Char]) -> List[(Int ,Char)] { 2. match (l1

表的简易实现 利⽤列表+⼆元组存储键值对 添加/更新时向列表前添加键值对 查询时从列表前开始，找到键即返回 简易实现需要判断存储的键值对是否为搜索的键 键应当满⾜相等接⼝ 1. fn get[Key: Eq, Value](map: Map[Key, Value], key: Key) -> Option[Value] 11 表：利⽤接⼝实现 我们以列表+⼆元组作为表 1. // let Map(original_map) = map 10. Map( Cons( (key, value), original_map ) ) 11. } 12 表：利⽤接⼝实现 我们以列表+⼆元组作为表 1. fn get[Key: Eq, Value](map : Map[Key, Value], key : Key) -> Option[Value] { 2. fn aux(list

现代编程思想 哈希表与闭包 Hongbo Zhang 1 回顾 表 键值对的集合，其中键不重复 简单实现：⼆元组列表 添加时向队⾸添加 查询时从队⾸遍历 树实现：⼆叉平衡树 基于第五节课介绍的⼆叉平衡树，每个节点的数据为键值对 对树操作时⽐较第⼀个参数 2 哈希表 哈希函数/散列函数 Hash function 将任意⻓度的数据映射到某⼀固定⻓度的数据 在⽉兔的 Hash ） 3 哈希冲突 根据抽屉原理/鸽巢原理/⽣⽇问题 不同数据的哈希可能相同 不同的哈希映射为数组索引时可能相同 解决哈希表的冲突 直接寻址（分离链接）：同⼀索引下⽤另⼀数据结构存储 列表 ⼆叉平衡搜索树等 开放寻址 线性探查：当发现冲突后，索引递增，直到查找空位放⼊ ⼆次探查（索引递增 ）等 4 哈希表：直接寻址 当发⽣哈希/索引冲突时，将相同索引的数据装进⼀个数据结构中 允许原地进⾏增删操作 8. } 9. 10. struct HT_bucket[K, V] { 11. mut values : Array[Bucket[Entry[K, V]]] // 存放键值对的列表，存放列表的数组 12. mut length : Int // 数组⻓度，动态维护 13. mut size : Int // 哈希表键值对数量，动态维护 14. } 6 哈希表：直接寻址

-> Queue // 创建空列表 4. fn push(self: Queue, t: Int) -> Queue // 添加元素 5. fn pop(self: Queue) -> Queue // 删除元素 6. fn peek(self: Queue) -> Int // 查看当前头元素 7. fn length(self: Queue) -> Int // 查看列表⻓度 其中 push 与 self.start = (self.start + 1) % self.array.length() 4. self.length = self.length - 1 5. self 6. } 列表⻓度⼀直被动态维护 1. fn length(self: Queue) -> Int { 2. self.length 3. } 9 循环队列：泛型版本 我们希望存储不⽌整数 1. fn

语法轻量，易上⼿ 浏览器开发环境、云原⽣开发环境或本地集成开发环境 4 课程概览 课程 主题 课程 主题 课程介绍与程序设计 接⼜：集合与表 ⾯向值编程 结构体 命令 函数 列表与递归 可变状态 与可变数据结构 列表 元组 嵌套模式 抽象堆栈结构机器 数据类型与树 可变队列 树与⼆分查找 迭代与尾递归 ⼆叉搜索树的插⼊与删除 闭包与对象 泛型与⾼阶函数 案例：句法分析器与程序解释器