现代编程思想 函数, 列表与递归 Hongbo Zhang 1 基本数据类型：函数 2 函数 在数学上，描述对应关系的⼀种特殊集合 对于特定的输⼊，总是有特定的输出 在计算机中，对相同运算的抽象，避免⼤量重复定义 计算半径为1的圆的⾯积： 3.1415 * 1 * 1 计算半径为2的圆的⾯积： 3.1415 * 2 * 2 计算半径为3的圆的⾯积： 3.1415 * 3 * * 3 …… fn ⾯积(半径: Double) -> Double { 3.1415 * 半径 * 半径 } 3 函数 计算半径为1、2、3的圆的⾯积： 1. let surface_r_1: Double = { let r = 1.0; pi * r * r } 2. let surface_r_2: Double = { let r = 2.0; pi * r * r } 3. let surface_r_3) 使⽤函数后 1. fn area(radius: Double) -> Double { pi * radius * radius } 2. let result = (area(1.0), area(2.0), area(3.0)) 4 顶层函数的定义 fn <函数名> (<参数名>: <类型>, <参数名>: <类型>, ...) -> <类型> <表达式块> 定义的函数接⼝让其他使⽤者⽆需关注内部实现

现代编程思想 泛型与⾼阶函数 Hongbo Zhang 1 设计良好的抽象 软件⼯程中，我们要设计良好的抽象 当代码多次重复出现 当抽出的逻辑具有合适的语义 编程语⾔为我们提供了各种抽象的⼿段 函数、泛型、⾼阶函数、接⼝…… 2 泛型函数与泛型数据 3 堆栈 栈是⼀个由⼀系列对象组成的⼀个集合，这些对象的插⼊和删除遵循后进先出原则 （Last In First Out） Empty) 10. NonEmpty(top, rest) => (Some(top), rest) 11. } 12. } 事实上，⽉兔中的列表就是⼀个堆栈 6 字符串堆栈 除了存储整数，我们也会希望存储字符串 1. enum StringStack { 2. Empty 3. NonEmpty(String, StringStack) 4. } 5. fn StringStack::empty() } 12. } 我们希望存储很多很多类型在堆栈中 每个类型都要定义⼀个对应的堆栈吗？ IntStack 和 StringStack 似乎结构⼀模⼀样？ 7 泛型数据结构与泛型函数 泛型数据结构与泛型函数以类型为参数，构建更抽象的结构 1. enum Stack[T] { 2. Empty 3. NonEmpty(T, Stack[T]) 4. } 5. fn Stack::empty[T]()

untu等环境），并参考⽉ 兔构建系统教程 7 ⽉兔中的表达式 8 ⼀个典型的⽉兔程序 1. //顶层函数定义 2. fn num_water_bottles(num_bottles: Int, num_exchange: Int) -> Int { 3. // 本地函数定义 4. fn consume(num_bottles, num_drunk) { 5. // 条件表达式 num_bottles = num_bottles - num_exchange + 1 9. let num_drunk = num_drunk + num_exchange 10. // 函数运算 11. consume(num_bottles, num_drunk) 12. } else { 13. num_bottles + num_drunk 14. ⽉兔的编译器会在运⾏前使⽤类型推导来确认程序是否正确使⽤类型 ⽉兔的开发⼯具可以在开发时实时提示检查到的类型错误 图中的错误源于字符串与数字不能直接相加 14 ⽉兔的基本数据类型 逻辑值（布尔值） 整数（整型、⻓整形） 浮点数（单精度浮点数、双精度浮点数） 字符与字符串 多元组 …… 15 逻辑值（布尔值） ⽉兔中逻辑值的类型为 Bool 逻辑值只有两个可能值： true false

