# 现代编程思想 接口 Hongbo Zhang ## 回顾 ## • 第六课：定义平衡二叉树 我们定义一个更一般的二叉搜索树，允许存放任意类型的数据 1. enum Tree[T] { 2. Empty 3. Node(T, Tree[T], Tree[T]) 4. } 5. 6. // 我们需要一个比较函数来比较值的大小以了解顺序 7. // 负数表示小于，0表示等于，正数表示大于

现代编程思想 案例：自动微分 Hongbo Zhang ## 微分 • 微分被应用于机器学习领域 ◦ 利用梯度下降求局部极值 牛顿迭代法求函数解： $ x^{3}-10x^{2}+x+1=0 $ • 我们今天研究简单的函数组合 ○ 例： $ f(x_{0},x_{1})=5x_{0}^{2}+x_{1} $ ■ $ f(10,100)=600 $ ■ $ \frac{\partial ■ 缺点：计算机无法精准表达小数，且绝对值越大，越不精准 符号微分：Mul(Const(2), Var(1)) -> Const(2) ■ 缺点：计算结果可能复杂；可能重复计算；难以直接利用语言原生控制流 1. // 需要额外定义原生算子以实现相同效果 2. fn max[N : Number](x : N, y : N) -> N { 3. if x.value() < ■ 缺点：计算机无法精准表达小数，且绝对值越大，越不精准 符号微分：Mul(Const(2), Var(1)) -> Const(2) ■ 缺点：计算结果可能复杂；可能重复计算；难以直接利用语言原生控制流 ◦ 自动微分：利用复合函数求导法则、由基本运算组合进行微分 ■ 分为前向微分和后向微分 ## 符号微分 ## • 我们以符号微分定义表达式构建的一种语义 1. enum Symbol

## 现代编程思想 ## 案例：基于梯度下降的神经网络 Hongbo Zhang ## 案例：鸢尾花 • 鸢尾花数据集是机器学习中的"Hello World" ☐ 1936年发布 包含对3种鸢尾花的测量，各有50个样本 ☐ 每个样本包含4项特征：花萼与花瓣的长度和宽度 目标 ☐ 通过特征，判断属于哪一类鸢尾花 ◦ 构建并训练神经网络，正确率95%以上 ## 神经网络

## 现代编程思想 案例：栈式虚拟机 Hongbo Zhang ## 编译与解释 ## • 编译 ☐ 源程序 x 编译器 -> 目标程序 ☐ 目标程序 x 输入数据 -> 输出数据 ## • 解释 ☐ 源程序 x 输入数据 x 解释器 -> 输出数据 ☐ CPU可以被视为广义上的解释器 • 拓展阅读：二村映射/部分计算 ◦ 部分计算：程序优化，根据已知信息，运算进行特化

现代编程思想 # 函数, 列表与递归 Hongbo Zhang 基本数据类型：函数 ## 函数 - 在数学上，描述对应关系的一种特殊集合。对于特定的输入，总是有特定的输出 - 在计算机中，对相同运算的抽象，避免大量重复定义 ○ 计算半径为1的圆的面积： $ 3.1415 \times 1 \times 1 $ ○ 计算半径为2的圆的面积： $ 3.1415 \times 2 \times // 42 (String) -> Int real_answer("Ultimate Question") 函数在月兔中是“一等公民”：可以将函数作为参数、返回值，亦可以绑定或存储函数。我们将在后续课程中深入学习。 ## 函数的类型 (<参数类型>，<参数类型>，<参数类型>，...) -> <返回值类型> • () let result_2 = aux(num - 2) 9. // 通过 <变量> = <值> 修改绑定的值 10. map = put(map, num, result_1 + result_2) 11.

现代编程思想 命令式编程 Hongbo Zhang ## 函数式编程 - 到此为止，我们介绍的可以归类于函数式编程的范畴 - 对每一个输入，有着固定的输出 对于标识符，我们可以直接用它所对应的值进行替代——引用透明性 • 开发实用的程序，我们需要一些计算之外的“副作用” ☐ 进行输入输出 ☐ 修改内存中的数据等 ☐ 这些副作用可能导致多次执行的结果不一致 ## 引用透明性 引用透明性 • 我们可以定义如下数据绑定和函数 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 - 引用透明性可以易于理解 ## struct Ref[T] { mut val : T } 2. 3. fn init { 4. let ref: Ref[Int] = { val: 1 } // ref 本身只是一个数据绑定 5. ref.val = 10 // 我们可以修改结构体的字段 6. println(ref.val.to_string() // 输出 10 7. } ## 变量 • 我们可以将带有可变字段的结构体看作是引用

现代编程思想 哈希表与闭包 Hongbo Zhang ## 回顾 ## · 表 键值对的集合，其中键不重复 简单实现：二元组列表 - 添加时向队首添加 - 查询时从队首遍历 树实现：二叉平衡树 - 基于第五节课介绍的二叉平衡树，每个节点的数据为键值对 - 对树操作时比较第一个参数 ## 哈希表 - 哈希函数/散列函数 Hash function ◦

现代编程思想 # 泛型与高阶函数 Hongbo Zhang ## 设计良好的抽象 - 软件工程中，我们要设计良好的抽象 - 当代码多次重复出现 ☐ 当抽出的逻辑具有合适的语义 - 编程语言为我们提供了各种抽象的手段 - 函数、泛型、高阶函数、接口..... ## 泛型函数与泛型数据 ## 堆栈 - 栈是一个由一系列对象组成的一个集合，这些对象的插入和删除遵循后进先出原则（Last

# 现代编程思想 多元组，结构体与枚举类型 Hongbo Zhang 基础数据类型：多元组与结构体 ## 回顾：多元组 • 多元组：固定长度的不同类型数据的集合 ☐ 定义： $ (\leq $ 表达式 $ \gt $ , $ \leq $ 表达式 $ \gt $ , $ \geq $ ) ☐ 类型：(<表达式类型>，<表达式类型>，...) ○ 例如： ■ 身份信息：("Bob" true 4. 1 | 2 | 3 => false 5. _ => false 6. } 7. } • 构造器中可以嵌套模式进行匹配，或定义标识符绑定对应结构 1. fn contains_zero(l: List[Int]) -> Bool { 2. match l { 3. Nil => false 4. tl2)) 6. } 7. } ## 本地定义中的匹配 我们还可以在本地定义中利用模式进行匹配 • let <模式> = <表达式> 此时会根据模式将表达式的值的子结构绑定到定义的标识符上，如： • let (first, second) = (1, 2) // first == 1, second == 2 • let Cons(1, x) = List::Cons(1

## 现代编程思想 队列：可变数据结构实现 Hongbo Zhang ## 队列 - 我们曾经介绍过队列这个数据结构 - 先进先出 ☐ 利用两个堆栈进行实现 - 我们利用可变数据结构进行实现 - 基于数组的循环队列 ☐ 单向链表 ## 队列 • 我们实现以下函数（以整数队列为例） 1. struct Queue { ... } 2. 3. fn make() -> stack size exceeded [INFO] program exited in 0.016s ## 函数调用栈 - 当我们调用函数时，我们进入一个新的计算环境 - 新的环境定义了参数的绑定 旧的环境被保留在堆栈上，在调用函数返回后继续进行运算 - 当我们调用链表长度函数，堆栈将会不断增高，直到超出内存限制。如果我们能够让旧的环境无需被保留，则可以解决问题 ## 尾调用 - 我们确保函数的最后一个运算是函数调用