现代编程思想 函数, 列表与递归 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） } 12. } 我们希望存储很多很多类型在堆栈中 每个类型都要定义⼀个对应的堆栈吗？ IntStack 和 StringStack 似乎结构⼀模⼀样？ 7 泛型数据结构与泛型函数 泛型数据结构与泛型函数以类型为参数，构建更抽象的结构 1. enum Stack[T] { 2. Empty 3. NonEmpty(T, Stack[T]) 4. } 5. fn Stack::empty[T]() 泛型数据结构与泛型函数 我们⽤ [<类型1>, <类型2>, ...] 来定义泛型的类型参数 enum Stack[T]{ Empty; NonEmpty(T, Stack[T]) } struct Pair[A, B]{ first: A; second: B } fn identity[A](value: A) { value } Stack 与 Pair 可以看做从类型上的函数：类型构造器

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)

⽜顿迭代法求函数解： 我们今天研究简单的函数组合 例： 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 尾调⽤ 我们确保函数的最后⼀个运算是函数调⽤ 若为函数本身，则称为尾递归 函数调⽤的结果即最终的运算结果

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 变量 在⽉兔中，我们可以在代码块中⽤

4. (self.0)(tokens) 5. } ⼤部分组合⼦与 Lexer[V] 类似 递归组合： atomic = Value / "(" expression ")" 延迟定义 递归函数 18 递归定义 延迟定义 利⽤引⽤定义 Ref[Parser[V]] ： struct Ref[V] { mut val : V } 在定义其他解析器后更新引⽤中内容 1. fn Pa }) 19. 20. expression_ref.val 21. } 20 递归定义 递归函数 解析器本质上是⼀个函数 定义互递归函数后，将函数装进结构体 1. fn recursive_parser() -> Parser[Expression] { 2. // 定义互递归函数 3. // atomic = Value / "(" expression ")" 4. fn List[Token]) -> Option[(Expression, List[Token])] { 5. lparen.and( 6. Parser(expression) // 引⽤函数 7. ).and(rparen).map(fn { ((_, expr), _) => expr}) 8. .or(number).parse(tokens) 9. } 10

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. Int, Int) 可以通过从0开始的下标访问数据 (2023, 10, 24).0 == 2023 (2023, 10, 24).1 == 10 20 其他数据类型 ⽉兔有丰富的类型结构 函数类型 op_add : (Int, Int) -> Int 单值类型 (): Unit 列表类型 List::Cons(1, Nil): List[Int] …… 我们会在后续课程中⻅到它们，以及⾃定义数据结构

对树操作时⽐较第⼀个参数 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 // 找到了对应的键则进⾏更新

隐含层的层数、节点数、连接⽅式 神经元的激活函数等 4 神经⽹络架构 输⼊：每个样本包含4个特征，四个输⼊ 输出：属于每⼀种类的可能性，三个输出 样本数：150（总共） ⽹络架构：前馈神经⽹络 输⼊层：四个节点 输出层：三个节点 隐含层：⼀层四个节点 全连接：每⼀个神经元与前⼀层所有神经元相连 5 神经元 , ：参数 ：输⼊ 激活函数 隐含层：线性整流函数 ReLU 当计算值⼩于零，不激活神经元 Self) -> Self 7. op_div(Self, Self) -> Self 8. exp(Self) -> Self // ⽤于计算softmax 9. } 7 神经⽹络实现 激活函数 1. fn reLU[T : Base](t : T) -> T { 2. if t.value() < 0.0 { T::constant(0.0) } else { t } 3. } 4 outputs |> softmax 10. } 10 神经⽹络训练 损失函数 评估当前结果与预期结果之间的�差距� 我们选择交叉熵 梯度下降 梯度决定参数的调整⽅向 学习率 学习率决定参数的调整幅度 我们选择指数下降，逐渐逼近 11 神经⽹络训练 多分类问题交叉熵： ：事件； ： 发⽣的概率 损失函数：基于抽象的定义 1. trait Log { 2. log(Self)