Call(String) // 函数调⽤ 5. Local_Get(String); Local_Set(String) // 取值、设值 6. If(Int, List[Instruction], List[Instruction]) // 条件判断 7. } 8 类型定义 函数 1. struct Function { 2. name : Local_Get("a"), Local_Get("b"), Add ] 函数参数及本地变量可通过 Local_Get 获取、 Local_Set 修改 …… Local_Get("a") 1 …… Local_Get("b") 1 2 …… Add 1 + 2 …… 1 a b 2 11 函数计算 例： add(1, 2) 1. Lists::[ Const(1), Call("add") ] 在栈上存储函数的返回值数量 …… Const(1) 1 …… Const(2) 1 2 …… Call("add") 1 …… 2 Function(1) a b 12 函数计算 例： add(1, 2) 1. Lists::[ Const(1), Const(2), Call("add") ] 在栈上存储函数的返回值数量 …… 3 Function(1)

语法分析 对输⼊⽂本进⾏分析并确定其语法结构 通常包含词法分析和语法分析 本节课均利⽤语法解析器组合⼦（parser combinator）为例 2 词法分析 将输⼊分割为单词 输⼊：字符串/字节块 输出：单词流 例如： "12 +678" -> [ Value(12), Plus, Value(678) ] 通常可以通过有限状态⾃动机完成 ⼀般⽤领域特定语⾔定义后，由软件⾃动⽣成程序 算术表达式的词法定义 1. Number = %x30 / (%x31-39) *(%x30-39) 2. Plus = "+" 每⼀⾏对应⼀个匹配规则 "xxx" ：匹配内容为xxx的字符串 a b ：匹配规则a，成功后匹配规则b a / b ：匹配规则a，匹配失败则匹配规则b *a ：重复匹配规则a，可匹配0或多次 %x30 ：UTF编码⼗六进制表示为30的字符（ "0" ） .many() 5. 6. fn init { 7. debug(tokens.parse("-10123-+-523 103 ( 5) ) ")) 8. } 我们成功地分割了字符串 - 10123 - + - 523 103 ( 5 ) ) 但这不符合数学表达式的语法 13 语法分析 对单词流进⾏分析，判断是否符合语法 输⼊：单词流 输出：抽象语法树 1. expression

Hongbo Zhang 1 函数式编程 到此为⽌，我们介绍的可以归类于函数式编程的范畴 对每⼀个输⼊，有着固定的输出 对于标识符，我们可以直接⽤它所对应的值进⾏替代⸺引⽤透明性 开发实⽤的程序，我们需要⼀些计算之外的�副作⽤� 进⾏输⼊输出 修改内存中的数据等 这些副作⽤可能导致多次执⾏的结果不⼀致 2 引⽤透明性 我们可以定义如下数据绑定和函数 1. let x: Int * 2 } // 4 引⽤透明性可以易于理解 3 命令 函数 print 允许我们输出⼀个字符串，例如 print("hello moonbit") ⽉兔中可以通过 init 代码块来定义初始化指令 可以简单理解为程序主⼊⼝ 1. fn init { 2. println("hello moonbit") // 函数名中的ln代表换⾏ 3. } 4 命令与副作⽤ 输出命令可能会破坏引⽤透明性 它仅有⼀个值： () 以 Unit 为运算结果类型的函数或命令⼀般有副作⽤ fn print(String) -> Unit fn println(String) -> Unit 命令的类型也是单值类型 1. fn do_nothing() { // 返回值为单值类型时可以省略返回类型声明 2. let _x = 0 // 结果为单值类型，符合函数定义 3. } 7 变量 在⽉兔中，我们可以在代码块中⽤

对树操作时⽐较第⼀个参数 2 哈希表 哈希函数/散列函数 Hash function 将任意⻓度的数据映射到某⼀固定⻓度的数据 在⽉兔的 Hash 接⼝中，数据被映射到整数范围内 trait Hash { hash(Self) -> Int } "这是⼀个⾮常⾮常⻓的字符串".hash() == -900478401 哈希表 利⽤哈希函数，将数据映射到数组索引中，进⾏快速的添加、查询、修改 添加/更新时，根据键的哈希计算出应当存放的位置 如果该位置被占⽤ 如果是对应的键，则更新对应的值 否则，向后查找 如果找到空位，则存放键值对 我们默认空位的存在 13 哈希表：开放寻址 辅助函数：查找键是否存在 如果存在，返回键的索引；如果不存在，则返回第⼀个空位所在位置 1. // 从键的哈希值向右查找，返回所查找的键或第⼀个找到的空位位置的索引 2. fn find_slot[K : Default](map : HT_open[K, V], key : K, value : V) -> Unit { 2. let index = find_slot(map, key) // 利⽤辅助函数进⾏查找 3. if map.occupied[index] { // 判断是找到了对应键还是找到了空位 4. map.values[index].value = value // 找到了对应的键则进⾏更新

option_int { 3. None => default 4. Some(value) => value 5. } 6. } 10 模式匹配 模式匹配可以匹配值（逻辑值、数字、字符、字符串）或者构造器 1. fn is_zero(i: Int) -> Bool { 2. match i { 3. 0 => true 4. 1 | 2 | 3 => false 5 enum Repeat1 { A; B } 2. enum Repeat2 { A; B } 3. let x: Repeat1 = Repeat1::A 19 枚举类型的意义 对⽐⼀下两个函数，枚举类型可以与现有类型区分开，更好地实现抽象 1. fn tomorrow(today: Int) -> Int 2. fn tomorrow(today: DaysOfWeek) -> DaysOfWeek

⽜顿迭代法求函数解： 我们今天研究简单的函数组合 例： 2 ⽜顿迭代法 3 ⽜顿迭代法 4 ⽜顿迭代法 5 ⽜顿迭代法 6 ⽜顿迭代法 7 ⽜顿迭代法 8 ⽜顿迭代法 9 ⽜顿迭代法 10 ⽜顿迭代法 11 微分 微分被应⽤于机器学习领域 利⽤梯度下降求局部极值 ⽜顿迭代法求函数解： 我们今天研究简单的函数组合 例： 12 微分 函数微分的⼏种⽅式 y } 4. } 13 微分 函数微分的⼏种⽅式 ⼿动微分：纯天然计算器 缺点：对于复杂表达式容易出错 数值微分： 缺点：计算机⽆法精准表达⼩数，且绝对值越⼤，越不精准 符号微分： Mul(Const(2), Var(1)) -> Const(2) 缺点：计算结果可能复杂；可能重复计算；难以直接利⽤语⾔原⽣控制流 ⾃动微分：利⽤复合函数求导法则、由基本运算组合进⾏微分 分为前向微分和后向微分 -> Symbol { Mul(f1, f2) } 13. 14. // 计算函数值 15. fn Symbol::compute(f : Symbol, input : Array[Double]) -> Double { ... } 15 符号微分 利⽤函数求导法则，我们计算函数的（偏）导数 如果 为常值函数 ⽉兔实现 1. fn differentiate(self : Symbol

Hongbo Zhang 1 队列 我们曾经介绍过队列这个数据结构 先进先出 利⽤两个堆栈进⾏实现 我们利⽤可变数据结构进⾏实现 基于数组的循环队列 单向链表 2 队列 我们实现以下函数（以整数队列为例） 1. struct Queue { .. } 2. 3. fn make() -> Queue // 创建空列表 4. fn push(self: Queue, t: Int) Some(node) 10. self.tail = Some(node) 11. } 12. } 13. self 14. } 14 单向链表⻓度 我们写⼀个简单的判定⻓度的递归函数 我们使⽤递归从头开始沿着引⽤链访问所有的节点 1. fn length[T](self: LinkedList[T]) -> Int { 2. fn aux(node: Option[Node[T]]) length()) 8. } 16 函数调⽤栈 当我们调⽤函数时，我们进⼊⼀个新的计算环境 新的环境定义了参数的绑定 旧的环境被保留在堆栈上，在调⽤函数返回后继续进⾏运算 当我们调⽤链表⻓度函数，堆栈将会不断增⾼，直到超出内存限制 如果我们能够让旧的环境⽆需被保留，则可以解决问题 17 尾调⽤ 我们确保函数的最后⼀个运算是函数调⽤ 若为函数本身，则称为尾递归 函数调⽤的结果即最终的运算结果